В такой игре, как Warcraft 3 или Age of Empires, способы, которыми противник AI может перемещаться по карте, кажутся почти безграничными. Карты огромны, и положение других игроков постоянно меняется.
Как работает поиск путей AI в таких играх? Стандартные методы поиска графа (такие как DFS, BFS или *) кажутся невозможными в такой настройке.
Возьмите с солью соль, потому что у меня нет опыта общения с человеком.
При этом, вероятно, будут разные подходы, но я считаю, что стандартные стратегические методы поиска, особенно (варианты) A *, вполне разумны для стратегических игр. Большинство игр, которые я знаю, похоже, основаны на системе черепицы, где карта состоит из маленьких квадратов, которые легко сопоставляются с графиком. В качестве примера можно привести StarCraft II (Снимок экрана), который я буду использовать в качестве примера в оставшейся части ответа, потому что я наиболее знакомы с ним.
В то время как A * может использоваться для игр в режиме реального времени, есть несколько недостатков, которые необходимо преодолеть с помощью настроек основного алгоритма:
A * слишком медленно
Так как RTS определяется определением "в реальном времени", ожидая завершения вычисления, это сломает игрока, потому что единицы будут отставать. Это можно устранить несколькими способами. Один из них - использовать многоуровневый A *, который вычисляет грубый курс, прежде чем принимать во внимание меньшие препятствия. Еще одна очевидная оптимизация заключается в том, чтобы группировать единицы, направляющиеся к одному месту назначения, в взвод и только вычислять один путь для всех из них.
Вместо наивного подхода к созданию каждой плитки a node на графике можно было бы построить навигационную сетку которая имеет меньше узлов и может быть быстрее поиск - для этого требуется немного изменить алгоритм поиска, но он все равно будет A * в ядре.
A * является статическим
A * работает на статическом графике, так что делать, когда меняется пейзаж? Я не знаю, как это делается в реальных играх, но я предполагаю, что путь повторяется неоднократно, чтобы справиться с новыми препятствиями или устранить препятствия. Возможно, они используют инкрементную версию A * (PDF).
Чтобы увидеть демонстрацию StarCraft II, справившись с этим, перейдите к 7:50 в это видео.
A * имеет отличную информацию
Часть многих игр RTS - неизведанная местность. Поскольку вы не можете видеть местность, ваши подразделения не должны знать, где ходить, но часто они все равно. Один из подходов состоит в том, чтобы оштрафовать прогулку по неизведанному ландшафту, поэтому подразделения более неохотно используют все свое всеведение, а другое - вывести всезнание и просто предположить, что неизведанный ландшафт можно ходить. Это может привести к тому, что подразделения спотыкаются в тупик, иногда те, которые очевидны для игрока, пока они, наконец, не исследуют путь к цели.
Туман войны - еще один аспект этого. Например, в StarCraft 2 на карте имеются разрушаемые препятствия. Было показано, что вы можете заказать подразделение, чтобы перейти на базу противника, и он начнет идти по другому пути, если препятствие уже уничтожено вашим противником, таким образом предоставив вам информацию, которую вы фактически не должны иметь.
Подводя итог: вы можете использовать стандартные алгоритмы, но вам, возможно, придется использовать их с умом. И в качестве последнего бонуса: я нашел Amits Game Information Information, интересный в отношении путей. Он также имеет ссылки на дальнейшее обсуждение проблемы.
Это немного простой пример, но он показывает, что вы можете создать иллюзию AI/Indepth Pathfinding из некомплексного набора правил: Pac-Man Pathfinding
По существу, AI может знать местную (рядом) информацию и принимать решения на основе этих знаний.
A * - общий алгоритм поиска пути. Это популярная тема разработки игр - вы можете найти множество книг и веб-сайтов, содержащих информацию.
Проверьте графики видимости. Я считаю, что это то, что они используют для поиска путей.