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 = [
p = coeffs * points;
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));
p = bezier(t_seg, p_seg);
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):
% How many samples of the function to plot (higher = higher resolution)
points = 1000;
ends = [
% a row vector of 12 random points
r = rand(1, 12);
p = zeros(points, 2);
t = i/points;
p(i+1, :) = bezier_compound(t, ends, r);
% 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), '.');
ylabel('Distance to target');
Here's a sample output:
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.