## How Many Pac-Man Mazes Are There?

The place for codemasters or beginners to talk about programming any language for the Spectrum.
Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### How Many Pac-Man Mazes Are There?

Interesting question. And the answer is...

Count them!!!

This is a Speccy landscape-ratio version of Shaun Lebron's maze generation concepts that you can see here:
https://shaunlebron.github.io/pacman-mazegen/

I've added my own take on it and adapted it for the smaller, wider Spectrum screen.
It works by making each of the white 'dots' you see the centre of a cell, so within the outer walls of the maze you have a grid of 9x6 cells.
The right-hand half are mirrored about the centre-line, so effectively you're working with a grid of 5x6 cells.
Then I add the Ghost House in the centre as permanent walls.
Next I pick one of a few pre-defined random arrangements for the centre line above and below the Ghost-House. The player may start immediately below the house, or one cell further down (if not obstructed by a vertical wall).
Then I pick one of a pre-defined set of left-hand walls, with or without tunnels and wall spikes poking inward. These are carefully prepared so as to only have one or no tunnel, and never to create a dead-end between two spikes.

Now onto the meaty bit of the algorithm. It has 16 different Tetris-like 3x3 shapes, and it works its way down each column, counting columns from left-to-right, picking a random shape and trying to fit it. If it can't it moves onto the next shape in the list, and so on, until it's exhausted all possibilities. It also won't place a shape that leaves a single cell of wall isolated and not connected to at least one other other cell. And so far, I haven't come across a maze that has just single isolated wall cells (unconnected white dots) left. But you never know with random numbers...

When you run it, you can just keeping tapping a key for a new, freshly-minted and minty-fresh magically undiscovered maze every time.
And don't forget to count them.

3 x

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

Oh, ouch, I just got a miss-fire!
Three white unconnected dots in a right-facing T-shape above the Ghost-House!

I wondered about leaving that particular shape off the list. A pain that I have 16 shapes which works nicely with a random number generator as you just AND 15 to your random byte to pick a shape. I suppose I could add it as a 17 shape that can't be picked at random, but can be used by the algorithm if nothing else will do...

Most other gaps can be filled by one, two or more other smaller pieces. But not a T-shape...
0 x

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

OK, fixed that. I've added the right-facing 'T' as a seventeenth shape it can't pick at random but will get round to if nothing else fits. Re-download the link for the update.

It does have a left-facing 'T', but it seems to use that fairly rarely. Whereas the up- and down-facing Ts are quite common. There's also a cross, which is the most complicated shape it has. There are all four possible right-angle corners, but with the longer L-shapes I've only put the horizontally stretched ones in, not vertical. And the same with the Tetris 'S' shapes; only the lying down variants, not the uprights. Simply because the maze is wider than it is tall. It needs to know some 3-high shapes to fill all possible spaces, but - so far - it doesn't seem to need all possible variants.
0 x

MatGubbins
Manic Miner
Posts: 678
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

### Re: How Many Pac-Man Mazes Are There?

Ah, you mean these ones... yup, they don't look street legal to me either.
0 x
Bomb Munchies Ver2210 4th July 2020 (look for the blue download box ) If you get a time-out message and live in the UK then try after 9pm-3am.
Send me a PM and I can email it to you too. Kent, UK

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

Yep, just done another upload (code v08 in the download). I've moved the 3-high vertical bar to be a 'shape of last resort' and moved the right-facing T into the first 16, so it should be randomly selecteable now. I did just see a maze where it placed the left- and right-pointing T-shapes back to back. I was so proud! *sniff*

Hopefully no more gaps or mini-roundabouts.

Not like Ghost's Revenge...

'Street legal', well, really...
0 x

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

Aww crap.

No idea how that's happened...
0 x

MatGubbins
Manic Miner
Posts: 678
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

### Re: How Many Pac-Man Mazes Are There?

New version working rather well.... oh, um, apart from that one.

Are you also having the ghost house door and player start position flip top/bottom?

I done that within Bomb Munchies/Tryantulas PacMunchies level and it adds a bit more variety.
1 x
Bomb Munchies Ver2210 4th July 2020 (look for the blue download box ) If you get a time-out message and live in the UK then try after 9pm-3am.
Send me a PM and I can email it to you too. Kent, UK

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

OK, I think I've cracked it now. Or at least, fixed that last bug.

When it first picked a shape, it calculated 'shape_ID - 1' to work out the last shape it should try. But when it picked shape '0' first, the sum '0 - 1' wrapped around to shape 15, not 16. So it thought it had got to the end of the list one early, and so missed off the 'in case of emergency' extra shape on the end (which was the 3-tall bar - a handy clue).

I've re-written the logic to what it should have been in the first place: note the shape_ID of the shape you picked initially (at random), then wait until that same shape_ID comes up again, and then quit.

MatGubbins wrote:
Sat Jun 27, 2020 7:45 pm
Are you also having the ghost house door and player start position flip top/bottom?
I done that within Bomb Munchies/Tryantulas PacMunchies level and it adds a bit more variety.
It's not something I thought of. I had a look at Pac-Man and the various Ms. Pac-Man mazes and tried to pick out a few common factors, and try to determine what factors helped with playability. And that's what fed into the few default layouts I had to fit on the centre line.

In Pac-Man you start at the bottom, and generally that part of the maze is a bit easier to play than the top. There's a horizontal run right across the bottom, so I have one or no spikes up from the bottom wall, to keep this characteristic. And I always have a vertical wall right above the Ghost House to split the top of the maze into two halves. That division can run right to the top wall to make it trickier to swap sides. Or if there's a passage over the top, there can be spikes down from the top either side of that, to split the top into three sections.

So generally, I don't want to invert the Ghost House as it would mess up that planning. Having said that, once complete, the whole maze could be flipped upside-down. Then the player could start at the top and the Ghosts exit downwards...
0 x

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

Some of the mazes it comes up with are a little too reliant on horizontal runs. I'm maybe not so keen on ones where you can run straight across from the tunnel on one side to the other. But I'm not sure whether I want to tackle stuff like that or just leave it to chance.

I suppose I could add a few final rules to it. e.g. count the number of vertical walls in the maze, and check for at least one vertical wall on a row with a tunnel at the ends, and tell it to re-start the algorithm if it doesn't quite work...

Or I could maybe add the 2-long and 3-long horizontal bars to the 'In-Case-Of-Emergencies' section at the end of the shape list, so they occur far less frequently. I could put the two vertical Tetris 'S-shapes' in their place instead...

EDIT: Nah, tried the latter. It never seems able to fit in the vertical 'S's, and it just biases the maze to be lots of vertical runs.
0 x

Joefish
Manic Miner
Posts: 839
Joined: Tue Nov 14, 2017 10:26 am

### Re: How Many Pac-Man Mazes Are There?

Hmm - looks like some shapes aren't getting picked randomly.
The right-facing 'T' and the 3-high Vertical Bar look like they only ever get picked for the missing shapes in the examples above. They just don't appear anywhere else.

I think it's an issue that could be solved by having a 'hot-spot' on each shape. Since it's trying to fit them working down each column and columns left-to-right, I think it will always favour putitng a 2-high shape in a gap before it moves down to the next cell and realises there may be space for a 3-high shape ahead.

By designating a 'hot-spot' on each shape I could tell it to compare different shapes in a slightly higher or lower position when looking at all the possibilities around an individual single cell in the maze. Then shapes which are 3-high and flat on their left-hand-side might get picked more.
0 x