Garis pandang diagonal dengan dua sudut

Saat ini saya sedang menggunakan algoritma garis Bresenham untuk saling berhadapan. Masalahnya adalah saya telah menemukan kasus tepi di mana pemain dapat melihat menembus dinding. Terjadi ketika pemain melihat antara dua sudut dinding dengan celah di sisi lain pada sudut tertentu.

Kasing garis pandang

Hasil yang saya inginkan adalah ubin di antara dua dinding ditandai tidak valid.

Hasil yang diinginkan

Apa cara tercepat untuk memodifikasi algoritma garis Bresenham untuk menyelesaikan ini? Jika tidak ada solusi yang baik, apakah ada algoritma yang lebih cocok? Setiap ide dipersilakan. Harap dicatat solusinya juga harus mampu mendukung 3d.

Sunting: Solusi sederhana saya adalah memeriksa apakah kedua sudut ditutup ketika koordinat x dan y garis berubah. Untuk kode sumber yang berfungsi dan demo interaktif dari produk yang telah selesai, lihat http://ashblue.github.io/javascript-pathfinding/

3d tiles tilemap raycasting line-of-sight Ash Blue
sumber

Apakah ada bedanya jika Anda beralih titik awal dan akhir? Mungkin kemudian Anda bisa menerima hasil jika kedua perhitungan mengembalikan garis pandang yang tidak terhalang. Anda juga mungkin menemukan beberapa artikel LOS bermanfaat di RogueBasin.

thalador

Either way, kedua blok hitam diagonal di 4-5 tidak terhubung ke dinding di tempat pertama, dan saya katakan ini karena Anda secara implisit memungkinkan gerakan diagonal. Anda harus kuadratkan diagonal itu untuk menjadikannya dinding yang berdekatan atau membuat garis walker Anda kuadrat dari gerakan diagonal alih-alih menjadi murni diagonal seperti 2-3 dan 4-5.

Patrick Hughes

Membaliknya kedengarannya seperti ide yang bagus, tetapi itu tidak menyelesaikan masalah. Satu-satunya hal yang dapat saya pikirkan adalah memeriksa dan melihat apakah salah satu dari dua sudut kosong. Tampaknya mahal.

Ash Blue

"Tampaknya mahal" tidak pernah cukup sebagai pembenaran untuk tidak mencoba sesuatu. "Akan terlalu mahal" pada umumnya, dengan asumsi Anda dapat membuktikan bahwa sesuatu akan terlalu lambat.

Mokosha

Hanya perubahan pada algoritma yang diperlukan adalah bahwa jika X dan Y berubah pada langkah yang sama, maka pertama-tama ubah X dan kemudian ubah Y, ini akan menghilangkan diagonal sama sekali.

Patrick Hughes

Jawaban:

Eric Lippert menulis seri yang sangat baik tentang menghasilkan line-of-sight dalam C # dengan Shadow Casting pada kotak planar persegi panjang ..

Di antara masalah lain, Eric berurusan dengan berbagai pertanyaan yang harus dijawab tentang persyaratan garis pandang, yang memberikan hasil yang berbeda, dan memberikan contoh dari beberapa hasil yang berbeda. Salah satu artikel membahas secara mendalam dengan keadaan "melihat sekeliling" yang terjadi dalam versi awal algoritmanya.

Saya telah mengadaptasi algoritma Eric ke kisi heksagonal di sini , dan berhasil menggunakannya pada kisi heksagonal besar (> 400 x 700) dengan radius visibilitas yang luas (> 60 heks). Implementasi ini menghitung dan menampilkan bidang pandang lengkap secepat saya bisa berkedip, menggunakan CPU i7 tunggal. Ini tentu saja cukup cepat untuk penggunaan apa pun yang saya harapkan.

Pembaruan - Line-of-sight dengan elevasi:
Implementasi hex-grid yang terhubung ke atas menghitung line-of-sight dengan elevasi, bukan hanya hambatan. Catatan dokumentasi juga membahas keputusan tambahan yang harus dibuat sehubungan dengan perhitungan ketinggian: Tinggi target dan tinggi pengamat. Pilihan default adalah untuk membuat keduanya sama, yang menciptakan bidang pandang simetris, tetapi ground-to-ground dan pengamat-mata ke tanah juga dapat dipilih. (Kode ini Open Source di bawah Lisensi MIT)

Pieter Geerkens
sumber

Saya benar-benar menggali Shadow Casting, tetapi saya mengalami masalah. Mengalami kesulitan menemukan informasi tentang penskalaan algoritma untuk beroperasi dengan sumbu z. Maaf menyebutkan ini, tetapi apakah Anda memiliki sumber daya yang disarankan untuk membuatnya berfungsi dalam 3d?

Ash Blue

@AshBlue: lihat addendum di atas

Pieter Geerkens

Saya melihat basis kode Anda. Ini memiliki hal-hal hebat di dalamnya, tapi sepertinya saya tidak menemukan algoritma menggambar garis seperti Bresenham yang disesuaikan dengan hex. Apakah Anda melakukannya dengan LOS?

MLProgrammer-CiM

@EfEs: FieldOfView adalah objek yang dikembalikan; ShadowCastingFov * .cs menghasilkan bidang pandang dengan memberikan bayangan. Jika Anda memiliki pertanyaan spesifik tentang kode tersebut, itu mungkin lebih baik ditanyakan di bagian Diskusi situs; pertanyaan yang lebih umum saya senang menjawab di sini.

Pieter Geerkens

@PieterGeerkens Anda dapat menemukan pertanyaan di sini gamedev.stackexchange.com/questions/57087/…

MLProgrammer-CiM

Bagaimana jika untuk perhitungan LOS Anda memiliki kisi "resolusi lebih tinggi" terpisah yang mengisi celah sudut. Saya sedang memikirkan sesuatu seperti ini:

masukkan deskripsi gambar di sini

Kiri adalah bagian blok asli dari 4 kotak.

Yang benar adalah versi "resolusi tinggi", karena Anda dapat melihat setiap kotak asli dibagi menjadi empat quaters dan salah satu sudut telah diisi. Saya tidak yakin begitu saja algoritma untuk menghasilkan itu, tetapi dapat dihitung sebelumnya dari peta saat ini.

Itu berarti ruang koordinat empat kali lipat tapi saya tidak membayangkan itu menjadi masalah kinerja yang signifikan.

Davy8
sumber

Cukup yakin resolusi yang lebih tinggi akan terlihat sama persis seperti aslinya. Saat membagi kisi menjadi kisi yang lebih kecil, Anda mendapatkan representasi visual yang sama, hanya dengan kisi yang lebih kecil. Setiap kotak hanya menjadi 4 kotak kecil di tempat yang sama.

MichaelHouse

@ Byte56 Benar, saya maksudkan bahwa logika tambahan akan diterapkan setelah membaginya untuk menambahkan blok tambahan ke salinan itu. Logika untuk melakukan itu adalah latihan yang diserahkan kepada pembaca.

Davy8

Anda dapat dengan mudah menghasilkan grid beresolusi tinggi dengan mengaburkan yang asli. Kemudian tentukan ambang, katakanlah, 0.5untuk sel beresolusi tinggi yang harus diisi atau tidak. Jadi, menggunakan grid beresolusi tinggi terasa cukup aneh bagiku.

danijar