Bagaimana mereka melakukannya: Jutaan ubin di Terraria

Saya telah mengerjakan sebuah mesin permainan yang mirip dengan Terraria , sebagian besar sebagai tantangan, dan sementara saya sudah menemukan sebagian besar dari itu, saya tidak bisa benar-benar membungkus kepala saya bagaimana mereka menangani jutaan ubin yang dapat berinteraksi / dapat dipanen permainan memiliki satu waktu. Membuat sekitar 500.000 ubin, yaitu 1/20 dari apa yang mungkin di Terraria , di mesin saya menyebabkan frame-rate turun dari 60 menjadi sekitar 20, bahkan saya masih hanya menampilkan ubin dalam tampilan. Pikiran Anda, saya tidak melakukan apa pun dengan ubin, hanya menyimpannya dalam ingatan.

Pembaruan : Kode ditambahkan untuk menunjukkan bagaimana saya melakukan sesuatu.

Ini adalah bagian dari kelas, yang menangani ubin dan menggambarnya. Saya menduga pelakunya adalah bagian "foreach", yang mengulangi semuanya, bahkan indeks kosong.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

Juga di sini adalah metode Tile.Draw, yang juga bisa dilakukan dengan pembaruan, karena setiap Tile menggunakan empat panggilan ke metode SpriteBatch.Draw. Ini adalah bagian dari sistem autotiling saya, yang berarti menggambar setiap sudut tergantung pada ubin tetangga. tekstur_ * adalah Persegi Panjang, ditetapkan sekali pada level penciptaan, tidak setiap pembaruan.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Setiap kritik atau saran untuk kode saya diterima.

Pembaruan : Solusi ditambahkan.

Inilah metode Level.Draw terakhir. Metode Level.TileAt cukup memeriksa nilai yang dimasukkan, untuk menghindari pengecualian OutOfRange.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...

Apakah Anda mengulang-ulang seluruh 500.000 ubin saat Anda merender? Jika demikian, itu kemungkinan akan menyebabkan sebagian dari masalah Anda. Jika Anda mengulang setengah juta ubin saat melakukan render, dan setengah juta ubin saat melakukan 'pembaruan', maka Anda mengulangi satu juta ubin setiap frame.

Jelas, ada cara untuk mengatasi ini. Anda dapat melakukan kutu pembaruan saat melakukan rendering, sehingga menghemat separuh waktu yang dihabiskan untuk mengulang semua ubin. Tapi itu mengikat kode rendering Anda dan kode pembaruan Anda bersama menjadi satu fungsi, dan umumnya BAD IDEA .

Anda bisa melacak ubin yang ada di layar, dan hanya mengulanginya (dan membuat) itu. Bergantung pada hal-hal seperti ukuran ubin Anda, dan ukuran layar, ini bisa dengan mudah mengurangi jumlah ubin yang perlu Anda lewati, dan itu akan menghemat sedikit waktu pemrosesan.

Akhirnya, dan mungkin opsi terbaik (sebagian besar game dunia melakukan ini), adalah untuk membagi medan Anda menjadi wilayah. Bagi dunia menjadi potongan-potongan, katakanlah, 512x512 ubin, dan muat / bongkar wilayah saat pemain semakin dekat, atau lebih jauh dari, suatu wilayah. Ini juga menyelamatkan Anda dari keharusan untuk mengulang melalui ubin jauh untuk melakukan segala jenis centang 'pembaruan'.

(Jelas, jika mesin Anda tidak melakukan semacam pembaruan pada ubin, Anda dapat mengabaikan bagian dari jawaban ini yang menyebutkannya.)

Saya melihat satu kesalahan besar di sini tidak ditangani oleh salah satu jawaban. Tentu saja Anda tidak boleh menggambar dan beralih di atas ubin lebih dari yang Anda butuhkan juga. Yang kurang jelas adalah bagaimana Anda benar-benar mendefinisikan ubin. Seperti yang saya lihat Anda membuat kelas ubin, saya selalu terbiasa melakukannya juga, tetapi itu adalah kesalahan besar. Anda mungkin memiliki semua jenis fungsi di kelas itu dan itu menciptakan banyak pemrosesan yang tidak perlu.

