Salut, pour mes études, je suis en train d'essayer de coder un générateur de labyrinthe, et j'ai notamment besoin de coder une fonction qui, pour un labyrinthe résoluble, donne le chemin (préférablement le plus court) sous forme de listes de coordonnées partant de l'entrée et arrivant à la sortie.

Le labyrinthe est codé comme une matrice (non nécessairement carrée) remplie de 1 et de 0 : les 1 correspondent à un mur, les 0 à une case disponible.

Pour créer cette fonction "chemin", j'aimerais m'inspirer de la fonction résoluble, qui pour un labyrinthe quelconque teste s'il est résoluble. Voici le principe de cette dernière : on fait partir une onde du point de départ qui va tester quelles sont les cases disponibles à proximité de la case de départ et qui va recommencer le processus avec les nouveaux points jusqu'à soit tomber sur la case d'arrivée (auquel cas le labyrinthe est résoluble) soit arrive à cours de cases disponibles
Voici le code de la fonction résoluble et de la sous-fonction case_dispo dont j'ai aussi besoin :
(je peux vous donner le fichier .py aussi au besoin)

donc pour la fonction chemin, l'idée serait de faire partir une onde du point d'entrée et une du point de sortie, qui iront toutes deux globalement à la même vitesse (parcourt une case chacune par itération, ou du moins autant chacune par itération)
jusqu'à ce que ces deux ondes se rencontrent en un point (au moins un point, s'il y en a plusieurs on en prend un arbitrairement)
alors, on garde en mémoire les coordonnées de ce point et on recommence le processus de façon dédoublée :
on fait partir une onde de ce point et une onde de la case de départ + une onde de ce point et une onde la case d'arrivée
on marque les points de rencontre de ces ondes (on en aura 2) et on recommence avec ces points
du coup à chaque itération on multiplie le nombre de points par deux, et théoriquement à l'issue du processus on aura un chemin qui correspondra à un itinéraire possible pour résoudre le labyrinthe - et ce sera l'itinéraire le plus court, je crois - (l'algorithme peut s'arrêter quand tous les points qui correspondent au chemin ont deux voisins qui correspondent au chemin aussi il me semble - sauf dans le cas de la case de départ et de sortie)

l'idée est claire dans ma tête mais mes lacunes en python m'empêchent de la transformer en algorithme... est-ce que quelqu'un pourrait m'aider ? Merci beaucoup

merci je connaissais pas, je me suis renseigné un peu mais je me demande si ce serait pas un peu dommage de ne pas se baser sur la fonction"resoluble" que j'avais codé ?
je m'y connais pas trop mais il me semble qu'entre celle-là et la fonction chemin il n'y a qu'un pas non ?

En effet ta solution serait correcte mais en terme de complexité algorithmique, pour le cas où tu recherches le chemin le plus court, ça n'est pas top.
Comme dis plus haut, l'algo de Dijkstra résoud facilement ton problème, il est très facilement programmable

J'ai du mal à implémenter l'algorithme de dijkstra, je suis un néophyte... vous pouvez m'aider ? J'ai vu comment faire pour trouver le chemin le plus court entre deux points A et B dans un graphe en cherchant sur google mais là dans un labyrinthe, vu qu'il faut prendre en compte les murs, je vois pas comment faire

Tu as déjà réalisé un code ou un algo ? Montre

C'est très bien de réinventer la roue, c'est même la partie la plus amusante en algorithmique Et puis je trouve qu'on comprend mieux un algorithme quand on l'a trouvé tout seul que quand on a juste lu la solution.

Tu n'as pas besoin de Dijkstra ici (c'est pour trouver le chemin le plus court, là tu t'en fiches un peu de la longueur), et en effet ta fonction "résoluble" fait déjà presque tout ce qu'il faut. Pour info, ce que tu fais s'appelle un "parcours en largeur" ( https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur ).

En fait, ta fonction "résoluble" trouve déjà un chemin de l'entrée vers la sortie ; le problème est juste que tu ne retiens pas la liste des cases que tu as traversées pour atteindre un point donné, tu te contentes de répondre "vrai" ou "faux". Tu n'as pas besoin de faire des trucs compliqués en partant simultanément de l'entrée et de la sortie pour se rejoindre au milieu, il suffit juste de garder ta fonction résoluble telle quelle, et retenir un peu plus d'informations.

Il existe aussi le "parcours en profondeur" qui est peut être légèrement plus adapté pour ton histoire de labyrinthe. Mais tu peux très bien t'en sortir comme t'es parti.

Et fais attention aux cas pathologique où la sortie est placée pile sur l'entrée, ou bien est un voisin direct de l'entrée : je pense que ton algo ne la trouve pas.

