Существует ли алгоритм объединения диапазона угроз с произвольным диапазоном перемещения на двумерной сетке?

Question

Существует ли алгоритм объединения диапазона угроз с произвольным диапазоном перемещения на двумерной сетке?

Я строю простую 2D-игру на основе сетки и ищу способ вычислить область "угрозы", которую каждый персонаж может оказать на игровое поле. Угрозу с текущей точки легко подсчитать - это красный бриллиант внизу. Но я собираюсь объединить эту информацию с произвольной областью "можно ходить здесь" (оранжевый).

Вместе алгоритм даст мне комбинацию всех тайлов, на которые мой персонаж может атаковать из всех доступных ходов и текущей позиции.

Конечно, я могу просто перебрать все возможные ходы, применить там форму ромба и создать набор всех квадратов угроз. Есть ли способ лучше?

4

algorithm map tile

Источник

user967484 17 дек '13 в 01:18

1 ответ

Решение

Другие вопросы по тегам algorithm map tile

user2726892 17 дек '13 в 02:11 2013-12-17 02:11 · Accepted Answer · 2013-12-17 02:11

Проблема, которую вы здесь решаете, аналогична 2D Convolution:

---------------     ---------------     -------XX------
-------X-------     ---------------     ------XXXX-----
------XXX------     -------XX------     -----XXXXXX----
-----XXXXX-----  *  ------XXX------  =  ----XXXXXXX----
------XXX------     --------X------     -----XXXXXX----
-------X-------     ---------------     ------XXXX-----
---------------     ---------------     --------X------

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