* Алгоритм для тактических ролевых игр?

15

Я возился с написанием действительно плохой тактической RPG на C ++. Пока у меня есть 2D-карта тайлов, и я только что получил алгоритм A *, основанный на псевдокоде в википедии .

Но настоящие тактические РПГ не просто находят лучший путь на плоской плоскости и двигаются туда. Они обычно имеют ограниченные диапазоны перемещения и должны подниматься или опускаться. Если вы когда-либо играли в Final Fantasy Tactics, на них повлияла бы статистика Move и Jump. Это где я заблудился. Как я могу изменить алгоритм A *, чтобы он нашел лучший путь к цели, но этот путь занимает только столько плиток? Как я должен принимать во внимание разницу в высоте и прыгать статистику? Как мне реализовать перепрыгивание через пробел?

Если это поможет, сейчас моя карта представлена ​​объектами Vector of Tile. Каждая плитка имеет указатели на плитку «Север», «Юг», «Восток» и «Запад», которые устанавливаются в nullptr, если там нет плитки, например, вдоль края карты или если мозаика установлена ​​в непроходимую.

user137
источник
5
Я не знаю, почему диапазон перемещения является проблемой. Найдите кратчайший путь, а затем переместите квадраты скорости по этому пути.
Mooing Duck

Ответы:

33

Восхождение и разрывы - это просто разные функции стоимости. Для юнита, который может прыгнуть, разрыв имеет нормальную (?) Стоимость, в то время как для непрыгающего юнита он имеет произвольно высокую стоимость. Восхождение стоит дороже, так же как и сложный рельеф и т. Д. Алгоритм A * вполне способен обрабатывать функции стоимости, поэтому, если ваша реализация еще этого не делает, просто обратитесь к Google, чтобы узнать, как реализовать A * с помощью функции стоимости.

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

Джек Эйдли
источник
10
Хорошие замечания по поводу «тактического позиционирования», но эти решения могут применяться на уровне выше, чем базовый поиск пути. С другой стороны, применение затрат к узлам в алгоритме поиска пути, которые генерируются каким-то тактическим анализатором, может быть хорошим вариантом. Например, если враг имеет линию прямой видимости с местностью, то создание узлов на этой местности будет очень дорогостоящим.
DrMcCleod
1
@DrMcCleod: Действительно, и это то, что я имел в виду под «Или, точнее, это не полная история». Вы, конечно, могли бы использовать A * или другой алгоритм для выполнения части обработки, однако я думаю, что я бы избегал таких подходов, как попытка избежать отслеживаемых узлов из-за стоимости перемещения, поскольку перемещение по местности, где юнит может попасть под огонь, лучше обрабатывать как расчет риска / вознаграждения, ИМО.
Джек Эйдли
13

Если вам нужны все возможные варианты движения юнита, используйте алгоритм Дейкстры .

Разница между A * и Dijkstra заключается в том, что Dijkstra предоставляет вам все возможные кратчайшие маршруты, достижимые при заданной стоимости, и, если ни один из них еще не достигает пункта назначения, он увеличивает стоимость на один и продолжается. A *, с другой стороны, предпочитает сначала рассчитывать те маршруты, которые имеют хороший шанс добраться до пункта назначения.

Поэтому, когда вы просто хотите кратчайший путь из точки А в точку Б, тогда A * - хороший выбор. Но если вам нужны все возможные варианты движения и кратчайший путь к каждому из них, то Dijkstra - именно то, что вам нужно.

Все, что вам нужно сделать, это запустить Алгоритм Дейкста без определенного узла назначения, но с максимальной стоимостью, которую нельзя превышать (диапазон движения юнита). При поездке на узел будет превышать максимальную стоимость, не посещайте его. Когда алгоритм завершается из-за отсутствия невидимых ребер, каждый узел в посещаемом наборе является возможным местом назначения, а маркеры предыдущих узлов узлов образуют связанный список, представляющий путь назад к начальному узлу.

Что касается прыжков: они могут быть представлены как еще одно ребро в A * и Dijkstra. Они могут иметь такую ​​же стоимость, что и обход обычного ребра или другого. Вы также можете передать параметр «jump_height» в алгоритм, который указывает алгоритму игнорировать края перехода, превышающие заданную высоту.

