How Many Pac-Man Mazes Are There?

The place for codemasters or beginners to talk about programming any language for the Spectrum.
Post Reply
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

How Many Pac-Man Mazes Are There?

Post by Joefish »

Interesting question. And the answer is...

Image

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

Count them!!! :D

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.

(Sauce included in download!)
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

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...
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

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.
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

Ah, you mean these ones... yup, they don't look street legal to me either.
Image
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

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! :cry: *sniff*

Hopefully no more gaps or mini-roundabouts.

Not like Ghost's Revenge...
Image
'Street legal', well, really... :lol:
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

Aww crap.

Image

No idea how that's happened...
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

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.
Image
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

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.

Download the same link, code v09 in the .ZIP
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...
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

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.
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

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.
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

I'd heard he was doing Aladdin... :lol:

Not sure if it's a regular term, but the sprite engine that came with STOS on the Atari ST allowed you to designate a pixel on a sprite as your 'hot spot'. This meant that the sprite would be positioned relative to that point rather than its top-left corner.

With my maze shapes, because of the column order they're being filled in, I need to focus on whichever bit of the shape sticks out most on the left-hand-side. So for a left-pointing 'T' that's the tip of the 'T'. But for a right-pointing 'T', it's the top-left corner.
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

Joefish wrote: Tue Jun 30, 2020 5:37 pm I'd heard he was doing Aladdin... :lol:

Not sure if it's a regular term, but the sprite engine that came with STOS on the Atari ST allowed you to designate a pixel on a sprite as your 'hot spot'. This meant that the sprite would be positioned relative to that point rather than its top-left corner.

With my maze shapes, because of the column order they're being filled in, I need to focus on whichever bit of the shape sticks out most on the left-hand-side. So for a left-pointing 'T' that's the tip of the 'T'. But for a right-pointing 'T', it's the top-left corner.
I recall that it was also used on the Amiga version AMOS for the sprite routine. I didn't really use the AMOS sprite routine, used the BOB routine more.


Image
Some ideas for storing a pre-made map

Version A
At 26 bytes per map, 2 bytes per row with lots of bits left over.

Code: Select all

DEFG X....X.. ........
DEFG .X.X..X. X.......
DEFG X.X.XXX. X.......
DEFG X.X....X .X......
DEFG ........ ........
DEFG X.X.XX.X .X......
DEFG X.X.X.X. X.......
DEFG ....XX.. ........
DEFG XX.X...X .X......
DEFG .X..XX.. X.......
DEFG X..X.X.X ........
DEFG .X...... X.......
DEFG X...X.X. ........
This would make it easier to have a mix 'n' match top half and bottom half and then join them together and decode into the main map buffer

Version B
13 bytes, just store the left side only, decode it into a minibuffer, mirror flip the bits over into the other half and decode into the main map buffer.
The last 2 bits on the right are not used, every odd line has an extra bit at the front. Depends how easy it is to flip the bits.

Code: Select all

DEFG X....X ..
DEFG ..X.X. ..
DEFG X.X.XX ..
DEFG .X.X.. ..
DEFG ...... ..
DEFG .X.X.X ..
DEFG X.X.X. ..
DEFG .....X ..
DEFG XX.X.. ..
DEFG ..X..X ..
DEFG X..X.X ..
DEFG ..X... ..
DEFG X...X. ..


Version C
At 20 bytes per map, reading down each green lettered column, decoding into the main map buffer as you go.

Code: Select all

DEFG XX.XXXX. ;A
DEFG .XX..... ;B
DEFG ....X... ;C
DEFG X...XX.. ;D
DEFG .X.X.... ;E
DEFG .XX..... ;F
DEFG ....XX.. ;G
DEFG X....... ;H
DEFG .X.X..X. ;I
DEFG ..XXX... ;J
DEFG XX...X.. ;K
DEFG ..XXX... ;L
DEFG .X.X..X. ;M
DEFG X....... ;N
DEFG ....XX.. ;O
DEFG .XX..... ;P
DEFG .X.X.... ;Q
DEFG X...XX.. ;R
DEFG ....X... ;S
DEFG .XX..... ;T
Bomb Munchies uses 6 bytes per map, storing only the top right part. It mirror flips the bits in X then in Y, decoding them into the main buffer.
Tryanulas PacMunchies will pic one map for the top half and then pic another map, flip it into the lower half, mirror into Y and decode it.
That's 6bytes X 36maps = 216 bytes
Decoder routine = 150 bytes
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

