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.

Advertisements

Comments are closed.