# Thread: Algorithm to walk through a maze.

1. ## Algorithm to walk through a maze.

HI,

MY problem is to write a recursive function to walk through a maze. There is an algorithm. It's that you start at the right wall and walk forward and keep following the wall. You are guaranteed to find the exit and if there's none you'll come back to the starting point. But i really don't know where to start. The function should receive as arguments a 12-by-12 double-subscripted array representing the maze and the starting location. As it walks through the maze it replaces the path with the character 'X'. The function should display the maze after each move so the use can watch as the maze is solved. I need some help since i really don't know where to start. How to determine its path. Pls direct. Here is a sample maze:

Code:
```############
#   #      #
# # #### #
### #    # #
#    ### #
#### # # # #
#  # # # # #
## # # # # #
#        # #
###### ### #
#      #   #
############```
i know it looks a bit strange but i guess you'll figure it out. Thnx in advance!

2. Pls anyone pls reply and give a hand

thnx

3. In psedocode.....

functolookforexit( what square)
{
if (exit found) do fireworks()
else
functolookforexit(next square)
}

4. how do i code so that it sticks to the right wall? And how do i make it turn corners ? thnx

5. Code:
```BFS:

if( direction_next_to_me( me ) != used )
{
move_direction( pick_direction( unused_directions ) );
}
else
backrack( );
}```
There are tons of matches on maze / path finding.

Quzah.

6. Okay, here's basically how to do the maze with the hand on the right wall. You'll need to keep track of the direction the mazee is facing, as well as, obviously, his x and y coordinates.

Let's assume you're facing a valid direction...

1. Take a step foreward.
2. Now, turn to your right.
3. Now turn left untill the area in front of you is clear.
4. Go back to 1.

or, in C version...
Code:
```int main (void)
{
while (!GameOver())
{
StepForeward();
TurnRight();
while (!CanStepForeward())
{
TurnLeft();
}
// end of while, goes back to StepForeward()
}
return 0;
}```
It might be worthwhile to actually try out this algorithm in real life. It's just like walking with your hand, except instead of using your hand, you turn right after every step you take (much turning is involved).

7. hey i think i get your idea now. Thnx a lot. How did you figure that out but?

8. oops i nearly forgot. I have to write the function as a recursive function. But how do u do that? Wouldn't it waste more memory? Anyway can someone like write a few lines of pseudocode to guide me a little?

thnx in advance, i'll post the code once i finished.

9. pls help

like do i call the function recursively EACH time i take a step or what?

thnx

10. Seems interesting.. I will try it myself..

11. It seems to me to be pretty strange that you have to use recursion in this case.

I would have done it by using a loop in main to call the function repeatedly.

My suggestion would be to either do what Stoned_Coder suggested, which seems to me to have incredible overheads for what you want it to do, or have the part which determines if the "cell" ahead and to the right is occupied, being recursively called.

eg.
Code:
```/* This checks if it can move forward whilst keeping a block on the right. */
int Looking(position *Facing)
{
if(Facing==UP)
{
/* check if right block exists */
if(maze[xnow+1][ynow]!=BLOCKED)
{
/* if not blocked, turn right */
*Facing=RIGHT;
Looking(Facing);
}
else
{
/* check if above block exists */
if(maze[xnow][ynow+1]!=BLOCKED) return TRUE;
if(maze[xnow][ynow+1]==BLOCKED)
{
/* blocked, turn left */
*Facing=RIGHT;
Looking(Facing);
}
/* otherwise, something has gone wrong! */
else return ERROR;
}
}
}```
A problem (and there are probably many more) with this code is that if the mazee starts off enclosed , ie.

Code:
```    ###
#X#
###```
then the program will recursively call and then hang until it runs out of memory... you may want to add a global or pass in a variable that gets incremented each time that it is recursively called. You would also want a switch statement for checking the various positions that the mazee is in instead of the if() that I used.

Hope it helps.