What you've just done on a diagram is way the working memory of the map generation routine is arranged! Though it works rather wastefully with bytes, rather than bits. Come to think of it, there's also an extra byte for whether the white dot at the centre of each cell is filled or not. That is redundant but only once they are all filled.

But the point of generating them at random is you don't need to store any maps!

Having said that, I was thinking of converting the algorithm into C, reducing the resultant map down to a handful of bits, then running it thousands of times to see how many genuinely different mazes it can come up with... Be interesting to see if the resultant list of mazes is shorter or longer than the code to generate them! :D
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

Image


Here we go...
This will decode a 14 byte map, to the screen attributes. It will also flip the map at random.
14bytes per map times 16 maps = 224 bytes.
Plus you get the flipped maps for free! = 32 maps
I've hopefully kept the code below simple to read.

All that needs to be added is the code to put the correct junction graphic/data into the white spots and sort the ghost house door.

Code: Select all


Screen        Equ  16384
ScreenAttribs Equ  22528

; colour definitions
Flash                   Equ    128
Bright                  Equ     64

iBlack                  EQU      0
iBlue                   Equ      1
iRed                    Equ      2
iMagenta                Equ      3
iGreen                  Equ      4
iCyan                   Equ      5
iYellow                 Equ      6
iWhite                  Equ      7

pBlack                  EQU      0
pBlue                   Equ      8
pRed                    Equ     16
pMagenta                Equ     24
pGreen                  Equ     32
pCyan                   Equ     40
pYellow                 Equ     48
pWhite                  Equ     56




ORG 32768  


; this will decode a map to the screen attribute area.
                LD    DE,Map0001       ; at map data

                  ; get a random 0/1
                LD    A,R
                BIT   0,A
                CALL  Z,FlipTheMapRoutine

                LD    HL,ScreenAttribs
                INC   HL               ; move along place from the top left corner

 ; this draws the top bar with spaces for the junction parts
                LD    A,pCyan
                LD    B,10
topbarloop      LD    (HL),A
                INC   HL
                LD    (HL),A
                INC   HL
                INC   HL
                DJNZ  topbarloop
                INC   HL



 ; now let's get decoding!
                LD    B,7               ; loop counter for all 14 lines of map data
DecoderLoop     PUSH  BC                ; store loop counter

                LD    A,(DE)            ; get byte from map data
                PUSH  DE                ; store map place
                LD    DE,30             ; add offset
                LD    C,A

                LD    B,6               ; loop counter
COLUMNBARSLoop  PUSH  BC                ; store counter and C
                PUSH  HL                ; store screen attr address
                LD    A,pGreen          ; wall OK
                BIT   7,C               ; check the bit
                JR    NZ,CBplacecolour  ;
                LD    A,pWhite          ; not wanted value
CBplacecolour   LD    (HL),A            ; onto screen
                LD    BC,32             ; down a line
                ADD   HL,BC
                LD    (HL),A            ; onto screen
                ADD   HL,DE
                LD    (HL),A            ; onto screen
                LD    BC,32             ; up a line
                SBC   HL,BC
                LD    (HL),A            ; onto screen
                LD    A,E
                SUB   6
                LD    E,A
                POP   HL                ; recall the screen attr address
                INC   HL                ; move along
                INC   HL
                INC   HL
                POP   BC                ; recall the loop counter and C
                RL    C                 ; RotL C
                DJNZ  COLUMNBARSLoop

ROWBARS         LD    BC,47             ; offset to move to the correct place
                ADD   HL,BC             ; saves a PUSH/POP and then adding

; now do a row of lines
                POP   DE
                INC   DE                ; next map data
                LD    A,(DE)            ; read byte
                PUSH  DE                ; store map place

                LD    DE,26             ; add offset
                LD    C,A
                LD    B,5
ROWBARSloop     PUSH  BC                ; store counter and C
                PUSH  HL
                LD    A,pCyan           ; wall OK
                BIT   7,C               ; check the bit
                JR    NZ,RBplacecolour  ;
                LD    A,pWhite          ; not wanted value
