# Thread: Algorithm to walk through a maze.

1. Hummmm...
Well, I strongly suggest learning structures; you're gonna be using them a lot more than you use recursion...

Now that I think of it, if you're working recursively, it might be easier to just do an even more brute-force method... here's how it goes.
Code:
// Don't need to keep direction for this one, although it does need a global array.

// This array holds a 1 if the corresponding square in the
//  maze is blocked, and a 0 if the square is allowed to be
//  used.  It is the caller's job to make sure that this array
//  has a 1 in it for every square with a wall.
int blocked [X_SIZE][Y_SIZE] = {};

int TraverseMaze (int x, int y)
{
// If you're on an illegal square, you fail.
if (blocked[x][y]) return 0;
// If you're at the end, you win.
if (GameOver(x, y)) return 1;

// Block the current square.  No moves after this may use this
//  square.
blocked[x][y] = 1;

// Try this function on each of the 4 directions.
if (TraverseMaze (x + 1, y)) return 1;
if (TraverseMaze (x - 1, y)) return 1;
if (TraverseMaze (x, y - 1)) return 1;
if (TraverseMaze (x, y + 1)) return 1;

// If all 4 directions fail, then throw in the towel.
blocked[x][y] = 0;
return 0;
}
This doesn't follow any right-wall algorithm, it just performs an exaustive search on all the possible paths which don't go through walls or cross it's own path. This algorithm actually will solve any maze.

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

and...

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

Apparently neither of you have done much with mazes. Recursion is a very common way to traverse a maze. It's also VERY easy.

Code:
traverseMaze( int x, int y )
{
maze[x][y]++; /* mark square as used */
if( !maze[x][y-1] ) traverseMaze( x, y-1 );
if( !maze[x+1][y] ) traverseMaze( x+1, y );
if( !maze[x][y+1] ) traverseMaze( x, y+1 );
if( !maze[x-1][y] ) traverseMaze( x-1, y );
}
This will move through all cells in the maze. You'd naturally want to do your own boundry checking, which I didn't bother to do, and also test for finding the goal, or using all squares.

Calls to this don't generate huge amounts of overhead, because it doesn't declare any variables. You can actually do the same with a loop, but it's MUCH easier to just write a recursive function to do it.

Quzah.

3. Can it also check that the wall to the right is the same wall starting from the startin point?
Well, its just designed to follow a wall to its right until the wall stops, if that's what you mean. If the wall is like the one below...

Code:
###########
#         #
#  #####  #
#  #   #X #
Where X is the person, facing down. It won't find its way out of the maze because it'll follow the wall around and around and around and not realise that its been there before. It does however, implement the algorithm you described.

Well, I strongly suggest learning structures; you're gonna be using them a lot more than you use recursion...
Yeah, I second that... recursion is hard thing to get your mind around and unless you're specifically aiming for it, you probably won't want to code an original algorithm involving recursion even if it does turn out easier.

Speaking of learning, have you learnt about pointers and call-by-reference yet? If you haven't, you should just use globals or whatever method you have been taught to pass variables between functions.

Apparently neither of you have done much with mazes. Recursion is a very common way to traverse a maze. It's also VERY easy.
No, I haven't but although the code is elegant, the logic will mess with your mind if you haven't had much exposure to recursion. I've found that often the coding is easy, its the logic that's hard. Also, would it be obvious to someone who has just started programming to do it this way? It may be better for a student to hand in a working program that is inelegant than to hand in an elegantly working program which looks like its been written by someone else.

4. All c++ texts that I have read that have dealt with traversing a maze have used it as a method of teaching recursion.
The same goes for traversing binary trees. Although both can be traversed iteratively it is easier in both cases to use recursion.

5. Hi,

I have the deitel book. And he gives me many which i think is pretty tough exercises. Anyway, this is what i have so far and it doesn't work. Dunno why. I know it's pretty messy sorry. It prints "maze solver!" even though it hasn't moved at all from the startin point!

Code:
/* Walk through maze */

#include <stdio.h>

int mazeTraverse( char maze[][ 12 ], int startingRow, int startingCol );
void check_gameover( int *gameover, int currentRow, int currentCol, int startingRow, int startingCol );
void printMaze( char maze[][ 12 ] );

