Utiliser une pile pour traverser et résoudre un labyrinthe - Java

Question

J'essaie donc de créer un programme de résolution de labyrinthe qui résoudrait un labyrinthe de X et de O. Ce que j'aimerais faire, c'est créer une classe de points, afin de pouvoir créer un tableau bidimensionnel de points, ce qui permettrait d'imprimer sur une page de sortie et d'implémenter la pile de manière relativement simple.

L'algorithme le plus simple de l'idée générale que j'aimerais mettre en œuvre dans le programme lui-même devrait être, selon moi, le suivant :

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

Mais j'ai du mal à trouver un algorithme plus approfondi, ainsi qu'à mettre en place ma classe de points. Je sais que pour les points, je devrais avoir des coordonnées X et Y, ainsi que des getters pour les deux. Pensez-vous que j'ai besoin de plus de méthodes que ces deux-là ? Par exemple, devrais-je créer une méthode qui passe une coordonnée x et une coordonnée y comme paramètres pour que je puisse simplement les regrouper en une seule, au lieu de définir x et y individuellement ?

Voici à quoi ressemblerait un exemple de labyrinthe, dans lequel vous commencez en bas à droite et essayez de traverser jusqu'en haut à gauche, les X représentant les murs et les O les espaces ouverts du labyrinthe :

O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O 
X X O X X X O

Answer 1

Etes-vous sûr que votre algorithme pourrait résoudre n'importe quel labyrinthe ? Je pense qu'il se bloquerait dans cette maquette simple (où S est le départ et F l'arrivée) :

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

Votre algorithme descendrait le premier couloir jusqu'à ce qu'il soit face à la chute, tournerait à gauche, serait face au mur "nord", tournerait à nouveau à gauche, et redescendrait le premier couloir, où il tournerait à gauche deux fois encore et continuerait à répéter ce problème.

L'algorithme de la règle de la main droite (voir le document page wikipédia (ainsi que d'autres sections pour d'autres algues de labyrinthe) devrait permettre de résoudre n'importe quel labyrinthe sans boucle, et devrait être assez facile à implémenter en Java.

Answer 2

Vous pourriez utiliser un

Stack<Point> points = new Stack<>();

// add a point
Point p = new Point(x, y);
if (points.contains(p))
   // been here before, in circles.
else
   points.add(p);

Answer 3

Pour l'algorithme, vous pourriez utiliser retour en arrière ( EDITAR bien que cela ne corresponde pas tout à fait à votre idée générale). Vous devez simplement réaliser que vos mouvements sont "poussés" dans une pile virtuelle et qu'ils doivent être défaits (et donc annulés). Vous devrez peut-être implémenter la pile vous-même si le "robot" est un objet qui se déplace réellement, mais vous pouvez compter sur la pile d'appel si vous voulez simplement résoudre le labyrinthe.

Answer 4

Pour la partie algorithmique, une récursion en profondeur dans la pile est préférable. Quelque chose du genre :

currentSpot = (0,0)  // The starting point //

while(! currentSpot.isExit()) {

  if (! currentSpot.left().isWall()) stack.push(currentSpot.left());
  if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward());
  if (! currentSpot.right().isWall()) stack.push(currentSpot.right());

  currentSpot = stack.pop();  // Get the next location //
}

Vous voudrez que votre classe de points renvoie le point suivant dans chaque direction donnée (sauf en arrière), et qu'elle détecte le moment où vous vous trouvez aux limites du labyrinthe. Vous aurez probablement besoin d'une classe Maze qui contient tous les points, effectue l'impression, stocke les X/O, etc. Ainsi, vous pourriez probablement remplacer le point initial currentSpot = (0,0) par currentSpot = Maze.getStartingSpot() ;

Answer 5

Pour votre algorithme, vous n'avez pas besoin d'une pile. Ce n'est que si vous utilisez le backtracking pour annuler une décision de traversée que vous aurez besoin d'une pile.