Struktur data di game yang lebih lama

10

Saya ingin tahu tentang struktur data yang digunakan saat memprogram game yang lebih lama seperti Super Mario Brothers untuk NES dan Super Mario World untuk SNES. Pemahaman saya adalah bahwa game periode ini ditulis dalam pertemuan. Apakah programmer mendefinisikan / menggunakan struktur data?

Sebagai contoh: ketika sekelompok koin muncul di layar bagaimana mereka disimpan? Apakah programmer hanya menggunakan array? Atau mungkin mereka memiliki daftar tautan?

Bersulang!

Sunting : Saya tertarik dengan berbagai pendekatan ... belum tentu pendekatan universal.

Sunting 2 : Dalam beberapa permainan saya, saya menggunakan pendekatan (berpotensi buruk) terhadap koleksi dan saya ingin tahu apakah ada game yang lebih tua menggunakan pendekatan yang sama. Saya suka melakukan hal berikut:

// statically allocated arrays (max number of coins is 4)
int coinsXs[4] = {0, 0, 0, 0};
int coinsYs[4] = {0, 0, 0, 0};

// bitset that keeps track of which coins are active
int coinsActive = 0;

// ...

// update the active coins in an update function
for(int i = 0; i < 4; i++){
    if(coinsActive & (1 << i)){
        // update ith coin
    }
 }
data-structure MrDatabase
sumber
2
Tidak ada jawaban universal; turun ke bagaimana programmer yang diberikan mengimplementasikan solusi untuk masalah yang diberikan.
Ed S.
1
Meskipun saya tidak berpikir semua game itu ditulis dalam assembly, saya akan mengatakan itu cukup umum bagi programmer assembly untuk mengumpulkan komponen kecil mereka untuk copy / paste reuse dari program ke program. Berapa kali Anda ingin menulis fungsi printf () setelahnya? :)
James
Poin bagus. Saya benar-benar ingin tahu tentang koleksi yang dialokasikan secara dinamis vs koleksi yang dialokasikan secara statis
MrDatabase
1
Apa masalah spesifik yang Anda miliki? Mengapa Anda peduli apa permainan lama lakukan?
Tetrad
2
Apa yang Anda dapatkan dalam suntingan kedua adalah contoh tata letak "susunan susunan", yang tetap umum bahkan dalam permainan modern karena memiliki manfaat untuk paralelisme dan operasi SIMD. Sony melakukan presentasi beberapa tahun yang lalu tentang bagaimana cara tradisional C ++ menyusun data dapat memiliki biaya perf tersembunyi yang serius: research.scee.net/files/presentations/gcapaustralia09/…
Crashworks

Jawaban:

13

Bahkan dalam 16-bit hari, konsol game pada dasarnya hanya kecil, komputer tertanam yang menjalankan perangkat lunak realtime, dan struktur data yang kami gunakan adalah yang sama dengan yang Anda temukan di mana pun dalam ilmu komputer: array, matriks, tumpukan, tumpukan. Tidak banyak daftar yang tertaut karena mereka sangat lambat (pencarian tidak langsung memiliki latensi yang panjang).

Perbedaannya adalah bahwa sebelum STL, dan dengan kinerja yang sangat kritis, kami biasanya harus menulis sendiri struktur dan algoritmanya!

David Braben melakukan ceramah yang menyenangkan di GDC 2011 di mana ia berbicara tentang semua trik gila yang digunakannya untuk mencocokkan Elite ke BBC Micro pada tahun 1984. Anda dapat menontonnya secara gratis di GDC Vault .

Crashworks
sumber
Keren. Apakah Anda menggunakan array yang dialokasikan secara dinamis? Atau apakah sebagian besar memiliki ukuran statis? Saya ingin tahu tentang situasi di mana, katakanlah, lima koin akan muncul di layar dan tetap di layar sampai pemain mengumpulkannya (atau mereka menggulir layar ke luar).
MrDatabase
2
@MrDatabase - Alokasi statis sedapat mungkin. Untuk kasus-kasus seperti yang Anda gambarkan, kami sering hanya memiliki array yang dialokasikan secara statis, misalnya, 32 koin yang mungkin ada. Ketika koin datang ke dunia, kami akan mengisi tempat di array. Ketika mereka pergi, kami akan mengosongkannya. Alokasi dinamis tidak tersedia, kami hanya menghindari menggunakannya karena ketika Anda hanya memiliki 2MB RAM, Anda benar-benar harus menjamin program Anda berjalan dalam memori konstan!
Crashworks
Keren. Saya melakukan sesuatu yang mirip (lihat edit # 2 untuk pertanyaan). Dalam fungsi pembaruan saya, saya memeriksa bitet "coinActive" if(coinsActive)sebelum saya mengulang maxNumCoins dan memperbarui. Dengan cara ini saya benar-benar menghindari loop jika nol koin aktif.
MrDatabase
+1 karena tautan GDC Vault. Pembicaraan postmortem Popolous oleh Peter Molyneux harus menjadi pembicaraan paling lucu yang pernah saya lihat.
TravisG
MeDataBase - Anda menyalin objek aktif terakhir ke slot yang ditempati oleh koin yang menjadi tidak aktif (yaitu, jika Anda memiliki 10 koin, koin 5 menjadi tidak aktif, salin koin 10 ke slot 5 dan kurangi koin numaktif) Anda dapat langsung beralih untuk numCoins dan memperbarui semua elemen tersebut. Anda tidak akan membutuhkan 'jika'. Tentu saja ini hanya berfungsi jika koin yang tidak aktif tidak perlu mempertahankan status dan jika urutan pembaruan tidak penting (keadaan dapat dipertahankan jika array menyimpan pointer ke koin dan bukan koin yang sebenarnya, tetapi kemudian Anda mendapatkan perilaku cache yang tersebar yang kemungkinan lebih buruk daripada 'jika')
Kaj
5

Berikut ini adalah diskusi menarik tentang GameDev.net untuk kode sumber Super Mario Bros: Kode sumber Super Mario

pek
sumber