Comment les systèmes d'entités sont-ils efficaces en cache?

Dernièrement, j'ai beaucoup lu sur les systèmes d'entités à implémenter dans mon moteur de jeu C ++ / OpenGL. Les deux avantages clés que j’entends constamment louer au sujet des systèmes d’entités sont:

1. la construction facile de nouveaux types d'entités, du fait de ne pas avoir à s'embrouiller avec des hiérarchies complexes d'héritage, et
2. l'efficacité du cache, que j'ai du mal à comprendre.

La théorie est simple, bien sûr; chaque composant est stocké de manière contiguë dans un bloc de mémoire, de sorte que le système concerné par ce composant ne peut que parcourir l'ensemble de la liste, sans avoir à sauter en mémoire et à tuer le cache. Le problème est que je ne peux pas vraiment penser à une situation où cela est réellement pratique.

Tout d’abord, voyons comment les composants sont stockés et comment ils se référencent les uns les autres. Les systèmes doivent pouvoir utiliser plusieurs composants, c'est-à-dire que les systèmes de rendu et de physique doivent accéder au composant de transformation. J'ai vu un certain nombre d'implémentations possibles résoudre ce problème, mais aucune ne le fait bien.

Vous pouvez demander aux composants de stocker des pointeurs sur d'autres composants ou des entités vers des entités stockant des pointeurs sur des composants. Cependant, dès que vous ajoutez des pointeurs à la composition, vous tuez déjà l'efficacité du cache. Vous pouvez vous assurer que chaque tableau de composants est "n" de grande taille, où "n" est le nombre d'entités actives dans le système, mais cette approche gaspille énormément de mémoire. il est donc très difficile d’ajouter de nouveaux types de composants au moteur, tout en maintenant l’efficacité du cache, car vous passez d’une matrice à l’autre. Vous pouvez entrelacer votre tableau d'entités au lieu de garder des tableaux séparés, mais vous perdez toujours de la mémoire. l'ajout de nouveaux composants ou systèmes est extrêmement coûteux, mais offre désormais l'avantage d'invalider tous vos anciens niveaux et de sauvegarder des fichiers.

Tout cela en supposant que les entités sont traitées linéairement dans une liste, chaque image ou coche. En réalité, ce n'est pas souvent le cas. Supposons que vous utilisiez un moteur de rendu secteur / portail, ou un octree, pour effectuer la suppression des occultations. Vous pourrez peut-être stocker des entités de manière contiguë dans un secteur / nœud, mais vous allez sauter, que cela vous plaise ou non. Ensuite, vous avez d'autres systèmes, qui pourraient préférer des entités stockées dans un autre ordre. L'IA pourrait accepter de stocker des entités dans une grande liste jusqu'à ce que vous commenciez à travailler avec AI LOD; ensuite, vous voudrez diviser cette liste en fonction de la distance qui le sépare du joueur ou d'une autre métrique de niveau de détail. La physique va vouloir utiliser cet octree. Les scripts ne s’inquiètent pas, ils ont besoin de courir, quoi qu’il en soit.

Je pouvais voir des composants se séparer entre "logique" (par exemple, ai, scripts, etc.) et "monde" (par exemple, rendu, physique, audio, etc.) et gérer chaque liste séparément, mais ces listes doivent toujours interagir. L'intelligence artificielle est inutile si elle ne peut pas affecter l'état de transformation ou d'animation utilisé pour le rendu d'une entité.

Comment les systèmes d'entités sont-ils "efficaces en cache" dans un moteur de jeu réel? Peut-être y a-t-il une approche hybride que tout le monde utilise, mais ne parle pas, comme stocker des entités dans un tableau globalement et le référencer dans l'octree?

Les deux principaux avantages dont je me félicite constamment à propos des systèmes d'entité sont 1) la construction facile de nouveaux types d'entités en raison de l'absence de mélange avec les hiérarchies d'héritage complexes et 2) l'efficacité du cache.

Notez que (1) est un avantage de la conception à base de composants , pas seulement ES / ECS. Vous pouvez utiliser des composants de nombreuses manières sans la partie "systèmes" et ils fonctionnent parfaitement (et de nombreux jeux indépendants et AAA utilisent de telles architectures).

