La gestion des collisions est un sujet intéressent car c’est une partie logique du code qui peut vite mal finir et ruiner les performances d’un jeu. Si vous développez un jeu avec peu d’élément mobiles à l’écran ça ne posera pas de problème mais dés que vous aurez beaucoup de choses mobiles à afficher il faudra penser à mettre en place des optimisations afin d’économiser les ressources pour les redistribuer ailleurs.
Voilà par exemple un test de collision basique, qui fonctionne bien mais qui n’est pas optimisé
foreach (Sprite monstre in monstreCollection)
{
if (joueur.Rectangle.Intersects(monstre))
joueur.Position = joueur.LastPosition;
}
Ici on fait un test sur toute une collection et si un élément de la collection entre en collision avec le joueur alors ce dernier récupère sa dernière position (la position avant la collision) et on simule une collision avec son arrêt. Comme je l’ai indiqué ça fonctionne bien mais imaginez que votre joueur soit en bas de la scène et que tous les objets avec lesquels il peut entrer en collision soient au dessus de la scène, il serait dommage de faire des tests pour rien car on sait pertinemment qu’il n’y aura pas de collisions. C’est là qu’entre en jeu le partitionnement de l’espace, cela va nous permettre de faire nos tests un peu plus finement en testant uniquement les objets qui sont susceptibles d’entrer en collision avec le joueur.
Dans cette optique j’ai implémenté dans le moteur que je développe, Yna Engine, une structure de donnée QuadTree qui permet d’alléger ses tests de collision et ainsi de gagner un peu plus en performance. Attention cependant car cette technique est quand même un peu lourde et elle n’est à utiliser que sur des scènes avec beaucoup d’objets. De même le QuadTree n’est pas la solution de partitionnement la plus optimisée car on peut arriver rapidement à un arbre complètement déséquilibré mais je ne vais pas entrer des les détails ici, si le sujet vous passionne je vous recommande ce très bon tutoriel qui explique très simplement quelques méthodes de détection de collision dans un jeu 2D ou 3D.
YnQuadTree
L’objet YnQuadTree est très facile à utiliser, il faudra lui fournir essentiellement deux choses
- Une collection d’objet à tester qui doivent implémenter l’interface ICollidable2 ;
- Un ou plusieurs objet implémentant l’interface ICollidable2 à tester sur la collection précédente.
Dans un Shoot’em Up par exemple vous passerez en premier une collection de laser et en second le vaisseau du joueur.
quadTree = new YnQuadTree(0, new Rectangle(0, 0, YnG.Width, YnG.Height)); quadTree.MaxObjectsPerNode = 10; quadTree.MaxLevels = 5;
La création d’un objet de type YnQuadTree est très simple, on commence par définir un niveau de départ qui est 0 et un rectangle qui représente la taille de la scène. Le nombre maximum de niveaux ainsi que le nombre maximum d’objet par nœud peut être réglé avec les propriétés MaxObjectsPerNode et MaxLevels. Typiquement la scène est un rectangle qui va être découpé en 4 rectangles (qu’on appellera noeuds) qui eux même au besoin pourrons être découpés en 4 rectangles, etc. le nombre de niveau maximum défini le nombre de découpage que l’algorithme autorise. Le nombre d’objets par nœud indique combien d’objet maximum un nœud peut contenir avant d’être découpé.
public override void Update(GameTime gameTime)
{
base.Update(gameTime);
// Suppression des objets du QuadTree et Mise à jour
quadTree.Begin(spriteToCollide.ToArray());
// De la logique comme des déplacements par exemple
someUpdateLogic();
// On utilise l'objet QuadTree pour récupérer
// les objets proches du jouer
// Une fonction de callback est utilisée et
// possède comme paramètre
// mSprite qui est le sprite du joueur
// lSprite qui est un sprite de la collection
// qui est proche du joueur
quadTree.Test(heroSprite, (mSprite, lSprite) =>
{
// Et le test final !
if (heroSprite.Rectangle.Intersects(lSprite.Rectangle))
heroSprite.Position = heroSprite.LastPosition;
});
}
Dans la boucle de mise à jour de la logique Update(GameTime gameTime) on va commencer par supprimer le contenu du QuadTree et le remplir avec les objets à tester car leur positions peut avoir changé. Ensuite on fait ce qu’on a à faire dans cette méthode et enfin, à la fin on réalise les tests de collisions dans une fonction callback que j’ai illustré ici avec une notation fonctionnelle. La méthode Test renvoie un booléen qui vaut true si un candidat a été trouvé sinon faux.
L’implémentation du QuadTree dans Yna est assez souple et demande juste des objets implémentant l’interface ICollidable2 pour travailler. Ainsi vous pouvez parfaitement utiliser YnQuadTree dans un monde en 3D où les objets n’évoluent pas sur l’axe Y.
Vous pourrez profiter de cette nouveauté à la sortie prochaine de Yna 0.5, ça ne devrait plus tarder maintenant. Sur ce codez bien !