Как работает поиск пути в играх RTS?

42

[перекрестно размещено из stackoverflow]

В такой игре, как Warcraft 3 или Age of Empires, способы, с помощью которых противник ИИ может перемещаться по карте, кажутся практически безграничными. Карты огромны, и положение других игроков постоянно меняется.

Как работает поиск искусственного интеллекта в играх, подобных этим? Стандартные методы поиска в графе (такие как DFS, BFS или A *) кажутся невозможными в такой установке.

одеяла
источник
2
Почему A * не работает на этом графике?
user712092
Связанный блог: ai-blog.net/archives/000152.html
tenfour
1
@tenfour, ссылка сейчас не работает.
Монреаль

Ответы:

29

В большинстве случаев использование A * над сеткой навигации (обычно называемой «navmesh») является решением для поиска пути, используемым в коммерческих RTS. Существует подробное объяснение того , как navmeshes работают, почему они являются лучшим решением , чем системы маршрутных точек, а также ссылки на ресурсы реализации, здесь .

Если вы планируете разрабатывать специальные игровые режимы (захват точек / узлов) или юниты, которые патрулируют, укрываются и т. Д., Вы, вероятно, захотите внедрить слой путевых точек поверх вашей навигационной сетки, чтобы контролировать поведение ИИ (а не поиск пути ).

Ари Патрик
источник
17

Ознакомьтесь с алгоритмом Flowfield , используемым в Supreme Commander 2. Он работает намного лучше, чем большинство систем поиска путей RTS (для нескольких примеров перейдите к 0:50).

