A Programmer Spent Months Generating Pac-Man Mazes. It Was Time Well Spent.
A programmer has developed a procedural Pac-Man maze generator.
Decades-old Pac-Man is a favorite subject among coders, especially if they grew up playing it.
The code works by dropping modified tetronimoes and then tracing paths around them.
In a new open source software experiment, developer Shaun LeBron has made a random Pac-Man level generator. The algorithm combines elements of mazemaking, snowflake cutting, and even crossword grid mechanics and is a great example of pathmaking in code.
👾 You love badass games. So do we. Let's nerd out over them together.
Coding even simple mazes is really tough. Think about how hard it would be to sit down and draw a functional maze if you didn’t have a special level of knowledge in advance of how that process works. (We’ll give you some tips in a second, and you can try it yourself.)
A Pac-Man level is a special case of maze: there’s no entrance or exit, there’s not only one path, and you can navigate it in a variety of ways. The goal is to traverse the entire path length contained in the level in order to collect the little blippies for points. And there are established standards within the Pac-Man franchise. The player can double back at any time and navigate how they want, but the maze itself can’t have sharp turns, for example.
LeBron’s code treats the developing grid as just one half, which the code mirrors out at the end, ensuring the symmetry required. A path is one grid square wide in the games, while the walls are technically two squares wide—their art has a built-in buffer that appears to add border space to the path.
This is classic early computer game graphics finagling, the same way Luigi was just a palette-flipped Mario.
The algorithm develops paths by starting with a grid, where cells can be coded with different identities depending on how many walls they have. If you’ve ever played the classic game Dots, where you try to close boxes on your opponent using a dot grid, you have experience taxonomizing these cell shapes.
But the way LeBron builds the cells is even cooler. “We start by stacking Tetris pieces on a 5x9 grid,” his GitHub explains. “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.”
The shapes (in Tetris canon, they’re tetronimoes, like dominoes) are tiled together to fill the grid. Like in a crossword grid, a series of predictable modules fill the space and determine what the paths are.
The Tetris-like shapes become the walls in the final maze, constricting until they’re in the scale of the Pac-Man art style. To fit the odd 28-by-31 grid in the game, LeBron’s algorithm pulls certain pieces by one “pixel” in height or width until it’s ready to mirror into the final grid. Using larger puzzle pieces lets him ensure everything will fit snugly into a nice-looking maze, and the rest is pretty tough coding.
You Might Also Like
