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.

Without recursion? Then use queues and/or stacks.

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.

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

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.

Thank you very much that helped a lot.