Algorithm to get through a maze

Question

Hello, We are currently programming a game (its a pretty unknown language: modula 2), And the problem we encountered is the following: we have a maze (not a perfect maze) in a 17 x 12 grid. The computer has to generate a way from the starting point (9, 12) to the end point (9, 1). I found some algorithms but they dont work when the robot has to go back:

xxxxx
    x
=>  x
    x
  xxx

or:

    xxxxx
        x
xxxxxx  x
     x  x
     x  x
xxxxxx  x
=>      x
xxxxxxxxx

I found a solution for the first example type but then the second type couldn't be solved and the solution I made up for the second type would cause the robot to get stuck in the first type of situation.

It's a lot of code so i'll give the idea:

WHILE (end destination not reached) DO { try to go right, if nothing blocks you: go right if you encounter a block, try up until you can go right, if you cant go up anymore try going down until you can go right, (starting from the place you first were blocked), if you cant go down anymore, try one step left and fill the spaces you tested with blocks. }

This works for the first type of problem ... not for the second one. Now it could be that i started wrong so i am open for better algorithms or solutions specificaly to how i could improve my algorithm.

Thanks a lot!!

Answer 1

I think I recall your algorithm only working when you enter the maze through an entrance, hug a wall, and try to go out. For example, if you start at an "island" in the middle of the maze, it will not work.

Take a look into Breadth-first search. This will also give you the shortest path to any cell you want to go. Basically the idea is that you don't want to visit the same cell twice (there's no reason to) so from each cell you branch out.

For your first example. You can probably recognize the pattern, with the numbers being the number of steps it takes to get to each cell starting from the arrow.

xxxxx
3212x
2101x
3212x
43xxx

You can, of course, reconstruct the path taken if you like, by keeping track, for each cell, of the best previous path taken to this cell.

Breadth-first search works assuming that the distance between each grid cell is a constant one. If the distance between adjacent cell varies, you might take a look at this class of problems: Shortest path problem.

Answer 2

You will probably need to implement a path finding algorithm cause you not only want to find any way, you also want to find the shortest way possible. The most popular path finding algorithms are the Dijkstra and the A*. If you know the layout of your whole maze it will give you the shortest possible path from one point to another.

Answer 3

The problem you are trying to solve is called pathfinding. There are lots of methods, from simple brute force to the amazing A*. Wikipedia has a very good overview here.

Answer 4

You're thinking of the problem as a character going through the maze. I wouldn't do that. I would imagine the maze as a series of tunnels with water flowing through them (meaning that the answer would flow in all directions). So if you were to represent the maze as a 2 space array of strings, with null (or some other char as a wall), a different delimiter as places that haven't been discovered (say 'o'), and the rest as the shortest path to get to that square (using 'n', 'e', 's', and 'w'). Then, iterate through a loop, each time, each square will look to see if it can spread out to another square (if the square has a 'o' in it), then, it will add a concatenated version of the string that square has to the next square, with the char representing the move it took to get there. When you find the end square, you're done.