int main()
{                         /* 0    1    2    3    4    5    6    7    8    9    10   11        */
char maze[ 12 ][ 12 ] = { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',  /* 0 */
'1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1',  /* 1 */
'0', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '1',  /* 2 */
'1', '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '1',  /* 3 */
'1', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0',  /* 4 */
'1', '1', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1',  /* 5 */
'1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1',  /* 6 */
'1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1',  /* 7 */
'1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1',  /* 8 */
'1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1',  /* 9 */
'1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1',  /* 10 */
'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' };/* 11 */
int retval;

retval = mazeTraverse( maze, 2, 0 );

if ( retval == 1 )
printf( "\n\nMaze solved!\n\n" );
else if ( retval == 2 )
printf( "\n\nThere is no exit point!\n\n" );

system( "PAUSE" );
return 0;
}

int mazeTraverse( char maze[][ 12 ], int startingRow, int startingCol )
{
int gameover = 0;
int currentRow = startingRow, currentCol = startingCol;
char currentDirection;
int turnLeft;

/* determine current direction facing */
if ( startingRow == 11 )
currentDirection = 'N';
else if ( startingRow == 0 )
currentDirection = 'S';
else if ( startingCol == 0 )
currentDirection = 'E';
else if ( startingCol == 11 )
currentDirection = 'W';

while ( gameover == 0 ) {
printMaze( maze );
switch ( currentDirection ) {
case 'N':
maze[ currentRow ][ currentCol ] = 'X';
if ( maze[ currentRow - 1 ][ currentCol ] != '1' )
currentRow -= 1;
check_gameover( &gameover, currentRow, currentCol, startingRow, startingCol );
currentDirection = 'E';
if ( maze[ currentRow ][ currentCol + 1 ] == '1' )
turnLeft = 1;
break;
case 'S':
maze[ currentRow ][ currentCol ] = 'X';
if ( maze[ currentRow + 1 ][ currentCol ] != '1' )
currentRow += 1;
check_gameover( &gameover, currentRow, currentCol, startingRow, startingCol );
currentDirection = 'W';
if ( maze[ currentRow ][ currentCol - 1 ] == '1' )
turnLeft = 1;
break;
case 'W':
maze[ currentRow ][ currentCol ] = 'X';
if ( maze[ currentRow ][ currentCol - 1 ] != '1' )
currentCol -= 1;
check_gameover( &gameover, currentRow, currentCol, startingRow, startingCol );
currentDirection = 'N';
if ( maze[ currentRow - 1 ][ currentCol ] == '1' )
turnLeft = 1;
break;
case 'E':
maze[ currentRow ][ currentCol ] = 'X';
if ( maze [ currentRow ][ currentCol + 1 ] != '1' )
currentCol += 1;
check_gameover( &gameover, currentRow, currentCol, startingRow, startingCol );
currentDirection = 'S';
if ( maze[ currentRow + 1 ][ currentCol ] == '1' )
turnLeft = 1;
break;
}

if ( turnLeft == 1 ) {
switch ( currentDirection ) {
case 'N':
if ( maze[ currentRow ][ currentCol - 1 ] != '1' ) {
currentDirection = 'W';
break;
}
else if ( maze[ currentRow - 1 ][ currentCol ] != '1' ) {
currentDirection = 'S';
break;
}
else if ( maze[ currentRow ][ currentCol + 1 ] != '1' ) {
currentDirection = 'E';
break;
}
case 'S':
if ( maze[ currentRow ][ currentCol + 1 ] != '1' ) {
currentDirection = 'E';
break;
}
else if ( maze[ currentRow + 1 ][ currentCol ] != '1' ) {
currentDirection = 'N';
break;
}
else if ( maze[ currentRow ][ currentCol - 1 ] != '1' ) {
currentDirection = 'W';
break;
}
case 'W':
if ( maze[ currentRow - 1 ][ currentCol ] != '1' ) {
currentDirection = 'S';
break;
}
else if ( maze[ currentRow ][ currentCol + 1 ] != '1' ) {
currentDirection = 'E';
break;
}
else if ( maze[ currentRow + 1 ][ currentCol ] != '1' ) {
currentDirection = 'N';
break;
}
case 'E':
if ( maze[ currentRow + 1 ][ currentCol ] != '1' ) {
currentDirection = 'N';
break;
}
else if ( maze[ currentRow ][ currentCol - 1 ] != '1' ) {
currentDirection = 'W';
break;
}
else if ( maze[ currentRow - 1 ][ currentCol ] != '1' ) {
currentDirection = 'S';
break;
}
}
}
}

printf( "\n\nCurrent row is %d", currentRow );
printf( "\nCurrent column is %d", currentCol );
printf( "\nCurrent direction is %c", currentDirection );

if ( gameover == 1 )
return 1;
else if ( gameover == 2 )
return 2;
else
return 0;

}

