Recherche chemin labyrinthe

Signaler
Messages postés
6
Date d'inscription
samedi 7 février 2009
Statut
Membre
Dernière intervention
24 mars 2011
-
Messages postés
6
Date d'inscription
samedi 7 février 2009
Statut
Membre
Dernière intervention
24 mars 2011
-
bonjour,je sui débutante en C
svp!! si qqun pourra m'aider sur ce sujet
g un labyrinthe défini a partir d'un fichier texte avec des 1 pour les murs et 0 sinon
je veux bien chercher un chemin entre deux cases mé jarrive pas à trouver une solution
Merci de me présenter un algo si c possible
Crdt

8 réponses

Messages postés
3829
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
8 janvier 2021
114
Renseigne toi sur un algo de backtracking. La récursivité devrait aussi résoudre le problème très rapidement. Plus bourrin, tu peux aussi regarder des algos tel que Manhattan, Astar, ou Dijkstra.
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
Salut
>>Cptpingus : Je ne suis pas d'accord avec toi quand tu dis "plus bourrin". Pour Dijkstra c'est vrai mais pas pour l'Astar. Un algo Astar bien codé est très loin de visiter toute la carte. Pour moi c'est le meilleur moyen pour résoudre ce problème.
A+
____________________________________________________________________________
Mon site internet :  
http://ImAnalyse.free.fr
Messages postés
3829
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
8 janvier 2021
114
Je dit plus bourrin au niveau de la difficulté d'implémentation. Il est plus simple de faire un truc en récursif qui visite tout, qu'un des algos précités.
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
Dans ce sens, alors là ok.
A+
____________________________________________________________________________
Mon site internet :  
http://ImAnalyse.free.fr
Messages postés
6
Date d'inscription
samedi 7 février 2009
Statut
Membre
Dernière intervention
24 mars 2011

Salut;
jarrive pa à comprendre ces algorithmes, jsuis encore débutante!!
Svp si qqun peut me donner un algo plus simple(ni pile ni listes chainèes) qui traite ce problème de recherche en C.
Merci bien d'avance
Cdlt
Messages postés
3829
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
8 janvier 2021
114
Fais le en récursif alors.

Exemple théorique:
Récupère tout les 1 et les 0, et tu les mets dans une matrice.

fonction est_valide(Matrice m, Entier x, Entier y) : qui renvoie un boolean
début
  // On vérifie si la coordonnés définit par x et y est valide
  // Vérifions que ça ne soit pas hors borne
  Si x >= largeur Ou x < 0 Ou y >= hauteur Ou y < 0 alors
    retourner faux;

  retourner Matrice[x][y] == 1;
// Si tu es débutante, cette ligne veut dire, retourner vrai si c'est égale à 1, faux sinon.
fin

fonction recherche(Matrice m, Entier x, Entier y) : qui renvoie un tableau de coordonnés
début
  variable locale:
    Tableau de coordonnés : tab = [(x,y)]
  // Regarder si les coordonnées d'à côté sont valides
  Si est_valide(Matrice, x - 1, y) alors
     tab = tab + recherche(Matrice, x - 1, y);
  Sinon Si est_valide(Matrice, x, y - 1) alors
     tab = tab + recherche(Matrice, x, y - 1);
  ... // Ici tu le fait pour les 8 directions.

  retourner tab;
fin

fonction Main()
début
  variable locale:
     Matrice d'entier: m;
     Tableau de coordonnés : tab = [] (vide);
     m = récuperer tout ce qu'il y a dans le fichier et le mettre dans la matrice.
   // Ici je suppose que tu commence tout en haut à gauche, et que la case est libre.
    tab = rechercher(m, 0, 0);
   Afficher (tab);
fin

Attention, ce n'est pas du C, c'est vraiment une méthode théorique pour te présenter la manière de faire, à toi ensuite de coder cela, si tu as compris la méthode.
Messages postés
3829
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
8 janvier 2021
114
Il manque quelque chose dans mon algo... La coordonnée d'arrêt !
Il faut bien entendu s'ârrêter quand on arrive à la bonne destination, ou si la destination n'est pas atteignable (mais c'est un poil plus dur, considère que la cible est toujours atteignable et existante, dans un premier temps).
Messages postés
6
Date d'inscription
samedi 7 février 2009
Statut
Membre
Dernière intervention
24 mars 2011

Merci de m'avoir rèpondu!!

j'ai dèja une matrice qui récupère les 1 et les 0!!!!!
mais comme même je vais l'essayer