Existe uma maneira melhor de configurar um sistema de eventos?

9

Os sistemas de eventos são incríveis, tornam o código extremamente difícil de manejar e realmente permitem a criação dinâmica de jogos através da fácil comunicação de objetos e do loop do jogo. Estou tendo dificuldades com a eficiência da minha implementação atual. Atualmente, minha pequena otimização de separar as listas de objetos nos eventos aos quais eles respondem fez maravilhas, mas deve haver mais que eu possa fazer.

Atualmente, tenho dois métodos:

  1. Mais simples: todos os objetos são adicionados a um vetor quando um evento é enviado, todos os objetos são enviados ao evento por meio do método handle_event ()

  2. Mais complexo: eu tenho um mapa com string como chave e int como valor. Quando um tipo de evento é adicionado, ele é adicionado a este mapa, com o int simplesmente sendo incrementado (deve haver uma maneira melhor)
    do vetor de vetores de objetos e, em seguida, empurra um novo vetor para lidar com esse tipo de evento.
    Quando um evento é chamado, ele simplesmente chama o int correspondente no mapa eventTypes para o tipo dentro do vetor de vetores de objetos e envia esse evento para cada objeto que manipula esse tipo de evento.

Esse primeiro método é bastante lento (obviamente) para muitos objetos, mas bastante rápido para muito poucos objetos. Enquanto o segundo método é bastante rápido com objetos grandes que gostariam de lidar com diferentes tipos de eventos, mas mais lento que o primeiro método por objeto com objetos manipulando o mesmo tipo de evento.

Existe uma maneira mais rápida (em termos de tempo de execução)? Existe uma maneira mais rápida de procurar um int do tipo string? (Inicialmente eu tinha um enum, mas não permitia tipos personalizados, necessários por causa do nível de dinamismo desejado).

ultifinito
fonte
11
É para isso que servem os mapas de hash (ou tabela de hash), a string é calculada para um número de hash que é usado para procurar diretamente em uma matriz. pt.wikipedia.org/wiki/Hash_table
Patrick Hughes
Uma boa pergunta é: isso realmente é um gargalo de desempenho ou você está apenas se preocupando prematuramente?
Jari Komppa
Já está implementado e há um gargalo quando muitos objetos são usados. Meu comentário anterior sobre a falta de gargalo não estava no aplicativo em si, mas na verdade na diferença de velocidade entre as duas implementações acima, onde o mesmo número de objetos foi realmente tratado. Eu estava esperando por outros métodos de criação de sistemas de eventos ... No entanto, algumas das idéias neste encadeamento aumentarão bastante a velocidade, especialmente no carregamento do sistema de eventos (11-25 segundos de tempo total de carregamento com 100000 objetos)
ultifinitus
100 mil objetos soam terrivelmente altos por apenas um jogo. É um servidor ou um aplicativo cliente de usuário final?
Patrick Hughes
Este é o meu motor, então estou realmente buscando flexibilidade. Ele será usado em aplicações de servidores e aplicativos do usuário final (menos frequentemente a primeira, optimization)
ultifinitus

Respostas:

5

Parece que você está dizendo que o grande gargalo de desempenho está pesquisando IDs de eventos (números inteiros) a partir de seus nomes de sequência. Você pode pré-processar os dados do jogo para converter todos os nomes de eventos em números inteiros antes de executar o jogo ou, possivelmente, ao carregar o nível; então você não precisaria fazer conversões durante o jogo.

Se os objetos estão sendo criados e destruídos com frequência, pode haver muita rotatividade nos vetores dos objetos. Nesse caso, você pode se beneficiar usando listas vinculadas em vez de vetores; eles são mais rápidos para inserção e exclusão.

