Changing to GPLv3

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 SHA1 sums.

A quick note

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.

Another day, another release

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, either as a comment to this post or an email.

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.

Generating a 50x50 maze Generating a 99×99 maze

* 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.

There are always bugs

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.

Faster! Faster!

The day before yesterday I decided to test CuteMaze with mazes larger than 50×50. 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 awhile.

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 99×99. To give some numbers, on my computer the “Hunt and Kill” algorithm (the slowest of the improved algorithms) only takes 20ms to generate a 99×99 maze. At the more managable size of 50×50 it takes a mere 1.53ms! The fastest algorithm is of course “Recursive Backtracker”, and it takes 2ms to generate a 99×99 maze and 0.47ms to generate a 50×50.

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 awhile.

Murhpy’s Law

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 awhile 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 SVG’s 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!

Just a minor release

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.