Thread: 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.

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.