Thread: Algorithm to walk through a maze.

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    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!
    Last edited by Nutshell; 01-16-2002 at 09:31 AM.

  2. #2
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Pls anyone pls reply and give a hand

    thnx

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    In psedocode.....

    functolookforexit( what square)
    {
    if (exit found) do fireworks()
    else
    functolookforexit(next square)
    }
    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

  4. #4
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    how do i code so that it sticks to the right wall? And how do i make it turn corners ? thnx

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

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

  7. #7
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    hey i think i get your idea now. Thnx a lot. How did you figure that out but?

  8. #8
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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. #9
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    pls help

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

    thnx
    Last edited by Nutshell; 01-17-2002 at 12:09 AM.

  10. #10
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531
    Seems interesting.. I will try it myself..
    [ 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.

  11. #11
    Registered User
    Join Date
    Jan 2002
    Posts
    6
    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. #12
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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
    Last edited by Nutshell; 01-17-2002 at 02:25 AM.

  13. #13
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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
    Last edited by QuestionC; 01-17-2002 at 03:21 AM.
    Callou collei we'll code the way
    Of prime numbers and pings!

  14. #14
    Registered User
    Join Date
    Jan 2002
    Posts
    6
    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. #15
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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

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