Le modèle d'objet Unity standard (using GameObjectet MonoBehaviourobjects) n'est pas un ECS, mais une conception à base de composants. La nouvelle fonctionnalité Unity ECS est bien sûr un véritable ECS.

Les systèmes doivent pouvoir utiliser plusieurs composants, c'est-à-dire que les systèmes de rendu et de physique doivent accéder au composant de transformation.

Certains ECS trient leurs conteneurs de composants par ID d'entité, ce qui signifie que les composants correspondants de chaque groupe seront dans le même ordre.

Cela signifie que si vous parcourez linéairement le composant graphique, vous êtes également itération linéaire sur les composants de transformation correspondants. Vous pourriez être des lignes ne sont pas transformées (puisque vous pouvez avoir des volumes de déclenchement de la physique que vous ne rendent pas ou ces) mais puisque vous êtes toujours sauter en avant dans la mémoire (et par des distances énormes pas particulièrement, le plus souvent) , vous allez encore avoir des gains d'efficacité.

Ceci est similaire à la façon dont la structure de tableaux (SOA) est l'approche recommandée pour HPC. Le processeur et le cache peuvent traiter plusieurs tableaux linéaires presque aussi bien qu’un seul tableau linéaire, et bien mieux qu’un accès en mémoire aléatoire.

Une autre stratégie utilisée dans certaines mises en œuvre ECS - notamment Unity ECS - consiste à allouer des Composants en fonction du type d'archétype de leur entité correspondante. C'est, toutes les entités avec précision l'ensemble des composants ( PhysicsBody, Transform) seront attribués séparément des entités avec différents composants (par exemple PhysicsBody, Transform, et Renderable ).

Les systèmes de telles conceptions fonctionnent d'abord en recherchant tous les archétypes correspondant à leurs exigences (qui possèdent l'ensemble de composants requis), en itérant cette liste d'archétypes et en itérant les composants stockés dans chaque archétype correspondant. Cela permet un accès entièrement linéaire et réel aux composants O (1) dans un archétype et permet aux systèmes de trouver des entités compatibles avec un temps système très faible (en recherchant une petite liste d'archétypes plutôt qu'en recherchant potentiellement des centaines de milliers d'entités).

Vous pouvez demander aux composants de stocker des pointeurs sur d'autres composants ou des entités vers des entités stockant des pointeurs sur des composants.

Les composants référençant d'autres composants sur la même entité n'ont besoin de rien stocker. Pour référencer des composants sur d'autres entités, stockez simplement l'ID d'entité.

Si un composant est autorisé à exister plusieurs fois pour une seule entité et que vous devez référencer une instance particulière, stockez l'ID de l'autre entité et un index de composant pour cette entité. Cependant, de nombreuses implémentations ECS n'autorisent pas ce cas, car cela rend ces opérations moins efficaces.

Vous pouvez vous assurer que chaque tableau de composants est "n" grand, où "n" est le nombre d'entités actives dans le système.

Utilisez des poignées (par exemple, index + marqueurs de génération) et non des pointeurs. Vous pouvez ensuite redimensionner les tableaux sans craindre de casser les références aux objets.

Vous pouvez également utiliser une approche de type "tableau de blocs" (un tableau de tableaux) similaire à de nombreuses std::dequeimplémentations courantes (bien que sans la taille de bloc pitoyablement petite desdites implémentations) si vous souhaitez autoriser les pointeurs pour une raison quelconque ou si vous avez mesuré des problèmes avec tableau redimensionner les performances.

Deuxièmement, tout cela en supposant que les entités sont traitées linéairement dans une liste à chaque image / tick, mais en réalité, ce n'est pas souvent le cas.

Cela dépend de l'entité. Oui, dans de nombreux cas d'utilisation, ce n'est pas vrai. En effet, c’est la raison pour laquelle j’insiste tellement sur la différence entre la conception à base de composants (bonne) et l’ entité-système (forme spécifique de CBD).

