Students Save 30%! Learn & create with unlimited courses & creative assets Students Save 30%! Save Now
Advertisement
  1. Game Development
  2. Game Development
Gamedevelopment

Ubah semula Senarai Paparan Anda Dengan Hashes Spatial

by
Difficulty:IntermediateLength:MediumLanguages:

Malay (Melayu) translation by Hamdan Veerlax (you can also view the original English article)

Dalam mana-mana permainan 2D, anda perlu tahu apa perintah untuk menarik sprite anda. Anda biasanya menarik dari belakang tempat kejadian ke bahagian depan, dengan benda-benda yang terdahulu diliputi oleh yang kemudian. Ini adalah Algoritma Painter standard yang digunakan untuk mewakili kedalaman pada kanvas (digital atau sebaliknya).

In the Painters Algorithm distant objects are drawn first
Oleh Zapyon - Kerja sendiri, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

Cara yang paling mudah untuk menjejaki ini adalah dengan memasukkan semua objek anda ke dalam satu array besar, disusun dengan kedalaman mereka. Jadi dalam kejadian di atas, array anda akan kelihatan seperti: [Gunung, Ground, Tree1, Tree2, Tree3, ...]

Masalah dengan Array Big Satu

Masalah dengan satu senarai paparan pusat adalah bahawa tidak ada cara mudah untuk mengetahui objek mana yang berada pada skrin pada bila-bila masa tertentu. Untuk melakukan itu, anda perlu melengkung melalui keseluruhan array dan semak setiap objek tunggal. Ini kebanyakannya menjadi isu jika anda mempunyai dunia permainan yang besar di mana banyak objek ada di luar skrin dan tidak boleh diberikan atau dikemas kini.

Hash spatial adalah cara menyimpan objek anda untuk mengelakkan masalah ini. Perkara yang kemas tentang menggunakan hash adalah sentiasa mengambil masa yang tetap untuk mengetahui objek yang berada di skrin, tanpa mengira betapa besarnya dunia permainan!

Sekarang kebanyakan enjin permainan tidak akan membiarkan anda bermain-main dengan bagaimana mereka menyusun objek mereka secara dalaman, tetapi jika anda memprogram dalam persekitaran di mana anda mengawal panggilan menarik (seperti enjin OpenGL anda sendiri, JavaScript tulen permainan, atau lebih banyak kerangka terbuka seperti LÖVE), ini mungkin sesuatu yang patut dilaksanakan.

Alternatif: Hashes Spatial

Hash spatial hanya mempunyai hash table di mana setiap kunci adalah koordinat 2D dan nilai adalah daftar objek permainan di kawasan itu.

Translation service is temporarily unavailable Berikut adalah cara anda mencari sesuatu di kedudukan (420,600) jika anda telah melaksanakannya dalam JavaScript:

Itu mudah! Anda boleh mengetahui dengan segera apa yang ada dalam kedudukan itu. Kuncinya ialah penyambungan rentetan koordinat X dan Y, tetapi ia tidak perlu menjadi rentetan, ataupun ia memerlukan koma di tengah; ia hanya perlu unik untuk setiap pasangan X dan Y.

Untuk melihat mengapa ini sangat mudah, pertimbangkan bagaimana anda akan mendapatkan objek di kedudukan ini dengan menggunakan satu jajaran yang besar:

Kami memeriksa setiap objek, walaupun sebahagian besarnya sangat jauh untuk dimulakan! Ini sangat boleh melumpuhkan prestasi anda jika anda melakukan banyak pencarian seperti ini dan array gameObjects anda adalah besar.

Contoh Konkrit

Sekiranya anda belum yakin betapa bergunanya ini, inilah demo yang ditulis dalam JavaScript tulen di mana saya cuba menjadikan satu juta benda di dunia permainan. Dalam kedua-dua kes, hanya objek pada skrin yang sebenarnya diberikan.

One Big Display List

Klik untuk melihat demo langsung yang sedang dijalankan!

Spatial Hash

Dan versi hash spatial hidup.

Versi array tunggal sangat lambat. Walaupun anda menyimpan unsur-unsur mana yang berada di skrin supaya anda tidak perlu menyemak setiap bingkai, anda masih perlu menyemak semula keseluruhannya apabila kamera bergerak, yang membawa kepada kecacatan yang teruk.

Hanya mengubah cara kita menyimpan objek permainan kita boleh membuat semua perbezaan antara pengalaman yang lancar dan permainan yang tidak dapat dimainkan.

Melaksanakan Hash Spatial

Hash spatial harus benar-benar mudah diterapkan dalam bahasa apa pun (sebenarnya, dari contoh pertama ke yang kedua di atas hanya mengambil 30 baris kod tambahan!)

Terdapat empat langkah untuk melaksanakan ini sebagai sistem persembahan anda:

  1. Sediakan jadual hash.
  2. Tambah dan alih keluar objek dalam hash.
  3. Mengumpul objek di mana-mana kawasan tertentu.
  4. Isih objek mengikut kedalaman sebelum memberikannya.

Anda dapat melihat pelaksanaan fungsi dalam JavaScript pada GitHub sebagai rujukan.

1. Sediakan Jadual Hash

Kebanyakan bahasa mempunyai beberapa hash terbina dalam / peta. Hash spatial kami hanya jadual hash standard. Dalam JavaScript anda boleh mengisytiharkan satu dengan:

