Manager de tour dans un tower defense

Version imprimable

22/08/2011, 12h32
dream25

Manager de tour dans un tower defense

Bonjour à tous.
Je vous explique mon problème. Je suis en train de développer un petit tower defense sur pc. Je possède une classe abstraite CTour qui renferme les propriétés de base d'une tour classique. J'ai ensuite plusieurs classes dérivées de cette classe (par exemple tour de feu, tour de glace etc...). Je peux faire référence à chaque tour grâce à une liste de pointeurs CTour* qui regroupe tous les pointeurs de mes tours.

Normalement pour ajouter une tour, j'ai juste à réaliser un "push_back" de la nouvelle tour à la fin de cette liste. Mais voilà je souhaite éviter au maximum les allocations dynamiques en cours de programme. Je voudrais du coup créer un manager de tours qui allouerait au tout début de mon programme toutes mes instances et qui s'occuperait de me renvoyer un pointeur sur une de ces instances lorsque je déciderais d'ajouter une nouvelle tour.

Mon problème est le suivant : comment réaliser l'allocation de mémoire pour ce manager. Je ne peux pas par exemple faire ceci : new CTour[100] car ma classe CTour est abstraite. De plus Je ne connais pas à l'avance le type de tour et les quantités dont je vais avoir besoin.

Une solution serait d'allouer 100 fois chaque type de tour mais je ne pense que ce soit une bonne solution.
Sinon j'avais pensé à créer une union de toutes mes classes de tours et d'instancier 100 fois cette union. Ainsi la place en mémoire de la plus grosse tour de l'union serait utilisée pour l'allocation au début de programme, et je pourrais caster cette mémoire en le bon type de tour lorsque que j'ajouterais une tour de feu par exemple. Est-ce une bonne solution ou y'en a-t-il une meilleure à laquelle je n'ai pas pensé ?

Bonjour,

j'ai la vague impression que tu fais tu C with classes :mouarf: En C++ tu pourrais par exemple faire un :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <vector> class CTour {}; class TourFeu : public CTour {}; int main() { std::vector<CTour*> tours ; tours.reserve(100); // Ne sert pas a grand chose car on alloue seulement pour des pointeurs. tours.push_back( new TourFeu() ); return 0; }
Et voila :) Mais attention, avec un .reserve tu ne peux pas accéder au élément via [] (tours[5]) s'ils n'ont pas déjà été "pushé". Utilise .resize() si tu veux faire ça.

EDIT : Code édité selon la remarque de Flob.
EDIT2 : Code édité selon la remarque de Cob.

22/08/2011, 13h31
Flob90

@Trademark: Tu oublies les pointeurs, sans eux pas de polymorphisme (ou référence mais ca ne va pas avec les conteneur).

@OP: Le "reserve" va te permetre d'allouer en avance la mémoire nécessaire pour stocker les pointeurs dans le conteneur. Pour ton problème, regardes du coté des allocateurs pour petits objets ou des pools de mémoire (Loki::SmallObject, boost::pool par exemple), cependant fait des tests c'est le seul moyen de savoir si ca optimisera ou non ton code.
22/08/2011, 15h16
cob59

Honnêtement, une allocation dynamique de tes CTour te semble-t-elle vraiment pénalisante ?

Je doute que l'utilisateur se mette à créer/détruire des centaines de CTour à la seconde, quand bien même le GUI le lui permettrait. Ça me semble être le parfait exemple d'une optimisation prématurée qui ne t'apportera que des ennuis.

Pour ce qui est de l'exemple de TradeMark, le reserve() ne va pas servir à grand chose puisqu'il allouera seulement une série de pointeurs vers des objets CTour, et pas les objets eux-même.
22/08/2011, 15h17
dream25

En fait ce n'est même pas que je veux optimiser mon code (même si au final c'est le résultat) c'est juste que par principe, si on m'oblige à ne pas faire d'allocation dynamique au cours du jeu je voudrais savoir comment gérer ça. Il doit bien exister un moyen pas trop compliqué ? Je suis en train de créer mon moteur et j'aimerai avoir la solution car je compte tout gérer via des managers (cameras, particules, objets...)

Si j'utilisais un seul type de tour, ce sera plié avec un new CTourDefeu[100] en début de programme et un tableau de booléens pour dire si oui ou non la tour est libre. Mais là avec l'héritage je ne m'y connais pas assez pour savoir comment m'y prendre.
22/08/2011, 15h57
cob59

