Как сделать поиск звездного корабля?

8

Я пытался выяснить, как реализовать что-то вроде поиска пути в Starcraft 2. Мне не нужны все сложные функции, такие как флокирование, организация очередей и т. Д. На самом деле мне нравится, как в Starcraft 1 юниты будут мешать друг другу. Другой. Но я хочу, чтобы поиск путей был лучше, чем в Starcraft 1.

Из поисков Google, которые я сделал, различные ответы имеют какое-то отношение к A * над сеткой навигации и / или имеют дело с неким «графом видимости». Но я получил несколько противоречивые или неясные ответы о том, что я должен делать.

Одна вещь, о которой я читал, имеет отношение к выполнению A * над вершинами треугольной сетки (навигационной сетки). А потом как-то «выправляет путь», что я не знаю, как сделать. Но это не гарантирует оптимальность, верно?

Другой вопрос, который у меня возник, заключается в том, как поиск путей в Starcraft 2 связан с тем, что юниты - это диски с конечным радиусом, а не точки при работе с углами? И как справляться с динамическими препятствиями, такими как неработающие юниты или даже другие движущиеся юниты.

Я ищу некоторые подробные подробные объяснения, а не общие обзоры сверхвысокого уровня, типичные для результатов поиска.

Если это имеет значение, я уже посмотрел заметки Амита о поиске пути . Я слышал, но не читал вычислительную геометрию: алгоритмы и приложения . А в блоге о презентации навигации AI на GDC 2011 упоминается, что Starcraft 2 использует ограниченную триангуляцию Делоне для навигационной сетки. Хотя в сообщении блога упоминается управление Boids и «анализ горизонта», в нем не упоминается, как именно выполняется поиск пути к ядру в navmesh.

user782220
источник
другие юниты просто сбиты с пути, вы увидите, как они сталкиваются друг с другом и скользят вдоль друг друга, пытаясь достичь следующей точки
трещотка
3
Я думаю, что на большинство ваших вопросов ответят, если вы посмотрите соответствующую колонку справа. Например: gamedev.stackexchange.com/questions/20392/… gamedev.stackexchange.com/questions/54361/… gamedev.stackexchange.com/questions/28041/… . В основном, немного больше исследований должно прояснить ситуацию для вас.
MichaelHouse

Ответы:

10

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

На самом деле мне нравится, как в Starcraft 1 юниты будут мешать друг другу. Но я хочу, чтобы поиск путей был лучше, чем в Starcraft 1.

Не должно быть проблемой - поиск маршрута в Starcraft 1 был глупым. Это сообщение в блоге одного из программистов рассказывает об этом.

Одна вещь, о которой я читал, имеет отношение к выполнению A * над вершинами треугольной сетки (навигационной сетки). А потом как-то «выправляет путь», что я не знаю, как сделать. Но это не гарантирует оптимальность, верно?

Речь идет о том, чтобы сделать ИИ не тупым более чем оптимальным. Ваши юниты заканчивают зигзагообразным движением между узлами, если вы не применяете немного сглаживания.

При планировании пути у вас будет этап уточнения, на котором вы увидите, через какие узлы вашему подразделению нужно пройти, чтобы достичь своей цели, а затем вы начнете извлекать лишние узлы в середине пути, которые нам не нужны следовать, то есть мы можем напрямую перейти от узла A к узлу C через B без статических коллизий, поэтому полностью игнорируем B.

Это в конечном итоге выправляет путь.

Я ищу некоторые подробные подробные объяснения, а не общие обзоры сверхвысокого уровня, типичные для результатов поиска.

Если вы хотите получить четкое объяснение, это уже хорошо описано в книгах (даже с рабочим кодом игры). Так что, если у вас есть деньги, чтобы сжечь, проверьте Программирование AI игры на примере и / или Искусственный интеллект для игр . Они оба обсуждают эти темы очень глубоко.

Йован
источник