ukVac.com Homepage
Forum Home Forum Home > Technical > Tech, Maintenance & Repairs
  New Posts New Posts RSS Feed - Sega Pengo: bug found in maze generating algorithm
  FAQ FAQ  Forum Search   Events   Register Register  Login Login

Skin:


Sega Pengo: bug found in maze generating algorithm

 Post Reply Post Reply Page  123>
Author
Message
 Rating: Topic Rating: 2 Votes, Average 5.00  Topic Search Topic Search  Topic Options Topic Options
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (4) Thanks(4)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Topic: Sega Pengo: bug found in maze generating algorithm
    Posted: 03 Nov 2013 at 11:30pm
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.

Back to Top
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Posted: 03 Nov 2013 at 11:47pm
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.


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


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


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


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


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


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.


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


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


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


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


End of 7th path (nearly done now!)


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




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

Back to Top
guddler View Drop Down
Senior Member
Senior Member
Avatar
Busting vectors like it's 1982!

5 Years of Supporting ukvac.com!

5 Years of Supporting ukvac.com!



Joined: 24 Sep 2000
Location: W.Somerset
Status: Offline
Points: 59609

Feedback: 5
Post Options Post Options   Thanks (0) Thanks(0)   Quote guddler Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:04am
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?
Back to Top
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:13am
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.



Edited by cmonkey - 04 Nov 2013 at 12:13am
Back to Top
guddler View Drop Down
Senior Member
Senior Member
Avatar
Busting vectors like it's 1982!

5 Years of Supporting ukvac.com!

5 Years of Supporting ukvac.com!



Joined: 24 Sep 2000
Location: W.Somerset
Status: Offline
Points: 59609

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote guddler Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:27am
Ah, OK - so basically a crude state machine and a lookup table sort of thing
Back to Top
RGP View Drop Down
Senior Members
Senior Members

Meeter & Greeter

Joined: 11 Apr 2013
Location: Blackburn
Status: Offline
Points: 4761

Feedback: 5
Post Options Post Options   Thanks (2) Thanks(2)   Quote RGP Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:41am
It's all my fault....

I was the self modifying code king in C64 demos back in the day.

Another amazing debug and explanation although your username needs to become z80monkey now lol.
Webstore closed due to lack of interest.
We make repro cab shells.
Don't PM me - contact through website please.
Back to Top
TheGecko View Drop Down
User
User
Avatar

Joined: 27 Feb 2012
Location: N Wales UK
Status: Offline
Points: 204

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote TheGecko Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 9:33am
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.
Back to Top
Macro View Drop Down
Senior Members
Senior Members
Avatar

Joined: 13 May 1999
Location: Norfolk, UK
Status: Offline
Points: 3203

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote Macro Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 9:54am
and used in copious amounts for protection purposes ...
Back to Top
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (2) Thanks(2)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:01pm
Originally posted by TheGecko TheGecko wrote:

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!


Back to Top
Muppz View Drop Down
User
User


Joined: 26 Jan 2012
Location: Alfreton
Status: Offline
Points: 824

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote Muppz Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:11pm
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.
Hand Soldering 160-Pin QFPs since 1994.
Back to Top
RGP View Drop Down
Senior Members
Senior Members

Meeter & Greeter

Joined: 11 Apr 2013
Location: Blackburn
Status: Offline
Points: 4761

Feedback: 5
Post Options Post Options   Thanks (0) Thanks(0)   Quote RGP Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 12:23pm
Originally posted by Macro Macro wrote:

and used in copious amounts for protection purposes ...

Nods knowingly

Webstore closed due to lack of interest.
We make repro cab shells.
Don't PM me - contact through website please.
Back to Top
ataritoobin View Drop Down
User
User
Avatar

Joined: 18 Nov 2010
Location: U.S.A.
Status: Offline
Points: 1008

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote ataritoobin Quote  Post ReplyReply Direct Link To This Post Posted: 04 Nov 2013 at 4:30pm
Fascinating post as always Thumbs Up
Back to Top
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Posted: 08 Nov 2013 at 11:55pm
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 Wink



Back to Top
guddler View Drop Down
Senior Member
Senior Member
Avatar
Busting vectors like it's 1982!

5 Years of Supporting ukvac.com!

5 Years of Supporting ukvac.com!



Joined: 24 Sep 2000
Location: W.Somerset
Status: Offline
Points: 59609

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote guddler Quote  Post ReplyReply Direct Link To This Post Posted: 09 Nov 2013 at 12:51am
Sweet ClapClapClap

You know you're just setting yourself up for doing a conversion though, don't you!!
Back to Top
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Posted: 09 Nov 2013 at 1:07am
Hmmm, not sure how the control mechanics would work, what with Pac-Land only have left/right/jump and Pengo needing a 4-way + fire! LOL
Back to Top
grainflavour View Drop Down
User
User
Avatar

Joined: 13 Apr 2013
Location: lancashire
Status: Offline
Points: 325

Feedback: 5
Post Options Post Options   Thanks (1) Thanks(1)   Quote grainflavour Quote  Post ReplyReply Direct Link To This Post Posted: 09 Nov 2013 at 1:23am
I found this fascinating to read, especially a good explanation with the pics  Smile
Back to Top
Hurray Banana View Drop Down
Moderator Group
Moderator Group
Avatar

5 Years of Supporting ukvac.com!

5 Years of Supporting ukvac.com!



Joined: 11 Feb 2013
Location: Essex
Status: Offline
Points: 69739

Feedback: 5
Post Options Post Options   Thanks (2) Thanks(2)   Quote Hurray Banana Quote  Post ReplyReply Direct Link To This Post Posted: 09 Nov 2013 at 2:50pm
Nice write up Ade.
Back to Top
cmonkey View Drop Down
Senior Member
Senior Member
Avatar

Joined: 10 Jan 2013
Location: Leeds, West YKS
Status: Offline
Points: 7782

Feedback: 5
Post Options Post Options   Thanks (0) Thanks(0)   Quote cmonkey Quote  Post ReplyReply Direct Link To This Post Posted: 11 Nov 2013 at 6:43pm
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.  


Back to Top
Hurray Banana View Drop Down
Moderator Group
Moderator Group
Avatar

5 Years of Supporting ukvac.com!

5 Years of Supporting ukvac.com!



Joined: 11 Feb 2013
Location: Essex
Status: Offline
Points: 69739

Feedback: 5
Post Options Post Options   Thanks (0) Thanks(0)   Quote Hurray Banana Quote  Post ReplyReply Direct Link To This Post Posted: 11 Nov 2013 at 6:52pm
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.?
Back to Top
favouredson View Drop Down
User
User
Avatar

Joined: 21 May 2002
Location: Chelmsford SX
Status: Offline
Points: 1009

Feedback: 0
Post Options Post Options   Thanks (0) Thanks(0)   Quote favouredson Quote  Post ReplyReply Direct Link To This Post Posted: 11 Nov 2013 at 10:10pm
Originally posted by cmonkey cmonkey wrote:

......This gives a maze twice the dimensions of the previous one......
 
[PEDANT] It is four times, actually. You are doubling both length and width. [/PEDANT]
Garry
Back to Top
 Post Reply Post Reply Page  123>
  Share Topic   

Forum Jump Forum Permissions View Drop Down



This page was generated in 0.313 seconds.