Bagaimana saya bisa mendukung komunikasi komponen-ke-objek dengan aman dan dengan penyimpanan komponen yang ramah-cache?

Saya membuat game yang menggunakan objek game berbasis komponen, dan saya mengalami kesulitan menerapkan cara untuk setiap komponen berkomunikasi dengan objek game-nya. Daripada menjelaskan semuanya sekaligus, saya akan menjelaskan setiap bagian dari kode sampel yang relevan:

class GameObjectManager {
    public:
        //Updates all the game objects
        void update(Time dt);

        //Sends a message to all game objects
        void sendMessage(Message m);

    private:
        //Vector of all the game objects
        std::vector<GameObject> gameObjects;

        //vectors of the different types of components
        std::vector<InputComponent> input;
        std::vector<PhysicsComponent> ai;
        ...
        std::vector<RenderComponent> render;
}

The GameObjectManagermemegang semua objek game dan komponennya. Ini juga bertanggung jawab untuk memperbarui objek game. Ini dilakukan dengan memperbarui vektor komponen dalam urutan tertentu. Saya menggunakan vektor alih-alih array sehingga hampir tidak ada batasan jumlah objek game yang bisa ada sekaligus.

class GameObject {
    public:
        //Sends a message to the components in this game object
        void sendMessage(Message m);

    private:
        //id to keep track of components in the manager
        const int id;

        //Pointers to components in the game object manager
        std::vector<Component*> components;
}

The GameObjectkelas tahu apa komponennya dan dapat mengirim pesan kepada mereka.

class Component {
    public:
        //Receives messages and acts accordingly
        virtual void handleMessage(Message m) = 0;

        virtual void update(Time dt) = 0;

    protected:
        //Calls GameObject's sendMessage
        void sendMessageToObject(Message m);

        //Calls GameObjectManager's sendMessage
        void sendMessageToWorld(Message m);
}

The Componentkelas begitu virtual murni bahwa kelas untuk berbagai jenis komponen dapat menerapkan cara menangani pesan dan update. Itu juga mampu mengirim pesan.

Sekarang muncul masalah tentang bagaimana komponen dapat memanggil sendMessagefungsi dalam GameObjectdan GameObjectManager. Saya datang dengan dua solusi yang mungkin:

1. Berikan Componentpointer ke nya GameObject.

Namun, karena objek permainan berada dalam vektor, pointer dapat dengan cepat menjadi tidak valid (Hal yang sama dapat dikatakan tentang vektor dalam GameObject, tetapi mudah-mudahan solusi untuk masalah ini juga dapat menyelesaikannya). Saya bisa meletakkan objek game dalam array, tapi kemudian saya harus memberikan angka arbitrer untuk ukurannya, yang bisa dengan mudah menjadi tinggi dan membuang-buang memori.

2. Berikan Componentpointer ke GameObjectManager.

Namun, saya tidak ingin komponen dapat memanggil fungsi pembaruan manajer. Saya satu-satunya orang yang mengerjakan proyek ini, tetapi saya tidak ingin terbiasa menulis kode yang berpotensi berbahaya.

Bagaimana saya bisa mengatasi masalah ini sambil menjaga kode saya aman dan ramah cache?

Model komunikasi Anda tampaknya baik-baik saja, dan opsi satu akan berfungsi dengan baik jika Anda dapat menyimpan pointer itu dengan aman. Anda dapat memecahkan masalah itu dengan memilih struktur data yang berbeda untuk penyimpanan komponen.

A std::vector<T>adalah pilihan pertama yang masuk akal. Namun, perilaku validasi iterator penampung adalah masalah. Apa yang Anda inginkan adalah struktur data yang cepat dan cache-koheren untuk iterate over, dan yang juga menjaga stabilitas iterator saat memasukkan atau menghapus item.

