Structure de donnée pour cartographier et mémoriser un trajet
Bonjour !
Je suis loin d'être un as en algorithmique et bien qu'ayant jeté un coup d'oeil à la FAQ et aux cours, je doute encore quand à la structure de données à adopter pour faire une cartographie des lieux et mémoriser un trajet.
Petit aperçut de l'environnement dans lequel je me situe pour mieux me faire comprendre :
Je m'intéresse aux MUD, vieux type de jeu uniquement en texte (si ça vous intrigue essayez MultiMUD) qui a la particularité de permettre un déplacement selon une liste de sorties possible.
Cela peut être nord, sud, est, ouest, porte, porte-coulissante, arche, escalier, haut, etc.
A chacune de ces actions, le décors change.
Ce que je souhaite donc faire, c'est bâtir une carte des lieux en fonction des sorties possibles et du chemin que j'emprunte.
Exemple :
(Lieu0) Sorties : nord
nord
(Lieu1) Sorties : ouest sud est
sud
(Lieu0) Sorties : nord
Ici, il faudrait donc mémoriser que
- le Lieu0 mène à Lieu1 grâce à nord.
- le Lieu1 mène à Lieu1 grâce à sud.
- le Lieu1 va mener vers 2 autres lieux qui sont inconnus pour l'instant.
Avec quelques contraintes :
Un lieu n'est pas obligé d'avoir une sortie (on tombe dans un trou, il est alors impossible d'en sortir en marchant dans une direction) et peut en avoir plusieurs (pas de nombre max).
Il faudrait également mémoriser le tracé du chemin emprunté :
- nord : mémorisation
- sud : mémorisation
- détection (automatique ou manuelle, je verrais plus tard) d'un "retour sur ses pas" avec suppression de sud et de nord
Voilà donc ce que j'aimerais réaliser.
Je pensais utiliser les listes pour la cartographie.
Chacun des éléments de cette liste serait un lieu, pointant vers les autres lieux (connus grâce aux sorties) vers lesquels il mène.
Ce nombre de pointeurs ne serait pas égal pour chacun des élément, puisqu'il pourrait y en avoir 0 ou plusieurs.
Je pensais utiliser une pile, ou également un liste, pour la mémorisation du chemin parcouru.
Pile parce que je ne fais que lui ajouter des sorties.
Liste parce que je me dis que ce serait plus simple pour la suppression d'une portion de chemin.
En effet il n'y a pas que le cas des opposés créant un retour sur ses pas (nord sud - porte porte - haut bas - ...) il peut y avoir des lieux magiques ramenant à un certain point, la carte peut ne pas respecter les contraintes de largeur et hauteur, exemple [nord est sud sud sud sud sud sud sud sud ouest], qui ramène au point de départ.
Dans ces cas là j'imaginais faire en sorte que les infos de la cartographie influeraient sur la gestion de la mémoire du chemin parcouru.
Dans l'exemple précédent, un lien serait créé entre le dernier lieu rencontré "anormal" et un autre lieu rencontré précédemment.
A la création de ce lien, tout ce qui se trouve après ce lien serait détruis, puisque il s'agirait d'un "retour sur ses pas".
Voilà, si vous pouviez confirmer / infirmer mes choix quand aux listes pour la cartographie et listes ou piles pour le trajet, ça me serait d'un grand secour.
Merci d'avance !
PS : Je me rend compte que c'est bien joli de créer des listes et tout pour mémoriser la cartographie, mais j'aimerais qu'à la fermeture du programme cette liste soit sauvegardable quelque part.
Existe t'il un support adéquat et connu pour ce genre de travail (cartographie), ou c'est à moi de "l'inventer" ?
Merci encore.
