Di mana wadah paling efisien untuk menyimpan objek permainan dinamis? [Tutup]

20

Saya membuat penembak orang pertama dan saya tahu tentang banyak jenis wadah yang berbeda tetapi saya ingin menemukan wadah yang paling efisien untuk menyimpan objek dinamis yang akan ditambahkan dan dihapus dari permainan cukup sering. EX-Peluru.

Saya pikir dalam hal ini akan menjadi daftar sehingga memori tidak berdekatan dan tidak pernah ada ukuran yang terjadi. Tapi kemudian saya juga berpikir untuk menggunakan peta atau set. Jika ada yang punya informasi bermanfaat, saya akan sangat menghargainya.

Saya menulis ini di c ++.

Juga saya datang dengan solusi yang saya pikir akan berhasil.

Untuk memulai saya akan mengalokasikan vektor ukuran besar .. katakanlah 1000 objek. Saya akan melacak indeks terakhir yang ditambahkan dalam vektor ini sehingga saya tahu di mana ujung objek berada. Kemudian saya juga akan membuat antrian yang akan menampung indeks semua objek yang "dihapus" dari vektor. (Tidak ada penghapusan yang sebenarnya akan dilakukan, saya hanya akan tahu bahwa slot itu gratis). Jadi jika antrian kosong saya akan menambah indeks ditambahkan terakhir di vektor + 1, kalau tidak saya tambahkan ke indeks vektor yang ada di depan antrian.

msawayda
sumber
Adakah bahasa tertentu yang Anda targetkan?
Phill.Zitt
Pertanyaan ini terlalu sulit untuk dijawab tanpa banyak spesifikasi yang lebih baik, termasuk platform perangkat keras, bahasa / kerangka kerja, dll.
PlayDeezGames
1
Pro tip, Anda dapat menyimpan daftar gratis di memori elemen yang dihapus (sehingga Anda tidak perlu antrian tambahan).
Jeff Gates
2
Apakah ada pertanyaan dalam pertanyaan ini?
Trevor Powell
Perhatikan bahwa Anda tidak harus melacak indeks terbesar juga tidak harus melakukan pra-alokasi sejumlah elemen. std :: vector mengurus semuanya untuk Anda.
API-Beast

Jawaban:

33

Jawabannya selalu menggunakan array atau std :: vector. Jenis seperti daftar yang ditautkan atau std :: map biasanya benar-benar menghebohkan dalam gim, dan itu pasti termasuk case seperti koleksi objek gim.

Anda harus menyimpan objek itu sendiri (bukan pointer ke mereka) dalam array / vektor.

Anda ingin memori yang berdekatan. Anda benar-benar menginginkannya. Iterasi atas data apa pun dalam memori yang tidak bersebelahan memaksakan banyak kesalahan cache secara umum dan menghilangkan kemampuan kompiler dan CPU untuk melakukan prefetching cache yang efektif. Ini saja dapat mematikan kinerja.

Anda juga ingin menghindari alokasi dan deallokasi memori. Mereka sangat lambat, bahkan dengan pengalokasi memori cepat. Saya telah melihat game mendapatkan 10x FPS bump dengan hanya menghapus alokasi memori beberapa ratus setiap frame. Kelihatannya tidak seburuk itu, tapi bisa juga.

Terakhir, sebagian besar struktur data yang Anda pedulikan untuk mengelola objek game bisa jauh lebih efisien diimplemetasikan pada array atau vektor dari pada dengan pohon atau daftar.

Misalnya, untuk menghapus objek game, Anda dapat menggunakan swap-and-pop. Mudah diimplementasikan dengan sesuatu seperti:

std::swap(objects[index], objects.back());
objects.pop_back();

Anda juga bisa menandai objek sebagai dihapus dan meletakkan indeks mereka pada daftar gratis untuk waktu berikutnya Anda perlu membuat objek baru, tetapi melakukan swap-and-pop lebih baik. Ini memungkinkan Anda melakukan loop sederhana untuk semua objek hidup tanpa bercabang selain dari loop itu sendiri. Untuk integrasi fisika peluru dan sejenisnya, ini bisa menjadi dorongan kinerja yang signifikan.

Lebih penting lagi, Anda dapat menemukan objek dengan sepasang tabel lookup sederhana dari stabil unik menggunakan struktur peta slot.

Objek gim Anda memiliki indeks di larik utamanya. Mereka bisa sangat efisien mencari hanya dengan indeks ini (jauh lebih cepat daripada peta atau bahkan tabel hash). Namun, indeksnya tidak stabil karena swap dan pop ketika menghapus objek.

