Is there an algorithm for combining threat range with arbitrary move range on 2D grid?

Question

I'm building a simple 2D grid based game and am looking for a way to calculate the "threat" area that each character can exert on the game board. Threat from the current spot is easy to calculate - this is the red diamond below. But I'm looking to combine this information with an arbitrary "can walk here" area (orange).

Together the algorithm will give me a combination of all tiles that my character can attack from all available moves and current position.

Of course I can just iterate over all possible moves, apply the diamond shape there and create a set of all threat squares. Is there a better way?

Answer 1

The problem you are solving here is analogous to 2D Convolution:

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

In your case where an element is only either covered or uncovered (versus containing a scalar or vector value), this reduces to the Dilation operation in morphology. There are many papers and code samples on efficient implementations of dilation - this one looks particularly applicable to your problem.