Bonjour

Je voudrais savoir comment gérer les collisions dans un jeu ? Pour l'instant je bosse un peu la librairie libgdx, je fais un casse brique pour m’entraîner mais je ne trouve pas "la" réponse à ma question

J'ai une liste de briques dans un casse brique donc je pourrais regarder à chaque frame si la balle touche une brique mais ça ne me parait pas très optimisé non ? Libgdx propose t-il une méthode plus optimisé (ex: qui regarderait juste si ma balle traverse un objet ?)

Parce que dans un jeu plus conséquent comme mario, faudrait vérifier à chaque instant tous les éléments de la map ? Et pour la 3D se serait encore plus lourd ?

Pour une casse brique tu considère ta balle un carré et tu vérifies si les deux boites se touchent. Pour les gros levels, la map est splitée

Pour gagner en temps de calcul tu peux filtrer les briques à tester. Ça sert à rien de tester une brique qui est loin de la balle puisque tu sais qu'à partir de telle distance il ne peux y avoir collision. Éventuellement tu peux retirer de la liste aussi les briques totalement entourées par d'autres briques.

Dans l'idée globale, oui il faut tester les collisions entre tous les éléments (ici la balle et toutes les briques).

Dans les jeux on procède a des simplifications pour tester le moins de collisions possibles.

Quelques techniques :

- On divise l'espace en zones, ainsi on ne teste que les éléments dans une zone précises (exemple un bsp)

- On utilise une formule très grossière pour eliminer les collisions impossibles (ex distance entre deux éléments)

- On utilise une forme simplifiée qui represente un objet plus complexe (une capsule pour representer un personnage par exemple)

Pour un casse brique, la balle peut en effet être representée par un carrée.

Un autre problème des collision est la gestion des deplacements. Dans un casse brique, la balle se deplace a une vitesse determinée et pour chaque image, la balle a parcouru xx pixels (par exemple 18 pixels). Si entre les deux position, tu as traversé une brique, tu va rater le teste de collision (tu risque aussi de rater le bon coté, et de collisionner sur l'interieur de la brique par exemple). Il faut donc faire un test tout le long du deplacement et pas juste a la position de depart et d'arrivée.

"Il faut donc faire un test tout le long du deplacement et pas juste a la position de depart et d'arrivée"

Dans la théorie, c'est vrai, mais dans la pratique tester simplement départ et arrivée ne pose pas de problème la plupart du temps, surtout quand les mouvements ne sont pas trop rapides. Sinon, si ça va vraiment vite, on peut faire genre 3 ou 4 tests successifs en divisant le déplacement à chaque fois pour réduire l'erreur (par exemple, au lieu de bouger de 12 pixels puis de test, on bouge de 3 pixels puis on teste le tout 4 fois).

En tout cas je sais que dans mon Terraria la totalité des collisions ne sont testées qu'une fois par frame (sauf les particules de pluie, 300 fois par seconde minimum donc 5 fois par frame en 60 FPS), et à moins de limiter à 60 FPS + ajouter le cheat de boost de vitesse + accélérer le temps, le tout pour passer à travers un mur de 1 bloc d'épaisseur, y'a quasiment aucun problème de collisions.

J'avais aussi fait un mini casse brique toujours avec cette méthode, et 1 test par frame suffisait largement à son fonctionnement.

On peut aussi utiliser un test dit d'intersection / "sweep test", qui tient compte du mouvement des agents , mais forcément, les formules sont un peu plus compliquées...

Ouais mais bon, je vois pas l'intérêt d'utiliser un test plus compliqué et plus lourd pour le processeur si en pratique il n'apporte aucune amélioration...

Le meilleur moyen est de faire un quadtree (la solution n1 de Lapintade). En plus de cela, tu rajoute un détection de collision boite-boite (un carre entoure ta balle et chaque bloc possède une boite). Tu vérifie deux cas de figure :

-Tu touche une boite
-Tu es dans une boite (tu as manqué la collision)

Et tu replace la balle au niveau de la collision pour une bonne gestion.

Ensuite, tu augmente le nombre de vérification de collision si possible dans le cas ou la balle est très rapide. Je te laisse googler tout ça, il y a beaucoup d'article dessus.

Voila, bonne chance.

"Le meilleur moyen est de faire un quadtree"
Encore une fois, on est dans un casse brique là... Imaginons qu'il y ait 10 000 briques (peu probable), la partie collisions prendrait un temps vraiment négligeable même en les testant toutes.

Et d'ailleurs y'a un moyen plus simple et plus optimisé: tu crée un tableau 2D qui te sers de grille, contenant chaque bloc à l'index correspondant à ses coordonnées (genre blocs[0][0] est en bas à droite, blocs[0][1] est juste au dessus etc.).

Ensuite tu get la position de deux coins opposés de la balle , tu les convertis en coordonnées de blocs (en utilisant la hauteur/largeur des blocs et la position de celui en [0][0] pour la conversion) en les mettant dans des variables int minx, maxx, miny, maxy, puis tu parcours avec un for(i = minx à maxx) dans un for(j = miny à maxy) et tu test les collisions uniquement des blocs de coord [i][j] avec la balle.

T'auras toujours les mêmes performances, qu'il y ait 2 blocs ou 2 000 000, contrairement au quadtree qui est d'ailleurs plus adapté à des situations ou on ne peut pas se servir de grille à moins que je dise des conneries.

C'est peut être pas très bien expliqué, mais de toutes façons ça sers à rien d'utiliser un tel système sur un casse brique, c'est pas comme si y'avait 10 millions de blocs à gérer...

Simple suggestion, tu pourrais faire un système de collision par couleur. Par exemple si le pixel sur lequel tu passe est rouge, il y a collision.

Bonjour, pourquoi ne pas récupérer la position de la balle avant chaque déplacement et faire un test sur ton vecteur de déplacement.
Si le test est vrai dans ce cas la on calcul la distance entre balle et la brique trouvée, ce qui nous donne notre nouveau déplacement suivi de la collision.

K, merci je vais me renseigner