Memindahkan kapal antara dua planet di sepanjang bezier, kehilangan beberapa persamaan untuk akselerasi

OK, saya sudah memposting ini di math.stackechange.com tetapi tidak mendapatkan jawaban :(

Pertama di sini adalah gambar masalah saya, uraian berikut setelahnya:

Jadi saya mengatur semua poin dan nilai.

Kapal mulai bergerak di sekitar planet kiri P1dengan S=0.27 Degreesper gametick, ketika mencapai Point Aitu mulai mengikuti kurva bezier sampai mencapai Point D, kemudian bergerak di sekitar planet kanan P2dengan S=0.42 Degreesper centang game. Perbedaannya Sadalah agar perjalanan dengan kecepatan gerakan yang sama di sekitar planet.

Sejauh ini bagus, saya bisa menjalankannya, sekarang masalah saya.

Kapan S P1dan sangat S P2berbeda, kapal melompat di antara dua kecepatan ketika mencapai tujuan itu, yang terlihat sangat buruk. Jadi saya perlu mempercepat kapal antara Point Adan Point Ddari S P1ke S P2.

Hal yang saya lewatkan berwarna ungu, yaitu:

• Cara untuk menghitung kutu diperlukan kapal untuk bergerak di sepanjang bezier dengan mempertimbangkan akselerasi.

• Dan cara untuk menemukan posisi pada kurva bezier berdasarkan T, sekali lagi mempertimbangkan akselerasi.

ATM Saya menghitung panjang bezier dengan menghitung jarak antara Ntitik-titiknya. Jadi apa yang saya pikir saya butuhkan, adalah cara untuk skala Tsaya perlu dimasukkan ke dalam perhitungan bezier saya sesuai dengan percepatan

OK, saya punya semuanya berfungsi, butuh selamanya, jadi saya akan memposting solusi rinci saya di sini.
Catatan: Semua sampel kode dalam JavaScript.

Jadi mari kita uraikan masalahnya menjadi beberapa bagian dasar:

1. Anda harus menghitung panjangnya, serta titik-titik di antara 0..1kurva bezier

2. Anda sekarang perlu menyesuaikan skala Anda Tuntuk mempercepat kapal dari satu kecepatan ke kecepatan lain

Memperbaiki Bezier dengan benar

Menemukan beberapa kode untuk menggambar kurva Bezier itu mudah, ada beberapa pendekatan yang berbeda, salah satunya adalah Algoritma DeCasteljau , tetapi Anda juga bisa menggunakan persamaan untuk kurva Bézier kubik:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;
}

Dengan ini, satu sekarang dapat menggambar kurva bezier dengan menelepon xdan ydengan tyang berkisar dari 0 to 1, mari kita lihat:

Eh ... itu bukan benar-benar distribusi poin, kan?
Karena sifat kurva Bézier, titik-titik pada 0...1memiliki perbedaan arc lenghts, sehingga segmen di dekat awal dan akhir, lebih panjang daripada yang dekat dengan tengah kurva.

Memetakan T secara merata pada kurva parameterisasi panjang busur AKA

Jadi apa yang harus dilakukan? Nah secara sederhana kita membutuhkan fungsi untuk memetakan kita Tke tkurva, sehingga T 0.25hasil tkita berada 25%pada panjang kurva.

Bagaimana kita melakukannya? Baiklah, kami Google ... tetapi ternyata istilah itu tidak dapat diunduh dari Google , dan pada titik tertentu Anda akan menemukan PDF ini . Yang pasti adalah bacaan yang bagus, tetapi jika Anda sudah lupa semua hal matematika yang Anda pelajari di sekolah (atau Anda tidak suka simbol-simbol matematika) itu sangat tidak berguna.

Apa sekarang? Baiklah dan Google lagi (baca: 6 jam), dan Anda akhirnya menemukan artikel yang bagus tentang topik tersebut (termasuk gambar yang bagus! ^ _ ^ "):
Http://www.planetclegg.com/projects/WarpingTextToSplines.html

Melakukan kode yang sebenarnya

Jika Anda tidak bisa menolak mengunduh PDF itu meskipun Anda sudah kehilangan pengetahuan matematis Anda sejak dulu, dan Anda berhasil melewati tautan artikel yang hebat , Anda mungkin sekarang berpikir: "Ya Tuhan, ini akan membutuhkan ratusan baris kode dan berton-ton CPU "

Tidak, tidak akan. Karena kami melakukan apa yang semua programmer lakukan, ketika sampai pada soal matematika:
Kami hanya curang.

Parameterisasi panjang busur, cara malas

Mari kita hadapi itu, kita tidak perlu ketelitian tanpa akhir dalam permainan kita, bukan? Jadi kecuali Anda bekerja di NASA dan berencana mengirim orang-orang Mars, Anda tidak akan membutuhkan 0.000001 pixelsolusi yang sempurna.

Jadi bagaimana kita memetakan Tke t? Ini sederhana dan hanya terdiri dari 3 langkah:

1. Hitung Ntitik pada kurva menggunakan tdan menyimpan arc-length(alias panjang kurva) pada posisi itu ke dalam array

2. Untuk memetakan Tke t, yang pertama kali Tdengan total panjang kurva untuk mendapatkan udan kemudian mencari array panjang untuk indeks dari nilai terbesar yang lebih kecil dariu

3. Jika kami memiliki hit yang tepat, kembalikan nilai array pada indeks itu dibagi dengan N, jika tidak menginterpolasi sedikit antara titik yang kami temukan dan yang berikutnya, bagi hal itu sekali lagi dengan Ndan kembali.

Itu saja! Jadi sekarang mari kita lihat kode lengkapnya:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;

    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

Ini menginisialisasi kurva baru kami dan menghitung arg-lenghts, itu juga menyimpan yang terakhir dari panjang sebagai total lengthkurva, faktor kunci di sini adalah this.lenyang kami N. Semakin tinggi, semakin akurat pemetaannya, karena kurva ukuran pada gambar di atas 100 pointstampaknya sudah cukup, jika Anda hanya perlu perkiraan panjang yang baik, sesuatu seperti 25sudah akan melakukan pekerjaan dengan hanya memiliki 1 pixel di contoh, tetapi kemudian Anda akan memiliki pemetaan yang kurang tepat yang akan menghasilkan distribusi tidak merata Tsaat dipetakan ke t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;

            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];
        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));
    },

    my: function (u) {
        return this.y(this.map(u));
    },

Kode pemetaan yang sebenarnya, pertama-tama kita lakukan sederhana binary searchpada panjang yang disimpan untuk menemukan panjang terbesar yang lebih kecil targetLength, lalu kita kembali atau melakukan interpolasi dan kembali.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x
               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }
};

Sekali lagi ini menghitung tpada kurva.

Waktunya untuk hasil

Dengan sekarang menggunakan mxdan myAnda mendapatkan merata Tpada kurva :)

Bukankah itu sulit, bukan? Sekali lagi, ternyata solusi sederhana (walaupun bukan solusi sempurna) akan cukup untuk sebuah gim.

Jika Anda ingin melihat kode lengkap, ada inti yang tersedia:
https://gist.github.com/670236

Akhirnya, mempercepat kapal

Jadi yang tersisa sekarang adalah mempercepat kapal di sepanjang jalurnya, dengan memetakan posisi Tyang akan kita gunakan untuk menemukan tkurva kita.

Pertama kita perlu dua persamaan gerak , yaitu ut + 1/2at²dan(v - u) / t

Dalam kode aktual yang akan terlihat seperti ini:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Kemudian kami menurunkannya 0...1dengan melakukan:

maxPosition = 0.5 * acceleration + startSpeed;
newT = 1 / maxPosition * position;

Dan begitulah, kapal sekarang bergerak dengan lancar di sepanjang jalan.

Jika tidak berfungsi ...

Ketika Anda membaca ini, semuanya bekerja dengan baik dan keren, tetapi saya awalnya memiliki beberapa masalah dengan bagian akselerasi, ketika menjelaskan masalah tersebut kepada seseorang di ruang obrolan gamedev, saya menemukan kesalahan terakhir dalam pemikiran saya.

Jika Anda belum lupa tentang gambar dalam pertanyaan asli, saya sebutkan di ssana, ternyata itu sadalah kecepatan dalam derajat , tetapi kapal-kapal bergerak di sepanjang jalan dalam piksel dan saya lupa tentang fakta itu. Jadi yang perlu saya lakukan dalam hal ini adalah mengubah perpindahan dalam derajat menjadi perpindahan dalam piksel, ternyata ini lebih mudah:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;
    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

Jadi itu saja! Terima kasih sudah membaca ;)

Masalahnya adalah bahwa kapal tidak akan mengambil lintasan itu secara alami. Jadi, meskipun bekerja dengan sempurna, tetap saja tidak akan terlihat benar.

Jika Anda ingin mensimulasikan transisi yang mulus antar planet, saya akan menyarankan untuk memodelkannya. Persamaannya sangat sederhana karena Anda hanya memiliki dua kekuatan signifikan: gravitasi, dan daya dorong.

Anda hanya perlu mengatur konstanta Anda: Massa P1, P2, kirim

Dengan setiap centang game (waktu: t) Anda melakukan 3 hal

1. Hitung gravitasi p1 di kapal dan p2 di kapal, tambahkan vektor yang dihasilkan ke vektor dorong.

2. Hitung kecepatan baru Anda berdasarkan akselerasi baru Anda dari langkah 1

3. Pindahkan kapal sesuai dengan kecepatan baru Anda

Mungkin tampak seperti banyak pekerjaan tetapi dapat dilakukan dalam selusin baris kode dan akan terlihat sangat alami.

Jika Anda perlu bantuan dengan fisika, beri tahu saya.

Saya menemukan artikel yang bagus menjelaskan kemungkinan solusi untuk masalah ini dengan contoh kode yang ditulis dalam javascript. Ini bekerja dengan "mendorong nilai t" ke arah yang benar.

Sebagai gantinya, kita dapat menggunakan fakta bahwa panjang kaki rata-rata d_avg untuk setiap distribusi titik hampir identik dengan panjang kaki yang akan dihasilkan oleh titik-titik dengan jarak yang sama (kesamaan ini meningkat dengan n bertambah). Jika kita menghitung selisih d_err antara panjang kaki aktual d dan panjang kaki rata-rata d_avg, maka parameter waktu t yang terkait dengan setiap titik dapat didorong untuk mengurangi perbedaan ini.

Pertanyaan ini sudah memiliki banyak jawaban keren, tetapi saya menemukan solusi ini layak diperhatikan.

Terima kasih atas halaman hebat Anda yang menjelaskan bagaimana Anda memecahkan masalah ini. Saya melakukan sesuatu yang agak berbeda dari Anda dalam satu detail, karena saya sangat terkandung dalam memori: Saya tidak membangun sebuah array, atau harus mencarinya untuk 'segmen' yang tepat dengan pencarian biner. Ini karena saya selalu tahu saya bergerak dari satu ujung kurva Bezier saya ke yang lain: Oleh karena itu, saya hanya mengingat segmen 'saat ini', dan jika saya melihat bahwa saya akan keluar dari batas-batas segmen tersebut untuk menghitung berikutnya posisi, saya menghitung segmen berikutnya (atau sebelumnya) (berdasarkan arah perjalanan.) Ini berfungsi dengan baik untuk aplikasi saya. Satu-satunya kesalahan yang harus saya selesaikan adalah, dalam beberapa kurva, ukuran segmennya sangat kecil sehingga plot berikutnya yang saya tunjukkan adalah - pada waktu yang jarang - lebih dari satu segmen di depan yang sekarang, jadi alih-alih hanya pergi ke '

Tidak tahu apakah ini cukup masuk akal, tetapi ini tentu membantu saya.

Pemodelan semacam itu aneh, dan dapat menghasilkan hasil yang tidak masuk akal aneh. Apalagi jika kecepatan planet mulai benar-benar lambat.

Model kapal dengan daya dorong.

Ketika kapal berada di orbit terakhir mereka di planet awal, berakselerasi dengan penuh.

Ketika kapal berada dalam jarak tertentu, gunakan dorongan terbalik untuk memperlambat kapal ke kecepatan orbit planet target.

Sunting: Lakukan seluruh simulasi sekaligus ketika sebuah simpul hendak meninggalkan orbit. baik mengirim semua data, atau mengirim hanya beberapa vektor gerakan pada interval, dan interpolasi di antara mereka.

Jika saya memahaminya dengan benar, masalah Anda terlalu dibatasi.

Saya percaya bahwa Anda ingin pesawat ruang angkasa untuk melakukan perjalanan di sepanjang jalur yang ditentukan antara orbit dalam beberapa waktu t , dan Anda juga ingin itu mempercepat dari kecepatan s1 ke kecepatan s2 dalam waktu yang sama t . Sayangnya, Anda tidak dapat (secara umum) menemukan akselerasi yang memenuhi kedua kendala ini secara bersamaan.

Anda harus sedikit merilekskan masalah Anda untuk menyelesaikannya.

Saya menemukan jawaban ini karena saya mencari untuk mendistribusikan poin secara merata di sepanjang jalur svg yang menggunakan kurva bezier.

Meskipun MDN mengatakan itu sudah usang, Anda dapat menggunakan path.getPointAtLengthuntuk mendapatkan hasil yang benar. https://developer.mozilla.org/en-US/docs/Web/API/SVGPathElement/getPointAtLength

