Thread: Algorithm to walk through a maze.

  1. #16
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  2. #17
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    > 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.
    Hope is the first step on the road to disappointment.

  3. #18
    Registered User
    Join Date
    Jan 2002
    Posts
    6
    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. #19
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #20
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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. #21
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  7. #22
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    nope, still doesn't solve my problem. How come it just doesn't move from the starting point!

    thnx

  8. #23
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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. #24
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  10. #25
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  11. #26
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  12. #27
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    yeah, coz if my direction is north, then my right would be east, if direction is east, right side would be south.....

  13. #28
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531

    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...

    here with comments ..

    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;
    *n_direction=(direction-1+NO_OF_D)%NO_OF_D; /*Your direction changed*/
    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;
    *n_direction=(direction+1)%NO_OF_D;	/*Your direction changed*/
    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;
    *n_direction=(direction+2)%NO_OF_D;	/*Your direction changed*/
    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
    
    
    /*
    Cell address:
    
     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("Cell address:\n\n");
    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*/
    Last edited by zahid; 01-21-2002 at 01:58 AM.
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  14. #29
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531
    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.
    Last edited by zahid; 01-21-2002 at 01:34 AM.
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  15. #30
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I really do enjoy seeing other people's code, but code tags need to be used for anything more than a few lines.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive Stack Algorithm Maze Solver
    By unrestricted in forum C Programming
    Replies: 0
    Last Post: 09-04-2007, 03:11 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM