Comment implémenter correctement la gestion des messages dans un système d'entités basé sur des composants?

30

J'implémente une variante de système d'entité qui a:

  • Une classe d'entité qui n'est guère plus qu'un ID qui lie les composants entre eux

  • Un tas de classes de composants qui n'ont pas de "logique de composant", uniquement des données

  • Un tas de classes système (alias "sous-systèmes", "gestionnaires"). Ceux-ci font tout le traitement de la logique d'entité. Dans la plupart des cas de base, les systèmes parcourent simplement une liste d'entités qui les intéressent et effectuent une action sur chacun d'eux

  • Un objet de classe MessageChannel qui est partagé par tous les systèmes de jeu. Chaque système peut s'abonner à un type spécifique de messages à écouter et peut également utiliser le canal pour diffuser des messages vers d'autres systèmes

La variante initiale de la gestion des messages système était quelque chose comme ceci:

  1. Exécutez une mise à jour sur chaque système de jeu séquentiellement
  2. Si un système fait quelque chose à un composant et que cette action peut intéresser d'autres systèmes, le système envoie un message approprié (par exemple, un système appelle

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

    chaque fois qu'une entité est déplacée)

  3. Chaque système qui s'est abonné au message spécifique obtient sa méthode de gestion des messages appelée

  4. Si un système gère un événement et que la logique de traitement des événements nécessite la diffusion d'un autre message, le message est diffusé immédiatement et une autre chaîne de méthodes de traitement des messages est appelée

Cette variante était OK jusqu'à ce que je commence à optimiser le système de détection de collision (cela devenait vraiment lent à mesure que le nombre d'entités augmentait). Au début, il suffit d'itérer chaque paire d'entités à l'aide d'un simple algorithme de force brute. J'ai ensuite ajouté un "index spatial" qui a une grille de cellules qui stocke des entités qui se trouvent à l'intérieur de la zone d'une cellule spécifique, permettant ainsi de faire des vérifications uniquement sur les entités dans les cellules voisines.

Chaque fois qu'une entité se déplace, le système de collision vérifie si l'entité entre en collision avec quelque chose dans la nouvelle position. Si c'est le cas, une collision est détectée. Et si les deux entités en collision sont des "objets physiques" (elles ont toutes les deux un composant RigidBody et sont censées se repousser pour ne pas occuper le même espace), un système de séparation de corps rigide dédié demande au système de mouvement de déplacer les entités vers certaines positions spécifiques qui les sépareraient. Cela entraîne à son tour le système de mouvement à envoyer des messages informant des positions d'entité modifiées. Le système de détection de collision est censé réagir car il doit mettre à jour son index spatial.

Dans certains cas, cela provoque un problème car le contenu de la cellule (une liste générique d'objets Entity en C #) est modifié pendant leur itération, provoquant ainsi une exception levée par l'itérateur.

Alors ... comment puis-je empêcher le système de collision d'être interrompu pendant qu'il vérifie les collisions?

Bien sûr, je pourrais ajouter une logique "intelligente" / "délicate" qui assure que le contenu des cellules soit correctement itéré, mais je pense que le problème ne réside pas dans le système de collision lui-même (j'ai également eu des problèmes similaires dans d'autres systèmes), mais dans la manière les messages sont traités lorsqu'ils voyagent d'un système à l'autre. Ce dont j'ai besoin, c'est d'un moyen de garantir qu'une méthode de gestion d'événement spécifique fonctionne correctement sans interruption.

Ce que j'ai essayé:

  • Files d'attente de messages entrants . Chaque fois qu'un système diffuse un message, le message est ajouté aux files d'attente de messages des systèmes qui l'intéressent. Ces messages sont traités lorsqu'une mise à jour du système est appelée à chaque trame. Le problème : si un système A ajoute un message à la file d'attente B du système, cela fonctionne bien si le système B est destiné à être mis à jour plus tard que le système A (dans le même cadre de jeu); sinon, le message est traité dans la trame de jeu suivante (non souhaitable pour certains systèmes)
  • Files d'attente de messages sortants . Lorsqu'un système gère un événement, tous les messages qu'il diffuse sont ajoutés à la file d'attente des messages sortants. Les messages n'ont pas besoin d'attendre le traitement d'une mise à jour du système: ils sont traités "immédiatement" une fois que le gestionnaire de messages initial a terminé son travail. Si la gestion des messages entraîne la diffusion d'autres messages, ils sont également ajoutés à une file d'attente sortante, de sorte que tous les messages sont traités dans la même trame. Le problème: si le système de durée de vie d'entité (j'ai implémenté la gestion de durée de vie d'entité avec un système) crée une entité, il en informe certains systèmes A et B. Alors que le système A traite le message, il provoque une chaîne de messages qui finit par détruire l'entité créée (par exemple, une entité balle a été créée juste là où elle entre en collision avec un obstacle, ce qui provoque l'auto-destruction de la balle). Pendant la résolution de la chaîne de messages, le système B ne reçoit pas le message de création d'entité. Ainsi, si le système B s'intéresse également au message de destruction d'entité, il l'obtient et ce n'est qu'après la résolution de la "chaîne" qu'il obtient le message de création d'entité initial. Cela provoque le message de destruction à ignorer, le message de création à "accepté",

