Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'd like a function to animate an object moving from point A to point B over time, such that it reaches B at some fixed time, but its position at any time is randomly perturbed in a continuous fashion, but never goes backwards. The objects move along straight lines, so I only need one dimension.

Mathematically, that means I'm looking for some continuous f(x), x ∈ [0,1], such that:

  • f(0) = 0
  • f(1) = 1
  • x < y → f(x) ≤ f(y)
  • At "most" points f(x + d) - f(x) bears no obvious relation to d. (The function is not uniformly increasing or otherwise predictable; I think that's also equivalent to saying no degree of derivative is a constant.)

Ideally, I would actually like some way to have a family of these functions, providing some seed state. I'd need at least 4 bits of seed (16 possible functions), for my current use, but since that's not much feel free to provide even more.

To avoid various issues with accumulation errors, I'd prefer the function not require any kind of internal state. That is, I want it to be a real function, not a programming "function".

share|improve this question
3  
Your third and fourth requirement can be approximated as f'(x)>0, so the the normalized integration of the absolute value of any noise function will fulfill all your requirements. Unfortunately I don't know of any easy way to calculate that, but maybe someone else does. :) –  SkimFlux Mar 29 '12 at 11:49
    
Would perturbing the perpendicular of your function instantaneous slope work? –  kaoD Mar 29 '12 at 15:08
    
When you say "To avoid various issues with accumulation errors" I thought you were worried about precision. It seems that, based on your many comments, you are concerned with the performance cost of excessively many evaluations. You should state exactly what performance and memory constraints we are subject to - the requirement is unhelpful anyway because one can seemingly construct functions with state which do not have accumulation errors (What does that mean, anyway?). Also, your 4th point is wrong. A trivial example: No derivative of e^x is constant, so it's not equivalent to saying that. –  Superbest Mar 29 '12 at 22:12

6 Answers 6

For this post, y = f(t) where t is the parameter you vary (time/progress) and y is distance to target. So I will speak in terms of points on 2D plots where the horizontal axis is time/progress and the vertical is distance.

I think you can make a cubic Bezier curve with first point at (0, 1) and fourth (last) point at (1, 0). The two middle points can be randomly placed (x = rand, y = rand) within this 1-by-1 rectangle. I am unable to verify this analytically, but just from playing around with an applet (yeah, go ahead and laugh) it seems that the Bezier curve will never decrease with such a constraint.

This will be your elementary function b(p1, p2) which provides a non-decreasing path from point p1 to point p2.

Now you can generate a b(p(1) = (0, 1), p(n) = (1, 0)) and pick a number of p(i)'s along this curve such that 1

Essentially, you are generating one "general" path, and then breaking it up into segments and regenerating each segment.

Since you want a mathematical function: Suppose the above procedure is packaged into one function y = f(t, s) which gives you the distance at t for the function of seed s. You will need:

  • 4 random numbers for placing the 2 middle points of the main Bezier spline (from (0, 1) to (1, 0))
  • n-1 numbers for the bounds of each segment if you have n segments (the first segment always starts at (0, 1) ie t=0 and the last ends at (1,0) ie t=1)
  • 1 number if you want to randomize the number of segments
  • 4 more numbers for placing the middle points of the spline of the segment your t lands at

So each seed must supply one of the following:

  • 7+n real numbers between 0 and 1 (if you want to control the number of segments)
  • 7 real numbers and one integer greater than 1 (for a random number of segments)

I imagine you can accomplish either of these by simply supplying an array of numbers as the seed s. Alternatively, you could do something like supply one number s as seed, and then call the built-in random number generator with rand(s), rand(s+1), rand(s+2) and so on (or initialize with s and then keep calling rand.NextNumber).

Note that even though the whole function f(t, s) is made up of many segments, you are only evaluating one segment for each t. You will need to repeatedly calculate the boundaries of segments with this method, because you will have to sort them to make sure no two segments overlap. You can probably optimize and get rid of this extra work and only find the endpoints of one segment for each call, but it is not obvious to me right now.

Also, Bezier curves are not necessary, any suitably behaving spline will do.

I created a sample Matlab implementation.

The Bezier function (vectorized):

