Возьмите следующее с недоверием, так как у меня нет опыта от первого лица в поиске путей.
При этом, вероятно, будут разные подходы, но я думаю, что стандартный поиск по графикуМетоды, особенно (варианты) A *, вполне приемлемы для стратегических игр.Большинство известных мне стратегий, похоже, основаны на системе тайлов, где карта состоит из маленьких квадратов, которые легко отображаются на графике.Одним из примеров может быть StarCraft II ( Screenshot ), который я буду использовать в качестве примера в оставшейся части этого ответа, потому что я наиболее знаком с ним.
Хотя A *может быть использован для стратегических игр в реальном времени, есть несколько недостатков, которые необходимо преодолеть путем настройки основного алгоритма:
A * слишком медленно
Поскольку RTS по определению «в реальном времени», ожидание окончания вычислений расстроит игрока, потому что юниты будут отставать.Это можно исправить несколькими способами.Одним из них является использование Многоуровневого A *, который вычисляет грубый курс, прежде чем учитывать меньшие препятствия.Другой очевидной оптимизацией является группировка подразделений, направляющихся в один и тот же пункт назначения, во взвод и вычисление только одного пути для всех из них.
Вместо наивного подхода, заключающегося в том, чтобы сделать каждую плитку узлом на графе, можно такжепостроить навигационную сетку , которая имеет меньше узлов и может быть найдена быстрее - для этого требуется немного доработать алгоритм поиска, но в ядре все равно будет A *.
A * является статическим
A * работает на статическом графике, что делать при изменении ландшафта?Я не знаю, как это делается в реальных играх, но я представляю, что путь выполняется неоднократно, чтобы справиться с новыми препятствиями или удаленными препятствиями.Возможно, они используют инкрементную версию A * (PDF).
Чтобы увидеть демонстрацию того, как StarCraft II справляется с этим, перейдите к 7:50 в этом видео .
A * имеет отличную информацию
Часть многих игр RTS - это неизведанная местность.Поскольку вы не можете видеть местность, ваши отряды также не должны знать, куда идти, но часто они все равно знают.Один из подходов состоит в том, чтобы наказывать ходьбу по неизведанной местности, поэтому отряды более неохотно пользуются своим всеведением, другой - убирать всеведение и просто предполагать, что неизведанная местность проходима.Это может привести к тому, что юниты попадут в тупики, иногда те, которые очевидны для игрока, пока они наконец не исследуют путь к цели.
Туман войны - еще один аспект этого.Например, в StarCraft 2 на карте есть разрушаемые препятствия.Было показано, что вы можете отдать приказ юниту перемещаться на вражескую базу, и он начнет двигаться по другому пути, если препятствие уже было уничтожено вашим противником, что дает вам информацию, которой вы на самом деле не должны иметь.
Подводя итог: Вы можете использовать стандартные алгоритмы, но, возможно, вам придется использовать их умно.И в качестве последнего бонуса: я нашел Информацию о программировании игры Амит интересной в отношении путей.Здесь также есть ссылки на дальнейшее обсуждение проблемы.