Creating Pacman Labyrinth

[ichabod801]

If you want to create a random graph, there is an algorithm by David Wilson that creates a random graph such that all possible graphs have an equal chance of being chosen. Pick a random node to start with. Then pick another random node, and add an edge to the current node if it is not already in the graph. The second random node becomes the current node whether or not it was already in the graph. Repeat this process until all of the possible nodes are in the graph. At that point you have a random spanning graph. You can now add edges to that graph randomly until you have the number of edges you want.

Since pacman labyrinths tend to be symmetrical, you might want to generate a random graph and then reflect it once or twice.