Biased, conservative random walk

Question

I have a sprite which has Velocity and Position, either stored as Vector2. At each Update cycle, velocity is added to the position.

I would like to give the sprite a third vector, Target. New targets may be given at any iteration. I would like the sprite to essentially move in a random walk pattern, however two parameters must be exposed:

1. A typical random walk is equally likely to increase or decrease the distance to any given Target (plus the small chance of tangential movement). I must be able to bias my random walk such that, while still random, the direction on which the sprite "decides" should be more likely to bring it closer to Target.
2. The random walk should be "smooth"- the sprite should not rapidly change direction, as this will look like it's "flickering" or "trembling" to the player. It should gradually veer this way or that, moving randomly, while slowly getting closer when averaged.

What is a good, simple way to do this? If possible, give the answer as a Vector2 RandomWalk(Vector2 target) method.

I already have a NextGaussian(mean, stdev) method available, if that is helpful.

Answer 1

I would take the "wander" steering-behavior (source code can be found here) and tweak it in a way so that the random numbers are biased towards your target.

Answer 2

To get a smooth random walk, you could use Catmull-Rom splines. This kind of spline takes a sequence of points and generates smooth curves that pass through each point. So, you could generate random waypoints for the sprite to move through and animate it along a Catmull-Rom spline through the waypoints. For the spline to work you'll need a total of four waypoints: the previous two and the next two. When the sprite reaches a waypoint, throw away the oldest one of your set of four and generate a new one, then continue animating along the spline.

As for eventually heading toward the target, one idea would be to offset the distribution of the random walk toward the target. For instance, if you'd usually pick a random waypoint using a Gaussian distribution centered on the current position of your sprite, you could instead offset the center of the Gaussian by some preset distance toward the target. The relative sizes of the offset and the Gaussian's standard deviation would determine how biased the motion is.

Answer 3

Here's something I whipped up in about 20 minutes. We take the direction from the walker to the target, pick a direction within a certain amount of degrees of that direction (an amount that decreases as the walker gets closer to their target). This algorithm also accounts for distance to target so that it will not walk past the target. Long story short, it basically wobbles left and right a small random amount and homes in on the target as it gets closer.

To test this algorithm I placed the walker at (10, 0, 10), and the target at (0, 0, 0). The first time the algorithm ran it randomly chose a position for the walker to walk to of (3.73f, 0, 6.71f). After the walker reached that position it chose (2.11f, 0, 3.23), then (0.96f, 0, 1.68f), then (0.50f, 0, 0.79f), then it walked straight to the target because it was within a minimum tolerance distance.

Graphed out from a bird's eye view the path would look like the points in the image below, starting at 'W' (walker) and ending at 'T' (target). If you want a more natural movement you would precalcuate a few points ahead of time, and create a spline, giving you many more points you can have the walker follow. I've estimated what this path would look like after being made into a spline, and that is represented by the line in the image.

And here's the example code:

Vector3 WalkerPosition = new Vector3(10, 0, 10);
Vector3 TargetPosition = Vector3.Zero;

public Game1()
{
    // Each time you reach the next walk-to position, call this again.
    // Eventually you'll reach your target, assuming the target isn't moving away
    // from the walker faster than the walker can reach them.
    Vector3 NextWalkToPosition = PickRandomTarget();
}

public Vector3 PickRandomTarget()
{
    // For this code sample we'll assume that our two targets are on
    // the same horizontal plane, for simplicity.

    Vector3 directionToTarget = ( TargetPosition - WalkerPosition );
    float distance = directionToTarget.Length();
    directionToTarget.Normalize();

    float distanceThisIteration = distance * 0.5f;

    // We should never walk too little or too far, to make this more realistic
    // you could randomize the walking distance each iteration a bit.
    distanceThisIteration = MathHelper.Clamp(distanceThisIteration, 1.0f, 10.0f);

    // We're within minimum distance to the target, so just go straight to them
    if (distanceThisIteration > distance)
    {
        return TargetPosition;
    }

    directionToTarget *= distanceThisIteration; // Walk roughly halfway to the target            

    // Now we pick a new walking direction within an FOV that gets smaller as
    // we get closer to the target. We clamp the FOV between 0 and 90 degrees (45 degrees in either direction).
    const float walkerAggroRadius = 30.0f; // Walker aggros when within 30 units of target

    // Any distance outside of 30 we'll just treat as 30.
    float distanceMod = MathHelper.Clamp(distance, 0.0f, walkerAggroRadius);

    // We need a percentage value representing the current distance between the min 0, and max, 30
    float percentageAlongDistance = distanceMod / walkerAggroRadius;

    // We want FOV from center, so we cut the final FOV result in half
    float maxFOVAtThisDistance = MathHelper.Lerp(0.0f, MathHelper.PiOver2, percentageAlongDistance) * 0.5f;

    // Now we pick a random FOV from center within our maxFOV based on how far we are
    // from the target
    Random rand = new Random(System.DateTime.Now.Second);
    float randFOV = (float)(rand.NextDouble() * maxFOVAtThisDistance);

    // Right now our FOV value is an FOV from a vector pointing directly at our target, we now
    // need to randomly choose if we're going to aim to the left or right of the target. We'll
    // treat a result of 0 as left, and 1 as right
    int randDirection = rand.Next(2);
    if (randDirection == 0) // Left
    {
        // Rotate our direction vector left by randFOV radians
        return WalkerPosition + RotateAroundPoint(directionToTarget, Vector3.Zero, Vector3.UnitY, -randFOV);
    }
    else // Right
    {
        return WalkerPosition + RotateAroundPoint(directionToTarget, Vector3.Zero, Vector3.UnitY, randFOV);
    }
}

// Generic helper function to rotate a vector by a specific amount of degrees
public Vector3 RotateAroundPoint( Vector3 point, Vector3 originPoint, Vector3 rotationAxis, float radiansToRotate )
{
    Vector3 diffVect = point - originPoint;

    Vector3 rotatedVect = Vector3.Transform(diffVect, Matrix.CreateFromAxisAngle(rotationAxis, radiansToRotate));

    rotatedVect += originPoint;

    return rotatedVect;
}

Based on your specific game you can tweak distances, FOV, randomness, and frequency that this is run, until it suits your needs. I'm sure the algorithm could be cleaned up a bit and optimized, I didn't spend much time on that, I just wanted it to be easy to read.