Mengapa ukuran chunk sering kali memiliki kekuatan dua?

15

Ada banyak klon Minecraft di luar sana dan saya sedang mengerjakan implementasi saya sendiri. Prinsip rendering medan adalah ubin seluruh dunia dalam potongan ukuran tetap untuk mengurangi upaya perubahan lokal.

Di Minecraft ukuran chunk adalah 16 x 16 x 256 sejauh yang saya miliki sekarang. Dan di klon saya juga selalu melihat ukuran bongkahan kekuatan nomor 2.

Apakah ada alasan untuk itu, mungkin terkait kinerja atau memori? Saya tahu bahwa kekuatan 2 memainkan peran khusus dalam komputer biner tetapi apa hubungannya dengan ukuran chunk?

danijar
sumber
1
Sangat menyenangkan bahwa Anda dapat terus membaginya dengan dua dan mendapatkan kembali angka. (Bukan jawaban yang lengkap, tetapi sesuatu yang berguna tentang menggunakan nomor seperti 2^n)
ashes999

Jawaban:

27

Ini akan tergantung pada game dan struktur pengindeksan yang digunakan untuk potongan. Meskipun, pada tingkat setinggi itu, kemungkinan besar itu tidak ada hubungannya dengan memori atau peningkatan kinerja tertentu. Kemungkinan besar ini adalah keputusan yang sewenang-wenang untuk menentukan ukuran potongan dengan cara yang dapat diprediksi. Hal ini memungkinkan untuk beberapa trik penghitungan dan pengindeksan menggunakan bit shifting yang tidak mungkin dilakukan dengan angka yang bukan kekuatan dua.

Misalnya, menghitung dalam kekuatan dua semudah menggeser sedikit dalam biner:

Dec =  Bin
1   =  000001
2   =  000010
4   =  000100
8   =  001000
16  =  010000
32  =  100000

Di mana pintasan ini akan digunakan akan tergantung pada pengembang dan masalah apa yang mereka coba selesaikan.

Jika Anda membuat keputusan untuk ukuran apa untuk membuat potongan, dan itu tidak masalah dalam aspek lain, Anda juga dapat menggunakan sesuatu yang akrab dan memiliki manfaat yang biasa Anda gunakan.

MichaelHouse
sumber
15

Pertama, mengalikan dengan kekuatan dua jauh lebih murah daripada mengalikan dengan angka sewenang-wenang, karena Anda dapat melakukannya dengan menggeser sedikit . Sebagian besar waktu kompiler dapat melakukan ini untuk Anda, jadi setiap kali Anda menulis "* 16" dalam kode Anda, kompiler benar-benar melakukan pergeseran empat, dan Anda tidak perlu khawatir tentang hal itu - Anda hanya perlu memberikan kompilasi peluang dengan merancang struktur data Anda dengan cara ini.

Kedua, karena jalur cache, bus memori, dan informasi jalan raya lainnya di komputer Anda juga cenderung dirancang untuk menggunakan kekuatan dua, Anda mungkin mendapatkan kinerja yang lebih baik secara keseluruhan dengan cara ini.

Ketiga, kita para geek tua hanya terbiasa bermain-main dengan kekuatan dua, jadi itu kebiasaan.

(Keempat, Geeks tua lainnya yang mendesain perangkat keras dan kompiler Anda juga menyukai kekuatan dua, jadi ini tidak akan berubah dalam waktu dekat).

Jari Komppa
sumber
2
+1 "Ketiga, kami Geeks tua hanya terbiasa bermain-main dengan kekuatan dua, jadi itu kebiasaan." Ini mungkin alasan utama .
Laurent Couvidou
9

Jawaban sebenarnya adalah ini: Pada komputer biner, kekuatan dua adalah angka bulat yang bagus.

Ketika orang normal perlu memilih nomor acak untuk suatu tujuan, mereka biasanya memilih angka bulat yang bagus dalam sistem angka yang mereka sukai, basis 10. Jadi mereka akan memilih 10, 100, 1000, dll. Karena mereka sederhana dan mudah dan tidak memerlukan banyak pemikiran dan nilai yang tepat tidak terlalu penting bagi mereka, mereka hanya bertujuan pada skala umum besarnya.

Sebagai pemrogram, ketika kita perlu memilih angka acak untuk suatu tujuan, kita biasanya memilih angka bulat yang bagus dalam sistem angka yang digunakan komputer, basis 2. Jadi kita akan memilih 2, 4, 8, dll. Karena mereka sederhana dan mudah dan tidak memerlukan banyak pemikiran dan nilai tepatnya tidak terlalu penting bagi kami, kami hanya bertujuan pada skala umum besarnya.

Benar-benar tidak lebih rumit dari itu. Itu angka bulat yang bagus.

Trevor Powell
sumber
6

Salah satu alasan yang tidak disebutkan dalam jawaban lain adalah bahwa jika diperlukan, kekuatan dua angka selalu dapat dibelah dua tanpa menyelesaikan masalah. Ini mungkin bukan alasan di klon Minecraft, tetapi dalam beberapa kasus lain seperti dalam tekstur dengan mipmaps .

msell
sumber
2

Alasan potensial lainnya adalah memungkinkan Anda untuk menyandikan informasi tentang setiap chunk dalam tekstur 3D. Jika perangkat keras target Anda mendukung tekstur 3D tetapi tidak memiliki dukungan tekstur non-power-of-two yang sepenuhnya kuat dan umum (yang saya akui Anda ingin memotret dengan sangat rendah), maka membuat ukuran chunk Anda menjadi dua tidak hanya ideal - ini penting.

Maximus Minimus
sumber