Stockage de carte problématique

Version imprimable

01/08/2016, 20h13
Waether

Stockage de carte problématique
Bonjour,

J'ai récemment commencé un petit jeu 2D vu de dessus et avant même d'avoir quelque chose de jouable je bute sur le stockage de la carte.
Celle-ci étant plutôt grande je ne peux plus faire comme à mes débuts et travailler sur un simple tableau de cases contenant toutes les informations.
Actuellement ma carte est sous la forme d'une image BMP, ou la valeur d'une des couleurs de chaque pixels désigne un biome.
Avant d'y ajouter des objets comme les arbres ou des murs je pense revoir la façon dont je vais la stocker aussi bien en jeu que hors jeu (sauvegarde).

J'ai une idée et j'aimerais que vous me disiez ce que vous en pensez, voir me donniez des conseils sur comment vous gèreriez ce problème.

Plutôt que de stocker chaque cases et de lui affecter des valeurs ensuite je pensais plutôt lister dans chaque valeurs les cases lui appartenant.
Par exemple:
Code:

1 2 3 Terre: Case(0 -> 200)(215) Mer: Case(201 -> 214)(216 -> 400) Arbre: Case(15, 67, ...)
Cela devrait diminuer la taille des fichier de stockage mais forcera a faire plus de calculs à la volée en échange.

Après je ne sais pas si c'est une bonne idée de tout mettre en fonction d'une case, la position des PNJ étant un décimal.
Et même pour le décor pas sûre qu'un monde parfaitement aligné suivant des cases soit agréable à voir.

Je vois pas vraiment comment je pourrais à la fois stocker toutes ces informations sans prendre trop de place sur le disque dur et épargner le processeur lorsqu'il faudra savoir ce quels objets se trouvent à proximité du personnage.

Merci d'avance =)
02/08/2016, 09h03
darkman19320

Salut,

Tout d'abord, il faut voir ce que tu entends par trop de place, quelle est la taille de ta carte, sur quelle(s) plateforme(s) est destiné ton jeux. Par exemple si ta carte fait 500 par 500, c'est pas énorme en terme d'espace occupé sur un pc moderne mais pourrait être important sur des appareils embarqués (par exemple les montres connectées etc...)
Ensuite, ton idée de regrouper les éléments un ensemble d'indices de ta carte est une bonne idée. Tu peux essayer de stocker toutes ces informations en binaire plutôt qu'en format texte pour gagner un espace important ainsi qu'en temps de chargement. Cependant, il faudra faire attention à l'endianness.
02/08/2016, 11h06
jopopmk

Salut,

comme le dit darkman il va falloir une sacrée map pour avoir un fichier vraiment volumineux.
Pour exemple une BITMAP de 1k x 1k va peser un peu moins de 3Mo (je viens de tester).

Une méthode simple pour réduire la taille du fichier pourrait-être de simplement compresser ta BITMAP.
Les compressions/décompressions ne sont pas longues en temps de traitement (sur des fichiers de tailles contenues), et tu va drastiquement tomber la taille de ton fichier. Avec ma précédente BITMAP de 3Mo et une compression max (7zip lvl 9) on tombe à 4Ko.

