Bagaimana mereka melakukannya: Jutaan ubin di Terraria

45

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);

            }
        }
    }
...
William Mariager
sumber
2
Apakah Anda benar-benar yakin hanya memberikan apa yang ada dalam tampilan kamera, artinya kode untuk menentukan apa yang harus dirender dengan benar?
Cooper
5
Framerrate turun dari 60 hingga 20 fps, hanya karena memori yang dialokasikan? Itu sangat tidak mungkin, pasti ada sesuatu yang salah. Platform apa itu? Apakah sistem menukar memori virtual ke disk?
Maik Semder
6
@Rackir Dalam hal ini saya akan mengatakan itu salah jika bahkan ada kelas ubin, array bilangan bulat panjang yang sesuai harus dilakukan, dan ketika ada setengah juta objek, overhead OO bukan lelucon. Saya kira itu mungkin dilakukan dengan objek, tetapi apa gunanya? Array integer sudah mati mudah untuk ditangani.
aaaaaaaaaaaa
3
Aduh! Iterasi semua ubin dan panggil Draw empat kali pada masing-masing yang ada dalam tampilan. Pasti ada beberapa perbaikan yang mungkin terjadi di sini ....
thedaian
11
Anda tidak perlu semua partisi mewah yang dibicarakan di bawah ini untuk membuat hanya apa yang terlihat. Ini tilemap. Ini sudah dipartisi menjadi grid biasa. Hitung saja ubin di kiri atas layar dan kanan bawah, dan gambar semuanya dalam persegi panjang itu.
Blecki

Jawaban:

56

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.)

thedaian
sumber
5
Bagian wilayah tampaknya menarik, jika saya ingat betul, itulah cara minecraft melakukannya, namun, itu tidak berfungsi dengan bagaimana medan di Terraria berevolusi bahkan jika Anda tidak berada di dekatnya, seperti penyebaran rumput, pertumbuhan kaktus, dan sejenisnya. Sunting : Kecuali tentu saja, mereka menerapkan waktu yang berlalu sejak terakhir kali kawasan ini aktif, dan kemudian melakukan semua perubahan yang akan terjadi pada periode itu. Itu mungkin benar-benar bekerja.
William Mariager
2
Minecraft pasti menggunakan wilayah (dan game Ultima kemudian melakukannya, dan saya cukup yakin banyak game Bethesda melakukannya). Saya kurang yakin tentang bagaimana Terraria menangani medan, tetapi mereka mungkin menerapkan waktu yang telah berlalu ke wilayah "baru", atau mereka menyimpan seluruh peta dalam memori. Yang terakhir akan menuntut penggunaan RAM yang tinggi, tetapi kebanyakan komputer modern bisa mengatasinya. Mungkin ada opsi lain yang belum disebutkan.
thedaian
2
@MindWorX: Melakukan semua pembaruan saat memuat ulang tidak selalu berhasil - misalkan Anda memiliki banyak area tandus dan kemudian memotong rumput. Anda pergi selama berabad-abad dan kemudian berjalan menuju rumput. Ketika blok dengan beban rumput itu menangkap dan menyebar di blok itu tetapi tidak akan menyebar ke blok yang lebih dekat yang sudah dimuat. Namun, hal-hal seperti ini jauh lebih lambat daripada permainan - periksa hanya sebagian kecil ubin dalam satu siklus pembaruan apa pun dan Anda dapat membuat medan yang jauh tetap hidup tanpa memuat sistem.
Loren Pechtel
1
Sebagai alternatif (atau pelengkap) untuk "mengejar ketinggalan" ketika suatu wilayah mendekati pemain, Anda dapat melakukan simulasi terpisah dengan mengulangi setiap wilayah yang jauh dan memperbaruinya dengan laju yang lebih lambat. Anda bisa memesan waktu untuk ini setiap frame atau menjalankannya di utas terpisah. Jadi misalnya Anda dapat memperbarui wilayah pemain ditambah 6 wilayah yang berdekatan setiap frame, tetapi juga memperbarui 1 atau 2 wilayah tambahan juga.
Lewis Wakeford
1
Bagi siapa pun yang bertanya-tanya, Terraria menyimpan seluruh data ubinnya dalam array 2d (ukuran maksimum adalah 8400x2400). Dan kemudian menggunakan beberapa matematika sederhana untuk memutuskan bagian ubin mana yang akan ditampilkan.
FrenchyNZ
4

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.

