Bonjour.

Pour un jeu, j'ai une map (std::map, en C++) d'objet qui seront dessiné à l'écran, cette map a comme clef une pair de nombre (qui représente la case ou l'objet est dans le niveau) et comme valeur un objet.

J'aimerais savoir comment optimiser au mieux le stockage d'une map en 2D, enfin le problème c'est pas tant le fait d'avoir la map en mémoire (qui est de toute façon très légère) mais plutôt de gérer l'affichage des tout les objets présent dans cette map.

Avec une map normale (comme j'utilise actuellement) les seuls moyens (du moins que je vois) c'est soit d'afficher tout les objets (relativement bof si c'est une grande map avec beaucoup d'objets) soit de parcourir toutes les cases qui sont censé être visible et les dessiner (relativement bof si il n'y a pas beaucoup d'objets à dessiner, voir relativement bof tout court en fait).

La meilleur solution que je vois serait d'utiliser des chunks, un tableau 2D qui contiendrait des maps (les mêmes que celles que j'utilise actuellement) et pour chaque chunks visible ont dessine tout les objets de la map.

J'aimerais votre avis, si vous avez des meilleurs propositions, ou une taille de chunk optimale (par rapport au nombre maximum de case affichable par l'écran). Merci d'avance.

Je sais pas comment ton truc fonctionne, donc c'est pas sur que j'aide beaucoup.
Si il y a un lien direct entre les coordonnées d'un objet et sa position dans le tableau, et que tu as moyen de connaître les coordonnées les plus à droite/gauche/haut/bas visible à l'écran, tu peux facilement afficher uniquement les objets visibles à l'écran.
Je sais pas trop comment expliquer donc je vais te donner ce que j'ai fait dans mon jeu (c'est du Java, et l'origine de ma map est au point de coordonnées 0,0):

minX = (int)((camera.position.x - camera.zoom*camera.viewportWidth/2)/getTileWidth()
);

minY = (int)((camera.position.y - camera.zoom*camera.viewportHeight/2)/getTileHeight
());

maxX = (int)((camera.position.x + camera.zoom*camera.viewportWidth/2) /getTileWidth());

maxY = (int)((GamePlay.camera.position.y + camera.zoom*camera.viewportHeight/2)/getTileHeight
());

for(int i = minX; i<maxX; i++)
{
for(int j = minY; j<maxY; j++)
{
batch.draw(AllTextures[blocs[i][j]][state[i][j]], i*16, j*16, 16, 16);
}
}

Voila, je sais pas si ça peut aider car ton truc fonctionne peut être pas du tout pareil mais au moins j'aurais essayé

Pourquoi une hashmap plutot qu'un tableau en 2D pour stocker tout ça ?

hexabeast, c'est une des solutions que j'ai évoqué «soit de parcourir toutes les cases qui sont censé être visible et les dessiner» et que j'aimerais éviter vu que si il y a qu'un objet a affiché sur l'écran j'trouve ça bof de tout parcourir.

dark_drow, j'utilise une map déjà, je l'ai dis dans mon message, et si tu parle pour les chunks j'trouve ça plus logique d'utiliser un tableau (ou un vector ou n'importe) qui lui contiendra une map, on gagne du temps d'accès sans consommer trop de mémoire (vu qu'il devrait pas y avoir 500 chunks non plus).

justement je parlais de la map globale, je trouve ça un peu bizarre j'ai des doutes que ça soit très optimisé

"j'aimerais éviter vu que si il y a qu'un objet a affiché sur l'écran j'trouve ça bof de tout parcourir. "

A moins d'avoir une densité d'objets visibles à l'écran extrêmement haute, ça risque pas de causer d'énormes problèmes de performances, si?

Je veux dire si c'est de la forme:
for(int i = minX; i<maxX; i++)
for(int j = minY; j<maxY; j++)
if(!case[i][j].empty)
draw...

même si il y a 10 000 objets potentiellement visibles à l'écran et qu'en réalité il n'y en a qu'un seul à afficher, la boucle tournera 9 999 fois dans le vide, ce qui ne ralentira en rien le jeu, vu que pour la machine un nombre de cet ordre est dérisoire.

Donc je comprends pas trop le problème avec cette technique

Ou alors la version moche :
Tu fais un vector contenant tous les elements actif a afficher.

C'est ce que fait box2D pour gagner des perfs ; Uniquement update les objets ayant besoin de ca.

Ouais mais dans ce cas faut pas aussi stocker les coordonnées des objets? ça fait un peu "lourd" non?

Mais bon selon le contexte c'est peut être la meilleure solution, je sais pas...

Tu programme quoi pigeon ?

on parles de combien d'objet?

de memoire une map ce n'est rentable qu'a partir d'une cinquantaine d'objet. donc une fois que tu as un tilling de l'espace, la map pourrait bien devenir inutile. la contiguite memoire c'est bien!

"justement je parlais de la map globale, je trouve ça un peu bizarre j'ai des doutes que ça soit très optimisé"

map globale de quoi ? juste pour info, toutes les fois ou j'ai dis "map" dans mon message je parlais des std::map du C++.

"ce qui ne ralentira en rien le jeu, vu que pour la machine un nombre de cet ordre est dérisoire."

Je préfère éviter ça quand même

" Tu programme quoi pigeon ? "

Un jeu.

" on parles de combien d'objet? "

Environ 2000 objets en même temps sur l'écran maximum, en moyenne ça tournera plutôt dans la centaines voir quelques centaines, après le nombre d'objets maximum en tout (visible et non visible) j'voudrais le maximum possible quoi

Du coups godrik tu conseillerais quoi ? Je verrais finalement peut-être une map 2D qui contient des tronçons de 20*20 (représenté par un tableau), et les tronçons vide seraient tout simplement inexistant (sachant que les objets ont plus tendance à être regroupé, avoir un seul objet dans une zone de 20*20 serait quand même assez rare).

Un tableau2d de vecteur d'objet semble raisonnable.

http://jeux.developpez.com/tutoriels/tile-mapping-construction-niveau/presentation-generale/#LV

map globale de quoi ? juste pour info, toutes les fois ou j'ai dis "map" dans mon message je parlais des std::map du C++.

Oui HashMap si tu préfère. Si tu cherche un truc optimisé c'est pas terrible car tu doit stocker toutes les coordonnées en mémoire pour commencer, et ensuite deux cases adjacentes peuvent très bien être à l’opposée niveau mémoire (alors qu'un tableau ça reste des offsets)

dark_drow, bah pour moi c'est plus logique d'avoir une map de 2000 objets qu'un vecteur de 8000 objets dont 6000 ne servant à rien

Odvie, je peux pas simplement remplacer mes objets par des nombres

Godrik, un tableau de vecteur ? Mouais, je verrais bien