ZorbaTHut
источник
4
это действительно классная демонстрация, но ничего не говорит мне о самой реализации
MetaGuru 30.10.10
4
Они упоминаются в одном предложении - оно основано на исследовании массового потока в UW, которое вы можете найти по адресу grail.cs.washington.edu/projects/crowd-flows .
Алгоритм поля потока кажется довольно интересным, и определенно, по-видимому, выполняет лучшую работу по сравнению с большинством алгоритмов, но мне хотелось бы, чтобы была общедоступная документация о том, как работает сама система, а не только о том, как система основана на ее работе. Естественно, разработчикам нужно задать много вопросов, прежде чем внедрять такую ​​систему, как эта, но в этом случае кажется, что единственный способ ответить на эти вопросы - это сначала внедрить систему. :(
Ари Патрик
2
@Kragen: вам действительно нужны только две единицы, прежде чем простая A * (особенно путевая точка) заставит их сталкиваться друг с другом снова и снова, и вам нужна какая-то система, чтобы обойти ее.
5
Основываясь на видео, поиск путей в Starcraft 2 выглядит следующим образом. Использует ли SC2 поле потока?
Крис Буй
7

Многие старые игры используют A *. Оригинальный Starcraft использовал A *; что привело к некоторым проблемам при столкновении. Starcraft 2 очень хорошо справляется с столкновением, используя поведение слипания / скопления, чтобы поддерживать контроль над большими группами. В этой статье Gamedev обсуждается, как это может быть достигнуто.

phillipwei
источник
2

Я согласен с другими ответами ей уже, но также, попытаться думать о WoW / Warcraft3 как о реальных 2D мирах. Они ничем не отличаются от плиточных, это просто плитки.

Вы могли бы также подумать о том, как GPS находит лучший путь? Есть множество алгоритмов для поиска пути по связанным картам.

Я думаю, что некоторые из первых скриптов «Quake-ботов» также могут помочь вам, так как они были разработаны для работы в «неизвестных областях», потому что мы могли создавать свои собственные уровни с нуля.

В общем, мой личный способ иметь дело с такой картой - думать о ней как о поиске пути A *. Но сначала я бы предварительно вычислил каждую «точку плитки» и проиндексировал все это «ближайшим соседом» и т. Д. Затем, когда объекту нужно было перейти от А к В, просто поискать в В, посмотреть, к чему он подключен, и повторять до тех пор, пока вы достичь цели.

В зависимости от типа игры и ландшафта / сценария могут быть полезны различные тактики предварительного сканирования. В некоторых играх очень мало препятствий, и это может быть движение "по прямой линии" + некоторые "как мне передвигаться" для объектов.

Надеюсь, что это имеет немного смысла и, возможно, дал вам некоторые мысли для работы.

BerggreenDK
источник
1

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

Вы заметите это в Starcraft 2, где зерглинги, очевидно, не совсем хорошо идут, это было бы кошмаром для процессора, чтобы сделать это для зерглингов. Они просто делают все возможное, чтобы добраться от А до Б и даже не пытаются найти лучший путь. Они подойдут как можно ближе к горлышку бутылки у дросселей или пандусов.

Брайан Харрингтон
источник
1

Карта - это сетка. Сетка - это график. A * работает на графике, это алгоритм поиска графиков. A * должен искать несколько узлов графа.

Как уже упоминалось, они могут использовать навигационную сетку. Но A * (или что-то подобное) будет в любом случае поверх этой сетки, потому что полигоны этой сетки являются просто узлами графа; * Затем будет искать путь от одного полигона к другому.

Не уверен насчет Warcraft или коммерческих игр, но есть также метод, называемый Collaborative Diffusion, и он очень прост; это обычно делается на сетке. Существует также методика, называемая Потенциальные поля , которая очень похожа на предыдущую, если не идентична.

Вы также можете попробовать:

  • есть ли у некоторых из этих игр доступный исходный код
  • есть ли у некоторых клонов этих игр доступный источник
  • SDK или редакторы ничего не намекают
  • Спросите работодателей компаний, производящих эти игры, некоторые из них могли бы поделиться
user712092
источник
0

Я совершенно не опытный, но я думаю, что хорошее решение основано на эвристике, а не на полной проверке известной карты. Эвристика, о которой я могу думать, основана на местном уровне и основана на опыте. Местное управление может основываться на локальной проверке местности и препятствиях, продолжая двигаться в требуемом направлении. Я думаю, что большинство карт не требуют сложных движений, похожих на лабиринт, но довольно тесно связаны. Другой эвристикой является использование предыдущих известных путей (исследованных другими единицами или явно пользователем) для перемещения единиц в известные или почти известные позиции. Но я говорю о перемещении на больших картах, а не в закрытых пространствах, как сказал ZorbaTHut. В многолюдных случаях алгоритм может быть более сложным, требующим своего рода «прогнозирования», координации между подразделениями одной команды или просто семафороподобных стратегий ожидания. Также,

Я думаю, что эвристические алгоритмы хороши, потому что они обычно обеспечивают хорошее решение на больших пространствах с разумным временем вычисления (что имеет значение, когда вы перемещаете много единиц).

Извините, если это общий ответ: я работал с толпами, но пространство было довольно своеобразным, и я не могу объяснить, как именно работает алгоритм (во всяком случае, на основе агентов, а не на глобальном уровне). Я надеюсь, что вы можете получить некоторые полезные идеи из моего ответа.

AkiRoss
источник
Мммм, интересно, что не так в том, что я сказал ... Было слишком сложно написать комментарий?
AkiRoss
Кстати, я хотел бы подчеркнуть, что A * использует эвристический подход. Спасибо за -2.
AkiRoss
Ваш ответ равняется «Дитч А * и все такое». Это может быть началом для разумного ответа, но вы предоставляете очень мало информации, кроме предложения. Похоже, причина отрицательного голосования заключается в том, что вы не даете понять, насколько сложно будет реализовать ваше решение. Я не сомневаюсь, что супер-гений, которому дано неограниченное время, может передать код / ​​настроить алгоритм маршрутизации для данной RTS, который будет лучше, чем A * в навигационной сетке. Но «гений» и «безграничность» очень трудно найти.
deft_code
О верно. Я думал, что парень хотел получить общий ответ, так как он не спрашивал, как его сделать, а как они вообще работают. Во всяком случае, я не эксперт, как я сказал: я просто давал некоторую информацию о решениях, которые я знаю, об исследовании больших пространств в общем приложении IA. Спасибо за ваш комментарий.
AkiRoss