Algorithm for finding spaces to attack target with

Question

I'm looking for an algorithm name or implementation that can give me valid positions from a list of valid moves from which I can attack a given target.

I have a 2D tile map and a hero who can move a certain number of moves and attack enemy at range. Because of obstacles on the map, hero's move area varies and can have holes in it:

In this question I have learned how to combine this move area with attack area to get the total "threat" range that my hero exerts on the game board. In this case, 2 enemies are within threat range and can be attacked:

I'm looking for a name or info on a generalized algorithm that will take :

• Threat area (yellow)
• Valid moves (orange)
• Target position (green)

And return all cells within orange area from which I can attack a given target. Because enemies exert a threat area of their own, I do not necessarily need the closest square - I will examine possible moves and pick the one with the least threat for my hero to move to for attacking.

Answer 1

Here's how I think the problem can be solved:

1) Find Hero's threat (move+attack squares)

For each target within threat area do following:

2) For each square in valid moves, calculate Manhattan distance to a particular target

3) If the (distance <= attack range) AND square is within valid moves, Hero can attack target from that square

In my particular case, I allow melee heroes to attack all 8 squares around them (connexity 8), so they will behave like a king in chess and instead of manhattan distance will calculate Chebushev distance

Answer 2

Your HERO's set of reachable tiles is known. Around each of these tiles is a THREAT AREA, which is like a (convex?) polygon (a diamond?) An enemy's position could then be thought of as another convex polygon (a square in this case). In the general case, you'd like to test whether these polygons intersect, yes?

Unfortunately it seems that this general problem is more difficult than one might hope.

We might have better luck if we can find that your problem has some special properties. If your HERO's threat area is always convex, then you can perform an inside/outside test using the boundary of the diamond (something akin to CGAL's bounded_side_2 test)

If you find that the approach is NOT good enough, then here's what you can do: pre-generate the set of "attackable positions" for the board; each cell knows the set of other cells the HERO could attack. This is a time-space tradeoff, and if you don't have big memory constraints or moving obstacles, then it should work very well.