I've generated literally hundreds of mazes in the past week using both the native Pac-Land random number generator and also the Pengo random number generator ported to 6809 and I've come across a weakness in the maze generating algorithm that only seems to occur when using the Pac-Land random number generator. I'm hoping a fellow programmer might be able to assist.
The bug can be clearly seen in this video. The second and final mazes (which are actually identical) in this clip both show a 2x3 block of ice blocks which is unfinished.
In order to debug it I had to capture the random numbers into ram as they were being generated during maze generation and then replay the building of the maze manually by setting a break point immediately after the call to the random number generator and then substituting the generated random numbers with the saved random numbers. This proved where the algorithm was potentially weak.
This first shot shows how the replayed maze looked at the end of the first path. The big letter 'F' shows where the path began (first path always begins at lower left corner). When the path ends the algorithm goes back to where the path began, jumps two ice blocks to the right and looks for an empty block to begin the next path with (small number '1'). As the block two blocks to the right of the lower left corner is not empty it jumps another two blocks to the right looking for an empty block (small number '2'), and so on until it reaches the end of the row. By the time it reaches the tiny letter 'F' at the end of the bottom row it still hasn't found an empty block to begin a new path with so it returns to the start of the row and moves upwards two rows. The block on the left of that row IS empty but the algorithm can't start a new path there as the positions above, below and to the right of that block are already empty (taken by path 1) and the position to the left is off the edge of the maze. So the algorithm moves right two blocks and finds an empty block that it can potentially begin a new path with. It then looks upwards and sees that the blocks 2 blocks above is empty (taken by path 1) so it looks downwards and sees that the block 2 blocks below is not empty. It now knows that it can potentially start a part down to that block (even though it might not actually end up going down to that block as it can also potentially go to the right at this point too) and so moves into the path generation phase. The second path therefore begins where the big letter 'S' is.
This next shot shows the first step of the second path. The path generation phase calls the random number generator and gets a value of either 0 (up), 1 (down), 2 (left) or 3 (right). The faulty maze returned a value of 3 for its first step of the second path and so the path clears 2 blocks of ice to the right.
It then looks up and sees that it can potentially move up on the next step as the block 2 blocks above is available (even though it might not end up going upwards as it can also potentially go down and right, depending on what random number is returned).
The random number that was returned in the faulty maze at this point was 1, so the path turned downwards and cleared two blocks. This is shown here.
This is now a critical point because the random number that is returned at this point determines whether the maze will be faulty or not.
At this point the algorithm looks up and sees that it can't move upwards from here (as the path is already clear), it then looks down, but it can't go downwards as that would take us off the edge of the maze. So it looks to the left and sees that we can potentially move to the left (even though we might not actually end up moving to the left as there is also the possibility of moving to the right, depending on the random number returned).
The random number returned at this point was 3, so the path turned to the right. At this point we've created a faulty maze (reason why will be explained later). This is shown in this screen shot.
The rest of the second path looked like this, after replaying the random numbers into the algorithm.
The reason why the maze is faulty at this point is because when the second path ends the algorithm will return to start point of the second path and move right two blocks looking for the next available empty block with which to begin the third path with. It will find one straight away (marked with a letter 'T' for third path start point in the shot above). However the third path can only move upwards from here as the positions to the left, right and below are already empty. The 2x3 block is now unreachable by the algorithm as it is constantly going to the right and then upwards as it looks for empty blocks with which to begin any new paths with.
The maze looks like this at the end of the third path.
And like this at the end of the 4th path.
And like this at the end of the 5th path.
And like this at the end of the 6th path.
And like this at the end of the 7th path.
I won't bother with the rest of the paths as it's clear to see by this point that it will never complete the 2x3 block at the lower left of the maze.
What I'm most perplexed over however is why this phenomenon only seems to rear its ugly head when using the Pac-Land random number generator and NOT when using the Pengo random number generator. I've generated literally hundreds of mazes using both random number functions and only ever seen this with the Pac-Land one.
So I did some profiling of the random number functions to see if the spread of values that they returned during maze generation differed wildly. Both random number functions return an 8-bit value in register A which is then ANDed with $03 to give a value from 0-3. I altered the code and added 4 counter variables which incremented each time their respective value of 0,1,2 or 3 was returned from the random number function. I didn't observe any notable differences in the counts during maze generation with either the Pac-Land random number function or the Pengo random number function. In both cases the average count is around $78 to $7d for the values 0,1,2 and 3 for a complete maze.
So I'm baffled as to why this is only happening with the Pac-Land random number generator.
In the meantime I've implement a workaround for faulty mazes. When the maze generation begins there is a bitmap held in ram in which each bit represents whether a node is populated (bit is set) or empty (bit is clear). By the end of maze generation all values in the bitmap SHOULD BE nil, if the maze is not faulty. I now scan through the bitmap at the end of maze generation checking for non-nil values, if I find one I do a second 'clean-up' pass through the maze, which captures any faults. It's not an ideal solution, but it is a solution. Until I can think of a better way, or one of you lot can think of a better way
So here's a video showing the fix in place. The final maze of this video clip would have been faulty, but the second pass through the maze captures the fault. You can just about see the 2x3 block at the lower right of the maze is left untouched until the very end of maze generation, whereby the second pass sees it and finishes off the maze.