Programming Intelligence – Part II – Avoiding Obstacles

In this part of the series we are going to take a look at avoiding obstacles with two different approaches: simulating eyesight using raycasts, and secondly implementing an algorithm that is inspired by an observer pattern.

Wall Avoidance:

Firstly we want to take a look at avoiding walls (or any other kind of object).
To do that we are placing an algorithm that’ll simulate eyesight using raycasts to detect obstacles.

This GIF shows an agent that walk back and forth between two points. We aren’t using any kind of pathfinding to avoid the wall in between.¬†

So what’s actually happening here? Depending on the accuracy you want to achieve you’ll fire one or several raycasts from the agent in his walking direction. If our raycasts collide with something, we start heading towards a new point, based on our avoidance distance.
By doing this, it appears as if our agent saw the wall and was smart enough to walk around it without bumping into it.

AvoidWalls.cs:

Let’s create a new C#-Script AvoidWalls.cs in our Scripts folder and take a look at the code necessary to implement this behavior.

This behavior is inherited from seek, and this is due to the fact that we use Seek’s GetSteering() function to actually move to the position we set in between to avoid running into the wall.
At the top of our new class, we are declaring an avoidingDistance which represents how far away from our obstacle we are placing our avoiding position. We also declare a sight range. The longer the sight range, the further away from the wall you’ll see the movement of our agent change.

using UnityEngine;

public class AvoidWalls : Seek 
{
    [SerializeField] float avoidingDistance;
    [SerializeField] float sightRange;

    Vector3 currentPosition;
    Vector3 currentRayDirection;

    RaycastHit currentHitInfo;

    public float AvoidingDistance
    {
        get{ return avoidingDistance;}
        set{ avoidingDistance = value;}
    }

    public float SightRange
    {
        get{ return sightRange;}
        set{ sightRange = value;}
    }

    public override void Awake()
    {
        base.Awake();
        Target = new GameObject();
    }

    public override Steering GetSteering()
    {
        Steering steering = new Steering();

        currentPosition = transform.position;
        currentRayDirection = agent.Velocity.normalized * sightRange;

        if(Physics.Raycast(currentPosition, currentRayDirection, out currentHitInfo, sightRange))
        {
            currentPosition = currentHitInfo.point + currentHitInfo.normal * avoidingDistance;
            Target.transform.position = currentPosition;
            steering = base.GetSteering();
        }

        return steering;
            
    } 
}

 

It is really important to see how several rays can have an impact on the outcome. The two following GIF’s will help demonstrate what I am talking about.
However, even though it is true that more rays will yield a better result it is also a fact that rays are costly when it comes to performance – so you’ll have to consider that when you are building a game with hundreds of AI agents.

As you can see one of the agents struggles a bit before he eventually finds a way to avoid the wall while the other one is moving more smoothly around it.

Avoiding other Agents:

Now, it probably goes without saying that the algorithm we implemented before works nicely to avoid agents. This next approach I am going to present to you is called an observer pattern. The idea behind it is to keep track of the position of your agents at all time in order to avoid them colliding with each other.
This basically means that we keep an Array of all of our Agents which we can loop through to check for an agent that is really close to us. If we find one, we calculate if we would collide with him using his velocity. If we would, we are adjust our current agent’s movement to avoid the two agents crashing into each other.

The red ball has a set path that it is following,¬† the white balls way points are crossing red’s path which results in them changing their movement to accommodate for red’s movement.

This algorithm is very useful if you are trying to simulate a crowd, as it would be highly unnatural to see everyone bump into each other. Performance-wise, this observer pattern is also a nicer choice for simulations with many agents because, as I mentioned before, simulating eyesight with raycasts can be costly and it is very easy to multi-thread the iteration through the list/array or even utilize the job system to do so.

AvoidOtherAgents.cs:

Let’s look at the code for our AvoidOtherAgents class and see what this looks like in code:

As you can see here we are simply caching all the targets in an Array. (Keep in mind that for the sake of efficiency you don’t want to do that every time but rather have a manager class that will handle this task once at the start for you.
We are now basically iterating through our Array looking for the closest agent to us to see if he would collide with our current agent.
If he would, we are using the other agent’s velocity value to change our own linear Movement and make sure we won’t collide with the other agent.

using UnityEngine;

public class AvoidOtherAgents : Behavior 
{
    public float collisionRadius = 0.4f; 
    GameObject[] targets;

    float shortestTime = Mathf.Infinity; 
    GameObject firstTarget = null; 
    float firstMinSeparation = 0.0f; 
    float firstDistance = 0.0f; 
    Vector3 firstRelativePos = Vector3.zero; 
    Vector3 firstRelativeVel = Vector3.zero;

    public override Steering GetSteering() 
    { 
        Steering steering = new Steering(); 
        shortestTime = Mathf.Infinity; 
        firstTarget = null; 
        firstMinSeparation = 0.0f; 
        firstDistance = 0.0f; 
        firstRelativePos = Vector3.zero; 
        firstRelativeVel = Vector3.zero; 

        foreach (GameObject t in targets) 
        { 
            Vector3 relativePos; 
            Agent targetAgent = t.GetComponent<Agent>(); 
            relativePos = t.transform.position - transform.position; 
            Vector3 relativeVel = targetAgent.Velocity - agent.Velocity; 
            float relativeSpeed = relativeVel.magnitude; 
            float timeToCollision = Vector3.Dot(relativePos, relativeVel); 
            timeToCollision /= relativeSpeed * relativeSpeed * -1; 
            float distance = relativePos.magnitude; 
            float minSeparation = distance - relativeSpeed * timeToCollision; 
            if (minSeparation > 2 * collisionRadius) 
                continue; 
            if (timeToCollision > 0.0f && timeToCollision < shortestTime) 
            { 
                shortestTime = timeToCollision; 
                firstTarget = t; 
                firstMinSeparation = minSeparation; 
                firstRelativePos = relativePos; 
                firstRelativeVel = relativeVel; 
            } 
        } 

        if (firstTarget == null) 
            return steering; 
        if (firstMinSeparation <= 0.0f || firstDistance < 2 * collisionRadius) 
            firstRelativePos = firstTarget.transform.position; 
        else 
            firstRelativePos += firstRelativeVel * shortestTime; 
        firstRelativePos.Normalize(); 
        steering.LinearMovement = -firstRelativePos * agent.MaximumAcceleration; 
        return steering; 
    }
}

 

Now, full disclosure – this isn’t really a full observer pattern but rather a pattern that takes the basic idea of an observer pattern. The real deal is basically some kind of event system, which means we would need a class managing our objects and notifying them if there are changes.
And while that on its own is an interesting topic it would be way too much for this article.
(Feels free to comment if you’d like me to cover that though)

Up Next:

The next part will handle decision making and will be available for Early Access Patrons from 18th September and from the 25th available for everyone.

Please subscribe to my Twitter to get notified when the next part of this series is available.

Liked it? Take a second to support Kristin on Patreon!

1 comment

Leave a Reply

Your email address will not be published. Required fields are marked *