Sega Pengo: bug found in maze generating algorithm

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
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.

pengo_rd_1_1st_path_buggy_version.png


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.

pengo_rd_1_1st_path_bug_fixed_version.png


At the end of the 2nd path generation the bugged version has caught up with the fixed version.

pengo_rd_1_2nd_path_buggy_version.png


However at the end of the 2nd path generation the fixed version is now racing ahead of the bugged version.

pengo_rd_1_2nd_path_bug_fixed_version.png


At the end of the 3rd path generation the bugged version has again caught up with the fixed version.

pengo_rd_1_3rd_path_buggy_version.png


However yet again the fixed version races ahead at the end of the 3rd path generation.

pengo_rd_1_3rd_path_bug_fixed_version.png


At the end of 4th path generation the bugged version again catches up with the fixed version.

pengo_rd_1_4th_path_buggy_version.png


The fixed version at the end of the 4th path generation looks like this.

pengo_rd_1_4th_path_bug_fixed_version.png


The bugged version catches up again at the end of the 5th path generation.

pengo_rd_1_5th_path_buggy_version.png


The fixed version at the end of the 5th path generation looks like this

pengo_rd_1_5th_path_bug_fixed_version.png


At the end of the 6th path generation the bugged version has again caught up.

pengo_rd_1_6th_path_buggy_version.png


The fixed version at the end of the 6th path looks like this.

pengo_rd_1_6th_path_bug_fixed_version.png


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.

pengo_rd_1_7th_path_buggy_version.png


The fixed version finishes drawing the maze at the end of the 7th path generation.

pengo_rd_1_7th_path_bug_fixed_version.png


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.

pengo_rd_1_8th_path_buggy_version.png


I'll post a better example from the round 2 mazes of the bugged and fixed versions in the next post.
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Here's some screen shots from round 2. Due to the fact that the random number generator is being called constantly during round 1 I had to synchronise the random numbers to be the same value at the start of path generation for the round 2 mazes in both the bugged and fixed game plays that I did. This was to ensure that 1st paths would start identical.

Here's the end of the 1st path generation in the bugged version. The bug has caused the path to terminate prematurely where it should have turned right.

pengo_rd_2_1st_path_buggy_version.png


Here's the end of the 1st path generation in the fixed version.

pengo_rd_2_1st_path_bug_fixed_version.png


At the end of the 2nd path generation the bugged version has again caught up with the fixed version.

pengo_rd_2_2nd_path_buggy_version.png


But at the end of the 2nd path generation the fixed version is again racing ahead.

pengo_rd_2_2nd_path_bug_fixed_version.png


At the end of the 3rd path generation the bugged version has again caught up.

pengo_rd_2_3rd_path_buggy_version.png


But again the fixed version takes the lead at the end of the 3rd path generation.

pengo_rd_2_3rd_path_bug_fixed_version.png


The bug strikes again at the end of the 4th path generation in the bugged version. The path should have turned right but the bug caused the path to terminate.

pengo_rd_2_4th_path_buggy_version.png


The fixed version looks like this at the end of the 4th path generation. Nearly done.

pengo_rd_2_4th_path_bug_fixed_version.png


The bug strikes again at the end of the 5th path generation in the bugged version (should have turned right).

pengo_rd_2_5th_path_buggy_version.png


The maze completes at the end of the 5th path generation in the fixed version.

pengo_rd_2_5th_path_bug_fixed_version.png


But the bugged version is still slugging away.... (and still succumbing to the bug!!) at the end of the 6th path.

pengo_rd_2_6th_path_buggy_version.png


End of 7th path (nearly done now!)

pengo_rd_2_7th_path_buggy_version.png


The bugged version finally finishes the maze at the end of the 8th path generation.

pengo_rd_2_8th_path_buggy_version.png


In comparing the 2 mazes I think the fixed version produces a better maze. What do you guys think?
 

guddler