RBplacecolour   LD    (HL),A            ; onto screen
                INC   HL
                LD    (HL),A
                ADD   HL,DE
                LD    (HL),A
                INC   HL
                LD    (HL),A
                LD    A,E
                SUB   6
                LD    E,A
                POP   HL                ; recall the screen attr address
                INC   HL                ; move along
                INC   HL
                INC   HL
                POP   BC                ; recall the loop counter and C
                RL    C                 ; RotL C
                DJNZ  ROWBARSloop
                XOR   A
                LD    BC,16             ; offset to move to the next place
                ADD   HL,BC
                POP   DE
                INC   DE                ; next map data
                POP   BC                ; recall loop counter
                DJNZ  DecoderLoop
                RET

FlipTheMapRoutine    ; this will flip the map data for good (until it is flipped again)
                     ; or you can copy the map data to a buffer and flip that instead
                PUSH  DE                ; store the map place
                PUSH  DE                ; put DE into HL
                POP   HL
                LD    BC,12
                ADD   HL,BC
                LD    B,6               ; loop counter
flipthemaploop  LD    C,(HL)
                LD    A,(DE)
                LD    (HL),A
                LD    A,C
                LD    (DE),A
                INC   DE
                DEC   HL
                DJNZ  flipthemaploop
                POP   DE                ; recall the map place
                RET

; Maps 14 bytes each
Map0001      ;  Wall data left hand side of the map
  ; first line is the | coloumn walls
  ; second line is the - row walls
DEFB %10000100   ; | ; 6bits from left
DEFB %01010000   ; - ; 5bits from left
DEFB %10101100   ; | ; 6bits from left
DEFB %10100000   ; - ; 5bits from left
DEFB %00000000   ; | ; 6bits from left
DEFB %10101000   ; - ; 5bits from left
DEFB %10101000   ; | ; 6bits from left
DEFB %00001000   ; - ; 5bits from left
DEFB %11010000   ; | ; 6bits from left
DEFB %01001000   ; - ; 5bits from left
DEFB %10010100   ; | ; 6bits from left
DEFB %01000000   ; - ; 5bits from left
DEFB %10001000   ; | ; 6bits from left
DEFB %11111100   ; - ; 5bits from left  ; this should be the same for all maps - great for a data marker



; end
[code]
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

Well, technically it can be done in 7 bytes. The whole area around the Ghost House is common to all variants, and there's no need to store the outer walls. You could even spare 3 bits to say which row the tunnel was on, or simply deduce it from a dead-end being formed on the left-hand side.
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

Image

Ah! If I read down each letter column, each map will be 11 bytes.
The decode routine and a map flipper in at 150 bytes - that's with my average programming skills.

16 maps 11 bytes per = 176 bytes + 150 byte routine = 326 bytes with another 16 flipped maps free
32 maps 11 bytes per = 352 bytes + 150 byte routine = 502 bytes with another 32 flipped maps free

Code: Select all

Org 32768
                LD    IX,Map0002   ; put map address into IX and save a headache
                CALL  UnpackMap

; all unpacked, now flip the map at a toss of a bit
                LD    A,R
                BIT   0,A
                RET   Z

FlipMap         LD    DE,ScreenAttribs+32
                LD    HL,ScreenAttribs+(20*32)
                LD    B,11
mainfliploop    PUSH  BC
                LD    B,32
fliponeline     LD    C,(HL)
                LD    A,(DE)
                LD    (HL),A
                LD    A,C
                LD    (DE),A
                INC   DE
                INC   HL
                DJNZ  fliponeline
                LD    BC,65536-64
                ADD   HL,BC
                POP   BC
                DJNZ  mainfliploop
                RET


UnpackMap       LD    HL,ScreenAttribs+32   ; unpack data here
                LD    DE,30                 ; offset to jump to the other side of the screen
                LD    B,5                   ; repeat counter
mainloop        PUSH  BC                    ; store repeat counter
                PUSH  HL                    ; store place

                CALL  ColARoutine           ;

                POP   HL                    ; recall place
                LD    BC,65536-31           ; move up one line and one place right
                ADD   HL,BC

                INC   IX                    ; next place for the map data
                LD    C,(IX+0)              ; read the byte

                DEC   DE                    ; decrease the jump value to the other side
                DEC   DE
                DEC   DE
                DEC   DE

                PUSH  HL                    ; store place
                LD    B,8                   ; counter
