Discussion :

[Ashantyy]

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...

[Sve@r]

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).

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 !!!

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

Ben oui, surtout qu'on ne l'écrira pas à ta place...

[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.

[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

[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..

[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.

[Matt_Houston]

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

[Ashantyy]

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