Avant d'imprimer, retirer la feuille de style En cliquant ici

Consignes

Même si vous n'avez pas terminé le tp2, commencez le tp3 en séance (il faut au minimum avoir fait correctement afficheGrille()). Vous reprendrez le tp2 où vous vous étiez arrêté si vous terminez l'exercice 1.

Les objectifs

  • Allocation dynamique et lecture de fichier
  • Avancer le mini-projet "Sokoban"

Vous devrez terminer le mini-projet sokoban en travail personnel d'ici le mois de Janvier. Pour cela vous taperez la commande "make zip" et enverrez par mail au chargé de cours le fichier ".tgz" ainsi généré avant le 4e TP (4 janvier 2010). Ce travail peut être rendu individuellement ou par binôme, dans ce cas, n'oubliez pas de préciser les noms/prénoms des deux membres du binôme dans le mail.

Le Makefile a changé !

Le Makefile du tp2 a été mis à jour, utiliser la dernière version : Makefile (click!) :
  1.  
  2. CC=gcc
  3. CFLAGS=-Wall -ansi -pedantic
  4. LDFLAGS=
  5. EXEC=sokoban
  6. BIN=sokoban.o main.o
  7. SRC=sokoban.c main.c
  8. HEAD=sokoban.h
  9.  
  10. all: $(EXEC)
  11.  
  12. sokoban: $(BIN)
  13. $(CC) -o sokoban $(BIN) $(LDFLAGS)
  14.  
  15. %.o: %.c $(HEAD)
  16. $(CC) -c $< $(CFLAGS)
  17.  
  18. clean:
  19. rm -f *.o *~ 2> /dev/null
  20.  
  21. clear: clean
  22. rm -f $(EXEC) $(USER)_sokoban.tgz 2> /dev/null
  23.  
  24. zip: clear
  25. mkdir -p $(USER)_sokoban
  26. cp Makefile *.c *.h *.sok $(USER)_sokoban
  27. tar czf $(USER)_sokoban.tgz $(USER)_sokoban
  28. rm -rf $(USER)_sokoban
  29.  

Exercice 1 - Modification du type Grille

