Labyrinthe programme en C.mp4

Channel:

Xavier Foisset

Subscribers:

6,680

Published on April 19, 2011 9:55:23 PM ● Video Link: https://www.youtube.com/watch?v=YnzqBWrnmSE

Duration: 2:59

8,059 views

21

Ce programme est composé de 2 sous programmes, un pour générer aléatoirement le labyrinthe avec boucle et une autre plus complexe pour le "résoudre" cad passer au moins une fois sur chaque case. Et un bip audible est entendu une fois que le mobile est passé sur toutes les cases.

La construction du labyrinthe est la partie la moins dure. Ma technique est de remplir une variable à 2 dimensions (pour largeur/hauteur du labyrinthe) en donnant une valeur de case à chaque valeur de la variable et pour ça je trace des couloirs. Je trace un 1er couloir assez long de façon aléatoire (changement de direction haut, bas, gauche ou droite), et à chaque fois alors que je remplis cette variable, j'élimine dans une autre variable contenant toutes les positions des cases vides la position de la case que je viens de remplir. Puis je repars pour un nouveau couloir d'une case vide de cette variable avec là aussi une direction et longueur aléaoire, et qui se termine quand je rencontre un autre couloir donc une case prise, que je transforme en case intersection pour faire la jonction dans la var à 2 dimensions représentant le labyrinthe qui se construit dans cette var. Je m'arrête aussi quand je suis bloqué par un côté.
Et quand toutes les cases sont remplies donc que je n'ai plus de case vide dans ma variable recensant les cases restantes, j'ai fini.
J'ai en tout 11 sortes de cases : 1 horizontale/1 verticale/ 4 coudes / 4 intersections à 3 branches / 1intersction en croix
La variable qui contient l'information du labyrinthe à 2 dimensions est var (x,y)= valeur de la case pour ces coordonnées x,y
La variable qui sert à faire partir un nouveau couloir et me dire quand j'ai fini est à une dimension et recense pour un indice (donc de façon "empilée") toutes les positions (x,y) de case non encore remplie

Le programme de résolution bien qu'en apparence très compliqué sachant que le labyrinthe possède des boucles est en fait assez simple :
Dans une 1ière variable de tableau à une dimension je mémorise chaque case intersection au fur et à mesure que je les rencontre. Et dans une 2nde variable de tableau à 2 dimensions je mémorise pour le 1er indice qui correspond à l'ancienne variable à une dimension des cases intersections, le nombre de sortie de cette case intersection dans le 2nd indice, donc 3 ou 4 sorties max.
Puis, quand le mobile rencontre une case intersection :
- Soit c'est une nouvelle case intersection car inconnue de la 1ère variable et alors je l'empile à la suite des autres dans cette variable à 1 dimension, ainsi que toutes ses sorties que j'énumère dans la 2nde variable à 2 dimensions en "parallèle".
- Soit c'est une case connue de la 1ière variable mais pas la dernière de la pile, ce qui est possible puisque le labyrinthe possède des boucles, et alors je supprime la sortie par laquelle je tombe dessus dans la 2nde variable correspondant à cette case précise.
- Soit c'est une case intersection connue et aussi la dernière de la pile de la 1ière variable, sur quoi je supprime cette sortie par laquelle je retombe dessus dans la 2nde variable à 2 dimensions (qui encore une fois mémorise toutes les sorties). Et s'il n'y a plus aucune sortie à cette case intersection je ne la supprime pas malgré tout car elle mémorise le fait que j'y suis déjà passé.