ColBloop        PUSH  BC                    ; store count and C

                LD    A,pCyan               ; wall OK
                BIT   0,C                   ; check the bit
                JR    NZ,ColBplacecolour    ;
                LD    A,pBlue               ; not wanted value
ColBplacecolour LD    (HL),A                ; onto screen
                PUSH  HL                    ; store for a moment
                INC   HL                    ; move along
                LD    (HL),A                ; onto screen
                ADD   HL,DE                 ; to the opposite side
                LD    (HL),A                ; onto the screen
                INC   HL                    ; move along
                LD    (HL),A                ; onto the screen
                POP   HL                    ; recall place
                LD    BC,96                 ; down 3 lines
                ADD   HL,BC
                POP   BC                    ; recall count and C
                RR    C                     ; RoL C
                DJNZ  ColBloop

                POP   HL                    ; recall place to top of screen
                LD    BC,34                 ; move one line down and two places
                ADD   HL,BC
                DEC   DE                    ; decrease the jump value
                DEC   DE
                INC   IX                    ; next place in the map data
                POP   BC                    ; recall the counter
                DJNZ  mainloop              ; loop until done



; this is here so that the middle column is completed
ColARoutine     LD    C,(IX+0)          ; read from the map data
                LD    B,7               ; counter
ColAloop        PUSH  BC                ; store count and C
                LD    A,pGreen          ; wall OK
                BIT   0,C               ; check the bit
                JR    NZ,ColAplacecolour  ;
                LD    A,pBlue           ; not wanted value
ColAplacecolour LD    (HL),A            ; onto screen
                LD    BC,32             ; down a line
                ADD   HL,BC
                LD    (HL),A            ; onto screen
                PUSH  HL                ; store for a moment
                ADD   HL,DE             ; jump to the other side of the screen
                LD    (HL),A            ; onto the screen
                SBC   HL,BC             ; up one line
                LD    (HL),A            ; onto the screen
                POP   HL                ; recall the place
                ADD   HL,BC             ; down two lines
                ADD   HL,BC
                POP   BC                ; recall count and C
                RR    C                 ; RoL C
                DJNZ  ColAloop
                RET                     ; exit to basic

Map0002 ; at 11 bytes
DEFB %01111011 ; A   ; left wall, bit 0 right is the top left corner of the map data
DEFB %10001101 ; B   ; next column in, bit 0 and bit 7 are the outer walls
DEFB %00010000 ; C
DEFB %11100011 ; D
DEFB %00001010 ; E
DEFB %10001101 ; F
DEFB %00110000 ; G
DEFB %10000011 ; H
DEFB %01001010 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K   ; middle column

I can see an advantage to a random map generator, but if it consumes more memory than a good bagful of pre-made maps then I dunno, but it'll certainly keep Pavero mapping busy!
This has been great fun and kept the grey matter ticking over.
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by Joefish »

It's actually really hard to just sit down with a 32x24 grid of squares and sketch out a half-decent maze, especially with only 1-wide walls but 2-wide passageways. Unless you apply at least some of the rules I've devised for this process, anyway. You keep painting yourself into a crap corner where nothing quite lines up. The thought of doing 20 or so that don't all look the same is quite challenging!

I have just refined the shape-fitting algorithm to better cope with a few patterns. Before, it would only ever fit a right-facing T just over the Ghost House, but now I can see it using it in more places. I've also added a couple of rules, that if there's a straight run between the two tunnels with no vertical walls in the way, or if there's fewer than 3 vertical walls in one half of the maze (not counting the permiter nor the row the Ghost House is on), then it re-runs the whole algorithm, up to four times, to try and ensure a maze with a decent amount of variety.

Next step is to convert the walls into specific UDGs for all the bends, ends and branches; place the power-pills; then fill the rest of the maze with dots.
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

Map designing, that is where I would've cracked out some Lego bricks and randomly placing them onto a huge grey baseboard, but you designed a map maker and made a bloody good job of it too! Glad that you're making progress on finding ways of getting the maps to behave better.

Spent an evening screen grabbing a whole lot of maps made by your map maker, numbering them up with 1s and 0s, and typing in the data and this is the result so far...

https://www.sendspace.com/file/p3i9gj

It contains 25 random maps made by your program, converted into 11 bytes per map, decodes, random flip a bit to mirror it, sort the corners and ends out, bung in the ghost door, do a simple print using the rom routine.
700 bytes with udgs.
Just need to byte align the map to a 256 boundary and add the dots.

Reminded me of the R'n'R Gnasher pacman clone re-released by Mastertronic.

Code: Select all

Screen        Equ  16384
ScreenAttribs Equ  22528


Org 32768

Start
                LD    A,2 ; always print to the top area
                CALL  05633
                LD    HL,UDGs
                LD    (23675),HL

                LD    IX,Map0001   ; put map address into IX and save a headache
               
pickagain       LD    A,R
                CP    25
                JR    NC,pickagain
                LD    B,A  ;1
                ADD   A    ;2
                ADD   A    ;4
                ADD   B    ;5
                ADD   A    ;10
                ADD   B    ;11
                LD    C,A
                LD    B,0
                ADD   IX,BC


mapaa

                CALL  UnpackMap
                ; all unpacked,
                CALL  FlipMap      ; now flip the map at a toss of a bit
                CALL  PutCornersIn ; and place the ghost door


PrintTheMapToTheScreen ;
                ; Print AT 0,0
                LD    A,22  ;Print AT control
                RST   16
                XOR   A     ; 0
                RST   16
                RST   16
                 ;
                LD    HL,Map           ; place of the unpacked map data
                LD    BC,768-64        ; amount of bytes to process
printloop       LD    A,(HL)           ; read byte
                ADD   144              ; add the UDG offset
                RST   16               ; print the UDG to the scree
                INC   HL               ; shuffle along the map data
                DEC   BC               ; decrease the counter
                LD    A,B              ;
                OR    C                ; does B and C match zero?
                JR    NZ,printloop     ; JR if no
                RET


;---------------------------------------------------------------
FlipMap         LD    A,R
                BIT   0,A
                RET   Z
                LD    DE,Map+32
                LD    HL,Map+(20*32)
                LD    B,11
mainfliploop    PUSH  BC
                LD    B,32
fliponeline     LD    C,(HL)
                LD    A,(DE)
                LD    (HL),A
                LD    A,C
                LD    (DE),A
                INC   DE
                INC   HL
                DJNZ  fliponeline
                LD    BC,65536-64
                ADD   HL,BC
                POP   BC
                DJNZ  mainfliploop
                RET

;---------------------------------------------------------------
PutCornersIn    LD    IX,Map
                LD    B,8            ; Counter for rows
Cornerloop      PUSH  BC             ; store counter
                LD    B,11           ; Counter for columns
Cornerbitsloop  XOR   A              ; set A to zero
                LD    D,A            ; D to zero ; part of the jump offset, saves a byte
                LD    C,A            ; C to zero for totals
CheckUP         CP    (IX-32)        ; is the square above empty
                JR    Z,Exitup       ; yes, do JR
                SET   0,C            ; no, add 1
Exitup
CheckRIGHT      CP    (IX+1)         ; is square to the right empty
                JR    Z,Exitright    ; yes, do JR
                SET   1,C            ; no, add 2
Exitright
CheckDOWN       CP    (IX+32)        ; is square below empty
                JR    Z,Exitdown     ; yes, do JR
                SET   2,C            ; no, add 4
Exitdown
CheckLEFT       CP    (IX-1)         ; is squre to the left empty
                JR    Z,Exitleft     ; yes, do JR
                SET   3,C            ; no, add 8
Exitleft
                LD    (IX+0),C       ; put C into the empty square
                LD    E,3            ; offset jump
                ADD   IX,DE          ; move along
                DJNZ  Cornerbitsloop ; loop
                LD    E,63           ; offset jump to move down 2 lines
                ADD   IX,DE          ; move
                POP   BC             ; recall counter
                DJNZ  Cornerloop     ; loop

PlaceTheGhostDoor
                LD    HL,GhostDoorData
                LD    DE,Map+(9*32)+13
                LD    BC,5
                LDIR
                RET
GhostDoorData   DEFB 8,0,0,0,2


;---------------------------------------------------------------
UnpackMap       LD    HL,Map+32             ; unpack data here
                LD    DE,30                 ; offset to jump to the other side of the screen
                LD    B,5                   ; repeat counter