Busting vectors like it's 1982!
vacBacker
Feedback
10 (100%)
Credits
4,058CR
Very cool. I skipped a bunch of the actual explanation because I wanted to ask what you mean by self modifying code? How can it self modify? Does it copy the code to ram before executing and then alter stuff as it executes? Or what. Sorry, bit of a noob question maybe, but ROM is ROM. Read Only, so how can it be modified on the fly?
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
You got it in one sir!

Thirteen bytes are copied from rom to ram. Three bytes are code bytes, ten bytes are data bytes. Only one of the code bytes is subject to self-modification, it constantly changes from bit x,(hl) to res x,(hl) based on which bit of one of the data bytes needs either testing or clearing. The data bytes are used as a bitmap to represent whether a position we wish to move into is available or not. When we move into a position its bit is cleared in the bitmap to show that it is no longer available as a potential path point.

Self-modifying code was pretty rife in the days of the Spectrum/C64 but this it the first time I've seen it on an arcade board.

cmonkey2013-11-04 00:13:49
 

TheGecko

Newbie
Feedback
1 (100%)
Credits
24CR
Alot of code back then used self-modifying code - it was often the optimal way to get things done, especially in the limited room available. I'd never seen it on an arcade board either, though - makes me all nostalgic seeing the old z80 opcodes again! (old game programmer here). Mind you, some of the hoops we used to go through to draw stuff on the Spectrum were pretty wacky too.
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
TheGecko said:
Alot of code back then used self-modifying code - it was often the optimal way to get things done, especially in the limited room available. I'd never seen it on an arcade board either, though - makes me all nostalgic seeing the old z80 opcodes again! (old game programmer here). Mind you, some of the hoops we used to go through to draw stuff on the Spectrum were pretty wacky too.

It's always nice to hear from old game programmers. I have the utmost respect for the programmers of the systems back in the day. The amazing tricks that they had to come up with in order to do what they did in the constraints of the machines that they worked with still amazes me to this day. So tell us, did you work on any commercially available Spectrum games? If so, then which ones? It would be nice to think that members of this fine community may have played a game or games that you had input on BITD. You never know, I may have even reversed one of your games as I've done plenty of Spectrum games in my time!
 

Muppz

Active member
Feedback
6 (100%)
Credits
362CR
Very nice writeup sir, <doffs cap>

Never did self modifying code but used optimised opcodes in order to able to use the code as constant data lookup tables a few times when we ran out of ROM space.
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Ok, for sh*ts and giggles I decided to port the maze generating algorithm from Z80/Pengo hardware to 6809/Pac-Land hardware. I had to adapt the algorithm slightly to suit the horizontal (15x13 ice blocks) nature of the Pac-Land screen. Thankfully the resolution of both games is identical so it adapted well to being turned 90 degrees.

I kept the self-modifying code but decided to use the random number generator from Pac-Land rather than the weaker and less random one from Pengo!

I designed 5 new tiles (4 for the ice block and 1 for the checkerboard pattern that runs around the edge of the maze) and had to adjust some of the colour palette entries to more closely match the palette entries from Pengo.

All-in-all I don't think the results are too shabby.

I'm done with toying with Pengo now, back to work on Pac-Land.

Oh, and there's a little Easter Egg in the video
smiley2.gif


 
  • Like
Reactions: trm

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Even though I'd said I was done with the whole Pengo maze thing on Pac-Land hardware I couldn't resist making a high res version of the maze with 8x8 pixel ice blocks (instead of the usual 16x16 blocks). This gives a maze twice the dimensions of the previous one. I doubt the sprites for Pengo and the Sno-Bees would be pretty at that size however.

I am thinking about converting this into a full-blown maze game now. Even with the limitations of only having left/right/jump on Pac-Land hardware it would be possible by having the main character have some kind of propulsion device on his back (a-la Jet Pac) which would allow him to climb upwards through the maze and then allow gravity to naturally bring him back downwards when he walks off the edge of a platform. This would mean only left/right/thrust would be required. It's just a thought.

 

Hurray Banana

Moderator
Staff member
vacBacker
Feedback
8 (100%)
Credits
2,755CR
This looks good mate. Love the pacland music when the maze is drawing.

Are you thinking of being able to push blocks left and right or drop down and hit.?
 
Top