Barème

Règlement de projet

La réalisation de cet exercice est assujettie aux règles en vigueur dans l’école en matière de triche et de normalisation. Tricher vous expose à de graves sanctions.

Vous devez respecter les règles de normalisation suivantes : https://git.ecole-89.com/eriizu/coding_style/src/branch/main/norm.md

Le non-respect de la norme vous fera perdre une partie ou la totalité des points qui auraient pu être acquis, sur l’ensemble du rendu.

Fichiers à rendre

La structure de votre dépôt doit être la suivante :

• fichiers *.c dans src/
• fichiers *.h dans include/

Comme vous devez rendre un programme, vous devez rendre une fonction main. Son fichier, devra s’appeler main.c, être dans le dossier src/ et respecter les règles de normalisation (il ne s’agit pas d’un fichier de test.)

Votre projet sera compilé avec la commande suivante :

gcc -Wall -Wextra -Werror -Iinclude ./src/*.c -o maze

Fonctions autorisées et interdites

Pour tout le sujet, les fonctions autorisées sont :

• write
• read
• malloc
• free
• open
• close
• strerror

Tests

Vous pouvez inclure des main de test dans votre rendu. Ces main doivent être rendus dans un dossier test/. Vous pouvez organiser ce dépôt comme vous le souhaitez.

Introdution

Votre objectif c’est d’apprendre à travailler sur une carte en deux dimension tout en vous assurant de gérer la mémoire de votre programme en toute sécurité.

Vous allez devoir lire une carte qui correspond à un labyrinthe et votre objectif est de déterminer si la labyrinthe est faisable.

Ensuite, vous devrez tenter de trouver le chemin le plus rapide jusqu’à l’arrivée.

Format

Les cartes de labyrinthe seront toujours rectangulaire et peuvent avoir n’importe quel nombre de colonnes et n’importe quel nombre de lignes.

Légende d’une carte :

• # les murs
• S le point de départ (start)
• G l’arrivée (goal)
• . les cases sur lesquelles il est possible de marcher

Règles

Vous pouvez vous déplacer de haut en bas et de droite à gauche mais pas en diagonale. Ainsi se rendre sur une case en diagonale coûte deux mouvements.

Se déplacer sur la case juste à gauche, à droite, au dessus, ou en dessous coûte un mouvement.

Fichiers exemples

Vous trouverez des fichiers de labyrinthes d’exemples (que vous pouvez utiliser pour tester votre programme) sur la forge https://git.ecole-89.com/eriizu/sample_mazes.

Étapes

E1. Lecture de la carte

Commencez par faire un programme qui charge une carte lorsqu’on lui passe le nom d’un fichier.

Ce programme doit :

• ouvrir le fichier,
• le lire en intégralité tout en stockant son contenu,
• fermer le fd du fichier après l’avoir lu,
• afficher le nombre de lignes et de colones que contient la carte.

$ cat > map.txt << EOF
####S######
#.....#...#
#####.###.#
#...#...#.#
#.#.###.#.#
#.#.....#.#
#.#######.G
#.#.....#.#
#.###.#.#.#
#.....#...#
###########
EOF
$ ./a.out map.txt
width: 11, height: 11

E2. Tenez la gauche

Pour résoudre le labyrinthe, on va commencer par appliquer une stratégie basique qui est de rester collé au mur de gauche.

Pour le labyrinthe lu par votre programme, marquez toutes les cases parcourues par un algorithme qui ne fait que tenir la gauche. Retirez le caractère . des cases que vous avez traversé (en y mettant un espace à la place).

Ainsi pour ce labyrinthe dans map.txt :

###S###
#...#.#
###.#.#
G.#...#
#.###.#
#.....#
#######

L’exécution donnerait :

$ ./a.out map.txt
width: 7, height: 7
###S###
#.. # #
### # #
G #   #
# ### #
#     #
#######

Algorithme

L’algorithme que vous devez implémenter à besoin de :

• de votre position
• de la direction dans laquelle vous regardez (haut, bas, gauche, droite ou nord, sud, est, ouest)

Lorsque vous êtes sur une case et qu’il y a :

• un mur à votre gauche et champ libre devant vous : avancez
• un mur à votre gauche et un mur devant vous : tournez vous vers la droite
  • ordre de rotation: nord → est → sud → ouest → etc.
• champ libre à votre gauche : tournez vous à gauche et avancez d’une case
  • ordre de rotation: nord → ouest → sud → est → etc.

Données

Lorsque vous avez lu le fichier, vous avez probablement créé une chaîne de caractère qui représente toute la carte.

Si jamais je vous demande le premier caractère sur la première ligne, c’est simple, c’est str[0]. On peut dire que le caractère à la position $(0, 0)$ sur la carte peut être trouvé à la position $0$ dans la chaîne lue.

Mais qu’en est-il du caractère à la première position de la troisième ligne ?

Si votre chaîne contient encore les \n, pour connaitre la position du premier caractère de la troisième ligne, il suffit de multiplier la largeur + 1 par l’index de la ligne qui nous intéresse (ici 2 pour la troisième ligne).

Sur une carte de largeur 5, on aurait dont $idx=(width+1)*2$.

Pour avoir le deuxième caractère sur une ligne, il suffit d’ajouter l’indice du caractère que l’on veut donc 1.

Résumé pour une carte de 5 sur 5 :

• $(0, 0) → 0$
• $(0, 1) → 1$
• $(0, 2) → 2$
• $(2, 0) → (5 + 1) * 2 = 12$
• $(2, 1) → (5 + 1)*2 + 1 = 13$
• $(2, 2) → (5 + 1)*2 + 1 = 14$

Si en mémoire on retire les \n on peut visualiser les choses ainsi :

E3. Y’a-t’il une sortie ?

Avec l’algorithme de l’étape 2, si le labyrinthe lu n’a pas de sortie, vous allez avoir une boucle infinie.

Votre objectif pour l’étape 3 c’est de faire s’arrêter votre programme quand vous ne trouvez pas de sortie.

Dans l’exemple nous avons vu que revenir en arrière n’est pas une preuve suffisante que le labyrinthe est insolvable. Posez-vous la question : combien de fois maximum peut-il être normal de repasser sur une même case ?

Enfin, pour savoir si vous êtes passé sur une case : notez-le. Vous pouvez décider de stocker un chiffre sur la case directement par exemple.

Si un labyrinthe ne peut pas être résolu, affichez le message suivant :

No solution to maze.

Et sortez avec le code 1.

Exemple complet :

$ cat > blocked.txt << EOF
###S###
#...#.#
###.#.#
G.#...#
#.###.#
#..#..#
#######
EOF
$ ./a.out
width: 7, height: 7
No Solution to maze.
$ echo $?
1

E4. Propagation

Pour cette étape on va chercher un chemin plus rapide jusqu’à la sortie. Implémentez un algorithme de propagation, qui assigne à chaque case la distance au point de départ modulo 10, de sorte que vous ayez une chiffre de 0 à 9 dans chaque case.

Votre algorithme peut continuer de suivre le mur gauche, tout en assignant une distance à chacune des cases. Mais vous êtes libres d’implémenter le votre.

En toute hypothèse, une fois arrivé à la sortie avec cet algorithme, on peut connaitre le chemin le plus court en remontant depuis la sortie.

Pour la même carte qu’avant :

###S###
#...#.#
###.#.#
G.#...#
#.###.#
#.....#
#######

On se retrouverait avec :

###S###
#321#7#
###2#6#
G3#345#
#2###6#
#10987#
#######

Affichez cette carte à la suite de votre précédent affichage.

$ ./a.out map.txt
width: 7, height: 7
###S###
#.. # #
### # #
G #   #
# ### #
#     #
#######

distances to start:
###S###
#321#7#
###2#6#
G3#345#
#2###6#
#10987#
#######

En cas de difficulté

Coordonnées en Index

Implémentez la fonction dont le prototype est le suivant.

unsigned int coords_to_idx(unsigned int x,
			   unsigned int y,
			   unsigned int width);

D’après des coordonnées $(x,y)$ et une largeur, elle vous renvoie l’index qui correspond sur un tableau qui n’a qu’une seule dimension.

Référez vous aux explications dans l’étape 2.