| Optimisation des collisions | |
|
|
Auteur | Message |
---|
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Optimisation des collisions Lun 4 Juin 2012 - 11:12 | |
| Bondour cbna 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.
|
|
| |
arthuro Utilisateur confirmé: Rang ****
Messages : 1480 Localisation : Paris Projet Actuel : Diagon https://arthursonzogni.com/Diagon
| Sujet: Re: Optimisation des collisions Lun 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.htmlIl 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é. |
|
| |
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Re: Optimisation des collisions Lun 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.
|
|
| |
arthuro Utilisateur confirmé: Rang ****
Messages : 1480 Localisation : Paris Projet Actuel : Diagon https://arthursonzogni.com/Diagon
| Sujet: Re: Optimisation des collisions Lun 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? |
|
| |
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Re: Optimisation des collisions Lun 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 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.
|
|
| |
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Re: Optimisation des collisions Mar 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à _________________ Because these are not the words of God, the same God that burnt the knowing.
|
|
| |
arthuro Utilisateur confirmé: Rang ****
Messages : 1480 Localisation : Paris Projet Actuel : Diagon https://arthursonzogni.com/Diagon
| Sujet: Re: Optimisation des collisions Mar 5 Juin 2012 - 16:58 | |
| Oué, en faisant ça tu divise par deux le nombre de test. |
|
| |
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Re: Optimisation des collisions Mar 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.
|
|
| |
D-z Utilisateur confirmé: Rang *****
Messages : 1611 Localisation : Montpellier
| Sujet: Re: Optimisation des collisions Mar 5 Juin 2012 - 18:50 | |
| Un quadtree ? _________________ Home is not a place, it's a feeling.
|
|
| |
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Re: Optimisation des collisions Mar 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.
|
|
| |
arthuro Utilisateur confirmé: Rang ****
Messages : 1480 Localisation : Paris Projet Actuel : Diagon https://arthursonzogni.com/Diagon
| Sujet: Re: Optimisation des collisions Mer 6 Juin 2012 - 19:18 | |
| |
|
| |
Termite Utilisateur confirmé: Rang ****
Messages : 1005 Localisation : Dans ta charpente ! Projet Actuel : RayEngine 5.0
| Sujet: Re: Optimisation des collisions Mer 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 J'uperais le topic si jamais j'dois vous embêter, merci _________________ Because these are not the words of God, the same God that burnt the knowing.
|
|
| |
Contenu sponsorisé
| Sujet: Re: Optimisation des collisions | |
| |
|
| |
| Optimisation des collisions | |
|