Sega Pengo: bug found in maze generating algorithm

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
You're right favouredson, it is four times the size! My bad!

@Hurray Banana - I'm not planning on having pushable blocks initially, want to keep things simple to start with. I guess that's the good thing about maze type games though, they're very extendable, you can always come up with new ideas to add to them. I need to think of 8x8 sprite designs first, something simple that can easily convey the direction that you're heading in. Maybe something as simple as an arrow, that points in the direction you're going.
 

Hurray Banana

Moderator
Staff member
vacBacker
Feedback
8 (100%)
Credits
2,755CR
Ade I use this set of tiles when testing tile based stuff, obviously the sizes are wrong for you, these are 32x32, but it gives you an idea, the're easy to colour.

maze_test_tiles.png


Hurray Banana2013-11-12 07:38:54
 

Sprint

Newbie
Credits
55CR
How about a little yellow disc shape, with a wedge cut out of it to give an indication of direction? I hear pacland even has something similar in its character set.

I should totally copyright that idea before some steals it
smiley36.gif
 

cmonkey

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

pengo_end_of_path_1.png


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.

pengo_start_of_path_2.png


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.

pengo_second_step_of_path_2.png


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.

pengo_third_step_of_path_2.png


The rest of the second path looked like this, after replaying the random numbers into the algorithm.

pengo_end_of_2.png


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.

pengo_end_of_path_3.png


And like this at the end of the 4th path.

pengo_end_of_path_4.png


And like this at the end of the 5th path.

pengo_end_of_path_5.png


And like this at the end of the 6th path.

pengo_end_of_path_6.png


And like this at the end of the 7th path.

pengo_end_of_path_7.png


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
smiley1.gif


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.

 

trm

Who loves you, and who do you love?
Feedback
2 (100%)
Credits
2,877CR
My first thought would be to run the RNG and capture the output for many hundreds of thousands of iterations and then plot it.

Assuming no coding error this weakness must exist in all implementations of the maze algorithm but if you've never seen it on the native platform then either it's observation bias kicking in and it does happen on the original, or the PRNG is biasing numbers so you have a slightly increased chance of getting a fault creating 3 at the wrong time.

I'm wondering if it's a mix of all of them - without a look-ahead sanity check then original Pengo must occasionally build dead-spot mazes.

I'm off to re-read what sources of entropy the PRNG uses to see if there could be a bias introduced by hardware differences.

You do start some really interesting discussions on here dude - thank you very much
smiley20.gif
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Eric - I did export the chunk of Pac-Land memory that contained the logged random numbers when I was generating faulty mazes, that's how I managed to replay those same random numbers and recreate the faulty maze. What would be the best way to profile these now? Would you suggest plotting a graph of random number against time as Tim suggests?