mainloop        PUSH  BC                    ; store repeat counter
                CALL  ColARoutine           ;
                LD    BC,64833 ;65536-31-768+96           ; move up one line and one place right
                ADD   HL,BC
                DEC   DE                    ; decrease the jump value to the other side
                DEC   DE
                DEC   DE
                DEC   DE

                INC   IX                    ; next place for the map data
                LD    C,(IX+0)              ; read the byte

                LD    B,8                   ; counter
ColBloop        PUSH  BC                    ; store count and C

                LD    A,10                  ; wall OK
                BIT   0,C                   ; check the bit
                JR    NZ,ColBplacecolour    ;
                XOR   A                     ; not wanted value
ColBplacecolour LD    (HL),A                ; onto screen
                PUSH  HL                    ; store for a moment
                INC   HL                    ; move along
                LD    (HL),A                ; onto screen
                ADD   HL,DE                 ; to the opposite side
                LD    (HL),A                ; onto the screen
                INC   HL                    ; move along
                LD    (HL),A                ; onto the screen
                POP   HL                    ; recall place
                LD    BC,96                 ; down 3 lines
                ADD   HL,BC
                POP   BC                    ; recall count and C
                RR    C                     ; RoR C
                DJNZ  ColBloop

                LD    BC,34-768             ; move one line down and two places
                ADD   HL,BC
                DEC   DE                    ; decrease the jump value
                DEC   DE
                INC   IX                    ; next place in the map data
                POP   BC                    ; recall the counter
                DJNZ  mainloop              ; loop until done



; this is here so that the middle column is completed
ColARoutine     LD    C,(IX+0)          ; read from the map data
                LD    B,7               ; counter
ColAloop        PUSH  BC                ; store count and C
                LD    A,5               ; wall OK
                BIT   0,C               ; check the bit
                JR    NZ,ColAplacecolour  ;
                XOR   A                 ; not wanted value ; wipes old data too!
ColAplacecolour LD    (HL),A            ; onto screen
                LD    BC,32             ; down a line
                ADD   HL,BC
                LD    (HL),A            ; onto screen
                PUSH  HL                ; store for a moment
                ADD   HL,DE             ; jump to the other side of the screen
                LD    (HL),A            ; onto the screen
                SBC   HL,BC             ; up one line
                LD    (HL),A            ; onto the screen
                POP   HL                ; recall the place
                ADD   HL,BC             ; down two lines
                ADD   HL,BC
                POP   BC                ; recall count and C
                RR    C                 ; RoR C
                DJNZ  ColAloop
                RET                     ;

DEFW 255,255
;---------------------------------------------------------------

Map0001
DEFB %01111011; A
DEFB %10101101; B
DEFB %00000000; C
DEFB %11010011; D
DEFB %00101000; E
DEFB %10110111; F
DEFB %00000100; G
DEFB %11000101; H
DEFB %00001000; I
DEFB %10111011; J
DEFB %01000010; K

Map0002
DEFB %01111011 ; A
DEFB %10101101 ; B
DEFB %00000000 ; C
DEFB %11010011 ; D
DEFB %00011010 ; E
DEFB %11000001 ; F
DEFB %00010101 ; G
DEFB %10000101 ; H
DEFB %00001000 ; I
DEFB %11111011 ; J
DEFB %00000010 ; K

Map0003
DEFB %01111110 ; A
DEFB %10001011 ; B
DEFB %00100000 ; C
DEFB %11010101 ; D
DEFB %00010100 ; E
DEFB %10010011 ; F
DEFB %00100100 ; G
DEFB %11000111 ; H
DEFB %00001000 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K

Map0004
DEFB %01101111 ; A
DEFB %10110001 ; B
DEFB %00000100 ; C
DEFB %11001011 ; D
DEFB %00010000 ; E
DEFB %10011111 ; F
DEFB %00100000 ; G
DEFB %10000101 ; H
DEFB %00101000 ; I
DEFB %10111011 ; J
DEFB %01000010 ; K

Map0005
DEFB %01101111 ; A
DEFB %10110101 ; B
DEFB %00000000 ; C
DEFB %11001011 ; D
DEFB %00101010 ; E
DEFB %10001101 ; F
DEFB %01010000 ; G
DEFB %10000011 ; H
DEFB %00001010 ; I
DEFB %11111001 ; J
DEFB %00000011 ; K

