Programming theory: Solve a maze

Question

You can think of your maze as a tree.

     A
    / \
   /   \
  B     C
 / \   / \
D   E F   G
   / \     \
  H   I     J
 / \
L   M
   / \
  **  O

(which could possibly represent)

        START
        +   +---+---+
        | A   C   G |
    +---+   +   +   +
    | D   B | F | J |
+---+---+   +---+---+
| L   H   E   I |
+---+   +---+---+
    | M   O |
    +   +---+
    FINISH

(ignoring left-right ordering on the tree)

Where each node is a junction of paths. D, I, J, L and O are dead ends, and ** is the goal. Of course, in your actual tree, each node has a possibility of having as many as three children.

Your goal is now simply finding what nodes to traverse to to find the finish. Any ol' tree search algorithm will do.

Looking at the tree, it's pretty easy to see your correct solution by simply "tracing up" from the ** at the deepest part of the tree:

A B E H M **

Note that this approach becomes only slightly more complicated when you have "loops" in your maze (i.e., when it is possible, without backtracing, you re-enter a passage you've already traversed through). Check the comments for one nice solution.

Now, let's look at your first solution you mentioned, applied to this tree.

Your first solution is basically a Depth-First Search, which really isn't that bad. It's actually a pretty good recursive search. Basically, it says, "Always take the rightmost approach first. If nothing is there, backtrack until the first place you can go straight or left, and then repeat.

A depth-first search will search the above tree in this order:

A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J

Note that you can stop as soon as you find the **.

However, when you actually code a depth-first search, using recursive programming makes makes everything much easier. Even iterative methods work too, and you never have to explicitly program how to backtrack. Check out the linked article for implementations.

Another way of searching a tree is the Breadth-First solution, which searches through trees by depth. It'd search through the above tree in this order:

A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O

Note that, due to the nature of a maze, breadth-first has a much higher average amount of nodes it checks. Breadth-first is easily implementing by having a queue of paths to search, and each iteration popping a path out of a queue, "exploding it" by getting all of the paths that it can turn into after one step, and putting those new paths at the end of the queue. There are no explicit "next level" commands to code, and those were just there to aid in understanding.

In fact, there is a whole expansive list of ways to search a tree. I've just mentioned the two simplest, most straightforward way.

If your maze is very, very long and deep, and has loops and crazies, and is complicated, I suggest the A* algorithm, which is the industry standard pathfinding algorithm which combines a Breadth-First search with heuristics...sort of like an "intelligent breadth-first search".

It basically works like this:

1. Put one path in a queue (the path where you only walk one step straight into the maze). A path has a "weight" given by its current length + its straight-line distance from the end (which can be calculated mathematically)
2. Pop the path with the lowest weight from the queue.
3. "Explode" the path into every path that it could be after one step. (i.e., if your path is Right Left Left Right, then your exploded paths are R L L R R and R L L R L, not including illegal ones that go through walls)
4. If one of these paths has the goal, then Victory! Otherwise:
5. Calculate the weights of the exploded paths, and put all of them back into the queue (not including the original path)
6. Sort the queue by weight, lowest first. Then repeat from Step #2

And that's A*, which I present specially highlighted because it is more or less the industry standard pathfinding algorithm for all applications of pathfinding, including moving from one edge of the map to another while avoiding off-road paths or mountains, etc. It works so well because it uses a shortest possible distance heuristic, which gives it its "intelligence". A* is so versatile because, given any problem, if you have a shortest possible distance heuristic available (ours is easy -- the straight line), you can apply it.

BUT it is of great value to note that A* is not your only option.

In fact, the wikipedia category of tree traversal algorithms lists 97 alone! (the best will still be on this page linked earlier)

Sorry for the length =P (I tend to ramble)

Lots of maze-solving algorithms exist:

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm#solve

For a robot, Tremaux's algorithm looks promising.

An interesting approach, at least I found it interesting, is to use cellular automata. In short a "space" cell surrounded by 3 "wall" cells turns into a "wall" cell. At the end the only space cells left are the ones on route to the exit.

If you look at the tree Justin put in his answer then you can see that leaf nodes have 3 walls. Prune the tree until you have a path.

This is one of my favorite algorithms ever....

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

How about building a graph out of your Matrix and using Breadth First Search, Depth First Search or Dijkstras Algorithm?