Bagaimana cara menghitung jalur untuk objek dengan akselerasi terbatas?

Sebagai contoh, katakan saya memiliki mobil dan mobil memiliki radius belokan minimum tertentu dan saya ingin mengendarai mobil itu dari titik a ke titik b, tetapi mobil itu tidak menghadap ke titik b. Bagaimana cara menghitung jalur ke titik b? Mampu menentukan orientasi pada titik b juga akan baik (katakanlah Anda ingin pergi ke jalan masuk dan kemudian masuk ke garasi Anda - tidak ada gunanya jika Anda sampai di jalan masuk dengan mengemudi melewati halaman Anda dan menghadap ke samping :)

Pointer ke dokumentasi (atau bahkan hanya nama) akan baik-baik saja - Saya mengalami kesulitan menemukan apa pun.

Dalam upaya saya, mereka bekerja dalam kasus-kasus sederhana, tetapi gagal total dalam situasi seperti ketika titik b lebih dekat ke daripada radius putar minimum.

Misalnya, bagaimana Anda menentukan jalur yang mirip dengan ini (jalur tebal):

sunting: Dalam masalah saya yang sebenarnya, ada beberapa kendala lintasan sederhana, tapi saya sudah memiliki algoritma A * yang berfungsi, tetapi memungkinkan hal-hal untuk membuat perubahan heading sesaat, sehingga tampak konyol melihat mobil tiba-tiba berbelok 90 ˚ pada sepeser pun ketika mereka sampai pada titik balik.

Saya belum mengerjakan persamaan lengkap untuk ini, tapi di sini ada beberapa visual untuk membantu mengatasi masalah ini. Itu bermuara pada beberapa geometri:

( Ikon mobil melalui Kenney )

Dari titik awal dan orientasi mana pun, kita dapat menggambar dua lingkaran dengan jari-jari belok minimum - satu di kiri, satu di kanan. Ini menggambarkan titik-titik di awal seketat mungkin menuju jalan kita.

Kita dapat melakukan hal yang sama untuk posisi akhir dan orientasi yang diinginkan. Lingkaran-lingkaran ini menggambarkan ujung seketat mungkin untuk jalan kita.

Sekarang masalahnya berkurang menjadi menemukan jalan yang bergabung dengan salah satu lingkaran mulai ke salah satu lingkaran akhir, mencium masing-masing sepanjang garis singgung.

(Ini dengan asumsi kita tidak perlu mencari-cari kendala di antara, yang tidak disebutkan dalam pertanyaan. Jawaban Stormwind masuk ke bagaimana kita dapat menggunakan informasi grafik navigasi untuk jenis masalah ini. Setelah kita memiliki urutan node untuk melewati, kita dapat menerapkan metode di bawah ini untuk setiap segmen dari rencana.)

Jika, untuk kesederhanaan, kami menggunakan garis lurus, kami mendapatkan sesuatu seperti ini:

Ini memberi kita kasus pembatas. Setelah Anda menemukan jalur dengan metode ini, Anda dapat mengembang satu atau keduanya secara otomatis mulai & akhiri lingkaran untuk mendapatkan jalur yang lebih langsung namun lebih halus, hingga titik di mana kedua lingkaran mencium.

Hitung jalur ini

Mari kita selesaikan case untuk satu arah belokan - katakan kita memulai jalan kita dengan belok kanan.

Pusat lingkaran kanan kita adalah:

startRightCenter = carStart.position + carStart.right * minRadius

Mari kita sebut sudut bagian lurus dari lintasan kita (diukur dari sumbu x positif) pathAngle

Jika kita menggambar vektor dari rightCenterke titik di mana kita meninggalkan lingkaran berputar (pada titik mana kita harus menghadapi pathAngle), maka vektor itu adalah ...

startOffset = minRadius * (-cos(pathAngle), sin(pathAngle))

Itu berarti titik di mana kita meninggalkan lingkaran harus ...

departure = startRightCenter + startOffset

Titik di mana kita masuk kembali ke lingkaran berputar tergantung pada apakah kita bertujuan untuk mengakhiri dengan belokan kiri atau kanan:

// To end with a right turn:
reentry = endRightCenter + startOffset

// To end with a left turn: (crossover)
reentry = endLeftCenter - startOffset

Sekarang, jika kita sudah melakukan tugas kita benar, garis bergabung departureke reentryseharusnya menjadi tegak lurus ke startOffset:

dot(reentry - departure,  startOffset) = 0

Dan memecahkan persamaan ini akan memberi kita sudut pandang yang benar. (Saya menggunakan jamak di sini karena secara teknis ada dua sudut seperti itu, tetapi salah satunya melibatkan mengemudi secara terbalik yang biasanya tidak seperti yang kita inginkan)

Mari gantilah belokan kanan ke belok kanan sebagai contoh:

dot(endRightCenter + startOffset - startRightCenter - startOffset, startOffset) = 0
dot(endRightCenter - startRightCenter, startOffset) = 0
pathAngle = atan2(endRightCenter - startRightCenter)

Kasus crossover lebih rumit - itu yang saya belum mengerjakan semua matematika untuk saat ini. Saya akan memposting jawabannya tanpa untuk saat ini, kalau-kalau itu berguna bagi Anda saat saya mengerjakan rincian yang tersisa.

Sunting: Tujuan di dalam radius putaran minimum

Ternyata, metode ini sering bekerja di luar kotak bahkan ketika tujuannya lebih dekat dari jarak belokan minimum kami. Setidaknya beberapa bagian dari salah satu lingkaran masuk kembali berakhir di luar radius belokan, membiarkan kami menemukan jalur yang layak selama kami tidak keberatan mendapatkan sedikit seperti pretzel ...

Jika kita tidak menyukai jalan yang kita dapatkan seperti itu (atau jika ada yang tidak layak - saya belum memeriksa setiap kasus secara menyeluruh - mungkin ada yang mustahil), kita selalu dapat mengemudi lurus ke depan atau ke belakang sampai kita mendapatkan yang sesuai mencium kontak antara lingkaran awal & akhir, seperti yang digambarkan di atas.

Ini sangat tergantung pada sisa model data Anda untuk navigasi. Yaitu. data apa yang Anda miliki, apa yang dapat Anda tambahkan dengan mudah, dan bagaimana Anda menggunakannya.

Mengambil skenario serupa dari sistem lalu lintas di air, dan dengan asumsi itu

• Anda berada dalam lingkaran permainan
• Anda memiliki sistem jalur simpul
• mobil Anda berperilaku seperti benda otonom yang mengendalikan diri "dari dalam", menggunakan kekuatan dan kemudi sendiri
• mobil Anda tidak bergerak seperti di rel

Anda dapat memiliki sesuatu seperti di bawah ini (maafkan saya untuk penampilan kekanak-kanakan dari gambar)