Peta slot membutuhkan dua lapisan tipuan, tetapi keduanya adalah pencarian array sederhana dengan indeks konstan. Mereka cepat . Sangat cepat.

Ide dasarnya adalah bahwa Anda memiliki tiga array: daftar objek utama Anda, daftar tipuan Anda, dan daftar gratis untuk daftar tipuan. Daftar objek utama Anda berisi objek aktual Anda, di mana setiap objek tahu ID uniknya sendiri. ID unik terdiri dari indeks dan tag versi. Daftar tipuan hanyalah array indeks ke daftar objek utama. Daftar gratis adalah setumpuk indeks ke dalam daftar tipuan.

Ketika Anda membuat objek di daftar utama, Anda menemukan entri yang tidak digunakan dalam daftar tipuan (menggunakan daftar gratis). Entri dalam daftar tipuan menunjuk ke entri yang tidak digunakan dalam daftar utama. Anda menginisialisasi objek Anda di lokasi itu, dan menetapkan ID uniknya ke indeks entri daftar tipuan yang Anda pilih dan tag versi yang ada di elemen daftar utama, ditambah satu.

Saat Anda menghancurkan objek, Anda melakukan swap-and-pop seperti biasa, tetapi Anda juga menambah nomor versi. Anda kemudian juga menambahkan indeks daftar tipuan (bagian dari ID unik objek) ke daftar gratis. Saat memindahkan objek sebagai bagian dari swap-and-pop, Anda juga memperbarui entri dalam daftar tipuan ke lokasi baru.

Contoh pseudo-code:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

Lapisan tipuan memungkinkan Anda untuk memiliki pengidentifikasi stabil (indeks ke lapisan tipuan, di mana entri tidak bergerak) untuk sumber daya yang dapat bergerak selama pemadatan (daftar objek utama).

Tag versi memungkinkan Anda untuk menyimpan ID ke objek yang mungkin dihapus. Misalnya, Anda memiliki id (10,1). Objek dengan indeks 10 dihapus (misalnya, peluru Anda mengenai objek dan dihancurkan). Objek di lokasi memori itu dalam daftar objek utama kemudian memiliki nomor versinya bertemu, memberikannya (10,2). Jika Anda mencoba mencari lagi (10,1) dari ID yang sudah basi, pencarian akan mengembalikan objek tersebut melalui indeks 10, tetapi dapat melihat bahwa nomor versi telah berubah, sehingga ID tersebut tidak lagi valid.

Ini adalah struktur data tercepat mutlak yang dapat Anda miliki dengan ID stabil yang memungkinkan objek bergerak dalam memori, yang penting untuk lokalitas data dan koherensi cache. Ini lebih cepat daripada implementasi tabel hash yang dimungkinkan; tabel hash paling tidak perlu menghitung hash (lebih banyak instruksi daripada pencarian tabel) dan kemudian harus mengikuti rantai hash (baik daftar yang ditautkan dalam kasus mengerikan std :: unordered_map, atau daftar yang ditangani secara terbuka di implementasi tabel hash yang tidak bodoh), dan kemudian harus melakukan perbandingan nilai pada masing-masing kunci (tidak lebih mahal, tetapi mungkin lebih murah, daripada pemeriksaan tag versi). Tabel hash yang sangat baik (bukan yang ada dalam implementasi STL, karena STL mengamanatkan tabel hash yang dioptimalkan untuk berbagai kasus penggunaan dibandingkan dengan gim yang Anda gambarkan untuk daftar objek game) mungkin menghemat satu tipuan,

Ada berbagai peningkatan yang dapat Anda lakukan pada algoritme dasar. Menggunakan sesuatu seperti std :: deque untuk daftar objek utama, misalnya; satu lapisan tipuan tambahan, tetapi memungkinkan objek untuk dimasukkan ke dalam daftar lengkap tanpa membatalkan pointer sementara yang telah Anda peroleh dari slotmap.

Anda juga dapat menghindari menyimpan indeks di dalam objek, karena indeks dapat dihitung dari alamat memori objek (ini - objek), dan bahkan lebih baik hanya diperlukan ketika menghapus objek yang dalam hal ini Anda sudah memiliki id objek (dan karenanya index) sebagai parameter.

Permintaan maaf untuk penulisan; Saya tidak merasa itu deskripsi yang paling jelas. Sudah terlambat dan sulit untuk dijelaskan tanpa menghabiskan lebih banyak waktu daripada yang saya miliki pada sampel kode.

