1

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:

enter image description here

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:

enter image description here

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.

Community
  • 1
  • 1
Alex Stone
  • 46,408
  • 55
  • 231
  • 407
  • I think this can be solved by calculating manhattan distance to targets, and then reading this distance within the move area. If distance <= reach, then that tile can attack target. – Alex Stone Dec 17 '13 at 18:07

2 Answers2

1

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.

Community
  • 1
  • 1
AndyG
  • 39,700
  • 8
  • 109
  • 143
0

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

Algorithm find cells to attack target from

Alex Stone
  • 46,408
  • 55
  • 231
  • 407