Anda hanya harus mengulangi apa yang benar-benar diperlukan untuk diproses. Jadi pikirkan apa yang sebenarnya Anda butuhkan untuk ubin. Untuk menggambar, Anda hanya perlu tekstur, tetapi Anda tidak ingin mengulangi gambar yang sebenarnya karena gambar itu besar untuk diproses. Anda dapat membuat int [,] atau bahkan byte [,] yang tidak ditandatangani (jika Anda tidak mengharapkan lebih dari 255 tekstur ubin). Yang perlu Anda lakukan adalah beralih ke array kecil ini dan gunakan switch atau jika pernyataan untuk menggambar tekstur.

Jadi, apa yang perlu Anda perbarui? Jenis, kesehatan, dan kerusakannya tampaknya cukup. Semua ini dapat disimpan dalam byte. Jadi mengapa tidak membuat struct seperti ini untuk loop pembaruan:

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

Anda benar-benar bisa menggunakan tipe untuk menggambar ubin. Jadi Anda bisa melepaskan yang itu (membuat array miliknya sendiri) dari struct sehingga Anda tidak beralih pada bidang kesehatan dan kerusakan yang tidak perlu dalam loop undian. Untuk tujuan memperbarui, Anda harus mempertimbangkan area yang lebih luas daripada hanya layar Anda sehingga dunia game terasa lebih hidup (entitas mengubah posisi dari layar) tetapi untuk menggambar hal-hal Anda hanya perlu ubin yang terlihat.

Jika Anda menyimpan struct di atas hanya membutuhkan 3 byte per ubin. Jadi untuk tujuan penyimpanan dan memori ini sangat ideal. Untuk kecepatan pemrosesan, tidak masalah jika Anda menggunakan int atau byte, atau bahkan int panjang jika Anda memiliki sistem 64 bit.

Ada berbagai teknik penyandian yang bisa Anda gunakan.

RLE: Jadi Anda mulai dengan koordinat (x, y) dan kemudian menghitung berapa banyak ubin yang sama ada berdampingan (panjang) di sepanjang salah satu sumbu. Contoh: (1,1,10,5) berarti mulai dari koordinat 1,1 ada 10 ubin berdampingan dengan jenis ubin 5.

Array besar (bitmap): setiap elemen dari array memegang tipe ubin yang berada di area itu.

EDIT: Saya baru saja menemukan pertanyaan yang bagus di sini: Fungsi seed random untuk pembuatan peta?

Generator kebisingan Perlin terlihat seperti jawaban yang bagus.

Anda mungkin harus mempartisi tilemap seperti yang disarankan. Misalnya dengan struktur Quadtree untuk menghilangkan setiap pemrosesan potensial (misalnya, bahkan hanya melalui perulangan) dari ubin yang tidak perlu (tidak terlihat). Dengan cara ini Anda hanya memproses apa yang mungkin perlu diproses dan meningkatkan ukuran dataset (peta ubin) tidak menyebabkan penalti kinerja praktis. Tentu saja, dengan anggapan bahwa pohon itu seimbang.

Saya tidak ingin terdengar membosankan atau apa pun dengan mengulangi "lama", tetapi ketika mengoptimalkan, selalu ingat untuk menggunakan optimasi yang didukung oleh toolchain / kompiler Anda, Anda harus sedikit bereksperimen dengan mereka. Dan ya, optimasi prematur adalah akar dari semua kejahatan. Percayalah pada kompiler Anda, ia lebih tahu daripada Anda dalam kebanyakan kasus, tetapi selalu, selalumengukur dua kali dan tidak pernah bergantung pada perkiraan waktu. Ini bukan tentang memiliki implementasi cepat dari algoritma tercepat selama Anda tidak tahu di mana hambatan sebenarnya. Itu sebabnya Anda harus menggunakan profiler untuk menemukan jalur paling lambat (panas) dari kode dan fokus pada menghilangkan (atau mengoptimalkan) mereka. Pengetahuan tingkat rendah dari arsitektur target sering kali penting untuk memeras segala perangkat keras yang ditawarkan, jadi pelajari cache CPU tersebut dan pelajari apa itu prediktor cabang. Lihat apa yang profiler Anda memberi tahu Anda tentang cache / hit cabang / kehilangan. Dan seperti yang ditunjukkan beberapa bentuk struktur data pohon, lebih baik memiliki struktur data cerdas dan algoritme bodoh, daripada sebaliknya. Data lebih dulu, ketika menyangkut kinerja. :)