Certains de vos composants seront certainement faciles à traiter de manière linéaire. Même dans des cas d'utilisation normalement "très chargés", nous avons clairement constaté une augmentation des performances liée à l'utilisation de tableaux très compacts (principalement dans les cas impliquant un N de quelques centaines au plus, comme des agents IA dans un jeu typique).

Certains développeurs ont également constaté que les avantages en termes de performances de l’utilisation de structures de données allouées linéairement orientées données dépassaient l’avantage en termes de performances de l’utilisation de structures arborescentes «plus intelligentes». Tout dépend du jeu et des cas d'utilisation spécifiques, bien sûr.

Supposons que vous utilisiez un moteur de rendu secteur / portail ou un octree pour effectuer la sélection d'occlusion. Vous pourrez peut-être stocker des entités de manière contiguë dans un secteur / nœud, mais vous allez sauter de partout, que cela vous plaise ou non.

Vous seriez surpris de voir à quel point le tableau aide toujours. Vous sautez dans une région de mémoire beaucoup plus petite que «n'importe où» et même avec tous les sauts, vous avez encore plus de chances de vous retrouver dans quelque chose en cache. Avec un arbre d'une certaine taille ou moins, vous pourriez même être capable de pré-extraire le tout dans le cache et ne jamais avoir un cache manquant sur cet arbre.

Il existe également des arborescences construites pour vivre dans des tableaux très compacts. Par exemple, avec votre octree, vous pouvez utiliser une structure ressemblant à un tas (parents avant les enfants, frères et sœurs côte à côte) et vous assurer que même lorsque vous "explorez" l'arbre, vous êtes toujours en train de parcourir le tableau, ce qui aide la CPU optimise les accès mémoire / les recherches en cache.

Ce qui est un point important à faire. Un processeur x86 est une bête complexe. Le processeur exécute effectivement un optimiseur de microcode sur le code de votre machine, le divisant en un microcode plus petit et des instructions de réordonnancement, prédisant les modèles d'accès à la mémoire, etc. comment fonctionne le processeur ou le cache.

Ensuite, vous avez d'autres systèmes, qui pourraient préférer des entités stockées dans un autre ordre.

Vous pouvez les stocker plusieurs fois. Une fois que vous réduisez au minimum vos tableaux, vous constaterez peut-être une économie de mémoire (puisque vous avez supprimé vos pointeurs 64 bits et que vous pouvez utiliser des index plus petits) avec cette approche.

Vous pouvez entrelacer votre tableau d'entités au lieu de garder des tableaux séparés, mais vous perdez toujours de la mémoire

Ceci est antithétique à une bonne utilisation du cache. Si vous ne vous souciez que des transformations et des données graphiques, pourquoi faire en sorte que la machine prenne du temps pour extraire toutes ces autres données pour la physique et l'IA, les entrées et les mises au point, etc.?

C’est l’argument généralement avancé en faveur d’ECS et d’objets de jeu monolithiques (même s’il n’est pas vraiment applicable lorsqu’on le compare à d’autres architectures à base de composants).

Pour ce qui en vaut la peine, la plupart des implémentations ECS de «qualité production», dont je suis au courant, utilisent le stockage entrelacé. L'approche populaire d'archétype que j'ai mentionnée précédemment (utilisée dans Unity ECS, par exemple) est très explicitement conçue pour utiliser le stockage entrelacé pour les composants associés à un archétype.

L'intelligence artificielle est inutile si elle ne peut pas affecter l'état de transformation ou d'animation utilisé pour le rendu d'une entité.

Le fait qu'AI ne puisse pas accéder efficacement aux données de transformation de manière linéaire ne signifie pas qu'aucun autre système ne peut utiliser efficacement cette optimisation de la présentation des données. Vous pouvez utiliser une matrice compacte pour transformer des données sans empêcher les systèmes de logique de jeu de faire les choses de la même manière que les systèmes de logique de jeu ad hoc.