Un pool serait une bonne solution. (boost::pool est cité au dessus)
Tu crées autant de pool qu'il existe de classes non-abstraites héritant de CTour. Tu te bases sur l'exemple de Trademark sauf qu'au lieu d'utiliser new TourFeu() tu utilises le pseudo-constructeur de ton pool qui te retourne un pointeur de type TourFeu*. Idem pour le destructeur.
22/08/2011, 16h47
dream25

D'accord merci je vais regarder ça, ça a vraiment l'air d'être ce que je cherche. Et théoriquement, si je n'ai pas le droit d'utiliser des libs comme boost, comment le faire à la main ? (oui je sais je suis un peu ennuyeux mais j'aimerais bien comprendre comment gérer ce genre de problème de mémoire, cast, héritage).

Il me semblait que faire une union de tous mes types de tour et d'allouer 100 fois cette union était une bonne solution ou bien est-ce horrible ? Qu'en pensez-vous ?
22/08/2011, 18h53
JolyLoic

Citation:

Envoyé par dream25

Il me semblait que faire une union de tous mes types de tour et d'allouer 100 fois cette union était une bonne solution ou bien est-ce horrible ? Qu'en pensez-vous ?

Horrible !

Ça ne marche pas en C++ actuel (en C++11, il y a eu des modifs, mais je ne sais plus trop lesquelles, et donc ne sais pas si ça marcherait). On ne peut pas mettre de classes dans une union. Et puis en terme d'efficacité, si une de tes tours demande 100 fois plus de mémoire que les autre, c'est pas top. Et même si ça marchait, ça n'éviterait pas l'allocation à l'exécution, pour peu que les tours utilisent en interne de la mémoire dynamique.

Si vraiment une solution à base de CTourDefeu[100] te semble acceptable et préférable à l'allocation dynamique (tu dois voir à mon ton que mon avis diffère sur ce sujet), une solution à base de CTourDefeu[100] + CTourDeGlace[100] + CTourDeRayonPsy[100] devrait te convenir et répondre à tes critères, non ?

Quand je lis

Citation:

si on m'oblige à ne pas faire d'allocation dynamique au cours du jeu

je me demande un peu comment tu ferais si on t'imposait de ne pas utiliser le caractère 'e' dans l'ensemble de ton code source. Les deux contraintes me semblent a priori avoir à peu près le même niveau d'intérêt...
22/08/2011, 20h15
Klaim

Une façon bien plus efficace de gérer tes tours :

D'abord, au lieu d'avoir un type par tour, fait un type par type de tour, disont une "catégorie de tour".
Elles hériteraient toutes d'une interface commune (une classe de base commune avec le minimum nécessaire). (par exemple "class TowerType" et les enfants "TowerType_Fire", "TowerType_Healer" etc.)

Elles surchargeraient au moins une function virtuelle de mise à jour qui prendrait en paramettre un objet tour. (par exemple "TowerType::update( Tower& tower )")

Tes instances/objets tours seraient toutes du même type C++ (par exemple "class Tower"), MAIS contiendraient chacune un pointeur (ou quelque chose faisant référence à) une "catégories de tour".

Enfin, ordonne tes listes de tours à mettre à jour par familles de types.

Conséquences :

