AccueilAccueil  RechercherRechercher  S'enregistrerS'enregistrer  Connexion  

 

 Optimisation des collisions

Aller en bas 
AuteurMessage
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Optimisation des collisions   Optimisation des collisions EmptyLun 4 Juin 2012 - 11:12

Bondour cbna bneige

Je cherche un moyens d'optimiser mon système de collision, histoire de gagner des FPS quand y'en a pas mal à tester.
Les collisions ne sont que des axis-oriented, le truc c'est qu'au bout de 200-300 boxes à tester, ben le moteur aime pas des masses...
Chacune de ces boxes possèdent un teamID (qui va définir qui peut être en collision avec qui), des flags (certaines boxes n'ont pas besoin de vérifier leur collisions, par exemple on s'en fiche de savoir si deux boxes qui sont des hipoints sont en collision, vu que les hitpoints sont fait pour être testé par les hitboxes)

Pour l'instant, ma façon de procéder est la suivante :

Je prend une box, je parcours ma liste de boxes (celle-ci sont contenu dans des std::map<int,zone>, parcours par iterator)
je vérifie la teamID
je vérifie les flags (opérateur logique &, les flags sont en binaire, le premier sera 0b1, le second 0b01, le troisème 0b001, etc)
Ensuite, j'ai introduit un système de bounding-sphere, c'est plus simple de vérifier l'intersection des sphères. J'ai utilisé la distance de manhattan pour vérifier les collisions, ça évite d'utiliser des racine-carré, manhatten se calcule comme ça : dx + dy, tout bêtement.
Une fois ce test effectué, je vérifie les boîtes en elle-même, donc côté gauche/droit/haut/bas.
Et je recommence pour toute les boites.

Niveau perfs, ça me donne ça :

101 boxes : 240 fps
201 boxes : 160 fps
301 boxes : 108 fps
501 boxes : 41 fps
1001 boxes : 11 fps

Sachant que dans le test, seulement une seule boxe testait les autres, les perfs sont pas terrible..
Lua est à prendre en compte aussi, vu qu'à chaque tick du moteur il récupère toute modification apportée à chaque boxe (position, taille, team, flags, etc), sans test de collision on est à ~20-30fps avec 1001 boxes..

Quel système pourrais-je mettre en place pour améliorer tout ça ?

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1472
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyLun 4 Juin 2012 - 16:04

Si j'ai bien compris tu as des AABB rectangle (rectangle de direction fixé). Tu programme en c++(/LUA). Et tu veux améliorer les perfs.

Dans ce cas tes perfs sont vraiment mauvaise (surtout si tu ne testait que la collision entre 1 box et les autre).
C'est un peu louche.


Si ce n'est que des AABB rectangle, ton test préliminaire ou tu parle de distance de Manhattan, me semble superflu. (le simple test sur les bords gauche, droit, haut, bas est sûrement même plus rapide) . Ce test pour gagner des perfs pourrait ne pas t'en faire gagner, voir t'en faire perdre.

vérifie peut-être ton programme.

Je te renvoie ici:
http://www.siteduzero.com/tutoriel-3-254492-theorie-des-collisions.html

Il y a quelques idées pour optimiser.



Sinon l'algo de base est de complexité (nombre de boite)²
J'ai pas mal d'idée pour obtenir de meilleurs complexité.

_________________
Optimisation des collisions PochetteOptimisation des collisions Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyLun 4 Juin 2012 - 17:43

Ben c'est qu'avant de vérifier les côté des boites, le code donne ça :

if ((abs(box2.cx - box1.cx) + abs(box2.cy -box2.cy) <=(box1.DistManhattan +box2.DistManhattan))
// Le test sur les côtés


cx et cy sont calculé lors de la maj de la box, et sont les coordonnées du centre de la boîte.
Y'a pas vraiment de changement si je vire ce test...


edit: en fait, rien que le fait de parcourir ma std::map deux fois me faire perdre ~10FPS

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1472
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyLun 4 Juin 2012 - 19:59

En même temps le temps d'accès à une std:map est en ln(n) de complexité ( n = nombre d'objet dans ta std::map)
tu risque de la parcourir n fois donc au final tu aura un truc en n*ln(n)

