2
\$\begingroup\$

I need to find the shortest path for an agent that wants to use a ranged attack against the specified target. This means that the path's ending point should be inside the range of the attack and have line-of-sight on the target, which may 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. The only solution I can think of is to use A* to find a path to every grid cell inside the range that has LOS on the target, and compare their length to find the shortest one - which is prohibitively expensive at longer ranges. 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.

Before we even consider LOS, I can't find a 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 too costly at long ranges. This approach also completely breaks down if we take LOS into account, because it is possible that no point on a circumference has LOS, but some point inside the 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 the wrong keywords or missing something. Are there any known algorithms for this problem? Alternatively, is finding the path to every sampled point inside circle my best bet, and I should work on optimizing this approach?

\$\endgroup\$
6
  • 7
    \$\begingroup\$ A common misunderstanding about A* is that the goal needs to be a single point/cell, and so if you have a wide area or nebulous definition of allowable goals you'd need to run it multiple times. This is absolutely wrong. You can run a single A* search to find the shortest path to any valid firing position. Run an A* search where your heuristic is the distance to the target minus the firing range (clamped to a minimum of zero) and when it arrives at a point in that range, check for line of sight for that point. Terminate when you find LOS. \$\endgroup\$
    – DMGregory
    Jun 16 at 11:44
  • 2
    \$\begingroup\$ If you don't want to discretize the problem to a grid, you could use a navmesh, as usual. \$\endgroup\$
    – DMGregory
    Jun 16 at 11:48
  • \$\begingroup\$ @DMGregory Thanks, after some testing, this seems to work well enough. I think there still may be some edge cases which A* can't solve (possibly needing some any-angle algorithm to avoid path-straightening post-processing which introduces its own problems), but this approach takes care of most obvious ones. \$\endgroup\$
    – MaxEd
    Jun 21 at 15:25
  • \$\begingroup\$ Want to post your solution as an Answer below? \$\endgroup\$
    – DMGregory
    Jun 21 at 15:27
  • \$\begingroup\$ I just used your comment to modify the heuristic, so we can promote it to the answer, I think? \$\endgroup\$
    – MaxEd
    Jun 21 at 15:34