|
CSE Home | 326 Home | About Us | Search | Contact Info |
Maze GenerationThere are several ways to go about generating a maze from a grid. We would like to generate mazes with the following two properties:
Figure 1. A maze with a cycle Depth first searchThis is very similar to the depth first search algorithm you used to search the maze. The version included in your code is an iterative version; below is the recursive version. Generate( Maze m ) Choose random cell to start at and initialize stack Call DFS( start , stack ) DFS( MazeCell current, Stack stack ) Choose a random neighbor of current that has all its walls up If there is no neighbor of current with all its walls up Pop a cell off of the stack and call DFS( popped cell, stack ) Else Knock down wall between current and neighbor Push current onto the stack call DFS( neighbor cell, stack ) Kruskal's algorithmThe algorithm described in your book, section 8.7, is Kruskal's algorithm. Think of the maze as a group of disjoint sets, one for each maze cell. Then union is equivalent to knocking down a wall between one set and another, so that there is now a passage between them. The algorithm works by performing a series of finds, and unioning sets with different labels. Note that once two sets have been unioned, knocking down any further walls within that set would produce an imperfect maze. The algorithm is complete when all the maze cells are within the same set and we are unable to perform any more unions.Generate( Maze m ) While (# Walls Down < Total # Cells - 1) Choose random cell current Choose random neighbor of current that has a wall up between it and current If such a neighbor exists Find the labels of current and neighbor If they are different, union them, knock down the wall, and add to # Walls Down Note that the condition under which a neighbor is chosen is different than the condition in depth first search. In DFS we choose a neighbor with all of its walls up (thus guaranteed to be disconnected); in Kruskal we just look for a neighbor with a wall up between it and the current cell. Union/find takes care of the rest. Prim's algorithm (Above and Beyond)Prim's algorithm and Kruskal's algorithm solve the same underlying problem. In fact, if you were to weight which walls to knock down and use a priority queue to choose walls with the lowest weight first, the Prim and Kruskal algorithms will form the same maze (in a different way). The algorithm is as follows:Generate( Maze m ) Choose a random cell, mark it visited, and add it to the list While there are cells on the list Pick a cell off the list Add its neighbors to the list Knock down a wall between it and a neighbor Mark that cell visited |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to gyngve] |