Sean Middleditch
sumber
1
Anda melakukan perdagangan ekstra dan alokasi tinggi / biaya gratis (swap) setiap akses untuk penyimpanan 'kompak'. Dalam pengalaman saya dengan video game, itu adalah perdagangan yang buruk :) YMMV tentu saja.
Jeff Gates
1
Anda tidak benar-benar melakukan dereferensi yang sering dalam skenario dunia nyata. Ketika melakukannya, Anda dapat menyimpan pointer yang dikembalikan secara lokal, terutama jika Anda menggunakan varian deque atau tahu Anda tidak akan membuat objek baru saat Anda memiliki pointer. Iterasi atas koleksi adalah operasi yang sangat mahal dan sering, Anda memerlukan id stabil, Anda ingin pemadatan memori untuk objek yang mudah menguap (seperti peluru, partikel, dll), dan tipuan sangat efisien pada perangkat keras modem. Teknik ini digunakan di lebih dari beberapa mesin komersial berkinerja sangat tinggi. :)
Sean Middleditch
1
Dalam pengalaman saya: (1) Video game dinilai berdasarkan kinerja kasus terburuk, bukan kinerja kasus rata-rata. (2) Anda biasanya memiliki 1 iterasi di atas koleksi per bingkai, sehingga memadatkannya hanya 'membuat case terburuk Anda lebih jarang' (3) Anda sering memiliki banyak allocs / membebaskan dalam satu frame, biaya tinggi berarti Anda membatasi kemampuan itu. (4) Anda memiliki deref tak terbatas per bingkai (dalam gim yang saya garap, termasuk Diablo 3, sering deref adalah op biaya perf tertinggi setelah optimasi moderat,> 5% dari beban server). Saya tidak bermaksud mengabaikan solusi lain, hanya menunjukkan pengalaman dan alasan saya!
Jeff Gates
3
Saya suka struktur data ini. Saya terkejut itu tidak terkenal. Ini sederhana dan menyelesaikan semua masalah yang membuat saya membenturkan kepala selama berbulan-bulan. Terima kasih telah berbagi.
Jo Bates
2
Setiap pemula yang membaca ini harus sangat waspada dengan saran ini. Ini adalah jawaban yang sangat menyesatkan. "Jawabannya selalu menggunakan array atau std :: vector. Jenis seperti daftar yang ditautkan atau std :: map biasanya benar-benar menghebohkan dalam game, dan itu pasti termasuk case seperti koleksi objek game." sangat dilebih-lebihkan. Tidak ada jawaban "SELALU", jika tidak, wadah lain ini tidak akan dibuat. Mengatakan peta / daftar "menghebohkan" juga merupakan hiperbola. Ada BANYAK permainan video yang menggunakan ini. "Paling Efisien" bukan "Paling Praktis" dan dapat salah dibaca sebagai "Terbaik" subyektif.
user50286
12

array ukuran tetap (memori linier)
dengan daftar bebas internal (O (1) mengalokasikan / membebaskan, indeks stabil)
dengan kunci referensi lemah (penggunaan kembali slot membatalkan kunci)
nol dereferensi overhead (ketika diketahui-valid)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Menangani semuanya, mulai dari peluru hingga monster, tekstur hingga partikel, dll. Ini adalah struktur data terbaik untuk video game. Saya pikir itu berasal dari Bungie (kembali pada hari-hari maraton / mitos), saya mempelajarinya di Blizzard, dan saya pikir itu ada dalam permainan pemrograman permata di masa itu. Mungkin di seluruh industri game saat ini.

T: "Mengapa tidak menggunakan array dinamis?" A: Dynamic array menyebabkan crash. Contoh sederhana:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

Anda dapat membayangkan kasus dengan lebih banyak komplikasi (seperti callstacks mendalam). Ini berlaku untuk semua wadah seperti array. Saat membuat game, kami memiliki pemahaman yang cukup tentang masalah kami untuk memaksa ukuran dan anggaran pada segala sesuatu dengan imbalan kinerja.

Dan saya tidak bisa mengatakannya dengan cukup: Sungguh, ini adalah hal terbaik yang pernah ada. (Jika Anda tidak setuju, posting solusi Anda yang lebih baik! Peringatan - harus mengatasi masalah yang tercantum di bagian atas posting ini: memori linier / iterasi, O (1) alokasikan / bebas, indeks stabil, referensi lemah, nol overhead derefs atau punya alasan yang menakjubkan mengapa Anda tidak memerlukannya;)

