Walk to nearest attackable range node

Question

My game has 3D environment which is partitioned in 2d cells(nodes). I have implemented A* for path finding.

Now I am just breaking my head to how to implement the algorithm to move the hero to the nearest attackable range node/point when the enemy is out of attack able range.

Which means, it should satisfy two conditions

1. Target whithin attackable range
2. No obstacles in between the target and attacker

See below picture (pardon for my bad drawings)

• Brown boxes are obstacles
• Attacker/hero is in the cell highlighted with Turquoise color dot, the circle is the radius/size of the model.
• Target is the red dotted color cell, surrounded with red color circle to indicate the size of the model
• Green circle is the radius where hero has to move to some where inside that location to attack (its the radius of hero's attack range)
• Blue dots are the A* path to reach from hero position to target position

When the player issues attack command, hero should move to the nearest attack able node and start attacking.

Finally I thought of below algorithm

1. Calculate radius to scan - This is the sum of attacker radius + attacker weapon radius + target radius
2. Get nodes fall within the radius (from step 1) from targets position
3. Find path from attacker to target using A*
4. Keep walking in the path (from step 3)
5. check if current node is in the scanned nodes (from step 1)
6. If true,
7. Check that no obstacle are in between
8. If true, attack, if false keep walking (repeat step 4)

If we put together the algorithm and the figure1

The A* gets the path of 9 node to reach the target After moving 5 steps, it enters the attackable range, since there is obstacle between the target, it take two more steps where it finds no obstacles and stats attacking.

I am not sure if this is the optimized method to achieve this but I am not getting alternative solution.

Very particular to the steps 2-5 which looks little weird and process intensive to me.

I am using actionscript 3 and Flare3D (Stage3D API)

Answer 1

Your algorithm looks fine, I'd do it like that myself.

The only thing I'd change is points 2 and 5 - you don't need to build a collection of valid nodes and check if current position is in the collection. You're only interested in being close enough to the target. I'd drop point 2 and replace point 5 with "check if current node is within the radius". It's a simple distance check, should be much cheaper than filling a datastructure and searching within it.

Answer 2

There is one other option you might want to consider, which might result in better playing experience.

after step 2, where you create a list of all possible you can find a path starting from yourself to the nearest point. The basic concept is just like A* with a single difference in heuristic function. In a normal A* you have a single target and you have a way to predict how many more steps you have to take to reach it. with multiple target you should predict the number of steps remaining for each of target nodes, and return minimum.