Прежде всего, 100 юнитов не так уж много, поиск пути достаточно быстр на современных компьютерах, поэтому он не является большим приемником ресурсов.Даже в старых играх сделаны оптимизации, чтобы сделать его еще быстрее, и вы можете видеть, что юнит иногда теряется или застревает, чего не должно быть при общем алгоритме, таком как A *.
Если картане меняет карту, вы можете предварительно обработать ее, чтобы построить набор узлов, представляющих регионы карты.Например, если карта представляет собой два острова, соединенных узким мостом, будет три «региона» - остров 1, остров 2, мост.В действительности вы, вероятно, сделали бы это с помощью некоторого графового алгоритма, а не вручную.Например:
- Оценка каждой плитки с расстоянием до ближайшей непроходимой плитки.
- Поместите все смежные плитки с оценкой выше порога в той же области.
- Когда закончитепостепенно расширяйтесь из всех областей, чтобы охватить также плитки с низкими показателями.
- Создайте новый график, где каждое пересечение области-региона является узлом, и рассчитайте кратчайшие пути между ними.
Тогда ваш алгоритм поиска пути становится двухэтапным:
- Найти, в каком регионе находится юнит.
- Найти, в каком регионе находится цель.
- Если разные регионы, сначала вычислите кратчайший путь к целевой области, используя приведенный выше график региона.
- Находясь в той же области, обычно рассчитывайте путь на сетке плитки.
При перемещении между удаленными местоположениями,это должно быть намного быстрее, потому что теперь вы ищете через несколько узлов (на графике региона) плюс относительно небольшое количество плиток вместо сотенплитки, которые составляют эти регионы.Например, если у нас есть 3 острова A, B, C с мостами 1 и 2, соединяющими AB и BC соответственно, то единицам, перемещающимся из A в C, действительно не нужно каждый раз искать все B, они заботятся только о кратчайшем путиот моста 1 до моста 2. Если у вас много островов, это действительно может ускорить процесс.
Конечно, проблема в том, что регионы могут изменяться, например, из-за зданий, блокирующих путь, или из-за единиц, временно мешающихпроход.Решение этого зависит от вашего воображения.Вы можете попытаться аккуратно обновлять график региона при каждом изменении карты, если карта редко изменяется в вашей игре.Или вы можете просто позволить юнитам наивно доверять графу регионов, пока они не столкнутся с препятствием.В некоторых играх вы можете видеть особенно плохие случаи последнего, потому что отряд будет продолжать бежать в долину, даже после того, как он был огорожен, и только после удара о стену он повернет назад и обойдет вокруг.Я думаю, что у оригинального Starcraft была эта проблема, когда юниты блокировали узкий путь.Они будут пытаться сделать очень длинный обходной путь, вместо того чтобы ждать, пока толпа освободит мост.
Есть также алгоритмы, которые выполняют аналогичные оптимизации без явного построения графа региона, например, JPS примерно так работает.