Problem with NPC rotating around a waypoint

Questions & Answers
1

[EDITED FOR A THIRD TIME]

Brief overview of the problem:

Created a simple waypoint script attached to an npc with a character controller component. It rotates him towards the current waypoint, moves him towards it and when he's within a certain radius of it, tells him to aim at the next waypoint. When he gets to the end he aims for the first waypoint again.

Later added functionality to have the NPC patrol back and forth between a series of points or go round the waypoints in a loop. A boolean determines which behaviour this NPC performs. Worked perfectly at first, but then a problem appeared: When the npc reaches the first waypoint he just rotates around and around and doesn't select the next waypoint as his target.

Based on SpinalJack and Johan's answers, the problem seems to be that the NPC is overshooting the waypoint radius. Making a bigger radius works, but i'd rather implement Johan's suggestion re. the Dot Product as this should be more accurate.

Update

I couldn't get it to work using the Dot Product. To be honest, I didn't really understand what it was doing. Looking at Johan's suggestion again, it seems using the Dot Product and squaring the distance are two different solutions, rather than two I should implement simultaneously? I say this because squaring the distance successfully stops the spinning problem.

It seems though, that all this is doing is creating a bigger radius to reduce the risk of the npc overshooting? If that's true, then it's not really any different than setting a bigger radius to begin with. It still seems to break at sizes less than my moveSpeed variable (3), so i'm thinking that setting my radius to my moveSpeed variable will make it work in any situation (even if my npc moves at different speeds)?

That's the approach i've taken below, the squared radius coming out as 9m with the default settings. Both the LoopWaypoints and PatrolWaypoints functions work but there does seem to be quite a bit of duplicate code in there that i'd like to tidy up, if anyone has any ideas? There's also a noticeable delay in both when reaching the end of the waypoints and deciding where to go next.

var waypoints = new Array();

var moveSpeed = 3.0;
var rotationSpeed = 3.0;

var waypointLoop : boolean = false;
var myWaypoints : Transform;

private var currentWaypoint : int;
private var returning : boolean;

private var forward;
private var moveDirection : Vector3;

var waypointDirection : Vector3;
var waypointDistance  : float;
var waypointRadius : float = moveSpeed;

function Start(){

    for (var child : Transform in myWaypoints) {

        waypoints.Add(child);
    }   

    currentWaypoint = 0;
    returning = false;
}

function Update(){

    forward = transform.TransformDirection(Vector3.forward);
    moveDirection = forward * moveSpeed;

    if(waypoints.length<=0){
        print("WARNING!! - No waypoints have been set for "+gameObject.name);
    } else {

        if(waypointLoop){
            LoopWaypoints();
        } else {
            PatrolWaypoints();
        }
    }
}

function LoopWaypoints(){

    if(currentWaypoint < waypoints.length){

        waypointDirection = waypoints[currentWaypoint].position - transform.position;
        waypointDistance = waypointDirection.sqrMagnitude;

        if(waypointDistance <= (waypointRadius * waypointRadius)){

            currentWaypoint++;
        } else {
            RotateTowards(waypointDirection);
            MoveForward();
        }

    } else {

        currentWaypoint = 0;
    }

}

function PatrolWaypoints(){

    if(!returning){

        if(currentWaypoint < waypoints.length){

            waypointDirection = waypoints[currentWaypoint].position - transform.position;
            waypointDistance = waypointDirection.sqrMagnitude;

            if(waypointDistance <= (waypointRadius * waypointRadius)){

                currentWaypoint++;
            } else {
                RotateTowards(waypointDirection);
                MoveForward();
            }

        } else {

            currentWaypoint--;
            returning = true;           

        }

    } else {

        if(currentWaypoint > 0){

            waypointDirection = waypoints[currentWaypoint].position - transform.position;
            waypointDistance = waypointDirection.sqrMagnitude;

            if(waypointDistance <= (waypointRadius * waypointRadius)){

                currentWaypoint--;
            } else {
                RotateTowards(waypointDirection);
                MoveForward();
            }

        } else {

            returning = false;
        }
    }
}
4

Answer from Andeeee on the Unity forums:

This "orbiting" effect occurs when the character is moving at its maximum speed and also turning at its maximum angular rate. If you are moving and turning at a constant rate, you are going in a circle and if the circle's radius is greater than the proximity distance for the waypoint, the character will orbit indefinitely. The best solution to this is to allow the character to slow down in proportion to the angle it has to turn. One easy way to do this is to multiply the speed by the dot product of the character's forward direction and the normalised direction of the next waypoint:-

var speedFactor = Vector3.Dot(waypointDirection.normalized, transform.forward);

var speed = moveSpeed * speedFactor;

This can give some slightly strange effects if the path has a "hairpin" turn around a single point, but it should usually work OK.

Unforunately I didn't have time to implement this in the project - it was our final piece of coursework on my Games Design degree - but it's nice to know why the problem occurs. I'm accepting this answer but thank you to SpinalJack and Johan for trying to help with this too.

2

Try making the distance required bigger or the turning speed faster, you can also make the npc slow down near the way point to be certain he doesn't over shoot it. It could also be that the way point you're trying to reach is too high or too low in the ground for the npc to ever reach it. One way to fix this is to change the distance check to a 2D test and ignore the y axis. Or you could go around your map and make sure every way point is reachable.

3

The problem you're likely encountering is that your NPC never reaches a position that is within `waypointRadius` units from the waypoint. Let's assume your NPC uses the default values, moving 3 units every frame and having to be within 1 unit of the target before moving to the next one. What happens if the NPC ends up at 1.5 units away from the target? He'll walk straight through and appear on the other side, ending up at 1.5 units away on that side instead, and keep doing this.

For a much more reliable way of doing it, compare the dot product of the direction vector before and after movement. If it is less than 0, you're on the other side of the target. A very simple and half-efficient example below, build it in however you see fit.

var beforeMovement : Vector3 = waypoints[currentWaypoint].position - transform.position;
var moveDirection  : Vector3 = forward * moveSpeed;
var afterMovement  : Vector3 = beforeMovement - moveDirection;

if (Vector3.Dot(beforeMovement, afterMovement) <= 0.0f)
{
    // you will end up on the other side of the target after this movement
}

Other than that, there's a few things you might want to look over with your code, that will do nothing but make it more time-efficient. For one, calculating distance between two points is expensive (at minimum a square root, a division, three multiplications and two additions) while calculating the square of the distance is cheap (three multiplications and two additions). Calculating square root and dividing is a lot more time consuming than one multiplication, therefore you'll want to use the square of the distance where you can. This is one such example. You could use this code instead, inside the `LoopWaypoints` and `PatrolWaypoints` methods;

var waypointDirection : Vector3 = waypoints[currentWaypoint].position - transform.position;
var waypointDistance  : float = waypointDirection.sqrMagnitude;

// if we are moving up through the waypoints (ie. not returning)
if(!returning){
    // if we have not reached the last waypoint (the -1 is necessary to avoid an Index Out of Range error)
    if(currentWaypoint < waypoints.length-1){
        // if we have reached the current waypoint, aim for the next one
        if(waypointDistance <= (waypointRadius * waypointRadius)){

Since the comparison is using the square of `waypointRadius` in this example, it is fine if we only determine the square of the distance. Also, instead of moving a set value each frame, you'll probably want to make it time dependent (with `Time.deltaTime`), unless the SimpleMove method already does this.

var moveDirection = forward * (moveSpeed * Time.deltaTime);