Gestion memoire des projectiles dans un shoot them up

Un article de Teto.


Sommaire

[modifier] Introduction

Le premier réflexe à avoir avant de coder une application est de réfléchir à ce qu'elle devra pouvoir faire, bref établir un cahier des charges.

Nous allons ici réfléchir aux possibilités du système de gestion des bullets dans le cadre d'un bullet hell shmup, c'est à dire un jeu avec beaucoup beaucoup de bullets avec des cycles de vie courts.

Au final le système doit pouvoir en temps réel :

  1. Mettre à jour
  2. Supprimer et créer rapidement des bullets
  3. Respecter l'ordre de création des bullets. En effet quand vous établissez vos jolis patterns de tir les bullets sont susceptibles de se superposer alors autant qu'elles se superposent dans leur ordre de création : ce sera cohérent et esthétique. ( faire une image exemple )


Pendant la deuxième phase, on doit se concentrer sur les solutions techniques ( quelles classes va-t-on créer/utiliser ? comment le tout va-t-il s'interfacer ? ). Zêtes pas obligé de faire un graphe UML/Merise pour cela :p , le mieux reste pour une petite équipe papier et crayon. En l'occurence vous n'avez qu'à vous laisser guider.


[modifier] Recherche de solutions

Normalement quand vous avez conçu votre jeu, vous avez très certainement créer une structure/classe pour les projectiles: elle sera appelée ici "CBullet".

On va également essayer de faire un système à allocation de mémoire dynamique ( ce serait moins fun sinon ).

Nous allons essayer de répondre point par point au cahier des charges mais il est évident qu'il s'agit d'un tout, que la solution apportée sur un point influe sur celles potentielles aux autres points. La démarche n'est pas toujours évidente étant donné que tout est lié.

[modifier] Mise-à-jour

Si l'on veut parcourir rapidement les entités bullets ( = les objets de classe CBullet ), il faut que celles-ci soient contigües en espace mémoire ( pour bénéficier de l'optimisation du cache ). Or ceci correspond à la définition d'un tableau. Mais nous voulons faire un tableau dynamique ! Le seul container standard qui répond à ces critères est le std::vector. En effet les éléments d'un std::vector sont contigües comme dans un tableau C.

TODO: arrive pas à le mettre en note :s Pour parcourir un container standard (dont std::vector), il peut s'avérer pratique d'utiliser la macro BOOST_FOREACH (au lieu de déclarer une boucle for avec itérateurs etc... ) qui s'utilise comme suit:

#include <boost/foreach.hpp>
std::vector<int> monVector;
BOOST_FOREACH(int monEntier,monVector){
    std::cout << "hello visiteur N°" << monEntier << std::endl;
}


Attention!
Rappel sur l'opérateur [] de std::vector: Quand vous utilisez cet opérateur vous n'avez pas la garantie d'être dans le tableau. En revanche si vous utilisez l'opérateur at(), celui-ci lancera une exception en cas d'accès à un élément hors du tableau


Vous pouvez d'ailleurs créer/initialiser un tableau C à partir d'un vecteur :

std::vector<int> vecteurEntiers; int
tableauEntiers[10]; tableauEntiers = &vecteurEntiers[0]

Là où il faut être vigilant c'est que si vous ne réservez pas l'espace mémoire final à l'avance, quand vous agrandirez votre vecteur ( avec la fonction membre push_back() ), si le vecteur ne dispose pas de la place contigüe nécessaire, il va TOUT déplacer dans une zone mémoire où cette place est disponible. Inutile de dire que ce processus est très lent et qu'on cherchera à l'éviter à tout prix.

Une première solution sera de réserver de l'espace au préalable avec la fonction membre reserve.

Pour peu que notre classe soit volumineuse, on reservea des pointeurs vers des instances de classe.

[modifier] Rapidité de la création et de la suppresion

