Qual é o container mais eficiente para armazenar objetos dinâmicos de jogos? [fechadas]

20

Estou criando um jogo de tiro em primeira pessoa e conheço muitos tipos diferentes de contêineres, mas gostaria de encontrar o contêiner mais eficiente para armazenar objetos dinâmicos que serão adicionados e excluídos do jogo com bastante frequência. Balas EX.

Penso que nesse caso seria uma lista para que a memória não seja contígua e nunca haja redimensionamento. Mas também estou pensando em usar um mapa ou conjunto. Se alguém tiver alguma informação útil, eu agradeceria.

Estou escrevendo isso em c ++ pelo caminho.

Também vim com uma solução que acho que funcionará.

Para começar, vou alocar um vetor de tamanho grande ... digamos 1000 objetos. Vou acompanhar o último índice adicionado nesse vetor para saber onde está o final dos objetos. Então, também criarei uma fila que conterá os índices de todos os objetos que são "excluídos" do vetor. (Nenhuma exclusão real será feita, apenas saberei que ela está livre). Portanto, se a fila estiver vazia, adicionarei o último índice adicionado no vetor + 1; caso contrário, adicionarei o índice do vetor que estava na frente da fila.

msawayda
fonte
Algum idioma específico que você está alvejando?
Phill.Zitt
Esta questão é muito difícil de responder sem um bom muitos mais detalhes, incluindo plataforma de hardware, a linguagem / frameworks, etc.
PlayDeezGames
11
Dica profissional: você pode armazenar a lista livre na memória dos elementos excluídos (para não precisar da fila extra).
9118 Jeff Gates
2
Existe uma pergunta nesta pergunta?
Trevor Powell
Observe que você não precisa acompanhar o maior índice nem pré-alocar vários elementos. std :: vector cuida de tudo isso para você.
API-Beast

Respostas:

33

A resposta é sempre usar uma matriz ou std :: vector. Tipos como uma lista vinculada ou um std :: map geralmente são absolutamente horríveis nos jogos, e isso definitivamente inclui casos como coleções de objetos do jogo.

Você deve armazenar os próprios objetos (não ponteiros para eles) na matriz / vetor.

Você quer memória contígua. Você realmente quer isso. A iteração sobre quaisquer dados na memória não contígua impõe muitas falhas de cache em geral e remove a capacidade do compilador e da CPU de realizar uma pré-busca de cache eficaz. Isso por si só pode prejudicar o desempenho.

Você também deseja evitar alocações e desalocações de memória. Eles são muito lentos, mesmo com um alocador de memória rápido. Eu já vi jogos obterem um aumento de 10x FPS ao remover algumas centenas de alocações de memória a cada quadro. Não parece que deve ser tão ruim, mas pode ser.

Por fim, a maioria das estruturas de dados de que você gosta para gerenciar objetos de jogo pode ser implementada com muito mais eficiência em uma matriz ou em um vetor do que com uma árvore ou uma lista.

Por exemplo, para remover objetos de jogo, você pode usar swap-and-pop. Facilmente implementado com algo como:

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

Você também pode marcar os objetos como excluídos e colocar o índice em uma lista gratuita para a próxima vez que precisar criar um novo objeto, mas fazer o swap-and-pop é melhor. Ele permite que você faça um loop for simples sobre todos os objetos ativos, sem ramificações além do próprio loop. Para integração da física de balas e similares, isso pode ser um aumento significativo no desempenho.

Mais importante, você pode encontrar objetos com um simples par de pesquisas de tabela a partir de um único estável usando a estrutura do mapa de slots.

Os objetos do seu jogo têm um índice em sua matriz principal. Eles podem ser pesquisados ​​de maneira muito eficiente com apenas esse índice (muito mais rápido que um mapa ou mesmo uma tabela de hash). No entanto, o índice não é estável devido à troca e pop ao remover objetos.

Um mapa de slots requer duas camadas de indireção, mas ambas são simples pesquisas de matriz com índices constantes. Eles são rápidos . Muito depressa.

A idéia básica é que você tenha três matrizes: sua lista principal de objetos, sua lista indireta e uma lista grátis para a lista indireta. Sua lista de objetos principal contém seus objetos reais, onde cada objeto conhece seu próprio ID exclusivo. O ID exclusivo é composto por um índice e uma tag de versão. A lista indireta é simplesmente uma matriz de índices para a lista principal de objetos. A lista livre é uma pilha de índices na lista indireta.

Ao criar um objeto na lista principal, você encontra uma entrada não utilizada na lista indireta (usando a lista gratuita). A entrada na lista indireta aponta para uma entrada não utilizada na lista principal. Você inicializa seu objeto nesse local e define seu ID exclusivo para o índice da entrada da lista indireta escolhida e a tag de versão existente no elemento principal da lista, mais uma.

Quando você destrói um objeto, faz o swap e pop normalmente, mas também incrementa o número da versão. Você também adiciona o índice da lista indireta (parte do ID exclusivo do objeto) à lista gratuita. Ao mover um objeto como parte do swap-and-pop, você também atualiza sua entrada na lista indireta para seu novo local.

