Making Challenging Mazes

Exploring solution length

There are lots of ways to make a maze more challenging, but many of them are highly subjective and difficult to quantify. One of the considerations to keep in mind while designing challenging mazes is the solution length. Let us see how Dijkstra’s algorithm again manages to make it successful.

In general, the longer the path, the more difficult the maze. Ideally, then, if we want a more challenging maze, we want to identify the longest path through it. We then put the entrance of our maze at one end of the path and drop the goal at the other end, and we’ve raised the difficulty level. Easy as that.

A general solution to the longest path problem—one that works for any arbitrary graph or grid—is what mathematicians call an NP-hard problem. Fortunately, we can narrow our requirements a bit. If we’re only looking to find the longest path through a perfect maze, there happen to be a few different ways to tackle it, and Dijkstra’s is one of them.

It might seem counterintuitive that an algorithm we just used to find a shortest path can also be used to find a longest path, but remember: Dijkstra’s has conveniently labeled each cell with a distance value. All we have to do is look for the largest one in the maze. That will tell us the longest path from our starting point to that cell.

We have to be careful, though. This is not necessarily going to be the longest path in the maze. If our starting cell happens to be somewhere in the middle of the actual longest path, then the longest path from that cell will be shorter than the real one. The trick is to run the algorithm twice. The first time, we find the most distant cell from some arbitrary starting point. The second time, we turn it around and use that most distant cell as the starting point, letting Dijkstra’s tell us the most distant cell from there. We’re basically asking Dijkstra’s to tell us the most distant point relative to the most distant point.

To make this real, we need to introduce a new method to our Distances class, to tell us which cell is furthest from the root and just how far away it is. We'll add the max method to the Distances class in the distances.rb file, just after the path_to method. The updated code for the Distances class is given below with the max method highlighted.

The updated Distances class