MODIFICATION - RÉPONSES AUX QUESTIONS, COMMENTAIRES:

  • Qui modifie le contenu de la cellule pendant que le système de collision le parcourt?

Pendant que le système de collision effectue des vérifications de collision sur une entité et ses voisins, une collision peut être détectée et le système d'entité enverra un message qui sera immédiatement réagi par d'autres systèmes. La réaction au message peut entraîner la création d'autres messages et leur traitement immédiat. Ainsi, un autre système pourrait créer un message que le système de collision devrait ensuite traiter immédiatement (par exemple, une entité a été déplacée de sorte que le système de collision doit mettre à jour son index spatial), même si les vérifications de collision antérieures n'étaient pas encore terminées.

  • Vous ne pouvez pas travailler avec une file d'attente de messages sortants globale?

J'ai récemment essayé une seule file d'attente globale. Cela provoque de nouveaux problèmes. Problème: je déplace une entité réservoir dans une entité mur (le réservoir est contrôlé avec le clavier). Ensuite, je décide de changer la direction du char. Pour séparer le réservoir et le mur de chaque cadre, le CollidingRigidBodySeparationSystem éloigne le réservoir du mur de la plus petite quantité possible. La direction de séparation doit être opposée à la direction de mouvement du tank (lorsque le dessin du jeu commence, le tank doit avoir l'air de ne jamais être entré dans le mur). Mais la direction devient opposée à la nouvelle direction, déplaçant ainsi le réservoir vers un côté du mur différent de ce qu'il était initialement. Pourquoi le problème se produit: Voici comment les messages sont traités maintenant (code simplifié):

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

Le code s'écoule comme ceci (supposons que ce n'est pas le premier cadre de jeu):

  1. Les systèmes commencent à traiter TimePassedMessage
  2. InputHandingSystem convertit les pressions de touches en action d'entité (dans ce cas, une flèche gauche se transforme en action MoveWest). L'action d'entité est stockée dans le composant ActionExecutor
  3. ActionExecutionSystem , en réaction à l'action d'entité, ajoute un MovementDirectionChangeRequestedMessage à la fin de la file d'attente de messages
  4. MovementSystem déplace la position de l'entité en fonction des données du composant Velocity et ajoute le message PositionChangedMessage à la fin de la file d'attente. Le mouvement se fait en utilisant la direction / vitesse du mouvement de l'image précédente (disons au nord)
  5. Les systèmes arrêtent le traitement de TimePassedMessage
  6. Les systèmes commencent à traiter MovementDirectionChangeRequestedMessage
  7. MovementSystem change la vitesse de l'entité / la direction du mouvement comme demandé
  8. Les systèmes arrêtent le traitement MovementDirectionChangeRequestedMessage
  9. Les systèmes commencent à traiter PositionChangedMessage
  10. CollisionDetectionSystem détecte que parce qu'une entité s'est déplacée, elle a rencontré une autre entité (le réservoir est entré à l'intérieur d'un mur). Il ajoute un CollisionOccuredMessage à la file d'attente
  11. Les systèmes arrêtent le traitement PositionChangedMessage
  12. Les systèmes commencent à traiter CollisionOccuredMessage
  13. CollidingRigidBodySeparationSystem réagit à la collision en séparant le réservoir et la paroi. Le mur étant statique, seul le réservoir est déplacé. La direction de mouvement des chars est utilisée comme indicateur de la provenance du char. Il est décalé dans une direction opposée

