retour aux essais techniques python ou autres
Principe des algorithmes BFS et DFS de recherche dans un réseau appliqué à la solution pas à pas du jeu balls sort
Ces algorithmes sont utilisés par les jeux à un seul joueur :
- recherche de la sortie d’un labyrinthe.
- appliqué ici au tri des balles couleurs dans des tubes.
Les algorithmes de parcours de graphe peuvent sembler simples dans leur principe. Il y en a de nombreuses descriptions mais ce n'est pas toujours faciles de les utiliser pour résoudre un jeu.
Cet article vous propose d'utiliser deux méthodes de recherche : DFS, exploration en profondeur récursive et BFS exploration en largeur avec de simples listes.
Les tests permettront de comparer les performances des deux méthodes en les appliquant à plusieurs jeux ball sort du plus simple au plus compliqué.
BALLS SORT, jeu pour regrouper des balles par couleur dans des tubes
Présentation du jeu
Les tubes sont placés horizontalement, le programme va explorer les possibilités puis donner la solution pas à pas
Dans l’exemple ci-dessous, il y a 13 tubes dont 2 vides (couleur noire).
Les tubes sont présentés en horizontal.
Le programme comprend trois parties :
- l’initialisation : lecture du fichier texte pour créer la matrice du jeu.
- la recherche de la solution : liste des mouvements de tube à tube pour regrouper les couleurs.
- l'affichage du jeu et de sa solution pas à pas : liste des mouvements de tube à tube pour regrouper les couleurs.
1- L’initialisation :
Le jeu est initié à partir d’un fichier ,txt énumérant les couleurs à raison d’une ligne par tube ou ‘0’ si le tube est vide (les emplacements libres sont en noir, (les tubes 12 et 13 sont vides). Le but est d’obtenir des tubes de couleur uniforme,
à partir de ce fichier txt, on constitue la matrice du jeu sous la forme de liste de listes
M = [
[les couleurs du tube 0],
[les couleurs du tube 1],
,,,[les couleurs du tube 11],[], []
]
2- Recherche de la solution par les deux méthodes DFS et BFS :
Sur un exemple simple de graphe,
l’algorithme Deep First Search, recherche en profondeur
Sur cet exemple, l’exploration DFS se fera de A vers B, puis de B vers C et D qui sont des impasses. On doit remonter ensuite à A pour explorer E puis F et trouver G qui est le but.
Breadth First testera les jeux par niveaux A,( B, E, F ), (C, D, G)
Les deux méthodes utiliseront des listes d'étapes à parcourir (THIST) et de mouvements à faire(lmvt).
Ces mouvements (i,j,k) décriront le déplacement de k balles du tube i vers le tube j
Pour éviter de retester des étapes déjà vues et donc de boucler indéfiniment, on enregistre les étapes parcourues dans TVUS.
3- l’affichage pas à pas de la solution
En utilisant le module python TKINTER, on affichera le jeu initial et son évolution en appliquant les mouvements de la liste solution trouvée par la méthode 2 (DFS ou BFS)
Voir le programme python
