Optimiser un système de collision

Bonjour

Voilà, je cherche à optimiser le système de collision de mon moteur, j'ai vraiment l'impression de m'y prendre comme un barbare..
Mon système de collision marche par zone, teamID et filtres, j'explique :

Chaque zone possède un numéro qui identifie son "équipe", ce qui permet de ne pas tester des zones qui sont dans la même "équipe", histoire que, par exemple, deux ennemies ne se mettent pas subitement à s'entretuer (ce qui est plutôt marrant, mais bref)

Ensuite, il y a la notion de filtre.
Les filtres sont définie par lua, voilà leur construction (exemple de zone de vue d'un ennemie) :

filter_viewzone={};
filter_viewzone[0]="hitpoint";
filter_viewzone[1]="player";
create_filter("viewzone",filter_viewzone);

Donc à chaque fois qu'une zone est enregistrée en tant que type "viewzone", elle ne testera les intersection qu'avec les zones de types "hitpoint" et "player".

Bon, tout ça c'est bien joli, mais voilà comment se passe la gestion des intersections :

Lorsque tous les events (instances si vous voulez comparer à GM) ont fini leur fonction step, le moteur lance une grosse boucle sur les zone.
Il récupère une zone, puis lance une deuxième boucle sur toute les zones, et teste sur chaque zone sa teamID, son filtre et enfin s'il y a une intersection avec la première zone récupérée.
Dès qu'il y a collision, il casse la boucle et prend la zone d'après et recommence le teste sur toute les autre zones.

ça marche, mais j'ai vraiment l'impression de m'y prendre comme un barbare, je voudrais savoir s'il y a moyens d'optimiser tout ça.. J'avais pensé à faire des std::map qui stockent des array pour regrouper toute les zones du même filtre, mais je peux pas tellement savoir si c'est plus rapide ou pas..

Merci pour votre aide

John Carmack a dit: Utilise un octree
Alors utilise un Quadtree(l'équivalant 2D d'un octree)
http://fr.wikipedia.org/wiki/Quadtree

Doux jésus

Ben, de toute façon les objets en dehors de la vue sont désactivés, et ce serait assez bordélique de tout découper en zone..
(surtout que je devrais tout le temps re-tester chaque zone, bref..

J'ai pas préciser, mais les collisions ne se font que sur des carrés (aucune collision par pixels)

Si ils sont désactiver ca doit demander pas mal de temps à activer/désactiver dès que tu bouge la caméra non?

Ben, c'est juste une zone définie autours d'eux, et ensuite on teste s'il n'y a pas d'intersection avec la position de la caméra

Mais j'ai vraiment peur de mal m'y prendre pour tout le système de base, et de me retrouver avec un vieux truc bouseux tout lent

C'est en forgeant qu'on deviens forgeron. Continue sur ta lancée et si ça marche pas recommence.
Franchement j'ai foi en toi lol, je suis sur que t'y arriveras. T'arrive a t'adapter super vite.

Et aussi les meilleurs solutions sont toujours celles qu'on trouve tout seul, surtout dans ce genre de situation !

Bon courage :p

Héhé, merci

C'était juste histoire d'éviter un peu de recommencer (j'ai déjà refait plusieurs fois le moteur, ça doit être au moins la 4 ou 5ième fois que je le réécris en entier )

Je comprend rien du tout mais alors rien du tout au quad tree.

Apparemment le principe est de créer une énorme zone dans tout le jeu, puis de la subdiviser plusieurs fois afin de générer des petites zones, et ensuite on limite les collisions à cette zone (en gros, le jeu essaiera pas de voir si y'a une collision avec l'object qui est à 800km par exemple )

Mais je pense que c'est surtout utile dans la mesure où les collisions sont faites par pixels, c'est largement plus lourd à tester qu'une intersection avec des boxes

Je penses aussi car les collisions par tileset avec tableau, ça ne recherche que les collisions dans la zone du perso.

Non, rien à voir

Quand tu fais un système de collision par tableau, tu créé d'autre variable x&y qui sont attachés à une grille, et tu teste sur _x/16 & _y/16 pour reporter sur ta matrice

Oui je sais très bien puisque je l'utilises

N'est-il pas?

onilink_ a écrit:

C'est en forgeant qu'on deviens forgeron. Continue sur ta lancée et si ça marche pas recommence.
Franchement j'ai foi en toi lol, je suis sur que t'y arriveras. T'arrive a t'adapter super vite.

Et aussi les meilleurs solutions sont toujours celles qu'on trouve tout seul, surtout dans ce genre de situation !

Bon courage :p

Bien dit ^^