Construction of mazes using Union-Find algorithm

This page displays an applet demonstrating a method of construction of mazes using the Union-Find algorithm. The ideas are explained in many places, for example in M. A. Weiss, Data Structures and Algorithm Analysis in Java, Second edition, Addison Wesley, Chapter 8. The algorithm is usually discussed in connection with the Kruskal's algorithm for constructing minimal spanning trees, but it can also be used to construct nice looking mazes.

To display, consruct, or solve the maze, click on the bluish button, labeled "Show the maze". Depending on your security setting, a yellow bar at the top of the page may appear warning you that running this applet ("ActiveX controls" it will say) maybe dangerous. In that case, click on this yellow bar and allow the applet to be run. Trust me. In any case, after you click on the bluish button, the tree will appear in a separate window. You may resize the window, minimize it, in which case its icon will appear in the bottom tray so you can restore it, or close it altogether. If this last action is taken, you must click on the bluish button again to restore the applet.

The idea is as follows: we start with an array of rectangles, something like this:

Inside each rectangle we place a vertex of a graph, marked in red. We then go and randomly select an interior wall between some two adjacent rectangles. If the corresponding vertices are not part of the same component of the graph, we remove the wall and draw an edge between the two vertices, combining the relevant two components into one. If the vertices are connected, we keep the wall. The first few walls, of course, will be removed, the algorithm becomes less trivial after several steps.

To illustrate a point, assume that after removing few of the walls, and joining the corresponding vertices, we arrive at the following situation:

The wall between the vertices R and S is not eligible for removal, because both R and S belong to the same connected component. Removing the wall between the vertices P and Q is, however, allowed because P and Q belong to different components. Removing this wall, and joining the vertices P and Q results in the following situation:

We continue to choose one of the remaining walls at random, and either keep it, or remove it and join the two relevant components together. We do this until all the vertices are in one connected component which forms a tree, i.e., it is possible to get from any vertex to any other vertex. At this point the path between any two vertices is unique, which in terms of the maze means there is only one solution. To make the maze a bit more spicier, we additionally remove 30 randomly selected walls.

The Union-Find algorithm is a method which allows us to decide quickly if given wall is to be removed or not. Check it out. The maze is actually solved either by the depth first search using a stack, or the breadth first search using a queue: Start at the entrance and search until you stumble on the exit. The queue solution actually produces the shortest solution.

Any comments are always welcomed:
Back to Drobot's home page