Quel conteneur pour une map?

[Crone123]

Bonjour,
Je développe actuellement un RPG, et j'ai besoin d'un conteneur pour stocker beaucoup d'objets pour la map. (Tout est positionné proprement sur des cases)
J'ai d'abord pris un std::vector mais le problème c'est qu'il fallait dans la boucle a chaque fois chercher dans tout le vector pour afficher les objets, et ça prends trop de temps, ça fait ramer le jeu.
Je suis donc passé sur un std::map<std::string, type_de_mon_obj> qui est plus pratique, mais pareil, ça a tendance a ramer...j'ai des chutes de FPS provenant de là, c'est injouable.
Je cherche donc un conteneur un peu comme les std::map, c'est a dire que je peux y accéder de la même façon, associatif en fait, mais plus rapide a l’exécution, ou bien, trouver une meilleure façon de l'utiliser.
J'ai pensé a la limite utiliser un std::map<sf::Vector2f, type_de_mon_obj> mais est-ce que je gagnerais des performances? Pas sur.

Existe-t-il, en dehors des bêtes tableaux standard, des objets dynamiques ou pour accéder a une case de ma map je demande:
obj[X][Y] ou X et Y sont des int, mais que le tableau soit géré dynamiquement par l'objet et supporte les nombres négatifs?
Ce ne serait pas associatif, mais ça serait sûrement encore mieux

Voilà, si quelqu'un pouvait m'aider pour ça, ça serait sympa parce que dans tous mes projets j'ai des gros problèmes avec les conteneurs et ça fait ramer le jeu...
Merci

[Ceylo]

Je m'y connais pas trop dans le domaine mais il me semble que les quadtree répondraient à ton problème (si le problème est vraiment là) : http://fr.wikipedia.org/wiki/Quadtree

[Crone123]

Merci pour ta réponse, mais je ne pense pas que ce soit ça dont j'ai besoin...
J'ai repensé plus précisément a l'objet dont j'ai besoin, et donc, ce qu'il me faudrait exactement, ce serait un tableau dynamique a 2 dimensions.
Sur lequel je peux avoir sa taille (comme un std::vector avec size()), et qui soit dynamique.
Exemple, je dis:
Tableau[82](104] = Pointeur_vers_un_obj;
Si cette case n'existe pas, il agrandi automatiquement le tableau

Sinon, au pire je prends un tableau standard que je fais assez grand (mais du coup, j'ai pas de taille illimitée, ni de fonctions pratiques sur l'objet, et ça bouffe beaucoup plus de ram...)

[Ceylo]

Dans ce cas le plus pratique serait probablement de faire ta propre classe à base de vector de vector de pointeur. Ainsi tu aurais ce que tu veux, une taille illimitée, une consommation mémoire en fonction de ton utilisation, et pour les fonctions pratique, à toi de les écrire.

Peut-être que tu peux aussi déjà trouver des classes de matrice en C++ sur le net.

[Crone123]

OK, Merci
Je vais essayer un truc a base de tableaux standard pour l'instant, si entièrement remplis ça me prends 1.2Go de ram, mais si ce n'est pas entièrement remplis, ça ne consomme rien
La map fera 1000*1000 en 32*32 je pense que c'est déjà bien (surtout a gérer en réseau) et ne prendra 1.2Go de ram que si la map empile toutes les textures possibles du jeu les une sur les autres sur les 1000000 de cases disponibles, donc voilà, merci pour votre aide

PS: Donc au final le jeu ne prendra pas plus de ram qu'avant

[lezebulon]

Tu veux stocker quoi dans ta map exactement?
Vu que apparement c'est des objets sur chaque case, je vois pas pourquoi un std::vector en 2D va pas marcher, pourquoi tu as besoin de boucler pour chercher un objet??
Moi pour mon RPG 2D j'utilisait un tableau 2D de pointeurs par map, donc même avec un million de cases tu t'en sors avec 8 Mo de RAM si il est vide (donc rien du tout), et puis je remplis ou vide les cases de ce tableau dynamiquement (genre si on ne ne voit pas la case, je détruis les objets graphiques associés)

[Koryushin]

Y a des petites optimisations qui existent pour booster un peu le fps.
entre autre n'afficher que ce qui est visible à l'écran, optimiser les boucles for() en faisant des ++obj au lieu de obj++ etc..

[Ceylo]

Y a des petites optimisations qui existent pour booster un peu le fps.
entre autre n'afficher que ce qui est visible à l'écran, optimiser les boucles for() en faisant des ++obj au lieu de obj++ etc..

oO
Je suis assez surpris par ta réponse. N'afficher que ce qui est visible à l'écran est loin d'être une petite optimisation. À moins que le module graphique ne gère ça de façon automatique, ça fait une énorme différence. En tout cas avec SFML 1.6 ce n'était pas géré automatiquement, je ne sais pas ce qu'il en est exactement avec SFML 2.0.

Et peux-tu expliquer en quoi un ++obj serait avantageux par rapport à un obj++ ?

[Crone123]

Oui, en fait je boucle pour chercher les objets avec des for parce que ce sont des tableaux de pointeurs.
Donc, j'utilise maintenant un tableau standard a 2 dimensions de 1000 * 1000 ça ne rame pas d'un poil

Je suis assez surpris par ta réponse. N'afficher que ce qui est visible à l'écran est loin d'être une petite optimisation. À moins que le module graphique ne gère ça de façon automatique, ça fait une énorme différence. En tout cas avec SFML 1.6 ce n'était pas géré automatiquement, je ne sais pas ce qu'il en est exactement avec SFML 2.0.

