The algorithm for the maze generator is based on Set Theory.During the maze creation time, the connected cells must belong to the same set (connected cells are the ones that there is a path from one to another). Each time we pick up two adjacent sets, and break down one wel between them, and merge them together. Iterate on this till there is only one set left.
The issue to be addressed here is how do we pick up adjacent sets, and which wall should we break down, as well as how to merge two sets efficiently. Further more, we need to optimize the use of memory space since it's easily to get an OutOfMemory error. Steps are:
- Initial step: assign each cell a unique set id, and put all cells into the adjacency list;
- randomly pick a cell, X, from adjacency list, and randomly break down a wall to the other cell belonging to different set
- merge two sets;
- remove cells that no longer adjacent to other sets
- go back to step 2 till the adjacency list is empty
- output the result maze.
One decision needs to be made if implement it by Java, that is whether use List or Set for adjacency list. List allows us to randomly pick an item with less effort in step 2; but it costs too much when we want to seek and remove an item in step 4. On the contrary, Set can't help us when randomly picking items, but it guarantees efficiency for deleting items. The trick here is to cast the Set into array, and then pick one randomly.
Interested in competing with my program? wanna build a faster one? Go ahead and have a try! Before that, take a look on this *world most complicted maze* I made :)
Here is a list of test results, tested on P4 centrino 1.6G, 512M windows laptop:
| Size |
Generating Time |
| 10 X 10 |
0.02 sec |
| 20 X 20 |
0.03 sec |
| 30 X 30 |
0.07 sec |
| 40 X 40 |
0.151 sec |
| 50 X 50 |
0.37 sec |
| 60 X 60 |
0.781 sec |
| 70 X 70 |
1.462 sec |
| 80 X 80 |
2.654 sec |
| 90 X 90 |
4.757 sec |
| 100 X 100 |
7.09 sec |
| 110 X 110 |
10.345 sec |
| 120 X 120 |
13.62 sec |
| 130 X 130 |
19.779 sec |
| 140 X 140 |
31.245 sec |
| 150 X 150 |
40.298 sec |
| 160 X 160 |
54.018 sec |
| 170 X 170 |
83.4 sec |
| 180 X 180 |
108.797 sec |
| 190 X 190 |
141.293 sec |
| 200 X 200 |
165.068 sec |
|
For the solver (or maze walker), the algorithm here is not a random one. The key here is that, I'll record each step (walk) on each cell it arrives at. and when I want to leave a cell, first check its accessable neighbours and pick one with the smallest step number. that one either can be never accessed before if step number equals 0, or the oldest one that has been accessed.
The algorithm guarantees that:
- we can always reach the end from the beginning, without fall into any infinite local trap;
- there are at most 4 times for a cell being visited.
- for equivelant choice, it in always in favor of moving right then down, and then up and left.
Don't be confused by the speed of the Applet above. The walker walks pretty fast (usually within a small fraction of second). The reason why the Applet looks slow is that I force the thread to take a short nap for each walk to allow UI to display current progress.
The efficiency of this algorithm can be reflected from the ratio of repeated walk over total number of walks made. The score is usually among 35% through 50%.
If you find a better algorithm that runs even faster, and/or gives even better results, pleas drop me an emal: jerric@uga.edu :) |
Maze Generator & Solver 
