Czy istnieje (rodzina) monotonicznie nie zmniejszających się funkcji hałasu?

Chciałbym, aby funkcja animowała obiekt przemieszczający się z punktu A do punktu B w czasie, tak że osiąga on B w pewnym ustalonym czasie, ale jego pozycja w dowolnym momencie jest losowo zaburzona w sposób ciągły, ale nigdy nie wraca. Obiekty poruszają się wzdłuż linii prostych, więc potrzebuję tylko jednego wymiaru.

Matematycznie oznacza to, że szukam ciągłych f (x), x ∈ [0,1], takich jak:

• f (0) = 0
• f (1) = 1
• x <y → f (x) ≤ f (y)
• W „większości” punktów f (x + d) - f (x) nie ma oczywistego związku z d. (Funkcja nie jest równomiernie rosnąca ani w inny sposób przewidywalna; myślę, że jest to również równoważne z twierdzeniem, że żaden stopień pochodnej nie jest stały).

Idealnie, chciałbym w jakiś sposób mieć rodzinę tych funkcji, zapewniającą trochę stanu początkowego. Potrzebowałbym co najmniej 4 bitów nasion (16 możliwych funkcji), do mojego obecnego użytku, ale ponieważ nie jest to zbyt wiele przyjemności, aby zapewnić jeszcze więcej.

Aby uniknąć różnych problemów z błędami akumulacji, wolałbym, aby funkcja nie wymagała żadnego rodzaju stanu wewnętrznego. To znaczy, chcę, żeby była to prawdziwa funkcja, a nie „funkcja” programowania.

W tym poście y = f (t), gdzie t jest zmiennym parametrem (czas / postęp), ay jest odległością do celu. Będę mówić o punktach na wykresach 2D, w których oś pozioma to czas / postęp, a pion to odległość.

Myślę, że możesz zrobić sześcienną krzywą Beziera z pierwszym punktem w (0, 1) i czwartym (ostatnim) punktem w (1, 0). Dwa środkowe punkty mogą być losowo umieszczone (x = rand, y = rand) w tym prostokącie 1 na 1. Nie jestem w stanie zweryfikować tego analitycznie, ale po prostu bawię się apletem (tak, śmiej się), wydaje się, że krzywa Beziera nigdy nie zmniejszy się z takim ograniczeniem.

Będzie to twoja elementarna funkcja b (p1, p2), która zapewnia nie malejącą ścieżkę od punktu p1 do punktu p2.

Teraz możesz wygenerować ab (p (1) = (0, 1), p (n) = (1, 0)) i wybrać liczbę p (i) wzdłuż tej krzywej, tak aby 1

Zasadniczo generujesz jedną „ogólną” ścieżkę, a następnie dzielisz ją na segmenty i regenerujesz każdy segment.

Ponieważ potrzebujesz funkcji matematycznej: Załóżmy, że powyższa procedura jest spakowana w jedną funkcję y = f (t, s), która daje odległość w t dla funkcji nasion s. Będziesz potrzebować:

• 4 losowe liczby do umieszczenia 2 środkowych punktów głównego splajnu Beziera (od (0, 1) do (1, 0))
• liczby n-1 dla granic każdego segmentu, jeśli masz n segmentów (pierwszy segment zawsze zaczyna się od (0, 1) tj. t = 0, a ostatni kończy się na (1,0) tj. t = 1)
• 1 liczba, jeśli chcesz losowo wybrać liczbę segmentów
• 4 dodatkowe liczby do umieszczenia środkowych punktów splajnu odcinka, na który wyląduje t

Dlatego każde ziarno musi dostarczyć jedno z poniższych:

• 7 + n liczb rzeczywistych od 0 do 1 (jeśli chcesz kontrolować liczbę segmentów)
• 7 liczb rzeczywistych i jedna liczba całkowita większa niż 1 (dla losowej liczby segmentów)

Wyobrażam sobie, że możesz to osiągnąć, podając po prostu tablicę liczb jako nasion. Alternatywnie, możesz zrobić coś takiego jak podać jedną liczbę s jako ziarno, a następnie wywołać wbudowany generator liczb losowych za pomocą rand (s), rand (s + 1), rand (s + 2) i tak dalej (lub zainicjować za pomocą s, a następnie nadal dzwonić rand.NextNumber).

Zauważ, że chociaż cała funkcja f (t, s) składa się z wielu segmentów, oceniasz tylko jeden segment dla każdego t. Państwo będzie musiał wielokrotnie obliczać granice segmentów z tej metody, ponieważ trzeba będzie uporządkować je, aby upewnić się nie ma dwóch segmentów zachodzą na siebie. Prawdopodobnie możesz zoptymalizować i pozbyć się tej dodatkowej pracy i znaleźć tylko punkty końcowe jednego segmentu dla każdego połączenia, ale nie jest to dla mnie teraz oczywiste.

Ponadto krzywe Beziera nie są konieczne, wystarczy odpowiednio zachowujący splajn.

Stworzyłem przykładową implementację Matlaba.

Funkcja Beziera (wektoryzowana):

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

Opisana powyżej złożona funkcja Beziera (celowo pozostawiona bez wektoryzacji, aby wyjaśnić, ile oceny jest potrzebne dla każdego połączenia):

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

Skrypt, który wykreśla funkcję losowego ziarna (zauważ, że jest to jedyne miejsce, w którym wywoływana jest funkcja losowa, zmienne losowe do wszystkich innych kodów są propagowane z tej jednej losowej tablicy):

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

