Usando uma arquitetura de sistema de entidades com paralelismo baseado em tarefas

9

fundo

Eu tenho trabalhado na criação de um mecanismo de jogo multithread no meu tempo livre e atualmente estou tentando decidir a melhor maneira de trabalhar com um sistema de entidades no que eu já criei. Até agora, usei este artigo da Intel como ponto de partida para o meu mecanismo. Até agora, implementei o ciclo normal do jogo usando tarefas e agora estou passando a incorporar alguns dos sistemas e / ou sistemas de entidades. Eu usei algo semelhante a Artemis no passado, mas o paralelismo está me deixando louco.

O artigo da Intel parece advogar a existência de várias cópias dos dados da entidade e a realização de alterações em cada entidade sendo distribuídas internamente no final de uma atualização completa. Isso significa que a renderização sempre estará um quadro atrás, mas isso parece um compromisso aceitável, considerando os benefícios de desempenho que devem ser obtidos. No entanto, quando se trata de um sistema de entidades como a Artemis, duplicar cada entidade para cada sistema significa que cada componente também precisará ser duplicado. Isso é possível, mas para mim parece que consumiria muita memória. As partes do documento da Intel que discutem isso são 2.2 e 3.2.2 principalmente. Pesquisei para encontrar boas referências para integrar as arquiteturas que pretendo, mas ainda não consegui encontrar nada útil.

Nota: Estou usando o C ++ 11 para este projeto, mas imagino que a maior parte do que estou pedindo seja bastante independente da linguagem.

Solução possível

Tenha um EntityManager global usado para criar e gerenciar Entidades e EntityAttributes. Permita acesso de leitura a eles apenas durante a fase de atualização e armazene todas as alterações em uma fila por encadeamento. Depois que todas as tarefas são concluídas, as filas são combinadas e as alterações em cada uma são aplicadas. Isso pode ter problemas com várias gravações nos mesmos campos, mas tenho certeza de que pode haver um sistema prioritário ou carimbo de data / hora para resolver isso. Essa parece ser uma boa abordagem para mim, porque os sistemas podem ser notificados sobre alterações nas entidades naturalmente durante o estágio de distribuição de alterações.

Questão

Estou procurando algum feedback sobre minha solução para ver se isso faz sentido. Não vou mentir e pretender ser um especialista em multithreading, e estou fazendo isso amplamente pela prática. Eu posso prever algumas bagunças complicadas surgindo da minha solução, onde vários sistemas estão lendo / gravando vários valores. A fila de mudanças que eu mencionei também pode ser difícil de formatar, de maneira que qualquer mudança possível possa ser facilmente comunicada quando eu não estiver trabalhando com o POD.

Qualquer feedback / conselho seria muito apreciado! Obrigado!

Ligações

Ross Hays
fonte

Respostas:

12

Fork-Join

Você não precisa de cópias separadas dos componentes. Basta usar um modelo de junção de garfo, que é (extremamente mal) mencionado nesse artigo da Intel.

Em um ECS, você efetivamente possui um loop como:

while in game:
  for each system:
    for each component in system:
      update component

Mude para algo como:

while in game:
  for each system:
    divide components into groups
    for each group:
      start thread (
        for each component in group:
          update component
      )
    wait for all threads to finish

A parte complicada é o bit "dividir componentes em grupos". Para gráficos, quase não há necessidade de dados compartilhados, por isso é simples (divida objetos renderizáveis ​​uniformemente pelo número de threads de trabalho disponíveis). Para física e IA, você deseja encontrar "ilhas" lógicas de objetos que não interagem e juntá-las. Quanto menor a interação entre os componentes, melhor.

Para a interação que deve existir, as mensagens atrasadas funcionam melhor. Se o objeto A precisar informar ao objeto B para sofrer danos, A poderá enfileirar uma mensagem em um pool por thread. Quando os encadeamentos são unidos, todos os conjuntos são concatenados em um único conjunto. Embora não esteja diretamente relacionado ao encadeamento, veja a série de artigos dos desenvolvedores do BitSquid (de fato, leia o blog inteiro; não concordo com tudo o que está lá, mas é um recurso fantástico).

Observe que "junção de bifurcação" não significa usar fork()(que cria processos, não threads), nem implica que você realmente deve ingressar nos threads. Isso significa apenas que você executa uma única tarefa, as divide em partes menores para serem tratadas pelo pool de threads de trabalho e aguarda que todas as parcelas sejam processadas.

Proxies

Essa abordagem pode ser usada isoladamente ou em combinação com o método de junção de forquilha para tornar menos importante a necessidade de separação estrita.

Você pode ser mais amigável com os threads em interação usando uma abordagem simples de duas camadas. Ter entidades "autoritativas" e entidades "proxy". Entidades autoritativas só podem ser modificadas a partir de um único encadeamento que é o proprietário claro da entidade autoritativa. As entidades de proxies não podem ser modificadas, apenas lidas. Em um ponto de sincronização no loop do jogo, propague todas as alterações de entidades autorizadas para os proxies correspondentes.

Substitua "entidades" por "componentes" conforme apropriado. O essencial é que você precisa de no máximo duas cópias de qualquer objeto, e existem pontos claros de "sincronização" no loop do jogo quando você pode copiar de um para o outro nos designs mais sensatos de mecanismos de jogos encadeados.

Você pode expandir proxies para ainda permitir que (um subconjunto de) métodos / mensagens sejam usados ​​simplesmente enviando todas essas coisas para uma fila que é entregue ao próximo quadro do objeto autoritativo.

Observe que a abordagem de proxy é um design fantástico para ter em um nível superior, pois torna o suporte à rede super fácil.

Sean Middleditch
fonte
Eu tinha lido algumas coisas sobre a junção de bifurcação que você mencionou anteriormente e fiquei com a impressão de que, embora isso permita que você utilize algum paralelismo, há situações em que alguns encadeamentos de trabalhadores podem estar esperando que um grupo termine. Idealmente, estou tentando evitar essa situação. A ideia do proxy é interessante e lembra um pouco o que eu estava trabalhando. Uma entidade tem EntityAttributes e esses são wrappers para os valores realmente armazenados pela entidade. Portanto, os valores podem ser lidos a qualquer momento, mas apenas definidos em determinados horários e podem conter um valor de proxy no atributo, correto?
Ross Hays
11
Há uma boa chance de que, ao tentar evitar a espera, você gaste tanto tempo analisando o gráfico de dependência que você perde tempo em geral.
Patrick Hughes
@roflha: sim, você pode colocar os proxies no nível EntityAttribute. Ou crie uma entidade separada com um segundo conjunto de atributos. Ou simplesmente abandone o conceito de atributos e use um design de componente menos granular.
Sean Middleditch
@SeanMiddleditch Quando digo atributo, estou me referindo essencialmente aos componentes que acho. Os atributos não são apenas valores únicos, como floats e strings, se é assim que eu fiz parecer. Em vez disso, são classes que contêm informações específicas como um PositionAttribute. Se componente é o nome aceito para isso, talvez eu deva mudar. Mas você recomendaria a proxy no nível da entidade e não no nível do componente / atributo?
Ross Hays
11
Eu recomendo o que você achar mais fácil de implementar. Lembre-se de que o ponto em que eu seria capaz de consultar proxies sem usar nenhum bloqueio, sem usar atômicos e sem conflitos.
Sean Middleditch