BOGUE: Lorsque le char a déplacé ce cadre, il s'est déplacé en utilisant le sens de déplacement du cadre précédent, mais lorsqu'il était séparé, le sens de déplacement de CE cadre a été utilisé, même s'il était déjà différent. Ce n'est pas comme ça que ça devrait fonctionner!

Pour éviter ce bug, l'ancienne direction de mouvement doit être enregistrée quelque part. Je pourrais l'ajouter à un composant juste pour corriger ce bogue spécifique, mais ce cas n'indique-t-il pas une manière fondamentalement erronée de gérer les messages? Pourquoi le système de séparation devrait-il se soucier de la direction de mouvement qu'il utilise? Comment puis-je résoudre ce problème avec élégance?

  • Vous voudrez peut-être lire gamadu.com/artemis pour voir ce qu'ils ont fait avec Aspects, quel côté résout certains des problèmes que vous voyez.

En fait, je connais Artemis depuis un bon moment maintenant. J'ai enquêté sur son code source, lu les forums, etc. Mais j'ai vu des "Aspects" mentionnés seulement à quelques endroits et, pour autant que je le comprenne, ils signifient essentiellement "Systèmes". Mais je ne vois pas comment le côté Artemis résout certains de mes problèmes. Il n'utilise même pas de messages.

  • Voir aussi: "Communication d'entité: file d'attente de messages vs publication / abonnement vs signal / slots"

J'ai déjà lu toutes les questions de gamedev.stackexchange concernant les systèmes d'entités. Celui-ci ne semble pas discuter des problèmes auxquels je suis confronté. Suis-je en train de manquer quelque chose?

  • Traitez les deux cas différemment, la mise à jour de la grille n'a pas besoin de s'appuyer sur les messages de mouvement car elle fait partie du système de collision

Je ne sais pas ce que tu veux dire. Les anciennes implémentations de CollisionDetectionSystem vérifiaient simplement les collisions lors d'une mise à jour (lorsqu'un TimePassedMessage était géré), mais je devais minimiser les contrôles autant que possible en raison des performances. J'ai donc opté pour la vérification des collisions lorsqu'une entité se déplace (la plupart des entités de mon jeu sont statiques).

Onlainas
la source
Il y a quelque chose qui n'est pas clair pour moi. Qui modifie le contenu de la cellule pendant que le système de collision le parcourt?
Paul Manta
Vous ne pouvez pas travailler avec une file d'attente de messages sortants globale? Ainsi, tous les messages qui y sont envoyés sont envoyés à chaque fois qu'une fois le système terminé, cela inclut l'autodestruction du système.
Roy T.
Si vous souhaitez conserver cette conception alambiquée, vous devez suivre @RoyT. C'est le seul moyen (sans messagerie complexe et temporelle) de gérer votre problème de séquençage. Vous voudrez peut-être lire gamadu.com/artemis pour voir ce qu'ils ont fait avec Aspects, quel côté résout certains des problèmes que vous voyez.
Patrick Hughes
2
Vous voudrez peut-être savoir comment Axum l'a fait en téléchargeant le CTP et en compilant du code - puis en inversant l'ingénierie du résultat en C # en utilisant ILSpy. La transmission de messages est une caractéristique importante des langages de modèles d'acteurs et je suis sûr que Microsoft sait ce qu'ils font - vous pourriez donc trouver qu'ils avaient la meilleure implémentation.
Jonathan Dickinson

Réponses:

12

Vous avez probablement entendu parler de l'anti-motif d'objet God / Blob. Eh bien, votre problème est une boucle God / Blob. Bricoler avec votre système de transmission de messages fournira au mieux une solution de pansement et au pire sera une perte de temps complète. En fait, votre problème n'a rien à voir avec le développement de jeux. Je me suis surpris à essayer de modifier une collection en itérant plusieurs fois dessus, et la solution est toujours la même: subdiviser, subdiviser, subdiviser.

Si je comprends bien le libellé de votre question, votre méthode de mise à jour de votre système de collision ressemble actuellement grosso modo à la suivante.

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

