Algorithm for generating a 2d maze

I have used a depth first search one time to good effect. It generates a good, random-looking maze.

Also available is a method where you recursively subdivide rectangles, which produces long corridors. This is called the recursive division method.

These algorithms and more can be found here.

Wikipedia has a great resource on maze generation. I've use randomized prims algorithm with great results. The division algorithm looks looks interesting but I've never used it.

Here is wikipedia example of prim's at work.

One easy way is to make a list of north walls and west walls, then permute them. Give each room a number. Then blow up one of the walls in the list, as long as the two rooms don't have the same number, then propagate one of the numbers to all the other rooms with the same number. Keep going until you run out of walls. This works for rectangular mazes or, really, any other maze where you can give a list of "potentially connected rooms". Plus, it's pretty straightforward to program.

I prefer the tightly wound mazes that Kruskal's Algorithm creates.

The standard description of Kruskal's Algorithm is inappropriate in that it fails to distinguish locations in the graph from location groups, while relying on a pun about datastructure choice, leading to description ambiguities that confuse novices. Therefore I reject Kruskal's termonology.

I will use the following terms:

• Graph
  • the maze itself.
• Node
  • a location in the maze. On a square maze, this is a square cell.
• Edge
  • the connection between two nodes. On a square maze, this is a 1-length bar.
• Tree Group
  • a set of nodes, which may be empty, arranged as a tree

And from those, we get:

1. Create a group GTG, for the Graph Tree Group, containing tree groups
2. Populate GTG with one tree group containing one node, for every location in your maze
3. Create an edge set E
4. Populate E with every valid edge in your maze
5. While there is more than one group in GTG, and while E is not empty:
6. Pick a random edge rE from E
7. Identify endpoints p1 and p2 of rE
8. Remove rE from E
9. Check which groups p1 and p2 belong to (p1g and p2g respectively).
10. If p1g and p2g are different, join tree group p1g and p2g at p1 -> p2, and rewrite all group ownership of one tree to the other, thus joining the trees.
11. Return to step 5.
12. If you have no edges left, but more than one tree, either the graph is not connected or there's a bug.
13. If you have just one tree, you have a complete no-loop maze.

I would also take a look at some of the algorithms used in Roguelike development. There's a good starting resource at Rogue Basin

You asked which one I used, so I will make sure to answer that. I used the Recursive Backtracker Algorithm in my maze game on Rootbeer Games.

This is evidence that I used the algorithm, please don't view it as an advertisement of my work.