Que faire pour supprimer un bullet ? Plutôt que de le supprimer simplement du vecteur, nous allons d'une part mettre un booléen propre à la classe CBullet à 0, et d'autre part enregistrer dans un autre vecteur ( d'entiers celui-ci ) la position des bullets ayant ce booléen nul par rapport au premier élément.

Attention!
Il peut être intéressant d'utiliser un entier "active" faisant référence au classement dans le vecteur plutôt qu'un simple booléen ( notamment dans le cas de la généralisation via template des doublebuffer )


Dans l'exemple qui suit, nous voulons tuer le XXX-ième élément du vecteur:

std::vector<CBullet> bullets;                   // Les noms sont explicites non ?
std::vector<int> indicesBulletsInactifs;
 
// On a remplit le vecteur de bullets vivants au moins jusqu'au rang 4
...
 
// Maintenant on veut supprimer le 4ieme bullet
bullets[4].active = false;// On dit a ce bullet qu'il n'est pas actif
indicesBulletsInactifs.push_back(4);
 
 
// Pour mettre a jour les bullets on fait une boucle for...
for( i=0; i < bullets.size();i++){
 
       // + verification pr savoir si c'est utile de le mettre a jour
       if(bullets[i].active){
 
               // alors on met a jour
               bullets[i].mettreAjour();
       }
}

Si on veut créer un nouveau bullet, on cherche s'il y a des indices de libres dans le tableau indicesBulletsInactifs sinon on ajoute un nouvel espace mémoire ( on a plus le choix ) mais comme on aura fait un reserve() avant, cela ne devrait pas ralentir le système' ou alors il faudra augmenter le nombre d'éléments réservés :

if(indicesBulletsInactifs.size()){
 
       // On reinitialise comme il faut la classe
       bullets[indicesBulletsInactifs.back()].active = true;
       bullets[indicesBulletsInactifs.back()].Reset();
       ...
 
       // On supprime l'indice du tableau des indices libres puisque
       justement il n'est plus libre :D
       indicesBulletsInactifs.pop_back();
 
}
// Sinon si tous les elements du vecteur bullets sont actifs
else {
 
       // On ajoute un nouvel element
       bullets.push_back(CBullet bullet);
 
}


[modifier] Respect de l'ordre de création

Maintenant un autre souci apparaît: Imaginons que vous deviez supprimer le bullet 3 ( dont la position dans le vecteur bullets est la position 3) puis le bullet 5 ( pareil:position 5 dans bullets ). Avec le système actuel vous allez mettre dans indicesBulletsInactifs d'abord le numéro 3 ( indicesBulletsInactifs.push_back(3) ) puis ensuite le numéro 5 ( indicesBulletsInactifs.push_back(5) ). Quand vous allez récupérer les identifiants pour créer de nouveaux bullets, vous les récupérerez en ordre inverse, c'est-à-dire d'abord 5 puis 3 ( pour l'instant tout est normal ). Le prochain bullet créé aura la position 5 dans le vecteur et le second bullet que vous voudrez créer aura la position 3 : l'ordre n'est plus respecté !!

Quand vous allez les afficher à l'aide d'une boucle for vous afficherez le bullet de position 3 dans le vecteur avant le bullet de position 5 ( logique ) qui ne respecte pas leur ordre de création:

// Pour mettre a jour les bullets on fait une boucle for...
for( i=0; i < bullets.size();i++){
 
       // + verification pr savoir si il faut l'afficher
       if(bullets[i].active){
               // On l'affiche
               bullets[i].Afficher()
 
       }
}

Pour résoudre ce souci, on pourrait classer le vecteur à chaque fois qu'on y insère un élément. Certes cela fonctionne mais le coup en performance n'est pas négilgeable. L'astuce ultime ( Il s'agit également de "l'ultime astuce" rassurez-vous ;) ) consiste à d'utiliser un doublebuffer d'indices en lieu et place du simple buffer.

Concrètement on remplace std::vector<int> indicesBulletsInactifs par std::vector<int> indicesBulletsInactifs[2]; et on ajoute 2 booléens indiceBufferSource, indiceBufferStockage dans notre système d'allocation des bullets. L'idée est de ne trier le tableau d'indices qu'une fois de temps en temps.

Dès que le buffer en cours d'utilisation est vide, on trie le buffer de stockage et on échange les valeurs des booléens: cela équivaut à "l'ex-buffer en cours d'utilisation devient le buffer de stockage et l'ex-buffer de stockage devient le buffer en cours d'utilisation". De cette manière les indices sont dans l'ordre nécessaire sans pour autant ralentir le système à "chaque passage".


[modifier] Conclusion

J'ai essayé d'écrire 2 classes template ( intrusive et non intrusive) C++ pour illustrer l'article mais qui peuvent aider à comprendre le tutorial ( regarder le container intrusif par valeur, les autres n'étant pas efficaces pour un bullet hell ):

Je vous invite également à jeter un coup d'oeil à boost::intrusive ( http://www.boost.org/doc/libs/1_41_0/doc/html/intrusive ) qui ne nécessite pas de compilation de boost ( il s'agit juste d'en-tête .hpp), permet d'itérer plus rapidement sur un container comme std::vector, et dispose de fonctionnalités permettant d'implémenter ce tutorial de manière très efficace ( http://www.boost.org/doc/libs/1_41_0/doc/html/intrusive/erasing_and_disposing.html ). J'essaierai d'ajouter un exemple utilisant boost::intrusive.

[page de dscussion]Discuter:Gestion memoire des projectiles dans un shoot them up

Sommaire

[modifier] std::vector est-il adapté?