Nathan Reed
fonte
O gargalo não é grande (para 100.000 objetos, perde .0000076 ms / objeto), mas acho que sua ideia é ótima! Eu acho que vou realmente fazer uma pesquisa única do id e ter o eventID armazenado como um int em vez dos dados da string original. Na verdade, eu não tinha pensado em listas vinculadas, boa ideia.
ultifinitus,
11
+1 Para pré-processar os IDs. Você também pode fazer isso preguiçosamente com um tipo de EventType que cada módulo pode obter por meio de algo como EventType takeDamageEvent = EventSystem::CacheEventType("takeDamageEvent");. Torne-o um membro estático das classes e você terá apenas uma cópia flutuando em cada classe que precisar.
michael.bartnett
2
Observe que o armazenamento de IDs em vez de seqüências de caracteres tornará a depuração um pouco difícil. É sempre útil poder ver algum texto especificando de onde um objeto veio. Você pode ir até a metade armazenando o id e a string, que você mantém por aí para fins de depuração (talvez até seja removida nas versões do release).
Nicol Bolas
2

Bem, vamos resolver as coisas simples primeiro. Você tem isso mapentre cadeias (o nome do evento, presumivelmente) e números inteiros (o índice dos ouvintes de eventos registrados).

O tempo de pesquisa em a mapé baseado em duas coisas: o número de itens no mapa e o tempo necessário para fazer a comparação entre duas chaves (ignorando problemas de cache). Se o tempo de pesquisa for um problema, uma maneira de lidar com isso é alterar a função de comparação, alterando o tipo de string.

Vamos supor que você esteja usando std::stringe operator<para comparação. Isso é altamente ineficiente; faz uma comparação em bytes. Você não se importa com a string real menos que a comparação; você só precisa de algum tipo de comparação que ofereça uma ordem estritamente fraca (porque mapnão funciona de outra maneira).

Portanto, você deve usar uma string de comprimento fixo de 32 bytes em vez de std::string. Eu os uso para identificadores. Os testes de comparação para essas cadeias fixas não fazem comparações de bytes; eles fazem comparações de 32 bits (ou 64 bits). Ele pega a cada 4 bytes como um número inteiro não assinado e o compara com os 4 bytes correspondentes da outra string. Dessa forma, a comparação leva apenas no máximo 8 comparações. Ele garante uma ordem estritamente fraca, embora a ordem não tenha nada a ver com os dados como caracteres.

Armazenar strings com mais de 31 bytes (precisa do caractere NULL) trunca a string (mas a partir do meio, e não das extremidades. Acho que a entropia tende a ser maior no início e no final). E seqüências de caracteres mais curtas do que isso exibem os caracteres restantes \0.

Agora, você pode abandonar mapcompletamente e usar uma tabela de hash. Se você realmente possui mais de 100.000 tipos diferentes de tipos de eventos, pode ser uma boa ideia. Mas não conheço um jogo em que isso seja remotamente razoável.

Nicol Bolas
fonte
Portanto, você deve usar uma string de comprimento fixo de 32 bytes em vez de std :: string. Fantástico! Eu não tinha pensado em mudar o tipo de corda.
ultifinitus 27/09
0

Para responder à pergunta geral:

Melhor maneira de configurar um sistema de eventos

Não há nenhum. Tudo o que você pode fazer é identificar as necessidades específicas que você terá para seus sistemas de eventos (pode haver várias diferentes) e, em seguida, usar a ferramenta certa para o trabalho certo.

Eu implementei e tentei generalizar toneladas de sistemas de eventos e cheguei a essa conclusão. Como os tradeoffs são realmente diferentes se você compilar em tempo de compilação ou tempo de execução, se usar hierarquias de objetos ou lousas etc.

A melhor maneira é estudar os diferentes tipos de sistemas de eventos e, em seguida, você terá dicas sobre qual usar.

Agora, se você deseja o sistema realmente mais flexível, implemente um sistema de quadro negro (tempo de execução) com propriedades dinâmicas de eventos e você terá algo muito flexível, mas talvez muito lento.

Klaim
fonte