Bukankah ini semua tentang terlalu banyak panggilan? Jika Anda meletakkan semua tekstur ubin peta Anda ke dalam satu atlas gambar ubin, tidak akan ada perpindahan tekstur saat rendering. Dan jika Anda menumpuk semua ubin Anda menjadi satu Mesh, itu harus ditarik dalam satu panggilan undian.

Tentang iklan dinamis ... Mungkin quad tree bukan ide yang buruk. Dengan anggapan bahwa ubin dimasukkan ke dalam daun dan simpul non-daun hanyalah jerat batch dari anak-anaknya, root harus berisi semua ubin yang dikumpulkan dalam satu mesh. Menghapus satu ubin memerlukan pembaruan node (rebatching mesh) hingga ke root. Tetapi pada setiap level pohon hanya ada 1/4 dari mesh yang direcatch yang seharusnya tidak sebanyak itu, 4 * tree_height mesh bergabung?

Oh dan jika Anda menggunakan pohon ini dalam algoritma kliping Anda akan membuat tidak selalu root simpul tetapi beberapa anak-anaknya, sehingga Anda bahkan tidak perlu memperbarui / rebatch semua node hingga root, tetapi hingga node (non-daun) Anda render saat ini.

Hanya pikiran saya, tidak ada kode, mungkin itu omong kosong.

@arrival benar. Masalahnya adalah kode undian. Anda sedang membangun array 4 * 3000 + perintah draw quad (24000+ perintah draw polygon ) per frame. Kemudian perintah ini diproses dan disalurkan ke GPU. Ini agak buruk.

Ada beberapa solusi.

• Jadikan balok besar (misalnya, ukuran layar) ubin menjadi tekstur statis dan tarik dalam satu panggilan.
• Gunakan shader untuk menggambar ubin tanpa mengirim geometri ke setiap frame GPU (yaitu menyimpan peta ubin pada GPU).

Yang perlu Anda lakukan, adalah membagi dunia menjadi beberapa wilayah. Generasi medan kebisingan Perlin dapat menggunakan benih umum, sehingga bahkan jika dunia tidak dibiakkan sebelumnya, benih akan membentuk bagian dari kebisingan, yang dengan baik menyelipkan medan baru ke bagian-bagian yang ada. Dengan cara ini, Anda tidak perlu menghitung lebih dari satu buffer kecil di depan tampilan pemain secara bersamaan (beberapa layar di sekitar yang sekarang).

Dalam hal menangani hal-hal seperti tanaman yang tumbuh di daerah yang jauh dari layar pemain saat ini, Anda dapat memiliki timer misalnya. Penghitung waktu ini akan diulang melalui file katakanlah menyimpan informasi tentang tanaman, posisi mereka dll. Anda hanya perlu membaca / memperbarui / menyimpan file dalam penghitung waktu. Ketika pemain mencapai bagian-bagian dunia lagi, mesin akan membaca dalam file seperti biasa, dan menyajikan data tanaman yang lebih baru di layar.

Saya menggunakan teknik ini dalam permainan serupa yang saya buat tahun lalu, untuk panen dan bertani. Pemain bisa berjalan jauh dari ladang, dan saat kembali, barang telah diperbarui.

Saya telah berpikir tentang bagaimana menangani blok sebanyak itu, dan satu-satunya hal yang muncul di kepala saya adalah Pola Desain Flyweight. Jika Anda tidak tahu, saya sangat menyarankan untuk membacanya: mungkin banyak membantu dalam hal menghemat memori dan pemrosesan: http://en.wikipedia.org/wiki/Flyweight_pattern