Существует ли (семейство) монотонно неубывающая шумовая функция (и)?

Мне бы хотелось, чтобы функция оживляла объект, перемещающийся из точки A в точку B с течением времени, так что он достигает B в какое-то фиксированное время, но его положение в любое время беспорядочно изменяется беспрерывно, но никогда не движется назад. Объекты движутся по прямым линиям, поэтому мне нужно только одно измерение.

Математически это означает, что я ищу некоторый непрерывный f (x), x ∈ [0,1], такой что:

• f (0) = 0
• f (1) = 1
• x <y → f (x) ≤ f (y)
• В «большинстве» точек f (x + d) - f (x) не имеет очевидного отношения к d. (Функция не является равномерно возрастающей или иным образом предсказуемой; я думаю, это также эквивалентно тому, что степень производной не является константой.)

В идеале мне бы хотелось, чтобы какой-то способ имел семейство этих функций, обеспечивающих некоторое начальное состояние. Мне нужно по крайней мере 4 бита (16 возможных функций) для моего текущего использования, но так как это не так много, можете предложить еще больше.

Чтобы избежать различных проблем с ошибками накопления, я бы предпочел, чтобы функция не требовала какого-либо внутреннего состояния. То есть я хочу, чтобы это была реальная функция, а не «функция» программирования.

Для этого поста y = f (t), где t - параметр, который вы меняете (время / прогресс), а y - расстояние до цели. Поэтому я буду говорить с точки зрения точек на двухмерных графиках, где горизонтальная ось - это время / прогресс, а вертикальная - это расстояние.

Я думаю, что вы можете сделать кубическую кривую Безье с первой точкой в ​​(0, 1) и четвертой (последней) точкой в ​​(1, 0). Две средние точки могут быть расположены случайным образом (x = rand, y = rand) в этом прямоугольнике 1 на 1. Я не могу проверить это аналитически, но, просто поиграв с апплетом (да, продолжайте смеяться), кажется, что кривая Безье никогда не уменьшится при таком ограничении.

Это будет ваша элементарная функция b (p1, p2), которая обеспечивает неубывающий путь от точки p1 к точке p2.

Теперь вы можете сгенерировать ab (p (1) = (0, 1), p (n) = (1, 0)) и выбрать число p (i) вдоль этой кривой так, чтобы 1

По сути, вы генерируете один «общий» путь, а затем разбиваете его на сегменты и восстанавливаете каждый сегмент.

Поскольку вам нужна математическая функция: предположим, что описанная выше процедура упакована в одну функцию y = f (t, s), которая дает вам расстояние в точке t для функции seed s. Тебе понадобится:

• 4 случайных числа для размещения 2 средних точек основного сплайна Безье (от (0, 1) до (1, 0))
• n-1 число для границ каждого сегмента, если у вас есть n сегментов (первый сегмент всегда начинается в (0, 1), т.е. t = 0, а последний заканчивается в (1,0), т.е. t = 1)
• 1 число, если вы хотите рандомизировать количество сегментов
• Еще 4 числа для размещения средних точек сплайна сегмента, в который вы попали

Таким образом, каждое семя должно обеспечивать одно из следующего:

• 7 + n действительных чисел от 0 до 1 (если вы хотите контролировать количество сегментов)
• 7 действительных чисел и одно целое число больше 1 (для случайного числа сегментов)

Я полагаю, что вы можете выполнить любой из них, просто указав в качестве начального числа массив чисел. В качестве альтернативы вы можете сделать что-то вроде предоставления одного числа s в качестве начального числа, а затем вызвать встроенный генератор случайных чисел с помощью rand (s), rand (s + 1), rand (s + 2) и т. Д. (Или инициализировать с помощью и затем продолжайте вызывать rand.NextNumber).

Обратите внимание, что, хотя вся функция f (t, s) состоит из множества сегментов, вы оцениваете только один сегмент для каждого t. Вам будет необходимо повторно вычислить границы сегментов с помощью этого метода, потому что вам придется сортировать их , чтобы убедиться , что никакие два сегмента перекрываются. Вероятно, вы можете оптимизировать и избавиться от этой дополнительной работы и найти только конечные точки одного сегмента для каждого вызова, но это не очевидно для меня сейчас.

Кроме того, кривые Безье не нужны, подойдет любой подходящий сплайн.

Я создал образец реализации Matlab.

Функция Безье (векторизация):

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

Составная функция Безье, описанная выше (намеренно оставлена ​​безвекторной, чтобы прояснить, сколько оценки требуется для каждого вызова):

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

Скрипт, который строит функцию для случайного начального числа (обратите внимание, что это единственное место, где вызывается случайная функция, случайные переменные для всего остального кода распространяются из этого одного случайного массива):

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');