Jeff Gates
sumber
Apa maksud Anda dengan array dinamis ? Saya menanyakan ini karena DataArraysepertinya juga mengalokasikan array secara dinamis di ctor. Jadi itu mungkin memiliki arti yang berbeda dengan pemahaman saya.
Eonil
Maksud saya sebuah array yang mengubah ukuran / memmoves selama penggunaannya (sebagai lawan dari konstruksinya). Vektor stl adalah contoh dari apa yang saya sebut array dinamis.
Jeff Gates
@ JeffGates Sangat menyukai jawaban ini. Sepenuhnya setuju untuk menerima kembali kasus terburuk sebagai biaya runtime kasus standar. Mendukung daftar tautan gratis menggunakan array yang ada sangat elegan. Pertanyaan P1: Tujuan dari yang maksimum? T2: Apa tujuan menyimpan indeks dalam bit urutan rendah id untuk entri yang dialokasikan? Kenapa tidak 0? T3: Bagaimana ini menangani generasi entitas? Jika tidak, saya sarankan menggunakan bit orde rendah Q2 untuk menghitung generasi ushort. - Terima kasih.
Insinyur
1
A1: Max digunakan memungkinkan Anda untuk membatasi iterasi Anda. Anda juga diamortisasi biaya konstruksi. A2: 1) Anda sering pergi dari item -> id. 2) Itu membuat membandingkan murah / jelas. A3: Saya tidak yakin apa artinya 'generasi'. Saya akan menafsirkan ini sebagai 'bagaimana Anda membedakan item ke-5 yang dialokasikan di slot 7 dari item ke-6?' di mana 5 dan 6 adalah generasi. Skema yang diusulkan menggunakan satu penghitung secara global untuk semua slot. (Kami benar-benar memulai penghitung ini pada nomor yang berbeda untuk setiap instance DataArray agar lebih mudah membedakan id.) Saya yakin Anda bisa menata ulang bit per pelacakan item itu penting.
Jeff Gates
1
@ JeffGates - Saya tahu ini adalah topik lama tapi saya sangat menyukai ide ini, dapatkah Anda memberi saya info tentang cara kerja void Free (T &) over void Free (id)?
TheStatehz
1

Tidak ada jawaban yang tepat untuk ini. Itu semua tergantung pada implementasi algoritma Anda. Hanya pergi dengan yang menurut Anda terbaik. Jangan mencoba mengoptimalkan pada tahap awal ini.

Jika Anda sering menghapus objek dan membuatnya kembali, saya sarankan Anda melihat bagaimana kumpulan objek diimplementasikan.

Sunting: Mengapa menyulitkan hal-hal dengan slot dan apa yang tidak. Mengapa tidak menggunakan tumpukan saja dan melepas item terakhir dan menggunakannya kembali? Jadi, ketika Anda menambahkan satu, Anda akan melakukan ++, ketika Anda pop satu yang Anda lakukan - untuk melacak indeks akhir Anda.

Sidar
sumber
Tumpukan sederhana tidak menangani kasing di mana item dihapus dalam urutan acak.
Jeff Gates
Agar adil, tujuannya tidak terlalu jelas. Setidaknya tidak untuk saya.
Sidar
1

Itu tergantung pada gim Anda. Wadah berbeda dalam seberapa cepat akses ke elemen tertentu, seberapa cepat elemen dihapus dan seberapa cepat elemen ditambahkan.


  • std :: vektor - Akses cepat dan menghapus dan menambahkan ke ujung cepat. Menghapus dari awal dan tengah lambat.
  • std :: list - Iterasi atas daftar tidak lebih lambat dari vektor tetapi mengakses titik tertentu dari daftar lambat (karena iterasi pada dasarnya adalah satu-satunya hal yang dapat Anda lakukan dengan daftar). Menambah dan Menghapus item di mana saja dengan cepat. Sebagian besar overhead memori. Tidak kontinu.
  • std :: deque - Akses cepat dan menghapus / menambahkan ke ujung dan awal cepat tetapi lambat di tengah.

Biasanya Anda ingin menggunakan daftar jika Anda ingin daftar objek Anda diurutkan dengan cara yang berbeda dari waktu yang lama dan karenanya harus memasukkan objek baru daripada menambahkan, deque sebaliknya. Sebuah deque telah meningkatkan fleksibilitas lebih dari satu vektor tetapi tidak memiliki banyak kelemahan.

Jika Anda memiliki banyak entitas, Anda harus melihat Space Partitioning.

API-Beast
sumber
Tidak benar daftar: kembali. Saran Deque sepenuhnya tergantung pada implementasi deque, yang sangat bervariasi dalam kecepatan dan pelaksanaannya.
metamorfosis