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.

Printable View

- 12-08-2002supaben34Maze 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. - 12-08-2002Magos
Without recursion? Then use queues and/or stacks.

- 12-08-2002PJYelton
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. - 12-08-2002supaben34Implemeting 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.

- 12-08-2002PJYelton
Ok, first you would need a struct that contains three integers like so:

Code:`struct spot`

{

int x,y,steps;

}

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)

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

}

- 12-08-2002supaben34
Thank you very much that helped a lot.