Thread: Maze program

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Maze program

    Hi all,
    Anybody know where to find ideas to solve a 2D-maze program WITHOUT using recursion. It has to be using Depth-First Search or Breadth-First Search algorithm. Pseudocode would be appreciated as well. Thank you.

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Without recursion? Then use queues and/or stacks.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    If by solving you mean how many steps from the beginning to the end, you could create a struct that contains an x-pos, y-pos, and number of steps from beginning, place the beginning as the first entry in a queue, and keep adding to the queue all the possibilities of directions that the front of the queue can go with current steps + 1. Do this until the ending is added to the queue and its step count is the answer.

    If you just want to find out the any path to the end, then I believe a stack is the way to go.

  4. #4
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Implemeting a Queue-Based Maze Program

    CAn you say that in a more pseudo-like format. I mean, what exactly would the 'step-count' be? Thank you.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Ok, first you would need a struct that contains three integers like so:
    Code:
    struct spot
    {
       int x,y,steps;
    }
    X and Y are the coordinates of that particular spot or room or whatever you want to think of it as. Steps is the number of steps it takes to get from the beginning to that room.

    So now you would need to create a queue and add a spot that signifies where you start with a step count of zero, since it takes zero steps to get there. In pseudocode:
    Code:
    create beg spot(x=begX, y=begY, steps=0)
    queue push(beg spot)
    Now, you basically do an infinite loop that always looks at the front of the queue, and it cycles through all the possible directions to go adding the rooms available to the back of the queue. Each of these rooms have one more step count than the current room (if it takes 2 steps to get here, then it takes 3 steps to get to the next room, etc). When you are done with that, pop the front and go to the next spot in the queue. Like so:
    Code:
    while queue is not empty
    {
        check north, east, west, and south from the room at the front of queue
        {
            *if room in this direction hasn't been entered yet* then
            add that room to the end of the queue with the appropriate
            x and y coordinates and with a step count one greater than
            the current room
    
            if the room in that direction is the end, stop and return the
            step count to this current room plus one
         }
         pop the front of the queue
    }
    Like I said this solves the problem of how many steps does it take to get from the beginning to the end if one takes the best route. I'm not sure if that is what you are trying to accomplish.

  6. #6
    Registered User
    Join Date
    Sep 2002
    Posts
    92
    Thank you very much that helped a lot.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  2. Help my c++ program
    By cal_cyrus in forum C++ Programming
    Replies: 0
    Last Post: 05-21-2007, 01:24 PM
  3. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  4. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM