Avant de savoir comment tester la collision entre deux objets (ce qui implique un certain nombre de calculs), peut être serait-il bon de connaître quels sont les objets à prendre en considération. En effet, si n objets (des tuiles par exemple) sont présents dans le monde, il faudrait faire O(n²) tests de collision par frame.
Le but de cette phase est donc de déterminer rapidement les paires d'objets qui pourraient entrer en collision. Qui dit rapidement, dit approximativement, nous n'avons pas besoin de le savoir de manière absolue, c'est le boulot de la phase suivante (collisions de proximité - narrow phase).
Recherche de proximité (broad phase)
Pour un faible nombre d'objets (inférieur à 5) il est possible de travailler avec hitTest() pour tester les cadres de délimitation des occurrences. Si hitTest() renvoie true, nous savons alors que les enveloppes des deux objets se recouvrent et nous pouvons donc passer à des tests plus complets pour savoir si effectivement les deux objets entrent en collision.
Par contre, pour un nombre plus important d'objets, nous avons besoin d'un moyen plus sophistiqué de déterminer si les objets sont proches les uns des autres. Une des méthodes les plus répandues est l'utilisation d'une grille pour partitionner l'espace (spatial database). Cette grille doit supporter :
la mise à jour (déplacement d'un objet)
la recherche de voisinage (déterminer rapidement si les cases voisines contiennent un objet)
Il existe plusieurs façons de découper l'espace qui sont représentées au niveau données par des tableaux ou par des arbres. Il faut savoir qu'en Flash l'utilisation des tableaux montre de meilleurs performances.
Subdivisions de l'espace
Un des problèmes de l'approche par décomposition de l'espace en une grille est que tous les objets dynamiques (comprendre : qui se déplacent) doivent être plus petit qu'une case de la grille (il est tout à fait possible de décomposé un objet en plusieurs plus petits). Pour simplifier le raisonnement, nous prendrons ici le cas d'un seul objet dynamique dans un monde composé de tuiles (tile-based).
Grille de tuiles basiques
L'utilité première de la grille est de stocker les tuiles qui définissent les parties solides du monde et la grille en elle-même est simplement un tableau 2D dont chaque entrée est un objet case. La première chose que l'on souhaite donc pouvoir faire c'est d'avoir la possibilité de déterminer quelle cellule contient le centre de notre objet. Rien de plus simple :
ligne = Math.floor(position.y / hauteur_cellule); colonne = Math.floor(position.x / largeur_cellule);
Etant donné que nous avons forcé la taille de l'objet à être inférieure à la taille d'une case, nous savons que cet objet ne peut chevaucher que quatre cases au maximum.
Objet et cellules
On peut donc supposer sans trop s'avancer que l'objet peut au plus chevaucher : la cellule courante, la cellule voisine horizontalement, la cellule voisine verticalement et la cellule en diagonale (voisine elle-même des cellules horizontale et verticale). La détermination de ces cellules peut se faire de plusieurs façons :
en faisant simplement les quatre calculs pour les quatre coins de l'objet
en faisant un seul calcul pour le centre de l'objet pour déterminer l'index dans le tableau 2D de la cellule contenant le centre et ensuite en procédant par décalage depuis cet index en se basant sur la position relative de l'objet par rapport à cette cellule (en plus clair : si, par exemple, le centre de l'objet est en bas à droite de la cellule courante [i][j], nous savons que nous devons regarder les cellules voisines : basse [i][j+1], droite [i+1][j] et diagonale basse-droite [i+1][j+1]).
Si une partie de l'objet sort des limites de la scène, les méthodes précédentes peuvent générer des index de cellules qui n'existent pas. On peut éviter ça en utilisant des valeurs min/max pour garder les indices dans les limites de la grille ou en utilisant le modulo pour déplacer l'index fautif de l'autre côté de la grille. Une méthode encore plus simple consiste à entourer la grille avec des cellules "bordure" qui peuvent être occupées par des objets statiques qui empêcheraient les autres de sortir des limites de la grille.
Maintenant que nous connaissons les quatre cellules touchées par notre objet dynamique, nous avons besoin de tester la collision avec les tuiles contenues par ces cellules (la méthode pour faire ce test est décrite dans la prochaine section Les collisions de proximité (narrow phase)). Chaque case de notre grille contient donc des informations relatives à la tuile contenue dans cette cellule, ces informations incluent un flag indiquant la forme de la tuile ainsi que toutes les informations nécessaires à la routine de détection de collision (largeur, hauteur, position du centre, etc...). Pour implémenter cette méthode, on peut définir une collection d'objets tuiles de différentes formes, chaque type de tuile étant alors chargée de générer le résultat du test de collision avec l'objet dynamique :
tuile.CollisionAvecCercle(monCercle);
Une autre méthode consiste à utiliser une table de hachage 2D contenant des fonctions de détection de collisions spécifiques à des couples de formes. Les flags de forme sont alors utilisés comme des clefs de hachages pour retrouver la bonne fonction :
L'idée précédente d'un tableau 2D contenant des tuiles sous forme d'objet peut être poussée un peu plus loin. On peut en effet envisager de stocker dans chaque cellule une référence directe aux quatre cellules voisines. De cette manière, une fois déterminée la cellule qui contient le centre de l'objet, il est possible d'accéder très facilement aux voisines. Certes cette méthode technique utilise plus de mémoire mais elle permet de faire l'économie de quelques calculs. Cette économie de calculs étant pratiquement négligeable, le principal bénéfice est une facilité et une clarté de développement :
cellule.vD; //désignera par exemple la case voisine à droite cellule.vG; //à gauche cellule.vH; //en haut cellule.vB; //en bas
Une autre amélioration que l'on peut apporter à notre grille est de stocker des informations concernant la cellule elle-même mais aussi concernant ses quatre propres bordures. Les données stockées doivent rester minime, par exemple un flag déterminant l'état de la bordure :
vide : aucune des cellules qui partagent cette bordure ne contient une tuile solide
solide : la forme de la tuile fait qu'un de ses côtés s'adapte parfaitement à la bordure courante
intéressante : les bordures adjacentes à une cellule contenant une tuile solide, mais qui ne s'adapte pas parfaitement à cette tuile sont marquées comme intéressantes, ce qui indique que des tests de collisions plus poussés doivent être effectués.
Bordures d'une tuile
Une fois que chaque tuile a reçu les états de ses bordures, on peut simplifier les futurs calculs en comparant les états des bordures des tuiles voisines, ainsi chaque bordure dont les deux tuiles adjacentes ont des bordures solides doit être considérée comme vide. Une telle simplification ne fausse pas les résultats tests de collisions car les objets dynamiques ne sont sensés percuter que la surface du monde hors la configuration citée précédemment ne peut arriver que sous la surface...
Cette structure permet de supprimer les calculs spécifiques à la forme de la tuile, si un objet croise une bordure solide, il suffit de le projeter sur cette bordure plutôt que d'avoir recours à des tests plus complexes. Les seules fois où nous devrons effectivement effectuer ces tests complexes seront lorsqu'un objet touchera une bordure dites intéressante.
Grille d'objets
Les chapitres précédents considéraient principalement la recherche de proximité mettant en jeu un objet dynamique et le monde dans lequel il évolue. Quand est-il de la détection objet/objet ?
Tout comme la structure précédente contenait des informations sur la tuile de la cellule, cette structure peut aussi rassembler des données concernant chaque objet dynamique actuellement contenu dans la cellule. Chaque cellule contient donc une liste d'objet dynamique et alors que les objets bouge, ils sont insérés ou supprimés de la liste des cellules concernées. Une grille étant simplement une structure de données, plusieurs approches sont possibles et les deux plus courantes sont les suivantes :
la grille régulière : chaque objet est associé a toutes les cellules qu'il touche (entre une et quatre dans notre cas) et lorsqu'il se déplace, il est supprimé des cellules qu'il touchait et inséré dans les nouvelles cellules qu'il recouvre à présent. Le test de proximité se fait alors seulement sur les cellules qu'il touche.
la grille lâche : chaque objet est placé dans une unique cellule qui contient son centre, lorsqu'il se déplace, il est supprimé de cette unique cellule et inséré dans la nouvelle qui contient sa nouvelle position. Pour le test de proximité nous devons alors prendre en plus en considération la totalité des huit cellules qui entoure la position de l'objet.
Types de grilles
Le choix du type de la grille dépendra vraiment du type de jeu, il faut juste savoir que la grille régulière permet de faire moins de tests de proximité mais sa mise à jour est plus longue et inversement pour la grille lâche. Il faut aussi garder à l'esprit que les performances d'un jeu sont directement reliées aux règles qui le régissent. Prenons l'exemple de missiles, si vous décidez qu'ils ne pourront pas entrer en contact les uns avec les autres, vous aurez simplement à leur faire lire la grille pour savoir si ils entrent en contact avec un objet ou une tuile sans avoir à la mettre à jour. Vous imaginez le gain de calculs ?
