How Many Pac-Man Mazes Are There?

[Joefish]

Nah, it's cleverer than that.

Here's an updated algorithm and some tests. It now includes all four long L-shapes. Because of the longer shape list, the random selector now picks a number from 0..31 (it was 0..15) and mods it, so you get 0..16 or 0..14 out of it. That way, the last two shapes (short vertical and horizontal bars) are half as likely to be picked first compared to the other more interesting shapes. And the long horizontal and vertical bars are now only tried if all else fails. There's also a secondary set of checks that makes it try it all again a couple of times if (a) there aren't enough vertical walls in the maze or (b) there's no vertical wall at all between the tunnel entrances. Makes the mazes more interesting.



Download: http://railtron.com/files/spectrum/PacM ... mo_002.zip

I think that's coming up with some pretty interesting mazes, and doing some fairly smart shape-fitting along the way. I'm not sure I'd have tried some of those concepts manually, particularly the fourth one there. Looks like it might be fun to play though.


And here's how the dots are done:



In the original Pac-Man the dots are at the centre of the character cells, and the sprites are centred on them. It's the walls that bridge over multiple cells.

In my version, I've shifted all the graphics up-and-left by 1 pixel. Thus each dot is in the bottom-right of a single character cell. The walls are 6 pixels wide and the sprites are 14x14, so they can all be shifted up-left.

Now I only have to navigate the sprites around one-cell-wide passageways (shown in blue) using their top-left point as a reference. This makes their movement much easier to deal with, particularly at junctions. The sprites treat the black areas as solid walls they can't pass through (except for exiting the ghost house), but the body of the sprite can still be drawn over the black areas.

[Joefish]

For a bit of fun I tried expanding the shape list to include all viable 3x3 shapes.
That includes the upright 'L' and 'S' shapes from Tetris. Also 3x3 corners and 3x3 wider-step S-shapes, and T-shapes with a longer spur. Then let it use the 3-long horizontal and vertical bars as part of the standard random selection.

What it came up with is a lot of mazes that look like this:



That produces some quite long runs in the lower half of the maze that you couldn't get out of if ghosts were closing in from both ends. I don't think that's as playable.

I quite like what the stubby T-shapes do, so long as they don't occur too often, but otherwise I don't think any of the 3-high shapes suit this ratio of maze. Were it more vertical, tall 'L' and 'S' shapes would be OK. But I think 2x3 or 3x2 is a good shape limit overall. The only truly 3x3 shape I'll keep is the cross.

So the list of shapes my regular routine works with is a cross, all four orientations of the 3x2 'T', all four lying-down Tetris 'L' shapes, the two lying-down Tetris 'S' shapes, all four 2x2 corners, 2-long horizontal and vertical bars (17 shapes) plus 3-long horizontal and vertical bars if nothing else will fit (19 total).

Any more complex shapes (and the 'L's and 'S's too) can be broken down into smaller components. But the rest are essential to fill gaps without leaving single any unconnected wall nodes

[Joefish]

Just realised that the second maze in that 4-way pic above violates my rule about not having a straight run across the maze from one tunnel entrance to the other. Turns out there was a bug in the code so it was doing the check, then throwing away the result while it went off to pick a random colour for the maze walls. It also meant it was doing lots of unnecessary re-tries. Now fixed in the download so it should run quicker too.