Wolfram Blog
Daniel Lichtblau

Retreat from Blenheim

February 1, 2011 — Daniel Lichtblau, Scientific Information Group

When last seen in the whereabouts of the Marlborough Maze, I was slinking off stage left, having been upstaged by Jon McCloone and his mix of image processing and graph theory alchemy. In a comment on my post, Jaebum Jung showed similar methods.

Me, I only wanted to compute a bunch of distances from the entrance, then walk the maze. But I was not at that time able to show which was the shortest path, or even to prune off the dead ends. I’m over that lapse now. In this post I will provide brief Mathematica code to take the grid of maze pathway distances that I computed, and get the hopeless paths to melt away. Technically this is referred to as a retraction—not in the sense of an apology, but, rather, topology.

Marlborough Maze

Wuzzat mean? Well, it is a bit complicated. The idea is to provide a set of pictures (technically, a parametrized function) that has the “bad” maze pathways retreating into the shortest path. Topology purists will object, and rightfully so, that we are cutting the maze—that is, altering the topology. True enough. But it is correctly a retraction, provided we understand that where there are loops, we regard the maze as “sliced” so that the longer paths do not actually connect to the shorter ones.

Let’s start by explaining the methodology. We want to get rid of maze pathway points that are surrounded either by boundary or other pathway points of lesser distance from the entrance. This is because such points are either at the end of a dead end or at the end of a roundabout path that has just intersected with a more direct path (where distances are smaller). It is at these latter places that we think of the maze as having been sliced.

For purposes of efficiency, we arrange our pathway points in a list ordered by distance. We start with the furthest, see if it qualifies as removable (by checking its neighbors), and if so, we change it to “boundary” status. This allows us, in a sense, to “melt” our way from further to closer points, removing new bad ones as we go.

We first force the points near the exit to stay in place by adding an artificial first row that has exit neighbors with values that make the exit points not appear to be surrounded by boundary or closer points.

We start with distances as computed in my prior blog on this subject, modified so that all entries not reachable or out of bounds are simply regarded as “far”. This was for purposes of graphing but serves us for the computation below as well. As this distance matrix is large, we do not show it here. It is kept in a hidden cell (how unexpectedly Spanish Inquisition) in the Computable Document Format (CDF) file accompanying this blog.

Let’s check the picture. We have the maze, with all the reachable points colored in some way by distance.

Distance matrix

Input 2

Input 3

So now we can compute our retraction of paths, taking snapshots every so often. We’ll then show it all in an animation.

Input 4

Input 5

Input 6

Note: For the maze image at the beginning, I used Bing Maps to get the aerial photo (data created by Intermap, NAVTEQ, and Getmapping).

Download the CDF file

Posted in: Image Processing
Leave a Comment

7 Comments


Pedro

It’s Amazing…

Posted by Pedro    February 1, 2011 at 3:26 pm
Lucile Lichtblau

There once was a man in a maze, who got stuck there in fog and some haze. He melted a path, by using some math, and was out in a matter of days.

Posted by Lucile Lichtblau    February 1, 2011 at 5:53 pm
Daniel Lichtblau

Ma, this is Blenheim. In England. Not Ireland. They use sonnets in England. (This is so embarrassing.)

Posted by Daniel Lichtblau    February 1, 2011 at 6:19 pm
E Lichtblau

Yes, this is amazing.

Ok, so here’s sonnet for my love lost in his maze (not written by me)

In but one moment I could lose it all-
His voice, his comfort, his eyes and that hair!
That which I’ve memorized with every stare.
Every second counts as I do stall,
To inhale the air before I must fall.
The passions are deeper than I can bear,
Yet time will steal everything however fair.
And my heart will keep longing, his love it will call.
So why should one love, knowing of its end

Posted by E Lichtblau    February 1, 2011 at 7:56 pm
Savvas

So, this seems to me like a competition on who will write the best code between these two gentlemen!

I am looking forward to reading the next post on the subject :)

Posted by Savvas    February 2, 2011 at 7:51 am
Daniel Lichtblau

Woe is this blog. First
a limerick, and now there’s
a sonnet onnet.

Posted by Daniel Lichtblau    February 2, 2011 at 12:29 pm
Hans

I am waiting for either one of the posters to extrude (bevel) the 2D image of the maze into 3D object and place a fictitional 3D view point or camera and solve the maze from a ground level perspective. No prunning. Just use some common sense such as most mazes require a user to go to the left first; and other rules like that (i don’t recall the rules correctly). Having the whole picture and solving the path with math is fine. How about solving the maze with rules. Who(m) ever gets there first we can say: “You rule.”

Nevertheless, they are all excellent post.

Posted by Hans    February 2, 2011 at 2:17 pm


Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):