Exemplo de pseudocódigo:

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)

A camada indireta permite que você tenha um identificador estável (o índice na camada indireta, para onde as entradas não se movem) para um recurso que pode se mover durante a compactação (a lista de objetos principal).

A tag version permite armazenar um ID em um objeto que pode ser excluído. Por exemplo, você tem o ID (10,1). O objeto com o índice 10 é excluído (digamos, seu marcador atinge um objeto e é destruído). O objeto nesse local da memória na lista principal de objetos tem seu número de versão aumentado, fornecendo-o (10,2). Se você tentar procurar (10,1) novamente a partir de um ID antigo, a pesquisa retornará esse objeto através do índice 10, mas poderá ver que o número da versão foi alterado, portanto o ID não é mais válido.

Essa é a estrutura de dados mais rápida e absoluta que você pode ter com um ID estável que permite que os objetos se movam na memória, o que é importante para a localidade dos dados e a coerência do cache. Isso é mais rápido do que qualquer implementação possível de uma tabela de hash; uma tabela de hash precisa, no mínimo, calcular um hash (mais instruções do que uma pesquisa de tabela) e seguir a cadeia de hash (uma lista vinculada no caso horrível de std :: unordered_map ou uma lista de endereços abertos em qualquer implementação não estúpida de uma tabela de hash) e, em seguida, faça uma comparação de valor em cada chave (não mais cara, mas possível menos cara do que a verificação da tag de versão). Uma tabela de hash muito boa (não a de qualquer implementação da STL, pois a STL exige uma tabela de hash otimizada para diferentes casos de uso do que você pensa em uma lista de objetos do jogo) pode economizar em um indireto,

Existem várias melhorias que você pode fazer no algoritmo base. Usando algo como um std :: deque para a lista principal de objetos, por exemplo; uma camada extra de indireção, mas permite que os objetos sejam inseridos em uma lista completa sem invalidar os ponteiros temporários que você adquiriu no mapa de slots.

Você também pode evitar o armazenamento do índice dentro do objeto, pois o índice pode ser calculado a partir do endereço de memória do objeto (this - objects) e, ainda melhor, só é necessário ao remover o objeto. Nesse caso, você já tem o ID do objeto (e, portanto, índice) como um parâmetro.

Desculpas pela redação; Não acho que seja a descrição mais clara possível. É tarde e é difícil de explicar sem gastar mais tempo do que eu tenho em amostras de código.

Sean Middleditch
fonte
11
Você está negociando um deref extra e um alto custo de alocação / custo livre (swap) todo acesso para armazenamento 'compacto'. Na minha experiência com videogames, isso é ruim :) YMMV, é claro.
9118 Jeff Gates
11
Na verdade, você não faz a desreferência que geralmente acontece em cenários do mundo real. Ao fazê-lo, você pode armazenar o ponteiro retornado localmente, especialmente se você usar a variante deque ou souber que não criará novos objetos enquanto tiver o ponteiro. A iteração sobre as coleções é uma operação muito cara e frequente, você precisa do ID estável, deseja compactação de memória para objetos voláteis (como marcadores, partículas, etc.), e a indireta é muito eficiente no hardware do modem. Essa técnica é usada em mais de alguns motores comerciais de alto desempenho. :)
Sean Middleditch
11
Na minha experiência: (1) Os videogames são julgados pelo pior desempenho, e não pelo desempenho médio. (2) Você normalmente tem 1 iteração em uma coleção por quadro, portanto, a compactação simplesmente 'torna seu pior caso menos frequente'. (3) Você costuma ter muitas alocações / liberta em um único quadro; alto custo significa que limita essa capacidade. (4) Você possui derefs ilimitados por quadro (nos jogos em que trabalhei, incluindo Diablo 3, geralmente o deref era o custo mais alto de desempenho após otimização moderada,> 5% da carga do servidor). Não pretendo descartar outras soluções, apenas apontando minhas experiências e raciocínio!
9108 Jeff Gates
3
Eu amo essa estrutura de dados. Estou surpreso que não seja mais conhecido. É simples e resolve todos os problemas que me fazem bater a cabeça há meses. Obrigado por compartilhar.
Jo Bates
2
Qualquer novato lendo isso deve ser muito cauteloso com esse conselho. Esta é uma resposta muito enganadora. "A resposta é sempre usar um array ou std :: vector. Tipos como uma lista vinculada ou um std :: map geralmente são absolutamente horrendos em jogos, e isso definitivamente inclui casos como coleções de objetos de jogos." é muito exagerado. Não existe uma resposta "SEMPRE", caso contrário, esses outros contêineres não teriam sido criados. Dizer mapas / listas é "horrendo" também é hipérbole. Existem muitos jogos de vídeo que os utilizam. "Mais eficiente" não é "Mais prático" e pode ser interpretado como um "Melhor" subjetivo.
User50286 20/05
12

matriz de tamanho fixo (memória linear)
com lista livre interna (O (1) alocação / livre, indicações estáveis)
com chaves de referência fracas (a reutilização do slot invalida a chave)
zero dereferências de sobrecarga (quando conhecidas como válidas)

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

