Desempenho de gargalo no ECS

5

Eu tenho procurado construir um sistema de componente-entidade. Basicamente, uma entidade é apenas um id envolvido em torno de uma struct, componentes são dados pertencentes a essa entidade (e referenciam o id), e os sistemas são o código. Entidades e componentes são todos armazenados dentro de matrizes, para permitir iteração rápida sobre cada um.

Por exemplo, uma entidade pode ter um componente de massa, posição e velocidade. Um GravitySystem usaria esses três componentes, calcularia alguma velocidade (com base na massa) e a adicionaria ao componente Posição.

Meu problema é, o que acontece quando uma entidade é removida do meio de uma matriz? Uma opção é ter o último elemento das posições de troca de matriz com a entidade que acabou de ser removida, para que o array permaneça bem empacotado. A desvantagem é que perco a capacidade de fazer referência a cada elemento pelo mesmo número de índice, isto é, a ID de entidade 5 está no índice 5 e cada componente pertencente a essa entidade também está localizado no índice 5 em suas próprias matrizes.

Uma solução seria apenas perguntar se a entidade [i] está "ativa" antes de cada iteração. Algo como,

void gravitySystem(entityList[], massList[], velocityList[], positionList[]) 
{
    for(int i = 0; i < 100; ++i) {
       if(entityList[i].isAlive == 1) {
         velocityList[i] += 9.81 * massList[i];
         positionList[i] += velocityList[i];
       }
       else {
         printf("The entity is dead, Jim.\n");
       }
     }
}

Meu problema com essa solução é que se eu tivesse uma lista enorme de entidades, digamos 4M, passando por esse loop, a instrução if (entityList [i] .isAlive == 1) teria um impacto no desempenho . Existe outra solução que removeria esse gargalo? Talvez um que manteria a matriz agradável e embalada sem "buracos"?

    
por Daniel Martin 23.12.2014 / 19:06
fonte

2 respostas

2

Uma solução possível seria substituir a entidade por uma nova entidade sem componentes. Com a configuração que você tem, isso soa como se fosse apenas uma questão de deixar a entidade lá e remover todos os componentes que fazem referência ao ID da entidade. Então, seus sistemas devem pular naturalmente essa entidade, já que ela não tem os componentes que eles precisam.

Ao mesmo tempo, você pode adicionar o índice a uma lista de índices de entidade "recicláveis". Ao criar novas entidades, se houver alguma coisa nessa lista, desloque um índice para fora da lista e use a entidade nesse índice em vez de colocá-lo no final. Ele não terá componentes neste momento, então você pode dar a ele os novos componentes, tornando-o efetivamente uma nova entidade.

Isso pressupõe que seus sistemas pularão entidades que não possuem os componentes necessários. O ideal seria escrever algo assim (c ++):

class GravitySystem : public System<MassComponent, PositionComponent, VelocityComponent> {
    public:
    GravitySystem() {}

    void logic(Entity& e) {
        auto mass = e.get<MassComponent>();
        auto pos = e.get<PositionComponent>();
        auto vel = e.get<VelocityComponent>();
        vel->y += 9.81 * mass->value;
        pos->x += vel->x;
        pos->y += vel->y;
    }
};

E, em seguida, no loop do seu jogo, você escreve algo como gravitySystem.process(entities) e itera sobre cada entidade e aplica a lógica em cada entidade que possui os componentes necessários. Então você não precisa se preocupar com IDs, a menos que você precise deles para outra coisa. Dê uma olhada em darkf / microecs para um exemplo.

    
por 23.12.2014 / 21:02
fonte
0

A solução simples é usar uma lista livre e, claro, remover todos os componentes ao solicitar a remoção de uma entidade. Reutilize a memória de uma entidade como um índice para a entidade next free quando ela for removida da lista (sem removê-la da matriz ou embaralhá-la). Este diagrama deve esclarecer a ideia:

Exemplodecódigo:

structEntity{unionData{...intnext_free;};Datadata;};structEcs{...vector<Entity>entities;intfree_entity;//setto-1initially};intEcs::insert_entity(constEntity&entity){if(free_entity!=-1){//Ifthere'safreeentityindexavailable,//popitfromthefreelistandoverwritethe//entityatthatindex.constintindex=free_entity;free_entity=entities[free_entity].data.next_free;entities[index]=entity;returnindex;}else{//Otherwiseinsertanewentity.entities.push_back(entity);returnentities.size()-1;}}voidEcs::erase_entity(intentity_index){//Pushtheentityindextothefreelist.entities[entity_index].data.next_free=free_entity;free_entity=entity_index;}

Issoevitaráqueseusíndicesseinvalidem,permitaarápidarecuperaçãodeespaçosvagosemantenhasuainserçãoeremoçãodeoperaçõesdetempoconstantebaratas,tudosemcriarnenhumanovaestruturadedadosoualgoassim.

Éclaroquesemprequevocêtiverumamatrizcom"buracos", ela poderá começar a desperdiçar memória se houver muitos espaços vazios em que o cliente removeu um monte de coisas e nunca se preocupou em inserir algo novo. Uma maneira de mitigar isso é usar uma sequência de acesso aleatório composta de blocos contendo, digamos, 16 entidades cada. Se um bloco ficar totalmente vazio, você pode liberar sua memória e substituí-lo por um ponteiro nulo, para ser realocado posteriormente se o cliente quiser recuperar o intervalo de índices que o bloco representava anteriormente. Isso tem o lado negativo do acesso aleatório mais lento (um pouco mais aritmético para acessar o elemento nth ), mas faz um trabalho melhor de liberar memória à medida que as pessoas removem elementos dele. Também é compatível com a abordagem de lista livre.

    
por 12.12.2017 / 21:23
fonte