QuadTree pour la détection de collision 2D

Je travaille actuellement sur un type de jeu en 2D, et j’utilise un arbre quadruple pour mes détections de collision. J’ai écrit un quad arbre qui pousse correctement mes acteurs dans les nœuds / feuilles auxquels ils appartiennent dans l’arbre. Cependant, j’ai quelques problèmes.

Premièrement, comment puis-je utiliser mon quadtree pour sélectionner les autres objects sur lesquels un object doit tester les collisions? Je ne sais pas comment cela se fait.

Ce qui soulève une deuxième question. Disons que j’ai un object dans le noeud qui n’est pas voisin d’un autre noeud, mais que l’object est suffisamment grand pour couvrir un noeud, comment puis-je vérifier une collision réelle, car je suppose que l’arbre pourrait considérer qu’il ne l’est pas suffisamment proche pour entrer en collision avec des objects dans un nœud “éloigné”? Les objects qui ne rentrent pas complètement dans un nœud doivent-ils être conservés dans le nœud parent?

Dans mon jeu, la plupart des objects sont de tailles différentes et se déplacent.

J’ai lu un bon nombre de blogs / articles sur les arbres à quatre twigs, mais la plupart expliquent simplement comment construire un arbre qui n’est pas vraiment ce que je cherche.

Toute aide / information est la bienvenue.

Vous pouvez établir une convention selon laquelle chaque élément est contenu dans le plus petit nœud sur quatre arbres qui le contient complètement .

Ensuite, lorsque vous vérifiez les collisions pour le noeud A, procédez comme suit:

  1. noeud actuel = noeud racine
  2. vérifier les collisions de A avec chaque élément directement dans le nœud actuel
  3. si A peut être entièrement contenu dans l’un des sous-nœuds du nœud actuel, définissez le nœud actuel sur ce sous-nœud et passez à nouveau à 2
  4. Enfin, vérifiez de manière récursive les collisions de A avec tous les éléments des nœuds enfants du nœud actuel.

Notez que plus les objects sont petits, plus ils seront profonds dans l’arbre quadrilatère et, par conséquent, ils seront comparés moins souvent.