Bah, dans mon jeu actuel, j'ai pas essayé, je sais que de toutes façon ça diminue beaucoup les perfs, mais dans un autre de mes projets:
25 - 50 FPS a tout casser en affichant tout (et des bugs de fluidité, des rams, passage a travers les murs, et tout et tout), et 110  a 120 FPS en affichant uniquement ce qui est visible

entre autre n'afficher que ce qui est visible à l'écran, optimiser les boucles for() en faisant des ++obj au lieu de obj++ etc..

Actuellement, je fais ça, j'affiche par rapport au joueur, vu que maintenant le tableau standard a les objets bien rangés en fonction de leurs positions, je fais des for pour afficher tout ce qui sera visible a l'écran, c'est ultra rapide, c'est impeccable

Rien qu'au chargement de la map depuis un serveur de jeu, avant ça mettait 10s avec un std::map, maintenant ça met a tout casser une seconde avec le tableau standard

[lezebulon]

Et peux-tu expliquer en quoi un ++obj serait avantageux par rapport à un obj++ ?

Tu peux être 100% sûr qu'en release ça change rien...
En fait quand tu fais "obj++" tu copies l'ancien obj en backup, tu incrémente obj avec ++obj et tu retournes le backup de obj (pas incrémenté), donc en théorie tu fais une copie de plus.
Bon je pense que meme en config debug, pour les int et les itérateurs la différence de temps est meme pas mesurable

Oui, en fait je boucle pour chercher les objets avec des for parce que ce sont des tableaux de pointeurs.

J'ai rien compris à ce message, tu boucles sur quoi pour chercher quoi? Peu importe ce que tu cherches, tu devrais pas avoir un temps en O(n) mais en ln(n) dans tous les cas...

[Crone123]

Moi perso j'ai jamais fait de obj++ j'ai toujours fait des ++obj.
Sinon, pour le fait de boucler:
Exemple avec un tableau de sf::Sprite:

Code: [Sélectionner]

sf::Sprite *Tableau[1000][1000];
//On suppose que le tableau est bien déclaré, que tous les pointeurs sont remis a 0 et qu'on a mis (ou pas) des objets dedans. (via pointeur)
for(unsigned int compteur(0); compteur < 1000; ++compteur)
{
for(unsigned int compteur2(0); compteur2 < 1000; ++compteur2)
{
if(Tableau[compteur][compteur2] != 0)
{
Draw(*Tableau[compteur][compteur2]);
}
}
}Je met Draw tout seul, vous pouvez choisir un rendu si vous le souhaitez, pour ma part vu que mon jeu tourne dans une fenêtre Qt: Draw()  me suffit puisque mes objets sont dans la sf::RenderWindow

[lezebulon]

Aaaah ok, j'avais pas compris... dans ce cas-là c'est le plus rapide effectivement

[Koryushin]

Y a des petites optimisations qui existent pour booster un peu le fps.
entre autre n'afficher que ce qui est visible à l'écran, optimiser les boucles for() en faisant des ++obj au lieu de obj++ etc..

oO
Je suis assez surpris par ta réponse. N'afficher que ce qui est visible à l'écran est loin d'être une petite optimisation. À moins que le module graphique ne gère ça de façon automatique, ça fait une énorme différence. En tout cas avec SFML 1.6 ce n'était pas géré automatiquement, je ne sais pas ce qu'il en est exactement avec SFML 2.0.

Et peux-tu expliquer en quoi un ++obj serait avantageux par rapport à un obj++ ?

Bah c'est pas si dur que ça si on prend le temps, comprendre comment sfml fonctionne.
-Extraire le rectangle englobant de la vue courante,
-Soit tester si les Sprites de notre map sont dans le rectangle de la vue. (Fonction sf::Rect::Intersects())
-Soit s'arranger pour que nos boucles for() bouclent en fonction du rectangle de la vue.

[Bigz]

A propos du post et pré incrémentation, comme l'a dit Lezebulon, la post incrémentation fait une copie en backup en plus de la post. De la sorte :

const Foo& Foo::operator++() // called for ++i
{
    this->data += 1;
    return *this;
}

const Foo Foo::operator++(int)  // called for i++
{
    Foo tmp(*this);
    this->data += 1;
    return tmp;
}

Autrement dit, sur un int, on s'en bat les reins. Même si ça reste une (très très très) légère optimisation, d'utiliser la pré incrémentation. D'ailleurs, je serais pas étonné que les compilo optimisent ça tout seul mais j'en suis vraiment pas sur.

Par contre, si l'objet est un peu plus compliqué qu'un int, il faut se rappeler qu'un appel au constructeur par copie peu être coûteux (c'est aussi pour ça qu'on évitera dans de nombreux cas des retours de fonctions par valeur, qui utilisent le constructeur par copie, au profit d'un retour par référence ou pointeur).

[Laurent]

Autrement dit, sur un int, on s'en bat les reins. Même si ça reste une (très très très) légère optimisation, d'utiliser la pré incrémentation. D'ailleurs, je serais pas étonné que les compilo optimisent ça tout seul mais j'en suis vraiment pas sur.

Pour les types natifs, post et pré-incrémentations donnent le même code, il n'y a aucune différence.

Par contre, si l'objet est un peu plus compliqué qu'un int, il faut se rappeler qu'un appel au constructeur par copie peu être coûteux

Pour les types incrémentables habituels qu'on utilise dans les boucles, autre que les types natifs (donc les itérateurs), c'est vraiment négligeable. Franchement, avant de commencer à optimiser ce genre de chose, il y a des questions bien plus importantes à se poser. Ne gaspillez pas trop votre temps sur ce genre de détail insignifiant.