Существуют ли алгоритмы поиска пути, которые бы обрабатывали разные типы движения?

12

Я разрабатываю бота для симулятора настольной игры BattleTech http://en.wikipedia.org/wiki/BattleTech , он пошаговый.

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

Я знаю только алгоритмы поиска путей Dijkstra и A *, но проблема в том, что есть 3 типа движений: ходить, бегать и прыгать по нескольким шестиугольникам (у каждого из них свои правила). Ходить и бегать практически одинаково.

Лучший путь может быть комбинацией или каждым типом движения. Вот пример карты http://megamek.info/sites/default/files/isometric_view.png

Знаете ли вы хороший алгоритм для этого сложного поиска пути или способ объединения результатов A * для каждого типа движения?

ai movement path-finding alexvisio
источник
Я думаю, что это часто решается с помощью некоторого умного манипулирования взвешенным путем с A * (вес является стоимостью этого пути / квадрата). Например, если прыжки предпочтительнее, они получают меньший вес (например, 5), чем ходьба (например, 10).
ashes999
Чем именно отличаются три типа движения? Можно ли их объединить (дойти до плитки A, затем бежать до B, а затем перейти к C в том же ходу)? Если да, каковы правила, которые запрещают игроку всегда использовать самый дешевый способ перехода из плитки A в плитку B?
Филипп
@ Филипп Да, они могут быть при использовании A *. Вы можете добавить каждую плитку, к которой вы можете перейти с каждым типом движения, в открытый список, затем, основываясь на цене каждого + хорошая эвристика, вы можете определить, какой из них будет развиваться дальше.
Акалтар
@ Филипп Нет, вы можете использовать только один тип хода каждый ход.
alexvisio
Ходить: двигаться через шестиугольники с небольшой разницей в высоте. Бег: то же самое, но вы можете пойти далеко, хотя вы будете генерировать тепло и терять точность стрельбы (так что это не всегда лучше). Прыжок: вы можете прыгать препятствия (стена или река) вместо того, чтобы ходить вокруг них.
alexvisio

Ответы:

10

И Dijkstra, и A * могут добавлять разные затраты к ребрам (= соединениям) от одной плитки к другой. Они также позволяют соединить два узла (= плитки) с более чем одним ребром, каждый из которых имеет свою стоимость.

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

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

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

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

Есть также еще один фактор при поиске пути, который вы должны учитывать: при некоторых условиях для робота может иметь смысл избегать окончания своего хода в определенных местах. Находясь в опасной зоне, использовать три поворота для перехода от А к В, но заканчивая каждый в укрытии, может быть лучше, чем использовать только два, но быть выставленным в конце каждого. А может и нет. Это зависит от обстоятельств и точной игровой механики. Опять же, это стратегическое решение, которое вы должны принять на основе эвристики. Вы можете представить это, добавив дополнительную стоимость к краям, которые заканчивают ход на опасном тайле, чтобы отговорить ИИ от этого хода.

Philipp
источник