12. hi, i also agree that it's not good and would make the problem even more complicated if i use recursion. But thats what my exercise require me to do. Wel............

But your function doesn't seem to work. It only tests if it can move UP. And it can't turn around corners. But other than that, i got some ideas from it. Thnx

13. This really is a problem where the loop seems best, but you certainly can do much the same thing recursively.

The algorithm used here is essentially the same as the one I used before... step foreward, turn right, repeat. The function itself returns TRUE if it finds a path to the exit, and FALSE if it doesn't (most recursive functions where you need to find a path will either have returns like this, return the number of paths found, or some score for deciding which path has the highest/lowest score).

A change I'm going to use is that instead of having a CanStepForeward function, the recursive function will handle illegal positions. This is another thing you see a lot in recursive functions, (for example, a binary tree traversal often doesn't test for whether the children are NULL before trying to operate on them; it just operates on them and is clever enough to handle NULL).

I'm going to firther C-ize the code. The player is a struct of 3 ints. One for his x position, one for his y position, and one for his direction...
Code:
```typedef struct
{
int x, y, dir;
} player;

int TraverseMaze(player ThePlayer)
{
if (GameOver(&ThePlayer)) return 1;
if (IllegalPosition(&ThePlayer)) return 0;

// At this point in the function, we know the player is at a legal
//  position, that is, he isn't standing in a wall.  Now we just do
//  the turn right, test for path in front, turn left if illegal part...
TurnRight(&ThePlayer);

// player StepForeward(player ThePlayer);
// Basically, if the path 1 step ahead of use leads to the exit, then
//  the path from our current position leads to the exit too.
if (TraverseMaze(StepForeward(ThePlayer))) return 1;
//else...
TurnLeft(&ThePlayer);
if (TraverseMaze(StepForeward(ThePlayer))) return 1;
// else...
TurnLeft(&ThePlayer);
if (TraverseMaze(StepForeward(ThePlayer))) return 1;
// now, if we turn left one more time, then we're going to be
//  facing the direction we came from, but we can't do that,
//  so we've exausted all the possibilities, so this path is false.

return 0;
}```
Umm.. obviously I suggest cleaning up this code a lot if you want to use it (I think half my lines are return statements, isk). This code doesn't have anything in it to actually print the path, but adding that isn't too tough.

If I might suggest, a similar (better) problem would be to write a function which returns the number of paths from the starting location to the ending location.

Or, if you're up for a chellenge, you might want to try writing a function that can solve mazes like this...
Code:
```###########
#    B    #
# ####### #
# #     # #
# # ### # #
# # #E# # #
# #     # #
# ### ### #
#         #
###########

B = Begin Here
E = End Here```

14. But your function doesn't seem to work. It only tests if it can move UP.
Well, you didn't expect me to write the lot for you did you?
I'm not that nice a person.

You'd have to code the remaining cases (left, right, down) before it would work and a main, and declare most of the variables, #define things, etc, etc, etc...

And it can't turn around corners.
Well, it was intended to do 2 things:
1) "Look" if it can go in the direction in which it is facing and return TRUE if it can. If it can't, it will turn around until it can move forward again.

2) Check if there is a wall to the right of it.

I also found another error... sort of...

Code:
```if(maze[xnow][ynow+1]==BLOCKED)
{
/* blocked, turn left */
*Facing=RIGHT;
Looking(Facing);
}```
Should be...

Code:
```if(maze[xnow][ynow+1]==BLOCKED)
{
/* blocked, turn left */
*Facing=LEFT;
Looking(Facing);
}```
Although that wouldn't have broken it (I don't think) it definitely wouldn't have done what I intended it to do.

If you are doing it for some kind of assignment, you may want to modify it to avoid the use of global variables and only use methods that have been covered in classes.

15. okay............

to QuestionC:
I haven't learnt structures yet.

To Limerick:
Can it also check that the wall to the right is the same wall starting from the startin point?

thnx for all help