Como implementar adequadamente o tratamento de mensagens em um sistema de entidade baseado em componentes?

Estou implementando uma variante do sistema de entidades que possui:

• Uma classe Entity que é pouco mais que um ID que liga componentes

• Um monte de classes de componentes que não têm "lógica de componente", apenas dados

• Um monte de classes de sistema (aka "subsistemas", "gerentes"). Eles fazem todo o processamento lógico da entidade. Na maioria dos casos básicos, os sistemas iteram através de uma lista de entidades nas quais estão interessados ​​e executam uma ação em cada uma delas.

• Um objeto de classe MessageChannel que é compartilhado por todos os sistemas de jogo. Cada sistema pode se inscrever em tipos específicos de mensagens para ouvir e também pode usar o canal para transmitir mensagens para outros sistemas.

A variante inicial do tratamento de mensagens do sistema era algo como isto:

1. Execute uma atualização em cada sistema de jogo sequencialmente

2. Se um sistema faz algo com um componente e essa ação pode ser interessante para outros sistemas, o sistema envia uma mensagem apropriada (por exemplo, um sistema chama

   messageChannel.Broadcast(new EntityMovedMessage(entity, oldPosition, newPosition))

   sempre que uma entidade é movida)

3. Cada sistema que se inscreveu na mensagem específica obtém seu método de tratamento de mensagens chamado

4. Se um sistema estiver manipulando um evento e a lógica de processamento de eventos exigir que outra mensagem seja transmitida, a mensagem será transmitida imediatamente e outra cadeia de métodos de processamento de mensagens será chamada

Essa variante estava OK até eu começar a otimizar o sistema de detecção de colisões (estava ficando muito lento à medida que o número de entidades aumentava). A princípio, ele iterava cada par de entidades usando um algoritmo simples de força bruta. Em seguida, adicionei um "índice espacial" que possui uma grade de células que armazena entidades que estão dentro da área de uma célula específica, permitindo assim fazer verificações apenas nas entidades nas células vizinhas.

Toda vez que uma entidade se move, o sistema de colisão verifica se a entidade está colidindo com algo na nova posição. Se for, uma colisão é detectada. E se ambas as entidades que colidem são "objetos físicos" (ambas têm o componente RigidBody e se destinam a se afastar para não ocupar o mesmo espaço), um sistema rígido de separação de corpos exige que o sistema de movimento mova as entidades para alguma parte posições específicas que os separariam. Isso, por sua vez, faz com que o sistema de movimentação envie mensagens notificando sobre as posições alteradas da entidade. O sistema de detecção de colisões deve reagir porque precisa atualizar seu índice espacial.