Allocation statique et tableaux à plusieurs dimensions

  • Commencez par taper la commande make clear.
  • Dans le fichier sokoban.h, remplacez les lignes : typedef char Ligne[LARGEUR+1];
    typedef Ligne Grille[HAUTEUR];
    par les lignes :
    typedef char* Ligne;
    typedef Ligne* Grille;
    Ne compilez pas pour l'instant.
  • Dans main.c, mettez en commentaire votre fonction main() et copiez celle-ci :
    int main(int argc, char ** argv){
      Grille initiale={
    	"########################",
    	"#.........#......#.....#",
    	"##.....O###............#",
    	"###.............O#.....#",
    	"####.............#O....#",
    	"##################.....#",
    	"####.............#.....#",
    	"###...............O..###",
    	"##...........#########o#",
    	"#....................oo#",
    	"#S....................o#",
    	"########################"
      };
      afficheGrille(initiale);
      return 0;
    }
    
    Ne compilez toujours pas.
  • Dans sokoban.c et sokoban.h, mettez en commentaire toutes les fonctions/procédures sauf afficheGrille();
    Ne décommentez pas avant que cela soit demandé
  • Compilez. Une erreur de compilation ?
    En principe vous n'obtenez que des avertissements (warnings), car nous n'avons pas changé le type réel de Grille (c'était un tableau de Ligne donc un Ligne *).
  • Exécutez. Segmentation Fault ?
    C'est normal, la fonction afficheGrille(Grille g); utilise un tableau à deux dimensions statique (g[][]) mais ne connait pas la taille des dimensions, et ne sait donc pas interpréter g[i][j] correctement !
  • Remplacez afficheGrille(Grille g) par afficheGrille(char g[][LARGEUR+1]) dans sokoban.c et sokoban.h et Grille initiale= par char initiale[][LARGEUR+1]= dans main.c ; ne changez rien d'autre, compilez et exécutez. Ça marche ?
    Cette fois, on a bien indiqué toutes les tailles sauf la première, pas de problème.
  • Cette solution n'est pourtant pas satisfaisante car nous ne souhaitons pas changer le prototype de afficheGrille(). Remettez donc afficheGrille(Grille g) dans sokoban.c/h et Grille intiale= dans main.c, puis passez à l'exercice suivant.

Allocation dynamique de la grille

  • Ajouter une fonction Grille initGrille() qui va :
    • Déclarer un tableau de char à deux dimensions statique :
      		char init[][LARGEUR+1] = {
      			"########...#",
      			...
      			"########...#"
      		}
    • Déclarer une Grille g et l'allouer dynamiquement avec malloc
    • Recopier ligne par ligne init dans g (pensez à allouer les lignes de la grille !)
    • Retourner g
    Faites vérifier vos malloc par un chargé de TP
  • Pourquoi ne peut on pas écrire initGrille comme une procédure : void initGrille(Grille g); ?
  • Écrivez la procédure void freeGrille(Grille g); qui libère la mémoire réservée pour la grille g passée en paramètre. Attention à bien libérer les lignes.
  • Dans le main, remplacez la déclaration statique de initiale par un appel à initGrille() et appellez la procédure freeGrille() avant l'instruction return 0;.

Grille de taille variable

Nous voulons maintenant pouvoir jouer avec plusieurs grilles différentes, et notamment de tailles différentes. Nous allons donc supprimer les deux constantes HAUTEUR et LARGEUR. Le type Grille va devenir une structure qui contient deux entiers (hauteur et largeur) plus un pointeur de Ligne.
typedef struct _grille{
	/* Completez */
	Ligne * grille;
} Grille;
  • Supprimez les constantes HAUTEUR et LARGEUR
  • Changez le type Grille dans sokoban.h
  • Adaptez les fonctions freeGrille(), initGrille() et afficheGrille(Grille g) dans sokoban.c, sans changer leur prototype. Vous pouvez écrire char init[][25] = {...} dans initGrille(), nous nous en occuperons dans l'exercice suivant.
  • Compilez et testez jusqu'à ce que ça marche

La fonction initGrille()

Nous allons maintenant nous débarrasser complètement des tableaux statiques en lisant la grille initiale dans un fichier texte.
  • Téléchargez le fichier grille1.sok. Comme vous pouvez le constater, ce fichier contient une ligne avec les dimensions de la grille, puis la grille sous sa forme textuelle, telle qu'elle serait affichée.
  • Modifiez le prototype de la fonction initGrille() pour qu'elle prenne en paramètre une chaîne de caractère
  • Dans le main, remplacez l'appel à initGrille() par initGrille("grille1.sok")
  • Dans initGrille(), supprimez la déclaration du tableau char init[][25]
  • À la place, vous aller dans l'ordre :
    1. ouvrir en mode lecture le fichier dont le nom est passé en paramètre avec fopen,
    2. utiliser fgets() pour lire la première ligne et la stocker dans une chaîne de caractères (tableau statique de taille 10 - on suppose que le nombre max de ligne/colonne est 9999),
    3. extraire les deux entiers de la chaîne récupérée à l'aide de sscanf(),
    4. allouer le tableau de Ligne de votre Grille,
    5. pour chaque ligne, l'allouer puis donner son adresse à fgets() pour la lire dans le fichier. Attention à donner la bonne valeur de size ! N'oubliez pas de lire le '\n' (avec fgetc() par exemple) avant de lire la ligne suivante.
    6. fermer le fichier avec fclose()

Exercice 2 - Retour au main de la fin du TP2

Vous devez avoir terminé le TP2 avant de commencer cet exercice.
Vous pouvez maintenant revenir à la version du main de la fin du tp2 : mettez votre nouveau main en commentaire, décommentez l'ancien ainsi que les fonctions de sokoban.c/h. Faites les changements nécessaires pour que le code compile et marche (lire les 5 points avant de commencer svp):
  • Partout où on utilisait les constantes LARGEUR/HAUTEUR, utiliser le champs correspondant de Grille
  • Faites une fonction Grille creerGrille(int hauteur, int largeur); qui créée une variable Grille, affecte les bonnes dimensions à ses champs, alloue l'espace necessaire (copier/coller du code de init)puis renvoit la Grille.
  • Modifiez initGrille() pour qu'elle appelle creerGrille au lieu de refaire le travail
  • Faites également une fonction Grille copieGrille(Grille g) qui appelle creerGrille et copie dans la nouvelle grille la grille passée en paramètre, puis retourne la nouvelle grille.
  • Le programme commence alors par un appel à initGrille() pour créer la grille initiale puis par deux appels à copieGrille() pour créer la grille cachée et la grille à afficher

Exercice 3 - La fonction undo

Nous voulons maintenant ajouter une commande undo qui permet d'annuler la dernière action, c'est à dire la dernière modification de la grille. Pour cela nous allons gérer dans le main une liste chaînée de Grille. Chaque version successive de la grille sera ajoutée en tête de la liste, et lorsque l'on veut revenir en arrière, il suffit de supprimer le premier maillon pour revenir à la grille précédante.

Les types List et Cell

Vous déclarerez les nouveaux types suivants dans un fichier pileGrille.h :

  • le type Cell pour représenter un maillon de la liste. Il comportera une Grille, une Position (celle du Sokoban, pour ne pas avoir à la retrouver à chaque undo), et un pointeur sur le maillon suivant.
  • le type List qui ne sera qu'un pointeur de Cell

Déclarez une List dans le main() et initialisez-la à NULL pour indiquer que la liste est vide.

Ajoutez dans un fichier pileGrille.c :

  • la procédure Cell* newCell(); qui alloue la mémoire nécessaire à un maillon (attention on alloue pas la grille dans cette procédure)
  • la procédure void freeCell(Cell* c); qui libère la mémoire associée au maillon passé en paramètre.
  • la procédure void freeList(List l); qui libère la mémoire associée à l'ensemble de la liste passée en paramètre (vous pouvez l'écrire récursivement).