Oto przykładowy wynik:

Wygląda na to, że spełnia większość twoich kryteriów. Jednak:

• Są „rogi”. Można to poprawić, stosując bardziej odpowiednie krzywe Beziera.
• „Oczywiście” wygląda jak splajny, chociaż tak naprawdę nie możesz zgadnąć, co zrobi po nietrywialnym czasie, chyba że znasz ziarno.
• Bardzo rzadko odchyla się zbytnio w stronę narożnika (można to naprawić, grając z rozkładem generatora nasion).
• Sześcienna funkcja Beziera nie może dotrzeć do obszaru w pobliżu rogu, biorąc pod uwagę te ograniczenia.

Wydaje mi się, że zamiast mieszać kilka transformowanych cosinusów (jak dają ci produkty kropkowe w szumie perlin), możesz mieszać kilka funkcji monotonicznych, które zaczynają się od f (0) = 0, np. F (x) = x lub 2x, lub x ^ 2, itd. W rzeczywistości, ponieważ twoja domena jest ograniczona do 0 => 1, możesz również łączyć funkcje trig, które pasują do rachunku w tej domenie, takie jak cos (90 * x + 270). Aby znormalizować metody kończące się na 1, możesz po prostu podzielić ważoną sumę tych metod monotonicznych zaczynając od f (0) = 0 przez f (1). Coś takiego powinno również być dość łatwe do odwrócenia (które, jak rozumiem, chcesz z części o bezpaństwowych funkcjach rzeczywistych kontra funkcjach programowania).

Mam nadzieję że to pomoże.

Można przeanalizować ten prymitywny obraz. Można uzyskać funkcję, która wykonuje animację w locie, wykorzystując jednolitą funkcję rand. Wiem, że nie jest to dokładna formuła matematyczna, ale tak naprawdę nie ma formuły matematycznej dla funkcji losowej, a nawet gdyby istniała, wiele byś napisał, aby to osiągnąć. Biorąc pod uwagę, że nie określono żadnych warunków płynności, profil prędkości ma ciągłą wartość $ C ^ 0 $ (ale ponieważ nie masz do czynienia z robotami, nie musisz martwić się o nieciągłe profile przyspieszenia).

Zwykłym sposobem generowania rosnącej sekwencji N liczb losowych z [0,1] jest wygenerowanie N liczb losowych w dowolnym zakresie, następnie podziel je wszystkie przez ich całkowitą sumę, a następnie zsumuj je pojedynczo, aby uzyskać sekwencja.

Wygeneruj sekwencję 2, 2, 5, 8, 6.
Ich suma wynosi 23, więc nasze sumy to 2/23, 2/23, 5/23, 8/23 i 6/23.
Nasza ostatnia sekwencja to 2/23, 4/23, 9/23, 17/23, 23/23

Można to rozszerzyć na 2D, generując te wartości zarówno dla X, jak i Y. Możesz zwiększyć N, aby uzyskać dowolną szczegółowość.

W podobnej odpowiedzi @ teodron przytoczyłeś obawy dotyczące wydajności w dużych skalach czasowych. Nie znając rzeczywistego problemu, przed którym stoisz, nie mogę stwierdzić, czy ta obawa jest uzasadniona; ale inną opcją byłoby wygenerowanie dla małego N i po prostu wygładzenie wyniku. W zależności od zastosowania może to faktycznie dać lepsze wyniki.

N = 100, bez wygładzania

N = 15, z wygładzaniem

Proponuję tę implementację zainspirowaną sumą oktaw znalezionych we fraktalnym hałasie, z odrobiną taniego tasowania w tyłku tu i tam. Uważam, że jest dość szybki i można go dostroić, prosząc o mniej oktaw niż zapisanych w parametrach z utratą precyzji około 1/2^octave.

Można to uznać za implementację częściową, która wymaga tylko czasu O (log (kawałki)) . Tablica parametrów jest używana zarówno dla pozycji przestawnej „dziel i rządź”, jak i dla odległości przebytej przy osiągnięciu punktu obrotu.

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

Można to przyspieszyć, wstępnie obliczając podziały zmiennoprzecinkowe, kosztem przechowywania trzykrotnie większej ilości informacji.

To jest szybki przykład:

Przykład uzyskano z następującego kodu:

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

Myślenie na głos i przyznawanie rachunku różniczkowego nie jest moją mocną stroną ... czy to może nie jest możliwe? Aby uniknąć jakiegokolwiek oczywistego wzorca, średnia funkcji szumu dla każdej zmiany x musi być bliska zeru, a dla zagwarantowania monotoniczności amplituda szumu dla tej zmiany x musi być mniejsza niż zmiana x, ponieważ każda większa amplituda mogłaby skutkować niższą wartością przy x 'względem x. Oznaczałoby to jednak, że w miarę zmniejszania dx do 0, funkcja taka musi również zmniejszać dA (gdzie A jest amplitudą) do zera, co oznacza, że ​​nie otrzymujesz żadnego wkładu z żadnej zgodnej funkcji szumu.

Mogę sobie wyobrazić, że można sformułować funkcję, która stopniowo zmniejsza udział hałasu, gdy x zbliża się do 1, ale da ci zakrzywioną funkcję, która zwalnia, gdy x zbliża się do 1, co nie jest tym, co myślę, że chcesz.