Discussion :

[sooth96]

Bonjours je suis actuellement élève en prépa en option informatique et j'aurai besoin d'un petit coup de main pour la création d'un algorithme permettant de construire un labyrinthe parfait c'est a dire que pour aller d'un point A à un point B un unique chemin existe la méthode consiste a partir de la case (0,0) et à chaque étape on marque dans un tableau la case visitée et on dresse une liste de toute les direction dans lesquelles il est possible d'aller puis on en choisit une au hasard et on casse le mur correspondant si la liste est vide on dépile une pile contenant le chemin parcourut .
Lorsque la pile est vide alors c'est fini. j'ai un petit problème je ne vois pas comment faire un programme évaluant les différent chemin possible et empruntant un au hasard je ne vois pas comment on peut distinguer un mur délimitant le labyrinthe et un mur qu'on peut casser tout en prenant en compte le fait qu'on ne peut pas aller vers une case ou on est déjà passé. Je vous remercie d'avance de votre aide

[stendhal666]

Wikipedia contient un excellent article sur les labyrinthes parfaits où les algorithmes de construction sont détaillés, avec un gif très bien fait:
http://fr.wikipedia.org/wiki/Mod%C3%...de_labyrinthes

Il n'est pas possible de faire plus clair! à toi de jouer...

[sooth96]

Merci de ton aide standhal666 j'ai déjà lu le dossier de Wikipédia seulement la méthode je l'ai déjà mais c'est pour la mettre sous forme algorithmique enfaîte mon problème c'est de faire un algorithme donnant les différentes directions possible sans qu'il soit plein de condition et totalement illisible c'est a dire lorsque l'on sort du labyrinthe ou alors qu'on passe sur une case déjà visitée . J'ai essayer un match sa marche bien pour les limites du labyrinthe mais les choix sont différent selon que une direction possible est déjà été empreinté .

[stendhal666]

D'accord, j'avais mal compris la question.
Tu pourrais envoyer le code que tu as fait jusqu'ici? Parce qu'aider un peu, avec plaisir, mais coder un générateur de labyrinthe je ne pense pas avoir le temps tout de suite...

[sooth96]

je n'ai fait que le programme permettant d'avancer dans le labyrinthe enfaîte j'ai une idée de la structure du programme pour créer le labyrinthe parfait que je peut te donner en pseudo code :
let labyrintheparfait laby (* labyrinthe de taille np ayant des murs partout*) =
(x,y) = (0,0)
Tab <- tableau de taille (n-1)(p-1) remplis de 0 a part le première élément étant (0,0) (* servant a stocker les cases déjà visitée *)
pile <- pile contenant (0,0) (*chemin parcourus *)
Tant que la pile est non vide faire :
Pour i allant de 1 à
L <- liste des directions possibles
(x,y) = exécution du programme avance dans une des directions au hasard de la liste
empile la nouvelle position dans la pile
on change le i ème élément du tableau en la nouvelle position
on casse le mur situé dans la direction souhaitée.

mon problème c'est juste le programme donnant la liste des directions possible en prenant en compte les dimension et les cases déjà visitée
merci de votre aide

[stendhal666]

mon problème c'est juste le programme donnant la liste des directions possible en prenant en compte les dimension et les cases déjà visitées

NB: je te réponds en pseudo-code, ma syntaxe OCaml est trop rouillée

On va faire en 3 parties:

1) les directions possibles: c'est le produit cartésien des éléments de a) map (+x) [-1,0,1] et map (+y) [-1, 0, 1] (si on compte la direction "immobile" - comme elle est déjà écartée par la partie 3, on ne s'en occupe pas maintenant)
2) dans les dimensions du tableau: on filtre les tuples obtenus par (1) avec ( x >= 0 && x < m && y >= 0 && y < n)
3) le problème n'est pas de savoir si la case a déjà été visitée mais si elle a le même "tag" que la case d'origine. Si oui, on recommence la procédure de choix d'un mur; si non, on abat le mur et on parcourt le chemin pour mettre un tag identique à toutes les cellules reliées (ça tu m'as dit que tu l'avais fait), on incrémente le compteur des murs abattus et, sauf s'il est égal à m*n-1, on recommence la procédure

[sooth96]

désolé de t’embêter encore mais je suis un peu débutant en la matière le tag sa équivaut a un booléen ou quelque chose dans le genre?
Enfaite j'ai crée un type direction et mon algo pour la liste des direction ressemble a sa sans map du coup mais je vois pas comment intégrer un tag ou autre chose comme mon tableau dedans peu etre que je m'y suis mal pris.

let listedirection n p (x,y) =
match (x,y) with
|(n-1,p-1) -> [nord , ouest]
|(n-1,0) -> [nord , est]
|(0,0) -> [sud , est ]
|(0,p-1) -> [ouest , sud ]
|(0,_) -> [ouest , sud , est ]
|(n-1,_) -> [ouest , nord , est ]
|(_,p-1) -> [nord , sud , ouest]
|(_,0) -> [nord, sud , est ]
|(_,_) -> [nord, sud, est, ouest]
;;
en claire je fais tout les cas possibles sauf le cas la case a déjà été visitée

[stendhal666]

Je me rends compte que j'ai fait une confusion entre les deux algorithmes de génération proposés par Wikipedia (je pensais que tu avais choisi le premier, où les cellules du tableau initial sont numérotées de 0 à (m*n-1). En fait tu utilises le deuxième: le modèle à pile (exploration exhaustive). Je reprends wikipedia:

"On part d'un labyrinthe où tous les murs sont fermés. Chaque cellule contient une variable booléenne qui indique si la cellule a déjà été visitée ou non (i.e. les cellules visitées sont celles qui appartiennent au chemin du labyrinthe en cours de construction).
Au départ, toutes les cellules sont marquées comme non visitées (faux)."
Donc on a au départ un tableau de dimension m*n initialisé à false

"On choisit arbitrairement une cellule et on la marque comme visitée (vrai)."
Jusque là pas de problème, n'est-ce pas? il suffit de sélectionner deux nombres aléatoires entre 0 et m et 0 et n

"Puis on regarde quelles sont les cellules voisines possibles et non visitées et on stocke la position en cours."
Donc:
1: on génère toutes les positions possibles = produit cartésien de deux listes formées en ajoutant -1, 0, +1 à x et y
2: avec une fonction de type: isVisited (x,y) = tab[x*m+y] (donc faux si pas visitée (état initial), vraie sinon) on fait un filtre pour écarter celles qui sont déjà visitées
3: on pousse la position en cours dans une pile (dernier entré = premier sorti)

"S'il y a au moins une possibilité, on en choisit une au hasard, on ouvre le mur et on recommence avec la nouvelle cellule."
là encore pas de problème

"S'il n'y en pas, on revient à la case précédente et on recommence."
il suffit de faire un pop sur la pile pour obtenir la case dont on vient

"Lorsque l'on est revenu à la case de départ et qu'il n'y a plus de possibilités, le labyrinthe est terminé."
c'est à dire lorsque la pile est vide

"L'historique des emplacements des cellules précédentes peut être géré de deux façons équivalentes :
par la sauvegarde dans un tableau de mn - 1
par la sauvegarde dans la pile, en utilisant la récursivité"
C'est là qu'on voit le problème de l'algorithme de wikipedia: il n'est pas fait pour un langage fonctionnel. Mais il est aisé à traduire, au prix d'un fonctionnement sous-optimal:

en prenant une fonction loop du genre
loop tab pile chemin
pour avoir une récursion terminale on peut faire (pseudo-code):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
loop tab pile chemin = if pile = empty then chemin
                              else case selectNewCellFrom (top pile) of
                                           none -> loop tab (pop pile) chemin 
                                           some of (x, y) -> let newTab = set Tab(x, y) true
                                                                       newPile = push (x,y) pile
                                                                   in loop newTab newPile ((x,y) :: chemin)

[sooth96]

C'est exactement cette méthode la sauf que dans mon cas je dois le faire a l'aide d'un tableau contenant la liste des positions déjà visitée au lieu de booléen ce qui n'a pour moi pas trop de sens a la limite une liste je comprendrai mais je ne vois pas pourquoi un tableau et ensuite je pense que mon programme renvoie quelque chose de type unit vu que j'ai ensuite une fonction pour l'afficher et donc sans booléen la seul solution que je vois c'est chercher si la case sur laquelle on est est déjà dans le tableau si oui on pop sinon on continue cependant se serai beaucoup plus simple avec une liste vu que je travaille sur caml light et qu'il n'y a pas de fonction permettant de vérifier si un élément est dans un tableau.Remarque peut etre que le tableau visite est un tableau de booléen mais dans ce cas la syntaxe serai make_vect false (n-1)*(p-1) ?

[stendhal666]

N'hésite pas à faire des pauses dans tes phrases, sinon on s'essouffle rien qu'à te lire

C'est exactement cette méthode la sauf que dans mon cas je dois le faire a l'aide d'un tableau contenant la liste des positions déjà visitée au lieu de booléen ce qui n'a pour moi pas trop de sens a la limite une liste je comprendrai mais je ne vois pas pourquoi un tableau

- En fait je me rends compte que le tableau est redondant par rapport au chemin: si (x,y) est dans le chemin alors la case du tableau est nécessairement true.
- Donc en effet la liste chemin suffit (et je suis d'accord avec toi que c'est plus approprié qu'un tableau
- Pour la transformer en tableau il suffit de créer dès le départ un tableau de m*n cellules avec une valeur conventionnelle indiquant la fausseté (par ex (-1,-1)

et ensuite je pense que mon programme renvoie quelque chose de type unit vu que j'ai ensuite une fonction pour l'afficher

Non, ce n'est pas nécessaire, ta fonction d'affichage peut avoir le type a -> unit a

et donc sans booléen la seul solution que je vois c'est chercher si la case sur laquelle on est est déjà dans le tableau si oui on pop sinon on continue cependant se serai beaucoup plus simple avec une liste vu que je travaille sur caml light et qu'il n'y a pas de fonction permettant de vérifier si un élément est dans un tableau.

Oui ce serait plus simple avec une liste mais il suffit de faire une boucle sur le tableau: dès que tableau[xy] renvoie (-1,-1) on renvoie false. Je suis d'accord que c'est pas beau, mais bon...

Remarque peut etre que le tableau visite est un tableau de booléen mais dans ce cas la syntaxe serai make_vect false (n-1)*(p-1) ?

Le tableau ne peut pas être à la fois booléen et la liste des positions! là l'énoncé est fautif

[sooth96]

Non je pense que c'est moi qui est mal interprété l'énoncé dis "on maintient un tableau visite pour garder en mémoire les cases déjà visitée." "a chaque étape on marque la case actuelle comme visitée " ça peut très bien être des booléen. Merci de ton aide stendhal666 je vais essayer avec sa pour voir .