Ajouté les prototypes des fonctions dans pileGrille.h puis Modifier le Makefile :

  • ajoutez pileGrille.o à la liste des fichiers binaires (ligne 6),
  • pileGrille.c à celle des fichiers source (ligne 7)
  • et pileGrille.h à celle des headers (ligne 8)

Compilez jusqu'à ne plus avoir d'erreur, puis passez à la suite.

Opérations sur la pile : push et pop

Nous allons écrire les fonctions necessaires pour pouvoir utiliser notre liste comme une pile : push() pour ajouter un élément au sommet de la pile (tête de la liste), pop() pour retirer le sommet de la pile (tête de la liste).

Dans pileGrille.c :
  • push: Écrivez la fonction List push(List l, Grille g, Position p);. Pour cela, il faut :
    • créer un nouveau maillon (newCell()),
    • recopier la grille passée en paramètre (copieGrille()),
    • affecter la nouvelle grille et la position passées en paramètres au nouveau maillon,
    • ajouter ce maillon en tête de la liste (c'est à dire l'empiler) en affectant son élément suivant à l'ancienne liste.
    • retourner la nouvelle liste, c'est à dire le nouveau maillon.
    Attention à ne pas casser le chaînage !
  • pop:
    • Comment récupère-t-on la dernière Grille empilée et la position de Sokoban ?
    • Écrivez la procédure void pop(List * l) qui supprime le premier maillon de la liste (n'oubliez pas de libérez la mémoire avec freeCell())
    • Pourquoi la liste est-elle passée par adresse ?
  • Pour éviter d'avoir à écrire List l=...; l=push(l,g,p); transformer la fonction push() en procédure qui prend en paramètre non plus une liste mais un pointeur de liste: void push(List * l, Grille g, Poisition p);. On peut maintenant écrire List l=...; push(&l,g,p);

undo

  • Ajoutez la commande undo au type énuméré, à la commande d'aide, et au switch du main().
  • Dans ce dernier, incrémentez le nombre de coups, testez si la pile est vide (dans ce cas, affichez un message), sinon dépilez.
  • N'oubliez pas d'empiler au bon moment.
  • Compilez, et testez le jeu, en particulier la nouvelle commande.

Exercice 4 - Repassage par adresse

En général, on évite d'utiliser le passage par copie pour les structures car ça peut être couteux. Modifier votre programme pour toujours passer la grille par adresse aux fonctions. Notamment, la fonction Grille initGrille(char * fileName); va devenir int initGrille(Grille * g, char * fileName);. Le retour de la fonction sera utilisé pour renvoyer un code d'erreur. L'allocation de la structure se fera dans initGrille(), et la libération de la mémoire associée dans freeGrille().

Fin du mini projet Sokoban

Avant de rendre votre programme (commande make zip puis envoi par mail au chargé de cours du fichier ainsi généré, avant le 4 janvier), pensez à :
  • Commenter vos sources, en particulier les .h
  • Faire deux documentations :
    • user.pdf : manuel d'utilisation de votre programme destiné à être lu par un utilisateur (compilation, installation, utilisation, ...)
    • dev.pdf : manuel d'utilisation de votre programme destiné à être lu par un développeur (design de conception, choix algorithmiques, rapport de bogue connus, optimisations possibles, ...)
    et les ajouter à votre email.
  • Vous êtes libre d'ajouter toutes les fonctionnalités qui vous passeraient par la têtes, n'oubliez pas de les commenter et de les décrire dans les manuels. Quelques suggestions ci-dessous.

Précision sur la documentation

Commenter le code, ça veut dire que dans les .h il faut mettre des commentaires qui expliquent ce que fait chaque fonctions, et comment elle s'utilise si il y a une façon particulière de l'utiliser (par exemple si il ne faut pas oublier de lire le code de retour d'une fonction), ou ce qui se passe si on donne un mauvais argument etc... vous pouvez vous inspirer des informations qui se trouve dans la javadoc des API standards de Java.

Dans les .c, il faut commenter seulement si il y a utilisation d'astuces, ou du code un peu illisible etc.

Dans la documentation développeur, il faut expliquer les choix algorithmiques et leur raison (si plusieurs possibilité expliquer la raison du choix), il faut expliquer comment un développeur devrait s'y prendre pour rajouter des fonctionnalités etc. En fait il faut se mettre à la place de qqun qui reprendrait votre projet, et lui faciliter la vie. Ne pas oublier aussi de parler de ce qui ne marche pas dans cette documentation.

Pour la documentation utilisateur, c'est la plus simple, il faut dire ce qu'on trouve dans l'archive, comment compiler et comment lancer le jeu, expliquer le but du jeu et comment utiliser l'interface. Il faut se mettre à la place de qqun qui voudrait jouer avec votre Sokoban.

Améliorations possibles

  • error() : ajoutez lui un paramètre chaîne de caractères et un entier ; la chaîne sera systématiquement affichée avant le message d'erreur, et l'entier pourra être nul s'il ne sert à rien. Modifiez tous les appels à error() pour qu'ils passent le nom de la fonction qui génère l'erreur.
  • getSokoban() : générez l'erreur 5 s'il y a plusieurs Sokoban dans la grille initiale.
  • verifJeu() : peut-on trouver un algorithme pour détecter dans la grille initiale qu'une caisse coincée contre un mur ne pourra jamais être poussée vers une cible ?
  • Récupérez les arguments de la ligne de commande, et s'il y n'y en a bien qu'un seul, utilisez-le comme nom du fichier d'initialisation (en ajoutant automatiquement l'extension .txt).
  • Lorsqu'on gagne(), ne terminez plus le programme, mais regardez s'il existe un fichier "de même nom + 1" que le fichier initial (grille2.sok par exemple), et continuez le jeu à ce niveau supérieur (et ainsi de suite ...)
  • Rendez plus modulaire le programme en séparant plus les différentes composantes (ex: type.h pour les typedef etc., util.c pour les fonctions d'affichages etc). N'oubliez pas de décrire l'architecture retenue dans le fichier dev.pdf et de modifier le Makefile.
  • Si vous écrivez des fichiers de niveaux, n'oubliez pas de les joindre à l'archive (ajoutez à la fin de la ligne 27 du makefile *.sok)
  • Faites une interface graphique en gtk+ par exemple
  • ...