Map0006
DEFB %01111110 ; A
DEFB %10001011 ; B
DEFB %00100000 ; C
DEFB %11010101 ; D
DEFB %00011010 ; E
DEFB %10010011 ; F
DEFB %00100100 ; G
DEFB %11000001 ; H
DEFB %00001010 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K

Map0007
DEFB %01111110 ; A
DEFB %10100011 ; B
DEFB %00000100 ; C
DEFB %11011001 ; D
DEFB %00010010 ; E
DEFB %10000001 ; F
DEFB %00110101 ; G
DEFB %10000101 ; H
DEFB %00101000 ; I
DEFB %10111011 ; J
DEFB %01000010 ; K

Map0008
DEFB %01111111 ; A
DEFB %10001001 ; B
DEFB %00100010 ; C
DEFB %10110011 ; D
DEFB %00001000 ; E
DEFB %11100111 ; F
DEFB %00001000 ; G
DEFB %11000101 ; H
DEFB %00001000 ; I
DEFB %10111011 ; J
DEFB %01000010 ; K

Map0009
DEFB %01111111 ; A
DEFB %10001001 ; B
DEFB %00010010 ; C
DEFB %11010001 ; D
DEFB %00000010 ; E
DEFB %11111001 ; F
DEFB %00000001 ; G
DEFB %10000101 ; H
DEFB %01001000 ; I
DEFB %10111011 ; J
DEFB %00100010 ; K

Map0010
DEFB %01110111 ; A
DEFB %10011001 ; B
DEFB %00100010 ; C
DEFB %10100011 ; D
DEFB %00001000 ; E
DEFB %11010111 ; F
DEFB %00100100 ; G
DEFB %11000001 ; H
DEFB %00001010 ; I
DEFB %10111001 ; J
DEFB %01000011 ; K

Map0011
DEFB %01111110 ; A
DEFB %10100011 ; B
DEFB %00000100 ; C
DEFB %11010001 ; D
DEFB %00000010 ; E
DEFB %10101001 ; F
DEFB %00110101 ; G
DEFB %10000101 ; H
DEFB %00101000 ; I
DEFB %10111011 ; J
DEFB %01000010 ; K

Map0012
DEFB %01111111 ; A
DEFB %10100101 ; B
DEFB %00001000 ; C
DEFB %11001011 ; D
DEFB %00100010 ; E
DEFB %10110011 ; F
DEFB %00001000 ; G
DEFB %11000101 ; H
DEFB %00001010 ; I
DEFB %10111001 ; J
DEFB %01000011 ; K

Map0013
DEFB %01111111 ; A
DEFB %10001001 ; B
DEFB %00100010 ; C
DEFB %11010011 ; D
DEFB %00010100 ; E
DEFB %10100101 ; F
DEFB %00001001 ; G
DEFB %11000101 ; H
DEFB %00001000 ; I
DEFB %10111011 ; J
DEFB %01000010 ; K

Map0014
DEFB %01111011 ; A
DEFB %10001101 ; B
DEFB %00100000 ; C
DEFB %10010011 ; D
DEFB %00010010 ; E
DEFB %11001101 ; F
DEFB %00101000 ; G
DEFB %11000011 ; H
DEFB %00001010 ; I
DEFB %10111001 ; J
DEFB %01000011 ; K

Map0015
DEFB %01101111 ; A
DEFB %10110001 ; B
DEFB %00000010 ; C
DEFB %11001011 ; D
DEFB %00010100 ; E
DEFB %11100111 ; F
DEFB %00001000 ; G
DEFB %10000001 ; H
DEFB %00001010 ; I
DEFB %11111001 ; J
DEFB %00000011 ; K

Map0016
DEFB %01111111 ; A
DEFB %10001001 ; B
DEFB %00100000 ; C
DEFB %10110111 ; D
DEFB %00000000 ; E
DEFB %11011001 ; F
DEFB %00100000 ; G
DEFB %10000111 ; H
DEFB %00001000 ; I
DEFB %11111001 ; J
DEFB %00000011 ; K

Map0017
DEFB %01111111 ; A
DEFB %10010001 ; B
DEFB %00000010 ; C
DEFB %11101011 ; D
DEFB %00010100 ; E
DEFB %10000111 ; F
DEFB %00101000 ; G
DEFB %11000001 ; H
DEFB %00001010 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K