Em alguns casos, isso causa um problema porque o conteúdo da célula (uma lista genérica de objetos de Entidade em C #) é modificado enquanto eles estão sendo repetidos, causando uma exceção a ser lançada pelo iterador.

Então ... como posso impedir que o sistema de colisão seja interrompido enquanto ele verifica colisões?

É claro que eu poderia adicionar uma lógica "inteligente" / "complicada" que garante que o conteúdo da célula seja iterado corretamente, mas acho que o problema não está no próprio sistema de colisão (eu também tive problemas semelhantes em outros sistemas), mas na maneira como as mensagens são tratadas à medida que passam de um sistema para outro. O que eu preciso é de alguma maneira de garantir que um método específico de manipulação de eventos seja executado sem interrupções.

O que eu tentei:

• Filas de mensagens recebidas . Toda vez que um sistema transmite uma mensagem, ela é adicionada às filas de mensagens dos sistemas interessados ​​nela. Essas mensagens são processadas quando uma atualização do sistema é chamada de cada quadro. O problema : se um sistema A adicionar uma mensagem à fila B do sistema, funcionará bem se o sistema B for atualizado mais tarde do que o sistema A (no mesmo quadro de jogo); caso contrário, fará com que a mensagem processe o próximo quadro de jogo (não desejável para alguns sistemas)
• Filas de mensagens enviadas . Enquanto um sistema está manipulando um evento, todas as mensagens que ele transmite são adicionadas à fila de mensagens enviadas. As mensagens não precisam esperar que uma atualização do sistema seja processada: elas são tratadas "imediatamente" depois que o manipulador de mensagens inicial terminar seu trabalho. Se o manuseio das mensagens fizer com que outras mensagens sejam transmitidas, elas também serão adicionadas a uma fila de saída, para que todas as mensagens sejam tratadas no mesmo quadro. O problema: se o sistema de tempo de vida da entidade (implementei o gerenciamento de tempo de vida da entidade com um sistema) cria uma entidade, ele notifica alguns sistemas A e B sobre ele. Enquanto o sistema A processa a mensagem, ele causa uma cadeia de mensagens que eventualmente causam a destruição da entidade criada (por exemplo, uma entidade de bala foi criada exatamente onde colide com algum obstáculo, o que faz com que a bala se autodestrua). Enquanto a cadeia de mensagens está sendo resolvida, o sistema B não recebe a mensagem de criação da entidade. Portanto, se o sistema B também estiver interessado na mensagem de destruição da entidade, ele será recebido e somente após a conclusão da "cadeia", ele receberá a mensagem inicial de criação da entidade. Isso faz com que a mensagem de destruição seja ignorada, a mensagem de criação seja "aceita",

EDITAR - RESPOSTAS A PERGUNTAS, COMENTÁRIOS:

• Quem modifica o conteúdo da célula enquanto o sistema de colisão itera sobre eles?

Enquanto o sistema de colisão estiver realizando verificações de colisão em alguma entidade e em seus vizinhos, uma colisão pode ser detectada e o sistema da entidade enviará uma mensagem que será reagida imediatamente por outros sistemas. A reação à mensagem pode fazer com que outras mensagens sejam criadas e também tratadas imediatamente. Portanto, algum outro sistema pode criar uma mensagem que o sistema de colisão precisaria processar imediatamente (por exemplo, uma entidade movida para que o sistema de colisão precise atualizar seu índice espacial), mesmo que as verificações anteriores de colisão ainda não tenham sido concluídas.

• Você não pode trabalhar com uma fila de mensagens de saída global?

Eu tentei uma única fila global recentemente. Isso causa novos problemas. Problema: movo uma entidade de tanque para uma entidade de parede (o tanque é controlado com o teclado). Então eu decido mudar a direção do tanque. Para separar o tanque e a parede de cada quadro, o CollidingRigidBodySeparationSystem afasta o tanque da parede pela menor quantidade possível. A direção de separação deve ser a oposta à direção de movimento do tanque (quando o desenho do jogo começa, o tanque deve parecer que nunca se moveu contra a parede). Mas a direção se torna oposta à direção NEW, movendo o tanque para um lado diferente da parede do que era inicialmente. Por que o problema ocorre: É assim que as mensagens são tratadas agora (código simplificado):

public void Update(int deltaTime)
{   
    m_messageQueue.Enqueue(new TimePassedMessage(deltaTime));
    while (m_messageQueue.Count > 0)
    {
        Message message = m_messageQueue.Dequeue();
        this.Broadcast(message);
    }
}

private void Broadcast(Message message)
{       
    if (m_messageListenersByMessageType.ContainsKey(message.GetType()))
    {
        // NOTE: all IMessageListener objects here are systems.
        List<IMessageListener> messageListeners = m_messageListenersByMessageType[message.GetType()];
        foreach (IMessageListener listener in messageListeners)
        {
            listener.ReceiveMessage(message);
        }
    }
}

O código flui assim (vamos supor que não seja o primeiro quadro do jogo):

1. Os sistemas iniciam o processamento do TimePassedMessage
2. InputHandingSystem converte pressionamentos de tecla em ação da entidade (nesse caso, uma seta esquerda se transforma em ação MoveWest). A ação da entidade é armazenada no componente ActionExecutor
3. ActionExecutionSystem , em reação à ação da entidade, adiciona um MovementDirectionChangeRequestedMessage ao final da fila de mensagens
4. MovementSystem move a posição da entidade com base nos dados do componente Velocity e adiciona a mensagem PositionChangedMessage ao final da fila. O movimento é feito usando a direção / velocidade do quadro anterior (digamos norte)
5. Os sistemas param de processar TimePassedMessage
6. Os sistemas iniciam o processamento de MovementDirectionChangeRequestedMessage
7. MovementSystem altera a velocidade / direção do movimento da entidade, conforme solicitado
8. Os sistemas param de processar MovementDirectionChangeRequestedMessage
9. Os sistemas iniciam o processamento de PositionChangedMessage
10. O CollisionDetectionSystem detecta que, porque uma entidade se moveu, ela se deparou com outra entidade (o tanque foi dentro de uma parede). Ele adiciona um CollisionOccuredMessage à fila
11. Os sistemas param de processar PositionChangedMessage
12. Os sistemas começam a processar o CollisionOccuredMessage
13. O CollidingRigidBodySeparationSystem reage à colisão separando o tanque e a parede. Como a parede é estática, apenas o tanque é movido. A direção de movimento dos tanques é usada como um indicador de onde o tanque veio. É deslocado na direção oposta

ERRO: Quando o tanque moveu esse quadro, ele se moveu usando a direção do movimento do quadro anterior, mas quando estava sendo separado, a direção do movimento do quadro ESTE foi usada, mesmo que já fosse diferente. Não é assim que deve funcionar!

Para evitar esse bug, a antiga direção do movimento precisa ser salva em algum lugar. Eu poderia adicioná-lo a algum componente apenas para corrigir esse bug específico, mas esse caso não indica uma maneira fundamentalmente errada de lidar com mensagens? Por que o sistema de separação se importa com a direção do movimento que usa? Como posso resolver esse problema com elegância?

• Você pode ler gamadu.com/artemis para ver o que eles fizeram com o Aspects, que lado soluciona alguns dos problemas que você está vendo.

Na verdade, eu já conheço Artemis há um bom tempo. Investiguei o código fonte, li os fóruns, etc. Mas já vi "Aspectos" sendo mencionados apenas em alguns lugares e, até onde eu entendi, eles basicamente significam "Sistemas". Mas não vejo como o lado de Artemis resolve alguns dos meus problemas. Ele nem usa mensagens.

• Consulte também: "Comunicação da entidade: Fila de mensagens vs Publicar / Assinar vs Sinal / Slots"

Eu já li todas as perguntas sobre gamedev.stackexchange sobre sistemas de entidades. Este parece não discutir os problemas que estou enfrentando. Estou esquecendo de algo?

• Lide com os dois casos de maneira diferente, a atualização da grade não precisa depender das mensagens de movimento, pois faz parte do sistema de colisão

Não sei bem o que você quer dizer. Implementações mais antigas do CollisionDetectionSystem apenas checavam colisões em uma atualização (quando um TimePassedMessage era tratado), mas eu precisava minimizar as verificações o máximo possível devido ao desempenho. Então, mudei para a verificação de colisão quando uma entidade se move (a maioria das entidades no meu jogo é estática).

Você provavelmente já ouviu falar do antipadrão de objetos God / Blob. Bem, seu problema é um loop de Deus / Blob. Ajustar o seu sistema de transmissão de mensagens fornecerá, na melhor das hipóteses, uma solução Band-Aid e, na pior das hipóteses, uma completa perda de tempo. De fato, seu problema não tem nada a ver especificamente com o desenvolvimento de jogos. Eu me peguei tentando modificar uma coleção enquanto iterava sobre ela várias vezes, e a solução é sempre a mesma: subdividir, subdividir, subdividir.

Pelo que entendi a redação de sua pergunta, seu método de atualizar seu sistema de colisão atualmente se parece amplamente com o seguinte.

for each possible collision
    check for collision
    handle collision
    modify collision world to reflect change // exception happens here

Escrito de maneira clara, você pode ver que seu loop tem três responsabilidades, quando deveria ter apenas uma. Para resolver seu problema, divida seu loop atual em três loops separados, representando três passes algorítmicos diferentes .

for each possible collision
    check for collision, record it if a collision occurs

for each found collision
    handle collision, record the collision response (delete object, ignore, etc.)

for each collision response
    modify collision world according to response

Ao subdividir seu loop original em três subloops, você não tenta mais modificar a coleção na qual está iterando no momento. Observe também que você não está fazendo mais trabalho do que no loop original e, de fato, pode obter algumas vitórias em cache executando as mesmas operações muitas vezes sequencialmente.

Há também um benefício adicional: agora você pode introduzir paralelismo no seu código. Sua abordagem de loop combinado é inerentemente serial (que é fundamentalmente o que a exceção de modificação simultânea está lhe dizendo!), Porque cada iteração de loop potencialmente lê e grava no seu mundo de colisão. Os três subloops que apresento acima, no entanto, todos lêem ou escrevem, mas não os dois. No mínimo, a primeira passagem, verificando todas as possíveis colisões, tornou-se embaraçosamente paralela e, dependendo de como você escreve seu código, as segunda e terceira passagens também podem ser.

Como implementar adequadamente o tratamento de mensagens em um sistema de entidade baseado em componentes?

Eu diria que você deseja dois tipos de mensagens: Síncrona e Assíncrona. As mensagens síncronas são tratadas imediatamente, enquanto as assíncronas são tratadas não no mesmo quadro de pilha (mas podem ser tratadas no mesmo quadro de jogo). A decisão geralmente tomada em uma base "por classe de mensagem", por exemplo, "todas as mensagens EnemyDied são assíncronas".

Alguns eventos são tratados com muito mais facilidade com uma dessas maneiras. Por exemplo, na minha experiência, um evento ObjectGetsDeletedNow - é muito menos sexy e os retornos de chamada são muito mais difíceis de implementar do que ObjectWillBeDeletedAtEndOfFrame. Por outro lado, qualquer manipulador de mensagens semelhante ao "veto" (código que pode cancelar ou modificar determinadas ações enquanto são executadas, como um efeito Shield modifica o DamageEvent ) não será fácil em ambientes assíncronos, mas é um pedaço de bolo em chamadas síncronas.

Assíncrono pode ser mais eficiente em alguns casos (por exemplo, você pode pular alguns manipuladores de eventos quando o objeto for excluído posteriormente mais tarde). Às vezes, o síncrono é mais eficiente, especialmente quando o cálculo do parâmetro para um evento é caro e você gosta de passar funções de retorno de chamada para recuperar determinados parâmetros em vez de valores já calculados (caso ninguém esteja interessado nesse parâmetro em particular).

Você já mencionou outro problema geral com sistemas de mensagens síncronas: Para minha experiência com sistemas de mensagens síncronas, um dos casos mais comuns de erros e luto em geral são as mudanças de lista enquanto iteramos nessas listas.

Pense sobre isso: é da natureza do síncrono (lidar imediatamente com todos os efeitos posteriores de alguma ação) e do sistema de mensagens (dissociar o receptor do remetente para que o remetente não saiba quem está reagindo às ações) que você não conseguirá facilmente localize esses loops. O que estou dizendo é: Esteja preparado para lidar muito com esse tipo de iteração auto-modificável. Seu tipo de "por design". ;-)

