Gérer les collisions d'un jeu 2D

a marqué ce sujet comme résolu.

Hello !

Je suis tout nouveau dans le monde du développement de jeux :) . Je fais actuellement des collisions pour un petit jeu que je développe. C’est quelque chose de ressemblant à Haxball.

Je me demandais quelle était la méthode la plus performante pour calculer des collisions: - Utiliser des calculs mathématiques ? - Utiliser un "canvas" caché composé de couleurs noir/gris et lorsqu’un gris est anormal cela veut dire qu’il s’agit d’une collision…

J’ai vu un petit article sur le sujet sur MDN et ça me semble "plus legit" que la seconde solution que j’ai proposé. La détection de collision entre cercles étant ce dont j’ai besoin (mais pas que, j’ai aussi les bordures du canvas).

Cependant, historiquement j’avais participé au développement d’un jeu (nekoro) et on avait beaucoup amélioré les performances en utilisant la seconde méthode.

J’avoue être un peu perdu. Avez vous des feedbacks à faire par rapport à cela ?

Merci d’avance :) .

+0 -0

D’un point de vue algorithmique, une structure de donnée type quad-tree ou r-tree devrait être largement suffisante avec les bons paramètres.

En revanche, si le nombre de joueur est relativement faible avoir une bonne complexité asymptotique est rarement une bonne solution. Par exemple avec du 4x4 tu te retrouves avec 9 cercles mouvants et 4 fixes (les 4 poteaux), ce qui fait sans phase large $9 \times 9 + 9 \times 4 = 117$ collisions à tester. Avec aussi peu de collisions, il est bien plus intéressant de s’assurer que toutes tes données sont au même endroit en mémoire et de faire des "micro" optimisations comme éviter le calcul d’une racine carrée plutôt que de cherche à utiliser des algorithmes plus complexes.

En revanche, plus tu as d’entités plus l’ajout d’une phase large sera importante.

+1 -0

Salut,

Le lien que tu renseignes vers MDN explique bien le principe général. La méthode par masque est clairement inférieur. Les moteurs de physique 2D / 3D utilisent tous des résolutions mathématiques.

Comme le coût de la détection des collisions est non négligeable, on sépare généralement la détection des collisions en deux phases: large et étroite.

Si tu as N entités, tu devras faire $\frac{N^2}{2}$ tests. Comme chaque test peut prendre un temps considérable, on essaie de dégrossir les paires à comparer. C’est le rôle de la phase large. Pour un premier jeu, cette phase pourrait être ignorée. Tu peux toujours l’implémenter plus tard, lorsque les performances commenceront à souffrir.

La phase étroite est simplement le test de collision même. Pour 2 cercles, 2 AABB (axis-aligned-bounding-boxes) ou cercle - AABB, c’est pas encore trop gourmand. C’est à partir du moment où tu veux faire des collisions entre des Rect non-orientés et des polygones quelconques que ça devient plus coûteux.

Il y a une troisième phase dont l’article ne parle pas vraiment. Et cette phase est non-trivial. Comment réagir à une collision? C’est le résultat est simplement la destruction d’un des deux objets, alors c’est simple. Mais s’ils doivent finir l’un à côté de l’autre, sans aucune pénétration, alors il y a aussi tout un tas de complications.

Conclusion: si tu as juste besoins de collisions entre cercles et AABB, ne te préoccupe pas de trop de la phase large. Concentre-toi juste sur la partie collision (phase étroite).

+1 -0

sinon, tiens-tu réellement à réinventer la roue plutôt que d’utiliser box2d ?

minirop

La petite remarque méchante. Bien joué, il en fallait bien une. Pour info j’ai testé plusieurs moteurs de jeux, et pour des besoins simples comme les miens, bien souvent ça complexifie pas mal. D’ailleurs c’est souvent parce que c’est super mal documenté. En outre ça n’est pas très intéressant de se casser la tête à utiliser la chose de quelqu’un d’autre pour ton projet alors qu’à moindre efforts tu peux faire ton truc perso. (qui plus est ton projet est en C alors que je parle de javascript depuis le début)

Autant de manière générale je suis pour, autant là ça me semble bien assez simple pour partir sans moteur. Mais j’avoue que du coup je ne participe pas à un projet dans le genre etc… Et bah non, une prochaine fois, sur un projet plus adapté !

Pour ce qui est des performances il est possible que j’ai besoin de gérer 11 à 13 cercles (le nombre de joueurs max plus la balle). Je n’ai pas encore expérimenté au max mais je pense que c’est ok… En tous les cas merci pour ton avis @Dan737 .

Je me demande si ce genre de choses peut être calculé par le GPU ?! (mes quelques recherches n’ont rien donné sur le sujet, si ce n’est que c’est potentiellement le cas par défaut sans avoir d’action à faire)

A vrai dire je n’y connais pas grand chose sur le sujet, ce que je dis est peut être complètement farfelu.

+0 -0

Salut,

Pour ton cas -une 20aine d’objets à tout casser- tu peux clairement faire ça avec un algorithme très naïf. Les perfs n’en souffriront vraiment pas. Surtout que tu dis que ces objets auront des formes circulaires. C’est l’algorithme de détection le moins gourmand !

Tu vas juste itérer sur chaque combinaisons de paires de cercles et vérifier si la distance entre leur centre est inférieure à la somme de leur rayon. En pseudo-code ça donnerait

1
2
3
4
5
for cercle1, cercle2 in paires_de_cercles():
    distance_au_carre = (cercle1.x - cercle2.x)**2 + (cercle1.y - cercle2.y)**2
    rayons_au_carre = (cercle1.r + cercle2.r)**2
    if distance_au_carre < rayons_au_carre :
        # Il y a collision

On garde le carré des distance, car c’est moins coûteux de calculer le carré de la somme des rayons plutôt que de calculer la racine carrée du carré des distances.

+0 -0

sinon, tiens-tu réellement à réinventer la roue plutôt que d’utiliser box2d ?

minirop

La petite remarque méchante. Bien joué, il en fallait bien une.

J’espère que c’est ironique. :-° Il a la gentillesse de te répondre, et d’apporter une alternative qui permet d’éviter la difficulté possible qu’on peut rencontrer à la "troisième phase" expliqué par Dan737 sur "Comment réagir à une collision ?".

D’après mon expérience, je peux t’assurer que pour ton usage tu n’as pas à t’inquiéter.

En effet, le calcul de simple collision d’une vingtaine de cercles ne consomme rien. Car quand tu calcules la collision de cercle, ça revient juste à calculer la distance de deux points et de soustraire cette distance par la somme des rayons des 2 cercles. Si tu as zéro ou moins, tu as une collision.

A comparaison ton affichage va consommer plus à essayer de dessiner et à calculer le lissage des formes surtout si c’est des images.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte