Finding the Shortest Path

Shortest path in our maze

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 now. We’ll implement more or less what we described previously, walking the path backward from our goal, and 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.

Let's make the Distance class more useful. In the distances.rb class, we'll add the path_to(goal) method at the end of the definition of the Distances class, just before that class’s final end keyword.