Quadruple arbre / collision basée sur la grille - mettre la logique en action

Tout d'abord, je n'écris ma propre logique de jeu que depuis peu de temps, donc je m'excuse si cela peut sembler simple.

J'ai beaucoup lu sur les arbres quadruples et la détection de collision basée sur une grille. Je comprends la logique - fondamentalement, ne vérifie pas la collision à moins que les objets ne soient proches à la base. Mais il n'est jamais mentionné comment l'exécuter réellement.

J'ai quelques méthodes possibles dans ma tête, mais je ne sais pas laquelle est la meilleure

Test de collision général - pas d'optimisation

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

stocker les voisins (méthode 1) Mais que faire si nous voulons optimiser les collisions pour ne vérifier que les objets qui sont proches. Passons-nous toujours en revue tous les objets, ou créons-nous un tableau avec des objets proches à vérifier?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

boucle tous les objets mais vérifie seulement les voisins pour la collision (méthode 3) L'autre possibilité est que nous bouclons tout, mais vérifions si les objets sont proches avant de tester la collision.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Stocker des objets dans les données de tuiles (méthode 3) L' utilisation d'un système basé sur les tuiles permet une autre option; Stockez les objets qui se trouvent sur une tuile spécifique dans les données de tuiles elles-mêmes. Vérifiez pour voir sur quelle tuile l'objet est les tuiles environnantes contiennent tous les objets avec lesquels il pourrait entrer en collision:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

J'essaie toujours de regarder le monde réel comme exemple. Si je voulais comparer des articles de la même couleur, il semblerait illogique de vérifier chaque article entier même s'ils ne correspondent pas à la couleur (méthode 2, vérifiez chaque article). Je collecterais probablement les articles de la même couleur (objets qui sont proches les uns des autres) et les vérifierais (méthode 1), au lieu de tout vérifier.

Ce n'est pas une comparaison appropriée, car les éléments de la vérification des collisions se déplacent constamment, de sorte que la commande est mélangée. C'est ce qui me déroute.

Serait-il plus efficace de vérifier chaque élément, supprimant ainsi la contrainte de continuer à générer un tableau de voisins.

Ou est-il plus efficace de trouver des voisins sans avoir à parcourir autant d'objets pour vérifier la collision?

Continuer à changer les données sur chaque tuile semble également très intensif, donc je ne sais pas si c'est une bonne idée ..

J'ai pensé à un jeu de tower defense où la tour doit détecter des objets si des objets sont à portée avant de lui tirer dessus. Et il semble juste stupide de vérifier tous les éléments alors qu'à certains moments, il n'y aura aucun objet à proximité.

Je m'excuse pour le long post, j'ai toujours du mal à m'expliquer!

Vous devez réduire le nombre de vérifications de collision réelles. Ouais c'est évident je sais. Permet donc d'élaborer sur ce point:

Votre premier algorithme de vérification des collisions sans aucune optimisation: combien de vérifications fera-t-il en une seule fois? Si n est le nombre d'objets, ce sera autour de n * (n-1) contrôles. Pour beaucoup d'objets (> 100), ce sera horriblement lent.

La méthode de vérification de votre voisin ne sera pas beaucoup plus rapide. Si vos objets ne sont pas statiques et se déplacent beaucoup, vous devrez créer cette liste de voisins pour chaque objet à chaque fois dans votre boucle de jeu. C'est en fait pire que le premier algorithme puisque vous faites n * (n-1) pour construire la liste des voisins, puis vérifiez chaque objet s'il entre en collision avec l'un de ses voisins.

Vous devez partitionner votre espace de jeu. Disons que votre espace de jeu fait 400x400 pixels de large. Vous pouvez le partitionner en 4 sous-espaces de 200 x 200 et vérifier chaque objet dans lequel des sous-espaces il appartient (un objet peut se trouver dans plus d'un sous-espace). Vous n'aurez alors qu'à vérifier si les objets de chaque sous-espace entrent en collision avec d'autres objets du même sous-espace.

Le coût d'exécution sera donc: n pour la construction de la liste des 4 sous-espaces + (n / 4) * ((n-1) / 4), ce qui est bien meilleur que le coût d'exécution précédent. Cela peut être réduit davantage en réduisant les sous-espaces (par exemple 50x50).

Donc, notre algorithme ressemble maintenant à ceci:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Ceci est quelque peu similaire à votre idée de données de tuile. Mais les sous-espaces n'ont pas besoin d'avoir la même taille que les tuiles.

Nous pouvons faire une dernière étape pour l'optimiser davantage en utilisant un quadtree. Soit k le nombre de sous-espaces. Pour construire les listes d'objets d'espaces, nous effectuons des vérifications k * n, ce qui entraîne de nombreuses vérifications si votre monde de jeu devient grand.

Pour réduire ce coût, nous utilisons un quadtree. Un quadtree est une autre façon de partitionner notre espace de jeu. Au lieu de diviser notre espace 400x400 en 64 sous-espaces 50x50 et de vérifier pour chaque objet dans lequel des 64 sous-espaces il se trouve actuellement, l'espace de jeu est divisé en 4 sous-espaces de la moitié de la taille de l'espace de jeu (200x200), qui à leur tour sont divisés en des sous-espaces plus petits (100x100), qui à leur tour sont divisés à nouveau en sous-espaces 50x50. Ceci est notre quadtree.

Maintenant, si nous voulons savoir à quel sous-espace 50x50 appartient un objet, nous vérifions à quel sous-espace 200x200 il appartient. Ensuite, nous allons un niveau plus loin dans notre quadtree et vérifions les 4 sous-espaces 100x100 qui sont à l'intérieur du sous-espace 200x200 que nous venons de trouver. Ceci est répété jusqu'à ce que nous sachions dans quel sous-espace 50x50 appartient l'objet. Alors, combien de contrôles étaient maintenant nécessaires? 4 pour chaque niveau du quadtree (rappelez-vous qu'un objet peut être sur le bord de deux sous-espaces). Nous avons donc besoin de 4 * 3 vérifications pour affecter un objet au sous-espace 50x50 correct. Beaucoup mieux que 64 chèques.

Donc, notre algorithme quadtree a besoin de 4 * 3 * n vérifications pour construire les listes de sous-espaces, puis quelque chose comme k * (n / k) vérifie pour vérifier les collisions de chaque objet.