(Kotak merah adalah node, garis merah adalah interkoneksi node. Asumsikan Anda menggunakan pemecah pathfinding yang memberi node 1-9 untuk melewati; node 4-9 terlihat pada gambar dan Anda ingin melewati node yang ditunjukkan oleh garis hijau , ke garasi di simpul # 9; namun Anda tidak ingin pergi tepat di garis hijau, melainkan tetap secara alami di jalur kanan dan lakukan manuver yang lancar).

Setiap node akan memiliki metadata yang menampung misalnya radius, atau beberapa, untuk berbagai keperluan. Salah satunya adalah lingkaran biru, yang memberikan panduan membidik mobil .

Pada setiap kesempatan , kendaraan perlu mengetahui dua titik simpul berikutnya P (berikutnya) dan P (berikutnya +1), dan posisinya. Secara alami, mobil memiliki posisi juga. Mobil mengarah ke garis singgung kanan lingkaran metadata biru P (berikutnya). Begitu juga mobil yang berjalan berlawanan arah, maka mereka tidak akan bertabrakan. Membidik garis singgung berarti mobil dapat mendekati lingkaran dari segala arah, dan selalu tetap di kanan. Ini adalah prinsip dasar yang kasar, yang dapat ditingkatkan dengan banyak cara.

P (selanjutnya +1) diperlukan untuk menentukan jarak - ketika mobil mencapai P (berikutnya), atau masuk ke dalam beberapa radius metadata-nya, ia dapat menyesuaikan sudut kemudi tergantung pada seberapa jauh P (berikutnya +1) adalah. Yaitu. jika dekat, putar banyak, jika jauh, putar sedikit. Rupanya perlu ada aturan lain & kondisi tepi juga, misalnya perhitungan jarak antara mobil dan garis bantuan berdasarkan garis singgung kanan P (berikutnya) dan P (berikutnya +1), dan koreksi dengan itu - Keinginan untuk tetap di garis putus-putus (di atas gambar) dan putus-putus (di bawah gambar).

Bagaimanapun, ketika mobil melewati satu simpul , ia melupakannya dan mulai melihat dua simpul berikutnya .

Untuk pertanyaan Anda. Rupanya, ketika mencapai simpul 7 (dalam gambar di atas, terlihat sebagai simpul 2 pada gambar di bawah), itu tidak bisa cukup .

Salah satu solusi yang mungkin untuk membangun beberapa garis bantuan dan mempertahankan tujuan sepanjang waktu , dan kemudian memiliki mobil bergerak dengan pengaturan fisika itu sendiri (mempercepat pada tingkat yang ditentukan, membalikkan lebih lambat, mengambil metadata node speedlimits ke dalam akun, rem pada yang diberikan atau dihitung G, dll.). Seperti yang dikatakan, mobil adalah objek otonom, menggambarkan diri, membawa sendiri dalam skenario ini.

Miliki garis bantuan hijau 1,2,3 . Ketika mobil mencapai lingkaran magenta , mulai belok ke kanan. Pada titik ini, Anda sudah dapat menghitung bahwa itu tidak akan berhasil (Anda tahu laju belokan maks dan dapat menghitung kurva, dan dapat melihat bahwa itu akan melintasi kedua saluran bantuan 2 dan 3). Putar setir sepenuhnya ke kanan dan biarkan mengemudi di depan (dengan kenaikan fisika) dan memperlambatnya saat mencapai garis bantuan 3 (mendekati ambang batas penggunaan, f (dist to helpline) dll). Saat berada di saluran bantuan 3, masuk ke mode mundur , putar setir ke posisi sebaliknya . Biarkan terbalik sampai mencapai garis bantuan 4(jalur koneksi antara node 1 dan 2 - google untuk "point at side of line algorithm"). Pelan, saat mencapai itu, masuk ke mode drive depan lagi, putar roda. Ulangi sampai jalannya jelas - rupanya cukup dengan 1 manuver tambahan kali ini.

Ini adalah ide umum: Selama loop game, atau ketika memeriksa sistem que tugas game:

• Periksa posisi mobil, kecepatan, sudut dll terhadap batas tepi saat ini & tujuan ,
• Jika belum tercapai , lanjutkan dengan apa yang Anda lakukan (biarkan fisika menggerakkannya; mobil memiliki rpm dan roda gigi). Masukkan cek baru di sistem que Anda, untuk terjadi misalnya 0,1 s.
• Jika tercapai , hitung kondisi baru, atur data dan mulai . Masukkan cek baru untuk terjadi di sistem que misalnya 0,1 s.
• Selesaikan siklus putaran - lanjutkan, ulangi.

Dengan memberikan node dan mobil data yang memadai, akan ada pergerakan dan kelanjutan.

Sunting: Dan tambahkan: Ini secara alami membutuhkan penyetelan yang bagus. Simulasi Anda sebelumnya mungkin memerlukan jalur bantuan berbeda, metadata, lingkaran, apa pun. Ini akan memberikan gambaran tentang satu solusi yang mungkin.

Saya akhirnya melakukan apa yang disarankan DMGregory dan bekerja dengan baik. Berikut adalah beberapa kode yang relevan (meskipun tidak mandiri) yang dapat digunakan untuk menghitung dua gaya garis singgung. Saya yakin kode ini tidak efisien, dan mungkin bahkan tidak benar dalam semua situasi, tetapi sejauh ini berfungsi untuk saya:

bool Circle::outer_tangent_to(const Circle & c2, LineSegment & shared_tangent) const {
    if (this->direction != c2.direction) {
        return false;
    }
    if (this->radius != c2.radius) {
        // how to add it: http://mathworld.wolfram.com/Circle-CircleTangents.html
        // just subtract smaller circle radius from larger circle radius and find path to center
        //  then add back in the rest of the larger circle radius
        throw ApbException("circles with different length radius not supported");
    }

    auto vector_to_c2 = c2.center - this->center;
    glm::vec2 normal_to_c2;
    if (this->direction == Circle::CW) {
        normal_to_c2 = glm::normalize(glm::vec2(-vector_to_c2.y, vector_to_c2.x));
    } else {
        normal_to_c2 = glm::normalize(glm::vec2(vector_to_c2.y, -vector_to_c2.x));
    }

    shared_tangent = LineSegment(this->center + (normal_to_c2 * this->radius),
                                 c2.center + (normal_to_c2 * this->radius));
    return true;
}


bool Circle::inner_tangent_to(const Circle & c2, LineSegment & tangent) const {

    if (this->radius != c2.radius) {
        // http://mathworld.wolfram.com/Circle-CircleTangents.html
        // adding this is non-trivial
        throw ApbException("inner_tangents doesn't support circles with different radiuses");
    }

    if (this->direction == c2.direction) {
        // inner tangents require opposing direction circles
        return false;
    }

    auto vector_to_c2 = c2.center - this->center;
    auto distance_between_circles = glm::length(vector_to_c2);

    if ( distance_between_circles < 2 * this->radius) {
//      throw ApbException("Circles are too close and don't have inner tangents");
        return false;
    } else {
        auto normalized_to_c2 = glm::normalize(vector_to_c2);
        auto distance_to_midpoint = glm::length(vector_to_c2) / 2;
        auto midpoint = this->center + (vector_to_c2 / 2.0f);

        // if hypotenuse is oo then cos_angle = 0 and angle = 90˚
        // if hypotenuse is radius then cos_angle = r/r = 1 and angle = 0
        auto cos_angle = radius / distance_to_midpoint;
        auto angle = acosf(cos_angle);

        // now find the angle between the circles
        auto midpoint_angle = glm::orientedAngle(glm::vec2(1, 0), normalized_to_c2);

        glm::vec2 p1;
        if (this->direction == Circle::CW) {
            p1 = this->center + (glm::vec2{cos(midpoint_angle + angle), sin(midpoint_angle + angle)} * this->radius);
        } else {
            p1 = this->center + (glm::vec2{cos(midpoint_angle - angle), sin(midpoint_angle - angle)} * this->radius);
        }

        auto tangent_to_midpoint = midpoint - p1;
        auto p2 = p1 + (2.0f * tangent_to_midpoint);
        tangent = {p1, p2};

        return true;
    }
};

Berikut adalah dua film dari kode di atas yang sedang beraksi:

Berikut ini jalur "luar": http://youtube.com/watch?v=99e5Wm8OKb0 dan inilah jalur "persimpangan": http://youtube.com/watch?v=iEMt8mBheZU

Jika kode ini membantu tetapi Anda memiliki pertanyaan tentang beberapa bagian yang tidak ditampilkan di sini, cukup kirim komentar dan saya akan melihatnya dalam satu atau dua hari.