Satu-satunya perkara lain yang perlu disebutkan di sini adalah bahawa anda mempunyai kelonggaran dengan memilih saiz sel. Secara umumnya, sel-sel anda menjadi dua kali lebih besar daripada objek purata anda seolah-olah berfungsi dengan baik. Jika sel anda terlalu besar maka anda akan menarik terlalu banyak objek dengan setiap pencarian. Jika mereka terlalu kecil maka anda perlu menyemak lebih banyak sel untuk menutup kawasan yang anda inginkan.

2. Tambah dan Buang Objek di Hash

Menambah objek ke hash hanyalah satu perkara yang mengoyakkannya ke sel, mewujudkan array sel jika ia tidak wujud, dan menambahkannya pada array itu. Inilah versi JavaScript saya:

Terdapat kaveat, walaupun: Bagaimana jika objek anda menjangkau pelbagai sel, atau terlalu besar untuk dimuatkan dalam satu sel?

An object in multiple cells

Penyelesaiannya hanya untuk menambahkannya ke semua sel yang disentuhnya. Ini menjamin bahawa jika mana-mana bahagian objek dilihat maka ia akan diberikan. (Sudah tentu, maka anda juga perlu memastikan anda tidak membuat objek ini berkali-kali.)

Saya tidak melaksanakan fungsi keluarkan dalam contoh saya, tetapi mengeluarkan objek hanyalah mengambil alih dari array (s) ia adalah sebahagian daripada. Untuk membuat ini lebih mudah, anda boleh mempunyai setiap objek menyimpan rujukan ke mana sel-sel itu miliknya.

3. Kumpulkan Objek di Kawasan Yang Diterima

Sekarang ini inti teknik ini: diberikan kawasan di skrin, anda mahu dapat mendapatkan semua objek di sana.

Apa yang perlu anda lakukan di sini adalah bermula melalui semua sel berdasarkan kamera di mana anda berada di dunia permainan, dan mengumpulkan semua sub-senarai bersama-sama ke dalam satu array untuk memberi. Berikut adalah coretan JavaScript yang berkaitan:

4. Susun objek mengikut Kedalaman Sebelum Menyajikan Mereka

Anda mungkin menyedari sekarang bahawa menyerah pada idea senarai paparan yang besar juga bermakna anda menyerah pada penyortiran kedalaman yang mudah. Kami merampas objek dari grid kami berdasarkan lokasi mereka, tetapi array yang kami dapatkan tidak disusun dengan cara apapun.

Sebagai langkah terakhir sebelum membuat rendering, kita perlu menyusun array kami berdasarkan beberapa kunci. Saya memberikan setiap objek nilai mendalam, dan saya boleh lakukan:

Sebelum akhirnya membuat segala-galanya:

Ini adalah salah satu kelemahan untuk kaedah ini, bahawa anda perlu menyusun apa yang ada di skrin setiap bingkai. Anda sentiasa boleh mempercepatkannya dengan memastikan semua sub-senarai anda diisih, supaya anda boleh menggabungkannya semasa anda mengikat untuk mengekalkan pesanan.

Itu sahaja! Anda kini perlu mempunyai sistem persembahan kerja (mudah-mudahan lebih cepat)!

Kegunaan & Tips Lain

Ini boleh menjadi teknik yang sangat berguna, tetapi seperti yang saya katakan dalam pengenalan, anda hanya boleh melakukan ini dalam enjin atau rangka permainan yang memberi anda kawalan ke atas panggilan menarik. Namun, ada perkara yang anda boleh menggunakan hash spatial untuk rendering selain. Malah, mereka lebih sering digunakan untuk mempercepatkan pengesanan perlanggaran (anda boleh melangkau sebarang pemeriksaan perlanggaran untuk objek yang anda tahu jauh atau tidak berada di dalam sel yang sama).

Teknik lain yang serupa dengan hash spatial, tetapi sedikit lebih rumit, menggunakan kuadran. Sedangkan hash spasi hanya grid yang rata, quadtree lebih struktur hierarkis, jadi anda tidak perlu risau tentang saiz sel, dan anda dapat dengan cepat mendapatkan semua objek di suatu kawasan tertentu tanpa harus memeriksa setiap sedikit sel.

Secara umumnya, anda harus ingat bahawa struktur spatial tidak semestinya penyelesaian terbaik. Ia sesuai untuk permainan yang mempunyai:

  • dunia yang besar dengan banyak objek
  • agak sedikit objek pada skrin berbanding saiz dunia
  • kebanyakan objek statik

Jika semua objek anda bergerak sepanjang masa, anda perlu terus mengeluarkan dan menambahnya ke sel yang berbeza, yang mungkin dikenakan penalti prestasi yang penting. Ia adalah sistem persembahan yang ideal untuk permainan seperti Move or Die (hampir dua kali ganda fps) kerana tahap terdiri daripada banyak objek statik, dan watak-watak adalah satu-satunya perkara yang bergerak.

Mudah-mudahan tutorial ini telah memberi anda idea tentang bagaimana penstrukturan data secara spasial boleh menjadi cara yang mudah untuk meningkatkan prestasi, dan bagaimana sistem penyampaian anda tidak semestinya menjadi senarai linear tunggal!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.