La façon dont je le fais implique le stockage d'un indice de retour à la entité du composant (32 bits). Il ajoute un peu de surcharge mémoire mais le temps de mémoire total d'un composant dans le mien est d'environ 8 octets, ce qui n'est généralement pas trop mauvais pour mes cas d'utilisation, et d'environ 4 octets par entité. Maintenant, quand vous avez un index retour à une entité, ce que vous pouvez faire en répondant à une requête pour toutes les entités qui ont 2 types de composants ou plus est d'utiliser des ensembles de bits parallèles. Par exemple, si vous recherchez des entités avec deux types de composants, Motion
et Sprite
, nous commençons par parcourir les composants de mouvement et définir les bits associés pour les entités qui en sont propriétaires.
Ensuite, nous parcourons les composants de l'image-objet et recherchons les bits d'entité déjà définis par les composants de mouvement. Si l'index d'entité apparaît à la fois dans les composants de mouvement et les composants d'image-objet, nous ajoutons l'entité à la liste des entités qui contiennent les deux.Un schéma de l'idée, ainsi que la façon de multithread et mutualiser les entités parallèles des réseaux de bits:
Cela vous donne une intersection de jeu dans le temps linéaire et avec une très petite m
(très, très pas cher travailler par itération car nous ne faisons que marquer et inspecter un peu - beaucoup, beaucoup, beaucoup moins cher qu'une table de hachage, par exemple). Je peux réellement effectuer une intersection entre deux ensembles avec 100 millions d'éléments chacun en moins d'une seconde en utilisant cette technique. En prime, avec un petit effort, vous pouvez le faire revenir dans l'ordre des entités pour des modèles d'accès faciles à mettre en cache si vous utilisez le bitset pour saisir les indices des entités qui appartiennent à 2 composants ou plus. Il y a des façons de le faire dans un temps meilleur que le temps linéaire (Log(N)/Log(64)
) bien qu'il soit considérablement plus impliqué où vous pouvez réellement effectuer une intersection définie entre deux ensembles contenant 100 millions d'éléments chacun en moins d'une milliseconde. Voici un indice:
J'ai déjà ce qui est essentiellement une enveloppe autour d'un 'std :: unordered_map' qui ajoute, supprime et récupère les composants de cette carte (et les entités sont ids dans la carte), de sorte que vous suggérez serait juste de changer un type de données et quelques fonctions. Parfait! – Freaxy