Saya membuat game berdasarkan grid 2D, dengan beberapa sel lumayan dan beberapa tidak. Objek dinamis dapat bergerak terus menerus, terlepas dari kisi, tetapi perlu bertabrakan dengan sel yang tidak bisa dilewati.
Saya menulis sebuah algoritma untuk melacak sinar pada grid, yang memberi saya semua sel yang bersilangan. Namun, objek sebenarnya tidak berukuran titik; Saat ini saya mewakili mereka sebagai lingkaran. Tetapi saya tidak dapat menemukan algoritma yang efektif untuk melacak lingkaran yang bergerak. Ini gambar yang saya butuhkan:
Angka-angka menunjukkan dalam urutan apa lingkaran bertabrakan dengan sel-sel kisi. Adakah yang tahu algoritma untuk menemukan tabrakan ini? Lebih disukai dalam C #.
Perbarui Lingkaran bisa lebih besar dari sel kotak tunggal.
sumber
Jawaban:
Saya pikir gambar Anda sedikit menyesatkan karena Anda memilih untuk menggambar garis dari titik pada lingkaran yang bersinggungan dengan arah bergerak Anda. Saya bisa melihat bahwa tabrakan ke tepi kisi Anda bahagia ketika titik TOP dan LEFT dari lingkaran Anda menyentuh tepi.
Biarkan C menjadi pusat Anda dan r jari-jari sehingga P ' = C + ( r , 0) dan P " = C + (0, r).
Jika D adalah vektor arah Anda (versor), Anda memiliki dua baris:
R '= D · t + P' ,
R "= D · t + P"
Anda harus menemukan persimpangan garis-garis tersebut dengan garis persamaan:
y = i dan y = i yang merupakan tepi dari grid Anda!
Solusinya mudah karena Anda hanya perlu mempertimbangkan komponen x atau y dari R 'dan R ". Anda akan menemukan t untuk setiap bagian, dan poin untuk thoose t , cukup urutkan titik tersebut dengan t dan Anda sudah selesai.
Saya percaya Anda dapat dengan mudah mengatakan sel apa yang dipukul jika Anda tahu titik persimpangan.
Ini berfungsi jika r <1 (lebar dan tinggi sel).
Ini bekerja juga untuk kasus-kasus lain hanya melakukan beberapa pertimbangan P ' dan P " . Kami memilih TOP dan KIRI karena arah, BOTTOM dan KANAN harus dipertimbangkan untuk arah yang berlawanan, Anda mengerti mengapa.
Sekarang lihat gambar ini:
Lingkaran lebih besar dari satu sel dan kami mengira itu akan arah yang sama dengan gambar Anda. P1 adalah titik pertama yang akan menyentuh, P2 adalah yang kedua, P3 tidak berguna karena berada di bagian bawah. Yang perlu Anda lakukan adalah melempar sinar dari P1 dan P2 seperti yang kita lihat sebelumnya dan melakukan hal yang sama untuk garis vertikal.
Secara umum Anda akan memiliki titik awal lainnya bersama dengan TOP dan yang KIRI dari mana menembakkan sinar Anda, semakin besar lingkaran Anda, semakin banyak sinar yang harus dilemparkan.
Sejujurnya beberapa Anda dapat menghindari untuk menembak semua sinar melakukan pertimbangan geometris, tetapi itu dapat membuat hal-hal lebih sulit untuk dipahami.
sumber
Jika Anda ingin menggunakan algoritme tabrakan-ray Anda, Anda dapat memilih delapan titik pada setiap lingkaran (dengan kenaikan 45 derajat, selaras dengan kisi-kisi persegi Anda), dan menggunakan tabrakan-ray antara titik-titik yang sesuai (yaitu, dari atas satu lingkaran ke atas yang lain). Penyatuan semua tabrakan sinar ini adalah seluruh set sel yang berpotongan.
Anda mungkin dapat memperbaiki ini sedikit - misalnya dengan menggunakan segmen garis dari pusat satu lingkaran ke pusat yang lain, tetapi diperluas di kedua sisi dengan jari-jari lingkaran, serta segmen garis paralel pada kedua sisi di ujung lingkaran.
sumber
Saya tidak mengatakan ini analogi yang sempurna, tetapi Anda mungkin berpikir tentang algoritma garis Bresenham . Modifikasi algoritme ini atau salah satu ekstensi mungkin membantu, terutama jika Anda memasangkannya dengan beberapa posting dan komentar lainnya. Biasanya, algoritme ini tidak berkaitan dengan pemesanan, tetapi saya akan berpikir bahwa Anda dapat menambahkannya secara sepele.
sumber