I need to find the shortest path for an agent that wants to use a ranged attack against the specified target. This means that path’s ending point should be a) inside range of the attack and b) have line-of-sight on target, which can be blocked by various static obstacles. This part of the game is turn-based, so I only have to worry about finding a path for one agent at a time, and can allow myself to take a small performance hit (anything under 100ms is probably acceptable).

I’m operating in a continuous space, but even if I constrain it with an overlaid grid, the problem doesn’t get much easier, because the only way I can think of to solve it is to find a path (using A*) to every grid cell inside the range that has LOS on target and compare their length to find the shortest one – which is prohibitively expensive, given longer ranges (e.g. calculation of path to target 3000 cells takes up to 600ms). What’s worse, LOS check is also somewhat expensive, so even determining a complete set of cells which have LOS is out of question.

But before we even consider LOS, I can find no good way to find the shortest path to the target circle. Of course, I can sample a number of points on the circumference and find a path to each one, but this sounds too unreliable and also costly enough for long ranges. And of course, this approach breaks down completely if we take LOS into account, because it is possible that no point on circumference has LOS, but some point inside circle does.

I was unable to find any algorithms or even research papers on the topic (of finding a path to a circular zone in continuous space), so maybe I’m using wrong keywords or missing something. Are there any known algorithms for this problem? Or is finding path to every (sampled) point inside circle is my best be, and I should work on optimizing this approach somehow?