Saat ini berfungsi di Chrome / Safari / Firefox, dan seharusnya bekerja di IE / Edge juga, tetapi saya tidak memverifikasi mereka 2.

Masalah dengan solusi yang diterima

Karena Bezier merupakan fungsi eksponensial , kami mengharapkan tingkat kemajuan yang berbeda di berbagai area kurva.

Karena solusi Ivo secara linear menginterpolasi antara sampel eksponensial awal ini , ketidakakuratan akan sangat bias terhadap ujung / tengah kurva (biasanya kubik) di mana delta-delta itu terbesar; jadi kecuali laju sampel Nmeningkat sangat seperti yang disarankannya, kesalahan tampak jelas, dan pada tingkat zoom tertentu, akan selalu terlihat jelas untuk yang diberikan N, yaitu bias bersifat intrinsik untuk algoritma itu. Tidak bagus untuk misalnya grafik berbasis vektor di mana zoom mungkin tidak terbatas.

Melawan bias melalui sampling terpandu

Sebuah solusi alternatif adalah untuk remap linear distanceuntuk tsetelah melawan bias alam yang fungsi Bezier menghasilkan.

Dengan asumsi inilah yang kami inginkan:

curve length = 10

t      distance
0.2    2
0.4    4
0.6    6
0.8    8
1.0    10

tapi inilah yang kami dapatkan dari fungsi posisi Bezier:

t      distance
0.2    0.12
0.4    1.22
0.6    2.45
0.8    5.81
1.0    10.00

Dengan melihat Nsampel yang diambil, kita dapat melihat di mana jarak delta terbesar, dan resample ("split") di tengah-tengah antara dua jarak yang berdekatan, meningkat Nsebesar 1. Misalnya, membelah pada t=0.9(yang merupakan tengah di delta terbesar), kita mungkin mendapatkan:

0.8    5.81
0.9    7.39
1.0    10.00

Kami mengulangi proses ini untuk interval jarak terbesar berikutnya sampai delta maksimum antara dua jarak di seluruh rangkaian berada di bawah beberapa minDistanceDelta, dan lebih khusus, kurang epsilondari jarak tertentu yang ingin kami petakan ke langkah-langkah t; kita kemudian dapat memetakan tlangkah-langkah yang diinginkan secara linear ke distances yang sesuai . Ini menghasilkan hashtable / peta yang bisa Anda akses dengan murah dan yang nilainya Anda dapat lerp di antara, saat runtime, tanpa bias.

Ketika set tumbuh N, biaya untuk mengulangi ini meningkat, jadi idealnya lakukan ini sebagai pra-proses. Setiap kali Nmeningkat, tambahkan dua interval resultan baru ke intervalskoleksi sambil menghapus lama, interval tunggal yang mereka ganti. Ini adalah struktur tempat Anda bekerja untuk menemukan interval terbesar berikutnya untuk dipecah menjadi dua. Menyortir intervalsberdasarkan jarak membuat segalanya mudah, karena Anda bisa menghapus item pekerjaan berikutnya dari ujung, dan membagi dll.

Kita berakhir dengan sesuatu seperti yang kita inginkan:

epsilon: 0.01

t            distance
0.200417     2.00417
0.3998132    3.9998132
0.600703     6.00703
0.800001     8.00001
0.9995309    9.995309

Karena kami mengambil tebakan pada setiap langkah, kami tidak akan mendapatkan tepat jarak yang tepat 2, 4dll. Yang kami inginkan, tetapi melalui pengulangan berulang-ulang ini cukup dekat dengan nilai jarak yang diinginkan sehingga Anda dapat memetakan ke tlangkah Anda dengan akurasi yang adil, menghilangkan bias akibat untuk pengambilan sampel yang hampir setara.

Anda kemudian dapat mengambil mis t=0.5, seperti yang dilakukan Ivo dalam jawabannya, yaitu dengan menyisipkan antara dua nilai terdekat di atas ( 3.9998132dan 6.00703).

Kesimpulan

Untuk sebagian besar kasus, solusi Ivo akan bekerja dengan baik, tetapi untuk kasus-kasus di mana bias harus dihindari dengan cara apa pun, pastikan bahwa Anda distancetersebar sebanyak mungkin, dan kemudian dipetakan secara linear t.

Perhatikan bahwa pemisahan dapat dilakukan secara stokastik daripada pemisahan di tengah setiap kali, misalnya kita mungkin telah membagi interval contoh pertama di t=0.827daripada di t=0.9.