Apakah ada (derau) fungsi noise monotonik yang tidak berkurang?

Saya ingin fungsi untuk menghidupkan objek yang bergerak dari titik A ke titik B dari waktu ke waktu, sehingga mencapai B pada waktu tertentu, tetapi posisinya kapan saja secara acak terganggu secara terus-menerus, tetapi tidak pernah mundur. Objek bergerak sepanjang garis lurus, jadi saya hanya perlu satu dimensi.

Secara matematis, itu berarti saya mencari beberapa kontinu f (x), x ∈ [0,1], sehingga:

• f (0) = 0
• f (1) = 1
• x <y → f (x) ≤ f (y)
• Pada "sebagian besar" titik f (x + d) - f (x) tidak memiliki hubungan yang jelas dengan d. (Fungsi tidak meningkat secara seragam atau dapat diprediksi; saya pikir itu juga setara dengan mengatakan tidak ada derajat turunan yang konstan.)

Idealnya, saya sebenarnya ingin beberapa cara untuk memiliki keluarga fungsi-fungsi ini, menyediakan beberapa kondisi awal. Saya membutuhkan setidaknya 4 bit benih (16 fungsi yang mungkin), untuk penggunaan saya saat ini, tetapi karena itu tidak banyak merasa bebas untuk memberikan lebih banyak lagi.

Untuk menghindari berbagai masalah dengan akumulasi kesalahan, saya lebih suka fungsi ini tidak memerlukan kondisi internal apa pun. Artinya, saya ingin itu menjadi fungsi nyata, bukan "fungsi" pemrograman.

Untuk posting ini, y = f (t) di mana t adalah parameter yang Anda variasikan (waktu / kemajuan) dan y adalah jarak ke target. Jadi saya akan berbicara dalam hal titik pada plot 2D di mana sumbu horizontal adalah waktu / kemajuan dan vertikal adalah jarak.

Saya pikir Anda bisa membuat kurva Bezier kubik dengan titik pertama di (0, 1) dan keempat (terakhir) titik di (1, 0). Dua titik tengah dapat ditempatkan secara acak (x = rand, y = rand) dalam kotak 1-by-1 ini. Saya tidak dapat memverifikasi ini secara analitis, tetapi hanya dari bermain-main dengan applet (yeah, silakan saja dan tertawa) tampaknya kurva Bezier tidak akan pernah berkurang dengan kendala seperti itu.

Ini akan menjadi fungsi dasar Anda b (p1, p2) yang menyediakan jalur non-menurun dari titik p1 ke titik p2.

Sekarang Anda dapat menghasilkan ab (p (1) = (0, 1), p (n) = (1, 0)) dan memilih sejumlah p (i) sepanjang kurva ini sehingga 1

Pada dasarnya, Anda membuat satu jalur "umum", dan kemudian memecahnya menjadi segmen dan meregenerasi setiap segmen.

Karena Anda menginginkan fungsi matematika: Misalkan prosedur di atas dikemas ke dalam satu fungsi y = f (t, s) yang memberi Anda jarak pada t untuk fungsi seed s. Anda akan perlu:

• 4 angka acak untuk menempatkan 2 titik tengah dari spline Bezier utama (dari (0, 1) hingga (1, 0))
• nomor n-1 untuk batas setiap segmen jika Anda memiliki n segmen (segmen pertama selalu dimulai pada (0, 1) yaitu t = 0 dan ujung terakhir pada (1,0) yaitu t = 1)
• 1 angka jika Anda ingin mengacak jumlah segmen
• 4 angka lebih banyak untuk menempatkan titik tengah spline segmen tempat Anda akan t

Jadi setiap benih harus menyediakan salah satu dari yang berikut ini:

• 7 + n bilangan real antara 0 dan 1 (jika Anda ingin mengontrol jumlah segmen)
• 7 bilangan real dan satu bilangan bulat lebih besar dari 1 (untuk jumlah segmen acak)

Saya membayangkan Anda dapat mencapai salah satu dari ini dengan hanya menyediakan array angka sebagai benih. Atau, Anda bisa melakukan sesuatu seperti memasok satu angka s sebagai seed, dan kemudian memanggil generator angka acak bawaan dengan rand, rand (s + 1), rand (s + 2) dan sebagainya (atau menginisialisasi dengan s dan kemudian terus memanggil rand.NextNumber).

Perhatikan bahwa meskipun seluruh fungsi f (t, s) terdiri dari banyak segmen, Anda hanya mengevaluasi satu segmen untuk setiap t. Anda akan perlu berulang kali menghitung batas-batas segmen dengan metode ini, karena Anda akan harus menyortir mereka untuk memastikan tidak ada dua segmen tumpang tindih. Anda mungkin dapat mengoptimalkan dan menyingkirkan pekerjaan tambahan ini dan hanya menemukan titik akhir dari satu segmen untuk setiap panggilan, tetapi tidak jelas bagi saya saat ini.

Juga, kurva Bezier tidak diperlukan, spline berperilaku yang sesuai akan dilakukan.

Saya membuat contoh implementasi Matlab.

Fungsi Bezier (vektor):

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

Fungsi majemuk Bezier yang dijelaskan di atas (sengaja dibiarkan tidak terverifikasi untuk memperjelas berapa banyak evaluasi yang diperlukan untuk setiap panggilan):

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

Script yang memplot fungsi untuk seed acak (perhatikan bahwa ini adalah satu-satunya tempat di mana fungsi acak dipanggil, variabel acak ke semua kode lain disebarkan dari satu array acak ini):

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

