How do you solve a real-world maze?

May 14, 2006 10:40 AM

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.

posted by Mwongozi to grab bag (10 comments total)

lots of maze (generating and solving) algorithms here.
posted by aberrant at 10:47 AM on May 14, 2006

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

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

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

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

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

(but it requires path marking, so I guess that's out.)
posted by aberrant at 11:23 AM on May 14, 2006

Tremaux's Algorithm requires you to leave a trail, however.
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

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