Regular readers of the Wolfram Blog will have seen that the item that I wrote on solving mazes using morphological image processing was thoroughly beaten by the much smarter and better read, Daniel Lichtblau from our Scientific Information Group in his post “Navigating the Blenheim Maze”.
Always up for a challenge (and feeling a little guilty about the rather hacky and lazy way I tried to deal with loops and multiple paths the first time), I am back for another go.
My first approach with any new problem is to think about the nearest available Mathematica command. In the new Mathematica 8 features is a graph theory command FindShortestPath. That certainly sounds promising.
Mixing image processing and graph theory may sound complicated, but one of the central strengths of Mathematica‘s integrated all-in-one design is that different functionality works together, and in this case it proves to be quite easy.
I’ll start the same way that I did the first time, using Peter Overmann’s method for reducing the maze to single pixel lines and throwing away dead ends (read the original post for an explanation of the code).
Now I will crop it, for the sole purpose of cutting the join between the entrance and the exit of the maze. Otherwise the shortest route will be not to enter the maze at all.
Now I get the coordinates of every white pixel. Each of these will be nodes in the graph that we must traverse.
While we are here, let’s find the start and end coordinates, which are the white pixels in the bottom (350th) row.
The next step is to make a function to find which of the eight neighbors of a point are white. We will need this to establish which of the graph nodes are connected.
Then we turn those into undirected edges in a graph.
For example, the start has just one neighbor, point {349,247}.
Now we just apply that function to all the points in the maze and de-duplicate to get a full graph description of the maze. The image below is a topological version of the maze, but each point’s name holds its coordinates in the original image.
In order to shorten the blog post, I have made one big approximation. I have not weighted the edges. Connections diagonally should really be weighted to be √ 2
times longer than horizontal or vertical neighbors. The Mathematica 8 graph capabilities support this, but it turns out not to matter here.
Now that we have a Graph object for the paths, we can solve it with the FindShortestPath function.
We then go back from this solution graph to an image. It’s pretty easy; just take all the nodes in the solution and use their names as the coordinate of non-zero elements in a sparse array and wrap Image around it.
Now I can’t claim victory over Dan, because the two solutions have different benefits. My approach is aided greatly by the assumption that we can thin the paths down so that the maze graph has only 5,132 nodes. I suspect that it becomes less efficient when you have mazes with large open areas where you care about not just which path you go down, but how you traverse the open areas.
However, my solution does have one big advantage. It is quite amenable to manual adjustment. As I explained in the original blog, there are bridges on either side of the main circle. So the solution above assumes that we can climb and rappel those. With a couple of manual corrections I can change the graph to represent the 3D nature of the Blenheim maze.
With some delicate use of the Get Coordinates tool, I find four key pixels that, once removed, will break the connection between the paths over the bridge and the ones under. I then construct two special edges that join up the broken paths on either side of the bridge.
And here is the new maze graph.
And now repeat what we did before for the true shortest solution to the maze respecting the bridges.
I expect there are other ways to solve this problem in Mathematica. That’s one of its strengths. If you have one of them, send it in, and perhaps we can turn this into the Marlborough Maze Solving Blog!
Note: For the maze image, I used Bing Maps to get the aerial photo (data created by Intermap, NAVTEQ, and Getmapping plc).