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

[crossposted from stackoverflow]

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

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

41 голос | спросил blankets 30 +04002010-10-30T20:19:13+04:00312010bEurope/MoscowSat, 30 Oct 2010 20:19:13 +0400 2010, 20:19:13

7 ответов


29

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

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

ответил Ari Patrick 31 +03002010-10-31T19:50:08+03:00312010bEurope/MoscowSun, 31 Oct 2010 19:50:08 +0300 2010, 19:50:08
16

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

ответил ZorbaTHut 30 +04002010-10-30T22:55:30+04:00312010bEurope/MoscowSat, 30 Oct 2010 22:55:30 +0400 2010, 22:55:30
7

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

ответил phillipwei 24 32010vEurope/Moscow11bEurope/MoscowWed, 24 Nov 2010 20:04:37 +0300 2010, 20:04:37
2

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

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

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

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

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

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

ответил BerggreenDK 8 12010vEurope/Moscow11bEurope/MoscowMon, 08 Nov 2010 05:05:53 +0300 2010, 05:05:53
1

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

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

ответил Bryan Harrington 30 +04002010-10-30T20:58:54+04:00312010bEurope/MoscowSat, 30 Oct 2010 20:58:54 +0400 2010, 20:58:54
1

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

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

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

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

  • есть ли в некоторых из этих игр исходный код.
  • есть ли у некоторых клонов этих игр исходный код.
  • Не подскажете ли SDK или редакторы что-то.
  • спросите у работодателей компаний, делающих эти игры, некоторые из них могут быть готовы поделиться.
ответил user712092 30 J000000Saturday11 2011, 10:02:53
0

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

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

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

ответил AkiRoss 31 +03002010-10-31T13:16:47+03:00312010bEurope/MoscowSun, 31 Oct 2010 13:16:47 +0300 2010, 13:16:47

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132