Merintis jalan di permukaan planet yang tidak rata

16

Pertanyaan saya adalah apa yang akan menjadi pendekatan terbaik untuk merintis jalan di permukaan planet yang tidak rata?


Informasi latar belakang

Saya telah membuat sebuah planet dari pemetaan perpindahan 6 bidang yang diproyeksikan. Pesawat awalnya membentuk kubus sebelum diproyeksikan menjadi bentuk bola.

masukkan deskripsi gambar di sini

Saya ingin tahu apakah mungkin untuk menggunakan setiap "sphere projected cube face" sebagai kisi-kisi dan menggunakan algoritma A * sederhana untuk menemukan rute terbaik, saya juga ingin ketinggian perpindahan diperhitungkan sehingga jalur menghindari pendakian pegunungan dll (saya kira ini hanya akan menjadi heuristik dalam algoritma A *) Pertimbangan lain adalah bahwa saya telah mencapai pergerakan planet dengan memanfaatkan mesin fisika Unity3d, menerapkan gravitasi ke pusat planet. Apakah solusi yang saya usulkan memerlukan gerakan agen untuk dikontrol secara independen ke fisika gravitasi.

Untuk membantu mengartikulasikan pertanyaan saya dengan lebih baik, inilah tubuh planet saya saat ini:

masukkan deskripsi gambar di sini

Caius Eugene
sumber
2
Anda mungkin tertarik dengan video ini dari Penghancuran Planetary. Mereka tampaknya melakukan hal yang sama ketika Anda membungkus dunia dari sebuah kubus dan menemukan jalan di sekitarnya. Ini sebenarnya bukan jawaban, tetapi Anda dapat melihat bahwa mereka menggunakan A * bersama dengan beberapa strategi lain untuk mengoptimalkan pencarian-jalan di sekitar bola. Bit pencarian jalur dimulai pada 24:30 .
MichaelHouse
@ Byte56 Terima kasih atas tautan ini, pendekatan yang sangat menarik untuk penetapan biaya, tidak sabar untuk melihat permainan itu saat selesai!
Caius Eugene

Jawaban:

12

Sepertinya Anda sudah menjawab pertanyaan Anda sendiri. A * kemungkinan merupakan pendekatan terbaik. Ya tentu saja dapat digunakan dengan cara yang Anda gambarkan, termasuk menggunakan informasi ketinggian untuk menghindari gunung. Selama Anda dapat mengakses informasi tentang kisi apa pun di permukaan dunia Anda, tidak ada alasan Anda tidak dapat menggunakannya dalam heuristik A *.

Akhirnya, Anda bingung mencari jalur dengan mengikuti jalur di akhir pertanyaan Anda. Menemukan jalan tidak peduli dengan gravitasi, kecuali jika Anda menambahkannya sebagai heuristik dan karena Anda berada di permukaan sebuah planet, gravitasi pada dasarnya akan sama di seluruh permukaan. Banyak permainan memiliki gravitasi bersama dengan gerakan, saya tidak melihat alasan Anda tidak bisa.

Pada dasarnya kami ingin memetakan dari merah ke biru, untuk menjadi sama di bola seperti di kubus.

masukkan deskripsi gambar di sini

Karena A * sering membuat tetangga ke node saat ini, Anda dapat dengan mudah membuat satu set fungsi untuk mendapatkan node yang berdekatan. Sebagai contoh, getXPlus(), getXMinus(), getZPlus()dan sebagainya. Fungsi-fungsi ini akan mengambil simpul saat ini dan mengembalikan simpul ke arah yang ditentukan oleh nama fungsi.

Sebagian besar waktu fungsi-fungsi ini hanya bisa menambah nilai dan dilakukan, namun, di tepi, itu akan berubah.

Anda ingin memetakan permukaan kubus Anda ke sistem koordinat 2D. Namun Anda melakukan ini terserah Anda, mereka tidak harus berbaris, cukup beri masing-masing ruang grid koordinat X, Y yang unik.

Sekarang ketika berada di tepi, dan mendapatkan ruang grid yang berdekatan itu tidak harus hanya akan menambah koordinat. Kita harus mencari tahu di mana wajah kita bergerak dan beralih ke koordinat wajah itu.

Misalnya, mendapatkan koordinat XPlus di sini akan mengubah koordinat X dan Y karena kita pindah ke ruang kisi baru pada wajah baru. Garis hijau mewakili tepi antara dua wajah.

masukkan deskripsi gambar di sini

Sekarang ini hanya koordinat global, mungkin lebih mudah untuk menggunakan sistem koordinat lokal internal, dengan dimensi ke-3 yang mewakili permukaan kubus yang saat ini Anda gunakan.

Either way, Anda harus memiliki koordinat unik untuk setiap ruang kotak di muka kubus. Beralih di antara mereka akan tergantung pada bagaimana Anda menerapkan sistem koordinat. Anda perlu tahu di mana peta itu terkoordinasi dengan permukaan bola juga.

Semua ini pada akhirnya harus disarikan sehingga Anda bahkan tidak mengetahuinya.

MichaelHouse
sumber
Sorakan atas tanggapannya. Saya pikir apa yang saya perjuangkan adalah dengan setiap pesawat menjadi grid yang terisolasi. Apakah Anda punya saran (atau bacaan lebih lanjut) tentang cara menangani jahitan, saya kira saya akan secara matematis membuka "kubus" saya, menggabungkan semua kisi dan menghitung jalur menggunakan dataset itu?
Caius Eugene
Sungguh itu hanya tepi yang perlu Anda khawatirkan. Itu mudah dipecahkan dengan fungsi pembungkus (membungkus kubus Anda dalam fungsi pembungkus, yang membungkus dunia Anda ...). Anda bisa mengabstraksi kubus menjadi permukaan datar yang membungkus. Buat fungsi untuk mendapatkan ruang grid yang berdekatan, getXPlus () akan mendapatkan grid dalam arah XPlus, tidak masalah jika berada di batas antara wajah, fungsi tersebut hanya akan beralih wajah dan mengembalikan informasi grid yang sesuai.
MichaelHouse
Satu-satunya ketidakakuratan dengan temuan jalur pada kubus terlipat adalah bahwa simpul miring dan oleh karena itu tepi memiliki panjang yang berbeda. Mungkin saja itu tidak akan membuat perbedaan yang nyata dalam jalur yang dihasilkan dan jika tidak Anda hanya bisa mempertimbangkan panjangnya.
danijar
1
Yang penting untuk dipahami di sini adalah bahwa A * tidak harus beroperasi di pesawat; beroperasi pada grafik. Meskipun di dalam masing-masing permukaan kubus, node disusun dan dihubungkan dalam sebuah grid, ada juga koneksi node di sepanjang tepi kubus.
jmegaffin
1
@ Byte56 Terima kasih atas jawaban yang bagus, saya sudah mulai menerapkan solusi tetapi saya telah menemukan sedikit hambatan. Mungkin saya salah paham. Saya telah memposting pertanyaan di stackoverflow karena saya merasa lebih banyak masalah matematika / pemrograman stackoverflow.com/questions/16089074/…
Caius Eugene