Contexte et objectifs
Après la SAE 1.01, le projet Sokoban en C était fonctionnel mais purement manuel. Dans le cadre de la compétence Optimiser, l'équipe pédagogique a proposé de passer à la résolution algorithmique automatique du jeu.
L'objectif était de faire jouer le programme lui-même, en trouvant et en comparant plusieurs approches pour résoudre les niveaux automatiquement — d'abord par lecture de fichiers de déplacements, puis par un algorithme de recherche de chemin optimisé. Le projet était réalisé en binôme avec Hadrien Gaspard Le Guillou.
Nous avons d'abord implémenté la lecture de fichiers .dep (séquences de déplacements pré-définies), puis conçu un algorithme de recherche permettant de calculer automatiquement les déplacements optimaux. Les deux approches ont été comparées en termes de complexité algorithmique et de performances mesurées.
Deux implémentations fonctionnelles ont été livrées avec une analyse comparative documentée. Cette SAE m'a appris à formaliser la comparaison d'algorithmes, à mesurer leur efficacité et à justifier le choix d'une solution selon les contraintes du problème.
Étapes du projet
- 1Déplacements automatiques (Étape 1) — Lecture de fichiers .dep contenant des séquences de déplacements pré-définies et exécution automatique dans le jeu.
- 2Déplacements optimisés (Étape 2) — Implémentation d'un algorithme de recherche de chemin pour automatiser et optimiser les déplacements, comparaison des approches.
Ce qui a été réalisé
- Lecture et interprétation de fichiers de déplacements .dep
- Exécution automatique des séquences dans le moteur Sokoban
- Algorithme de recherche de chemin pour résolution automatique
- Comparaison des deux approches (complexité, performance)
- Documentation des résultats et justification du choix retenu
Aperçus du projet
