Bagaimana cara saya mengurutkan sprite isometrik ke dalam urutan yang benar?

Dalam permainan 2D top-down yang normal, orang dapat menggunakan sumbu layar y untuk mengurutkan gambar. Dalam contoh ini pohon-pohon diurutkan dengan benar tetapi dinding isometrik tidak:

Dinding 2 adalah satu piksel di bawah dinding 1 sehingga ditarik setelah dinding 1, dan berakhir di atas.

Jika saya mengurutkan berdasarkan sumbu y isometrik, dinding muncul dalam urutan yang benar tetapi pohon-pohon tidak:

Bagaimana saya melakukan ini dengan benar?

Game isometrik secara fungsional 3D, jadi secara internal, Anda harus menyimpan koordinat 3D untuk setiap entitas dalam game. Koordinat aktual yang Anda pilih adalah arbitrer, tetapi katakanlah X dan Y adalah dua sumbu di darat, dan Z berada di atas tanah ke udara.

Perender kemudian perlu memproyeksikannya ke 2D untuk menggambar hal-hal di layar. "Isometrik" adalah salah satu proyeksi tersebut. Memproyeksikan dari 3D ke 2D secara isometrik cukup sederhana. Katakanlah sumbu X bergerak dari kiri atas ke kanan bawah dan turun satu piksel untuk setiap dua piksel horizontal. Demikian juga, sumbu Y bergerak dari kanan atas ke kiri bawah. Sumbu Z lurus ke atas. Untuk mengkonversi dari 3D ke 2D maka cukup:

function projectIso(x, y, z) {
    return {
        x: x - y,
        y: (x / 2) + (y / 2) - z
    };
}

Sekarang untuk pertanyaan awal Anda, menyortir. Sekarang kami bekerja dengan objek kami secara langsung dalam 3D, menyortir menjadi lebih sederhana. Di ruang koordinat kami di sini, sprite terjauh memiliki koordinat x, y dan z terendah (yaitu ketiga sumbu menunjukkan dari layar). Jadi Anda cukup mengurutkannya berdasarkan jumlah tersebut:

function nearness(obj) {
    return obj.x + obj.y + obj.z;
}

function closer(a, b) {
    if (nearness(a) > nearness(b)) {
        return "a";
    } else {
        return "b";
    }
}

Untuk menghindari penyortiran ulang entitas Anda setiap frame, gunakan semacam pigeonhole, detail di sini .

Dengan asumsi bahwa sprite Anda menempati set ubin yang persegi panjang (jika mereka menempati set sewenang-wenang, maka Anda tidak dapat menggambar dengan benar sama sekali dalam kasus umum), masalahnya adalah bahwa tidak ada hubungan urutan total antara elemen, sehingga Anda tidak dapat mengurutkan mereka menggunakan semacam yang akan menghasilkan perbandingan O (nlogn).

Perhatikan bahwa untuk dua objek A dan B, baik A harus digambar sebelum B (A <- B), B harus digambar sebelum A (B <- A) atau mereka dapat digambar dalam urutan apa pun. Mereka membentuk urutan parsial. Jika Anda menggambar sendiri beberapa contoh dengan 3 objek yang tumpang tindih, Anda mungkin memperhatikan bahwa meskipun objek 1 dan 3 mungkin tidak tumpang tindih, sehingga tidak memiliki ketergantungan langsung, urutan gambar mereka tergantung pada objek ke-2 yang ada di antara mereka - tergantung bagaimana Anda menempatkannya, Anda akan mendapatkan pesanan menggambar yang berbeda. Intinya - jenis tradisional tidak berfungsi di sini.

Salah satu solusinya adalah dengan menggunakan perbandingan (disebutkan oleh Dani) dan membandingkan setiap objek dengan masing-masing objek lainnya untuk menentukan dependensi mereka dan membentuk grafik dependensi (yang akan menjadi DAG). Kemudian lakukan pengurutan topologi pada grafik untuk menentukan urutan gambar. Jika tidak ada terlalu banyak objek, ini mungkin cukup cepat O(n^2).

