Using Breadth First Search

This is a discussion on Using Breadth First Search within the C++ Programming forums, part of the General Programming Boards category; For a project I have to create a text adventure type game. Using a graph to setup the rooms. One ...

  1. #1
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640

    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
    }
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Here you go.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    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.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Last edited by quzah; 05-06-2005 at 01:17 AM.
    Hope is the first step on the road to disappointment.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 08:41 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 06:20 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21