Wolfram Computation Meets Knowledge

The Battle of the Marlborough Maze at Blenheim Palace Continues

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).

Reducing the maze to single pixel lines and throwing away dead ends
Reducing the maze to single pixel lines and throwing away dead ends

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.

Cropping the image

Now I get the coordinates of every white pixel. Each of these will be nodes in the graph that we must traverse.

Getting the coordinates of every white pixel

While we are here, let’s find the start and end coordinates, which are the white pixels in the bottom (350th) row.

Finding the start and end coordinates

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.

Finding which of the eight neighbors of a point are white

Then we turn those into undirected edges in a graph.

Turning those into undirected edges in a graph

For example, the start has just one neighbor, point {349,247}.

The start point's neighbor

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.

 A topological version of the maze

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.

Using 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.

Going back from this solution graph to an image

Going back from this solution graph to an image

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.

Recreating the bridges

And here is the new maze graph.

The new maze graph

And now repeat what we did before for the true shortest solution to the maze respecting the bridges.

The true shortest path in the maze

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).

Download notebook

Comments

Join the discussion

!Please enter your comment (at least 5 characters).

!Please enter your name.

!Please enter a valid email address.

7 comments

  1. You seem to be a great programmer although those functions make it easier for others, too. ;-) In the previous maze article, it really looked like a part of the story was missing – great that it can be completed.

    I also liked the not-quite-subtle preference for friendly Bing Maps. :-)

    Reply
  2. I follow with the greatest interest that discussions on image processing. I found recently a puzzling limitation in Texture. Transforming an image into a texture using a statement such as
    Graphics@{Texture[ImageData@image],
    Polygon[{{0, 0}, {1, 0}, {1, k}, {0, k}},
    VertexTextureCoordinates ->
    Reverse@{{0, 0}, {1, 0}, {1, 1}, {0, 1}}]}
    works only if “image” has at the most 2048 rows and 2048 columns. I noticed that 2048 was 2^11 … but that did not help me! My question to the experts is thus: why such a limitation? and, if it is basic, how to compress an image to the format accepted by Texture?
    Bruno

    Reply
  3. Wow, great post.
    Going through Mathematica documentation I found the MorphologicalGraph function and I was able to quickly reproduce your results – it does not produce such as nice and detailed path as your post but seems fast enough, since it “straightens up” the path.

    Reply
  4. Nice demonstration!

    We visited this maze last weekend and took a picture of the design as shown at the entrance of the maze. As it turns out, the picture makes it look as though the maze has no solution. (It indicates one additional hedge where in reality there is none.) So, it was a good strategy to start from an aerial photo! My post about it, with the picture, is here: http://www.sylviawenmackers.be/blog/2011/11/over-fractals-engelse-gothiek-en-een-dwaaltuin/ (in Dutch).

    Reply
  5. I had noticed the error on the entrance map, but it doesn’t prevent any solution. The eroneous hedge blocks the solution that I calculated to be optimal, but there is a fundamentally different solution that goes around the outside top left end then goes under the bridge.

    As well as being shorter going over the bridge is much more fun!

    Reply
    • Up until know i have been falsely calling the second bridge the “bridge of doom” and if you got onto it you had gone wrong! Turns out its the fastest path…

      Current maze race record is 4min 20 seconds with my 7 year old daughter, this weekend we gonna roll with this new path and see if we can remember it.

      The benefit of the “around the outside top left” solutions is its easy for her to remember.. .:D

      Reply