Ini untuk flash game, dengan tampilan isometrik. Saya perlu tahu cara mengurutkan objek sehingga tidak perlu memeriksa z-buffer saat menggambar. Ini mungkin tampak mudah tetapi ada batasan lain, sebuah adegan dapat memiliki 10.000 objek sehingga algoritma harus dijalankan dalam waktu kurang dari O (n ^ 2). Semua objek adalah kotak persegi panjang, dan ada 3-4 objek bergerak dalam adegan. Apa cara terbaik untuk melakukan ini?
MEMPERBARUI
di setiap ubin hanya ada objek (maksudku benda tidak bisa menumpuk di atas satu sama lain). dan kami mengakses kedua Obyek dan Objek memiliki posisi sendiri.
UPDATE2
lihat angka-angka ini:
pertama satu objek biru pertama harus digambar kemudian hijau lalu merah. sedangkan yang kedua Anda harus menggambarnya dalam urutan terbalik. Anda perlu menggambar objek merah pertama dan kemudian hijau dan akhirnya biru. seperti yang Anda lihat tidak ada perbedaan posisi benda biru dan merah, keduanya memiliki jarak yang berbeda dari kamera dan sebagainya. tetapi karena posisi relatif mereka ke kotak hijau, Anda perlu mengubah urutan pengundian antara dua gambar. itulah yang membuat masalah ini berantakan.
Catatan: karena semua objek adalah prisma segi empat, secara matematis dapat dibuktikan bahwa setidaknya ada satu urutan undian untuk memenuhi kebutuhan masalah.
sumber
Jawaban:
Ini sebenarnya sangat sederhana jika objek Anda cocok dengan ubin isometrik Anda. Lihatlah gambar ini:
Pertama-tama Anda harus menggambar objek pada posisi merah, lalu objek dengan warna biru, lalu hijau, lalu kuning, lalu magenta, dan seterusnya ... Seharusnya sudah cukup jelas bagaimana menerapkan ini jika papan Anda memiliki objek di dalamnya alih-alih objek memiliki posisi sebagai atribut. Jika itu bukan kasus Anda, Anda harus menyimpan struktur data terpisah, memperbaruinya setiap kali objek bergerak (yang seharusnya juga cukup mudah.)
Ini memiliki masalah baru: Anda dapat dengan mudah melihat bagaimana sekarang kompleksitasnya adalah O (N) di mana N adalah ukuran papan Anda (
N=W*H). Untuk mengatasi masalah ini, buat saja struktur data linier baru di mana setiap indeks dalam struktur Anda cocok dengan kedalaman yang diberikan, perbarui setiap kali objek mengubah kedalaman.Kasus di mana suatu objek tidak cocok dengan satu ubin sedikit lebih sulit, jadi saya akan mempostingnya jika Anda membutuhkannya segera setelah Anda memperbarui pertanyaan Anda.
sumber
Saya tidak memiliki pengetahuan khusus tentang hal ini, tetapi inilah pemikiran.
Mulailah dengan menandai setiap sel sebagai "tidak ditarik". (Atau, ekuivalen, gunakan array untuk mewakili lokasi hal "yang ditarik" terdekat pada setiap "garis paling jauh" sel, atau set, dll. Kemudian, untuk setiap sel (saya mungkin akan menjelajahinya dalam urutan yang dijelaskan oleh kaoD): periksa apakah sel itu telah ditarik; jika belum ditarik dan berisi objek, periksa apakah setiap sel yang akan dikaburkan oleh objek itu telah ditarik, dan jika tidak gambar itu secara rekursif; gambar objek yang terkandung oleh sel itu jika perlu; dan tandai sel itu dan semua sel yang ditempati oleh objeknya sebagai "digambar".
Saya berasumsi bahwa Anda dapat dengan cepat memetakan sel ke objek di dalamnya, jika ada. Saya percaya ini adalah O (n) kali, meskipun itu bisa berakhir membangun tumpukan besar (yang Anda mungkin ingin berubah menjadi daftar tertaut jika Anda khawatir kehabisan ruang tumpukan).
Jika Anda benar-benar membutuhkan daftar, Anda dapat menambahkan daftar bukan menggambar. Saya menduga bahwa memulai dengan daftar yang sebagian besar disortir tidak membantu.
sumber
Saya akan menggunakan algoritma pelukis dengan jarak taksi dari sel terjauh dari kamera, menggambar yang terdekat dengan kamera terlebih dahulu dan kemudian bergerak ke luar.
Sunting: Ini tidak berfungsi kecuali Anda dapat menggambar konten masing-masing sel secara terpisah.
sumber
Apa yang membuat Anda percaya bahwa “dapat dibuktikan secara matematis bahwa setidaknya ada satu urutan undian untuk memenuhi kebutuhan masalah”? Ini adalah contoh tandingan sepele di mana Anda tidak bisa bergantung pada objek penyortiran z:
sumber