IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Structure de donnée pour cartographier et mémoriser un trajet


Sujet :

Algorithmes et structures de données

  1. #1
    Membre confirmé
    Inscrit en
    Mars 2010
    Messages
    74
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Mars 2010
    Messages : 74
    Par défaut 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.

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par SmallFitz Voir le message
    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.
    C'est une bonne idée.

    Ta carte est en fait un graphe : Lieu=noeud, sortie=arc. Les arcs sont typés en fonction du type de sortie. Ta représentation par liste (List Of List) est une des manières de représenter une matrice d'adjacence qui contient beaucoup de zéro (sparse matrix).


    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.
    La pile des déplacement me parait une bonne idée. J'ajouterai une deuxième information en plus du déplacement : le lieu actuel. Ca te permet de gérer facilement tes "retours sur ses pas". A chaque déplacement, tu parcours ta pile depuis le début pour voir si tu es déjà passé par le lieu courant, et auquel cas tu peux supprimer le reste de la pile.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre confirmé
    Inscrit en
    Mars 2010
    Messages
    74
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Mars 2010
    Messages : 74
    Par défaut
    Je te remercie pseudocode !

    J'ignore tout des graphes et des matrices, est-il nécessaire de m'y plonger pour réaliser mon projet ?

    Très bonne idée l'ajout du lieu pour la pile, je n'y avais pas pensé !

    Aurais tu des idées ou des redirections à me proposer à propos de la sauvegarde sur disque dur d'une telle cartographie ?

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par SmallFitz Voir le message
    Je te remercie pseudocode !

    J'ignore tout des graphes et des matrices, est-il nécessaire de m'y plonger pour réaliser mon projet ?
    Non, ce n'est pas *nécessaire*. Mais ca te permet d'avoir des mot-clés pour d'éventuelles recherches. Cela dit, regarder ce qu'est un graphe orienté et comment on le représente dans une matrice/liste d'adjacence, ca peut te donner des idées.

    Aurais tu des idées ou des redirections à me proposer à propos de la sauvegarde sur disque dur d'une telle cartographie ?
    La plupart des langages/frameworks proposent des fonctions pour faire cela : ca s'appelle la serialisation.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre confirmé
    Inscrit en
    Mars 2010
    Messages
    74
    Détails du profil
    Informations personnelles :
    Âge : 37

    Informations forums :
    Inscription : Mars 2010
    Messages : 74
    Par défaut
    Génial !
    J'avais peur de devoir me plonger dans le xml ou des trucs du genre que je ne connais absolument pas.
    Et hop c'est parti !
    Merci encore !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 2
    Dernier message: 03/11/2009, 21h34
  2. Réponses: 3
    Dernier message: 17/03/2009, 11h41
  3. Réponses: 2
    Dernier message: 09/08/2008, 13h30
  4. Structure de données pour gros volume de données
    Par Invité dans le forum Langage
    Réponses: 9
    Dernier message: 01/02/2007, 11h58
  5. Structure de données pour recherche rapide
    Par socrate dans le forum C
    Réponses: 1
    Dernier message: 18/06/2006, 14h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo