I decided that it was time to release into the wild the improvements I’ve made. Please report any bugs you encounter with the faster rendering* or the faster maze generation.

To show just how much faster the mazes generate on my computer, I’ve created the following two graphs. Now, this is on a relatively anemic system (1.8GHz Athlon XP with 768MB of DDR266) when compared to new computers, so your results may very well be much faster.

* Note: There seems to be a problem with the open source NVIDIA drivers and the new rendering algorithm. As of yet, I have not been able to track it down. I am sorry for any inconvenience this may cause you.

While optimizing the Prim algorithm I ran into a annoying situation. I couldn’t make the mazes match between the faster implementation and the original one. I triple checked the logic. I scoured the lines of code. Nothing seemed to be wrong! In the end I decided to have the old version print out exactly which cells it was checking, because it obviously wasn’t doing what it was supposed to. And it wasn’t. Here’s where things were going awry:

void PrimMaze::moveNeighbors(const QPoint& cell)
{
	int size = m_out.size();
	for (int i = 0; i < size; ++i) {
		if (areNeighbors(cell, m_out.at(i))) {
			m_frontier.append(m_out.takeAt(i));
			--size;
		}
	}
}

The code looks simple enough. The problem is that I didn’t decrement the counter along with the size, so it was skipping cells. Because of this the mazes generated by the current implementation of the Prim algorithm are actually wrong. The new implementation does not suffer from the bug, and it would make the new code messy (and slower) to try and recreate it.

This means that when I release the next version of CuteMaze any saved gave that uses the Prim algorithm will have to be restarted. Otherwise you’ll end up who knows where with incorrect information.

The day before yesterday I decided to test CuteMaze with mazes larger than 50x50. I quickly discovered that although the mazes generate nice and quick at smaller sizes, they kind of drag at larger sizes. I had to fix this, so I set to work on optimizing the algorithms used.

After some minor changes I was able to accelerate all except for the Prim and Kruskal algorithms (all of the rest of the algorithms share some code). However, the algorithms would be incompatible with the current saved games. That bugged me, so I set the code aside for a while.

Yesterday I picked it up again and made some larger modifications to it. I then spent time figuring out the exact sequence of when the rand() calls were called and in what order the cells were checked. I was able to match them to the original order of rand() calls and cell checking, and to massively speed up the generation of new mazes in the process.

What does this mean in a practical sense? If you are using anything but the Prim or Kruskal algorithm, you can expect new mazes to generate in the blink of an eye… even at the maximum size of 99x99. To give some numbers, on my computer the “Hunt and Kill” algorithm (the slowest of the improved algorithms) only takes 20ms to generate a 99x99 maze. At the more manageable size of 50x50 it takes a mere 1.53ms! The fastest algorithm is of course “Recursive Backtracker”, and it takes 2ms to generate a 99x99 maze and 0.47ms to generate a 50x50.

Now, of course, I’m looking at the two remaining algorithms to try and find some low-hanging fruit to tweak and speed them up. I am constraining myself to have them produce the exact same mazes as before, so it is taking a while.

Of course, I spoke too soon. Today I found and fixed two minor bugs in CuteMaze. One was a regression caused by changing the code around a while ago, and the other was simply an oversight on my part.

The big news today, however, is the speed improvements. I suspected that caching the results from rendering the SVGs would help, and it did, but not by much. What did make a dramatic change in performance was caching the rotated pixmaps. Once I did that the CPU use on my computer went from 40% to 1%, and it was able to smoothly scroll while maximized. Yay!

I uploaded a new version of CuteMaze that fixes a few bugs relating to the targets, for details you can look at the ChangeLog. I don’t know of any remaining bugs in the game, so please tell me if you find any.