When we solve a maze, many of the techniques we utilize are far beyond the capability of even an advanced robot. For example, we can take a look and try out possible pathways without having to start physically or virtually moving through the maze. But what if we have no view to utilize, where all we see is the part of the maze we are currently in? In this case, a robot would have an advantage: It would be able to store “digital breadcrumbs” that can be used to backtrack quickly to “rooms” that have untested pathway options. The correct pathway through the maze could be determined in milliseconds, as long as the data of the maze pathways is accessible to the algorithm. Quickly determining the correct pathway, before rendering, is also a good way to validate that the maze has a solution. The queue technique that we implemented in the Draw a Maze lesson is also useful in a maze solving algorithm.

Version Zero

Version Zero quickly validates that a maze has a solution. But it highlights every pathway that it explored on its way to finding the ending cell. We need to refine all of the explored pathways down to a single pathway that is the single solution to the maze.

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

Version Zero code:
https://github.com/clean-blue-dot/solve-a-maze

Version Zero code in a sandbox:
https://jsfiddle.net/clean_blue_dot/xuzer01w/2/

Version One

Pointless Tree

Version One builds a tree (“PointlessTree”) out of all the explored pathways, creating branches whenever a direction is explored. When the end cell is reached, Version One backtracks from the tip of the last branch until it reaches the trunk of the tree, where the start cell is located.

By traversing the tree from the end cell to the trunk (start cell), all dead-end pathways are automatically ignored, as they are sibling branches: Only the parent branches are traversed.

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

Far from Finished

Now that this draw-and-solve-mazes program is working, we might consider this project completed, and release it. But it has no interactive features that allow a user to do anything other than re-run the process with a browser reload button. Most AI implementations are released in this incomplete state, as the importance of releasing to the Consumer Products Market trumps any potential improvements.

If we were to change this project into something different (like a game or embedded software for a maze-builder-robot), the code would need to be altered; as it is over-verbose and hard to maintain. The maze-drawing and maze-solving algorithms are lumped together in the same code. There is a mixture of “functional” and “object-oriented” code. Most of the code is “unrolled” (which is a lie, as it was never “rolled” in the first place): There are repeating patterns that would be much easier to maintain if they were implemented as functions. Cryptic variable names and over-reliance on text comments makes the code hard to read or understand.

Most programmers follow these simple rules:

• Make it Work
• Make it Right
• Make it Fast

Make it Work

Despite being incomplete, this project contains great value in that it works. If every step we take in making something work is a mistake, the steps no longer count as mistakes: They become learning devices. They become part of the creative process. They become a method to achieve working from not-working.

When we are in the process of making something work, we do not waste our time trying to make it right. Our code should be ugly and unrolled. Our variable names cryptic and full of spelling and grammatical errors. Our compilers/interpreters should be reporting coding errors constantly. Our code should always be doing something unexpected. It needs to be broken until it works.

Make it Right

Now that our code is working, we should make it right by organizing it into structures, classes, functions, and self-documenting code. Any portions of our code that would be useful for other projects (such as the creation of a maze or the solving of a maze) should be separated out into code “libraries” that can be re-used as part of other projects.

Make it Fast

Once our code is right, we could translate it into another programming language or “port” it over to another platform. These lessons use JavaScript in order to be portable to all devices, but JavaScript is far from ideal as a programming language: Slow, interpreted, and dubious numeric processing (for example, in JavaScript, 1 + “1” = “11”). Ideally, I would create cross-platform C++ code based on this project, using pointers, templates, and optimized algorithms.