- tu peux créer des nouvelles catégories de tours sans toucher au code des tours elles-mêmes
- le code spécifique aux différentes catégories de tours sont dans des types spécifiques aux différentes catégories de tours. les objets tours eux-même sont indépendants et ne donnent que l'état d'une tour unique
- toutes tes tours sont du même type DONC tu peux les mettre dans une array par exemple, et donc parcourir la mise jour rapidement.
- si ton parcour de mise à jour est fait de manière à ce que tes tours soient groupées par catégories, la mise à jour sera plus rapide (pour différentes raisons qui se résume à "la cohérence du cache" si je ne me trompe pas de terme.
- tu pourras faire en sorte que certaines catégories de tours peuvent être implémentées via du script, sans avoir a toucher (encore une fois) le code tes tours elles mêmes.
- tu pourras aussi potentiellement faire des combinaison de catégories de tours -je me répète- sans changer le code des tours elles mêmes.

Globalement, ça te simplifiera la vie.

Enfin je trouve.
22/08/2011, 21h12
3DArchi

Salut,

Citation:

Envoyé par JolyLoic

je me demande un peu comment tu ferais si on t'imposait de ne pas utiliser le caractère 'e' dans l'ensemble de ton code source. Les deux contraintes me semblent a priori avoir à peu près le même niveau d'intérêt...

tout un roman cette disparition.

Citation:

Envoyé par Klaim

Une façon bien plus efficace de gérer tes tours....

+1
un Design Pattern Stratégie, en gros
23/08/2011, 01h33
dream25

Citation:

Envoyé par JolyLoic

je me demande un peu comment tu ferais si on t'imposait de ne pas utiliser le caractère 'e' dans l'ensemble de ton code source. Les deux contraintes me semblent a priori avoir à peu près le même niveau d'intérêt...

Oui je comprends ton point de vue, c'est juste qu'après un stage dans une boîte de jeux vidéo consoles on m'a bien fait comprendre que les new en dehors des constructeurs c'était pas top, du coup j'essai de voir comment résoudre le problème. Et avoir les données adjacentes en mémoire est plus performant.

En tout cas merci beaucoup pour ce pattern stratégie, je vais le mettre en place.
23/08/2011, 08h06
cob59
Citation:

Envoyé par dream25

on m'a bien fait comprendre que les new en dehors des constructeurs c'était pas top, du coup j'essai de voir comment résoudre le problème. Et avoir les données adjacentes en mémoire est plus performant.

Non, ce qui n'est pas top c'est ça :
Code:

1 2 3 4 5 6 7 std::list<CTour*> tours; for (int i=0; i<1000000; ++i) { tours.push_back( new CTourFeu() ); //... }
Ici on peut effectivement comprendre l'intérêt de passer par un pool. En effet l'alloc dynamique prend un temps non-négligeable dans une itération, et ces itérations sont nombreuses.

Ton cas est différent.
La création dynamique d'un objet CTourFeu prendra un temps vraiment négligeable (peut-être 1/100 ou 1/1000) en comparaison du temps requis par ton interface graphique pour interpréter le clic de l'utilisateur sur le bouton "Créer une Tour de Feu". Je crois que tu gaspilles ton temps et tes efforts pour grappiller quelques microsecondes, alors qu'il y aurait sûrement des optimisations plus primordiales.
23/08/2011, 11h21
dream25

D'accord cob59, l'exemple des tours n'est peut être pas le meilleur et je comprend désormais que ce n'est pas une petite allocation dynamique qui est à proscrire mais plusieurs d'un coup. Néanmoins je cherchais quand mêmeune solution à ce problème que je me pose souvent. Pour mon système de particules par exemple.

J'ai une particule abstraite et plusieurs particules dérivées (particule billboard2D, particule 3D, particule 3D tournante). Je vais surement en créer plein à la suite. Pour éviter les allocations dynamiques je peux me faire 3 arrays différents pour gérer toutes mes particules, ou bien je peux utiliser le pattern strategie ici aussi.
23/08/2011, 13h14
Klaim

Citation:

Ton cas est différent.
La création dynamique d'un objet CTourFeu prendra un temps vraiment négligeable (peut-être 1/100 ou 1/1000) en comparaison du temps requis par ton interface graphique pour interpréter le clic de l'utilisateur sur le bouton "Créer une Tour de Feu". Je crois que tu gaspilles ton temps et tes efforts pour grappiller quelques microsecondes, alors qu'il y aurait sûrement des optimisations plus primordiales.

Heu non je ne suis pas d'accord, dans un jeu le moindre new peu avoir un impact violent sur la réactivité/le framerate donc je ne recommanderai pas de faire des new dans la boucle principale du jeu. Contrairement à ce que tu crois, les new/delete se voient généralement assez vite dans un jeu.

En revanche, tu n'es pas forcé d'utiliser un pool de mémoire, juste un vecteur d'objets déjà alloué (std::vector avec reserve( MAX_TOWERS_COUNT ) ) doit suffire.

Ensuite tu fais en sortes d'avoir une information "est-ce que la tour est utilisée actuellement dans le jeu". Si oui, tu la gères (avec une liste (un vecteur) de pointeurs vers les tours qui existent dans le jeu par exemple) et sinon tu les laisses jusqu'a ce que l'utilisateur demande a créer une nouvelle tour, auquel cas tu en actives une.

Il faut limiter au maximum les manipulations mémoire dans les boucles principales de jeu, c'est réélèmenet source de perte violentes de performance, et c'est visible très vite.

Si tu veux un exemple ou j'ai créé un prototype de shoot où quand le joueur tire, les balles sont activées et gérées puis desactivées quand on en a plus besoin : http://code.google.com/p/radiant-las...source/browse/

Ca te donnera peut être des idées de comment organiser le code 1. de manière simple mais 2. en évitant les manips mémpoire quand le jeu tourne.

Le souci avec la préallocation des objets, c'est que pour simplifier, ils doiventtous être du même type.

D'où l'utilitée du pattern Strategy cité au dessus : tu crées ta reserve de Tower dans un vector, et tu les utilises avec chacunayant un pointeur vers sa catégory de Tower, qui est un objet unique.
23/08/2011, 13h41
dream25

Merci vraiment klaim pour confirmer ce que je pensais et pour ta solution c'est exactement ce que je cherchais !
23/08/2011, 15h49
cob59

Citation:

Heu non je ne suis pas d'accord, dans un jeu le moindre new peu avoir un impact violent sur la réactivité/le framerate donc je ne recommanderai pas de faire des new dans la boucle principale du jeu. Contrairement à ce que tu crois, les new/delete se voient généralement assez vite dans un jeu.

Justement, la création d'une instance de TourFeu doit se situer en dehors de la boucle principale. C'est l'équivalent d'un slot Qt : une simple fonction qui se lance en réaction à un évènement (le joueur a cliqué sur "créer une tour de feu") et qui n'a pas de contrainte Temps-Réel. Ça prend le temps que ça doit prendre, contrairement au rafraîchissement de l'affichage qui lui doit s'exécuter en un temps donné sous peine de voir chuter le framerate. En fait, qu'une tour se crée en 1ms ou 3s (je caricature), ça n'aura aucune influence sur le framerate.

Citation:

En revanche, tu n'es pas forcé d'utiliser un pool de mémoire, juste un vecteur d'objets déjà alloué (std::vector avec reserve( MAX_TOWERS_COUNT ) ) doit suffire.

Ensuite tu fais en sortes d'avoir une information "est-ce que la tour est utilisée actuellement dans le jeu". Si oui, tu la gères (avec une liste (un vecteur) de pointeurs vers les tours qui existent dans le jeu par exemple) et sinon tu les laisses jusqu'a ce que l'utilisateur demande a créer une nouvelle tour, auquel cas tu en actives une.

Je ne vois pas beaucoup de différences entre un pool et ce que tu décris ici :mrgreen:
Sauf qu'un pool aurait l'avantage d'être thread-safe.
23/08/2011, 19h42
Klaim

Citation:

Envoyé par cob59

Justement, la création d'une instance de TourFeu doit se situer en dehors de la boucle principale. C'est l'équivalent d'un slot Qt : une simple fonction qui se lance en réaction à un évènement (le joueur a cliqué sur "créer une tour de feu") et qui n'a pas de contrainte Temps-Réel. Ça prend le temps que ça doit prendre, contrairement au rafraîchissement de l'affichage qui lui doit s'exécuter en un temps donné sous peine de voir chuter le framerate. En fait, qu'une tour se crée en 1ms ou 3s (je caricature), ça n'aura aucune influence sur le framerate.

Non, ça aura une influence.

Activer une nouvelle tour, oui, l'allouer, non.

Essaie pour voir, avec un jeu complet, tu veras l'impact d'un un simple new sur un objet de taille non-triviale sur le framerate.

On ne voit pas l'impact sur un outil mais on le voit dans un jeu.
L'exemple des signaux de Qt n'es pas directement lié : dans ton signal, si tu crée des objets, c'est comme si dans ta boucle tu crées des objets aussi, certes sur un seul "tick", mais ça a bien un impact, pour peu que ton jeu commence a etre gourmand en se faisant compléter.

Cela étant dit, on peut toujours recourir a cette solution pour juste faire marcher le truc vite fait, vérifier que tout est correcte et ensuite optimiser en faisant des reserves de tourelles au lieu de les créer à la volée.

Mais pour un jeu complet, quel qu'il soit, éviter les allocations pendant le jeu c'est éviter les fluctuations de framerate.

Cela étant dit, si TourFeu est la classe de catégorie pour els tours de feu, mais pas la classe des tours, comme je l'ai décris, elle sera de toutes façons créée au départ.

Citation:

Je ne vois pas beaucoup de différences entre un pool et ce que tu décris ici :mrgreen:
Sauf qu'un pool aurait l'avantage d'être thread-safe.

Pour le coté thread-safe, ça dépends de l'implémentation du pool mais je suis d'accord si c'est prévu pour.

Pour la différence : le vector tu peux le prendre direct sans ajouter de lib et juste implémenter ton truc sans te poser d'autres question que "combien je réserve au départ".

En gros, c'est un pool "a la mc guyver", mais c'est effectivement le même principe. :aie: En fait pour être plus précis, pour quelqu'un qui ne veut pas se prendre la tete tout de suite avec les détails d'allocation, un vector est plus facile a comprendre qu'un pool. L'utilisation efficace d'un pool nécessite de savoir plein de choses. Ou d'en avoir un "générique" pour la plateforme en cours, ce qui est toujours possible.

(note : le pool de boost est pas top malheureusement, mais il est en cours d'amélioration d'après ce que j'ai lu...)