Lida com tudo, desde marcadores a monstros, texturas a partículas, etc. Essa é a melhor estrutura de dados para videogames. Eu acho que veio da Bungie (nos dias de maratona / mito), eu aprendi sobre isso na Blizzard e acho que estava em uma gema de programação de jogos na época. Provavelmente está em toda a indústria de jogos neste momento.

P: "Por que não usar uma matriz dinâmica?" R: Matrizes dinâmicas causam falhas. Exemplo simples:

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

Você pode imaginar casos com mais complicações (como pilhas de chamadas profundas). Isso é verdade para todos os array, como contêineres. Ao fazer jogos, temos compreensão suficiente do nosso problema para forçar tamanhos e orçamentos em tudo em troca de desempenho.

E não posso dizer o suficiente: sério, essa é a melhor coisa de todas. (Se você não concordar, poste sua solução melhor! Advertência - deve resolver os problemas listados na parte superior deste post: memória / iteração linear, O (1) alocação / livre, índices estáveis, referências fracas, zero derefs ou tem uma razão incrível pela qual você não precisa de um desses;)

Jeff Gates
fonte
O que você quer dizer com matriz dinâmica ? Estou perguntando isso porque DataArrayparece também alocar uma matriz dinamicamente no ctor. Portanto, pode ter algum significado diferente no meu entendimento.
Eonil
Quero dizer uma matriz que redimensiona / memoriza durante seu uso (em oposição à sua construção). Um vetor stl é um exemplo do que eu chamaria de matriz dinâmica.
Jeff Gates,
@JeffGates Realmente gosto desta resposta. Concordo plenamente em aceitar o pior caso como custo padrão de tempo de execução. Fazer o backup da lista vinculada gratuita usando a matriz existente é muito elegante. Perguntas Q1: Finalidade de maxUsed? P2: Qual é o objetivo de armazenar o índice nos bits de ID de ordem inferior para entradas alocadas? Por que não 0? T3: como isso lida com gerações de entidades? Caso contrário, sugiro o uso de bits de baixa ordem do segundo trimestre para a contagem de gerações breves. - Obrigado.
Engenheiro de
11
A1: O máximo usado permite limitar sua iteração. Você também amortiza qualquer custo de construção. A2: 1) Você costuma ir do item -> id. 2) Faz a comparação barata / óbvia. A3: Não sei o que significa 'gerações'. Vou interpretar isso como 'como você diferencia o quinto item alocado no slot 7 do sexto item?' onde 5 e 6 são as gerações. O esquema proposto usa um contador globalmente para todos os slots. (Na verdade, iniciamos esse contador com um número diferente para cada instância do DataArray para diferenciar os IDs com mais facilidade).
Jeff Gates,
11
@ Jeffffates - Eu sei que esse é um tópico antigo, mas eu realmente gosto dessa idéia. Você poderia me dar algumas informações sobre o funcionamento interno do void Free (T &) sobre void Free (id)?
TheStatehz 16/03/19
1

Não há resposta certa para isso. Tudo depende da implementação dos seus algoritmos. Basta ir com o que você achar melhor. Não tente otimizar nesta fase inicial.

Se você costuma excluir objetos e recriá-los, sugiro que você veja como os pools de objetos são implementados.

Edit: Por que complicar as coisas com slots e quais não. Por que não usar uma pilha, retirar o último item e reutilizá-lo? Então, quando você adiciona um, você faz ++, quando você abre um - para acompanhar o seu índice final.

Sidar
fonte
Uma pilha simples não lida com o caso em que os itens são excluídos em ordem arbitrária.
9118 Jeff Gates
Para ser justo, seu objetivo não era exatamente claro. Pelo menos não para mim.
Sidar
1

Depende do seu jogo. Os contêineres são diferentes na rapidez com que o acesso a um elemento específico é, na rapidez com que um elemento é removido e na rapidez com que um elemento é adicionado.


  • std :: vector - O acesso rápido, a remoção e a adição ao final são rápidos. A remoção do início e do meio é lenta.
  • std :: list - A iteração sobre a lista não é muito mais lenta que um vetor, mas o acesso a um ponto específico da lista é lento (porque a iteração é basicamente a única coisa que você pode fazer com uma lista). Adicionar e remover itens em qualquer lugar é rápido. Maior sobrecarga de memória. Não contínuo.
  • std :: deque - Acesso rápido e remoção / adição ao final e início é rápido, mas lento no meio.

Geralmente, você deseja usar uma lista se quiser que sua lista de objetos seja classificada de maneira diferente da cronocialmente e, portanto, precise inserir novos objetos em vez de anexá-los, caso contrário, deque. Um deque aumentou a flexibilidade em relação a um vetor, mas realmente não tem muita desvantagem.

Se você realmente possui muitas entidades, consulte o Particionamento de espaço.

API-Beast
fonte
Não é verdade re: list. O conselho do Deque depende inteiramente das implementações do Deque, que variam muito em velocidade e execução.
metamorfose