function p = bezier(t, points)
% p = bezier(t, points) takes 4 2-dimensional points defined by 2-by-4 matrix
% points and gives the value of the Bezier curve between these points at t.
% 
% t can be a number or 1-by-n vector. p will be an n-by-2 matrix.
    coeffs = [
        (1-t').^3, ...
        3*(1-t').^2.*t', ...
        3*(1-t').*t'.^2, ...
        t'.^3
    ];

    p = coeffs * points;
end

The compound Bezier function described above (deliberately left unvectorized to make it clear how much evaluation is needed for each call):

function p = bezier_compound(t, ends, s)
% p = bezier(t, points) takes 2 2-dimensional endpoints defined by a 2-by-2
% matrix ends and gives the value of a "compound" Bezier curve between
% these points at t.
% 
% t can be a number or 1-by-n vector. s must be a 1-by-7+m vector of random
% numbers from 0 to 1. p will be an n-by-2 matrix. 
    %% Generate a list of segment boundaries
    seg_bounds = [0, sort(s(9:end)), 1];

    %% Find which segment t falls on
    seg = find(seg_bounds(1:end-1)<=t, 1, 'last');

    %% Find the points that segment boundaries evaluate to
    points(1, :) = ends(1, :);
    points(2, :) = [s(1), s(2)];
    points(3, :) = [s(3), s(4)];
    points(4, :) = ends(2, :);

    p1 = bezier(seg_bounds(seg), points);
    p4 = bezier(seg_bounds(seg+1), points);

    %% Random middle points
    p2 = [s(5), s(6)] .* (p4-p1) + p1;
    p3 = [s(7), s(8)] .* (p4-p1) + p1;

    %% Gather together these points
    p_seg = [p1; p2; p3; p4];

    %% Find what part of this segment t falls on
    t_seg = (t-seg_bounds(seg))/(seg_bounds(seg+1)-seg_bounds(seg));

    %% Evaluate
    p = bezier(t_seg, p_seg);    
end

The script which plots the function for a random seed (note that this is the only place where a random function is called, the random variables to all other code are propagated from this one random array):

clear
clc

% How many samples of the function to plot (higher = higher resolution)
points = 1000;

ends = [
    0, 0;
    1, 1;
    ];

% a row vector of 12 random points
r = rand(1, 12);

p = zeros(points, 2);

for i=0:points-1
    t = i/points;
    p(i+1, :) = bezier_compound(t, ends, r);
end

% We take a 1-p to invert along y-axis here because it was easier to
% implement a function for slowly moving away from a point towards another.
scatter(p(:, 1), 1-p(:, 2), '.');
xlabel('Time');
ylabel('Distance to target');

Here's a sample output:

enter image description here

It seems to meet most of your criteria. However:

  • There are "corners". This may be amenable by using Bezier curves more appropriately.
  • It "obviously" looks like splines, although you can't really guess what it will do after a non-trivial period of time unless you know the seed.
  • It very rarely deviates too much towards the corner (can be fixed by playing with the distribution of the seed generator).
  • The cubic Bezier function cannot reach an area near the corner given these constraints.
share|improve this answer

I guess that instead of blending a bunch of transformed cosines (like the dot products in perlin noise give you), you could blend several monotonic functions that start at f(0)=0, like f(x) = x, or 2x, or x^2, etc. In fact since your domain is limited to 0=>1 you could also blend in trig functions that fit the bill within that domain like cos(90*x+270). To normalize your methods to end at 1, you can simply divide the weighted sum of these monotonic methods starting at f(0)=0 by f(1). Something like this should be fairly easy to invert as well (which I gather you want from the bit about stateless real functions versus programming functions).

Hope this helps.

share|improve this answer

One can analyze this crude picture enter image description here You can end up with a function that performs your animation on the fly, by making use of an uniform rand function. I know this isn't the exact mathematical formula, but there's actually no mathematical formula for a random function, and even if there were one, you'd be coding a lot to achieve this. Considering you didn't specify any smoothness conditions, the speed profile is $C^0$ continuous (but since you're not dealing with robots, no need to worry about discontinuous acceleration profiles).

share|improve this answer
    
"there's actually no mathematical formula for a random function" I want a noise function, not a random function. Noise functions are well-documented to exist. Piecewise definitions like this also tend to create either inefficiency (evaluating becomes O(pieces) which becomes a problem when you have long time scales), impure functions (evaluate in O(1) but need to keep the previous position), or over-constrain possible functions (e.g. all inflection points are at fixed intervals). –  user744 Mar 29 '12 at 12:55
    
Hmm, sorry, I thought that noise functions also use a random number generator procedure and that are also dependent on a discrete set of guide/key points to yield a shape (I saw Perlin Noise was mentioned.. that one works via pseudo-random number generators that are quite difficult to integrate, hence no analytic solution). Can one integrate a noise function analytically? I am wondering if one of these could be a candidate link –  teodron Mar 29 '12 at 13:38
    
As an example, Perlin noise takes a seed state of 255 8 bit numbers, but from that it generates random noise in infinite distance in three dimensions; it's not really accurate to describe them as "guide points", mathematically they are more like another 256 parameters you don't want to keep providing. As you say it's essentially not integrable, but it is a pure function. The page you linked to is a bad explanation of Perlin noise (it's not really Perlin noise he explains). As for whether it's possible for some kind of noise function... well, that's the question, isn't it? –  user744 Mar 29 '12 at 14:20

The usual way of generating an increasing sequence of N random numbers from [0,1] is to generate N random numbers in any range, then divide them all by their total sum, then sum them one-at-a-time to get the sequence.

Generate the sequence 2, 2, 5, 8, 6.
Their sum is 23, so our numbers to sum are 2/23, 2/23, 5/23, 8/23, and 6/23.
Our final sequence is 2/23, 4/23, 9/23, 17/23, 23/23

This can be extended to 2D by generating these values for both X and Y. You can increase N to get any granularity you want.


In @teodron's similar answer, you cited efficiency concerns with large time-scales. Without knowing the actual problem you're facing, I can't tell if that concern is valid; but another option would be to generate for small N, and simply smooth the result. Depending on the application, this may actually give better results.

enter image description here
N=100, no smoothing

enter image description here
N=15, with smoothing

share|improve this answer
    
Whatever you're doing for smoothing, it seems to have made the result not even a function (around x = 0.95); I'm not sure if that's an artifact of your graphing program or a mistake. Monotonicity also seems to be violated around 0.7. Anyway, I'm familiar with "the usual way" - I'm asking this question because I suspect the usual way is crappy. Pre-Perlin-noise, after all, no one had a problem with giant LUTs of value noise, it was just "the usual way". Today, we have a way that's considerably more flexible and efficient. –  user744 Mar 29 '12 at 18:47
3  
I agree with BlueRaja: There are well-known, easy-to-implement ways of smoothing without violating monotonicity, regardless of the example. For instance, moving average or drawing splines. However, @JoeWreschnig concern is not irrelevant. Game rules and mechanics may depend on objects never retreating to function - it is rarely a good idea to assume that things the asker doesn't really need what he says he needs. –  Superbest Mar 29 '12 at 20:02
1  
@BlueRaja: My basic complaints about piecewise approaches like this are described in my response to teodrone. It's not about finding "the most rigid and mathematically-precise result" - it's about opening up new possibilities with a mathematical tool previously unknown to us. Again, consider the analogy between giant value noise LUTs and Perlin noise. Not every question on the site needs an off-the-cuff "good enough" answer any halfway intelligent CS undergrad could bang out between lectures - sometimes, let's shoot for doing something original and professional, okay? –  user744 Mar 29 '12 at 20:09
1  
Or we could just continue to let this site wallow in 90% elementary confusion about transformation matrices, 10% "help me stop playing games!" That'll make an awesome Q&A site every professional will love to come to. –  user744 Mar 29 '12 at 20:10
2  
@Joe: That's, erm, uncalled for. You asked for a solution to fit your criteria, I gave you one. Just because it's simple doesn't make it bad. –  BlueRaja - Danny Pflughoeft Mar 29 '12 at 20:17

I suggest this implementation inspired by the summation of octaves found in fractal noise, with a bit of cheap ass shuffling here and there. I believe it is reasonably fast and can be tuned by asking for fewer octaves than stored in the parameters with a loss of precision of about 1/2^octave.

You could see it as a piecewise implementation that only requires O(log(pieces)) time. The parameter array is used both for the divide-and-conquer pivot position, and for the distance traveled when reaching the pivot.

template<int N> struct Trajectory
{
    Trajectory(int seed = 0)
    {
        /* The behaviour can be tuned by changing 0.2 and 0.6 below. */
        if (seed)
            srand(seed);
        for (int i = 0; i < N; i++)
            m_params[i] = 0.2 + 0.6 * (double)(rand() % 4096) / 4096;
    }

    double Get(double t, int depth = N)
    {
        double min = 0.0, max = 1.0;
        for (int i = 0, dir = 0; i < N && i < depth; i++)
        {
            int j = (dir + 1 + i) % N;
            double mid = min + (max - min) * m_params[j];
            if (t < m_params[i])
            {
                dir += 1;
                t = t / m_params[i];
                max = mid;
            }
            else
            {
                dir ^= i;
                t = (t - m_params[i]) / (1.0 - m_params[i]);
                min = mid;
            }
        }
        t = (3.0 - 2.0 * t) * t * t; // Optional smoothing
        return min + (max - min) * t;
    }

    double m_params[N];
};

It could be made faster by pre-computing the floating point divisions, at the cost of storing three times as much information.

This is a quick example:

five different trajectories

The example was obtained with the following code:

for (int run = 0; run < 5; run++)
{
    /* Create a new shuffled trajectory */
    Trajectory<12> traj;

    /* Print dots */
    for (double t = 0; t <= 1.0; t += 0.0001)
        printf("%g %g\n", t, traj.Get(t));
}
share|improve this answer

Thinking out loud, and admitting calculus is not my strong point... is this perhaps not possible? To avoid any obvious pattern, the average of the noise function over any change in x must be close to zero, and to guarantee monotonicity the amplitude of noise over that change in x must be smaller than the change in x, as any larger amplitude could result in a lower value at x' relative to x. But that would mean that as you reduce dx towards 0, such a function must also reduce dA (where A is amplitude) towards zero, meaning you get no contribution from any compliant noise function.

I can imagine it being possible to formulate a function that gradually decreases the noise contribution as x approaches 1, but that will give you a curved function that decelerates as x approaches 1, which is not what I think you want.

share|improve this answer
1  
I can draw millions of graphs of such functions, and as SkimFlux says the integration of a noise function gives a practically equivalent function if you normalize it. So the functions exist, it's just a matter of whether they can be feasible coded. Hence asking here instead of math.se. –  user744 Mar 29 '12 at 12:47
    
For example, any function that decelerates as x approaches 1 has an equivalent "reversed" function g(x) = 1 - f(1 - x), which instead accelerates as x departs 0. –  user744 Mar 29 '12 at 12:53
    
Sure, the functions exist - you can draw one like teodron did - but are they 'noise' functions? Noise implies a continuous function based on pseudo-random input with an implicit amplitude relative to a baseline. And if that amplitude is too high then you can't guarantee the difference between steps is low enough to keep the output monotonic. But it does occur to me that the density of the noise and the interpolation step could be crafted to meet your specifications, which I'm going to think a bit more about. –  Kylotan Mar 29 '12 at 15:20
    
Noise just means it's "unpredictable", it says nothing about the generation methods (or even, technically, continuity, though for animation you do almost always want coherent noise). It's true that the fixed endpoints constrain this function's possible amplitude somewhat, but not entirely. Other noise functions have similar properties, e.g. Perlin(x) = 0 for any integer x. Monotonicity is a stronger guarantee than that, but I'm don't think it's so much stronger it makes it impossible. –  user744 Mar 29 '12 at 15:32
    
@JoeWreschnig I'm sure you are aware that the Perlin noise function blatantly violates several of your criteria. Firstly it passes through 0 at grid nodes so f(x+d)-f(x) is a constant multiple of d for some certain (regularly spaced) x. Additionally, because of that clever caching trick, it will repeat for large grids. For classic noise, I think the reference implementation is supposed to have grid tile (x, y) be identical to tile (x+256, y+256). You should state if this is acceptable, and to what extent. –  Superbest Mar 29 '12 at 22:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.