Как извлечь путь, взятый из этого алгоритма кратчайшего пути? - PullRequest
Новая
       4

Как извлечь путь, взятый из этого алгоритма кратчайшего пути?

0 голосов
/ 08 августа 2011

Я пытаюсь реализовать алгоритм в стиле «6 градусов», в котором я пытаюсь найти кратчайший путь между двумя ссылками. В этом сценарии это видеоигра с картами областей, в которых есть порталы / деформации, связанные друг с другом.

Каждая карта имеет идентификатор карты int id и может иметь несколько порталов, реализованных как List<Portal>.
Каждый портал ведет к карте, int ToMapID и имеет карту, которая его содержит, Map HomeMap.

Во всяком случае, мне удалось найти наименьшее количество перекосов между двумя картами, что хорошо, потому что именно к этому я и стремлюсь. Проблема в том, что мне трудно обдумать, как записать путь, пройденный из точки А в точку Б.

Вот что я реализовал: 

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;
}

В идеале я хотел бы иметь массив Map[], который имеет порядок шагов для перехода из точки А в точку Б.

Хотя я абсолютно не знаю, с чего начать. Как мне разгадать путь?

Ответы [ 2 ]

3 голосов
/ 08 августа 2011

Когда вы делаете newQueue.Add(tm);, вы также должны записывать, откуда вы пришли. Простое решение - добавить отношение в словарь: dict.Add(tm,p). В конце вы можете использовать этот словарь, чтобы пройти путь назад от цели, просто спросив родителя текущего портала.

2 голосов
/ 08 августа 2011

Кратчайший путь работает в основном так:

Начальная точка начинается с нулевой стоимости. Все остальные зоны начинаются со стоимости бесконечности.

Поддерживать очередь доступных зон. Изначально это просто начальная зона.

Итерируйте по достижимым зонам, всегда выбирая ту, которая дешевле.

Для каждой непосредственно подключенной зоны вычислите (стоимость + текущая зона) + (стоимость, чтобы взять соединительную точку деформации). Если это меньше текущей стоимости соседней зоны, обновите стоимость, установите указатель обратной ссылки на текущую зону и добавьте ее в очередь.

Повторяйте до тех пор, пока следующая обрабатываемая зона (зона с наименьшей стоимостью в очереди) не будет иметь стоимость, равную или превышающую целевую зону.

Затем из зоны назначения следуйте указателям обратной ссылки, чтобы сформировать свой путь.

В простом случае, когда все ссылки имеют одинаковую стоимость, вы можете просто использовать очередь FIFO, она останется отсортированной. Если стоимость поездки варьируется, вам нужно будет отсортировать очередь по стоимости зоны.

...