Berikut ini contoh keluaran:

Tampaknya memenuhi sebagian besar kriteria Anda. Namun:

• Ada "sudut". Ini mungkin bisa diterima dengan menggunakan kurva Bezier lebih tepat.
• Ini "jelas" terlihat seperti splines, meskipun Anda tidak bisa menebak apa yang akan dilakukan setelah periode waktu yang tidak sepele kecuali Anda tahu benihnya.
• Sangat jarang menyimpang terlalu banyak ke sudut (dapat diperbaiki dengan bermain dengan distribusi generator benih).
• Fungsi Bezier kubik tidak dapat mencapai area dekat sudut mengingat kendala ini.

Saya kira bahwa alih-alih memadukan sekelompok cosinus yang ditransformasi (seperti yang diberikan produk titik dalam perlin noise), Anda dapat memadukan beberapa fungsi monoton yang dimulai dari f (0) = 0, seperti f (x) = x, atau 2x, atau x ^ 2, dll. Faktanya karena domain Anda terbatas pada 0 => 1, Anda juga dapat memadukan fungsi trigonometri yang sesuai dengan tagihan dalam domain tersebut seperti cos (90 * x + 270). Untuk menormalkan metode Anda hingga berakhir pada 1, Anda bisa membagi jumlah tertimbang dari metode monotonik ini mulai dari f (0) = 0 oleh f (1). Sesuatu seperti ini harusnya cukup mudah untuk dibalik juga (yang saya kumpulkan Anda inginkan dari sedikit tentang fungsi real stateless versus fungsi pemrograman).

Semoga ini membantu.

Orang dapat menganalisis gambar kasar ini. Anda dapat berakhir dengan fungsi yang menjalankan animasi Anda dengan cepat, dengan memanfaatkan fungsi rand yang seragam. Saya tahu ini bukan rumus matematika yang tepat, tetapi sebenarnya tidak ada rumus matematika untuk fungsi acak, dan bahkan jika ada, Anda akan banyak mengkode untuk mencapai ini. Mengingat Anda tidak menentukan kondisi kelancaran, profil kecepatannya adalah $ C ^ 0 $ terus menerus (tetapi karena Anda tidak berurusan dengan robot, tidak perlu khawatir tentang profil percepatan yang terputus-putus).

Cara yang biasa untuk menghasilkan urutan peningkatan angka acak N dari [0,1] adalah dengan menghasilkan angka acak N dalam rentang apa pun, kemudian membaginya semua dengan jumlah totalnya, kemudian menjumlahkannya satu per satu untuk mendapatkan urutan.

Hasilkan urutan 2, 2, 5, 8, 6.
Jumlah mereka adalah 23, jadi jumlah kami yang dijumlahkan adalah 2/23, 2/23, 5/23, 8/23, dan 6/23.
Urutan terakhir kami adalah 2/23, 4/23, 9/23, 17/23, 23/23

Ini dapat diperluas ke 2D dengan menghasilkan nilai-nilai ini untuk X dan Y. Anda dapat meningkatkan N untuk mendapatkan rincian yang Anda inginkan.

Dalam jawaban serupa @ teodron, Anda mengutip masalah efisiensi dengan skala waktu yang besar. Tanpa mengetahui masalah sebenarnya yang Anda hadapi, saya tidak bisa memastikan apakah kekhawatiran itu valid; tetapi opsi lain adalah menghasilkan untuk N kecil , dan hanya memperlancar hasilnya. Tergantung pada aplikasi, ini sebenarnya dapat memberikan hasil yang lebih baik .

N = 100, tidak ada smoothing

N = 15, dengan smoothing

Saya menyarankan implementasi ini terinspirasi oleh penjumlahan oktaf yang ditemukan dalam fraktal noise, dengan sedikit keledai murahan di sana-sini. Saya percaya ini cukup cepat dan dapat disetel dengan meminta oktaf lebih sedikit daripada disimpan dalam parameter dengan kehilangan presisi sekitar 1/2^octave.

Anda bisa melihatnya sebagai implementasi sedikit demi sedikit yang hanya membutuhkan waktu O (log (potongan)) . Array parameter digunakan baik untuk posisi pivot divide-and-conquer, dan untuk jarak yang ditempuh ketika mencapai 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];
};

Itu bisa dibuat lebih cepat dengan pra-komputasi divisi floating point, dengan biaya menyimpan informasi tiga kali lipat.

Ini adalah contoh cepat:

Contoh diperoleh dengan kode berikut:

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

Berpikir keras, dan mengakui kalkulus bukanlah poin kuat saya ... apakah ini mungkin tidak mungkin? Untuk menghindari pola yang jelas, rata-rata fungsi noise atas setiap perubahan dalam x harus mendekati nol, dan untuk menjamin monotonitas, amplitudo noise dari perubahan dalam x harus lebih kecil daripada perubahan dalam x, karena amplitudo yang lebih besar dapat menghasilkan nilai yang lebih rendah pada x 'relatif terhadap x. Tapi itu berarti bahwa ketika Anda mengurangi dx ke 0, fungsi seperti itu juga harus mengurangi dA (di mana A adalah amplitudo) menuju nol, yang berarti Anda tidak mendapatkan kontribusi dari fungsi kebisingan yang sesuai.

Saya bisa membayangkan itu mungkin untuk merumuskan fungsi yang secara bertahap mengurangi kontribusi kebisingan sebagai x mendekati 1, tetapi itu akan memberi Anda fungsi melengkung yang melambat ketika x mendekati 1, yang bukan apa yang saya pikir Anda inginkan.