Pages

Friday, April 1, 2011

Building a Maze

I always like to discover some cool ways of using a simple data structure or algorithm to simplify a piece of code. Yesterday I overheard a conversation about Maze construction and the Disjoint-Set data structure, often considered used for optimization purposes only. So, I decided to try and implement this small example of how to quickly create a maze using this data structure.

The Disjoint-Set, for those who are not familiar, is a data structure that allows to keep track of groups, letting you join groups and find the group to which a specific component belongs, all in O(Log*(n)).
For more info, read: http://en.wikipedia.org/wiki/Disjoint-set_data_structure.

Now, lets think of a maze as a grid of cells. For cells X and Y, you can reach from X to Y through the winding maze if there is a continuous route without walls between the two. So, lets start with a maze in which each cell has all its 4 walls built. The goal is to get a maze in which there is exactly 1 way to get from any cell X to any cell Y. Now lets add the data structure into the image. We start with a Disjoint-set that has a group for each of the cells. Each turn we destroy a wall between 2 cells that belong to different groups. This way we open exactly 1 passage between each of the cells in one group to each in the other. We know we've finished when there is exactly one group in the set.

For those who like algorithms, this is actually an implementation of the Kruskal algorithm for finding Minimal Spanning Trees in graphs (if you take the grid cells as vertices and the walls as edges).
You can read more here: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
or you can look at some boos here: Books on Algorithms on Amazon

Lets look at some code.
A simple implementation of the Disjoint-set:

 public class DisjointSet {  
      private int[] set;  
      private int[] sizes;  
      private int size;  
      public DisjointSet(int size) {  
           this.set = new int[size];  
           for (int i = 0; i < size; i++) {  this.set[i] = i;  }  
           this.sizes = new int[size];  
           for (int i = 0; i < size; i++) {  this.sizes[i] = 1; }  
           this.size = size;  
      }  
      public int find(int item) {
           int root = item;
           // find the root
           while (set[root] != root) {
                 root = set[root];
           }
           // now shorten the paths
           int curr = item;
           while (set[curr] != root) {
                 set[curr] = root;
           }
           return root;
      }
      public int join(int item1, int item2) {  
           int group1 = find(item1);  
           int group2 = find(item2);  
           --size;  
           if (sizes[group1] > sizes[group2]) {  
                set[group2] = group1;  
                sizes[group1] += sizes[group2];  
                return group1;  
           } else {  
                set[group1] = group2;  
                sizes[group2] += sizes[group1];                 
                return group2;  
           }  
      }  
 }  

Now, lets build the maze:

 Maze createRandomMaze(int rows, int columns) {  
           Maze maze = new Maze(rows, columns);  
           // create all walls  
           List<Wall> walls = maze.getAllInnerWalls();  
           // remove all the walls you can  
           DisjointSet diset = new DisjointSet(rows*columns);  
           while (diset.size() > 1) {  
                int wallIndex = random.nextInt(walls.size());  
                int cell1 = walls.get(wallIndex).cell1;  
                int cell2 = walls.get(wallIndex).cell2;  
                if (diset.find(cell1) != diset.find(cell2)) {  
                     // we can remove the wall  
                     maze.removeWall(walls.get(wallIndex));  
                     diset.join(cell1, cell2);  
                }  
                walls.remove(wallIndex);  
           }  
           return maze;  
      }  

And here is the result:




















For the full code and much much more, visit my open-source project at: https://code.google.com/p/ai4u/
The code in this post is located at:
Disjoint-Set: https://code.google.com/p/ai4u/source/browse/com.ai4u.util/trunk/src/com/ai4u/util/disjointSet/ArrayDisjointSet.java
Maze: https://code.google.com/p/ai4u/source/browse/com.ai4u.util/trunk/src/com/ai4u/util/games/maze/Maze.java

Well, this is it for my first post.
Please, send me any ideas, questions or comments to My Email

4 comments:

  1. That maze looks good. I am always trying to think up ways to draw mazes for games. I want to figure out the algorithm for myself. But it looks like good algorightms are out there.

    ReplyDelete
  2. Thanks for the excellent code. Will be keeping an eye on your blog!

    ReplyDelete
  3. Great idea. Keeping the sizes of each group seems unnecessary, though.

    ReplyDelete
  4. Ankur, you can see that when joining 2 groups, I join the small one into the bigger one.
    This is important for the complexity of the data structure. If you don't do this, you might get a spaghetti structure where each node points to the next and then find will be O(n).

    When joining the smaller into the bigger group, the find will be divided by 2 each time, and this will give you complexity of O(Log*n) which is practically O(1).

    ReplyDelete