Discussion :

[FrostfallDelphi]

Bonsoir à tous ! :-]

Dans le projet que je confectionne actuellement avec la SFML, j'ai constaté une chute significative de FPS au fur & à mesure que j'affiche des sprites, au début je me suis dit " ben m**rde alors, ça bouffe tant de CPU que ça les sprites ? ", mais Que Nenni ! Je me suis finalement rendu compte que ce qui ralentissait mon programme au fur & à mesure que le nombre de sprite augmentait.. c'était ma fonction de tri !

J'ai conçu cette mini-fonction toute simple en utilisant une fonction lambda :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
void Camera::sortFunction()
{
    ///ON TRI LES SPRITES LES PLUS LOINS AUX PLUS PROCHES///
    std::sort(m_vecSprites.begin(), m_vecSprites.end(),
        [](Sprite& s1, Sprite& s2) -> bool { return s1.getDistance() > s2.getDistance(); });
}

Le but étant de trier les sprites les plus loin jusqu'aux plus près de la caméra, je suis obligé de procéder à un tri dans mon cas de figure, mais quand je passe à 6,7 / 10,11 voir 15 sprites, mon programme rame énormément, comme si j'avais un vieux pentium 133mHz

Lorsque je retire cette fonction, mon programme redevient parfaitement fluide, j'ai mes 60 FPS, mais évidemment, mes sprites n'apparaissent pas le bon ordre car non triés...

Donc selon vous, comment pourrais-je essayer de procéder afin de pouvoir gérer un tri de manière rapide & optimisée ?
J'ai essayé d'appeler ma fonction dans un thread séparé, ça n'a rien changé au problème, hélas :-/

Merci à vous !

[dalfab]

Le coût du tri est lié à la quantité de données à déplacer, si l'opération de swap entre 2 objets de la liste est lourde cela ralenti car on il doit se faire plus de cent fois.
Ce qui coûte aussi est l'appel de la fonction getDistance() qui sera elle encore plus appelée alors qu'il suffirait d'une fois par sprite.
Si le tri ne sert qu'à l'ordre d'affichage, on peut passer par une table d'index qui sera triée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
std::vector<std::pair<double,std::size_t>> sprSorted(m_vecSprites.size());
for ( std::size_t i = 0 ; i < m_vectSprites.size() ; ++i )
   sprSorted[i] = std::make_pair( m_vecSprites[i].getDistance() , i );
std::sort( sprSorted.rbegin() , sprSorted.rend() ); // tri du plus éloigné au plus proche
for ( auto const& x : sprSorted )
    m_vecSprites[x.second].display();

[FrostfallDelphi]

Salut à toi Dalfab, merci beaucoup de m'avoir répondu aussi rapidement, ce forum est super dynamique, c'est top !

J'irais tester ça dés que je serais rentré chez moi, merci encore & encore :-)

[FrostfallDelphi]

Donc, j'ai testé ta solution mais j'ai trouvé un équivalent beaucoup plus rapide que ma précédente fonction et surtout bien plus simple ! :-)

J'ai utilisé std::swap de la manière suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
void Camera::sortFunction()
{
    for (short int i = 1 ; i < m_vecSprites.size() ; i++)
    {
        if (m_vecSprites[i].getDistance() > m_vecSprites[i-1].getDistance())
            std::swap(m_vecSprites[i], m_vecSprites[i-1]);
    }
}

Encore merci en tout cas

[JolyLoic]

Ce que tu fais là n'est pas un tri... Après ça, tes données seront un peu plus triées, mais pas totalement. Et pour qu'elles le soient totalement, il faudrait imbriquer 2 boucles de ce genre, et là tu aura un algorithme équivalent à std::sort, mais beaucoup moins performant.

Mais de toute façon, il n'y a aucune raison qu'un tri d’une quinzaine d'éléments ralentisse de manière mesurable ton rendu...

Quand tu parles de sprite, tu parles de sf::sprite, ou d’une classe à toi ? Si c'est une classe à toi, j'aimerais la voir. Sinon, un sf::sprite n'est pas quelque-chose d'ultra léger à copier (j'ai jeté un œil, et il y a grosso modo une centaine d'octets à copier), mais ce n'est pas non plus la mort (il n'y a pas d’allocation mémoire à faire, par exemple) et de toute manière, les std::swap doivent aussi faire les mêmes copies...

Dit autrement, je pense que ton problème n'est pas actuellement résolu, juste camouflé, et qu'il reviendra te poignarder dans le dos au moment le moins opportun...

[koala01]

Salut,