Vous oubliez également le cache de code . Lorsque vous utilisez l'approche système d'ECS (contrairement à une architecture de composant plus naïve), vous garantissez que vous exécutez la même petite boucle de code et que vous ne sautez pas dans les tables de fonctions virtuelles vers un assortiment de commandes aléatoires.Update fonctions . votre binaire. Donc, dans le cas de l'IA, vous voulez vraiment conserver tous vos différents composants d'IA (car vous en avez certainement plusieurs pour pouvoir composer des comportements!) Dans des compartiments séparés et traiter chaque liste séparément afin d'obtenir la meilleure utilisation du cache de code.

Avec une file d'attente d'événements retardée (où un système génère une liste d'événements mais ne les envoie pas avant que le système ait fini de traiter toutes les entités), vous pouvez vous assurer que votre cache de code est bien utilisé tout en conservant les événements.

En utilisant une approche dans laquelle chaque système sait à partir de laquelle les files d’événements doivent être lues, vous pouvez même effectuer rapidement la lecture des événements. Ou plus vite que sans, du moins.

N'oubliez pas que la performance n'est pas absolue. Il n'est pas nécessaire d'éliminer chaque dernière erreur de cache pour commencer à voir les avantages d'une bonne conception orientée données pour la performance.

Des recherches sont en cours pour améliorer le fonctionnement de nombreux systèmes de jeu avec l'architecture ECS et les modèles de conception orientés données. De la même manière que certaines des choses étonnantes que nous avons vues avec SIMD ces dernières années (par exemple, des analyseurs syntaxiques JSON), nous voyons de plus en plus de choses se faire avec une architecture ECS qui ne semble pas intuitive aux architectures de jeu classiques, mais offre un certain nombre de fonctionnalités. avantages (rapidité, multi-threading, testabilité, etc.).

Ou peut-être qu'il y a une approche hybride que tout le monde utilise mais dont personne ne parle

C’est ce que j’ai préconisé dans le passé, en particulier pour les personnes sceptiques à l’égard de l’architecture ECS: utilisez de bonnes approches orientées données pour les composants dont les performances sont essentielles. Utilisez une architecture plus simple où la simplicité améliore le temps de développement. Ne cognez pas chaque composant dans une définition trop stricte de la composant, comme le propose ECS. Développez votre architecture de composants de manière à pouvoir facilement utiliser des approches de type ECS lorsqu'elles ont un sens, et une structure de composant plus simple, où une approche de type ECS n'a pas de sens (ou a moins de sens qu'une structure arborescente, etc.). .

Personnellement, je suis moi-même assez récemment converti au véritable pouvoir d’ECS. Pour moi, le facteur décisif était quelque chose de rarement mentionné dans ECS: il rend l'écriture de tests pour les systèmes de jeu et la logique presque triviale comparée aux conceptions à couplage logique, à la logique complexe, avec lesquelles j'ai travaillé par le passé. Étant donné que les architectures ECS mettent toute la logique dans les systèmes, qui ne consomment que des composants et produisent des mises à jour de composant, il est relativement facile de créer un ensemble "fictif" de composants pour tester le comportement du système. étant donné que la plupart des logiques de jeu ne doivent vivre que dans les systèmes, cela signifie que le fait de tester tous vos systèmes fournira une couverture de code relativement élevée de votre logique de jeu. Les systèmes peuvent utiliser des dépendances factices (par exemple, des interfaces de GPU) pour des tests beaucoup moins complexes ou ayant moins d’impact sur les performances que vous.

En passant, vous remarquerez peut-être que beaucoup de gens parlent d’ECS sans vraiment comprendre ce qu’il en est. Je vois le classique Unity appelé ECS avec une fréquence déprimante, illustrant que trop de développeurs de jeux assimilent "ECS" à "Composants" et ignorent quasiment la partie "Système d'entités". Vous voyez beaucoup d’amour accumulé sur ECS sur Internet quand une grande partie de la population ne fait que préconiser une conception à base de composants, et non pas une véritable ECS. À ce stade, il est presque inutile de le discuter; ECS a été corrompu par sa signification originale en un terme générique et vous pouvez aussi bien accepter que "ECS" ne signifie pas la même chose que "ECS orienté données". : /