Bagaimana cara cepat menghitung area penglihatan dalam game ubin 2D?

Saya memiliki matriks ubin, pada beberapa ubin ada objek. Saya ingin menghitung ubin mana yang terlihat oleh pemain, dan mana yang tidak, dan saya perlu melakukannya dengan cukup efisien (jadi itu akan menghitung cukup cepat bahkan ketika saya memiliki matriks besar (100x100) dan banyak objek).

Saya mencoba melakukannya dengan algoritma garis Bresenham , tetapi lambat. Juga, itu memberi saya beberapa kesalahan:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

Saya yakin ini bisa dilakukan - lagipula, kami punya NetHack, Zangband, dan mereka semua berurusan dengan masalah ini entah bagaimana :)

Algoritma apa yang dapat Anda rekomendasikan untuk ini?

Untuk kebutuhan saya, saya akan mendefinisikan terlihat seperti ini: ubin terlihat ketika setidaknya bagian (misalnya sudut) ubin dapat dihubungkan ke pusat ubin pemain dengan garis lurus yang tidak memotong rintangan apa pun.

Definisi Anda yang terlihat adalah sebagai berikut:

ubin terlihat ketika setidaknya bagian (misalnya sudut) ubin dapat dihubungkan ke pusat ubin pemain dengan garis lurus yang tidak memotong rintangan apa pun

Anda dapat menerapkan konsep ini secara harfiah dengan menelusuri sinar dari ubin pemain Anda dan memotongnya dengan adegan Anda. Anda menerobos dari setiap iterasi setelah sinar menabrak rintangan (atau melebihi batas jarak tertentu) karena Anda hanya tertarik pada ubin yang bisa dilihat langsung oleh pemain. Saya akan memecah proses untuk Anda:

1. Tentukan tingkat presisi yang ingin Anda berikan algoritma. Ini akan menjadi jumlah sinar yang akan Anda telusuri.
2. Bagilah lingkaran 360 derajat penuh dengan presisi yang dipilih untuk mengetahui berapa derajat yang harus diputar di antara setiap sinar.
3. Mulai dari 0 derajat dan bertambah dengan jumlah yang ditentukan pada langkah 2, buat sinar dengan asal di tengah ubin pemain, dan arah yang ditentukan oleh sudut saat ini.
4. Untuk setiap sinar, mulai dari ubin pemain, berjalan di sepanjang arah sinar sampai Anda menekan ubin penghalang. Tambahkan ubin itu ke daftar ubin yang terlihat dan lanjutkan ke ray berikutnya. Anda mungkin juga ingin menambahkan jarak maksimum untuk "menyerah" jika tidak ada tabrakan yang ditemukan.

Berikut gambar yang menunjukkan 3 contoh sinar. Ubin berwarna gelap adalah "hasil" dari setiap sinar, yaitu di mana tabrakan terjadi. Anda harus mengulang ini di seluruh lingkaran:

Tweak jarak maksimum dan jumlah sinar untuk kinerja. Terlalu sedikit dan Anda akan kehilangan ubin, terlalu banyak dan kinerja Anda akan menderita. Juga, sinar terjauh yang harus dilalui, semakin besar "kesalahan" yang akan didapat, dan semakin presisi yang Anda butuhkan.

Edit

Periksa tutorial berikut tentang raycasting, khususnya Langkah 3 dan Langkah 4, untuk membantu Anda menerapkan bit persimpangan algoritma:

http://www.permadi.com/tutorial/raycast/rayc7.html

Saya lebih suka melemparkan bayangan bayangan daripada garis pandang.

Katakanlah ini area tampilan Anda (area yang berpotensi terlihat)

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

Blok # tidak terlihat saat. terlihat

Mari kita letakkan beberapa kendala X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

Anda memiliki daftar X yang ada di dalam area tampilan lalu Anda menandai sebagai disembunyikan setiap ubin yang ada di belakang setiap rintangan ini: ketika suatu rintangan ditandai sebagai tersembunyi, Anda menghapusnya dari daftar.

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

Pada contoh di atas, Anda dapat melihat bayangan yang dilemparkan oleh paling kanan dari dinding bawah dan bagaimana bayangan ini menghapus hambatan tersembunyi dari daftar hambatan yang harus Anda periksa (X harus memeriksa; * dicentang).

Jika Anda mengurutkan daftar menggunakan beberapa partisi biner sehingga cosest X diperiksa terlebih dahulu, Anda mungkin sedikit mempercepat pemeriksaan Anda.

Anda dapat menggunakan semacam algoritma "Naval Battles" untuk memeriksa blok Xs sekaligus (pada dasarnya mencari X yang ada di arah yang dapat membuat bayangan kerucut lebih luas)

[EDIT]

Diperlukan dua sinar untuk membuat bayangan dengan benar dan, karena ubin berbentuk persegi panjang, banyak asumsi dapat dilakukan dengan menggunakan simetri yang tersedia.

Koordinat ray dapat dihitung menggunakan partisi ruang sederhana di sekitar ubin rintangan:

Setiap area persegi panjang merupakan pilihan tentang sudut ubin apa yang harus diambil sebagai tepi kerucut bayangan.

Alasan ini dapat didorong lebih jauh untuk menghubungkan beberapa ubin yang berdekatan dan membiarkannya membentuk kerucut yang lebih luas sebagai berikut.

Langkah pertama adalah memastikan bahwa tidak ada rintangan yang mengarah ke arah pengamat, dalam hal ini yang dianggap sebagai hambatan terdekat adalah:

Jika ubin kuning merupakan kendala, ubin itu menjadi ubin merah baru.

Sekarang mari kita perhatikan tepi kerucut atas:

Ubin biru adalah semua kandidat yang memungkinkan untuk membuat bayangan kerucut lebih luas: jika setidaknya salah satu dari mereka adalah penghalang, sinar dapat dipindahkan menggunakan ruang yang berpisah di sekitar ubin seperti yang terlihat sebelumnya.

Ubin hijau adalah kandidat hanya jika pengamat berada di atas garis oranye yang mengikuti:

Yang sama adalah singkatan dari ray lain dan untuk posisi lain dari pengamat tentang hambatan merah.

Gagasan yang mendasarinya adalah untuk mencakup area sebanyak mungkin untuk setiap casting kerucut dan untuk mempersingkat secepat mungkin daftar hambatan untuk diperiksa.

Masalah yang Anda coba selesaikan kadang-kadang disebut Field of View, singkatnya FOV. Seperti yang Anda sebutkan roguelikes sebagai contoh, Anda harus melihat apa yang dikatakan wiki RogueBasin tentang subjek (bahkan ada tautan ke implementasi): http://www.roguebasin.com/index.php?title=Field_of_Vision

Ada beberapa algoritma berbeda dengan pro dan kontra yang berbeda - perbandingan yang sangat praktis juga tersedia di RogueBasin: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

Saya juga menemukan ini yang memiliki demo yang berfungsi:

http://www.redblobgames.com/articles/visibility/

Anda mungkin menemukan http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx berguna bersama dengan sisa seri .