QuadTree pour la détection des collisions 2D

je travaille actuellement sur un 2D shoot them up type de jeu, et j'utilise un arbre quad pour mes détections de collision. J'ai écrit un arbre quadrilatéral qui pousse correctement mes acteurs dans les noeuds/feuilles auxquels ils appartiennent dans l'arbre. Cependant, j'ai quelques problèmes.

tout d'abord, comment puis-je réellement utiliser mon quadtree pour sélectionner par rapport à quels autres objets un objet devrait tester les collisions ? Je ne suis pas sûr de savoir comment ce est fait.

qui évoque un la deuxième question. Disons que j'ai un objet dans le noeud qui n'est pas un voisin d'un autre noeud, mais que l'objet est assez grand pour s'étendre sur quelques noeuds, Comment puis-je vérifier une collision réelle, puisque je devine que l'arbre pourrait considérer qu'il n'est pas assez proche pour entrer en collision avec des objets dans un noeud "lointain"? Les objets qui ne correspondent pas complètement à un noeud devraient-ils être conservés dans le noeud parent?

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

j'ai lu un bon nombre de blogs/articles sur quadtrees, mais la plupart expliquent simplement comment construire un arbre qui n'est pas vraiment ce que je cherche.

toute aide/information est la bienvenue.

15
demandé sur Smi 2010-12-14 01:59:49

1 réponses

vous pouvez établir une convention que chaque élément est contenu dans le plus petit noeud quadtree qui le contient entièrement .

puis quand vous vérifiez les collisions pour le noeud A, vous procédez comme ceci:

  1. noeud courant = noeud racine
  2. vérifier les collisions de Un avec chaque élément directement dans le nœud actuel
  3. si A peut être contenu entièrement dans l'un des sous-noeuds de la noeud courant, régler le noeud courant à ce sous-noeud et passer à 2 de nouveau
  4. enfin, vérifiez les collisions de A avec tous les éléments dans les noeuds enfants du noeud courant, de façon récursive.

notez que plus les objets sont petits, plus ils seront localisés dans l'arbre quadruple, donc ils seront comparés moins souvent.

15
répondu Kos 2010-12-13 23:17:12