Pathfinding to Get In Attack Range with "Transparent" Tiles

Question

Currently I'm using A* and a raycasting algorithm to determine the path an entity (Player) should take to get close enough to the enemy (Enemy). The player has an attack range (it's illustrated around the enemy to show how close the player has to get to the enemy in order to attack it).

This works pretty well, but as soon as I add tiles that prevent entities from moving from them, but allows them to attack through them (imagine a river).

Using my current implementation the player entity takes the purple route to attack the entity, but I want it to take the yellow path.

I came up with the following, but this is highly inefficient:

• Mark the tiles around the enemy (cyan circle), which are in line of sight to the enemy (raycasting) as possible destinations
• Run the pathfinding algorithm to find which one of those destinations is the closest to the player

I know A* is good for finding a single destination and Dijkstra is better for multiple destinations, but since I already got this working with A* I wanted to know if it's possible to achieve this is an efficient manner.

Side question: how are the tiles where you cannot walk through, but can shoot through called in the industry? I know the wall likes entities are mostly called "solids".

Answer 1

"I know A* is good for finding a single destination and Dijkstra is better for multiple destinations"

I would not categorize them this way.

A* is just Dijkstra accelerated by a goal-seeking heuristic, so as long as you can come up with an admissible heuristic distance to the closest goal, it handles multiple goals as well or better than Dijkstra thanks to this acceleration.

The only reason to throw away the heuristic of A* is if you need all paths to everywhere (not just ones toward a goal), or if your goal is so complex it can't be captured by an efficient heuristic.

Here, this heuristic suffices:

h = max(0, (target.position - tile.position).length - attackRange)

This predicts a distance of zero for any tile within the attack range, and the shortest distance to the attack ring for any tile outside it. This is an admissible heuristic since it never over-estimates the remaining distance to get a good shot.

(This particular version accelerates the approach, but doesn't help us much once we're inside the attack radius, so that's an area where we could hope to improve the heuristic further. By this point we're hopefully close to a workable shot, so we should find a firing position without an undue amount of added searching)

Next, we can expand our concept of a goal tile from "a tile that was designated in advance as a goal" to "a tile for which the IsGoal() predicate evaluates to true"

When you expand a tile from A*'s priority queue of candidates, you can evaluate whether it satisfies these goal conditions by...

1. Checking whether it's within the attack radius - if not, early out.

2. If so, check whether it has line of sight to the target.

If so, the tile counts as a goal and you terminate the search.

Since each tile gets expanded only once, and we only do the expensive line of sight check for tiles in the attack radius (and you can cache results for the tiles along the line found, so you don't need to repeat sub-steps), this should generally evaluate the line of sight check fewer times than the exhaustive approach of marking all possible firing locations in advance.