Mazes for Programmers

Finding the Shortest Path

The whole point of this exercise is to help us find a solution to our maze, a path between any two arbitrary points, so let’s tackle that next. We’ll implement more or less what was described previously, walking the path backward from our goal, looking for neighboring cells with sequentially smaller distances.

We first decide where we want our path to end (let’s make it the southwest corner), and work backward from there. For each cell along the path, the neighboring cell with the lowest distance will be the next step of the solution.

Remember how I said we’d be making the Distances class more useful soon? Here we go. We’ll plug the following method into it. Open distances.rb and add this method at the end of the definition ...