Solusi lain adalah dengan menggunakan pohon quad (untuk menyeimbangkan - semu ) dan menyimpan persegi panjang dari semua objek ke dalamnya.

Kemudian beralih ke semua objek X, dan gunakan pohon quad untuk memeriksa apakah ada objek Y di garis di atas objek X yang dimulai dengan paling kiri dan berakhir dengan sudut paling kanan dari objek X - untuk semua Y, Y < - X. Seperti ini, Anda masih harus membentuk grafik dan mengurutkannya secara topologis.

Tapi Anda bisa menghindarinya. Anda menggunakan daftar objek Q, dan tabel objek T. Anda mengulangi semua slot yang terlihat dari yang lebih kecil ke nilai yang lebih besar pada sumbu x (satu baris), berjalan baris demi baris pada sumbu y. Jika ada sudut bawah objek di slot itu, lakukan prosedur di atas untuk menentukan dependensi. Jika suatu objek X tergantung pada beberapa objek Y lainnya yang sebagian di atasnya (Y <- X), dan setiap Y tersebut sudah ada di Q, tambahkan X ke Q. Jika ada beberapa Y yang tidak ada di Q, tambahkan X ke T dan menyatakan bahwa Y <- X. Setiap kali Anda menambahkan objek ke Q, Anda menghapus dependensi objek yang tertunda di T. Jika semua dependensi dihapus, objek dari T dipindahkan ke Q.

Kami mengasumsikan bahwa sprite objek tidak mengintip dari slot mereka di bagian bawah, kiri atau kanan (hanya di atas, seperti pohon di gambar Anda). Ini harus meningkatkan kinerja untuk sejumlah besar objek. Pendekatan ini akan kembali O(n^2), tetapi hanya dalam kasus terburuk yang mencakup objek berukuran aneh dan / atau konfigurasi objek aneh. Dalam kebanyakan kasus, itu O(n * logn * sqrt(n)). Mengetahui ketinggian sprite Anda dapat menghilangkannya sqrt(n), karena Anda tidak perlu memeriksa seluruh strip di atas. Bergantung pada jumlah objek di layar, Anda dapat mencoba mengganti pohon quad dengan array yang menunjukkan slot mana yang diambil (masuk akal jika ada banyak objek).

Akhirnya, jangan ragu untuk memeriksa kode sumber ini untuk beberapa ide: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

Saya tidak berpikir ada solusi matematika. Anda mungkin tidak memiliki cukup data di dunia 2D tempat tinggal barang Anda. Jika dinding Anda dicerminkan pada X, mereka akan berada dalam urutan "benar". Kemudian lagi Anda mungkin bisa melakukan pengujian tumpang tindih dengan kotak pembatas gambar, tapi ini adalah area yang saya tidak kenal.

Anda mungkin harus mengurutkan berdasarkan layar Y per-ubin dan mengatakan bahwa hal yang lebih rumit adalah "masalah desain". Misalnya, jika Anda membuat konten, cukup beri tahu perancang algoritme pengurutan dan sorong wall2 2 piksel ke atas untuk memperbaiki masalahnya. Itulah bagaimana kami harus memperbaikinya dalam permainan isometrik yang saya kerjakan. Ini mungkin termasuk mengambil item "panjang" dan memecahnya menjadi potongan berukuran ubin.

Jika Anda mengizinkan pengguna untuk mengedit konten, hal yang benar-benar aman untuk dilakukan adalah membuat semua ubin berdasarkan dan paling banyak satu ubin besar. Dengan begitu Anda terhindar dari masalah. Anda mungkin bisa bertahan dengan membuat segalanya lebih besar dari ubin, tetapi mungkin hanya jika itu persegi. Saya belum bermain-main dengan itu.

