Tile Mapping et structure de donnée

[Black Templar]

Bonjour à tous,

Je souhaite me mettre au "Game Programming" et j'ai envie de commencer par étudier la technique de TileMapping pour un RPG style Pokémon ou Zelda.

Il y a quelques temps, j'ai déjà fait un Mario et un Packman avec cette technique. Rien de très compliqué : je stockais la map dans un tableau 2D.

Mon soucis, c'est qu'avec un jeu style Zelda, c'est que la map peut vite devenir très grande et elle n'est pas rectangulaire, mais de forme indéterminée.
C'est pourquoi je recherche une structure de donnée adaptée à ce type de map.

* Avec un tableau 2D, je gâche beaucoup de mémoire.

* J'ai donc pensé à une structure d'arbre quadratique (ou quadrilatère, je ne sais pas comment ça s'appelle) : chaque noeud (tile) possède un pointeur vers ses 4 voisins connexes. Ainsi, on peut dessiner à l'écran le rendu en utilisant un algo de diffusion.
Avantage, on ne gâche pas de mémoire, l'affichage est super efficace.
Le soucis, c'est que la création de la map avec un éditeur de map n'est pas trivial... (l'utilisateur peut ajouter les tiles comme bon lui semble). La génération de la map demande donc beaucoup de calcul.

* J'ai pensé à une autre solution qui serait de stocker chaque tile dans une liste (chainée).
On ne consomme pas de mémoire inutilement, mais pour l'affichage, on est obligé de parcourir l'intégralité de la liste pour savoir quelle tile afficher... donc perte de temps...
Pour le générateur de map par contre, c'est super simple à concevoir ainsi

J'ai donc 3 méthodes :

• Tableau 2D : Gâche de la mémoire, très rapide à afficher
• Arbre quad : Pas de gâchis de mémoire, très rapide à afficher, mais conception de la map ardu
• Liste chainée : Pas de gâchis de mémoire, plus long à l'affichage

Je les implémenterais bien toutes les trois pour comparer les perfs en espace et en temps, mais je voulais d'avoir l'avis d'experts
Car comme le tileMapping est un sujet largement rependu, je suis sûr qu'il existe des structures de données plus utilisés que d'autres


Une astuce pourrait être d'utiliser une autre structure de donnée (liste chainée) pour l'éditeur de map, puis compilé la map pour qu'elle soit facilement lue par le jeu qui lui utilisera une structure d'arbre quad.

Qu'en pensez-vous ?
Black Templar

[Koryushin]

Pourquoi ne pas utiliser un tableau 2D de Zones ( ou un std::vector avec certains calculs cela revient au même) et définir une zone comme étant une tilemap.
Pour m'entrainer j'ai repris le tuto de la sdz que j'ai réadapté en c++. Ma zone est beaucoup plus grande que l'écran mais j'optimise en n'affichant que ce qui est sensé se trouver à l'écran. Ensuite arrivé au bord de ma zone je change de zone. Et ces zones sont stockées dans un tableau 2D et je n'est pas de perte de performances.

Pour résumer ce prendre la tête maintenant est une bonne chose mais pas forcément utile au vue de nos machines actuelles. Code comme tu le sens et si y a besoin d'optimiser regarde ce que tu peux faire à ce moment là.

[Black Templar]

Pour mieux comprendre ce que je souhaite faire :
J'ai une map "à ciel ouvert" comme celle-ci : http://www.vgmaps.com/Atlas/GB-GBC/Pokemon-GSC-Kanto.png
Avec un tableau2D (ou vector), je prend trop de place en mémoire (les zones blanches sont inutiles, mais bel et bien stocké)

Pourquoi ne pas utiliser un tableau 2D de Zones ( ou un std::vector avec certains calculs cela revient au même) et définir une zone comme étant une tilemap.

Intéressant.
ça permet de ne pas consommer trop de mémoire inutilement (si les tileMap sont bien découpés).
Par contre, lorsque le perso arrive au bord d'une tilemap, il faut charger la seconde en mémoire et gérer les deux tilemap en même temps... ça complique tout de même un peu les choses.

Pour résumer ce prendre la tête maintenant est une bonne chose mais pas forcément utile au vue de nos machines actuelles. Code comme tu le sens et si y a besoin d'optimiser regarde ce que tu peux faire à ce moment là.

Je suis d'accord, si une implémentation ne me convient pas, je pourrais toujours recoder le modèle.
Mais bon, autant implémenter directement ce qui me semble le mieux.


Merci pour ta réponse.
Je vais déjà commencer à coder l'éditeur en stockant les tiles dans une liste chainée. Je pourrais ainsi me rendre compte des perfs.

[Koryushin]

Je comprends mieux le problème maintenant un petit dessin aide beaucoup 

Perso j'utiliserai un vector de zone. Chaque zone connaitrait la(les) zone(s) qui lui sont accolé et les chargerait.
un petit schémas vite fait pour expliquer.

0   Z1 Z2
Z3 Z4  0
Z5  0   0

les Zx correspondent aux zone pleines et les 0 des zones vident.
Si mon perso se trouvent dans la zone Z1 je charge Z2 et Z4 mais ne dessine que Z1.
Si mon perso est en Z2 je ne charge que Z1 et dessine Z2.
Et ainsi de suite. Chaque zone connait sa ou ses voisines.

C'est primitif mais ça fonctionne. Ou alors j'utiliserais un tableau 2D de pointeurs vers des Zones et les zones vident je les mettrai à NULL.

Quelqu'un aura peut être une meilleur idée. Courage

[Black Templar]

Perso j'utiliserai un vector de zone. Chaque zone connaitrait la(les) zone(s) qui lui sont accolé et les chargerait.
un petit schémas vite fait pour expliquer.

0   Z1 Z2
Z3 Z4  0
Z5  0   0

les Zx correspondent aux zone pleines et les 0 des zones vident.
Si mon perso se trouvent dans la zone Z1 je charge Z2 et Z4 mais ne dessine que Z1.
Si mon perso est en Z2 je ne charge que Z1 et dessine Z2.
Et ainsi de suite. Chaque zone connait sa ou ses voisines.

Oui, j'avais bien compris ça.
ça serait assez efficace sur une map comme celle de mon poste précédent.
Par contre, pour une map plus complexe, ça risque d'être moins trivial.
La question : est-ce que j'ai besoin d'avoir une map complexe ou non.
En tout cas je vais implémenter ton idée pour voir !

Ou alors j'utiliserais un tableau 2D de pointeurs vers des Zones et les zones vident je les mettrai à NULL.

Hum. Aussi. On perdrait juste 4 octets par case non utilisé (pour le pointeur), ce qui est quedale