I can't imagine it's a coding error as sometimes I can generate over 30 mazes using the Pac-Land RNG without a fault. I'm adamant this is somehow related to the RNG returning a value of 3 at the wrong time, as Tim has said. The only change I make to the ASM source when comparing the two RNG's is to change two instances of the call to the RNG (from jsr RandomNumber (Pengo RNG) to jsr GetRandomNumber (Pac-Land RNG). The first instance of the call to the RNG is done within the main body of the maze generation algorithm and the second instance is done in the wait loop when the maze has finished (it's called once on every iteration of the wait loop to keep generating new random numbers). Other than that the code is identical.

At first I thought this all might be related to the original bug that I'd found in the algorithm and discussed in the first post of this thread but even re-introducing that bug into the algorithm and using the Pac-Land RNG I still get faulty mazes. I was thinking that maybe the original developers had put the bug in on purpose to prevent faulty maze generation, but that's not the case.

Maybe I should either implement a third, different RNG, to see if that too causes faulty mazes. There are plenty of 6809 games that I could use as a source and the RNG's aren't usually too hard to find in the asm source.

The Pengo RNG is very basic compared to the Pac-Land one. Here's the implementation :-

seed the original random number with a value of $365a (random number is stored internally as 16-bit)

rndnum:

multiply original random number by 2 to create a new random number

add original random number to new random number

add low byte of original random number to high byte of new random number

store new random number

on exit register A contains high byte of the new random number and is queried by the caller upon return
 

Hurray Banana

Moderator
Staff member
vacBacker
Feedback
8 (100%)
Credits
2,755CR
I think plotting against time is quick to get a visual look at any variance.

I wonder if its got something to do with maze size? Do you get broken mazes with pacland if you generate mazes with the same number of tiles as pengo?

If I get time this weekend I'll knock up the maze algorithm you worked out in my tile map engine and implement that rsndom algorithm you've judt outlined to see if I can replicate your bug.
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
It's not possible to generate mazes with the same x/y dimensions on Pac-Land as the monitor is oriented horizontally as opposed to the vertical orientation of Pengo. When I first implemented the algo on Pac-Land I did a 15w by 13h maze (as opposed to 13w by 15h on Pengo). When I switched the algo to high-res mode I made the dimensions 31w by 25h (the dimensions need to be odd). I still get faulty mazes when using the 15w by 13h maze size and the Pac-Land RNG but they happen MUCH less frequent (i.e. sometimes I have to generate in excess of 100 mazes before I get a faulty one). This leads me to believe that the algo doesn't scale well to bigger mazes.

Here's an example of a faulty maze at standard 15w by 13h size using the Pac-Land RNG.

pengo_faulty_maze.png


I'll plot the 2 RNG's vs time and report back with the results.
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Ok, so today I've implement a 3rd RNG! I took the XOR shift algorithm from here (http://www.worldofspectrum.org/forums/showthread.php?t=23070) and converted it to 6809. I've used this RNG before in Spectrum games so I know that it produces a good spread of random numbers. Instead of seeding it with $a280c0de (A Z80 CODE) I seeded it with $6809c0de instead (seemed apt)
smiley36.gif


The mazes that it produces seem to spread outwards to the right hand edge of the maze before they start to move upwards through the maze. The quality of the resulting mazes is good. In testing I didn't get a single faulty 15w x 13h maze after about 100 generated mazes. I did get faulty mazes when I tried the algorithm in the high res maze, but failures were less common than with the Pac-Land RNG (1 failure in 52 generated mazes was the best I observed, 1 in 28 was the worst).

This reinforces the fact that this maze generation algorithm is best suited to small mazes and doesn't perform well as the maze size grows.

I've done some plotting of the random numbers out of each of the 3 RNG's but the haven't been able to determine anything from the resulting graphs, they're simply too random to be able to pick out any particular patterns.

I think I'm going to go with the 'second pass' method of maze clean up. The actual checking routine to see whether a second pass is required takes about 10 scan lines, which is completely negligible. Even if a second pass through the maze is actually required it only takes 6 frames to do it, due to the fact that the second pass has virtually no block removal to do. Using a 60fps game engine that's only 1/10th of a second and not something that the average human would be able to notice.

Here's a couple of vids of the XOR shift RNG in action in both 15w x 13h and high res implementations. MAME has been speeded up to the max in these videos so the sound is a bit weird!


This video shows a faulted maze to begin with then a further 37 perfect mazes before we get another faulty one

 

Hurray Banana

Moderator
Staff member
vacBacker
Feedback
8 (100%)
Credits
2,755CR
Hi Ade,

Had a go at implementing these in my tilemap engine, had a job getting the algo you posted to work, it seemed to be looking for things that weren't possible (like the tests you said you were looking for were the opposite to what you need to look for). Looking for a new space when you needed to be looking for an ice block to remove up to.

Anyway got it working and here's a few vids with some large mazes:

the upshot I found (unless I partially re-wrote the original algorithm
smiley9.gif
), I found the pengo rng didn't generate any errors but does suffer from cycling on certain size mazes in some I found I could only generate the same maze each time which was weird but obviously the nature of rng. Interestingly if I ran with the .net random number generator I got some error mazes!

The tilemap is 16 pixels by 16 pixel tiles, but I'm scaling the rendering back so I can show the entire tilemap in one go.

here's some vids, the smaller ones I did using a sleeping thread so you could see it draw, but the largest ones I ran realtime.

Its a lovely little algorithm tho, would be interesting to found out if it's taken from some classic algorithm.

edit: best to watch them full screen at hi-res setting in youtube

smallest 167x99 using pengo rng


smallest 167x99 using dot net rng - gets an error on second maze


smallest 471x249 using pengo rng


smallest 471x249 using dot net rng quite a lot of errors on the later ones 45 and 51 in particular were bad


Mega 713 by 409 using pengo rng


Mega 713 by 409 using dot net rng lots of errors


Hurray Banana2013-11-17 21:43:01
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Hey Eric

That's awesome!!! Well done buddy! My mind is spinning thinking how hard it would be to get the 3 diamond blocks together in a game of Pengo based on a 713x409 maze
smiley36.gif


Looks like you've nailed the algorithm to me. Are you maintaining a bitmap of available locations during generation and then clearing bits in the bitmap as the locations are slowly taken? If so then it must be some huge sized bitmap, especially for the biggest maze! Are these written in C# or C++? I can provide you with the comment Z80/6809 versions of the algorithm if you want to compare yours to the originals.

I agree with you that whenever I use the Pengo RNG I never get any faulty mazes but I only get about 8 or 9 different mazes before cycling occurs. Using the Pac-Land or XOR shift RNG I do get errors but the cycling is much less frequent. It's nice to see you're observing the same results as I am.

I believe the algorithm is loosely based on the depth first search method. It has traits of the recursive backtracker algorithm but doesn't actually backtrack to the previous node to start a new path when the current path terminates, instead it iterates across and up the bitmap when the previous path terminates.

The wiki page on maze generation is pretty good

http://en.wikipedia.org/wiki/Maze_generation

I've adapted my algorithm now so that instead of starting in the lower left corner and working across each row and then upwards when the previous path terminates it starts in the centre and creates the first path from there. It then picks a random x/y position within the confines of the maze and tests whether it's an empty block or not, if it is then it begins the next path from that point, if not then it picks another random x/y position and tries again. At the end of each path it checks the maze bitmap to see if the maze is complete (all values = nil), if not then it continues generating random x/y positions and new paths until it is.

The strange thing is that if I pick the random x/y positions using the XOR shift RNG the maze never completes as there seem to be certain values that it just will not ever generate, hence paths can never be created from those points. If I use the Pac-Land RNG then all is fine and dandy. Very odd!

So in the end I've ended up using the Pac-Land RNG for x/y position generation and the XOR shift RNG for up/down/left/right decision making. Seems to give good mazes with not many long corridors.


Anyway, fantastic work on the high level implementation of this!
smiley32.gif
 

Hurray Banana

Moderator
Staff member
vacBacker
Feedback
8 (100%)
Credits
2,755CR
Hi ade

I'd appreciate the assembly code so I can check. It will also be a nice example for my second year computing students to see the difference in implementation between assembler and high level.

It's awkward implementing low byte/ hi byte arithmetic in high level stuff assembler is so much nicer for low level mucking about.

The implementation is in c# using a tilemap engine I built on top of xna. It's part of an engine I wrote to enable students to get code running on the Xbox360. The tilemap just has an index to a tile object which holds texture portion info (among other fancy things). Its not super optimised as I only get snippets of time to work on it.

It's funny as I was doing these runs I thought about rigging it to run from the centre for a bit more variety, you beat me to it.

I'll use the assembly code you post as my excuse to spend a little time getting back into some low level code, haven't done much since moving to pc

Thanks for reigniting my interest
 

trm

Who loves you, and who do you love?
Feedback
2 (100%)
Credits
2,877CR
Hi Ade,

Do you still have the random numbers that you graphed? If so could you send them over so I can do some analysis to see how random they are? I have a minor interest in cryptography so have tools for determining entropy.

It does seem as though you've found a weakness in the maze algorithm though. If only I'd paid more attention years ago in Data Structures & Algorithms I might be able to figure out the bias.

Good post btw!
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Hey Tim

Would you like the full fat, untouched, 8-bit random numbers or the numbers after they've been trimmed by the AND $03 statement? Not forgetting that all 3 RNG's that I've played with so far generate a random number of 16-bits in size, but we only ever use 8 of those 16-bits.

Cheers!

@Eric - I'm cleaning up my code and making the comments a bit more user friendly, should have it done by tonight!
 

Hurray Banana

Moderator
Staff member
vacBacker
Feedback
8 (100%)
Credits
2,755CR
cmonkey said:
Hey Tim

Would you like the full fat, untouched, 8-bit random numbers or the numbers after they've been trimmed by the AND $03 statement? Not forgetting that all 3 RNG's that I've played with so far generate a random number of 16-bits in size, but we only ever use 8 of those 16-bits.

Cheers!

@Eric - I'm cleaning up my code and making the comments a bit more user friendly, should have it done by tonight!

Nice one Ade, looking forward to it.
 

cmonkey

Active member
vacBacker
Feedback
4 (100%)
Credits
1,659CR
Right guys, sorry for the delay.

Eric - attached to this post is the Z80 and 6809 implementations of the maze algorithm. The Z80 version is taken verbatim (except for the bug fix) from the Pengo rom (I've shuffled the routines around a little to make it more readable but the actual code is untouched as far as opcodes go). The 6809 version is my interpretation of the that. I've left out platform specific routines such the the ice block removal routine as that's more of a tile display/erase routine than part of the algorithm itself. I've structured the code exactly the same for both source files and kept all labels identical, where possible. This makes it very easy to put the 2 files side by side and do comparisons between the different instruction sets. The source files are heavily commented so it shouldn't be too difficult to follow them (let this be a lesson to your pupils to get into the good habit of commenting their source amply!!). The high-res version of the algorithm works in a similar manner, it's merely the handling of the maze node bitmap which differs a little. Any questions, ask away.

Tim - attached to this post are lots of random numbers just for you!
smiley36.gif
For each of the 3 different random number generators that I've experimented with (Pengo/Pac-Land/XOR shift) I've given you 5 good maze examples (both the random numbers and a screen shot of the maze that was generated with those random numbers) and either 5 bad ones (in the case of the Pac-Land RNG) or 3 bad ones (in the case of the XOR shift RNG). Try as I might I simply can't get the Pengo RNG to generate faulty mazes, no matter how many I generate (probably because the random numbers cycle too quickly due to it being a weak RNG). I could only manage to generate 3 faulty mazes using the XOR shift RNG in the time I had available. The random numbers are AND 3, as you requested. For each set of random numbers there is a corresponding PNG file.

Have fun boys!
smiley1.gif


https://www.ukvac.com/forum/data/uploads/1497/Good_and_bad_Pengo_mazes.zip

https://www.ukvac.com/forum/data/uploads/1497/Pengo_maze_gen_z80_and_6809.zip
 
  • Like
Reactions: trm
Top