Pac-Man Maze Generation

Work in Progress

Generating random Pac-Man mazes is a deceptively difficult problem that I spent some months working on. It is not easy to describe clearly. I hope you are patient. This page is an effort to begin communicating how the algorithm works. It will slowly be refined (your feedback appreciated) until it is all stated as clearly as possible.

Contraints

The mazes are built carefully to closely match design patterns deduced from the original maps found in Pac-Man and Ms. Pac-Man:

Map is 28x31 tiles.
Paths are only 1 tile thick
No sharp turns (i.e. intersections are separated by atleast 2 tiles).
There are 1 or 2 tunnels
No dead-ends.
Only I, L, T, or + wall shapes are allowed, including the occasional rectangular wall.
Any non-rectangular wall pieces must only be 2 tiles thick.

It's like Tetris

We start by stacking tetris pieces on a 5x9 grid. Gravity pulls the pieces in the left direction rather than down. The edges of the resulting tetris pieces correspond to walkable paths in the maze. This grid is then mirrored across the left vertical axis to create a symmetric map, then scaled by 3 to form an original-size 28x31 map.

Definitions

For clarity, I call the squares in the initial 5x9 grid, cells, and the squares in the final 28x31 grid, tiles. So, this algorithm first creates the cells and transforms them into tiles

Simple Model

Shown in the above diagram titled "Simple Model" is the 5x9 grid of tetris pieces. The pieces are created one cell at a time using some algorithm to limit the type of pieces at certain locations (they are numbered to show the order of creation).

The ghost pen and the edge between rows 7 and 8 at column 1 are present in every map, since the starting location of Pac-Man and the ghost pen location are constant.

Height and Width Adjustments

Cells are directly transformed into a 3x3 group of tiles. Unfortunately, this creates a resulting map that is too short by 1 tile and too wide by 1 tile. So, we increase the height of one cell for every column, and decrease the width of one cell for every row, allowing the generated map to fit in the exact dimensions of the original game.

Shown in the above diagrams titled "Height Adjustments" and "Width Adjustments", the highlighted cells are the candidate cells whose size can be changed without creating ugly walls (i.e. walls that have non-uniform thickness).

Arrows occupy cells which have been chosen for size adjustment. Care is taken to prevent discontinuities in the edges as a result of the shifting of cells from the size change.

Border Cells and Tunnels

I won't explain too much about this right now. But the above diagram titled "Border Cells and Tunnels" has arrows to indicate the tunnel candidates. The highlighted cells show the type of tunnel candidates by color. Some cell edges are erased to create some variation in how walls connect with the boundary of the map (shown in green). The tunnel creation algorithm is sophisticated in how it chooses different types of tunnels.

Final Paths

When the cells are finally transformed into tiles, what you are left with is shown in the diagram above titled "Final Paths". Here you can directly map a cell to a 3x3 group of tiles. You can even pick out the cells whose height are width have been adjusted by 1 tile in this map.

Final Tiles

See how the above diagram titled "Final Tiles" differs from "Final Paths". The paths are shifted from the tile edges toward the tile centers. Each tile with a path going through its center is turned into a path tile. Finally, any tile that touches a path tile becomes a wall tile. The map structure is now complete.

Results

Click here to see many generated Pac-Man mazes together.