Эффективный поиск пути в свободном пространстве

У меня есть игра, расположенная в космосе, и я хотел бы издавать приказы о перемещении, которые требуют поиска пути. Теперь я понимаю, что A * и такие в основном применяются к деревьям, а не к пустому пространству, в котором нет узлов для поиска пути. У меня есть некоторые препятствия, которые в настоящее время выражаются в виде фиксированных AABB, то есть, нет неограниченных «ландшафтных» препятствий. Кроме того, я ожидаю, что большинство препятствий будут разумно приближаться как кубы или сферы.

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

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

Будут ли потенциальные поля достигать разумного приближения с учетом моих параметров, или мне нужно другое решение?

Хотя потенциальные поля могут работать, я думаю, у вас будут проблемы с неоптимальными путями и «локальными минимумами», где ваши юниты будут захвачены окружающими препятствиями. A * подходит для 3D открытого пространства. Это просто становится проблемой создания навигационной сетки, которая соответствует вашим потребностям. Вы даже можете использовать структуры, такие как Octrees, для навигационных узлов. Чем меньше максимальный размер каждого октанта, тем ровнее путь. Ознакомьтесь с этой статьей из игр Face to Face (теперь не существует, добавлена ​​ссылка на обратную дорогу). A * в сочетании с оптимизацией пути (например, ярлыками прямой видимости) и поведением рулевого управления, и вам будет хорошо! Посмотрите на изображение ниже как пример использования октодерева для узлов пути: