CODEWITHSUNDEEP
c#shortest-path
Corey
Corey

Reputation: 1195

How to extract the path taken from this shortest-path algorithm?

I'm trying to implement a "6 Degrees"-style algorithm, in that I'm trying to find the shortest path between two links. In this scenario, it is a video game, which has area maps, which have portals/warps that link to one another.

Each map has a map ID, int id, and can have several portals, implemented as List<Portal>.
Each portal leads to a map, int ToMapID and has the map that contains it, Map HomeMap.

Anyway, I've been successful in finding the least number of warps between two maps, which is good because that is what I am going for. The problem is, I'm having a hard time wrapping my head around how to record the path taken from point A to point B.

Here is what I have implemented:

Map start = allMaps[0];
Map end = allMaps[1];

int distance = 0;

List<Portal> alreadyChecked = new List<Portal>();
List<Portal> queue = start.Portals;

while (queue.Count > 0) {
    distance++;
    List<Portal> newQueue = new List<Portal>();
    foreach (Portal p in queue) {
        foreach (Portal tm in theMap.Portals) {
            if (!alreadyChecked.Contains(tm)) {
                alreadyChecked.Add(tm);
                if (tm.ToMap == end.ID) {
                    Console.WriteLine("Found a path, it is " + distance + " map(s) away;");

                    Console.ReadKey();
                    Environment.Exit(0);
                }
                newQueue.Add(tm);
            }
        }

    }
    queue = newQueue;
}

Ideally, I would like to have an array of Map[], which has the order of steps to go from point A to point B.

I have absolutely no idea where to start, though. How do I unravel the path?

Upvotes: 0

Views: 385

Answers (2)

Ben Voigt
Ben Voigt

Reputation: 283773

The shortest path works basically like this:

The starting point starts with a cost of zero. All other zones start with a cost of infinity.

Maintain a queue of reachable zones. Initially this just has the starting zone.

Iterate through reachable zones, always choosing the one with lowest cost.

For each directly connected zone, calculate (cost + current zone) + (cost to take connecting warp point). If that's less that the current cost of the neighbor zone, update the cost, set a backlink pointer to the current zone, and add it to the queue.

Repeat until the next zone to process (the lowest cost zone in the queue) has a cost equal to or greater than the destination zone.

Then, from the destination zone, follow the backlink pointers to form your path.

In the simple case where all links have equal cost, you can just use a FIFO queue, it will stay sorted. If the travel cost varies, you will have to keep the queue sorted by zone cost.

Upvotes: 2

CodesInChaos
CodesInChaos

Reputation: 108830

When you do newQueue.Add(tm); you should also record where you're coming from. An easy solution is adding the relation to a dictionary: dict.Add(tm,p). In the end you can use this dictionary to walk the path backward from the goal by simply asking for the parent of the current portal.

Upvotes: 3

Related Questions