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.