Philipp
источник
9
Здесь стоит упомянуть, что A*на самом деле это просто обобщение Дейкстры, поэтому, если вы понимаете одно, не должно быть слишком сложно понять другое.
Куб
8
Действительно, если у вас есть эвристика, которая просто возвращает 0 в вашем алгоритме A *, поздравляем! Вы только что написали алгоритм Дейкстры.
Янн
9
«Dijkstra дает вам все возможные кратчайшие маршруты, достижимые при заданной стоимости, и если ни один из них еще не достигает вашего пункта назначения, он увеличивает стоимость на единицу и продолжается» - это не то, как он работает, и что он выводит. На самом деле это просто обобщение поиска в ширину для взвешенных графиков. Он находит единственный кратчайший путь. A * - это всего лишь обобщение этого, когда у вас есть дистанционная эвристика.
BlueRaja - Дэнни Пфлугхофт
1
Не уверен, почему это так проголосовало. С прагматической точки зрения Дейкстра устарела. Он преподается в CS по образовательным и историческим причинам. Даже A * устарел для серьезной работы; Карты Google, конечно, не используют его. Вы бы сейчас посмотрели варианты ArcGraph.
MSalters
2
@MSalters Dijkstra и A * - прекрасные алгоритмы для простых задач, таких как тактические RPG. Существует очень узкий диапазон допустимых перемещений (плиток) и очень ограниченное количество способов перемещения по упомянутым плиткам (ортогональные, иногда диагональные) и обычно довольно короткий максимальный путь: SQRT (ArenaWidth² * ArenaHeight²). В вычислительном отношении разница незначительна на современных машинах для того, что, вероятно, довольно мало значений, так зачем беспокоиться о более сложной реализации, когда простой достаточно для целей, описанных здесь?
Valthek
2

Другие ответы содержат полезную информацию, поэтому обязательно прочитайте их.

Однако, чтобы ответить на ваш вопрос: на основе псевдокода, с которым вы связались, у вас есть какая-то функция, в heuristic_cost_estimateкоторой вы рассчитываете стоимость от tileA до tileB (при условии, что они смежны). Вместо того, чтобы использовать квартиру (1) для этой стоимости, вы должны будете настроить ее так, чтобы она включала статистику плиток и статистику юнитов и, возможно, статистику краев.

Например:

if (edge == JUMP && !unit.canJump()) 
    return INF;
if (tile.Type == Forest && unit.moveType == HORSE) 
    return 2;
//Other cases here
//-----
else 
    return 1;

Это даст вам ваш путь. Затем вы просто перемещаете юнит вдоль их пути, потребляя точки движения, и останавливаете его, когда оставшиеся точки <edgeCost. Обратите внимание, что это может быть не совсем оптимальным, если вы в конечном итоге с остаточным количеством очков = 1, но это должно быть достаточно для практической RPG. В действительности, вы бы хотели больше тактики, как указал Джек Эйдли!

Задача:
Если вы хотите стать более продвинутым, вы, вероятно, захотите использовать Djikstras, как предложено, чтобы найти все пробелы в пределах расстояния X, тогда вы хотите оценить каждый пробел в этом списке на «лучшее» место, основываясь на близости к цели, защите сила, вне зависимости от того, можете ли вы атаковать с этой позиции и т. д. На основании этой информации вы бы выбрали плитку, а затем переместились туда по пути, который вы только что рассчитали с помощью Djikstras.

Марс
источник
1

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

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

Хорошие симуляции сознательно не находят лучшего пути. Гораздо лучшим алгоритмом может быть иерархическое нахождение пути - если ничто иное, путем рисования прямой линии на карте и выбора 4-5 путевых точек, затем нахождение пути от одной путевой точки к другой с учетом только тех весов узлов, которые находятся на данный момент. известный, и установка всех остальных весов узлов равнодушными. Кроме того, вы можете сначала запустить A * на более грубой сетке, а затем найти путь от одного большого узла к следующему (но я предполагаю, что рисование линии на карте тоже очень хорошо).

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

Damon
источник
1
Имейте в виду, что «простой иерархический поиск пути» может выглядеть довольно глупо. Вы получаете единицы, идущие прямо к горному хребту, только чтобы обнаружить там, что путь заблокирован. Затем они прокладывают путь через горный перевал до следующей путевой точки, а оттуда до места назначения - даже если эта последняя путевая точка была для них далеко от курса. Предварительная обработка идентифицировала бы горный перевал впереди и указала бы путь туда. Но даже если вы этого не сделаете, если вы слишком далеко от запланированного курса, вы должны перепланировать оставшуюся часть.
MSalters
@MSalters: это может случиться с методом «нарисовать линию» даже после первой попытки, да. Это вряд ли произойдет более одного раза с грубым иерархическим методом сетки (который, например, принимает среднее значение, или медиану, или даже максимальное значение стоимости узлов внутри). Примерно так и будет играть человеческий противник - избегайте больших препятствий, о которых вы знаете или можете видеть издалека, как горная цепь, и в противном случае планируйте грубый, в основном прямой маршрут, и пробивайте себе дорогу. Если вы не знаете, что есть гора, вы идете прямо к ней.
Дэймон