Вот пример вывода:

Кажется, соответствует большинству ваших критериев. Однако:

• Есть "углы". Это может быть исправлено с помощью более подходящих кривых Безье.
• Это «очевидно» выглядит как сплайны, хотя вы не можете точно догадаться, что он будет делать после нетривиального периода времени, если вы не знаете семя.
• Он очень редко отклоняется слишком сильно к углу (это можно исправить, играя с распределением генератора семян).
• Кубическая функция Безье не может достичь области вблизи угла с учетом этих ограничений.

Я предполагаю, что вместо смешивания нескольких преобразованных косинусов (как дают точечные произведения в перлин-шуме), вы можете смешать несколько монотонных функций, которые начинаются с f (0) = 0, например, f (x) = x или 2x, или x ^ 2 и т. д. На самом деле, поскольку ваш домен ограничен 0 => 1, вы также можете смешивать триггерные функции, которые соответствуют требованиям, в этом домене, например, cos (90 * x + 270). Чтобы нормализовать методы, заканчивающиеся на 1, вы можете просто разделить взвешенную сумму этих монотонных методов, начинающихся с f (0) = 0, на f (1). Нечто подобное должно быть довольно легко также инвертировать (что, как я понимаю, вы хотите из битов о реальных функциях без сохранения состояния по сравнению с функциями программирования).

Надеюсь это поможет.

Можно проанализировать эту грубую картину. Вы можете получить функцию, которая выполняет анимацию на лету, используя унифицированную функцию rand. Я знаю, что это не точная математическая формула, но на самом деле нет математической формулы для случайной функции, и даже если бы она была, вы бы много программировали, чтобы достичь этого. Учитывая, что вы не указали никаких условий сглаживания, профиль скорости является непрерывным $ C ^ 0 $ (но поскольку вы не имеете дело с роботами, не нужно беспокоиться о прерывистых профилях ускорения).

Обычный способ генерирования возрастающей последовательности из N случайных чисел из [0,1] состоит в том, чтобы сгенерировать N случайных чисел в любом диапазоне, затем разделить их все на их общую сумму, а затем сложить их по одному за раз, чтобы получить последовательность.

Генерация последовательности 2, 2, 5, 8, 6.
Их сумма равна 23, поэтому наши числа для суммирования: 2/23, 2/23, 5/23, 8/23 и 6/23.
Наша последняя последовательность: 2/23, 4/23, 9/23, 17/23, 23/23

Это может быть расширено до 2D путем генерации этих значений для X и Y. Вы можете увеличить N, чтобы получить любую гранулярность, которую вы хотите.

В аналогичном ответе @ teodron вы привели проблемы эффективности с большими временными масштабами. Не зная реальной проблемы, с которой вы сталкиваетесь, я не могу сказать, обоснована ли эта проблема; но другой вариант будет генерировать для малого N и просто сгладить результат. В зависимости от приложения, это может дать лучшие результаты.

N = 100, без сглаживания

N = 15, со сглаживанием

Я предлагаю эту реализацию, вдохновленную суммированием октав, найденных в фрактальном шуме, с небольшим количеством дешевой задницы, шаркающей здесь и там. Я считаю, что это достаточно быстро и может быть настроено, запрашивая меньше октав, чем хранится в параметрах с потерей точности около 1/2^octave.

Вы можете видеть это как кусочную реализацию, которая требует только O (log (куски)) времени. Массив параметров используется как для позиции поворота «разделяй и властвуй», так и для расстояния, пройденного при достижении точки поворота.

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];
};

Это можно сделать быстрее, предварительно вычислив деления с плавающей запятой, за счет хранения в три раза больше информации.

Это быстрый пример:

Пример был получен с помощью следующего кода:

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));
}

Мышление вслух и признание исчисления не моя сильная сторона ... разве это возможно? Чтобы избежать какой-либо очевидной закономерности, среднее значение шумовой функции по любому изменению x должно быть близко к нулю, и для обеспечения монотонности амплитуда шума по сравнению с этим изменением x должна быть меньше, чем изменение x, поскольку любая большая амплитуда может привести к более низкому значению в х 'относительно х. Но это будет означать, что когда вы уменьшаете dx до 0, такая функция также должна уменьшать dA (где A - амплитуда) до нуля, а это означает, что вы не получите никакого вклада от любой соответствующей функции шума.

Я могу представить себе возможность сформулировать функцию, которая постепенно уменьшает вклад шума, когда x приближается к 1, но это даст вам изогнутую функцию, которая замедляется при приближении x к 1, что, как я думаю, вам не нужно.