Итоги и оптимизация
Существует множество других вещей, которые следует учесть в вашем коде поиска пути. Поработайте над упомянутыми ниже моментами, чтобы превратить заготовку аггоритма поиска пути в готовое к выпуску изделие.
- Выполняя поиск среди открытых узлов, начинайте его с тех узлов, которые расположены ближе к цели. Во многих случаях это поможет сократить количество узлов, которые требуется просмотреть при поиске пути.
- Не помещайте другие подразделения на карту препятствий. Если вы поступите так, перемещения подразделений могут вызвать проблемы. Одно из возможных решений состоит в том, чтобы при поиске пути не учитывать другие подразделения и в случае столкновения с другим подразделением заново рассчитывать путь. Если подразделения не блокируют друг друга, это не требуется.
- Используйте диспетчер путей для управления фиксированным пулом путей. Если вы используете пул путей, это поможет вам сократить нагрузку на процессор, вызванную необходимостью динамического формирования каждого пути.
- Используйте многоуровневый поиск пути. Для этого применяйте крупномасштабную карту препятствий, каждый узел которой соответствует нескольким блокам обычной карты, что позволит маневрировать среди больших ландшафтных препятствий. Как только подразделение достигнет более сложной области, переключитесь на карту препятствий более мелкого масштаба с большим количеством узлов. Многоуровневый поиск пути может значительно ускорить работу кода.
- Никогда не вычисляйте перемещение всех подразделений сразу. Создайте очередь путей и вычисляйте на каждом такте игры пути для небольшого числа подразделений.
- Если в вашей игре разворот подразделений занимает какое-то время, добавьте к вычислениям общей стоимости каждого узла карты стоимость смены направления движения. Это позволит выбирать для подразделений наиболее эффективный путь с наименьшим количеством поворотов. Кроме того, вы можете сделать ряд других подобных дополнений к стоимости узла карты. Например, вы можете увеличить стоимость узлов, расположенных рядом со вражескими позициями, чтобы предотвратить случайное вступление ваших подразделений в бой!
- Алгоритм А* работает на картах различных типов, в том числе и на тех, где форма блоков отличается от квадратной. Испытайте его на картах с шестиугольными блоками или даже на маршрутных картах.
Содержание раздела