Map0018
DEFB %01111111 ; A
DEFB %10100101 ; B
DEFB %00001000 ; C
DEFB %11001011 ; D
DEFB %00000010 ; E
DEFB %10110011 ; F
DEFB %01001000 ; G
DEFB %10000101 ; H
DEFB %00001000 ; I
DEFB %11111011 ; J
DEFB %00000010 ; K

Map0019
DEFB %01111011 ; A
DEFB %10101101 ; B
DEFB %00000000 ; C
DEFB %11010011 ; D
DEFB %00100010 ; E
DEFB %10101101 ; F
DEFB %01001000 ; G
DEFB %10000011 ; H
DEFB %00001010 ; I
DEFB %11111001 ; J
DEFB %00000011 ; K

Map0020
DEFB %01101111 ; A
DEFB %10110001 ; B
DEFB %00000100 ; C
DEFB %11001011 ; D
DEFB %00000010 ; E
DEFB %10110011 ; F
DEFB %00101000 ; G
DEFB %10000101 ; H
DEFB %01001010 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K

Map0021
DEFB %01110111 ; A
DEFB %10011001 ; B
DEFB %00100010 ; C
DEFB %10100011 ; D
DEFB %00000100 ; E
DEFB %11110101 ; F
DEFB %00001000 ; G
DEFB %11000011 ; H
DEFB %00001010 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K

Map0022
DEFB %01110111 ; A
DEFB %10011001 ; B
DEFB %00100010 ; C
DEFB %10100011 ; D
DEFB %00000100 ; E
DEFB %11110001 ; F
DEFB %00000101 ; G
DEFB %11000101 ; H
DEFB %00001000 ; I
DEFB %10111011 ; J
DEFB %01000010 ; K

Map0023
DEFB %01111111 ; A
DEFB %10100101 ; B
DEFB %00000000 ; C
DEFB %11011011 ; D
DEFB %00000000 ; E
DEFB %10111111 ; F
DEFB %01000000 ; G
DEFB %10000101 ; H
DEFB %00001000 ; I
DEFB %11111011 ; J
DEFB %00000010 ; K

Map0024
DEFB %00111111 ; A
DEFB %11010001 ; B
DEFB %00000100 ; C
DEFB %10101011 ; D
DEFB %00110010 ; E
DEFB %10001001 ; F
DEFB %00110000 ; G
DEFB %10000111 ; H
DEFB %00101000 ; I
DEFB %10111001 ; J
DEFB %01000011 ; K

Map0025 ; at 11 bytes
DEFB %01111011 ; A   ; left wall, bit 0 right is the top left corner of the map data
DEFB %10001101 ; B   ; next column in, bit 0 and bit 7 are the outer walls
DEFB %00010000 ; C
DEFB %11100011 ; D
DEFB %00001010 ; E
DEFB %10001101 ; F
DEFB %00110000 ; G
DEFB %10000011 ; H
DEFB %01001010 ; I
DEFB %10111001 ; J
DEFB %00100011 ; K   ; middle column

DEFW 255





UDGs
DEFB 000,000,000,000,000,000,000,000
DEFB 195,195,195,195,195,231,126,060
DEFB 063,127,224,192,192,224,127,063
DEFB 195,195,192,192,192,224,127,063
DEFB 060,126,231,195,195,195,195,195
DEFB 195,195,195,195,195,195,195,195
DEFB 063,127,224,192,192,192,195,195
DEFB 195,195,192,192,192,192,195,195
DEFB 252,254,007,003,003,007,254,252
DEFB 195,195,003,003,003,007,254,252
DEFB 255,255,000,000,000,000,255,255
DEFB 195,195,000,000,000,000,255,255
DEFB 252,254,007,003,003,003,195,195
DEFB 195,195,003,003,003,003,195,195
DEFB 255,255,000,000,000,000,195,195
DEFB 195,195,000,000,000,000,195,195
DEFB 060,126,231,195,195,231,126,060


DEFB 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
DEFB 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Map

DEFB 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
User avatar
MatGubbins
Dynamite Dan
Posts: 1238
Joined: Mon Nov 13, 2017 11:45 am
Location: Kent, UK

Re: How Many Pac-Man Mazes Are There?

Post by MatGubbins »

Dotty thoughts...
Image
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by 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.

Image

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:

Image

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.
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by 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:

Image

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
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: How Many Pac-Man Mazes Are There?

Post by 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.
Post Reply