como posso impedir que o sistema de colisão seja interrompido enquanto verifica colisões?

Para o seu problema específico com a detecção de colisão, pode ser bom o suficiente para tornar os eventos de colisão assíncronos, para que eles fiquem na fila até o gerenciador de colisão ser concluído e executado como um lote depois (ou em algum momento posterior no quadro). Esta é a sua solução "fila de entrada".

O problema: se um sistema A adicionar uma mensagem à fila B do sistema, funcionará bem se o sistema B for atualizado mais tarde do que o sistema A (no mesmo quadro de jogo); caso contrário, fará com que a mensagem processe o próximo quadro de jogo (não desejável para alguns sistemas)

Fácil:

while (! fila.empty ()) {fila.pop (). handle (); }

Basta executar a fila repetidamente até que nenhuma mensagem permaneça. (Se você gritar "loop infinito" agora, lembre-se de que você provavelmente teria esse problema como "spam de mensagens" se atrasasse para o próximo quadro. Você pode reivindicar () um número razoável de iterações para detectar loops infinitos, se você quiser;))

Se você está realmente tentando fazer uso da natureza de design orientado a dados do ECS, convém pensar na maneira mais DOD de fazer isso.

Dê uma olhada no blog BitSquid , especificamente na parte sobre eventos. É apresentado um sistema que combina bem com o ECS. Faça o buffer de todos os eventos em uma fila limpa por tipo de mensagem, da mesma forma que os sistemas em um ECS são por componente. Os sistemas atualizados posteriormente podem iterar eficientemente sobre a fila de um determinado tipo de mensagem para processá-los. Ou apenas ignorá-los. Qualquer que seja.

Por exemplo, o CollisionSystem geraria um buffer cheio de eventos de colisão. Qualquer outro sistema executado após a colisão pode percorrer a lista e processá-los conforme necessário.

Ele mantém a natureza paralela orientada a dados do design do ECS sem toda a complexidade do registro de mensagens ou algo semelhante. Somente os sistemas que realmente se preocupam com um tipo específico de evento repetem a fila para esse tipo, e fazer uma iteração de passagem única direta na fila de mensagens é o mais eficiente possível.

Se você mantiver os componentes consistentemente ordenados em cada sistema (por exemplo, solicitar todos os componentes por ID da entidade ou algo parecido), você poderá obter o benefício agradável de que as mensagens serão geradas na ordem mais eficiente para iterá-las e procurar os componentes correspondentes no sistema de processamento. Ou seja, se você tiver as entidades 1, 2 e 3, as mensagens serão geradas nessa ordem e as pesquisas de componentes realizadas durante o processamento da mensagem estarão em ordem de endereço estritamente crescente (que é a mais rápida).