Оптимизировать алгоритм поиска кратчайшего пути

Question

[Андрей Апанасик]

День добрый.

Возникла проблема с алгоритмом поиска пути. Реализовывал алгоритм Ли и многие другие. Проблем раньше не возникало в силу того, что карты игровые маленькие.
Сейчас возникла необходимость рассчитывать кратчайший путь у npc на довольно большой карте.

И вот две проблемы возникли:
1) Так как карта большая, то прогонка волнового алгоритма для каждого npc само по себе довольно затратна.
2) Пока что путь рассчитывается на каждом шаге по новой.

Поэтому, хочу попросить помощи в оптимизации алгоритма, чтобы как-то исключить эти проблемы. Или, по крайней мере, минимизировать как-то время вычисления.

p.s. нет необходимости в уже готовых исходниках и т.д., мне интересна именно теоретическая часть.

Comments

[soniq]

Если вы пользуетесь А* то зачем пересчитывать весь путь, если N шагов впереди свободны. Пусть гейм-мастер определит допустимое N и тогда пересчитывайте путь.

Answer 1

[rPman]

Я не знаю, пробовали ли вы этот вариант, основанный на утверждениях:
1. полностью вся карта игрового мира изменяется не сильно
2. обычно карту можно попытаться поделить на зоны или в тупом варианте ячейки (или точнее варианты перемещения между ними), которые так же меняются очень редко и не сильно
Простейший пример: пусть зоны — просто квадратные ячейки внутри простой сетки, размер ячейки сравним со средним размером препятствия на карте.
Более сложный пример: многоугольная область поделена на зоны по границам больших препятствий, и перпендикулярно пересекающие типичные пути движения юнитов (грубо говоря магистрали их движения), такую статистику в процессе игры собрать не сложно, сложнее выбрать размер зоны, как враиант — фиксировать количество таких зон от среднего количества юнитов в игре…
Тогда из соседних ячеек пути перемещения обычно либо в обход через соседние ячейки либо через соединяющую грань между этими двумя.
Размеры ячеек должны быть подобраны таковыми, чтобы вмещать некоторое (не сильно большое) количество препятствий… десятки или сотни.

Заранее просчитываем (и постепенно обновляем по мере изменения мира, это не обязательно делать в реальном времени, хотя тогда будут возможны забавные артефакты в движениях) возможные пути перемещения между такими зонами (каждая грань — список пересекаемых зон возможными путями), а в момент, когда необходим точный путь, просчитываем его только в пределах этих ячеек, добавив в алгоритм поиск точки на грани между ячейками, ближайшей к пути (та еще задачка).

Весь путь считать не актуально, достаточно рассчитывать в пределах 1-2 ячеек вперед (по уже известным вам алгоритмам) и получать ответ, есть ли вообще возможность попасть к цели. Добавить к алгоритму пересчет пути в зависимости от игровых объектов актуальных для расчета коллизий (тут проблема — возможны ли заторы).

Такие ячейки — это аналог памяти юнитов о том, как можно было бы примерно пройти в соответствующую зону.
Добавит даже больше реализма, например поведение при заторах, юнит как бы еще не видит что путь впереди закрыт, но послушно топает, пока не попадет в ячейку с этим затором… тогда возникнет событие что путь достигнуть нельзя… так как меду ячейками вариантов перемещения всегда несколько, это создает не один путь перемещения по ячейкам несколько, соответственно временно помечаем что путь закрыт и выбираем следующий.

Answer 2

[simbajoe]

Посмотрите вот эту статью: habrahabr.ru/post/162915/. И вот эту: habrahabr.ru/post/166713/. Вместе, вроде, то что надо.

Answer 3

[afiskon]

Попробуйте ознакомиться с этой заметкой, может наведет на нужные мысли.