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.
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 notebook accompanying this blog.
Let’s check the picture. We have the maze, with all the reachable points colored in some way by distance.
So now we can compute our retraction of paths, taking snapshots every so often. We’ll then show it all in an animation.
Note: For the maze image at the beginning, I used Bing Maps to get the aerial photo (data created by Intermap, NAVTEQ, and Getmapping).
"
No comments:
Post a Comment