Алгоритм нахождения мест для атаки цели в зоне атаки-движения на игровой доске 2D-сетки
Я ищу имя алгоритма или реализацию, которая может дать мне правильные позиции из списка допустимых ходов, из которых я могу атаковать заданную цель.
У меня есть двухмерная карта тайлов и герой, который может перемещать определенное количество ходов и атаковать врага на расстоянии. Из-за препятствий на карте область движения героя меняется и может иметь дыры в ней:
В этом вопросе я узнал, как объединить эту область движения с областью атаки, чтобы получить общий диапазон "угрозы", который мой герой оказывает на игровое поле. В этом случае 2 врага находятся в пределах досягаемости и могут быть атакованы:
Я ищу имя или информацию об обобщенном алгоритме, который будет принимать:
- Зона угрозы (желтая)
- Допустимые ходы (оранжевый)
- Целевая позиция (зеленая)
И вернуть все клетки в оранжевой области, из которых я могу атаковать данную цель. Поскольку враги создают собственную зону угрозы, мне не обязательно нужен ближайший квадрат - я буду изучать возможные ходы и выбираю тот, с которым мой герой подвергнется наименьшей угрозе для атаки.
2 ответа
Вот как я думаю, что проблема может быть решена:
1) Найти угрозу героя (ход + квадраты атаки)
Для каждой цели в зоне угрозы сделайте следующее:
2) Для каждого квадрата в действительных ходах вычислите расстояние Манхэттена до конкретной цели
3) Если квадрат (расстояние <= дальность атаки) И находится в пределах допустимых ходов, герой может атаковать цель из этого квадрата
В моем конкретном случае я позволяю героям ближнего боя атаковать все 8 квадратов вокруг них (связь 8), поэтому они будут вести себя как король в шахматах и вместо манхэттенского расстояния будут вычислять расстояние Чебушева
Ваш набор доступных героев HERO известен. Вокруг каждой из этих плиток находится ЗОНА УГРОЗЫ, которая похожа на (выпуклый?) Многоугольник (алмаз?). Позицию противника можно было бы тогда рассматривать как еще один выпуклый многоугольник (в данном случае квадрат). В общем случае вы хотели бы проверить, пересекаются ли эти многоугольники, да?
К сожалению, кажется, что эта общая проблема сложнее, чем можно было бы надеяться.
Возможно, нам повезет больше, если мы обнаружим, что ваша проблема имеет некоторые особые свойства. Если область угрозы вашего HERO всегда выпуклая, вы можете выполнить внутренний / внешний тест, используя границу ромба (что-то похожее на тест bounded_side_2 CGAL)
Если вы обнаружите, что подход НЕ достаточно хорош, то вот что вы можете сделать: предварительно сгенерируйте набор "атакующих позиций" для доски; каждая ячейка знает множество других ячеек, на которые может напасть HERO. Это компромисс между временем и пространством, и если у вас нет больших ограничений памяти или движущихся препятствий, то он должен работать очень хорошо.