Tu pourrais peut-être tout stocké dans un std::vector (en temps d'accès constant)
Ceci à la condition que tu n'ajoute pas d'éléments en permanence.
Même dans ce cas là, tu peux jouer avec la méthode reserve(nb case) de std::vector pour pas que la mémoire soit en permanence réalloué quand la taille de ton tableau augmente.

Je persiste à dire que tu devrais jeter le test où tu fait la distance de manhattan ( faire 4 test <= sur les côté est déjà très rapide, ton test ralentit par 2 ton programme)


Tu as besoin de LUA pourquoi?

_________________
Optimisation des collisions PochetteOptimisation des collisions Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyLun 4 Juin 2012 - 20:07

Même sur les iterators ?
J'ai changé en un vector, les perfs ne changeait pas (parcours par iterator toujours), par contre, si je fais un truc du style (avec un vector) :

Zone ** ZZ = &MonVectZone[0];

Et que je parcours avec un int ce pointeur sur pointeur, les perfs sont améliorées (avec 500 instances j'tourne à ~48FPs avec les testes de collisions, sinon j'étais à ~40 sans les tests)

Bon du coups je vire mon truc du manhattan Very Happy

En gros, le Lua est pour tout ce qui est "haut niveau" dans le jeu (ennemis/joueur/objets,etc) à l'instar de l'unreal-script pour l'unrealEngine, et il gère aussi les zones (collisions entre objets), seulement le côté position/taille,etc, les testes se font au sein du moteur.

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMar 5 Juin 2012 - 14:33

C'est bon, j'ai réussi à faire un truc plus potable (perte de fps après ~450 boxes)
en gros, au lieu de parcourir deux fois entièrement ma liste, je pars du premier index dans la seconde boucle, je vérifie les flags des deux boxes à tester, et je fais les tests de collisions.

Parcourir deux fois entièrement revient à faire ça :

(id des boxes)
0 1
0 2
1 0
1 2
2 0
2 1

Du coups, des testes sont refait plusieurs fois ( 1 0 / 0 1, 1 / 2 , 2 / 1)

En repartant de l'id du premier, ça donne ça :

0 1
0 2
1 2

Voilà Very Happy

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1472
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMar 5 Juin 2012 - 16:58

Oué, en faisant ça tu divise par deux le nombre de test.

_________________
Optimisation des collisions PochetteOptimisation des collisions Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMar 5 Juin 2012 - 18:12

Il y aurait autre chose à faire pour optimiser ? Perso j'suis à court d'idée (bien que ~400 devrait suffire)

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
D-z
Utilisateur confirmé: Rang *****
D-z

Messages : 1611
Localisation : Montpellier

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMar 5 Juin 2012 - 18:50

Un quadtree ?

_________________
 
Home is not a place, it's a feeling.
Revenir en haut Aller en bas
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMar 5 Juin 2012 - 19:42

Jpense que ça mangerait plus les perfs qu'autre chose,et je sais pas si c'est trop adaptable à cette situation

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
arthuro

Messages : 1472
Localisation : Paris
Projet Actuel : Diagon https://arthursonzogni.com/Diagon

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMer 6 Juin 2012 - 19:18

Vu le nombre de bloc que tu as je pense qu'il y aurait une réel optimisation.

Un article de wikipédia qui présente les différentes façon d'optimiser ton algo.
http://fr.wikipedia.org/wiki/D%C3%A9tection_de_collision

_________________
Optimisation des collisions PochetteOptimisation des collisions Signature.php?gid=588
D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
Termite
Utilisateur confirmé: Rang ****
Termite

Messages : 1005
Localisation : Dans ta charpente !
Projet Actuel : RayEngine 5.0

Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions EmptyMer 6 Juin 2012 - 21:21

Ben les tests sont fait pour voir les limites, 450 boxes c'est vraiment beaucoup et c'est normalement pas censé se produire (sachant qu'un ennemi en aura en gros 2, le reste une seule à certaines exceptions probable)

Je vais quand même tester ça, mais j'me serais plutôt orienté sur un système de grilles, sur lesquels les boxes s'enregistrent quand elles y sont présente. Déjà que 450 boxes sur une map est peu probable, qu'il y en ai 450 dans la même zone c'est du sadisme envers mon pauvre moteur Very Happy

J'uperais le topic si jamais j'dois vous embêter, merci bneige

_________________
Because these are not the words of God, the same God that burnt the knowing.
Revenir en haut Aller en bas
Contenu sponsorisé




Optimisation des collisions Empty
MessageSujet: Re: Optimisation des collisions   Optimisation des collisions Empty

Revenir en haut Aller en bas
 
Optimisation des collisions
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Programmation-
Sauter vers: