Bekerja dengan banyak kubus. Meningkatkan kinerja?

12

Sunting: Singkatnya, saya memiliki dunia berbasis voxel (gaya Minecraft (Thanks Communist Duck)) yang menderita karena kinerja yang buruk. Saya tidak positif pada sumbernya tetapi ingin saran yang mungkin tentang bagaimana menghilangkannya.

Saya sedang mengerjakan sebuah proyek di mana dunia terdiri dari sejumlah besar kubus (saya akan memberi Anda angka, tetapi itu adalah dunia yang ditentukan pengguna). Tes saya adalah sekitar (48 x 32 x 48) blok.

Pada dasarnya balok-balok ini tidak melakukan apa pun dalam diri mereka. Mereka hanya duduk di sana.

Mereka mulai digunakan ketika datang ke interaksi pemain.

Saya perlu memeriksa kubus apa yang berinteraksi dengan mouse pengguna (mouse over, mengklik, dll.), Dan untuk mendeteksi tabrakan saat pemain bergerak.

Sekarang saya memiliki banyak lag pada awalnya, melewati setiap blok.

Saya telah berhasil mengurangi kelambatan itu, dengan mengulangi semua blok, dan menemukan blok mana yang berada dalam kisaran karakter tertentu, dan kemudian hanya mengulangi blok tersebut untuk deteksi tabrakan, dll.

Namun, saya masih mengalami tekanan 2fps.

Adakah yang punya ide lain tentang bagaimana saya bisa mengurangi keterlambatan ini?

Btw, saya menggunakan XNA (C #) dan ya, itu 3d.

Joel
sumber
Apakah maksud Anda seperti Minecraft? Yaitu, voxel?
Bebek Komunis
4
Sudahkah Anda melihat ke oktaf? en.wikipedia.org/wiki/Octree
bummzack
1
Sudahkah Anda mencoba membuat profil game Anda? Ini mungkin menunjukkan beberapa bidang utama di mana sebagian besar waktu dihabiskan. Mungkin bukan itu yang Anda pikirkan.
decaviatedcaviar
2
Daripada menggambar semua 6 wajah dari setiap kubus, Anda hanya bisa menggambar wajah yang tidak bersentuhan dengan apa pun
David Ashmore
1
@ David: Ya, atau dia bisa berhenti melakukan satu panggilan undian per kubus terlebih dahulu, dan kemudian khawatir tentang poligon individu nanti.
Olhovsky

Jawaban:

20

Sepertinya Anda ingin belajar tentang Pohon!

Dan saya serius, jika Anda saat ini mengulang array dari semua kubus Anda, maka Anda benar-benar harus melihat ke dalam berbagai struktur data spasial. Untuk kasus ini, cara terbaik untuk membayangkan kembali dunia kubus Anda adalah sebagai pohon.

Sebelum kita masuk ke alasan mengapa, mari kita pikirkan masalah kita. Kami sedang mencari solusi di mana, untuk biaya sesedikit mungkin, kami dapat mengambil daftar kubus terdekat yang mungkin bertabrakan dengan pemain. Daftar ini harus sekecil mungkin, namun setepat mungkin.

Sekarang untuk menentukan zona ini, kita perlu memetakan ruang koordinat pemain kita ke ruang koordinat peta kubus; yaitu, kita perlu memetakan posisi titik mengambang pemain ke indeks diskrit array multi-dimensi kubus (contoh notasi mungkin world[31][31][31], yaitu tepat tengah untuk array multidimensi 64 * 64 * 64).

Kita bisa menghitung blok di sekitarnya menggunakan pengindeksan diskrit yang sama, mungkin mengambil sampel hanya kubus di dekatnya, tetapi ini masih membutuhkan perhitungan ulang yang konstan, dan tidak memungkinkan untuk objek yang tidak terpisah dalam penempatan (yaitu mungkin tidak memetakan ke kubus peta).

Situasi yang ideal adalah satu set ember yang berisi set kubus kami untuk bagian tertentu dari peta kubus kami, dibagi rata sehingga alih-alih menghitung ulang daerah sekitarnya, kami cukup bergerak masuk dan keluar dari zona ini . Untuk perhitungan non-sepele, memegang data kami seperti ini bisa menghilangkan iterasi semua kubus, dan hanya set individu ini yang berada di dekatnya.

Pertanyaannya adalah: Bagaimana kita menerapkan ini?

Untuk dunia 64 * 64 * 64, bayangkan dunia dipecah menjadi 8 * 8 * 8 zona . Ini berarti bahwa di dunia Anda, Anda akan memiliki 8 zona per sumbu (X, Y, Z). Masing-masing zona ini akan berisi 8 kubus, mudah diambil oleh indeks baru yang disederhanakan ini.

Jika Anda perlu melakukan operasi pada satu set kubus terdekat, alih-alih iterasi setiap kubus di dunia Anda, Anda bisa dengan mudah beralih ke zona ini , meruntuhkan jumlah iterasi maksimum dari 64 * 64 * 64 (262144) asli ke hanya 520 (8 * 8 * 8 + 8).

Sekarang perkecil dari dunia zona ini, dan tempatkan zona itu ke zona super besar ; dimana masing - masing zona super berisi 2 * 2 * 2 zona reguler . Karena dunia Anda saat ini berisi 512 (8 * 8 * 8) zona , kami dapat memecah 8 * 8 * 8 zona menjadi 64 (4 * 4 * 4) zona super dengan membagi 8 zona dengan 2 zona per zona super . Menerapkan logika yang sama dari atas, ini akan mematahkan iterasi maksimum dari 512 ke 8 untuk menemukan super-zone ; dan kemudian maksimum 64 untuk menemukan zona proses(total maks 72)! Anda dapat melihat bagaimana ini sudah menghemat banyak iterasi (262144: 72).

Saya yakin Anda dapat melihat sekarang betapa bermanfaatnya pohon. Setiap zona adalah cabang di pohon, dengan masing - masing zona super sebagai cabang sebelumnya. Anda hanya melintasi pohon untuk menemukan apa yang Anda butuhkan; menggunakan set data yang lebih kecil untuk meminimalkan biaya keseluruhan.

Diagram di bawah ini akan membantu Anda memvisualisasikan konsep. (gambar dari Wikipedia: Octrees ): Oktree

Penolakan:

Dalam pengaturan ideal seperti di atas, di mana dunia voxel Anda sudah diletakkan dalam array multi-dimensi ukuran tetap, Anda bisa menanyakan posisi pemain, lalu mengindeks blok di sekitarnya dengan biaya O (1)! (Lihat penjelasan Olhovskys) Tapi ini menjadi lebih sulit ketika Anda mulai mempertimbangkan bahwa dunia Anda jarang ukuran tetap dalam permainan voxel; dan Anda mungkin perlu struktur data Anda untuk dapat memuat seluruh zona super dari HDD ke memori. Tidak seperti array multi-dimensi ukuran tetap, pohon mudah memungkinkan ini tanpa terlalu banyak waktu dihabiskan untuk algoritma kombinatori.

kaviar melambat
sumber
Saya akan mengatakan saya mendapatkannya, tetapi sayangnya saya tidak mendapatkannya. Kotak tabrakan blok tidak bergerak, hanya kotak tabrakan pemain. Dan saya punya metode sekarang yang (tanpa perulangan melalui semua blok) mengembalikan semua blok yang berada dalam radius 5 blok pemain. Maaf atas kerumitannya, tetapi ada klarifikasi? Ngomong-ngomong, untuk membuatnya lebih sederhana, dapatkah Anda menganggap dunia ini 64 x 64 x 64?
Joel
Dan saya masih mendapatkan sekitar 5fps :(
Joel
Saya mengucapkan kembali jawaban saya, beri tahu saya jika itu membantu.
decaviatedcaviar
Jadi saya mempersempit blok di mana pemain bisa, menggunakan teknik octree ini. Saya cukup yakin saya mengerti. Tetapi apakah Anda menyarankan saya menggunakan deteksi tabrakan saya setelah saya mempersempitnya menjadi hanya beberapa blok, atau apakah Anda memiliki beberapa metode lain?
Joel
2
Kecuali jika pemain sangat besar relatif terhadap ukuran kubus, maka memeriksa tabrakan di sekitar pemain mungkin adalah cara tercepat. Jika pemain tidak menempati ruang lebih dari satu kubus misalnya, maka ia hanya perlu memeriksa 27 kubus sekitarnya paling banyak, untuk menemukan tabrakan. Ini tidak memerlukan pohon karena Anda dapat mengindeks langsung ke lokasi kubus itu, dengan asumsi ia menyimpan kubus dalam array yang dapat diindeksinya, dengan satu slot dialokasikan untuk setiap lokasi kubus yang mungkin.
Olhovsky
13

Saya setuju dengan Daniels jawaban, di iterasi bahwa melalui jumlah besar kotak adalah penyebab paling mungkin, dan bahwa dengan menggunakan partisi spacial Anda bisa mempercepat permainan sampai banyak - tapi masalahnya bisa juga berada di tempat lain, dan Anda bisa membuang-buang waktu Anda .

Untuk meningkatkan kecepatan gim Anda secara signifikan, Anda perlu membuat profil kode Anda. Identifikasi di mana hambatannya, ini akan memungkinkan Anda untuk melakukan perbaikan terbesar.

Ada banyak cara untuk membuat profil kode Anda, Anda dapat menggulung kelas analisis kinerja Anda sendiri (yang dapat menggunakan kelas Stopwatch (MSDN) ), atau Anda dapat menggunakan PIX untuk mendapatkan gambaran umum tentang seberapa sibuk CPU / GPU. .

Anda juga dapat menempatkan penanda acara PIX dalam kode Anda, yang akan muncul sebagai wilayah berwarna dalam pembacaan PIX. Tidak ada antarmuka C # resmi untuk fungsi-fungsi ini, tetapi utas ini menunjukkan bagaimana Anda dapat membuat antarmuka C # sendiri.

CiscoIPPhone
sumber
2
+1, sepenuhnya setuju. Anda seharusnya tidak melihat ke dalam algoritma, Anda harus melihat profiling kode Anda. Dugaan saya adalah tidak ada hubungannya dengan fakta bahwa Anda melakukan iterasi melalui blok (tidak banyak), itulah yang Anda lakukan dengan setiap blok. Pada akhirnya ya Anda harus memiliki metode yang lebih baik daripada brute force, tetapi jika Anda tidak dapat menangani iterasi sederhana pada 48x32x48 kubus, Anda perlu memikirkan kembali apa yang Anda lakukan dengan setiap kubus, bukan bagaimana Anda mengulang.
Tim Holt
4
@Tim: Kecuali jika pemainnya cukup besar untuk menempati ruang 48x32x48, maka dia seharusnya tidak melakukan iterasi melalui kubus sebanyak itu. Jika dia melakukan iterasi melalui 73.000 kubus per frame, maka saya dapat memberitahu Anda tanpa membuat profil apa pun, bahwa itu layak baginya untuk memperbaikinya, jika tanpa alasan lain selain belajar bagaimana menghindari melakukan iterasi sepuluh ribu kali lebih banyak daripada diperlukan. Ini bukan apa yang saya sebut optimasi mikro atau prematur.
Olhovsky
Pemain saya kurang dari ukuran 1 kubus, meskipun mungkin lebih besar pada tahap tertentu (tapi tidak banyak)
Joel
Randomman159: Maka Anda hanya perlu menguji 27 kubus sekitarnya untuk menemukan tabrakan. Lihat jawaban saya.
Olhovsky
6

Jika pemain Anda relatif besar dengan ukuran kubus, maka Anda mungkin menginginkan sebuah oktaf atau struktur partisi spasial lainnya, seperti yang disarankan orang lain.

Namun, jika pemain Anda relatif kecil dengan ukuran kubus, maka mungkin cara tercepat untuk mendeteksi tabrakan dengan kubus adalah dengan melakukan pencarian linear sederhana dari area di sekitar pemain.

Karena pemain Anda lebih kecil dari 1 kubus, maka Anda hanya perlu menguji tabrakan terhadap 27 kubus tetangga, paling banyak.

Ini mengasumsikan bahwa Anda menyimpan kubus dalam array yang dapat Anda indeks, dengan satu slot dalam array untuk setiap kubus.

Seperti yang ditunjukkan oleh orang lain, Anda perlu membuat profil kode Anda untuk melihat apa yang sebenarnya memperlambat Anda.

Jika saya harus menebak, saya akan mengatakan bahwa Anda mungkin melakukan panggilan draw untuk setiap kubus, yang akan menjadi hambatan Anda sejauh ini. Untuk memperbaikinya, Anda harus melihat ke geometance instancing.

Olhovsky
sumber
Atau Anda bisa memiliki 'kotak pembatas' yang mengelilingi pemain, dan kemudian Anda cukup memeriksa objek apa yang bertabrakan untuk menentukan objek apa yang pemain harus bertabrakan. Mesin fisika yang baik akan dapat melakukan semua optimasi untuk Anda; itu juga akan memungkinkan lebih dari sekedar 'blok' untuk bertabrakan.
decaviatedcaviar
Secara pribadi, saya tidak ingin bergantung pada kata kunci mesin fisika untuk menguji 73.000 kubus untuk saya, ketika saya hanya bisa menulis dua lusin atau lebih baris kode untuk secara efisien menguji tabrakan untuk saya. Juga, dia mungkin tidak memiliki mesin fisika untuk memanfaatkan saat ini.
Olhovsky
1

Satu saran lagi untuk mempercepat: Blok-blok Anda kira-kira sudah diperbaiki - itu artinya tidak mungkin seorang pemain dapat bertabrakan dengan sebagian besar dari mereka. Tambahkan boolean ke blok yang menunjukkan apakah mereka terbuka atau tidak. (Ini dapat dihitung ulang dengan melihat tetangga mereka.) Blok yang tidak terekspos tidak perlu diperiksa untuk tabrakan.

Jelas sekali Minecraft melakukan sesuatu yang mirip dengan ini - saya menabrak bongkahan yang tidak dimuat yang memberi saya pandangan ke dunia - saya bisa melihat menembus tanah yang kokoh, yang muncul hanyalah ruang terbuka (sisi jauh dari mereka adalah permukaan terbuka dan karenanya dirender.)

Loren Pechtel
sumber
-1

Saya punya masalah dengan mesin voxel saya.

Solusi: (Jauh lebih sederhana dari segi delapan) Alih-alih mengulangi semua blok, cukup gunakan persamaan untuk menentukan posisi blok dalam array blok.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Kemudian jika Anda ingin melihat apakah ada blok:

Blocks[BlockIndex].Type > -1;

Atau bagaimanapun Anda menentukan apakah blok itu ada.

BMW
sumber
Masalah di sini lebih rumit, karena Anda hanya memiliki 2 koordinat untuk mouse Anda, untuk menguji dengan dunia 3D. Jika tampilan top-down, Anda dapat menemukan 2 dari 3 indeks yang tepat untuk posisi mouse, dan kemudian loop untuk ketinggian, mulai dari atas - lebih dekat ke kamera, dan menemukan kemunculan pertama blok.
Markus von Broady