Madmenyo
sumber
1
Ya, iterasi mesin saya kemudian berevolusi untuk menggunakannya. Sebagian besar untuk mengurangi konsumsi memori dan meningkatkan kecepatan. Tipe ByRef lambat dibandingkan dengan array yang diisi dengan struct ByVal. Meskipun demikian, ada baiknya Anda menambahkan ini ke jawabannya.
William Mariager
1
Ya tersandung padanya sambil mencari beberapa algoritma acak. Segera memperhatikan Anda di mana menggunakan kelas ubin Anda sendiri dalam kode Anda. Itu kesalahan yang sangat umum saat Anda baru. Senang melihat Anda masih aktif sejak Anda memposting ini 2 tahun yang lalu.
Madmenyo
3
Anda tidak perlu healthatau damage. Anda dapat menyimpan buffer kecil dari lokasi ubin yang baru saja diambil dan kerusakan pada masing-masingnya. Jika ubin baru diambil pada dan buffer penuh maka roll off lokasi terlama darinya sebelum menambahkan yang baru. Ini membatasi berapa banyak ubin yang bisa Anda gali sekaligus tetapi ada batas intrinsiknya (kira-kira #players * pick_tile_size). Anda dapat menyimpan daftar ini per-pemain jika itu membuatnya lebih mudah. Ukuran memang penting untuk kecepatan; ukuran yang lebih kecil berarti lebih banyak ubin di setiap cacheline CPU.
Sean Middleditch
@SeanMiddleditch Anda benar tetapi bukan itu intinya. Intinya adalah berhenti dan pikirkan apa yang sebenarnya Anda butuhkan untuk menggambar ubin di layar dan lakukan perhitungan Anda. Karena OP menggunakan seluruh kelas saya membuat contoh sederhana, sederhana berjalan jauh dalam kemajuan belajar. Sekarang buka kunci topik saya untuk kerapatan piksel, Anda jelas-jelas seorang programmer mencoba melihat pertanyaan itu dengan mata seorang artis CG. Karena situs ini juga untuk CG untuk game afaik.
Madmenyo
2

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.

Sam Axe
sumber
Saya tidak benar-benar yakin Anda menjawab pertanyaan yang diajukan, karena Anda berbicara tentang penyandian (dan perlin noise), dan pertanyaan itu tampaknya berhubungan dengan masalah kinerja.
thedaian
1
Dengan menggunakan pengkodean yang tepat (seperti perlin noise), Anda tidak dapat khawatir tentang menahan semua ubin dalam memori sekaligus .. alih-alih Anda cukup meminta encoder (generator suara) untuk memberi tahu Anda apa yang seharusnya muncul pada koordinat yang diberikan. Ada keseimbangan di sini antara siklus CPU dan penggunaan memori, dan generator derau dapat membantu dengan tindakan keseimbangan tersebut.
Sam Axe
2
Masalahnya di sini adalah bahwa jika Anda membuat game yang memungkinkan pengguna untuk memodifikasi medan entah bagaimana, cukup menggunakan generator derau untuk "menyimpan" bahwa informasi tidak akan berfungsi. Plus, pembuatan noise cukup mahal, seperti juga kebanyakan teknik pengkodean. Anda lebih baik menyimpan siklus CPU untuk hal-hal gameplay aktual (fisika, tabrakan, pencahayaan, dll.) Perlin noise sangat bagus untuk pembuatan medan, dan penyandian baik untuk menyimpan ke disk, tetapi ada cara yang lebih baik untuk menangani memori dalam kasus ini.
thedaian
Ide yang sangat bagus, seperti halnya thedaian, medannya berinteraksi dengan pengguna, yang berarti saya tidak dapat mengambil informasi secara matematis. Saya akan melihat kebisingan perlin, untuk menghasilkan medan dasar.
William Mariager
1

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. :)

zxcdw
sumber
+1 untuk "optimisasi prematur adalah akar dari semua kejahatan" Saya bersalah atas ini :(
thedaian
16
-1 quadtree? Berlebihan sedikit? Ketika semua ubin memiliki ukuran yang sama dalam game 2D seperti ini (untuk terraria), sangat mudah untuk mengetahui kisaran ubin yang ada di layar - itu hanya bagian paling kiri (di layar) ke ubin paling kanan bawah.
BlueRaja - Danny Pflughoeft
1

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.

kedatangan
sumber
0

@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).
Ark-kun
sumber
0

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.

Jason Coombes
sumber
-2

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

Tiago Frossard
sumber
3
-1 Jawaban ini terlalu umum untuk berguna, dan tautan yang Anda berikan tidak secara langsung mengatasi masalah khusus ini. Pola Flyweight adalah salah satu dari banyak cara mengelola set data besar secara efisien; Bisakah Anda menguraikan bagaimana Anda akan menerapkan pola ini dalam konteks spesifik menyimpan ubin dalam permainan seperti Terraria?
postgoodism