Shortest Path on Unweighted Edges

maxx2310

I am trying to develop a dynamic pathing algorithm for a game (all text) and running into an issue of finding the shortest path when all the edges(connectors) are the same cost or weight. The algorithm below will capture all the rooms from start to finish, but the issue is sorting it out to find the shortest distance to the finish, perhaps new algorithm is needed? Thanks in advance for any assistance.

public void findRoute(ROOM_INFO startRoom, ROOM_INFO destinationRoom)
{

        Dictionary visitedStartRooms = new Dictionary();
        Dictionary visitedStopRooms = new Dictionary();

        List directions = new List();


        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))
            {
                foundRoom = true;
                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.Contai

Luc Pattyn

I did not study your code, and unfortunately you did not describe your algorithm at all, nor did you provide a reference to whatever inspired you. I do know the normal approach would be something along these lines: - provide a storage for "distance from starting point" to each node; - initialize to "infinite" (well, zero would be fine too as long as you read that as infinite!); - now start walking around from the starting node, using a "breadth first" scheme; this means you go one step away from the starting point in all possible ways, you keep track of all the possible points at this distance (that needs a collection, say a list, it does not need an ordered collection such as a queue), and also set the distance to 1 for all the nodes you can reach in that one step. - now repeat for all the nodes you collected as having distance 1, then 2, then 3, etc. - however, for each node N that you can reach from node P in one step, make distance(N) equal to distance(P)+1 only if it does not already have a smaller value. - now the first time you reach the destination, you are sure to have reached it in the minimal number of steps. And by looking at the distance values, you can trace one way back to the starting point without needing any memory or any trials, just walk the way the distance decreases by one on every step. To my knowledge there isn't any superior algorithm, so the only thing you can do for performance is come up with a decent implementation! :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

maxx2310

Sorry Luc, your right I should have just explained what I was trying to do with the algorithm instead of the code. I am pretty much doing what your saying except for the keeping track of distance. Algorithm goes like this: 1. Place Start and End rooms into a start queue and end queue. 2. Enter a while loop with a condition not to leave while there is at least a Start or End Room loaded or that the destination is found. 3. I dequeue the room and iterate through each exit the room has and mark it as visited and load that room into the queue. 4. Repeat step 3 until I reach my destination or run out of rooms.

Luc Pattyn

That sounds pretty similar, I see it is breadth first; I'm not sure you also are getting the best route, as it seems you don't have permanent storage (the steps taken are being removed from the queues, aren't they?). :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

BupeChombaDerrick

This looks like you have to implement Dijkstra's algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm[^] :).

“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”

Luc Pattyn

Dijkstra's is considering too many possibilities: when all the edge costs are equal, the first solution found is bound to be the cheapest, no need to continue and investigate all the remaining routes. :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

BupeChombaDerrick

Luc Pattyn wrote:

when all the edge costs are equal, the first solution found is bound to be the cheapest, no need to continue and investigate all the remaining routes.

The best way might be to implement a generalized algorithm like Dijkstra's algorithm, you never know what might come up :laugh: .But for the sake of simplicity it is good to use Breadth First Search (BFS) in such a case as you outlined in your answer. However, in a game application the graph might not always contain edges of equal cost, anyways since the OP wants a specific algorithm for a graph with edges of equal cost then BFS suffices.

“Be at war with your vices, at peace with your neighbors, and let every new year find you a better man or woman.”

Tadeusz Westawic

This is an easy read if you are familiar with set notation. http://planning.cs.uiuc.edu/node4.html I have an unfinished project on the shelf which attempts to find the shortest path through a maze by "pressurizing" the maze at the entrance and coloring-in "temperature" or "pressure" at each cell in the maze. The "coolest" or "lowest pressure" (bluest) path is the shortest solution. Good Luck

Tadeusz Westawic Sum quid sum.