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
Trees cover up a multitude of sins.
Bob Ross
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.
Talk to the tree, make friends with it.
Bob Ross
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.
There’s nothing wrong with having a tree as a friend.
Bob Ross
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.