Algorithm to get through a maze
- by Sam
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!!