Écrit clairement comme ceci, vous pouvez voir que votre boucle a trois responsabilités, alors qu'elle ne devrait en avoir qu'une. Pour résoudre votre problème, divisez votre boucle actuelle en trois boucles distinctes représentant trois passes algorithmiques différentes .

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

En subdivisant votre boucle d'origine en trois sous-boucles, vous n'essayez plus de modifier la collection sur laquelle vous êtes en train d'itérer. Notez également que vous ne faites pas plus de travail que dans votre boucle d'origine, et en fait, vous pourriez gagner des gains de cache en effectuant les mêmes opérations plusieurs fois de manière séquentielle.

Il y a aussi un autre avantage, c'est que vous pouvez maintenant introduire le parallélisme dans votre code. Votre approche de boucle combinée est intrinsèquement série (ce qui est fondamentalement ce que l'exception de modification simultanée vous dit!), Car chaque itération de boucle peut potentiellement lire et écrire dans votre monde de collision. Les trois subloops que je présente ci-dessus, cependant, tous lisent ou écrivent, mais pas les deux. À tout le moins, la première passe, vérifiant toutes les collisions possibles, est devenue embarrassante en parallèle, et selon la façon dont vous écrivez votre code, les deuxième et troisième passes peuvent l'être également.

Canard
la source
Je suis complètement d'accord avec ça. J'utilise cette approche très similaire dans mon jeu et je pense que cela sera payant à long terme. C'est ainsi que le système de collision (ou le gestionnaire) devrait fonctionner (je pense en fait qu'il est possible de ne pas avoir de système de messagerie du tout).
Emiliano
11

Comment implémenter correctement la gestion des messages dans un système d'entités basé sur des composants?

Je dirais que vous voulez deux types de messages: synchrone et asynchrone. Les messages synchrones sont traités immédiatement tandis que les messages asynchrones ne sont pas traités dans le même cadre de pile (mais peuvent être traités dans le même cadre de jeu). La décision qui est généralement prise sur une base "par classe de message", par exemple "tous les messages EnemyDied sont asynchrones".

Certains événements sont simplement beaucoup plus faciles à gérer grâce à l'une de ces méthodes. Par exemple, d'après mon expérience, un événement ObjectGetsDeletedNow est beaucoup moins sexy et les rappels sont beaucoup plus difficiles à implémenter que ObjectWillBeDeletedAtEndOfFrame. Là encore, tout gestionnaire de messages de type "veto" (code qui peut annuler ou modifier certaines actions pendant qu'elles sont exécutées, comme un effet de bouclier modifie le DamageEvent ) ne sera pas facile dans les environnements asynchrones mais est un jeu d'enfant dans appels synchrones.

Asyncrone peut être plus efficace dans certains cas (par exemple, vous pouvez ignorer certains gestionnaires d'événements lorsque l'objet est supprimé plus tard de toute façon). Parfois synchrone est plus efficace, en particulier lorsque le calcul du paramètre d'un événement est coûteux et que vous préférez passer des fonctions de rappel pour récupérer certains paramètres au lieu de valeurs déjà calculées (au cas où personne ne serait intéressé par ce paramètre particulier de toute façon).

Vous avez déjà mentionné un autre problème général avec les systèmes de messages synchrones uniquement: D'après mon expérience avec les systèmes de messages synchrones, l'un des cas les plus fréquents d'erreurs et de problèmes en général est le changement de listes lors de l'itération sur ces listes.

Pensez-y: c'est dans la nature du système synchrone (gérer immédiatement toutes les séquelles d'une action) et du système de messages (découpler le récepteur de l'expéditeur pour que l'expéditeur ne sache pas qui réagit aux actions) que vous ne pourrez pas facilement repérer de telles boucles. Ce que je dis, c'est: soyez prêt à gérer beaucoup ce type d'itération auto-modifiable. Son genre "par conception". ;-)

comment puis-je empêcher le système de collision d'être interrompu pendant qu'il vérifie les collisions?

Pour votre problème particulier avec la détection de collision, il peut être suffisant de rendre les événements de collision asynchrones, afin qu'ils soient mis en file d'attente jusqu'à ce que le gestionnaire de collision soit terminé et exécuté en un seul lot par la suite (ou à un moment ultérieur dans le cadre). Il s'agit de votre solution "file d'attente entrante".