void check_gameover( int *gameover, int currentRow, int currentCol, int startingRow, int startingCol )
{
if ( currentRow == 0 || currentRow == 11 )
*gameover = 1;
else if ( currentCol == 0 || currentCol == 11 )
*gameover = 1;
else if ( currentRow == startingRow && currentCol == startingCol )
*gameover = 2;
else
*gameover = 0;
}

void printMaze( char maze[][ 12 ] )
{
int i, j;

printf( "\n\n" );

for ( i = 0; i < 12; i++ )
for ( j = 0; j < 12; j++ ) {
printf( "%c", maze[ i ][ j ] );
if ( j == 11 )
printf( "\n" );
}
}

6. Here are a few ideas:
Code:
int check_gameover( int cRow, int cCol, int sRow, int sCol )
{
if( cRow == 0 || cRow == 11 ) return 1;
if( cCol == 0 || cCol == 11 ) return 1;
if( cRow == sRow && cCol == sCol ) return 2;
return 0;
}
No need for a pointer there.

...sorry, phone call, I'll have to cut this short.

Quzah.

7. nope, still doesn't solve my problem. How come it just doesn't move from the starting point!

thnx

8. Hi,

To quzah: Your idea doesn't seem to move according to the current direction facing. WHich i am mostly troubled at. And if i am right, the code would be much longer to do direction checkin and move accordingly?

