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
by RS  admin@robinsnyder.com : 1024 x 640


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
Here are links to a series on recursive maze generation and visualization (more coming) This recursive method is simple but also creates somewhat simple mazes since there tend to be long corridors that can be quickly visually inspected. Such mazes can be used for small children as a series of more complicated mazes can be created. Once a child has learned one, they can move to the next.

3. The maze
Maze 15Here 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
Maze 0To 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
Maze 1From 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
Maze 2This 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
Maze 3The divide and conquer subdivision process continues.

10. Step case 4
Maze 4The divide and conquer subdivision process continues.

11. Step case 5
Maze 5The 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
Maze 6The divide and conquer subdivision process continues.

13. Step case 7
Maze 7The divide and conquer subdivision process continues.

14. Step case 8
Maze 8The divide and conquer subdivision process continues.

15. Step case 9
Maze 9The divide and conquer subdivision process continues.

16. Step case 10
Maze 10The divide and conquer subdivision process continues.

17. Step case 11
Maze 11The divide and conquer subdivision process continues.

18. Step case 12
Maze 12The divide and conquer subdivision process continues.

19. Step case 13
Maze 13The 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.

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

by RS  admin@robinsnyder.com : 1024 x 640