Simple collision avoidance among agents

[binaryParticipant]

Hi again,

unfortunately my agents run into each other so perfectly frontally, that their collider’s can’t even glitch past each other.

But this circumstance gave me a simple idea for avoidance.
Assuming that the objects are moving along the forward vector you can calculate if one object is facing another.

Quaternion.Dot(transform.rotation, Quaternion.LookRotation( transform.position - otherTransform.position)));

A value close to zero would mean its time to take some action.

I set up the AI and Entity so that the agents could detect each other. With a short range and a very narrow Horizontal Angle of 3 degrees for the sensor, i can convenient tweak the thresholds for the dot product mentioned above so that agents will only detect each other when they are likely to collide. This happens parallel to a wandering behavior.

But i’m stuck at the take (custom) action part:
* pause current wandering behavior
- keep walking and rotate until detection is lost - this would be nice so it could be tweaked trough detector width/range too. Or rotate a fixed amount.
- if new direction is on the navmesh walk a fixed distance or time, else do nothing (and rely on the opposite AI to have avoidance space.)
- optionally trigger a walk-by-high-five animation
* resume wandering behavior

What really troubles me is to make sure to stay on the navmesh.
Is my “simple” idea even remotely possible, or can i stop banging my had against the keyboard? (warning: this is a very advanced programming technique. don’t try at home!)

[primeKeymaster]

It’s a tough problem - if it were really simple it would already be directly supported in RAIN. Obvious solutions that include steering and raycasting don’t work well enough in real game scenarios/Unity to be feasible (IMO). The problems, as you mentioned, amount to:

1) Tracking the things you could potentially collide with
2) Determining quickly if a potential collision will occur
3) Creating an alternate behavior (usually a change in movement)
4) Testing the alternate behavior to see if it is viable (e.g., do I stay on the navmesh?)

Here’s the solution we’ve been considering. I’m detailing it here so that people can give feedback:
1) Use a global manager to track registered moving agents that you want to include in avoidance checks
- this is important, since using colliders or sensors can be extremely slow if you aren’t careful
- you typically only care about avoiding a limited number of things
- you may want to add meta information that helps with collision prediction/avoidance
2) Determine walkable “corridors” around the agents’ path
- corridors would consist of connected line segments that run along the sides of the path at some distance
- corridors would be created by sampling the navmesh at misc points perpendicular to the path
3) Detect future collisions and attempt to compute viable alternatives when possible. Do this by adjusting the path itself, not by steering away from the path and then returning to it.
4) When avoidance is needed, attempt to adjust the path points directly without recomputing the original path (this would be done as part of the path smoothing process). New path points would be restricted to the corridor bounds

[binaryParticipant]

First off, the last time i did something remotely AI related was in high school, turtle programming in a maze. I’m aware that avoidance is not a trivial problem, especially on the scale of an AI engine.

My naive opinion to the solution you’re considering is, that it sounds like a lot of overhead (to be precomputed though but would be a pain during run-time if anything changes) and, more important, the agents will loose autonomy with a global manager.

Maybe calculating an escape vector on the involved velocity’s alone will be good enough. Maybe the (moving) obstacle avoidance through dynamic navmeshes you announced can be extended or not calculating the path to the very mesh edges and keep space for offsetting (lerp) the agent to the left or right of the path will work. There are so many options and you probably have already explored far more then i myself can even imagine. I’m confident you will find a good and robust solution. But, as you might have guessed by now, i personally would favor autonomy over a global tracking solution at any cost, even general performance, and tweak that as much as possible. (Btw. did you ever hear of the RoboCup RescueLeague? It’s an simulated ai contest and if i remember correctly, full agent autonomy is a requirement to qualify for World Championship).

After all, like stated above, i don’t know much about steering behaviors or ai in general, which can be easily a lifetime research field, and hope for insight by an agile discussion.

After looking for a solution for my problem for 2 days now by coding, i came up with an even easier solution without a line of code.
I manged to solve my problem by adding a walk animation that moves the character slightly to the right while walking forward and trigger that with a mecanim parameter on detection in the behavior tree ( i use root motion ). This works in 80% and at least the characters can glitch free now for the other 20. (it works in code too but this way i saved the option to animate the walk-by-high-five )

Im totally amazed (again) how powerful Rain already is. Thank you!

[binaryParticipant]

…. Nooot. My solution has a good chance to put the agent of the mesh.

I’d like to pursue a simple idea: have the agent move always right of the navgraph.
For that i need to calculate the graph with some margin to the meshedge, is the calculation exposed in the api?

[urpro-basParticipant]

Prime,

What you suggest, sounds a lot like some acadamic papers I read, maybe you based you’re ideas on those papers. I don’t know that much about it but the results achieved there seem promising.
Regarding a global manager, that doesn’t seem like to much of a problem to me, because I would see this avoidance problem as the dynamic part of the navmesh. There has to be some medium through which all the agents communicate. It doesn’t really matter whether this is the game world (through colliders/sensors) or through a global manager.
The only part I do not fully understand yet is how the agents would avoid a player with direct controls. Maybe the player should project some kind of expected path? Otherwise all agents respond very intelligently to eachothers collision but have to apply a very ad-hoc avoidance for usercontrolled characters?

Sorry, if I am hijacking the thread, I didn’t know somewhere else to respond to this since Prime set it open for discussion here.

[primeKeymaster]

@binary - Yes, there is a fair amount of overhead in the procedure I outlined. However, the construction can be done on an as-needed basis and can use features of the NavMesh to speed itself up. Once the corridor is constructed, avoidance calculations become much simpler. The global manager doesn’t interfere with autonomy; it is only used for fast lookup of relevant information (as opposed to doing raycasting and tracking all nearby moving objects).

@urpro-bas - Anything that needs to be tracked for avoidance would be registered with the global manager, including the player.

The main goal is to use relevant data that has been precomputed whenever possible. The NavMesh is a precomputed representation of collidable objects in the scene. It should be used instead of raycasting when dealing with locomotion collisions. The corridor would be calculated from the navmesh, and then avoidance calculated from only the dynamic data.

[urpro-basParticipant]

I realised I made an assumption, that is that the paths are avoided ahead, so an upcoming collision between agents was detected by intersection their paths and adjusting the paths. Players obviously don’t have path so such a upcoming collision could not be avoided. But I guess the collision avoidance is more “on the spot”.

[binaryParticipant]

With “simple” i had Unity’s NavMeshAgent avoidance steering in mind.
Though my experiments plugging the NavMeshAgent into a custom motor/navigator went promising, unity cant bake the navmesh at run time nor instantiate prebaked as i need it.

[Author]

Posts