Dans le cadre d’un projet de jeu 2D personnel, j’ai eu besoin de créer une carte 2D.

Il y a plusieurs façons de la faire:
La plus naïve (mais qui fonctionne) est de créer un tableau à 2 dimensions de la taille de la carte total. Dans ce cas la carte est coupable en sous unités atomique, qui sont appelées Tuile( Tile en anglais).

Unités de base

On obtient alors un code de ce genre:

Cette méthode est rapide à mettre en place, et sera suffisante dans un certain nombre de cas (tétris, pacman, ect…).

Cependant, dans mon cas cela ne suffisait pas. En effet, j’ai besoin d’une carte “infinie”, et qui possède tout de même un système de coordonnées, négatives y compris.

Le problème devient alors tout autre.
Le point commun, est que dans les 2 cas, la carte est coupable en petit morceau (Tuile). On va donc commencer par créer cet class, bien que assez flou pour le moment, on sait ceci:

• Elle possède des coordonnées
• Une image
• Une forme

On ne s’attardera pas sur le skin de cette cellule, car spécifique à chaque carte. On peu alors faire:

Tile.hpp

Tile.cpp

Grouper ces unités ??

Ok On a maintenant notre unité de base. Pour pouvoir avoir une carte infinie, in faut que cette carte puisse être chargée / libérée à la volée.

On à alors le choix suivant:

• Crée/supprimer les tuiles dont on a besoin une à une en temps venu
• Regrouper les tuiles par groupes de X*Y et les gérées(crées/supprimer) toutes en même temps.

Je ne me suis pas attardé longtemps sur ce choix, et ai choisis l’option 2, car je pense que niveau perf, c’est bien meilleur.
Reste à déterminer X et Y. Du fait de l’alignement en mémoire, ce seront des 2^n (2,4,8,16,32,65,128, ...) afin de restreindre celle ci au minimum. Ensuite je me suis posé la question suivante:

«Est il utile que X et Y soit différent?»

La réponse est non.

En ce qui concerne sa valeur, elle reste assez flou. Cependant, je pense que faire des zone 2×2 ou 4×4 à peut d’utilité, et qu’en faire de 128×128 est trop gros, car cela assez lent lors de sa création (ça reste à prouver..).

Vu que sa valeur reste un peu flou je vais le stoker dans une constante, MAP_AREA_SIZE.

On peut alors l’implémenter de cette façon: (l’utilité des templates est pour rendre la classe réutilisable)

Area.hpp

h4. Area.tpl (vu que l’on peu pas mettre dans un .cpp à cause des templates)

h3. Accéder aux sous zones

Bon on a maintenant nos regroupement de tuiles par zones, reste à lier ces zones entre elles, pour y accéder/créer/supprimer.

Un choix est à faire pour les stoker:

• tableau
• vecteur
• liste
• arbre rouge/noire
• arbre quart
• autre arbre ..
• map
• table de hash

Ce choix, est pas évident à faire, il faut donc situer les besoins:

• accès le plus rapide à un élément
• changement de taille fréquent
• pas de doublons

Les doublons sont gérer ailleurs, il seront donc pas pris en compte. Cependant, du fait du changement de taille fréquent, on peu éliminer tableau et vecteur. Ensuite vient la rapidité d’accès. On peu donc éliminer les liste car trop lent (O(n)). Les arbre et map eux sont de façon générale en O(log(n)), table de hash en O(1) à O(n) au (rare) pire cas.

Mon choix c’est donc fait sur la table de hash, et sont implémentation dans la lib standard c++, à savoir std::unordered_map.

Choix de la clef

Il va donc me falloir une clef pour la hash map. Ce qui nous vient directement à l’esprit, est d’utiliser les coordonnées auxquels on veux accéder, soit celle de la zone.

Un peut de maths

Il vas nous falloir un moyen de passer des coordonnée de monde réel (celles des tuiles) à celles des zones. Rappelons que les zones regroupent MAP_AREA_SIZE x MAP_ARE_SIZE tules.

La manière la plus simple est de diviser par MAP_AREA_SIZE les coordonnée du monde et de garder la partie entière. Cependant cela nous pose un problème autour des points qui ant un 0 en x ou y.

Exemple pour mieux comprendre:

avec MAP_AREA_SIZE = 2

etc …
-4/2 = -2
-3/2 = -1
-2/2 = -1
-1/2 = 0
0/2 = 0
1/2 =0
2/2 = 1
3/2 = 1
4/2 = 2
etc…

On remarque que autour de 0, il y a un gros soucis. On souhaiterais avoir les résultats suivant:

...
-4 => -2
-3 => -2
-2 => -1
-1 => -1
0 => 0
1 => 0
2 => 1
3 => 1
4 => 2
…

On remarque que pour les positifs, cela ne change rien. pour les négatif, il faut les décaler. on obtient alors:

int X = ...;

int area_x = (X<0)?((X+MAP_AREA_SIZE +1)/MAP_AREA_SIZE:(X/MAP_AREA_SIZE);

Retour sur la clef

On peu maintenant calculer les coordonnée des zones à partir des coordonnées globales.

On peut maintenant penser que l’on peut créer notre clef unique en utilisant std::pair(X,Y) et bien non … en effet, tel quel c’est pas possible, car la fonction de hash existe pas pour les pairs ..

Fonction de hash

On va donc devoir la créer nous même. Je vous rassure, c’est pas très compliqué:

std_hash.hpp

Maintenant c’est bon (enfin) !

Création le la Map

On peut donc enfin commencer à crée la map en temps que tel.

Il nous faut:

• pouvoir récupérer une tuile à une coordonnée précise
• ajouter des zones
• supprimer des zones

Je vais passer la suppression des zone, car elle dépend de problème. L’ajout quant à lui peut être fait lors de l’accès. En gros si la zone existe pas, on la crée. De plus, il y aura très sûrement des loop sur la map pour l’affichage, on va donc ajouter un cache.

Map.hpp

Map.tpl

Voila voila, on a donc notre map prète à lemploi.

h3. Testons la

On va pouvoir maintenant la tester.

juste le temp du test, j’ai mis les “int x,y” de Tile en public.

h4. main.cpp

On obtient alors une sortie (assez déroutante je vous l’accorde):

MAP_AREA_SIZE: 8
Tile(0,0);
Tile(0,1);
...
Tile(7,6);
Tile(7,7);
T:0 0
T:1 3
T:4 4
Tile(-8,-8);
Tile(-8,-7);
Tile(-8,-6);
...
Tile(-1,-2);
Tile(-1,-1);
T:-1 -1
Tile(-16,40);
Tile(-16,41);
...
Tile(-9,46);
Tile(-9,47);
T:-12 42

On remargue alors plusieurs chose:

• La première est que l’on obtient bien les tuiles voulus (heuresement)
• la deuxième est que la création se fait bien à la volée comme voulus
• Enfin pas de problème avec les index nétatifs

Et voila.

Le code est disponible sur github:

https://github.com/Krozark/2D-infinite-map