## The Battle of the Marlborough Maze at Blenheim Palace Continues

December 21, 2010 — Jon McLoone, International Business & Strategic Development

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

## 5 Comments

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

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

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.

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

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!