Projet C - labyrinthe

Version imprimable

24/04/2018, 22h43
Ashantyy

1 pièce(s) jointe(s)

Projet C - labyrinthe

Bonjour à tous,

Je dois concevoir un labyrinthe et le résoudre.
J'utilise un automate cellulaire avec 7 états (cela fait parti de la consigne) :

* -1 : sortie
* 0 : case libre
* 1 : mur
* 2 : aller à gauche
* 3 : aller à droite
* 4 : aller en haut
* 5 : aller en bas

J'ai décidé de partir de la sortie pour inspecter (via une file) toutes les cases libre (à l'état 0), jusqu'à arriver à l'entrée (0,0). Pendant le parcours, je calcule le voisinage en attribuant un état à chaque cellule parcourue. Une fois arrivée à l'entrée, la boucle s'arrête et je trace le chemin (parcours inverse)

Mon problème :
Certains états de cellule du laby ne sont pas bons, et plus particulièrement au niveau des carrefours

Je vous mets une image du résultat (laby sous forme de matrice)

Merci beaucoup pour votre aide

PS : dites-moi si vous avez besoin de bout de code...
25/04/2018, 06h58
Sve@r

Citation:

Envoyé par Ashantyy

J'ai décidé de partir de la sortie pour inspecter (via une file) toutes les cases libre (à l'état 0), jusqu'à arriver à l'entrée (0,0). Pendant le parcours, je calcule le voisinage en attribuant un état à chaque cellule parcourue. Une fois arrivée à l'entrée, la boucle s'arrête et je trace le chemin (parcours inverse)

Bonjour

L'algorithme pour traverser un labyrinthe est assez simple. A l'entrée on place sa main gauche sur le mur de gauche et ensuite on avance en gardant toujours la main collée au mur. Fatalement à un moment ou à un autre on arrive à la sortie. (Et ça marche aussi avec la main droite).

Citation:

Envoyé par Ashantyy

Certains états de cellule du laby ne sont pas bons, et plus particulièrement au niveau des carrefours

Ben je vois ça oui. Première case en haut à gauche (donc l'entrée si je suis bon) est à 0 (case libre). Où je vais alors ? En bas ? A droite ?
Autre exemple: Première case en bas à gauche est à 5 (aller en bas) alors qu'on est déjà tout en bas !!!

Citation:

Envoyé par Ashantyy

PS : dites-moi si vous avez besoin de bout de code...

Ben oui, surtout qu'on ne l'écrira pas à ta place...
25/04/2018, 08h14
Matt_Houston

Ce dont nous aurions besoin c'est tout d'abord de la description précise de l'algorithme utilisé.

Il y a deux sortes d'erreurs : les erreurs de logique (la méthode est incorrecte) et les erreurs d'implémentation (la méthode est correcte mais on n'a pas su l'expliquer à la machine). Connaître l'algorithme et ses entrées et sorties nous permettrait déjà de déterminer si la logique est viable.
25/04/2018, 10h41
Ashantyy

La description précise de l'algorithme c'est :
à partir de la sortie, et n'avoir à viser que les case à l'état 0 (libres), ça éviterait de parcourir toutes les cases.
De là, on inspecte les cases libres voisines, on met leurs coordonnées dans une pile ou une file (j'ai testé avec les 2 mais le résultat est le même), et on les traite avec la fonction voisinage qui va permettre d'attribuer un état à la case courante. Seulement parfois, il y a des impasses dans le labyrinthe, et du coup pour le peu que le "bon chemin" soit traité après l'impasse,'état de la case courante ne sera pas bon...j'espère que vous comprenez ce que je veux dire

Merci beaucoup
25/04/2018, 12h47
Matt_Houston

Ça me semble un peu confus, as-tu écrit ton algorithme en français avant de te lancer dans l'implémentation ?

Peut-être retires-tu les cellules trop tôt de la liste ? À ta place j'aurais d'abord considéré l'ensemble du labyrinthe à chaque tour (sans file), en mettant à jour toutes les cases qui ne sont pas des murs, afin de valider le processus de simulation.

Une erreur courante dans l'implémentation des automates cellulaires est de mettre à jour le jeu de données que l'on est en train de consulter, effaçant ainsi une partie des informations du tour précédent. Il est souvent nécessaire d'utiliser deux grilles que l'on intervertit à chaque étape : le jeu de données du tour n - 1 devient celui du tour n + 1, celui du tour n devient celui du tour n + 2, etc..
25/04/2018, 13h03
Bousk

Cela ressemble à une description maladroite de A* : https://fr.wikipedia.org/wiki/Algorithme_A*

Sinon, pourquoi ne pas ajouter d'autres états ? "tentative d'aller en haut", "tentative de chemin du bas", ... et si le chemin s'avère faux, tu reviens en arrière jusqu'à trouver une case validée et pars dans une autre direction.
Ou plus simplement avec l'algo de svear : si tu reviens sur une case où tu es déjà passé puisque tu as été dans une impasse, tu réinitialises toutes ces cases et prends le chemin suivant.
Es-tu sûr que ton labyrinthe a toujours une solution ? Sinon tu pourrais avoir des surprises à base de boucles infinies.
25/04/2018, 13h26
Matt_Houston

C'est un automate cellulaire a priori, donc pas un Dijkstra/A*. Chaque cellule n'a conscience que de ses voisines.
25/04/2018, 13h37
Ashantyy

Citation:

Envoyé par Bousk

Cela ressemble à une description maladroite de A* : https://fr.wikipedia.org/wiki/Algorithme_A*

Sinon, pourquoi ne pas ajouter d'autres états ? "tentative d'aller en haut", "tentative de chemin du bas", ... et si le chemin s'avère faux, tu reviens en arrière jusqu'à trouver une case validée et pars dans une autre direction.
Ou plus simplement avec l'algo de svear : si tu reviens sur une case où tu es déjà passé puisque tu as été dans une impasse, tu réinitialises toutes ces cases et prends le chemin suivant.
Es-tu sûr que ton labyrinthe a toujours une solution ? Sinon tu pourrais avoir des surprises à base de boucles infinies.

Oui c'est vrai que cela peut-être une solution, comment pourrais-je faire ? il faudrait détecter les carrefours et les impasses..

Mon laby a normalement toujours une solution car j'ai utilisé l'algo fusion des chemins pour pouvoir le générer, donc il n'y a pas de soucis pour ça je pense

Sinon oui je l'ai écris avant, mais j'ai peut-être du mal à être clair, et je m'en excuse