Exploration algorithmique
Trouver la sortie du donjon, le plus vite possible.
- Type
- Algorithmique
- Cadre
- Projet en binôme, BUT 1
- Année
- 2025
- Technologies
- Java, Graphes
Un donjon est décrit dans un simple fichier texte : des salles, des passages, un départ A et une arrivée B. Le programme le transforme en graphe, cherche un chemin avec trois algorithmes, parcours en profondeur (DFS), parcours en largeur (BFS) et A*, puis traduit la solution en directions : nord, sud, est, ouest.
Chaque donjon est résolu 10 000 fois par algorithme pour mesurer le temps, et on compte les salles explorées. Sur le donjon 6, DFS trouve un chemin de 78 salles là où BFS et A* en trouvent 10 ; A* y arrive en explorant 63 salles, contre 275 pour BFS.
J’ai codé le parcours en largeur, A* avec une heuristique de Manhattan, la transformation du donjon en graphe et celle de la solution en directions. J’ai aussi créé les deux donjons ajoutés : l’un presque linéaire avec un détour imposé, l’autre très maillé pour montrer les limites de DFS.
- DFS, BFS et A* comparés sur huit donjons
- Deux donjons créés pour piéger les algorithmes
- Mesures de temps et de salles explorées