Ada dua cara untuk menjawab pertanyaan ini yang bisa saya lihat. Pertama, jika Anda hanya ingin menemukan cara untuk mengarahkan, maka Anda hanya perlu menerapkan pathfinding ( saya menemukan ini cukup membantu ). Itu akan menjadi akhir dari itu (dan merupakan jawaban praktis yang benar untuk pertanyaan ini), tetapi saya pikir Anda lebih penasaran dengan solusi matematika untuk masalah Anda.
Untuk mengatasinya, mari kita lihat masalah yang setara. Ambil irisan 2D adegan Anda "di depan" pilot Anda dari sebuah pesawat yang normal dengan vektor asli. Apa yang akan Anda dapatkan adalah titik yang mewakili vektor asli Anda dan serangkaian elips yang merupakan proyeksi 2D dari kerucut oklusi Anda. Sekarang yang ingin Anda lakukan adalah menemukan titik terdekat dengan titik awal Anda (sebut saja P
) yang terletak di bagian luar elips yang tidak tumpang tindih. Ternyata ini adalah masalah yang cukup sulit untuk dipecahkan. Ada 3 langkah:
- Cari tahu titik persimpangan semua elips Anda
- Temukan lubang di persatuan semua elips Anda
- Cari tahu titik terdekat untuk
P
semua elips Anda di luar serikat (yang bisa berada di dalam lubang)
Oke, semua ini membutuhkan pengganda Lagrange dan pengecekan sudut dan beberapa hal rumit lainnya untuk dipecahkan. Mari kita lihat opsi lain. Jika kita mengubah masalah kita menjadi ruang sudut, kita melihat bahwa apa yang sebenarnya ingin kita lakukan adalah menemukan jarak minumum antara titik dan beberapa lingkaran yang diproyeksikan ke permukaan bola. Dalam geometri diferensial, ini sering disebut bola-2 dan berguna di sini. Jadi pertama-tama, kita perlu menemukan jarak antara dua titik di permukaan bola, yang akan kita gunakan metrik 2-bola untuk menemukan. Untungnya, ini cukup mudah:, di ds^2 = (R^2)*(dth^2) + (R^2)*(sin(th)^2)*(dph^2)
mana kita memegang R
konstan ketika jari-jari 2-bola kita diproyeksikan menjadi 3-ruang. Berasal dari fisika, saya mengambil th
sudut dari positif z
dan ph
menjadi sudut dari positif x
dengans
menjadi jarak.
Apa yang dilakukan dengan melakukan ini? Hal ini memungkinkan kita untuk menghapus penggunaan pengganda Lagrange untuk meminimalkan jarak, dan memungkinkan kita untuk bekerja dalam koordinat "asli" (karena kita mendefinisikan kerucut kita dalam hal sudut oklusi). Jadi sekarang kita perlu menemukan radius proyeksi kerucut kita. Mari kita ambil satu kerucut untuk saat ini, dan memanggil sudut yang mendefinisikannya a
. Jari-jari proyeksi kemudian sederhana R*a
. Itu cukup mudah - kuantitas apa lagi yang perlu kita ketahui tentang kerucut? Kita perlu mengetahui pusat proyeksi, yang ditentukan oleh vektor tampilan dari aktor. Pertama-tama kita mengkonversi x
,, y
dan z
menjadi koordinat bola di mana kita tahu kita berada jauh R
, dan menyelesaikannya untuk th
dan ph
, yang dapat kita lakukan dengan hanya memasukkan ke rumus konversi kita:th = acos(z/R)
dan ph = atan2(y/x)
(gunakan di atan2
sini untuk menjelaskan ambigitas kuadran arctangent). Prosesnya sama untuk menemukan posisi vektor asli Anda dalam koordinat bola.
Jadi masalahnya sudah disederhanakan. Namun, masalahnya masih cukup sulit untuk dipecahkan, tetapi sekarang Anda hanya perlu khawatir tentang lingkaran dan titik, bukan elips dan titik atau sudut dan vektor. Sisa prosesnya agak prosedural. Anda pada dasarnya perlu menemukan area pembatas yang dibentuk oleh lingkaran Anda, dan ada beberapa solusi. Saya akan menyajikan satu metode yang mungkin bukan yang terbaik, tetapi akan berhasil.
Pertama-tama saya akan membandingkan jumlah jari-jari semua pasangan lingkaran dan jarak antara pusat, dan kemudian jika jumlah mereka lebih besar dari jarak pusat, setel sama dan pecahkan untuk th
danph
untuk menemukan persimpangan. Anda tahu bahwa setiap pasangan persimpangan menggambarkan "sudut terlarang" untuk lingkaran yang dimaksud, yang akan Anda simpan sebagai array sudut titik persimpangan (dari pusat lingkaran) untuk setiap lingkaran yang memotong yang ini - yang penting Anda harus " gabungkan "rentang apa pun yang tumpang tindih saat Anda menambahkannya ke array agar bagian selanjutnya berfungsi dengan benar. Kemudian Anda menemukan titik terdekat di tepi lingkaran ke titik asli (yang sesederhana menggambar garis melalui titik pusat lingkaran dan titik asli, lalu menemukan lokasi pada garis di jari-jari lingkaran) jauh dari pusat). Kemudian loop melalui array yang tersimpan dan uji apakah sudut itu dalam kisaran masing-masing sudut terlarang. Jika demikian, maka pilih tepi terdekat. Itu adalah titik terdekat ke luar yang dijelaskan di dalam lingkaran ini. Ulangi proses untuk semua lingkaran (beberapa optimasi dapat dilakukan dalam proses pemilihan - Anda sebenarnya tidak perlu menghitung ini untuk setiap lingkaran). Sekarang bandingkan semua jarak terpendek Anda, temukan yang terkecil, dan itulah jawaban Anda, dijelaskan dalam sudut pandangth
dan ph
. Ingatlah bahwa jarak dijelaskan dengan metrik 2-bola saat melakukan perhitungan ini. Karena Anda tidak peduli dengan bola tempat semua ini aktif, hanya sudutnya, Anda dapat mengatur R=1
dan melakukan perhitungan ini pada unit bola.
Ini adalah cara paling sederhana yang dapat saya pikirkan untuk melakukan ini. Saya tidak yakin itu cara termudah mutlak, tetapi itu akan bekerja dengan cukup baik. Secara praktis untuk sebuah game, Anda hanya ingin mengimplementasikan pathfinding.