Send
Close Add comments:
(status displays here)
Got it! This site "robinsnyder.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Maze algorithm explanation using GIF images
1. Maze algorithm explanation using GIF images
This page looks at a recursive divide and conquer problem solving approach to generating a maze.
Since a number of visualization techniques are used, this page is also useful for creating certain types of visualizations as used, for example, in data science.
2. Recursive maze generation and visualization
3. The maze
Here is an example maze.
One is to enter at the upper left at the in-arrow and exit at the lower right at the out-arrow without crossing any lines.
4. The problem
How does one approach this problem of generating a maze such as this?
The way used here is a backward-chaining (from the goal) top-down (from the goal) recursive design and implementation.
5. Solving the maze
Note that to get through the maze, one tends to use a forward-chaining (from the start) bottom-up (from the start) method involving look-ahead and some trial and error. In this case, starting at the goal and working backwards is similar to starting at the starting point and working forwards.
6. Design start with base case
To get started in the design one can start with a empty grid that has only the outline and the enter and exit points.
This is the base case. In counting as a computer scientist, the base case is step 0.
Note that there is a clear solution from entry to exit points. This condition will be preserved at each step.
7. Step case 1
From the base case, a partition point is selected to divide the area with a line and a gap provided to insure a solution.
The method used here is to always divide the larger of the height or the width and to use a pre-determined gap length which divides the area into a integer number of rows and columns.
At this point, the divide and conquer problem solving strategy is invoked. Each of the two parts can now be independently divided using the same strategy as for this part. This is where recursion in programming becomes useful as the same code can process a rectangular area, stopping when no further subdivision can be done (i.e., when the height or width has reached the gap width).
8. Step case 2
This subdivision can now be done on both parts, resulting in the following.
At each step, if the previous step had a solution, and a dividing line is added with a gap, a solution is preserved.
In the design explanation, parts of the maze will be shaded where on each division, the largest part will retain the original shade and a new shade used.
9. Step case 3
The divide and conquer subdivision process continues.
10. Step case 4
The divide and conquer subdivision process continues.
11. Step case 5
The divide and conquer subdivision process continues.
At this point, enough colors have been used and no further subdivision shading is used.
12. Step case 6
The divide and conquer subdivision process continues.
13. Step case 7
The divide and conquer subdivision process continues.
14. Step case 8
The divide and conquer subdivision process continues.
15. Step case 9
The divide and conquer subdivision process continues.
16. Step case 10
The divide and conquer subdivision process continues.
17. Step case 11
The divide and conquer subdivision process continues.
18. Step case 12
The divide and conquer subdivision process continues.
19. Step case 13
The divide and conquer subdivision process continues.
At this point, no more subdivisions are needed so the algorithm (for this instance) terminates.
20. Algorithm pesudo-code
Here is a pseudo-code for the maze generation algorithm as described to make a maze of rows and columns.
Main:
Start with an empty canvas.
Outline the maze limits with an entry and exit point on opposite sides.
Call MazeGenerate with the rows and columns to be filled in.
MazeGenerate:
If the rows and columns requested are both greater than 1 Then
If the height is greater than the width Then
Divide the grid into top and bottom parts.
Draw a (horizontal) line between the parts, leaving a gap to pass through.
Call MazeGenerate on the top part
Call MazeGenerate on the bottom part
Else
Divide the grid into left and right parts.
Draw a (vertical) line between the parts, leaving a gap to pass through.
Call MazeGenerate on the left part
Call MazeGenerate on the right part
End If
End If
The actual code fills in details that are not needed at the higher level of the algorithm description. For example, the side and gap lengths, and exact x and y coordinates are omitted. As another example, the division into parts can be done using pseudo-random numbers, but that is omitted from the algorithm.
For more information, see the following:
Maze algorithm explanation using GIF images (this page)
21. Dynamic display
A dynamic display of the maze development can be done with an animated
GIF (Graphics Interchange Format) or using JavaScript. A border is used on the image so one can see the white space that is in the image itself.
22. HTML
Here is the HTML for the above image, buttons, etc.
23. JavaScript
Here is the JavaScript to connect the HTML to the IMG change.
24. Animation
JavaScript can be used to animate the display of the grid. Note the use of id status2 instead of status1 and maze2 instead of maze1 in order to keep the previous example from conflicting with the current example.
The statusSet1 routine is re-used since the id is passed to the routine.
The mazeMax1 variable does not change, but mazePos2 is used instead of mazePos1 for the same reason.
25. Maze demo
Here is a animation demo of a top-down maze generation process.
26. HTML
Here is the HTML for the above image, buttons, etc.
27. JavaScript
Here is the JavaScript to connect the HTML to the IMG change.
28. Implementation description issues
An issue that arises in creating the above sequence is that for each step, the number of total subdivisions changes. So one cannot just use a pseudo-random number generator is each step would involve a different sequence. There are many ways around this problem. In the past, the ways I have used include the following.
Run the complete algorithm on the complete maze every time, but only display to a certain level.
Determine all of the possible nodes in the binary tree and assign a random number to each node and use it during the generation process. Since this maze took 13 steps, there are 213-1 = 8192 nodes in the tree, most of which are not used. In this case, I use a lazy node assignment to the random numbers as needed.
29. Left as an exercise
The rectangular maze used here is fairly simple. To extend to a circular maze, instead of rows and columns one has a radius and angle with the gap changing as the radius changes. As an exercise, extend the ideas presented here to a circular maze.
30. End of page