Penyortiran isometrik yang sempurna itu sulit. Tetapi untuk pendekatan pertama, untuk mengurutkan item Anda dengan benar, Anda harus menggunakan fungsi perbandingan yang lebih kompleks dengan setiap objek yang tumpang tindih. Fungsi ini harus memeriksa kondisi ini: Objek tumpang tindih "a" berada di belakang "b" jika:

(a.posX + a.sizeX <= b.posX) atau (a.posY + a.sizeY <= b.posY) atau (a.posZ + a.sizeZ <= b.posZ)

Tentu saja, ini adalah ide pertama untuk implementasi isometrik naif. Untuk skenario yang lebih kompleks (jika Anda ingin melihat rotasi, posisi per-pixel pada sumbu z, dll.) Anda perlu memeriksa lebih banyak kondisi.

Saya menggunakan formula yang sangat sederhana yang bekerja dengan baik dengan mesin isometrik kecil saya di OpenGL:

Anda masing-masing objek (pohon, ubin lantai, karakter, ...) memiliki posisi X dan Y di layar. Anda harus mengaktifkan PENGUJIAN KEDALAMAN dan menemukan nilai Z yang baik untuk setiap nilai. Anda bisa langsung ke yang berikut ini:

z = x + y + objectIndex

Saya menggunakan dan indeks yang berbeda untuk lantai dan objek yang akan berada di atas lantai (0 untuk lantai dan 1 untuk semua objek yang memiliki ketinggian). Ini seharusnya bekerja dengan baik.

Jawaban luas dengan berbagai solusi, gambar, dan semua matematika di sini:

/programming/892811/drawing-isometric-game-worlds

Jika Anda membandingkan nilai y pada posisi x yang sama, itu akan berfungsi setiap saat. Jadi, jangan bandingkan pusat ke pusat. Alih-alih membandingkan pusat satu sprite dengan posisi x yang sama pada sprite lainnya.

Tetapi, ini membutuhkan beberapa data geometri untuk setiap sprite. Bisa semudah dua poin dari kiri ke kanan yang menggambarkan batas bawah untuk sprite. Atau, Anda bisa menganalisis data gambar sprite dan menemukan piksel pertama yang tidak transparan.

Pendekatan yang lebih mudah adalah dengan membagi semua sprite menjadi tiga kelompok: diagonal sepanjang sumbu x, diagonal sepanjang sumbu y dan datar. Jika dua objek sama-sama diagonal di sepanjang sumbu yang sama, urutkan berdasarkan sumbu lainnya.

Anda harus menetapkan id unik untuk semua objek dengan tipe yang sama. Kemudian Anda mengurutkan semua objek berdasarkan posisi mereka dan menggambar kelompok objek sesuai id mereka. Sehingga objek 1 di grup A tidak akan pernah overdraw objek 2 di grup A dll.

Ini bukan jawaban, tetapi hanya komentar dan suara yang ingin saya berikan untuk jawaban axel22 ini di sini /gamedev//a/8181/112940

Saya tidak memiliki reputasi yang cukup untuk memilih atau berkomentar atas jawaban lain, tetapi paragraf kedua dari jawabannya mungkin adalah hal yang paling penting yang harus diperhatikan ketika mencoba menyortir entitas dalam permainan isometrik tanpa mengandalkan 3D "modern". teknik seperti Z-buffer.

Di mesin saya, saya ingin melakukan hal-hal "old-school", 2D murni. Dan saya menghabiskan banyak waktu menghancurkan otak saya mencoba mencari tahu mengapa panggilan saya untuk "mengurutkan" (dalam kasus saya itu adalah c ++ std :: sort) tidak berfungsi dengan benar pada konfigurasi peta tertentu.

Hanya ketika saya menyadari bahwa ini adalah situasi "parsial-urutan" adalah saya bisa menyelesaikannya.

Sejauh ini semua solusi yang saya temukan di web menggunakan semacam penyortiran topologi untuk menangani masalah dengan benar. Pemilahan topologis tampaknya menjadi cara untuk maju.