Gestion d'une grille avec des murs

Afin de réaliser un projet, j'ai dû imaginer une implémentation de grille telle que chaque case pouvait être d'un certain type (`herbe`, `eau`, `lave`) et où il pouvait y avoir un `mur` entre deux cases. La question est donc : comment implémenter intelligemment ce `plateau` de jeu ?  _Figure : Plateau de 4 cases des trois types avec deux murs entourant la lave. Les murs entourant le plateau ne sont pas représentés._ ## Naïvement En effet, il y a deux choix simples qui peuvent venir en tête directement : le représentation par cases et la représentation par murs. Toutefois ces deux méthodes ne sont pas optimales d'un point de vue de la mémoire, laissez moi vous expliquer. ### Représentation par cases Définissons une `Case` avec ses murs : ``` type Case { entier type; booleen murHaut; booleen murDroit; booleen murBas; booleen murGauche; } ``` Nous pourrions construire une matrice de `Case` et le `plateau` serait fonctionnel **mais** un problème existe : _la redondance d'information_. Car en prenant deux cases collées l'une à l'autre, nous allons stocker deux fois l'état du mur entre les deux cases (une fois dans l'attribut `murDroit` et une autre dans l'attribut `murGauche` par exemple).  _Figure : Deux cases séparées par un mur. Les flèches représente le référencement des objets (ici la case stocke l'information du mur)._ On voit que le mur est stocké dans deux cases. Cette méthode n'est donc pas la meilleure d'un point de vue mémoire. ### Représentation par murs Idem, définission un `Mur`: ``` type Mur { booleen estActif; booleen estHorizontal; entier typeCase1; entier typeCase2; } ``` Ici on doit faire la distinction entre l'existance d'un mur entre deux cases (`estActif = true`) ou pas (`estActif = false`) et de si le mur est horizontal ou vertical entre les cases `1` (en haut / à gauche du mur) et `2` (en bas / à droite du mur). De même, nous pouvons faire une matrice pour stocker le `plateau` or on a encore _une redondance d'information_. Elle se trouve dans les types de cases, prenons deux murs séparés par une case : le type de la case est stocké par le mur gauche (`typeCase2`) et par le mur droit (`typeCase1`). Cette méthode n'est donc toujours pas bonne.  _Figure : 3 cases séparées par des murs. Les flèches représentent toujours le référencement (cette fois le mur stocke l'information de la case)._ On peut observer de plus que ces deux méthodes mènent à devoir modifier deux endroits de la mémoire en même temps pour rester cohérent, ce qui est un risque pour l'utilisateur. ## Une solution Une solution que j'ai trouvé à ce problème est celui de prendre une représentation par cases mais où seulement le mur droit et le mur bas sont stockés. ``` type Case { entier type; booleen murDroit; booleen murBas; } ``` De cette façon, chaque mur n'est stocké qu'une et unique fois : il n'y a pas de redondance.  _Figure : Plateau de 9 cases possédant en gris des murs entre certaines cases et en tirets des zones sans murs. Les flèches représentent toujours le référencement, on voit que chaque mur n'est pointé que par une unique case. Seule les murs du bord gauche et haut doivent subir un traitement particulié car stocké nul part (souvent des murs sur tout le bord)._ L'accès aux murs est toujours de complexité constante (temps et mémoire), cette méthode est surement la bonne ! Un exemple pour accèder aux murs d'une case en `(x,y)` dans une matrice `grille` : ``` Mur Droit : grille[x][y].murDroit Mur Bas : grille[x][y].murBas Mur Gauche: grille[x-1][y].murDroit Mur Haut : grille[x][y-1].murBas ``` _(Tout en faisant attention à où est le haut et où est le bas et à ne pas sortir des limites du `plateau`, ici (0,0) représente le coin haut gauche)_