Anda dapat membangun struktur data seperti itu. Ini terdiri dari daftar- halaman yang ditautkan . Setiap halaman memiliki kapasitas tetap, dan menyimpan semua item dalam satu larik. Hitungan digunakan untuk menunjukkan berapa banyak item dalam array yang aktif. Sebuah halaman juga memiliki daftar gratis (yang memungkinkan penggunaan kembali entri dibersihkan) dan daftar melewatkan (yang memungkinkan Anda untuk melewatkan lebih entri dibersihkan sementara iterasi.

Dengan kata lain, secara konseptual sesuatu seperti:

struct Page {
   int count;
   int capacity;           // Optional if every page is a fixed size.
   T * m_storage;
   bool * m_skip;          // Skip list; can be bit-compressed.
   std::stack<int> m_free; // Can be replaced with a specialized stack.

   Page * next;
   Page * prior;           // Optional, allows reverse iteration
};

Saya secara tidak imajinatif menyebut struktur data ini sebuah buku (karena ini adalah kumpulan halaman yang Anda ulangi), tetapi struktur ini memiliki berbagai nama lain.

Matthew Bentley menyebutnya "koloni." Implementasi Matthew menggunakan bidang lompatan penghitungan lompatan (permintaan maaf untuk tautan MediaFire, tapi begitulah Bentley sendiri yang menyimpan dokumen) yang lebih unggul daripada daftar lompatan berbasis boolean yang lebih khas dalam jenis struktur ini. Pustaka Bentley hanya untuk header dan mudah dimasukkan ke proyek C ++ apa pun, jadi saya sarankan Anda untuk menggunakannya dibandingkan dengan menggulirkan proyek Anda sendiri. Ada banyak seluk-beluk dan optimisasi yang saya sampaikan di sini.

Karena struktur data ini tidak pernah memindahkan item setelah ditambahkan, pointer dan iterator ke item tersebut tetap valid sampai item itu sendiri dihapus (atau wadah itu sendiri dihapus). Karena ia menyimpan potongan-potongan item yang dialokasikan berdekatan, iterasi cepat dan sebagian besar-cache-koheren. Penyisipan dan penghapusan keduanya masuk akal.

Itu tidak sempurna; itu mungkin untuk merusak koherensi cache dengan pola penggunaan yang melibatkan banyak penghapusan dari tempat-tempat acak efektif dalam wadah dan kemudian iterasi atas wadah itu sebelum sisipan berikutnya memiliki item yang ditimbun kembali. Jika Anda sering berada dalam skenario itu, Anda akan melompati wilayah memori yang berpotensi besar secara bersamaan. Namun dalam praktiknya saya pikir wadah ini adalah pilihan yang masuk akal untuk skenario Anda.

Pendekatan lain, yang akan saya tinggalkan untuk jawaban lain untuk dibahas, mungkin termasuk pendekatan berbasis pegangan atau semacam struktur peta-slot (di mana Anda memiliki array asosiatif "kunci" integer untuk "nilai" integer, "nilai yang dijadikan indeks dalam array backing, yang memungkinkan Anda untuk beralih pada vektor dengan masih mengakses oleh "indeks" dengan beberapa tipuan ekstra).

Menjadi 'cache friendly' adalah keasyikan yang dimiliki game besar . Ini sepertinya menjadi optimasi dini bagi saya.

Salah satu cara untuk menyelesaikan ini tanpa menjadi 'cache friendly' adalah dengan membuat objek Anda di heap, bukan di stack: gunakan newdan (smart) pointer untuk objek Anda. Dengan cara ini, Anda dapat merujuk objek Anda dan referensi mereka tidak akan dibatalkan.

Untuk solusi yang lebih ramah cache, Anda bisa mengelola de / alokasi objek sendiri, dan menggunakan pegangan untuk objek-objek ini.

Pada dasarnya, pada inisialisasi program Anda, sebuah objek menyimpan sepotong memori pada heap (sebut saja MemMan), kemudian, ketika Anda ingin membuat komponen, Anda memberi tahu MemMan bahwa Anda memerlukan komponen ukuran X, itu ' Saya akan mencadangkannya untuk Anda, membuat pegangan dan menjaga internal di mana alokasi itu adalah objek untuk pegangan itu. Ini akan mengembalikan pegangan, dan bahwa satu-satunya yang Anda simpan tentang objek, tidak pernah pointer ke lokasi di memori.

Saat Anda membutuhkan komponen, Anda akan meminta MemMan untuk mengakses objek ini, yang dengan senang hati akan ia lakukan. Tetapi jangan menyimpan referensi karena ....

Salah satu tugas MemMan adalah menjaga benda-benda saling berdekatan dalam memori. Setelah setiap beberapa frame game, Anda dapat memberitahu MemMan untuk mengatur ulang objek dalam memori (atau bisa melakukannya secara otomatis saat Anda membuat / menghapus objek). Ini akan memperbarui peta pegangan-ke-lokasi-memori. Pegangan Anda akan selalu valid, tetapi jika Anda menyimpan referensi ke ruang memori (sebuah pointer atau referensi ), Anda hanya akan menemukan keputusasaan dan penghancuran.

Buku teks mengatakan bahwa cara mengelola memori Anda ini memiliki setidaknya 2 keuntungan:

1. cache kurang meleset karena objek saling berdekatan dalam memori dan
2. mengurangi jumlah memori de panggilan alokasi / Anda akan membuat ke OS, yang dikatakan untuk mengambil beberapa waktu.

Perlu diingat bahwa cara Anda menggunakan MemMan dan bagaimana Anda akan mengatur memori secara internal sangat tergantung pada bagaimana Anda akan menggunakan komponen Anda. Jika Anda akan mengulanginya berdasarkan jenisnya, Anda ingin menyimpan komponen berdasarkan jenisnya, jika Anda mengulanginya berdasarkan objek permainan mereka, Anda harus menemukan cara untuk memastikan mereka dekat dengan lain berdasarkan itu, dll ...