Je suis d'accord avec toi AlphaCigny pour inventer son propre algo, mais c'est aussi important de l'optimiser là on voit qu'il a déjà apporté une réflexion, on ne lui aura pas maché le travail.

Oui c'est un parcours en largeur, mais sinon tu peux aussi faire l'algo de D avec des pondérations de 1 Mais c'est du bricolage oui

Le 11 juin 2016 à 14:33:14 skywear a écrit :
J'ai du mal à implémenter l'algorithme de dijkstra, je suis un néophyte... vous pouvez m'aider ? J'ai vu comment faire pour trouver le chemin le plus court entre deux points A et B dans un graphe en cherchant sur google mais là dans un labyrinthe, vu qu'il faut prendre en compte les murs, je vois pas comment faire

Ton labyrinthe est un graphe : tu as un sommet pour chaque case vide, et une arête entre deux cases vides adjacentes.
En fait je me rends compte que vu que toutes tes arêtes sont de longueur 1, Dijkstra va juste revenir à faire un parcours en largeur, donc bravo, tu as déjà implémenté Dijkstra, c'est ta fonction "résoluble"

Merci beaucoup, j'ai juste une question

Le 11 juin 2016 à 14:38:52 AlphaCygni a écrit :

SpoilAfficherMasquer

- méthode bourrine : tu retiens pour chaque nouvelle case explorée la liste de toutes les cases que tu as traversées pour arriver là
- un peu mieux : tu retiens juste quelle était la case d'où tu es arrivé, puis quand tu es arrivé à la sortie tu remontes le chemin jusqu'à l'entrée.

Comment, juste en gardant en mémoire les cases que l'on a précédemment exploré, l'algorithme peut garder le chemin précis en mémoire ? Vu qu'il n'y a pas une seule case disponible à la fois... Si on part de la sortie, il peut a priori y avoir trois choix de "parents" à chaque fois
ou sinon j'ai pas bien compris ce que tu as dit

Mais sinon j'aimerais bien pouvoir récupérer le chemin le plus court justement

Oui tel quel en faisant un parcours en largeur t'auras le chemin le plus court c'est bon.

Chaque case n'a qu'un seul parent.
Concrètement dans ton code, la case (x,y) sera le parent de tous les gens qui sont dans ta liste B.

bon j'ai essayé de modifier l'algo histoire de garder les coordonnées des points au fur et à mesure
mais la seule chose que j'ai su faire c'est garder en memoire toutes les cases disponibles... et du coup certaines n'appartiennent pas au chemin... je nage

Le 11 juin 2016 à 16:02:59 AlphaCygni a écrit :
Oui tel quel en faisant un parcours en largeur t'auras le chemin le plus court c'est bon.

Ah ok merci

Chaque case n'a qu'un seul parent
Concrètement dans ton code, la case (x,y) sera le parent de tous les gens qui sont dans ta liste B.

mais je voulais parler de parent en partant de la sortie du coup de "fils" en partant de l'entrée
je vais réfléchir à ce que tu dis c'est pas très clair dans ma tête

non décidément je vois pas comment procéder

help

Ton algo part de l'entrée et avance jusqu'à la sortie.
Au fur et à mesure de ton parcours, tu vas remplir une matrice parent[x][y] qui te dit, pour chaque case que tu as explorée pendant ton parcours, d'où tu venais quand tu as atteint cette case pour la première fois.

Exemple ton labyrinthe est:

0 0 0 1
0 1 0 1
0 1 1 1
0 0 0 0 

Je donne des noms aux cases pour que ce soit lisible:

a b c d
e f g h
i j k l
m n o p

L'entrée est a, la sortie est p.

- Tu commences en a (qui n'a pas de parent), et tu vas commencer par explorer ses voisins qui sont b et e.
Donc tu vas mettre parent[b] = a, et parent[e] = a.
- Ensuite tu explores b, son seul voisin est c. Tu mets parent[c] = b.
- Tu explores e, son seul voisin est i, tu mets parent[i] = e.
- Tu explores c, son voisin est g, parent[g] = c.
- Tu explores i, son voisin est m, parent[m] = i.
- Tu explores g, pas de voisin.
- Tu explores m, etc...
- ...
- Tu arrives à la sortie p, avec parent[p] = o.

Concrètement pour l'instant ça consiste juste à rajouter une ligne dans ton code pour noter le parent à chaque fois que tu trouves une nouvelle case.
Ensuite une fois que t'as ça tu reconstruis le chemin en partant de p et en suivant les cases indiquées par ta matrice "parents"