Como posso oferecer suporte à comunicação componente a objeto com segurança e com armazenamento de componente compatível com cache?

Estou criando um jogo que usa objetos de jogo baseados em componentes e estou tendo dificuldades para implementar uma maneira de cada componente se comunicar com seu objeto de jogo. Em vez de explicar tudo de uma vez, explicarei cada parte do código de exemplo relevante:

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

Ele GameObjectManagercontém todos os objetos do jogo e seus componentes. Também é responsável por atualizar os objetos do jogo. Isso é feito atualizando os vetores de componentes em uma ordem específica. Eu uso vetores em vez de matrizes para que praticamente não haja limite para o número de objetos do jogo que podem existir ao mesmo tempo.

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

A GameObjectclasse sabe quais são seus componentes e pode enviar mensagens para eles.

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

o Component classe é virtual pura, para que as classes dos diferentes tipos de componentes possam implementar como lidar com mensagens e atualizar. Também é capaz de enviar mensagens.

Agora, surge o problema de como os componentes podem chamar as sendMessagefunções em GameObjecte GameObjectManager. Eu vim com duas soluções possíveis:

1. Dê Componentum ponteiro para o seu GameObject.

No entanto, como os objetos do jogo estão em um vetor, os ponteiros podem rapidamente ser invalidados (o mesmo pode ser dito do vetor em GameObject , mas espero que a solução para esse problema também possa resolver esse). Eu poderia colocar os objetos do jogo em uma matriz, mas teria que passar um número arbitrário para o tamanho, que poderia facilmente ser desnecessariamente alto e desperdiçar memória.

2. Dê Componentum ponteiro para o GameObjectManager.

No entanto, não quero que os componentes possam chamar a função de atualização do gerente. Sou a única pessoa trabalhando nesse projeto, mas não quero adquirir o hábito de escrever códigos potencialmente perigosos.

Como posso resolver esse problema, mantendo meu código seguro e amigável ao cache?

Seu modelo de comunicação parece bom, e a opção um funcionaria bem se você pudesse armazenar esses ponteiros com segurança. Você pode resolver esse problema escolhendo uma estrutura de dados diferente para armazenamento de componentes.

A std::vector<T>foi uma primeira escolha razoável. No entanto, o comportamento de invalidação do iterador do contêiner é um problema. O que você quer é uma estrutura de dados que é rápido e cache-coerente para repetir, e que também preserva iterador estabilidade ao inserir ou remover itens.

Você pode criar essa estrutura de dados. Consiste em uma lista vinculada de páginas . Cada página tem uma capacidade fixa e mantém todos os seus itens em uma matriz. Uma contagem é usada para indicar quantos itens nessa matriz estão ativos. A página também tem uma lista livre (que permite a reutilização de entradas desmatadas) e uma lista de ignorar (o que lhe permite saltar sobre entradas apuradas durante a iteração.

Em outras palavras, conceitualmente algo como:

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

Eu, sem imaginação, chamo essa estrutura de dados de livro (porque é uma coleção de páginas que você itera), mas a estrutura tem vários outros nomes.

Matthew Bentley chama isso de "colônia". A implementação de Matthew usa um campo de pular com contagem de pulos (desculpas pelo link MediaFire, mas é como o próprio Bentley hospeda o documento), que é superior à lista de pulos baseada em booleano mais típica nesse tipo de estrutura. A biblioteca da Bentley é apenas de cabeçalho e fácil de ser inserida em qualquer projeto C ++, por isso aconselho que você simplesmente o use em vez de criar seu próprio. Há muitas sutilezas e otimizações que estou comentando aqui.

Como essa estrutura de dados nunca move itens depois de adicionados, ponteiros e iteradores para esse item permanecem válidos até que o próprio item seja excluído (ou o próprio contêiner seja limpo). Como armazena pedaços de itens alocados de forma contígua, a iteração é rápida e, na maior parte, coerente em cache. Inserção e remoção são razoáveis.

Não é perfeito; é possível arruinar a coerência do cache com um padrão de uso que envolve a exclusão de pontos efetivamente aleatórios no contêiner e a iteração sobre esse contêiner antes que as inserções subsequentes tenham itens de preenchimento. Se você estiver nesse cenário com frequência, estará ignorando regiões potencialmente grandes de memória por vez. No entanto, na prática, acho que esse contêiner é uma escolha razoável para o seu cenário.

Outras abordagens, que deixarei para outras respostas, podem incluir uma abordagem baseada em identificador ou um tipo de estrutura de mapa de slots (onde você tem uma matriz associativa de valores "chaves" a números inteiros "", os valores sendo índices em uma matriz de suporte, que permite iterar sobre um vetor, ainda acessando por "index" com alguma indireta extra).

Ser "amigável ao cache" é uma preocupação dos grandes jogos . Isso parece ser uma otimização prematura para mim.

Uma maneira de resolver isso sem ser 'amigável ao cache' seria criar seu objeto no heap em vez de na pilha: use new ponteiros (inteligentes) para seus objetos. Dessa forma, você poderá referenciar seus objetos e a referência deles não será invalidada.

Para uma solução mais amigável ao cache, você pode gerenciar a des / alocação de objetos e usar alças para esses objetos.

Basicamente, na inicialização do seu programa, um objeto reserva um pedaço de memória na pilha (vamos chamá-lo de MemMan); então, quando você deseja criar um componente, diz ao MemMan que precisa de um componente do tamanho X, ele ' Vamos reservá-lo para você, criar um identificador e manter internamente onde a alocação é o objeto para esse identificador. Ele retornará a alça e a única coisa que você manterá sobre o objeto, nunca será um ponteiro para sua localização na memória.

Conforme você precisar do componente, você solicitará ao MemMan para acessar esse objeto, o que ele fará com prazer. Mas não guarde a referência porque ...

Um dos trabalhos do MemMan é manter os objetos próximos um do outro na memória. Uma vez a cada poucos quadros de jogo, você pode pedir ao MemMan para reorganizar objetos na memória (ou pode fazê-lo automaticamente quando você cria / exclui objetos). Ele atualizará seu mapa de localização da memória. Suas alças sempre serão válidas, mas se você mantiver uma referência ao espaço da memória (um ponteiro ou uma referência ), encontrará apenas desespero e desolação.

Os livros didáticos dizem que essa maneira de gerenciar sua memória tem pelo menos 2 vantagens:

1. menos cache falha porque os objetos estão próximos um do outro na memória e
2. isso reduz o número de chamadas de des / alocação de memória que você fará para o sistema operacional, o que leva algum tempo.

Lembre-se de que a maneira como você usa o MemMan e como você organiza a memória internamente depende muito de como você usará seus componentes. Se você iterar através deles com base em seu tipo, manterá os componentes por tipo; se iterar através deles com base no objeto do jogo, será necessário encontrar uma maneira de garantir que eles estejam próximos. outro baseado nisso, etc ...