I read Jon McLoone’s recent “aMazeing Image Processing in Mathematica” post with some interest.

It showed how to import an image of a maze, and then use image processing functions in Mathematica (some new to Version 8) to draw paths through the maze. What fun! I then observed, to my dismay, that there was no way to determine a “good” path. Frankly, I was disappointed.

I decided that there must be ways to do this in Mathematica. One approach would involve forming a graph. We would have vertices at points where the maze path forks, and we would make weighted edges from approximated distances between these vertices. New functionality in Mathematica supports these graph methods. Unfortunately I am not yet familiar with it.

Next I thought there might be a way to emulate an accretion of distances via cellular automata. There are people at Wolfram Research who program with cellular automata on a regular basis. But I’m not one of them. (Indeed, while it would seem an odd pursuit, I gather there are people here who even study them. Apparently this must be done late at night, presumably when the automata are dormant.)

So I decided to use some old code I’d prepared for a talk back in 2003. It is based on work by James Sethian and others, and is well described in Sethian’s book Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science (Cambridge University Press, 1996).

The idea is to track what is called a “moving front”. In our case the front will consist of those points on the path we’ve not yet traversed that abut points we’ve just hit (that is to say, neighbors of those points that were last on the “front”). We traverse in order, based on the distance from where we began. In a sense we are oozing through the maze. Well, we are not ourselves oozing, but it seems a reasonable metaphor. The “tracking” will simply keep note of how far a point is from where we began. Naturally we’ll begin at the opening of the maze.

I’ll just crib some of Jon’s code and the aerial photo (data created by Intermap, NAVTEQ, and Getmapping plc) he got from Bing Maps for the next steps.

For the task at hand I prefer to reverse zeros and ones. I’ll then make the ones into a large value. This will be used later to demarcate maze boundaries, so we do not cheat and cross over hedges.

Here is a picture of the maze. The white parts are the open spaces.

I want to clip away the outer regions, so as to obtain just the maze. I’ll especially want to trim the last rows (shown at the bottom of the picture), so that we’ll have a distinct entrance and exit (the entrance will be the path part right near the center, which leads to the wheel-with-spokes region).

Here is where things (briefly) get technical. We want to have a “start” region with values of -1. We then move forward into spaces of zeros and mark them as occupied until we’ve permeated all the pathways that are reachable from the start. First I explicitly tack on a row that is impassable on two sides, with a slim region containing our start: think of it as a doormat leading into a big forest.

We’ll run this to get our set of pathway distances.

Let’s see how this looks graphically.

Of course we immediately observe that this picture gives no hint as to how to actually traverse the maze. At junctures it is not clear which way to turn, and there is nothing to stop us from traveling to a dead end. I first thought maybe I could modify this fast marching method so that we might discover when we hit dead ends or junctures reached by shorter traversals, and then wend our way backward. But I decided this was too hard. The notion that “I’ve no idea what I’m doing, and I don’t even understand my old code” crossed my mind. At this point I’ll remove a few expletives, and just observe that, frankly, I was disappointed.

The next idea was to sneak in through the exit. After all, we can just as well ooze from there to the entrance. OK, but why do that? I wasn’t so sure myself; the Big Idea was on a slow route to my office that day.

For this computation we simply use a new last row. This time we move the starting region for our flow to the base of the exit.

We’ll take a peek.

No surprises. Now we overlay these, and things start to look better.

We see quite clearly the path we want. The slight shimmer is just luck of the color function; I’m not particularly adept with graphics.

So here is the point. When we overlay these, we are in effect summing distances from entrance and exit to each pathway point. On the best path the sum will be approximately constant and equal to the length of that path (approximate because we use numerical approximations throughout the tracking code). Elsewhere the sum will be larger.

The reader might wonder whether the author just pulled a rabbit out of his hat, knowing all along this would work. In actual fact I was not at all certain, and it was one of those ideas that happened to succeed. Had it not, then I’d have buried it. I do that often. (Sometimes I forget why the idea was so wretched, and exhume it later. I may have missed a career in politics.)

To extract just that path, we’ll find its value and then only take points with distance sums close to that value.

Finally we overlay the shortest path on the maze.

For the morbidly curious, the code (in the download notebook below) we used for the distance tracking weighs in at approximately 160 lines. I thank Wolfram Research colleagues Joel Klein, Rob Knapp, and Michael Trott for helping me with some of the finer points of the Mathematica 8 Compile functionality.

I think I now understand the early medieval injunction (Babylonian, circa 530 CE): “Ye pour ooze in two byways, before cruising through thy maze.”

Download notebook