How to traverse a maze programatically when you've hit a dead end.

Question

Moving through the maze forward is pretty easy, but I can't seem to figure out how to back up through the maze to try a new route once you hit a dead end without going back too far?

Answer 1

Use backtracking by keeping a stack of previous direction decisions.

Answer 2

The simplest (to implement) algorithm would be to just keep a stack of locations you've been at, and the route you took from each, unless backtracking gives you that information.

To go back, just pop off old locations from the stack and check for more exits from that location until you find an old location with an untested exit.

By consistently testing the exits in the same order each time, if you know that backtracking to a location comes from down (ie. last time you were at the old location you went down), then you simply pick the next direction after down.

I am not entirely sure what you mean by going back too far though, I would assume you would want to go back to the previous place you have untested routes, is that not what you want?

Note that unless you try to keep track of the path from the starting point to your current location, and avoiding those squares when you try to find new routes, you might end up going in circle, which would eventually make the stack too large.

A simple recursive method which marks the path it takes and never enters areas that are marked can easily do this.

Also, if your thing that moves through the maze is slightly smarter than just being able to move, and hit (stop at) walls, in that it can see from its current point in all directions, I have other algorithms that might help.

Answer 3

Eric Lippert did a series of articles on creating a C# implemention of A*, which might be more efficient.