Je me pose la question. J'ai rarement eu à utiliser std::vector pour quoi que ce soit, et je pense qu'il est piégeux de penser que parce qu'on utilise un std::vector, les performances vont être nécessairement meilleures.

Voici pourquoi: Ce que tu cherches à faire avec le tableau "bullets", c'est créer des objets CBullet pour les réutiliser par la suite, et éviter d'en réallouer à tire-larigot. C'est louable, tu veux créer un pool de CBullet réutilisables pour te dédouaner un maximum du temps d'allocation/désallocation.

Le problème avec une approche par valeur dans le vecteur est que la ligne où tu ajoutes un nouvel élément (bullets.push_back(CBullet bullet) qui est d'ailleurs syntaxiquement incorrecte) a deux problèmes (sans tenir compte de la move semantics de C++1x): Premièrement, il y aura effectivement 2 CBullet qui seront crées (1 dans la fonction appelante, 1 dans le push_back, et une copie de la valeur de l'un vers l'autre). Deuxièmement, si ton reserve() n'est pas assez important, il y aura une copie de l'intégralité des éléments présents vers une nouvelle zone contiguë de mémoire. Et si tu cherches à augmenter la taille initiale de ton reserve(), plus il sera grand au départ, plus grande sera la copie lors de la réallocation. (et plus dure sera la chute)

Troisièmement, (et tu as offert un début de solution à ce problème), c'est que la suppression d'un élément au milieu d'un std::vector provoque la copie "un cran à gauche" de tous les éléments à droite de l'élément supprimé. (std::algorithm permet de supprimer en une passe plusieurs éléments et de mitiger l'effet d'une suppression de plusieurs éléments)

Voici une solution alternative qui, simplement en changeant de structure de stockage, se dédouane de plusieurs choses.

[modifier] Copie des CBullet

A la limite, si tu veux réutiliser des objets, mieux vaut utiliser des allocations sur le tas (avec new) et stocker le pointeur résultat dans un boost::shared_ptr. Tu hériteras ainsi d'une désallocation automatique des objets qui ne seront plus utilisés (comptage de références).

[modifier] Stockage des indices

Rien ne garantit dans un std::vector qu'un élément que tu push n'y est pas déjà présent. Si tes indices t'arrivent sans ordre précis, il vaudrait mieux les stocker dans un std::set. Il garatira l'unicité et quand tu itéreras dessus, ils seront par ordre croissant. (je simplifie volontairement la fonctionnalité du std::set)

Ce n'est pas non plus ce que je préconiserais.

[modifier] Utiliser std::slist

En fait, le principal problème du std::vector qu'on essaie de contourner ici, c'est la copie des éléments un cran à gauche lors d'une suppression. Les listes chaînées n'ont pas ce problème. Quand tu supprimes un élément au milieu d'une liste chaînée, les autres éléments ne changent pas de place, il n'y a pas de relocation.

Il te suffit donc de créer une liste chaînée (std::list ou std::slist) qui maintient dans l'ordre de création tes shared_ptr sur CBullet:

 std::slist<boost::shared_ptr<CBullet>> bulletsActifs;

Pour itérer sur tes éléments dans l'ordre, utilise un itérateur (begin() et end()). Ce n'est pas plus lent que sur un std::vector, et tu n'as pas à vérifier que tes bullets sont actifs (tu ne gardes dans cette liste que les bullets actifs). Pour garantir que tes éléments te seront fournis dans l'ordre où ils sont activés, il te suffit de faire un push_back quand tu insères un élément. Pour supprimer un élément t : bulletsActifs.remove(t). La comparaison de shared_ptr est ultra rapide.

Et pour gérer ta pool d'objets CBullet:

 std::slist<boost::shared_ptr<CBullet>> poolDeBulletInactifs;

Pour mettre dans ta pool un bullet non utilisé (fraîchement précréé ou désactivé), tu peux faire un push_front(). Pour obtenir un bullet non utilisé, tu peux faire un front()/pop_front(). Le reste de la liste ne bouge pas, du coup c'est ultra rapide.

Le choix entre std::slist et std::list est simple : est-ce qu'il peut t'arriver d'itérer à rebours sur ta liste? si oui, std::list permet une itération en avant comme à rebours. sinon, std::slist ne permet qu'une itération vers l'avant, mais le chaînage est moins complexe et suffit souvent.

Perso, je trouve ça beaucoup plus propre, et la perte de performance est minime. (Je dirais même inexistante, mais il je n'ai pas de chiffres pour appuyer une telle déclaration)

The Ultimate Koala


[modifier] commentaires à supprimer plus tard :)

hello,

Je ne trouve pas que ce soit un problème de std::vector, il a son utilisation. C'est tout simplement la différence d'utilisation d'un tableau et d'une liste, un std::vector est un tableau. l'avantage du tableau c'est son accès en temps constant à un index i, qui n'est pas nécessaire ici à priori. Si t'as des explosions, par exemple 100 particules, comme leur nombre est fixe tu préféreras les stocker dans un std::vector (voir même un tableau avec une approche C-like si c'est critique en performance, mais cela intervient pendant une phase d'optimisations).

Pour ce qui est des shared_ptr: n'oublies pas qu'il y a un overhead non négligeable même s'il n'est pas très important avec les machines actuelles, parfois ça peut devenir critique (si t'as beaucoup d'objets).

Personnellement je n'utilise les shared_ptr que très rarement, en général j'ai un manager qui garde la main sur les objets crées, ainsi mon allocation est localisée à en endroit précis.

...discussion à continuer... :p

Thelvyn


Edit: j'ai créé un thread sur le forum: http://forum.games-creators.org/showthread.php?p=66343

[modifier] Réponse au 2 commentaires ci -dessus

Le but de cet article c'est de montrer comment éviter certains pièges du vector, alors même qu'on peut etre tente de l'utiliser parce que c'est le seul container à garantir la continuité des éléments en mémoire (et à priori améliorer les performances mais j'ai jamais testé). L'histoire du shmup est un prétexte pour exposer qques techniques avec le std::vector. Maintenant c'est vrai que on peut discuter de l'interet pratique du truc. The Ultimate Koala

par exemple 100 particules, comme leur nombre est fixe tu préféreras les stocker dans un std::vector

ou dans un boost::array qui est un tableau C avec des outils C++ (iterateurs). C'est vraiment très pratique.

Deuxièmement, si ton reserve() n'est pas assez important, il y aura une copie de l'intégralité des éléments présents vers une nouvelle zone contiguë de mémoire. Et si tu cherches à augmenter la taille initiale de ton reserve(), plus il sera grand au départ, plus grande sera la copie lors de la réallocation. (et plus dure sera la chute)

C'est vrai que le risque c'est d'avoir une frame ou ca rame de temps à autre (mais quand tu realloues to nvector, tu realloues de 100 en 100). En mm temps si cela te permet d'avoir le reste du jeu un peu plus fluide je prends.

(bullets.push_back(CBullet bullet) qui est d'ailleurs syntaxiquement incorrecte) a deux problèmes (sans tenir compte de la move semantics de C++1x): Premièrement, il y aura effectivement 2 CBullet qui seront crées (1 dans la fonction appelante, 1 dans le push_back, et une copie de la valeur de l'un vers l'autre)

c'est du pseudo-C++ donc ok syntaxe incorrecte mais on comprends ce qu'il faut faire ^^ D'accord aussi avec le reste, c'est le vrai probleme du systeme. On peut imaginer que C++1x (je connaissais pas move_semantics, merci à toi) corrigera ca mais dans 30 ans. Après on peut aussi créer un CBullet static qu'on reconfigure différemment à chaque fois plutot que de le recréer. Après on peut allouer sur le tas mais à ce moment là il est clairement plus intéressant d'utilsier des containers intrusifs type boost::intrusive.

Rien ne garantit dans un std::vector qu'un élément que tu push n'y est pas déjà présent. 

Ce n'est pas un probleme pour un shmup ou tu ne risques pas de créer 2 fois la mm bullet.

Ta solution fonctionne également mais comme le souligne thelvyn, elle ajoute un overhead par bullet (un pointeur pour slist,2 pour list) + le poids du shared_ptr qui ne se justifie pas ici mais qui est un concept utile dans d'autres contextes (ca evite de faire une boucle pour desallouer tous les pointeurs du container).

Par contre, pour le remove dans la liste, mm si la comparaison est rapide, c'est pas génial génial.

Pour finir et 1 an après l'article, je signale que j'utilise maintenant boost::intrusive::slist (que je ne connaissais pas quand j'ai écrit l'article) qui apparait comme le meilleur compromis à tout point de vue. On a un surpoids de un pointeur par élément, mais ca permet d'etre bcp plus souple et de faire tout ce que tu détailles dans ta solution. La suppression est également plus rapide puisque l'élément sait ou il se trouve dans la liste.

[modifier] Snippet sur l'utilisation des listes chaînées en C++11

Avec la sortie de C++11, on peut commencer à utiliser des listes simplement chaînées de façon standard. Exemple ici: http://bluecosmos.tuxfamily.org/2012/02/bout-de-code-facilitant-lemploi-de-stdforward_list/



Les commentaires ci-dessus ont été laissés par des visiteurs.
Le gestionnaire du site n’est pas responsable de leur contenu. This site's operators can not take responsibility for the content of such comments.