Pathfinding issues

Question

Ok I am trying to make a dynamic pathing system so the player can move from point A to point B without having predefined paths. Note this game is all text based no graphics. The player can move in 10 directions: up, down, n, e, s, w, sw, se, nw and ne.

The map of the entire world is in a database, each row of the database contains a room or a node, each room/node has directions it's capable of going. The room may not be sequential persay. An Example:

Map Number, Room Number, Direction_N, Direction_S, Direction_E, Direction_W, etc.
    1            1           1/3          1/100       1/1381       1/101

The Direction_N indicates it goes to Map 1 Room 3, Direction_S Map 1 Room 100, etc...

Ok, I reworked the code with suggestions (thank you guys by the way!) here is revised code. It seems to find the rooms now, even vast distances! But now the issue is finding the shortest path to the destination, I tried traversing the collection but the path is not coming out right...

In the image link below, I have start point in red square in center and stop point at red square at upper left. This returns visitedStartRooms = 103 and visitedStopRooms = 86, when it's only about 16 rooms. Quess my missing piece of the puzzle is I am not sure how to sort out the rooms in those collection to gain the true shortest route.

Example of map

Here is the new code

        public void findRoute(ROOM_INFO startRoom, ROOM_INFO destinationRoom)
    {
        Dictionary<ROOM_INFO, bool> visitedStartRooms = new Dictionary<ROOM_INFO, bool>();
        Dictionary<ROOM_INFO, bool> visitedStopRooms = new Dictionary<ROOM_INFO, bool>();

        List<string> directions = new List<string>();


        startQueue.Enqueue(startRoom); // Queue up the initial room
        destinationQueue.Enqueue(destinationRoom);

        visitedStartRooms.Add(startRoom, true);// say we have been there, done that
        visitedStopRooms.Add(destinationRoom, true);

        string direction = "";
        bool foundRoom = false;

        while (startQueue.Count != 0 || destinationQueue.Count != 0)
        {

            ROOM_INFO currentStartRoom = startQueue.Dequeue(); // remove room from queue to check out.
            ROOM_INFO currentDestinationRoom = destinationQueue.Dequeue();

            ROOM_INFO startNextRoom = new ROOM_INFO();
            ROOM_INFO stopNextRoom = new ROOM_INFO();

            if (currentStartRoom.Equals(destinationRoom))
            {
                break;
            }
            else
            {
                // Start from destination and work to Start Point.
                foreach (string exit in currentDestinationRoom.exitData)
                {

                    stopNextRoom = extractMapRoom(exit); // get adjacent room
                    if (stopNextRoom.Equals(startRoom))
                    {
                        visitedStopRooms.Add(stopNextRoom, true);
                        foundRoom = true;
                        break;
                    }

                    if (stopNextRoom.mapNumber != 0 && stopNextRoom.roomNumber != 0)
                    {
                        if (!visitedStopRooms.ContainsKey(stopNextRoom))
                        {
                            if (visitedStartRooms.ContainsKey(stopNextRoom))
                            {
                                foundRoom = true;
                            }
                            else
                            {
                                destinationQueue.Enqueue(stopNextRoom);
                                visitedStopRooms.Add(stopNextRoom, true);
                            }
                        }
                    }
                }

                if (foundRoom)
                {
                    break;
                }
            }

            // start from the start and work way to destination point
            foreach (string exit in currentStartRoom.exitData)
            {

                startNextRoom = extractMapRoom(exit); // get adjacent room
                if (startNextRoom.Equals(destinationRoom))
                {
                    visitedStartRooms.Add(startNextRoom, true);
                    foundRoom = true;
                    break;
                }
                if (startNextRoom.mapNumber != 0 && startNextRoom.roomNumber != 0)
                {
                    if (!visitedStartRooms.ContainsKey(startNextRoom))
                    {
                        if (visitedStopRooms.ContainsKey(startNextRoom))
                        {
                            foundRoom = true;
                            break;
                        }
                        else
                        {

                            startQueue.Enqueue(startNextRoom);
                            visitedStartRooms.Add(startNextRoom, true);
                        }

                    }
                }
            }


            if (foundRoom)
            {
                break;
            }
        }

    }

Answer 1

You have a good start. There are a few basic improvements that will help. First, to be able to reconstruct your path, you should create a new data structure to store visited rooms. But for each entry, you want to store the room, plus the previous room in the path back to the starting point. A good data structure for this would be a dictionary where the key is the room identifier, and the value is the previous room identifier. To know if you've visited a room, you look to see if it exists in that data structure, not your openList queue. With this new structure, you can properly check if you've visited a room, and you can reconstruct the path back by repeatedly looking up the previous room in the same structure until you get to the origination.

The second improvement will increase the performance quite a bit. Instead of just doing a breadth-first search from the start point until you bump into the destination, as you currently do, instead create matching data structures like you have for the start room search, but have them be for the destination room. After you've looked one room away from the start, look one room away from the destination. Repeat this...two rooms away from start, then two rooms away from destination.. etc., working your way out, until you discover a room that has been visited by both your search from start and your search from destination. Build the path from this room back to the start, and back to the destination, and that will be your shortest path.

The problem you are trying to solve is the shortest path problem with unweighted edges or where the weights of all edges are equal. The weight of an edge is the time/cost to move from one room to another. If the cost to move from one room to another varies depending on which pair of rooms you're talking about, then the problem is more complicated, and the algorithm you started with and for which I've suggested modifications, will not work as it is. Here are some links about it:

Shortest path (fewest nodes) for unweighted graph

http://en.wikipedia.org/wiki/Shortest_path_problem

You may also be interested in the A* algorithm which uses a different approach. It uses a hueristic approach to concentrate the search in a subset of the solution space more likely to contain the shortest path. http://en.wikipedia.org/wiki/A%2a_search_algorithm But A* is probably overkill in your case since the weight of all edges is the same between all rooms.