Faster! Faster!

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.