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

24

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.

Rogach
sumber
1
Ups, kesalahan saya, NetHack tidak main-main dengan saling berhadapan :)
Rogach
Beberapa ide lama dapat ditemukan di fadden.com/tech/fast-los.html , meskipun itu mengingatkan kembali pada hari-hari ketika CPU cukup lambat dan perhitungan floating point adalah sesuatu yang sebaiknya dihindari.
fadden

Jawaban:

10

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:

masukkan deskripsi gambar di sini

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

David Gouveia
sumber
Haruskah saya "berjalan" di sepanjang setiap sinar dengan jarak tetap (katakanlah, 0,3 poin) atau apakah saya perlu menjalankan sesuatu seperti algoritma Besenham pada setiap sinar?
Rogach
Jika Anda maju hanya dengan jarak tetap Anda akan mendapatkan masalah dengan ubin yang terlewat. Lihat tutorial ini tentang raycasting . Saya akan mengedit sumber daya itu menjadi jawaban saya juga. Anda pada dasarnya memeriksa tabrakan horizontal dan vertikal secara terpisah.
David Gouveia
1
Algoritma itu baik, tetapi akan membutuhkan sejumlah besar sinar untuk bekerja secara benar dengan terowongan panjang 1-ubin-lebar.
HolyBlackCat
@HolyBlackCat - itu akan menjadi kasus hanya jika Anda mengirim sinar di sudut bahkan di semua arah. Tetapi Anda dapat menghindari mengirimkan sebagian besar dari sinar-sinar itu dan hanya melemparkannya pada garis di adegan Anda. Berikut ini penjelasan yang bagus: redblobgames.com/articles/visibility
Rogach
8

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:

Contoh partisi ruang

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:

pilih rintangan terdekat

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

Sekarang mari kita perhatikan tepi kerucut atas:

ubin calon

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:

pemeriksaan diperpanjang

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.

FxIII
sumber
Pendekatan yang menarik dan mungkin ide yang lebih baik karena sifatnya yang subtraktif. Setelah membaca ini saya mungkin akan menerapkannya dengan cara ini juga.
David Gouveia
Saya dapat melihat masalah dalam situasi seperti ini . Pemain berwarna kuning, rintangan berwarna biru dan ungu. Pemain harus bisa melihat rintangan ungu (seperti yang ditunjukkan sinar hijau). Tapi sinar bayangan merah yang melewati rintangan biru menolak ubin ungu. Tapi saya kira versi line of sight berpotensi memiliki masalah lebih besar dari ini.
David Gouveia
Masalah ini berasal dari definisi "tersembunyi": ketika sinar memotong ubin, hampir tidak pernah akan menutupi ini sepenuhnya. Masalah yang sama diselesaikan dengan aliasing ketika membuat segmen garis. Secara pribadi saya berpikir bahwa ubin disembunyikan ketika bagian utama tertutup, orang dapat mendefinisikannya tersembunyi sepenuhnya tertutup, Anda mungkin menemukan jika itu mengekspos sisi yang berpotensi dapat membuat bayangan kerucut lebih luas ... Pokoknya, Anda dapat delist hanya blok yang sepenuhnya tertutup.
FxIII
@ David Gouveia - masalah apa yang lebih besar?
Rogach
@ David Gouveia - Saya sudah mencoba pendekatan dengan bayangan "kerucut", dan itu sangat tidak efisien. Adapun ketepatan sinar visibilitas - ~ 5500 sinar cukup untuk melihat dinding 20 ubin di setiap arah jika Anda berdiri langsung di dekatnya, dan karena jarak di mana hanya satu ubin terlihat jauh lebih banyak. Dan tentang kehilangan beberapa ubin pada jarak yang lebih besar - well, tidak semua orang memiliki penglihatan prefek, eh?
Rogach
8

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

Tapio
sumber
Ringkasan yang benar-benar bagus dan lengkap!
Rogach
Situs web itu adalah sumber yang bagus, terima kasih telah berbagi tautan itu. Ini juga berisi deskripsi yang luar biasa dimengerti tentang bagaimana A * pathfinding bekerja :-)
uliwitness
Tautan dalam jawaban sekarang menuju ke beranda situs - roguebasin.com/index.php?title=Category:FOV tampaknya merupakan kecocokan yang masuk akal.
fadden