Smooth random motions with differentiable random providers

Real-world movements are restricted by the laws of physics. E.g, body is required to move in a continuous motion without any sudden jumps. When modelling NPCs, a realistic movement is essential. Furthermore, mostly is is desirable for the NPC to move randomly. Most programming languages include random number generators, sometimes even for pre-defined probability distributions. However, if one assigns the output of these generators to an NPC’s position, the resulting movement will be far from realistic because the generator produces independent output that does not obey to the laws of physics. In this post, I will introduce a neat structure that overcomes this restriction by ensuring continuous differentiability of output.

Continuous Differentiability

Derivatives

Before we begin, let’s discuss the question why continuous differentiability is desirable. For this, we assume a simple scenario where a body can move back and forth (in a single dimension). Let’s denote the body’s position with x. The derivative of x with respect to time t is its velocity v (how much does the body move in a specified time step). We’ve already stated that the body’s position cannot produce jumps over time. But can the velocity? It turns out that it cannot neither. A body that moves with a constant velocity of 10 m/s cannot suddenly move with 20 m/s. It needs an acceleration phase. And, indeed, the derivative of velocity v with respect to time is the acceleration a (how much does the body’s velocity change in a specific time step). Theoretically, the acceleration (which is induced by any kind of force) does not need to be continuous. So, the body’s position needs to be at least once continuously differentiable (the velocity needs to be continuous). This property is called C1-continuity.

The figure to the right shows the development of acceleration, velocity and position (from top to bottom) of a bodies motion over time.

Enforcing Cn-continuity

As can be seen in the figures of the preceeding section, the topmost quantity does not need to be continuous. Hence, a standard random number generator can be used to produce this quantity. Everything else can be calculated by integration.

The overall scheme can be applied to any quantity that needs differentiability. The position of a body at a given time is just one example. The general quantity will be denoted by dn(t) from now on, where n specifies the number in the derivative hierarchy. d0(t) denotes the base quantity (which is produced by the random number generator). Subsequent n's are calculated by integrating the previous function.

Most applications calculate simulations in discrete steps (e.g. frame by frame). The length of a single step will be denoted by Δt, the values at the beginning of a step by dn, and the values at the end of a step by dn. Each step can be integrated separately. The formulae for the first four antiderivatives are as follows:

AntiDerivatives

As we go deeper in the derivative hierarchy, the antiderivatives get more complicated. However, they share a common base. The correction terms at the end are of higher order and can be neglected if we choose small enough step sizes. Therefore, the generalized formula is:

AntiDerivativeGeneralized

The last summand in the formula is the neglected error term of square order. Although it is not obvious, the second to last summand is of higher order (because preceeding derivatives are included). This makes the neglected error very small and in practice not noticeable.

This formula allows to construct a list of integrators that produce a differentiable output in the end.

Implementation

The implementation is very simple and can be done with the following class:

public class DifferentiableRandom
{
    private static Random rand = new Random();

    public DifferentiableRandom DerivativeProvider { get; private set; }

    protected double ValueAtStepBegin { get; private set; }

    public double Value { get; set; }

    public double Min { get; set; }
    public double Max { get; set; }

    int level;

    public DifferentiableRandom(double min, double max, double initialValue = 0)
    {
        Min = min;
        Max = max;
        Value = initialValue;
    }

    public DifferentiableRandom AddDifferentiableLayer(double min, double max, double initialValue = 0)
    {
        level++;
        if (DerivativeProvider == null)
        {                
            DerivativeProvider = new DifferentiableRandom(min, max, initialValue);
        }
        else
        {
            DerivativeProvider.AddDifferentiableLayer(min, max, initialValue);
        }
        return this;
    }

    public void Advance(double step)
    {
        if(DerivativeProvider == null)
        {
            //choose a random value
            Value = rand.NextDouble() * (Max - Min) + Min;
            ValueAtStepBegin = Value;
        }
        else
        {
            //Evaluate the derivative
            DerivativeProvider.Advance(step);
            ValueAtStepBegin = Value;
            Value += step * (DerivativeProvider.ValueAtStepBegin + 1.0 / level * (DerivativeProvider.Value - DerivativeProvider.ValueAtStepBegin));
            if (Value < Min)
                Value = Min;
            if (Value > Max)
                Value = Max;
        }
    }
}

The idea is that each random provider may have a derivative provider of the same type. If a step is evaluated, the random provider first evaluates its derivative and then itself. Furthermore, each provider has some bounds which avoids extreme values. In the above scenario (with random accelerations), the class could be used as follows:

xProvider = new DifferentiableRandom(0, 500, 250) //position
                .AddDifferentiableLayer(-100, 100) //velocity, pixels per second
                .AddDifferentiableLayer(-200, 200); //acceleration, pixels per second²

//Evaluate a step of 20 milliseconds
xProvider.Advance(0.02);

//Use the differentiable output in some visualization
displayObject.Left = xProvider.Value;

Demo

In the demo application, the x and y coordinates of an object have been associated with a differentiable random provider. Two providers have been used. One as discussed above and one with an additional differentiable layer (resulting in a continuous acceleration). Although laws of physics allow random accelerations, this is mostly not the case. The additional layer produces a smoother motion. The following video compares both motions:

Visual Studio 2013 Solution (WPF)

As stated earlier, the randomizer can be applied to any quantity. E.g. if a random car movement is desired, the car’s position could be expressed in polar coordinates. The direction can be controlled by one random provider and the speed by another. Furthermore, it is not necessary to integrate over time. Smooth procedural terrains can be generated by integrating over location (although in its current form only one-dimensional terrains are supported).

Advertisements

, , , ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: