algorithmdictionarygridgame-ai

Algorithm for finding spaces to attack target within move-attack area on a 2D grid game board


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 :

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.


Solution

  • 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