I'm taking a little break from Pac-Land reversing, but there's always other games that need reversing so, as I've always been curious as to how the maze generation algorithm in Sega's iconic Pengo works, I thought I'd spend a few hours learning it. Little did I realise when I started this just how long it would actually take to fully understand it! It's a pretty complex routine, not helped by the fact that it uses self-modifying code. Routines like this are made more complex by the shear fact that they're constantly changing during runtime.
Anyway, as the thread title explains, during the process of taking apart and thoroughly understanding the whole routine I found a nasty bug which ultimately leads to mazes that aren't as complex as they should be. I've fixed the bug (it's only a single byte that's incorrect) so you can compare for yourselves the results using the fixed algorithm. I think the mazes that the fixed algorithm generates are much better than the broken ones. The bug exists in all known versions of Pengo, even the bootleg version.
First I need to explain a little how the algorithm works. I'll try and keep it as high level as possible, without delving into the depths of the self-modifying code and the more intricate bits of the process.
Here's the pseudo-code, as best as I can explain it :-
flood fill the play field with ice blocks (13 wide by 15 high)
remove the bottom left ice block (this is ALWAYS the starting position for the first path)
path_initiialisation:
begin outer loop
position ourselves at the leftmost column of a row (this is our current position)
begin inner loop
test to see if current position is clear (i.e. no ice block)
if it is then we can POTENTIALLY begin a new path here, if not then jump to end of inner loop
test if the position 2 blocks above our current position is clear (i.e. no ice block)
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks above)
if it isn't then test if the position 2 blocks below our current position is clear
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks below)
if it isn't then test if the position 2 blocks to the left of our current position is clear
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks to the left)
if it isn't then test if the position 2 blocks to the right of our current position is clear
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks to the right)
end of inner loop:
move our current position 2 blocks to the right and go back to top of inner loop
end of outer loop:
when we get to end of current row move back to start of row and move up 2 rows
path_generating:
call the random number generator to get a value between 0 and 3
if the value is 0 then test if the position 2 blocks above our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in an upwards direction from current position and jump to path_continue
if the value is 1 then test if the position 2 blocks below our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in a downwards direction from current position and jump to path_continue
if the value is 2 then test if the position 2 blocks to the left of our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in a left direction from current position and jump to path_continue
if the value is 3 then test if the position 2 blocks to the right of our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in a right direction from current position and jump to path_continue
(we break out of this loop via the path_continue routine)
path_continue:
test if the position 2 blocks above our current position is clear
if it is then jump to start of path_generating routine
if it isn't then test if the position 2 blocks below our current position is clear
if it is then jump to start of path_generating routine
if it isn't then test if the position 2 blocks to the left of our current position is clear
if it is then jump to start of path_generating routine
if it isn't then test if the position 2 blocks BELOW our current position is clear (**** BUG ****)
if it is then jump to start of path_generating routine
if it isn't then this path has reached its end so return to path_initialisation routine to find the next empty block to begin a new path with
The bug is clear to see. During the path_continue routine it's checking if we can go up, down, left and then down from our current position but it should be checking if we can go up, down, left and then right from our current position. This leads to paths that terminate prematurely.
The code is :-
307C: call $308E ; test if we can go up from our current position
307F: ret nz ; return if we can
3080: call $3097 ; test if we can go down from our current position
3083: ret nz ; return if we can
3084: call $309E ; test if we can go left from our current position
3087: ret nz ; return if we can
3088: call $3097 ; test if we can go DOWN from our current position (**BUG** should be call $30a5)
To fix the bug you need to change the value at offset $0089 in the rom that covers address space $3000-$3fff (in the pengo3u MAME set this rom is called ep5123.14) from $97 to $a5. This will fix up the 'call' instruction to call the correct routine. However it has to be noted that Pengo does checksumming on the individual roms, as well as checksumming the entire rom area in one big chunk and if the checksums don't agree (which they won't if you've fixed the bug) then the game will only play once and after that it won't accept any more coin inputs. I can explain how to bypass the rom checksums, if people would like me to do so, so that you can overcome this issue.
This bug is probably better demonstrated with some screen shots taken at the end of each path generating routine.
The first maze in Pengo is ALWAYS identical as long as you start a game BEFORE attract mode has dropped into the gameplay segment of attract (i.e. before attract mode has drawn a maze itself). This is because maze generation is based around the random number generator and that value is ALWAYS the same when you start the first round (as long as you start it before attract mode draws a maze).
So, here's a shot at the end of the generation of the 1st path in the bugged version. Where I've drawn a big letter E is where the bug has caused the algorithm to fail to turn right into available path space during the path_continue phase. It only attempted to go up (which it couldn't do as there was already a path there), down (which it couldn't do as it would drop off the end of the play field), left (which it couldn't do as there was already a path there) and DOWN again.
Here's a shot at the end of the generation of the 1st path in the fixed version. Notice how the path is considerably longer than the one above as it doesn't terminate prematurely.
At the end of the 2nd path generation the bugged version has caught up with the fixed version.
However at the end of the 2nd path generation the fixed version is now racing ahead of the bugged version.
At the end of the 3rd path generation the bugged version has again caught up with the fixed version.
However yet again the fixed version races ahead at the end of the 3rd path generation.
At the end of 4th path generation the bugged version again catches up with the fixed version.
The fixed version at the end of the 4th path generation looks like this.
The bugged version catches up again at the end of the 5th path generation.
The fixed version at the end of the 5th path generation looks like this
At the end of the 6th path generation the bugged version has again caught up.
The fixed version at the end of the 6th path looks like this.
At the end of the 7th path generation the bugged version has again succumbed to the bug. Here the big yellow E shows that the algorithm failed to turn right into available path space and the path ended prematurely.
The fixed version finishes drawing the maze at the end of the 7th path generation.
But it takes an extra path generating call to finish the maze in the bugged version, resulting in a maze that looks slightly different to the fixed version one.
I'll post a better example from the round 2 mazes of the bugged and fixed versions in the next post.
Anyway, as the thread title explains, during the process of taking apart and thoroughly understanding the whole routine I found a nasty bug which ultimately leads to mazes that aren't as complex as they should be. I've fixed the bug (it's only a single byte that's incorrect) so you can compare for yourselves the results using the fixed algorithm. I think the mazes that the fixed algorithm generates are much better than the broken ones. The bug exists in all known versions of Pengo, even the bootleg version.
First I need to explain a little how the algorithm works. I'll try and keep it as high level as possible, without delving into the depths of the self-modifying code and the more intricate bits of the process.
Here's the pseudo-code, as best as I can explain it :-
flood fill the play field with ice blocks (13 wide by 15 high)
remove the bottom left ice block (this is ALWAYS the starting position for the first path)
path_initiialisation:
begin outer loop
position ourselves at the leftmost column of a row (this is our current position)
begin inner loop
test to see if current position is clear (i.e. no ice block)
if it is then we can POTENTIALLY begin a new path here, if not then jump to end of inner loop
test if the position 2 blocks above our current position is clear (i.e. no ice block)
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks above)
if it isn't then test if the position 2 blocks below our current position is clear
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks below)
if it isn't then test if the position 2 blocks to the left of our current position is clear
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks to the left)
if it isn't then test if the position 2 blocks to the right of our current position is clear
if it is then jump to start of path_generating routine (we can start a path from current pos to pos 2 blocks to the right)
end of inner loop:
move our current position 2 blocks to the right and go back to top of inner loop
end of outer loop:
when we get to end of current row move back to start of row and move up 2 rows
path_generating:
call the random number generator to get a value between 0 and 3
if the value is 0 then test if the position 2 blocks above our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in an upwards direction from current position and jump to path_continue
if the value is 1 then test if the position 2 blocks below our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in a downwards direction from current position and jump to path_continue
if the value is 2 then test if the position 2 blocks to the left of our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in a left direction from current position and jump to path_continue
if the value is 3 then test if the position 2 blocks to the right of our current position is clear
if it isn't then jump back to top of this routine and get another random number and try again
if it is then clear 2 ice blocks in a right direction from current position and jump to path_continue
(we break out of this loop via the path_continue routine)
path_continue:
test if the position 2 blocks above our current position is clear
if it is then jump to start of path_generating routine
if it isn't then test if the position 2 blocks below our current position is clear
if it is then jump to start of path_generating routine
if it isn't then test if the position 2 blocks to the left of our current position is clear
if it is then jump to start of path_generating routine
if it isn't then test if the position 2 blocks BELOW our current position is clear (**** BUG ****)
if it is then jump to start of path_generating routine
if it isn't then this path has reached its end so return to path_initialisation routine to find the next empty block to begin a new path with
The bug is clear to see. During the path_continue routine it's checking if we can go up, down, left and then down from our current position but it should be checking if we can go up, down, left and then right from our current position. This leads to paths that terminate prematurely.
The code is :-
307C: call $308E ; test if we can go up from our current position
307F: ret nz ; return if we can
3080: call $3097 ; test if we can go down from our current position
3083: ret nz ; return if we can
3084: call $309E ; test if we can go left from our current position
3087: ret nz ; return if we can
3088: call $3097 ; test if we can go DOWN from our current position (**BUG** should be call $30a5)
To fix the bug you need to change the value at offset $0089 in the rom that covers address space $3000-$3fff (in the pengo3u MAME set this rom is called ep5123.14) from $97 to $a5. This will fix up the 'call' instruction to call the correct routine. However it has to be noted that Pengo does checksumming on the individual roms, as well as checksumming the entire rom area in one big chunk and if the checksums don't agree (which they won't if you've fixed the bug) then the game will only play once and after that it won't accept any more coin inputs. I can explain how to bypass the rom checksums, if people would like me to do so, so that you can overcome this issue.
This bug is probably better demonstrated with some screen shots taken at the end of each path generating routine.
The first maze in Pengo is ALWAYS identical as long as you start a game BEFORE attract mode has dropped into the gameplay segment of attract (i.e. before attract mode has drawn a maze itself). This is because maze generation is based around the random number generator and that value is ALWAYS the same when you start the first round (as long as you start it before attract mode draws a maze).
So, here's a shot at the end of the generation of the 1st path in the bugged version. Where I've drawn a big letter E is where the bug has caused the algorithm to fail to turn right into available path space during the path_continue phase. It only attempted to go up (which it couldn't do as there was already a path there), down (which it couldn't do as it would drop off the end of the play field), left (which it couldn't do as there was already a path there) and DOWN again.
Here's a shot at the end of the generation of the 1st path in the fixed version. Notice how the path is considerably longer than the one above as it doesn't terminate prematurely.
At the end of the 2nd path generation the bugged version has caught up with the fixed version.
However at the end of the 2nd path generation the fixed version is now racing ahead of the bugged version.
At the end of the 3rd path generation the bugged version has again caught up with the fixed version.
However yet again the fixed version races ahead at the end of the 3rd path generation.
At the end of 4th path generation the bugged version again catches up with the fixed version.
The fixed version at the end of the 4th path generation looks like this.
The bugged version catches up again at the end of the 5th path generation.
The fixed version at the end of the 5th path generation looks like this
At the end of the 6th path generation the bugged version has again caught up.
The fixed version at the end of the 6th path looks like this.
At the end of the 7th path generation the bugged version has again succumbed to the bug. Here the big yellow E shows that the algorithm failed to turn right into available path space and the path ended prematurely.
The fixed version finishes drawing the maze at the end of the 7th path generation.
But it takes an extra path generating call to finish the maze in the bugged version, resulting in a maze that looks slightly different to the fixed version one.
I'll post a better example from the round 2 mazes of the bugged and fixed versions in the next post.