Я пытался выяснить, как реализовать что-то вроде поиска пути в Starcraft 2. Мне не нужны все сложные функции, такие как флокирование, организация очередей и т. Д. На самом деле мне нравится, как в Starcraft 1 юниты будут мешать друг другу. Другой. Но я хочу, чтобы поиск путей был лучше, чем в Starcraft 1.
Из поисков Google, которые я сделал, различные ответы имеют какое-то отношение к A * над сеткой навигации и / или имеют дело с неким «графом видимости». Но я получил несколько противоречивые или неясные ответы о том, что я должен делать.
Одна вещь, о которой я читал, имеет отношение к выполнению A * над вершинами треугольной сетки (навигационной сетки). А потом как-то «выправляет путь», что я не знаю, как сделать. Но это не гарантирует оптимальность, верно?
Другой вопрос, который у меня возник, заключается в том, как поиск путей в Starcraft 2 связан с тем, что юниты - это диски с конечным радиусом, а не точки при работе с углами? И как справляться с динамическими препятствиями, такими как неработающие юниты или даже другие движущиеся юниты.
Я ищу некоторые подробные подробные объяснения, а не общие обзоры сверхвысокого уровня, типичные для результатов поиска.
Если это имеет значение, я уже посмотрел заметки Амита о поиске пути . Я слышал, но не читал вычислительную геометрию: алгоритмы и приложения . А в блоге о презентации навигации AI на GDC 2011 упоминается, что Starcraft 2 использует ограниченную триангуляцию Делоне для навигационной сетки. Хотя в сообщении блога упоминается управление Boids и «анализ горизонта», в нем не упоминается, как именно выполняется поиск пути к ядру в navmesh.
источник
Ответы:
Если у вас установлен Starcraft 2, откройте редактор карт и переключите поиск пути . Вы сможете увидеть, как строится навигационная сетка, размещая здания и другие препятствия вокруг.
Не должно быть проблемой - поиск маршрута в Starcraft 1 был глупым. Это сообщение в блоге одного из программистов рассказывает об этом.
Речь идет о том, чтобы сделать ИИ не тупым более чем оптимальным. Ваши юниты заканчивают зигзагообразным движением между узлами, если вы не применяете немного сглаживания.
При планировании пути у вас будет этап уточнения, на котором вы увидите, через какие узлы вашему подразделению нужно пройти, чтобы достичь своей цели, а затем вы начнете извлекать лишние узлы в середине пути, которые нам не нужны следовать, то есть мы можем напрямую перейти от узла A к узлу C через B без статических коллизий, поэтому полностью игнорируем B.
Это в конечном итоге выправляет путь.
Если вы хотите получить четкое объяснение, это уже хорошо описано в книгах (даже с рабочим кодом игры). Так что, если у вас есть деньги, чтобы сжечь, проверьте Программирование AI игры на примере и / или Искусственный интеллект для игр . Они оба обсуждают эти темы очень глубоко.
источник