QuadTree pour la détection de collision 2D

Je suis actuellement en train de travailler sur un shoot them up 2D type de jeu, et je suis à l'aide d'un quad arbre pour mon détections de collision. J'ai écrit un travail de quad arbre qui pousse correctement mes acteurs dans les nœuds/feuilles auquel ils appartiennent dans l'arbre. Cependant, j'ai quelques problèmes.

Tout d'abord, comment j'utilise mon quadtree pour sélectionner l'encontre de laquelle d'autres objets d'un objet doit tester les collisions ? Je ne suis pas sûr de savoir comment ce est fait.

Ce qui nous amène à une deuxième question. Dire que j'ai un objet dans le nœud qui n'est pas un voisin d'un autre nœud, mais que l'objet est assez grande qu'il s'étend sur un peu de nœud, comment puis-je vérifier pour une collision, car j'imagine que l'arbre peut considérer qu'elle est pas assez près pour entrer en collision avec des objets dans une "loin" nœud? Devrait objets qui ne sont pas complètement adaptée à un nœud être conservés dans le nœud parent?

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

J'ai lu un bon nombre de blogs/articles sur les quadtrees, mais plus juste d'expliquer comment construire un arbre qui n'est pas vraiment ce que je cherche.

Toute aide/info est la bienvenue.

source d'informationauteur dotminic

  1. 15

    Vous pouvez établir une convention qui chaque élément est contenu dans le plus petit quadtree nœud qui contient entièrement.

    Puis lorsque vous vérifiez les collisions pour Un nœud, vous procédez comme ceci:

    1. actuel node = nœud racine
    2. vérifier les collisions de Un avec chaque élément directement dans le nœud actuel
    3. si l'Un peut être contenue entièrement dans l'une quelconque des sous-nœuds de l'actuel nœud, nœud pour que le sous-nœud et aller de 2 à nouveau
    4. enfin, vérifier les collisions de tous les éléments dans les noeuds enfants du noeud courant, de manière récursive.

    Remarque que plus les objets, le plus profond, ils se trouvent dans le quad de l'arbre, d'où ils seront comparés moins souvent.