Поиск возможных ходов для сущности в двумерной мозаичной игре

10

У меня возникают проблемы с определением конкретного поискового запроса, но как найти возможные ходы в 2D пошаговой стратегии (например, FF: Tactics, Fire Emblem, Advance Wars).

введите описание изображения здесь

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

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

Просто интересно, может ли кто-нибудь указать мне правильное направление (то есть название алгоритмов, техники, статей и т. Д.).

NRaf
источник
Я думаю, что это называется поиск пути, для поискового запроса? Если вы используете поиск пути, то у вас могут быть счетчики для обработки того, что вам нужно
Exikle
По сути, это часть поиска пути (вычисление метаданных для затрат на перемещение). Вы определяете только те места, которые находятся в пределах досягаемости, но вы также не обязательно определяете маршрут, по которому будете идти.
Марио
1
Это не в реальном времени (RTS), если это пошаговая а-ля FFTactics. : p
Alayric
В 2d вы можете использовать расчет Таксикаба / Манхэттена. En.wikipedia.org/wiki/Taxicab_geometry
Гербен Джейкобс,

Ответы:

5

Я думаю, что ограниченная Dijkstra это именно то, что вы хотите использовать. Способ, которым Дейкстра находит расстояние между двумя точками, заключается в том, что он отображает расстояние до каждого узла от исходного узла, а затем «выбирает» кратчайший путь из этой карты расстояний. Вы хотите сделать практически то же самое, за исключением того, что вам нужен график узла расстояния, который он создает в качестве выходного, а не путь к какой-либо конкретной точке.

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

Виола.

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

TASagent
источник
Я думаю, что Дейкстры в этом случае излишни. ОП не нужен путь ко всем возможным направлениям перемещения, просто ответ да / нет о том, может ли агент туда добраться. Он может вычислить путь позже, как только пользователь выберет его.
Михаил Кристофик
Стоимость использования алгоритма Дейкстры для расчета пути после определения пункта назначения практически такая же, как и при его использовании заранее (если только вы не используете эвристический подход, такой как A *, для маршрутизации). Если вы не сделаете это заранее, это создаст лишнюю работу, так как Дейкстра ответит на вопросы «куда мне идти» и «как туда добраться?». Это также позволяет добавлять в среду усложнения, которые изменяют стоимость перемещения, хотя это может быть ненужным для приложения. Кроме того, подход хорошо документирован, что полезно для исполнителя.
TASagent
1
Просматривая ответ Марио, он фактически описывает алгоритм Дейкстры, за исключением того, что он инвертирует расстояние и не упоминает, что это Дейкстра.
TASagent
1
Не сказал бы, что это Дейкстра, потому что вы на самом деле не ищете кратчайшего пути и не пытаетесь достичь какой-то конкретной точки. По сути, это первая часть алгоритма Дейкстры, правда. Проблема с вашей формулировкой, использующей Дейкстру, может вводить в заблуждение, и я думаю, что это также смутило Майкла. Он, вероятно, подумал, что вы предлагаете использовать Дейкстру один раз для каждого поля / ячейки.
Марио
1
Заканчивая использование этого подхода, он хорошо работал и его очень легко расширить для преодоления препятствий.
NRaf
12

Самый простой (и, вероятно, самый наивный) подход, который я могу придумать прямо сейчас:

  • Начните с вашего персонажа и отметьте все окружающие поля как steps - 1.
  • Выполните итерацию по всем вновь отмеченным полям и снова пометьте окружающие их поля как места, steps - 1где stepsбудет номер шага текущего поля, если только у нового поля нет уже более высокого номера.
  • Повторяйте последний шаг, пока у вас не закончатся шаги.
Марио
источник
1
Этот алгоритм имеет название: Flood Fill .
Майкл Кристофик
6
@MichaelKristofik: я бы назвал это поиском в ширину . Заливка не отслеживает расстояния.
BlueRaja - Дэнни Пфлугхофт
2

Я думаю, что вы ищете, может быть Манхэттен Расстояние . При условии отсутствия препятствий, вы можете сказать, что квадрат достижим просто, если:

| Tox-fromX | + | toY-fromY | <maxMoveDistance

Этот алгоритм может быть неправильным направлением, если позже у вас будут препятствия; Один из возможных способов его адаптации может заключаться в том, чтобы препятствия отбрасывали «тени» и переоценивали их с ближайшей точки.

РЕДАКТИРОВАТЬ (потому что у меня есть немного больше свободного времени сейчас):

Под «тенями» я подразумеваю что-то вроде этого, если 0 - достижимый квадрат, C - символ, а X - препятствие:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Поскольку (5, 2) является препятствием, вы начинаете с предположения, что не можете ничего достичь с x> = 5 AND y <= 2. Затем вы можете пересчитать из другого квадрата; если вы хотите перейти к (5, 1), вы можете рассчитать манхэттенское расстояние от (4, 1) и посмотреть, меньше ли это + расстояние от персонажа до (4, 1), чем расстояние перемещения игрока.

Это довольно тривиальный пример, но если у вас есть несколько препятствий и / или немного больший диапазон перемещения, он должен справиться со сложностью.

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

Оловянный человек
источник
Что вы имеете в виду, бросая тени?
NRaf
1
Отредактировано для уточнения.
Жестянщик,