Draw a Maze - Robot School

Not just for mice anymore!

One way to design, program, and test robots: Teach them to solve a maze.

Before we can solve a maze, however, we need to design a tool that creates a single-solution maze.

The best way to create and solve a maze is in software. Even when a physical robot is tasked with solving a physical maze, the job can be accomplished with less energy and time, when it is done purely in software. This could be accomplished by analysis of an image of the maze. Or by analysis of the data that represents the maze pathways.

For this lesson, we will design and implement an algorithm that creates a single-solution maze. The pathway data is stored in a rectangular array of cells, and the image is drawn by rendering boxes representing the cells.

Version Zero

Not entirely unexpected: The algorithm draws an initial pathway, stopping as soon as it hits the first dead-end.

Proposed Redesign Approach

We need to add a feature that stores previous cells that have unused directions, so they can be revisited, and the other directions utilized.

Version Zero in action:
https://school.cleanbluedot.com//wp-content/uploads/mazing_js/version_zero.html

Version Zero code:
https://github.com/clean-blue-dot/draw-a-maze/blob/main/version_zero.html

Version One

Version One uses a queue. It enqueues cells that have unused directions still available. It also enqueues each new cell that is being added as a branch. The maze drawing loop runs until there are no more cells in the queue.

Predictable

Notice how predictable a Version One maze is. The solution is very easy to track on sight, especially if we start at the Southeast corner and find the pathway to the Northwest corner. There are no spiral patterns or any complex dead-ends. What we want out of a maze generator is unpredictability. The probability of available pathway directions in the North or West is so low that the random direction picker is almost always picking either South or East.

Proposed Redesign Approach

Version Zero, despite failing to draw complete mazes, produces unpredictable pathways. Version One, despite failing to draw unpredictable pathways, retains cells in an optimal way. We need to revert the pathway generator loop to Version Zero, but add a feature that revisits cells that have unused directions still available whenever a dead-end has been reached.

Version One in action:
https://school.cleanbluedot.com//wp-content/uploads/mazing_js/version_one.html

Version One code:
https://github.com/clean-blue-dot/draw-a-maze/blob/main/version_one.html

Version Two

Version Two only dequeues a backtrack cell when a dead end is reached. It also centers the maze within the window. The pathways are allowed to wander until a spiral or other structure leads to a dead end. The predictable starting point (Northwest corner) makes the North and West pathways look straight and easy.