Apa cara paling efisien untuk menemukan titik persimpangan dari rudal dan medan bitmap?

10

Menindaklanjuti pertanyaan saya sebelumnya tentang menemukan kemiringan medan bitmap 2D sekarang saya perlu tahu cara terbaik untuk menemukan titik pada medan 2D yang terkena rudal. Jelas, saya bisa melihat apakah ada piksel di bawah medan berpotongan rudal, tetapi mengatakan itu telah bergerak cukup dalam ke medan.

Apa cara terbaik untuk mundur untuk menemukan di mana ia bertabrakan? Saya dapat memindahkan kembali piksel X pada satu waktu ke posisi sebelumnya rudal, tetapi apa yang akan menjadi nilai X yang baik? Dan adakah cara yang lebih cerdas? Mungkin bergerak setengah jarak, lalu seperempat dll?

2d collision-detection terrain projectile-physics Iain
sumber
Fenomena yang Anda gambarkan umumnya disebut "tunneling", dan cara terbaik untuk mengatasinya adalah dengan memperkenalkan tes sapuan - seperti yang disebutkan TetraD dan JasonD di bawah ini.
jpaver
hanya mengatakan "sapu uji" sebenarnya tidak membantu saya. Bagaimana saya melakukannya dengan medan bitmap?
Iain
Saran Jason tampaknya menjadi yang terbaik bagi saya: satu piksel pada suatu waktu.
jpaver

Jawaban:

3

Untuk pengujian tabrakan Anda tidak boleh melakukan pengujian statis tick-by-tick, Anda harus melakukan tes jejak / sapuan.

Ada daftar lengkap berbagai formula untuk berbagai jenis primitif di sini: http://www.realtimerendering.com/intersections.html

Itu, tentu saja, dengan asumsi Anda dapat memecah medan Anda menjadi beberapa jenis primitif yang dapat Anda uji terhadap (yaitu segmen garis). Ada berbagai cara untuk melakukan itu.

Lihat juga pertanyaan ini (hanya sedikit terkait): Apa algoritma yang baik untuk mendeteksi tabrakan antara bola yang bergerak?

Tetrad
sumber
Saya sedang berpikir tentang medan bitmap yang dapat dirusak seperti di Worms. Bisakah Anda secara dinamis menghasilkan primitif dari bitmap atau apakah itu terlalu gila?
Iain
1
Saya yakin Anda bisa, tetapi mungkin lebih mudah / lebih cepat untuk melakukan pengujian piksel demi piksel untuk bitmap yang sewenang-wenang.
Tetrad
DENGAN QUADTREE !! (jadi tidak butuh selamanya)
bobobobo
3

Pencarian biner tidak akan membantu jika Anda memiliki sedikit pemandangan tipis dan proyektil yang bergerak cepat - Anda mungkin melewatkannya.

Saya pikir pilihan terbaik Anda adalah dengan menyapu garis di depan proyektil di sepanjang jalan yang diperlukan, pixel pada suatu waktu. Anda bisa melakukan pemeriksaan batas terlebih dahulu pada seluruh volume untuk menghindari melakukannya setiap langkah.

JasonD
sumber
Apa itu pencarian biner?
Iain
1
Maaf - pencarian biner kurang lebih seperti yang Anda bicarakan dalam pertanyaan. Anda mulai di tengah, dan membagi ruang pencarian dengan dua sampai Anda bertemu pada jawabannya. Ini optimal dalam banyak kasus, tetapi dalam kasus Anda itu tidak akan berhasil (Anda mungkin melewatkan jawaban yang benar sepenuhnya).
JasonD
3

Karena rudal tidak mungkin untuk memindahkan sejumlah besar piksel setiap frame (itu tidak akan mulus di layar) saya tidak melihat alasan untuk tidak hanya memeriksa setiap piksel di jalan. Algoritma garis Bressenham adalah teman Anda, dan memastikan Anda mendapatkan salinan lokal bitmap Anda juga karena Anda biasanya tidak ingin mengakses memori video untuk setiap piksel. Ini dengan asumsi medan bitmap Anda sepenuhnya acak (sesuai medan cacing yang dapat dirusak). Jika dunia Anda berbasis ubin, Anda bisa melewati setiap ubin yang Anda tahu kosong untuk memulai, tetapi seperti yang disebutkan sebelumnya, kecuali jika Anda memiliki sejumlah besar rudal untuk memeriksa. Saya tidak dapat memikirkan platform yang membutuhkan platform yang terlalu lambat. untuk hanya menguji pixel demi pixel, dan Anda tidak perlu memiliki dunia Anda didefinisikan dalam primitif (klon cacing akan membuat itu rumit)

Kaj
sumber
ya saya sedang memikirkan medan seperti Worms. Bisakah Anda membaginya menjadi ubin secara dinamis, lalu hanya menandai ubin kosong untuk tidak diperiksa? Jika ada banyak rudal sekaligus mungkin itu akan mempercepat sedikit?
Iain
Jadi, apakah Anda pikir saya harus bergerak maju pixel demi pixel, memeriksa persimpangan, daripada melangkah mundur?
Iain
Saya pikir ketiga jawaban telah menyarankan pencarian ke depan. Memeriksa mundur tidak akan berfungsi jika langkah maju membuatnya melewatkan beberapa pemandangan.
JasonD
Ya, pasti ke depan.
Kaj
1

Selain jawaban lain, ada beberapa hal yang dapat Anda lakukan untuk mempercepat ini jika Anda ingin melakukan sedikit pembukuan sehubungan dengan "mengumpulkan" sekelompok piksel ke dalam blok "keadaan serupa yang diketahui." Misalnya Anda dapat menyimpan ketinggian potongan medan tertinggi, sehingga Anda dapat menerima begitu saja bahwa rudal tidak akan mengenai apa pun selama itu di atas itu. Anda juga bisa menyimpan ketinggian ruang "udara" terendah, jadi Anda akan tahu bahwa jika rudal mencapai ketinggian itu, ia pasti mengenai sesuatu (walaupun ini mungkin lebih baik digunakan sebagai pemeriksaan kewarasan). Lebih jauh dari ini, Anda bisa menyimpan persegi panjang yang mewakili area yang semuanya terrain dan persegi panjang lain yang semuanya berudara, tapi itu mungkin lebih berfungsi daripada nilai.

Pada akhirnya, metode terbaik mungkin adalah "menyimpan ketinggian setiap kolom medan" dan kemudian hanya menghitung ketinggian rudal di setiap langkah dari jalurnya. Saya tidak dapat berbicara dengan permainan yang lebih modern, tetapi saya percaya bahwa ketika Anda membuat "gua" di Bumi Hangus, bahwa medan di atas gua itu jatuh lurus ke bawah, tanpa meninggalkan menggantung. Jika Anda ingin overhang, pekerjaan akan sedikit lebih besar, tetapi itu akan menjadi perpanjangan dari ide dasar ini. (Petunjuk: dapatkan ide dasar bekerja terlebih dahulu!)

Karena medan Anda mungkin sepenuhnya arbitrer, tidak ada jalan pintas. Bahkan jika Anda memaksa medan Anda menjadi spline atau sesuatu, itu akan menjadi marah setelah Anda mulai menghancurkannya dan tes persimpangan garis-spline adalah berulang dan tidak sempurna atau lengkap dan lengkap dan lambat untuk jenis masalah Anda.

dash-tom-bang
sumber