Collision Avoidance Process

Dynamic avoidance while path following is a process that computes a velocity in each frame to meet these requirements:

• Avoid any moving or static bot, or obstacle in the path.
• Pick a velocity that follows the computed path (does not stray too far from it).
• Respects the NavMesh boundaries and the computed channel.
• Minimizes the avoidance effort while being as stable as possible.

Dynamic avoidance consists of these steps:

1. Collect the potential colliders. See Collecting the Colliders below.
2. Generate and score a set of avoidance velocities on various criteria. See Generating the Avoidance Velocity below.
3. Choose the most suitable velocity to apply in the given frame. See Utility Function for Final Score below.

The following sections explain the dynamic avoidance process.

It is costly to compute the avoidance for a bot based on the entire world elements in a scene. Moreover, it does not serve the purpose because avoidance is mostly local and based on nearby entities.

It is also likely that the entities to avoid in a given frame are roughly the same in the subsequent frames because of time coherence. Therefore, you can leverage the NavMesh propagation structure to build a list of nearby potential colliders. You only need to update this list at a given frame rate. The following figure shows the collider collection extent displaying the entities that you can avoid.

You can configure this process in ColliderCollectorConfig. Following are the parameters:

• m_colliderCollectorRadius – Defines the radius in meters around the bot in which potential colliders are collected.
• m_colliderCollectorHalfHeight – Defines the height in meters above and below the bot altitude in which potential colliders are collected.
• m_colliderCollectorFramesBetweenUpdates – Defines the number of frames between two consecutive collection of potential colliders.

For a bot at any given time, the entity can reach a wide range of potential velocities. For path following and to avoid chaotic behaviors, you can limit the set of avoidance velocities to a fixed range.

First, a global path following direction must be determined. This direction is computed to be compatible with the path following process.

• Shortcut mode – Take the direction of the current path edge that supports the target on the path. The following figure shows the reference direction for avoidance is parallel to the current path edge.

• Channel mode – Take the direction in the current channel section. The following figure shows the reference direction is parallel to the direction between the two gates for the current section.

Now, generate samples of N avoidance velocities around the path following direction. The following figure shows the generated velocity samples, all scored to 1.0 by default.

The speed of these velocities matches the desired speed in the bot config. You can configure the number and angle span for these velocity samples in AvoidanceConfig. Following are the parameters:

• m_avoidanceAngleSpan – Angle span in degrees for avoidance velocities.
• m_avoidanceSampleCount – Sample count for avoidance velocities.

You can now perform a scoring process to choose which velocity is the best.

The avoidance is both local in space and in time. You can specify a time limit that serves as a horizon, and compute a collision time with the collected colliders for each sample. The following figure shows the collision time computed for a given frame.

If there are no collisions, or if the collision is beyond the configured time limit, you can set the sample cost as the time limit.

You can score the samples based on their distance from the NavMesh/channel boundaries. The following figure shows that samples leading outside the NavMesh get a bad score.

You can divide the collision time with the horizon to compute a ratio between 0.0 and 1.0f, where 1.0f is the safest velocity. The following figure shows the collision time as a ratio.

You can specify the time horizon in AvoidanceConfig. Following are the parameters:

• m_minimalTimeToCollision – If an obstacle collides with another obstacle in less than N seconds, take it into account for avoidance.
• m_safetyDistance – Safety distance around a collider to avoid moving too close. You can slightly expend the size of the colliders by a safety distance to pick velocities that remain far from the colliders.

Sampling might be inaccurate because only a few degrees separate a valid sample from an invalid one. To avoid picking samples that are not safe, you can compute the average collision time ratio for each velocity sample with its neighbors. The following figure shows the smooth collision time.

You can now choose safe collision free velocities. However, there are several possibilities, so you can consider two other criteria to decide.

The path following already produced a desired velocity. You can leverage this velocity to score the samples based on how far they are relative to this velocity. The following figure shows how the desired velocity (in green) is used to score the samples based on how far they are from it.

To stabilize even further, you can perform a similar computation relative to the previously computed velocity. The following figure shows how scoring is based on the previous velocity (in red).

You can use the following utility function for each sample and compute the final score.

Final Score = (A * CollisionTimeRatio) + (B * DesiredVelocityDistance) + (C *  PreviousVelocityDistance)

Where, A, B, and C are constants that you can configure (best understood if A +B + C = 1.0). After you get the final score, simply return the velocity whose sample has the highest score. The following figure shows the chosen final score and final velocity to output for avoidance.

You can configure A, B, and C in AvoidanceConfig. Following are the parameters:

• m_timeToCollisionInfluence – Influence of the time to collision in choosing the avoidance velocity.
• m_desiredVelocityInfluence – Influence of the desired velocity in choosing the avoidance velocity.
• m_previousVelocityInfluence – Influence of the previous velocity in choosing the avoidance velocity.

When there are no good avoidance solutions, you can return a zero velocity for the entity to stop if the next collision time is below a given threshold. Following are the parameters:

• m_stopCollisionTime – The entity stops if a collision cannot be avoided in less than stopCollisionTime seconds. After stopping, it is better to commit to this decision for a while to avoid jerky movements.
• m_stopWaitTime – If the entity stops, wait for stopWaitTime seconds before moving again.

In some cases, you might prefer slowing down first, or even disabling the ability of the entity to stop. Following are the parameters:

• m_enableSlowingDown – If set to true, velocity candidates with reduced speed are considered. Otherwise, only velocity candidates with Bot::GetDesiredSpeed() length are considered.
• m_enableStop – If set to true, null velocity candidate is considered. Otherwise, the AvoidanceSolver never considers stopping the bot, which sometimes forces its way through the colliders.

You might still want to force the passage if you are blocked for too long. Following are the parameters:

• m_enableForcePassage – If set to true, solutions with collisions are allowed if no other solutions are found after a while.
• m_waitPassageTimeLimit – If m_enableForcePassage is true, the passage is forced only after a delay of m_waitPassageTimeLimit seconds.
• m_forcePassageTimeLimit – If m_enableForcePassage is set to true, the passage is forced for at most m_forcePassageTimeLimit seconds only after a delay of m_waitPassageTimeLimit seconds.