Now that Trolltech has released a version of Qt 4 under the GPL version 3, I have decided to re-license CuteMaze as GPL 3 or later. As this is the only change between the 1.0 and 1.0.1 releases, it’s quite a minor update.

I’m amazed that nobody has reported any bugs after the 1.0 release. If you do encounter any bugs, please don’t hesitate to inform me. They won’t get fixed if I don’t know about them!

Update: In my zeal to upload the newest version of CuteMaze earlier today, I accidentally uploaded the wrong versions for most of the files—the only correct builds were the Linux ones. 🙂 I have replaced the incorrect files and updated their checksums.

I have not been doing much with CuteMaze recently. That’s probably due to the fact that I have almost completed the game. Today I uploaded a version that allows the player to install or uninstall themes, which should make sharing them easier. If you have a theme you would like for me to put on the website, please email it to me.

The one task I have left for CuteMaze is to port it to the Mac. This should be relatively easy, and the only thing holding me up is that I don’t have a Mac. However, I will have one in about a week, so that isn’t too big of an issue.

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.