il n'y a rien à faire, quelque soit la méthode de tri envisagée, si tu t'amuse à trier tous les éléments d'une collection (quelle qu'elle soit : il s'agit d'un [c]std::vector[c] dans ton cas) tu dois t'attendre à ce que chaque élément de ta collection soit comparé avec tous les autres, ce qui fait un nombre de comparaison évoluant plus ou moins à la manière d'une factorielle.

Les choses sont encore pires lorsque tu dois trier des éléments lourds / dont la copie prend du temps, car, en plus de toutes les comparaisons, tu te tapes à chaque fois au moins trois copie par déplacement.

La première chose à faire est donc peut-être de faire en sorte de ne pas devoir faire autant de parcours de ta collection. Or, dans le cas que tu explique, il est tout à fait possible de le faire. Je m'explique:

Tu veux trier tes sprites par rapport à la distance qui les sépare de la caméra (sur l'axe des Z). Mais chaque éléments n'a que trois choix possible:

1. soit il s'approche de la caméra et "dépasse" donc éventuellement les éléments qui sont "devant lui", mais ceux qui sont "derrière lui" n'ont aucun intérêt
2. soit il s'éloigne de la caméra se fait fait donc éventuellement "dépasser" par les élément qui sont "derrière lui", mais ceux qui sont "devant lui" n'ont aucun intérêt
3. soit il reste "à la même distance" de la caméra, et il n'y a donc rien à faire

Cela signifie que l'on peut donc déjà très fortement limiter le nombre de comparaisons et de déplacements en évitant d'aller comparer notre élément courant à ceux qui "n'ont aucun intérêt", sous une forme qui serait proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
Si 'élément courant avance
    Tant qu'il y a un élément précédant et que élément précédant a été dépassé
        intervertir élément courant et élément précédant
     Fin Tant
Sinon  Si élément courant recule
    Tant qu'il y a un élément suivant et que élément courant a été dépassé par l'élément suivant
        intervertir élément courant et élément suivant
     Fin Tant
Fin Si

(je te laisse traduire cela en C++ )
Cela signifie que, dans le pire des cas,

1. si l'élément avance, il ne sera comparé qu'une seule fois à tous les éléments qui le précèdent
2. si l'élément recule, il ne sera comparé qu'une seule fois à tous les élément qui le suivent

Tu me diras que cela revient finalement grosso modo au même qu'avec n'importe quelle fonction de tri (vu que ce sera quand même effectué pour chaque élément qui se déplace). Mais il y a quand même de grosses différences parce que:

1. il y a "toute une partie" des éléments qui seront ignorés, selon le sens du mouvement (voire tous, si l'élément ne se déplace pas sur l'axe des Z)
2. Soit il n'y a plus d'élément devant / derrière l'élément (selon le sens du déplacement) courant, et on a fini, soit l'élément qui se trouve devant / derrière (selon le sens du déplacement) n'a pas été dépassé par l'élément courant (respectivement n'a pas dépassé l'élément courant), et cela ne sert donc à rien de vérifier les autres.

La deuxième chose à faire, ce sera d'éviter les copies inutiles d'éléments (de sf::Sprite dans ton cas):Il faut savoir en effet que le processus de copie d'un élément prend du temps et tu as trois copies qui sont effectuées lors de l'inversion de deux éléments (nommons les A et B), car la logique est proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
soit Temp est un élément du type adéquat:
Temp =  A (première copie)
A = B (deuxième copie)
B = Temp (troisième copie)

Avant l'arrivée de C++11, on aurait sans doute travaillé avec des pointeurs, car un pointeur n'est jamais qu'une valeur numérique entière (généralement non signée) représentant l'adresse mémoire à laquelle on devrait trouver un élément du type qui nous intéresse.

On ne pouvait pas utiliser les références à l'époque parce que les règles sur les références font qu'on ne peut pas faire en sorte qu'une référence fasse référence à un autre élément que celui qui lui a été assigné au moment de sa définition en cours d'utilisation et parce que l'on ne peut pas créer une collection de références.

Autrement, une référence n'est jamais qu'un pointeur bien déguisé, et elle sera représentée dans le code binaire final utilisable par le processeur sous la forme d'un pointeur

Mais C++11 est arrivé avec une classe géniale qui lève ces restriction en nous permettant la création d'un objet contenant une référence. Objet qu'il est possible de placer dans une collection et que l'on peut "réassigner" afin de changer l'élément référencé. Je veux bien sur parler de la classe std::reference_wrapper.

Tu peux donc utiliser un std::vector<std::reference_wrapper<sf::Sprite>> et le manipuler (à peu de chose près: il faut utiliser tab[i].get()./* la fonction qui t'intéresse*/) exactement comme si tu manipulait ton tableau de sf::Sprite, les copie inutiles en moins