Discussion :

[luckyvae]

Bonjour, je suis en train de réfléchir à un système pour gérer les collisions dans le cadre d'un jeu en 2D.

J'avais pensé à un quadtree, ce qui me permettrais de tester uniquement les collisions entre objets se trouvant proche les uns des autres. Donc, chaque objet aurait une référence vers la feuille qui le contiendrais. Pour tester les collisions, je teste avec tout ceux qui sont dans le même nœud. Jusqu'ici, rien de spécial.

Mais une question m'est venue à l'esprit: mes objets ne sont pas des points, ils ont une certaine surface, et pourraient donc potentiellement appartenir à deux nœuds comme je ne me fixe pas de taille maximale et minimale pour mes objets dynamiques.
Une possibilité serait de bouger les frontières des nœuds, mais j'ai peur que le coût pour calculer celà me ferait perdre l'avantage des quadtree.

Une autre, serait que chaque nœud contenant une partie de mon objet dynamique contienne une référence vers cet objet. Mais alors, cet objet doit aussi compter autant de références que de nœud qui le contienne...

Comment est-ce que vous vous y prenez? Quelles pistes que je viens d'évoquer ne sont pas bonnes, lesquelles le sont?

[Ange_blond]

La méthode que j'ai déjà vu utiliser... c'est qu'a la racine de chaque element du quadtree, tu as une liste qui permet de stoker les elements à cheval sur plusieurs de ses fils... ainsi tu accede à cette liste sans devoir acceder aux fils.

C'est un choix, ) toi de voir ce qui est le mieux dans ton cas...

Sinon tu peux stocker l'élément à cheval dans chaque fils sur lesquels il est à cheval...

[Mat.M]

Bonjour, je suis en train de réfléchir à un système pour gérer les collisions dans le cadre d'un jeu en 2D.

J'avais pensé à un quadtree, ce qui me permettrais de tester uniquement les collisions entre objets se trouvant proche les uns des autres. ?

Quel type de jeu 2d ? Est-ce que les entités se déplacent avec les touches claviers ou bien alors en point et click c.a.d. un clic souris et l'entité se déplace jusqu'à ce point ?
Un quadtree parce que les possibilités de déplacement sont haut bas gauche droite ?
Si c'est un jeu point click oui un quadtree serait je pense la meilleure solution

[luckyvae]

Merci pour vos réponses

Quel type de jeu 2d ?

Un jeu de plate-forme, déplacements à l'aide du clavier

c'est qu'a la racine de chaque element du quadtree, tu as une liste qui permet de stoker les elements à cheval sur plusieurs de ses fils... ainsi tu accede à cette liste sans devoir acceder aux fils.

L'ennui avec cette méthode, c'est que toutes les entités ne sont plus dans des feuilles, et donc, il faudra remonter jusqu'à la racine du quadtree pour chaque test de collision...

Sinon tu peux stocker l'élément à cheval dans chaque fils sur lesquels il est à cheval...

et l'ennui avec cette méthode, c'est que l'élément doit alors avoir une référence vers chacun des noeuds qui le contient.


Je pense que je me trouve dans une situation où "je dois prendre la moins mauvaise des deux solutions". A moins que quelqu'un d'autre ait une idée?

[bafman]

au lieu de stocker les feuilles, tu stock le plus petit nœud contenant ton objet pour tester tes collisions.

[Mat.M]

Un jeu de plate-forme, déplacements à l'aide du clavier

Utiliser des structures arborescentes c'est un peu complexifier la chose.
Un bête et banal test coordonnée x =object y et coordonnée x =object y ( alors pas de mouvement ) en parcourant la liste des objets ne suffit pas ?

[luckyvae]

au lieu de stocker les feuilles, tu stock le plus petit nœud contenant ton objet pour tester tes collisions.

juste pour être sur: le plus petit nœud qui contient entièrement mon objet, c'est ça?
en effet, ça pourrait marcher (ou en tout cas, je ne vois pas de problème important à première vue)

Utiliser des structures arborescentes c'est un peu complexifier la chose.
Un bête et banal test coordonnée x =object y et coordonnée x =object y ( alors pas de mouvement ) en parcourant la liste des objets ne suffit pas ?

Le soucis, c'est que c'est de complexité n². Tandis qu'avec une structure d'arbre, je peux avoir une complexité de n log(n), ce qui sera plus performant.
Ce ne serait pas très important dans le cas où il n'y avait qu'une petite cinquantaine d'objets, mais comme j'aimerai pouvoir créer des niveaux avec énormément d'objets dynamiques, ça permettra de gagner en temps d'exécution.

[bafman]

juste pour être sur: le plus petit nœud qui contient entièrement mon objet, c'est ça?
en effet, ça pourrait marcher (ou en tout cas, je ne vois pas de problème important à première vue)

oui, c'est exactement ça.

[ZouBi]

juste une petite precision, c'est quoi le quadtree?

[Ange_blond]

juste une petite precision, c'est quoi le quadtree?

http://en.wikipedia.org/wiki/Quadtree

Y'a quand meme pas de quoi chercher un peu...

[Mat.M]

Le soucis, c'est que c'est de complexité n². Tandis qu'avec une structure d'arbre, je peux avoir une complexité de n log(n), ce qui sera plus performant.

D'accord mais si tu n'as qu'un seul personnage, tu connais ses coordonnées X et Y donc c'est simplement de complexité n objets ? Je me trompe ?
Tu n'en dis pas assez

[babar63]

D'accord mais si tu n'as qu'un seul personnage, tu connais ses coordonnées X et Y donc c'est simplement de complexité n objets ? Je me trompe ?
Tu n'en dis pas assez

Un jeu de plateforme 2D un minimum développé comporte en général plus que les collisions avec un seul personnage (on risque de s'ennuyer sinon) . Enfin c'est vrai que ce n'est pas obligatoire mais on peut supposer que ce n'est pas le cas ici puisqu'il parle d'une complexité en n².

Le soucis, c'est que c'est de complexité n². Tandis qu'avec une structure d'arbre, je peux avoir une complexité de n log(n), ce qui sera plus performant.
Ce ne serait pas très important dans le cas où il n'y avait qu'une petite cinquantaine d'objets, mais comme j'aimerai pouvoir créer des niveaux avec énormément d'objets dynamiques, ça permettra de gagner en temps d'exécution

Ça me parait en effet la meilleure solution si tu dois gérer de nombreux objets, surtout que le quadtree n'est pas si compliqué à mettre en place

[luckyvae]

D'accord mais si tu n'as qu'un seul personnage, tu connais ses coordonnées X et Y donc c'est simplement de complexité n objets ? Je me trompe ?
Tu n'en dis pas assez

Le fait est justement qu'il n'y aura pas que le personnage principal qui aura besoin de ces test de collisions. Il y aura aussi tous les ennemis, et autre objets dynamiques.
Je pourrais me contenter d'un simple passage en revue de chaque objet si il n'y avait que lui qui ait besoin de bouger au sein de mon niveau, et mes ennemis se contenterais de faire des aller retour du point A au point B, mais j'ai envie de faire des ennemis un peu intelligent.

Bon, je vais passer le sujet en résolu. merci beaucoup pour votre aide

[ZouBi]

C'est la méthode que j'utilise.
J'ai distingué deux types d'élements :
- Statique ( Sol, Bloc, Pièce...)
- Dynamique ( Personnage, Ennemis... )

On parcourt tous les objets d'Elements Dynamiques qu'on a, et on verifie si il y a collision avec les autres Elements ( Statiques & Dynamiques... ) qui sont dans un certain périmètre définis ( 100px? 50px autour? ).
voilà