Using Breadth First Search

For a project I have to create a text adventure type game. Using a graph to setup the rooms. One option that is needed, is to find a path to from a start node to a finish node. I've tried implementing a breadth first search, but I'm not seeing how I'm supposed to use it. Right now, the BFS works correctly, however, I am supposed to print out the the path (room to room). I am having difficulty trying to figure out how to keep track of the path taken. Obviously I have to use some structure (array, list, stack, queue), but I don't understand how I am supposed to know which rooms need to be stored for the path. Once the destination is reached, it's not always possible to back track (going west to one room doesn't mean going east leads you back). Any ideas on what I'm missing?

Here is the basic idea of my BFS:

Code:

---

clear all room's visit status to false
set start room visit to true
enqueue start room

while queue is not empty
{

dequeue a room

if north path exists

if north room is not yet visited

set north room as visited

if north room is destination room, display and exit

enqueue north room

//do the same for south, east, west paths

}

---

Here you go.

Quzah.

Quote:

---

Originally Posted by quzah

Here you go.

Quzah.

---

Yea, I was at that site earlier, and it helped a little. I learned from there that I need to use Depth First Search instead. If it doesn't matter, then I understand DFS better, and I got the problem fixed. Thanks though.

DFS is definately the way to go. It's a pretty good illustration on BFS though for the rest of you out there who want to look at it.

You could use BFS if instead of marking each room as "used" with an increasing number, if you marked them as "used" with the room that you got there from. Basicly, 0 is "not used", and anything else means that room is in use. Then what you would do is "mark" the room with the number of the room that got you there. Thus, when you hit the end, you would mark it with the room that got you there. Then you'd go to that room, and see what it's marked. Then you go to that room... and so on.

That should do the trick. :)

Or if you don't have room "numbers", then replace the "number" marker with a pointer. "Mark" the room by assinging that pointer the address of the room that got you there. Otherwise, if it's null, it's unvisited. If it has a "mark", then you just jump back to there, and repeat until you hit the start. The start room would simply point to itself.


Quzah.

The problem with a DFS tree is that it won't necessarily find the shortest path between two points. This may or may not be a concern for you, and indeed if your rooms are set up as a perfect maze where there only exists one path between any two rooms then it doesn't matter.

When I do a BFS I usually create a struct that contains two items, 1) a pointer to the previous room and 2) the name of the current room. This structure is what I add to the queue. Then I also have an array of bools that I set to true that match the rooms, and I set to true when I enter a new room.

To print out the path, just iterate through the pointers recursively from beginning to end. Something like this:

Code:

---

// call this function as printPath(end) where end is pointer to ending room
void printPath(roomStruct *r)
{
      if (r->prev!=NULL)
        printPath(r->prev);
      cout<<r->name<<endl;
}

---