9. Hmm. I get the feeling that this isn't correct...
Code:
currentDirection = 'S';
if ( maze[ currentRow + 1 ][ currentCol ] == '1' )
turnLeft = 1;
Or, if that is correct, then this is probably wrong...
Code:
else if ( maze[ currentRow + 1 ][ currentCol ] != '1' ) {
currentDirection = 'N';
break;
You've clearly mixed up how you treat north and south. I'm not sure which one is correct.

Also, that code is a bit hard to read, with so much in one function. You'll save yourself a lot of pain if you split mazeTraverse into smaller functions wherever possible. For example, instead of
Code:
if ( turnLeft == 1 ) {
// Page of code
}
Try using the following...
Code:
if (turnLeft == 1)
{
currentDirection = handleTurnLeft (currentDirection, currentCol, currentRow);
}
Technically it doesn't save any typing, since you'll have to put it somewhere ense in the program, but the more organized you can get your mazeTraverse function, the easier it will be to read and debug, not to mention it lets you test these subfunctions of mazeTraverse individually.

10. Another odd thing I noticed is the way you assign a starting position. If you start in a corner, your rules may not apply correctly.

I honestly don't see a point in using "facing" here. Unless you're using some other character to show what way they're facing:

> face right
< face left
^ face up/north/foreward
v face down/south/backwards

Additionally, you'll need to change your loop if you use my version of 'gameover' function:
Code:
while( check_gameover( currentRow, currentCol, startingRow, startingCol ) == 0 )
{

}
This is better because you only have to have 'check_gameover' once in your loop. Additionally, it seems like you're confusing 'turn left' with 'move to the left'. Again, I'm not sure why you're bothering with "turning" as opposed to "moving".

The only way "turning" is useful is if you do:
Code:
if( canMoveForeward( ... ) == 0 )
{
turnLeft( )
}
else
moveForeward( ... );
Then, if you've turned around four times without moving, you're stuck.

Quzah.

11. The direction is neccisary because this is using the follow the right wall algorithm.

If it were just an exaustive search of all possible paths, then it wouldn't be.

12. yeah, coz if my direction is north, then my right would be east, if direction is east, right side would be south.....

13. ## Sorry, it's not bug free. Here is a solution.

Sorry, Daniel

I have tried to read your idea.. I mean code .. may that one is also a right way.. but I felt better to try this way..
The code is not bug free just found the logic is working....

I'm sure that you have to fix errors...

Code:
/*************************************/
/*mazebyz.h on 20th Jan 2002*/
/* Part of magebyz.c*/
/* I found that this is the core part should be clear*/
/*************************************/

int get_next_move(char maze[][12],int row, int col,
int direction, int *n_row, int *n_col, int *n_direction)
{

switch(direction) 	/* 4 possible directions*/
{

case 0:			/*when your direction is West*/

if(is_a_valid_cell(maze, row+1,  col)==YES) /*first possible move*/
{

*n_row=row+1;
*n_col=col;
return YES;

}
/* if left cell is not valid*/
else  if(is_a_valid_cell(maze, row,col-1)==YES) /*second possible move*/
{
*n_row=row;
*n_col=col-1;
*n_direction=direction; 		/*same direction*/
return YES;
}

/* if left cell & front cell is not valid*/
else if(is_a_valid_cell(maze, row-1,  col)==YES)/*third possible move*/
{
*n_row=row-1;
*n_col=col;
return YES;
}

/* if left cell & front & right cell is not valid*/
/* turn back*/
else if(is_a_valid_cell(maze, row,col+1)==YES)/*fourth and last possible move*/
{
*n_row=row;
*n_col=col+1;
return YES;
}

break;

case 1:			/*when your direction is North*/
if(is_a_valid_cell(maze, row,  col-1)==YES)
{
*n_row=row;
*n_col=col-1;
*n_direction=(direction-1+NO_OF_D)%NO_OF_D;

return YES;
}

else  if(is_a_valid_cell(maze, row-1,col)==YES)
{
*n_row=row-1;
*n_col=col;
*n_direction=direction;

return YES;
}

else if(is_a_valid_cell(maze, row,  col+1)==YES)
{
*n_row=row;
*n_col=col+1;
*n_direction=(direction+1)%NO_OF_D;

return YES;
}

else if(is_a_valid_cell(maze, row+1,col)==YES)
{
*n_row=row+1;
*n_col=col;
*n_direction=(direction+2)%NO_OF_D;

return YES;
}

break;

case 2:				/*when your direction is East*/

if(is_a_valid_cell(maze, row-1,col)==YES)
{
*n_row=row-1;
*n_col=col;
*n_direction=(direction-1+NO_OF_D)%NO_OF_D;

return YES;
}

else if(is_a_valid_cell(maze, row,  col+1)==YES)
{
*n_row=row;
*n_col=col+1;
*n_direction=direction;

return YES;
}

else if(is_a_valid_cell(maze, row+1,col)==YES)
{
*n_row=row+1;
*n_col=col;
*n_direction=(direction+1)%NO_OF_D;

return YES;
}

else if(is_a_valid_cell(maze, row,  col-1)==YES)
{
*n_row=row;
*n_col=col-1;
*n_direction=(direction+2)%NO_OF_D;

return YES;
}

break;

case 3:				/*when your direction is South*/

if(is_a_valid_cell(maze, row,  col+1)==YES)
{
*n_row=row;
*n_col=col+1;
*n_direction=(direction-1+NO_OF_D)%NO_OF_D;

return YES;
}

else  if(is_a_valid_cell(maze, row+1,col)==YES)
{
*n_row=row+1;
*n_col=col;
*n_direction=direction;
return YES;
}

else if(is_a_valid_cell(maze, row,  col-1)==YES)
{
*n_row=row;
*n_col=col-1;
*n_direction=(direction+1)%NO_OF_D;
return YES;
}

else if(is_a_valid_cell(maze, row-1,col)==YES)
{
*n_row=row-1;
*n_col=col;
*n_direction=(direction+2)%NO_OF_D;
return YES;
}

break;

}

return NO;
}

/*************************************/
/*mazebyz.c on 20th Jan 2002*/
/*************************************/

#include <stdio.h>
#define YES 	0
#define NO 	1
#define SUCCESS 0
#define NO_OF_D 4
#define ST_POINT 2

/*

00------>11
|
|
|
|
v
11

Directions:
01 N
^
|
W 00<- x ->02 E
|
v
03 S
*/

int position[3]={2,0,2}; /*row 2, col 1, north 2*/
static int starting_flag= 0;
void printMaze( char maze[][ 12 ] );
int check_gameover(int, int , int);

#include "mazebyz.h"

int main()
{
int row, col, direction;

/* 0    1    2    3    4    5    6    7    8   9   10   11 */
char maze[ 12 ][ 12 ] =
{ '1', '1', '1', '1', '1', '1', '1', '1', '1','1', '1', '1',  /* 0 */
'1', '0', '0', '0', '0', '0', '0', '0', '0','0', '0', '1',  /* 1 */
'0', '0', '1', '0', '1', '0', '1', '1', '1','1', '0', '1',  /* 2 */
'1', '1', '1', '0', '0', '0', '0', '0', '0','1', '0', '1',  /* 3 */
'0', '0', '0', '0', '0', '1', '1', '1', '0','1', '0', '1',  /* 4 */
'1', '1', '1', '1', '0', '1', '0', '0', '0','1', '0', '1',  /* 5 */
'1', '0', '0', '1', '0', '1', '0', '1', '0','1', '0', '1',  /* 6 */
'1', '1', '0', '1', '0', '1', '0', '1', '0','1', '0', '1',  /* 7 */
'1', '0', '0', '0', '0', '0', '0', '0', '0','1', '0', '1',  /* 8 */
'1', '0', '1', '1', '1', '1', '0', '1', '0','1', '0', '1',  /* 9 */
'1', '0', '0', '0', '0', '0', '0', '1', '0','0', '0', '1',  /* 10 */
'1', '1', '1', '1', '1', '1', '1', '1', '1','1', '1', '1' };/* 11 */

row=2;
col=0;
direction=2;

//printMaze(maze);
//printf("\n%d %d %d\n",row, col, direction);
printf(" 00------>11\n");
printf("  |\n");
printf("  |\n");
printf("  |\n");
printf("  |\n");
printf("  v\n");
printf(" 11\n\n");

printf("\nDirections:\n");

printf("      01 N\n");
printf("       ^\n");
printf("       |\n");
printf("W 00<- x ->02 E\n");
printf("       |\n");
printf("       v\n");
printf("      03 S\n");

/*Recursive function call*/
mazeTraverse( maze, row, col, direction );

//printMaze(maze);

return 0;
}

/* here is the recursive function to walk through the maze*/

int mazeTraverse( char maze[12][ 12 ], int row, int col, int direction )
{
int stat;
int n_row, n_col, n_direction; /* Move: next position*/

stat=check_gameover(row, col, direction); /* checkes if game is over*/

if(stat==ST_POINT && starting_flag==1) /*1 is to avoid the first move*/
{
printf("\nReturned to the starting point.\n");
printf("No other exit through this entry.\n");
return ST_POINT;
}

if(starting_flag==0) starting_flag=1; /*To mark that first move done*/

if(stat==YES) 		/*When check_gameover(); returns yes.*/
{
printf("\nExit point found!!!\n");
printf("Now, you are free.\n");
return YES;
}

if(maze[row][col]=='0')
maze[row][col]='x';	/*mark first time foot step*/

else if(maze[row][col]=='x')
maze[row][col]='*';	/*mark second time foot step*/

printMaze(maze);		/*display your position in the maze*/

/*find the qualified next pisition*/
get_next_move(maze, row, col, direction, &n_row, &n_col, &n_direction);

/*Testing: display next move:*/
printf("Move: r=%2.2d, c=%2.2d, d=%2.2d\n",n_row, n_col, n_direction);

/*Recursion*/
mazeTraverse( maze, n_row, n_col, n_direction );

return YES;

}

/*Compare the starting position with current position*/
int is_starting(row,col,direction)
{

if(row!=position[0])
return NO;

else if(col!=position[1])
return NO;

else return YES;

}

/* Checkes if a position is qualified*/
/*Not out of border & not a wall*/

int is_a_valid_cell(char maze[][12],int row, int col)
{
if( row < 0 || row > 11)
return NO;

else if( col < 0 || col > 11)
return NO;

else if(maze[row][col]!='1') return YES;

}

/*checks if you can see the outside world*/
/*check exit point*/

int is_at_border(int row, int col)
{
if(row==0||col==0)
return YES;

if(row==11||col==11)
return YES;

else return NO;
}

/*checks the position: exit point or entry position*/
int check_gameover(int row, int col, int direction)
{
if (is_starting(row,col,direction)==YES)
return ST_POINT;

if(is_at_border(row, col)==YES)
return YES;

else return NO;

}

/*displays the your position in the maze*/
void printMaze( char maze[][ 12 ] )
{
int i, j;

printf( "\n\n" );

for ( i = 0; i < 12; i++ )
for ( j = 0; j < 12; j++ ) {
printf( "%c", maze[ i ][ j ] );
if ( j == 11 )
printf( "\n" );
}
}
/*made little change: when no exit point found*/

14. output:

111111111111
100000000001
x01010111101
111000000101
000001110101
111101000101
100101010101
110101010101
100000000101
101111010101
100000010001
111111111111
Move: r=02, c=01, d=02

...............................
...............................
...............................

111111111111
1xxxxxxxxxx1
xx10101111x1
1110000001x1
0xxxx11101x1
1111x10001x1
1x*1x10101x1
11*1x10101x1
1x*xx0xxx1x1
1x1111x1x1x1
1xxxxxx1xxx1
111111111111
Move: r=04, c=00, d=00

Exit point found!!!
Now, you are free.

15. I really do enjoy seeing other people's code, but code tags need to be used for anything more than a few lines.