How do you solve a real-world maze?
May 14, 2006 10:40 AM Subscribe
Non-theoretical real-world maze solving?
You are placed at the entrance of a maze, which is on its edge. You know that the goal of the maze is somewhere in the middle, not at an edge. You also know that some parts of the maze are connected to other parts of the maze by bridges. You cannot see over the walls, but you can always tell which direction you are travelling.
What is the best (fastest/most efficient) way to solve such a maze, that does not involve marking a trail on the maze itself? Bonus points if the solution doesn't involve making a map.
Edge-following wouldn't seem to work here, as with the goal in the middle you could end up going in circles. The Pledge algorithm also seems to fail if the exit is not on the edge.
You are placed at the entrance of a maze, which is on its edge. You know that the goal of the maze is somewhere in the middle, not at an edge. You also know that some parts of the maze are connected to other parts of the maze by bridges. You cannot see over the walls, but you can always tell which direction you are travelling.
What is the best (fastest/most efficient) way to solve such a maze, that does not involve marking a trail on the maze itself? Bonus points if the solution doesn't involve making a map.
Edge-following wouldn't seem to work here, as with the goal in the middle you could end up going in circles. The Pledge algorithm also seems to fail if the exit is not on the edge.
Best answer: What I typically do when I'm in this situation every August is do an edge-following approach, but switch edges immediately upon entrance (hoping to be following an interior edge) and then every time I think I'm in a loop. The mazes I'm put in don't have bridges, but I don't know how much that matters.
posted by aubilenon at 10:58 AM on May 14, 2006
posted by aubilenon at 10:58 AM on May 14, 2006
I'm wondering what exactly counts as "marking a trail on the maze itself".
When I do corn mazes every summer, I generally do end up constructing a fairly rich representation of the maze in my memory. I don't actually mark anything on the trail physically, but I most certainly do mark off locations and previously-tried paths in memory... but that's not really an algorithm.
I think what you're saying is that you're looking for something that's a simple rule that doesn't require maintenance of state, right?
My head just exploded as I learned about hypermazes from aberrant's link.
posted by dmd at 11:15 AM on May 14, 2006
When I do corn mazes every summer, I generally do end up constructing a fairly rich representation of the maze in my memory. I don't actually mark anything on the trail physically, but I most certainly do mark off locations and previously-tried paths in memory... but that's not really an algorithm.
I think what you're saying is that you're looking for something that's a simple rule that doesn't require maintenance of state, right?
My head just exploded as I learned about hypermazes from aberrant's link.
posted by dmd at 11:15 AM on May 14, 2006
Response by poster: that doesn't require maintenance of state, right?
Maintenance of state is OK, but only for very small amounts of state.
posted by Mwongozi at 11:19 AM on May 14, 2006
Maintenance of state is OK, but only for very small amounts of state.
posted by Mwongozi at 11:19 AM on May 14, 2006
Hmm. The human-targeted algorithms referenced on aberrant's tend to involve marking your path.
posted by dmd at 11:21 AM on May 14, 2006
posted by dmd at 11:21 AM on May 14, 2006
The only algorithm that meets your requirements is Tremaux's Algorithm. According to my link above, it's human-doable, guaranteed to find a solution, and, while not memory-free, is fast.
posted by aberrant at 11:22 AM on May 14, 2006
posted by aberrant at 11:22 AM on May 14, 2006
(but it requires path marking, so I guess that's out.)
posted by aberrant at 11:23 AM on May 14, 2006
posted by aberrant at 11:23 AM on May 14, 2006
Response by poster: Tremaux's Algorithm requires you to leave a trail, however.
posted by Mwongozi at 11:23 AM on May 14, 2006
posted by Mwongozi at 11:23 AM on May 14, 2006
from my days going caving we had a lot of small tricks, but it's hard to boil it down into one algorithm. edge following is definitely a good one. remembering your direction by adding and subtracting turns. estimating position by counting steps (most of these only work for 2d mazes). sectioning off areas.
posted by destro at 6:36 PM on May 14, 2006
posted by destro at 6:36 PM on May 14, 2006
For fastest way, I beat the local time record of a maze with no real algorithm, just by getting lost as usual at a running/jogging pace instead of a walking pace. I.e. don't forget speed :-)
posted by -harlequin- at 12:31 AM on May 15, 2006
posted by -harlequin- at 12:31 AM on May 15, 2006
« Older Travel: what to do in Austria ? | Contact information for Venezuela press office in... Newer »
This thread is closed to new comments.
posted by aberrant at 10:47 AM on May 14, 2006