[A.I. For Games] Collision/Obstacle Avoidance

This blog series is a part of the write-up assignments of my A.I. for Games class in the Master of Entertainment Arts & Engineering program at University of Utah. The series will focus on implementing different kinds of A.I. algorithms in C++ with the openFrameworks library, following most of the topics in the book Artificial Intelligence for Games by Ian Millington and John Funge.

In this post, I will talk about the implementations collision/obstacle avoidance behavior in my AI project.

Collision/Obstacle Avoidance

In order to be able to create a smooth and life-like steering behavior. Collision avoidance is crucial since the boids will just be walking through each other if this is not implemented. Generally speaking, we can split the collision avoidance into two categories, one is dynamic collision avoidance and one if static obstacle avoidance.

Dynamic Collision Avoidance

This is the collision avoidance that will stop prevent the boids from running through each other. The simplest way we can try to solve this problem is to have a cone in front of each of the boids (Fig. 1), and detect whether there is anyone else inside that cone. If there is, then we can perform some sort of evading or fleeing behavior to prevent that from happening. This is really easy to implement mathematically and very low cost. However, this does not work in many cases.

Imagine that we have two boids side-to-side and moving toward the same target (Fig. 2). We can see that they will clearly collide with each other in the future, but they won’t be able to know at all before it’s too late!

Fig. 1

Fig. 2

To address the collision problem better, we need to project the current motions of the boids into the future and try to determine whether there will be a collision at all. Given the positions and the velocities of the boids, we can calculate the future closest collision distance and time (Fig. 3) with a simple formula (Fig. 4).

Fig. 4

Now that we retrieve the closest collision distance and time, we can use that future potential collision point as the target for us to perform avoidance behavior. At first, I was delegating to dynamic evade behavior. However, since evade doesn’t take the distance between objects into consideration, it simply tries to run away on the first sight that it detects any future potential collision (Vid. 1). Because of all those reasons. Switching from dynamic evade to dynamic separation seems like a sensible option.

Switching to separation does solve the problem of early panicking. However, if the two boids are experiencing a directly head-on collision (Vid. 2), it is not trivial to resolve. If there is not a head-on collision (Vid. 3), then the boids can proceed without any problem, of crouse.

Even though perfectly head-on collision might be really rare to see in an actual game, I decided to introduce some randomness to help the steering algorithm escape from this equilibrium. However, where should I introduce the randomness?

I decided to add this randomness into the dynamic separation. To think about it, it kind of makes sense since even human is not able to make the perfect avoidance to keep ourselves from other people.

After introducing the randomness and tweaking the parameters for a bit, we can observe the subtle avoiding behavior when the two boids are almost colliding to each other in the video below.

Obstacles Avoidance

Comparing to collision avoidance, obstacles avoidance will test collision against some static obstacles. The algorithm I adopted here detects collision using a ray cast and simple AABB (Axis-Aligned Bounding Box) collision. To achieve this, I created a new AABB structure and a ray structure. While I call it a ray structure, it is essentially a line segment since the length can be specified.

3D AABB structure

2D ray structure

To check if a ray intersects with AABB, I am actually performing the box-ray separation test on both axes. For the x-axis, I check the time for the closing gap and the time for the opening gap. After doing the same for the y-axis, we will get the time of collision and also the point of collision.

Ray checking against one axis

Ray check against AABB

Result

Now, let’s examine the result and see how it performs. Note that currently I am only performing one single ray to check for collision, and I have tuned the parameters for a bit to achieve an acceptable result in the video shown below.