Ensuite en reprenant l'idée sympathique de conserver tes info via une image tu peux regarder du côté des algo de compression d'image sans perte (la fiche wiki sur la Compression d'image). Mais cela me parait pas la solution la plus simple à mettre en place.

Enfin pour ta proposition ça va dépendre de ton implémentation et de tes maps.
En effet si tu as un damier d'arbres, par exemple dans une map carrée de 1024 de côté, tu te retrouveras à enregistrer 1024*1024/2 entiers de 4 octets (max size map carrée de 65536 de côté) soit 2Mo. En restant sur le principe de BITMAP tu pourras n'utiliser qu'un bit pour conserver le statut "arbre"/"pas arbre" et tu n'auras 128Ko d'utilisé à cet effet.

En conclusion, si j'étais à ta place, je ferais mon propre fichier binaire.
Je commencerais par énumèrer tout ce qui peut être représenté dans une case et trouver la taille minimum utile à chaque info.

Tu peux utiliser les bits pour les valeurs booléennes, par contre il faudra les regrouper par 8. Un entier positif peut-être ramené à un octet (char) si ta valeurs ne dépasse pas 255. Un réel te prendra 4 octets (float) si tu optes pour de la simple précision.
Et si le format sur mesure est toujours trop gros alors il reste la solution de la compression zip.
02/08/2016, 11h34
Médinoc

Le stockage façon "matrice creuse", ça ne marche pas si chaque case de la matrice contient quelque chose.
Si chaque case de ta carte est soit terre, soit mer, soit arbre, alors il est inutile de stocker une liste de terre, une liste de mer, et une liste d'arbres: tu ne gagneras rien.

Par contre, si tu as genre 90% terre, 5% mer et 5% arbre, ça peut devenir une bonne idée de présupposer que la carte est 100% terre et maintenir séparément une liste de mers et d'arbres.

L'autre solution, c'est de garder le format normal de ta carte, mais le compresser lors de la sauvegarde. Au niveau où tu es, un simple RLE suffirait. Mais si tu as accès à de bonnes bibliothèques graphiques, tu peux aussi garder ta carte sous forme d'un vrai bitmap, que tu compresserais alors en PNG.
02/08/2016, 11h35
ternel

Dans le cas du BMP indexé, le fichier contient à la fois une palette de couleur (par exemple: 0=#ff0000, 1=#0000ff), et une grille de pixels uniquement défini par des index dans cette palette.

Sans te forcer à cette forme, tu peux avoir une "palette" extérieure au fichier de carte.
La carte pourrait commencer par un en-tête avec un numéro de version du format (terriblement important) et le nom de la palette à utiliser.
De cette façon, la palette peut être choisie parmi plusieurs.

De même, les "palettes" pourront être définies par des fichiers externes, à l'instar des tileset de certains jeux (ou de RPG maker)

Merci à tous !

darkman19320, jopopmk > Par "plutôt grande" j'entendais un BMP de 1Go sur la dernière version générée et je compte la faire bien plus grande ^^ Après je ne vise pas de l'embarqué mais plutôt le PC moyen actuel.

Médinoc > Dans mon cas une case contient un biome (Terre, mer par exemple), mais peux aussi contenir un objet, par exemple une arbre mais ce n'est pas obligatoire.

Actuellement je pourrais loader directement le BMP, le sauvegarder et le convertir ensuite en jpeg pour gagner de la place, mais vu la taille de ma carte j'aurais plusieurs Go de RAM prit pour la stocker en cours et je ne souhaites pas avoir de fichier BMP temporaire lourds à quelque moment du programme. Ce serais gênant de demander à l'utilisateur d'avoir plusieurs Go de libre avant de démarrer le jeu.

leternel > Je comptais utiliser un système d'ID, après je penses que je testerais les deux pour voir ce qui est le plus efficace et facile à utiliser.

Après un peu de brainstorming je crois que j'ai choisi la façon dont je vais le faire.

Au niveau du stockage un fichier binaire sera parfait pour prendre un minimum de place.
Je penses segmenter ma carte en un certain nombre de parties.
Dans le fichier binaire le header donnera le nombre de parties et leurs emplacement dans le fichier, les parties quant à elles contiendront les informations les concernant.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 struct map_header { uint_32 header_size; uint_16 segment_number; uint_32* segment_offset; } struct segment_header { uint_8 segment_number; uint_32 segment_size; uint_32 segment_biome_offset; uint_32 segment_biome_entry_number; uint_32 segment_object_offset; uint_32 segment_object_entry_number; uint_32 segment_position_x; uint_32 segment_position_y; }
Du coup je ne devrais plus avoir de problème lors du chargement des cartes, ça ne devrais pas consommer trop, seule la zone de jeu actuelle est chargée.

Par contre au niveau du contenu "data"(biomes et objets) des segments je ne vois pas vraiment d'autre solutions.
Peut-être faire des rectangles plutôt que d'index à index.
par exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Pour cette carte : (T = Terre, M = Mer) 0 9 0 TTTTTTTTTT 1 TTTTTTTTTT 2 TTTTTMMMMM 3 TTTTTTMMMM 4 TTTTTTTMMM On aurait : Rect(Index_0 , Index_24) : T Rect(Index_5 , Index_19) : T Index_25 : M Rect(Index_26, Index_36) : M Rect(Index_27, Index_49) : M Rect(Index_30, Index_45) : T Index_46 : T // Dans le fichier cela pourrait donner quelque chose comme : <Index>-<Index><ID_Biome> 0-24T 5-19T 25-25M 26-36M 27-49M 30-45T 46-46T
Après dans cet exemple ce n'est pas très utile mais vous avez saisi le concept ^^

03/08/2016, 08h46
jopopmk

Re,

j'ai dû mal comprendre comment tu utilises ta BITMAP. Pour moi c'était un hack du format pour enregistrer du binaire sous forme matriciel. Mais avec 1Go qui serait insuffisant c'est que tu dois faire autrement.

Si tu dois passer par une compression (tu parles de JPEG) le zip 9 semble quand même plus adapté.

PS : pour optimiser un poil tes structures tu peux jeter un oeil à ce billet : Mémoire cache et optimisation du code.
Pas obligatoire mais toujours intéressant à lire.
03/08/2016, 08h50
Médinoc

Séparer la carte en plusieurs sous-cartes est une bonne idée.

Par contre:

Citation:

convertir ensuite en jpeg

Il ne faut pas utiliser de compression dégradante pour des données de jeu. Si tu convertis, ça doit être en PNG (voire en GIF ou encore en RLE8 pour une image 8 bits).

Edit: Note aussi que tu n'es pas obligé de charger ton gros bitmap en mémoire pour bosser dessus: Tu peux aussi le mapper à la place, si le format dans lequel tu l'enregistres est aussi le format dans lequel tu travailles dessus (ce qui implique de ne pas le compresser).
03/08/2016, 11h48
Bousk

Est-ce que tu parles du fichier en disque ou de la carte en mémoire ?
En disque, on s'en moque un peu, j'utilise maintenant Tiled pour les créer en les exportant en xml.
En mémoire, à priori tu peux voir large. Les PC récents ont tous pas mal de mémoire, et tu peux y aller avant de la faire exploser (dans un cas réel, mais si tu pars sur une carte de 1M*1M*1M où chaque case peut prendre 36 valeurs, tu fonces de toutes façons dans un mur). Et dans ce cas, un simple vector<unsigned char> ou vector<enum Case> suffira à la redessiner.
Ou bien une structure plus complexe pour l'animer du style vector<vector<Tile>> où struct Tile { int id; int duration; };
03/08/2016, 15h09
Waether

jopopmk > A la base j'ai toujours utiliser le bitmap de cette façon donc quand j'ai commencer ce jeu ci j'ai prit une bitmap, ce qui est loi d'être ce qu'il me faut.
Merci pour le lien je vais aller voir.

Médinoc > My bad j'avais pas vu que le jpeg dégradais les images.

Bousk > En fait des deux, a priori du côté RAM ça devrait passer sans trop consommé donc c'est bon, du côé HDD je veux simplement éviter un fichier temporaire qui serait ensuite compressé pour faire office de sauvegarde,
d'où la compresion directe de la carte a la main sans faire appel à un logiciel tier.
03/08/2016, 15h29
jopopmk

Citation:

Envoyé par Waether

[..]jopopmk > A la base j'ai toujours utiliser le bitmap de cette façon donc quand j'ai commencer ce jeu ci j'ai prit une bitmap, ce qui est loi d'être ce qu'il me faut.

"Toujours utilisé [..] de cette façon" : comment ? J'aimerai comprendre et je suis naturellement curieux :mrgreen:

Citation:

Envoyé par Waether

Médinoc > My bad j'avais pas vu que le jpeg dégradais les images.

Il existe une méthode JPEG sans perte d'après wiki. Perso je connais pas cet algo, je te laisse voir.
Sinon il existe d'autres méthodes de compression sans perte pour les images (toujours moins simple que le zip, cf. le point suivant).

Citation:

Envoyé par Waether

Bousk > En fait des deux, a priori du côté RAM ça devrait passer sans trop consommé donc c'est bon, du côé HDD je veux simplement éviter un fichier temporaire qui serait ensuite compressé pour faire office de sauvegarde,
d'où la compresion directe de la carte a la main sans faire appel à un logiciel tier.

Pour le zip je parle pas de logiciel tiers mais de bilbi (zlib ou libzip en C).
03/08/2016, 19h48
Waether

Citation:

Envoyé par jopopmk

"Toujours utilisé [..] de cette façon" : comment ? J'aimerai comprendre et je suis naturellement curieux :mrgreen:

Par exemple j'avais recommencer un pokemon dans le style des premières générations il y a un peu plus d'un an.
Je m'étais servi du rouge pour le sol, du vert pour de décor et du bleu pour les personnages et de l'alpha pour les interactions possibles.
Enfin à l'époque j'avais pas penser à utiliser une libraire externe pour le BMP et j'en avais refaite une à la main. Ça avait pas été de la tarte.

Citation:

Envoyé par jopopmk

Il existe une méthode JPEG sans perte d'après wiki. Perso je connais pas cet algo, je te laisse voir.

Je vais voir ça, peu de chance que je m'en serve pour ce projet mais c'est toujours bon à prendre ^^

Citation:

Envoyé par jopopmk

Pour le zip je parle pas de logiciel tiers mais de bilbi (zlib ou libzip en C).

Ça m'a l'air bien pratique je garde :D

Bon bah du coup j'ai plus ou moins terminer ma conception au niveau des cartes (sauvegardes et utilisation), plus que quelques trucs à peaufiner et je m'y met.
Si ça intéresse quelqu’un je devrais push quelques trucs sur GitHub de temps à autre.

Merci à tous pour votre aide c'était bien sympa de votre part =D