4

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.

enter image description here

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?

Alex Stone
  • 46,408
  • 55
  • 231
  • 407
  • Can't you apply the diamond shape to the tiles that you know the player can walk to? You'll still have to do the "iterate over all possible" process but it'll significantly limit the tiles you have to parse. Unless I'm missing something – jraede Dec 17 '13 at 01:22
  • So, you really only have to worry about the edge moves, right? The outermost squares? After you draw the original diamond, iterate over all the "canMoveTo" squares, but instead of iterating through the entire diamond, just iterate through the border squares. – nhgrif Dec 17 '13 at 01:23
  • @nhgrif: No, because your move range might be longer than your weapon range. Checking only the border could leave a big hole in the middle of the displayed threat zone. – user2357112 Dec 17 '13 at 01:25
  • Not if you iterate over every tile the player can move to (after first doing the complete diamond for the original square), what you're saying would only happen if the was a empty space between where the player is and can move (like how a knight moves in chess) – nhgrif Dec 17 '13 at 01:27
  • @nhgrif: But your suggestion was to *not* iterate over every tile the player can move to. Your suggestion was to only iterate over the border of the movement range. Even if you include the unit's starting point, a unit with 10 move and attack range 1 would have a big ring-shaped hole in the computed threat zone. – user2357112 Dec 17 '13 at 01:28
  • No, iterate only over the border of the attack range and do this for every square the unit can move to. I mistyped. Fill in the entire attack range for the current square. Then iterate over every square the unit can move to, but iterate only over the border squares of the attack range. – nhgrif Dec 17 '13 at 01:29
  • Only the border of the attack range? It'd work given certain restrictions on how units can move, but it's entirely possible that, say, a unit can jump over a gap without being able to stop and attack in the middle, or a unit can move diagonally in a situation where vertical and horizontal moves are blocked by terrain. – user2357112 Dec 17 '13 at 01:32

1 Answers1

6

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.

MooseBoys
  • 6,641
  • 1
  • 19
  • 43