4
\$\begingroup\$

Recently I have been implementing the Block A* any-angle path-finding algorithm in a project I have, for which I need extremely efficient results due to the large number of NPCs. However, I still do not know exactly how to handle the problem of local avoidance between the NPCs moving at the same time in the same scene.

So, my question is this: what is the best method to implement local avoidance with any-angle path-finding? Just testing for LOS and steering to the tangent of the predicted encounter is a good enough solution or should a specific AI implementation be included within the pathfinding routine?

I would highly appreciate references (academical or not) with state-of-the-art implementations of local avoidance for me to explore the most recent developments in that field.

Many thanks.

\$\endgroup\$
  • \$\begingroup\$ Just an idea, but what about adding a repulsive force between close NPCs, like the separation behavior in a Boids flocking simulation? \$\endgroup\$ – Danik Jan 24 '16 at 22:18
1
\$\begingroup\$

I have no academical references but when I faced this problem I integrated local avoidance AI into my path finding.

Assuming that from your path finding you have a "next point to bee reached" call it NEXT, in the ai while reaching NEXT cast one or more short rais forward of your NPC :

enter image description here

If its blocked by another NPC chose a near point left or right (so that NEXT is still "visible"), reache the near point then procede to NEXT. You can also decelarate/stop for a random time waiting for less traffic.

\$\endgroup\$
  • \$\begingroup\$ Many thanks for your answer. That's pretty much what I have been planning to do. However, the tricky part is precisely how to decide what is near point to left or right or whatever, in a smooth and inteligent way so other moving NPCs won't choose the same and create even more trouble. Or at best, to avoid the bouncing around or getting stuck in a corner after doing the avoidance. So, that's precisely what I am after, and your answer helped me put it more clearly: interesting ways of making that refined calculation. \$\endgroup\$ – Andy Astro Sep 25 '15 at 15:34
  • \$\begingroup\$ I do almost that but cast a few rays out so I know if the other AI is on the left or right of me and then move the other way. It works well most of the time. Just need some tweaking. 3 rays each side 0.2r, 0.5r, 1.5r then test against an offset boundingsphere with a rad of 200 \$\endgroup\$ – Justin William Stanley Bryant Feb 28 '17 at 2:16
  • \$\begingroup\$ You may also want to look at a few simple rules which would reduce ambiguity. ;) \$\endgroup\$ – Draco18s May 3 '17 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.