Les quadriphes sont utilisés lorsque vous avez uniquement besoin de stocker des objets qui se trouvent effectivement dans un plan. Comme des unités dans un RTS classique où ils sont tous sur le terrain ou juste un peu au-dessus. Essentiellement, chaque nœud a des liens vers 4 enfants qui divisent l'espace du nœud en quartiers répartis uniformément.
Les arbres font la même chose mais dans les trois dimensions plutôt que seulement deux, et ils ont donc 8 nœuds enfants et divisent l'espace en huit. Ils devraient être utilisés lorsque les entités du jeu sont réparties plus également entre les trois dimensions. Si vous cherchez un arbre binaire - comme un arbre rouge-noir - alors vous voulez utiliser une structure de données appelée un arbre de partitionnement binaire (arbre BSP) ou une version appelée l'arbre KD. Ces espaces de partition en moitiés utilisant un plan, dans l'arbre KD les plans sont orthogonaux (sur les axes XZ, XY, ZY) donc parfois cela fonctionne mieux dans une scène 3D. Les arbres BSP divisent la scène en utilisant des plans dans n'importe quelle orientation, mais ils peuvent être très utiles, et ils ont été utilisés aussi loin que Doom. Maintenant que vous avez partitionné l'espace de jeu, vous n'avez plus besoin de tester chaque entité de jeu par rapport à toutes les autres entités du jeu pour voir si elles entrent en collision, ce qui est un algorithme O (n^2). Au lieu de cela, vous interrogez la structure de données pour renvoyer les entités de jeu dans une sous-région de l'espace de jeu, et effectuez seulement la détection de collision pour ces nœuds l'un contre l'autre. Cela signifie que la détection de collision pour toutes les entités de jeu doit être une opération n O (nlogn) (au pire).
Un certain nombre de choses supplémentaires à surveiller:
- Assurez-vous de tester des entités de jeu de noeuds adjacents, non seulement ceux dans le nœud actuel, car ils pourraient encore entrer en collision.Rééquilibrer la structure de données après le déplacement des entités car vous pouvez avoir des nœuds vides dans la structure de données ou des entités contenant trop d'entités pour de bonnes performances (le cas dégénéré de toutes les entités étant également dans le même nœud).
Ceci est un peu vague. Je pense que l'implémentation de l'arborescence doit savoir quel type de données vous voulez stocker, car cela affecte les détails sur le fonctionnement de l'insertion (fractionnement, etc.). – unwind