Алгоритм PathFinding: как эффективно обрабатывать изменения веса

Question

Итак, у меня есть простой алгоритм поиска пути, который предварительно рассчитывает кратчайший маршрут до нескольких конечных точек, каждая из которых имеет свой вес. Это несколько эквивалентно наличию одной конечной точки с узлом между ней и каждой конечной точкой, хотя ребра там имеют разные веса. Используемый алгоритм представляет собой простой алгоритм расширения, который в 1d выглядит следующим образом (| означает стену, - означает пространство):

• 5 - - - 3 | - - - 2 - - - - 2
• 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
• 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
• 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
• 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
• Done. Any remaining rooms are unreachable.

Итак, давайте предположим, что у меня есть предварительно рассчитанное решение для поиска пути, подобное этому, где только 5 является целью:

- - - - | 5 4 3 2 1 -

Если я поменяю стену на комнату. Перерасчет прост. Просто повторно обработайте все удаленные узлы (но игнорируйте те, которые уже существуют). Однако я не могу найти эффективный способ справиться с тем, что делать, если четверка превратилась в стену. Ясно, что результат таков:

- - - - | 5 | - - - -

Однако в двумерном решении я не уверен, как эффективно справиться с 4. Можно легко сохранить, что 4 зависит от 5 и, следовательно, требует повторного вычисления, но как мне безопасно определить его новую зависимость и значения? Я бы предпочел не пересчитывать весь массив.

Одним из решений, которое лучше, чем ничего, является (примерно) только пересчет элементов массива с манхэттенским расстоянием 5 от 5 и сохранение исходной информации. Это в основном означало бы повторное применение алгоритма к выбранной области. Но могу ли я добиться большего успеха?

Answer 1

Хммм. Одно из решений, которое я нашел, заключается в следующем: Держите список узлов, которые достижимы наиболее быстро от каждого узла. Если узел становится стеной, проверьте, с какого узла он был доступен, и возьмите соответствующий список. Затем перепроверьте все эти узлы, используя стандартный алгоритм. При достижении узла, где новое расстояние меньше, отметьте его как нуждающегося в повторном тестировании.

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