How to create a random pacman maze

Question

Hello I have been working on an algorithm to generate a random pacman maze. I have seen a couple of articles but could not break down the logic. I am using the maze algorithm depth first search and then I mirror the maze to make each maze symetrical. I am running into issues like cleaning up the dead ends. If this is not possible I would also attempt another algorithm if anyone has their own logic to generate the random maze. Any help is appreciated. Thanks

Answer 1

I solved my problem and wanted to share. For starters I set the top row and first column and last column as a wall obstacle then I set a path on the second column, second to last row and second row so it surrounds the outer wall. Also keep in mind I am only creating 50% of the maze so when I am done I copy the maze so both sides are equal. Then I created a middle section surrounded by a wall for the area where the ghosts spawn. Then any part of the maze that hasn't been looked at I generated paths using the depth first search algorithm. After this was done I know that in a pacman maze there are no dead ends. What I did was check every cell that is part of the path that pacman can travel. If any cell has only 1 bordering cell then it is a dead end. If it is a dead end see if it can be connected to another path. If not set the dead end as a wall and check the maze again for any dead ends. After you follow these steps you will have a random maze with no dead ends that resembles the typical pacman maze.

Answer 2

I'd offer to do a random walk by dfs in the clean area (without any wall, in n*n matrix of 0's), after that fill the areas which are not covered by random walk (make them as wall), this also could cause to unused spaces, but this guarantee to have a long walk. you could set the size of walk arbitrary (e.g when your walk size arrived to (n^2)/2, you could stop the walk).

Answer 3

I created a random PacMan maze generator a long time ago on the C=64 using the depth first and elimination of dead-ends, but recently got challenged by my friend to do it again. Found a better way. Check it out at my site

Essentially, I created a grid of rooms with each direction having an open door (closed on the border except where the tunnel goes), then start closing the doors randomly according to the rule that there should never be more than 1 closed door in an adjacent room if 2 doors are closed, a third one would create a dead end. Just keep doing this randomly until all the potential door are either closed or open by the rule.

Mirroring was a bit more work, but I started with the basics and just built up the rules to allow for mirroring, ghost house location, minimum wall length (no single walled roundabouts) and maximum wall length, etc...