Le problème: si un système A ajoute un message à la file d'attente B du système, cela fonctionne bien si le système B est destiné à être mis à jour plus tard que le système A (dans le même cadre de jeu); sinon, le message est traité dans la trame de jeu suivante (non souhaitable pour certains systèmes)

Facile:

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

Exécutez simplement la file d'attente encore et encore jusqu'à ce qu'il ne reste plus de message. (Si vous criez "boucle sans fin" maintenant, n'oubliez pas que vous auriez très probablement ce problème en tant que "spamming de message" s'il était retardé à la trame suivante. Vous pouvez affirmer () pour un nombre raisonnable d'itérations pour détecter les boucles sans fin, Si vous vous sentez comme ça ;))

Imi
la source
Notez que je ne parle pas exactement de "quand" les messages asynchrones sont traités. À mon avis, c'est parfaitement bien pour permettre au module de détection de collision de vider ses messages une fois qu'il a terminé. Vous pouvez également considérer cela comme des "messages synchrones, retardés jusqu'à la fin de la boucle" ou une façon astucieuse de "simplement implémenter l'itération de manière à ce qu'elle puisse être modifiée pendant l'itération"
Imi
5

Si vous essayez réellement d'utiliser la nature de conception orientée données d'ECS, vous voudrez peut-être réfléchir à la façon la plus DOD de le faire.

Jetez un œil au blog BitSquid , en particulier la partie sur les événements. Un système qui cadre bien avec ECS est présenté. Mettez en mémoire tampon tous les événements dans une belle file d'attente propre par type de message, de la même manière que les systèmes dans un ECS sont par composant. Les systèmes mis à jour ultérieurement peuvent parcourir efficacement la file d'attente pour un type de message particulier afin de les traiter. Ou tout simplement les ignorer. Peu importe.

Par exemple, le CollisionSystem générerait un tampon plein d'événements de collision. Tout autre système exécuté après une collision peut alors parcourir la liste et les traiter selon les besoins.

Il conserve la nature parallèle orientée données de la conception ECS sans toute la complexité de l'enregistrement des messages ou similaires. Seuls les systèmes qui se soucient réellement d'un type d'événement particulier parcourent la file d'attente pour ce type, et effectuer une itération directe en un seul passage sur la file d'attente de messages est à peu près aussi efficace que possible.

Si vous gardez les composants ordonnés de manière cohérente dans chaque système (par exemple, commandez tous les composants par identifiant d'entité ou quelque chose comme ça), vous obtenez même l'avantage de générer des messages dans l'ordre le plus efficace pour les parcourir et rechercher les composants correspondants dans le système de traitement. Autrement dit, si vous avez les entités 1, 2 et 3, les messages sont générés dans cet ordre et les recherches de composants effectuées pendant le traitement du message seront dans un ordre d'adresse strictement croissant (qui est le plus rapide).

Sean Middleditch
la source
1
+1, mais je ne peux pas croire que cette approche ne présente aucun inconvénient. Cela ne nous oblige-t-il pas à coder en dur les interdépendances entre les systèmes? Ou peut-être que ces interdépendances sont censées être codées en dur, d'une manière ou d'une autre?
Patryk Czachurski
2
@Daedalus: si la logique du jeu a besoin de mises à jour physiques pour faire la bonne logique, comment ne vas- tu pas avoir cette dépendance? Même avec un modèle pubsub, vous devez vous abonner explicitement à tel ou tel type de message qui n'est généré que par un autre système. Éviter les dépendances est difficile et consiste principalement à trouver les bonnes couches. Les graphiques et la physique sont indépendants, par exemple, mais il y aura une couche de colle de niveau supérieur qui garantira que les mises à jour de simulation physique interpolées seront reflétées dans les graphiques, etc.
Sean Middleditch
Ce devrait être la réponse acceptée. Une façon simple de procéder consiste à créer simplement un nouveau type de composant, par exemple le CollisionResolvable, qui sera traité par tous les systèmes intéressés à faire les choses après une collision. Ce qui cadrerait bien avec la proposition de Drake, mais il existe un système pour chaque boucle de subdivision.
user8363