Page principale

Cette page permet de tester différents algorithmes de parcours afin de résoudre un Sokoban. Ces algorithmes, leurs enjeux d'optimalité, de complexité temporelle et d'utilisation de la mémoire, sont largement détaillés sur cette page.

Un Sokoban est un jeu se déroulant sur une grille régulière telle que celle présentée ci-dessous. Le but du jeu est d'amener ces caisses aux emplacements cibles marqués d'une croix, en un nombre minimal de déplacement. Résoudre un niveau de Sokoban est un problème NP-difficile

On considérera dans toute la suite le nombre de déplacement de caisses - les déplacements de personnage qui ne poussent pas de caisse étant considérés de coût nul. Peu importe donc la position précise du personnage parmi l'ensemble des cases auxquelles il peut accéder sans déplacer de caisse.

Le problème peut donc se formuler comme un parcours dans le graphe des positions accessibles : chaque sommet est une position (décrite par la position des caisses et la zone où se trouve le personnage), et un arc relie deux sommets si et seulement si on peut passer du premier au second en poussant une caisse. On cherche alors dans ce graphe un chemin reliant la position initiale à la position cible, où chaque caisse est sur un emplacement cible.

L'application permet de tester différents niveaux, et différents algorithmes de parcours. Vous trouverez en dessous des précisions supplémentaires sur les algorithmes, et notamment sur les heuristiques utilisées pour les algorithmes d'exploration guidée.

Nouvelle position :


Résoudre :





Positions possibles pour les caisses :


Algorithme :
    Itérations :
    Temps :
    Mémoire utilisée :
    Longueur du chemin trouvé :




Éditeur de niveau

Cliquer plusieurs fois sur une case pour changer son contenu.



Références