Un résolveur de labyrinthe à Java

1. Introduction

Dans cet article, nous explorerons les moyens possibles de naviguer dans un labyrinthe à l'aide de Java.

Considérez le labyrinthe comme une image en noir et blanc, avec des pixels noirs représentant les murs et des pixels blancs représentant un chemin. Deux pixels blancs sont spéciaux, l'un étant l'entrée du labyrinthe et une autre sortie.

Compte tenu d'un tel labyrinthe, nous voulons trouver un chemin entre l'entrée et la sortie.

2. Modélisation du labyrinthe

Nous considérerons le labyrinthe comme un tableau d'entiers 2D. La signification des valeurs numériques dans le tableau sera conforme à la convention suivante:

  • 0 -> Route
  • 1 -> Mur
  • 2 -> Entrée du labyrinthe
  • 3 -> Sortie labyrinthe
  • 4 -> Cellule partie du chemin de l'entrée à la sortie

Nous modéliserons le labyrinthe sous forme de graphique . L'entrée et la sortie sont les deux nœuds spéciaux entre lesquels le chemin doit être déterminé.

Un graphe typique a deux propriétés, des nœuds et des arêtes. Une arête détermine la connectivité du graphe et relie un nœud à un autre.

Par conséquent, nous supposerons quatre arêtes implicites de chaque nœud, reliant le nœud donné à ses nœuds gauche, droit, supérieur et inférieur.

Définissons la signature de la méthode:

public List solve(Maze maze) { }

L'entrée de la méthode est un labyrinthe, qui contient le tableau 2D, avec la convention de dénomination définie ci-dessus.

La réponse de la méthode est une liste de nœuds, qui forme un chemin entre le nœud d'entrée et le nœud de sortie.

3. Backtracker récursif (DFS)

3.1. Algorithme

Une approche assez évidente consiste à explorer tous les chemins possibles, qui finiront par trouver un chemin s'il existe. Mais une telle approche aura une complexité exponentielle et ne s'adaptera pas bien.

Cependant, il est possible de personnaliser la solution de force brute mentionnée ci-dessus, en effectuant un retour en arrière et en marquant les nœuds visités, pour obtenir un chemin dans un délai raisonnable. Cet algorithme est également connu sous le nom de recherche en profondeur d'abord.

Cet algorithme peut être décrit comme:

  1. Si nous sommes au mur ou à un nœud déjà visité, retournez échec
  2. Sinon, si nous sommes le nœud de sortie, retournez le succès
  3. Sinon, ajoutez le nœud dans la liste des chemins et voyagez de manière récursive dans les quatre directions. Si un échec est renvoyé, supprimez le nœud du chemin et renvoyez l'échec. La liste des chemins contiendra un chemin unique lorsque la sortie est trouvée

Appliquons cet algorithme au labyrinthe illustré à la figure 1 (a), où S est le point de départ et E la sortie.

Pour chaque nœud, nous parcourons chaque direction dans l'ordre: droite, bas, gauche, haut.

En 1 (b), nous explorons un chemin et frappons le mur. Ensuite, nous faisons marche arrière jusqu'à ce qu'un nœud soit trouvé qui a des voisins non-mur, et explorons un autre chemin comme indiqué dans 1 (c).

Nous frappons à nouveau le mur et répétons le processus pour enfin trouver la sortie, comme indiqué en 1 (d):

3.2. la mise en oeuvre

Voyons maintenant l'implémentation Java:

Premièrement, nous devons définir les quatre directions. Nous pouvons définir cela en termes de coordonnées. Ces coordonnées, lorsqu'elles sont ajoutées à une coordonnée donnée, renverront l'une des coordonnées voisines:

private static int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 

Nous avons également besoin d'une méthode utilitaire qui ajoutera deux coordonnées:

private Coordinate getNextCoordinate( int row, int col, int i, int j) { return new Coordinate(row + i, col + j); }

Nous pouvons maintenant définir la signature de la méthode résoudre. La logique ici est simple - s'il y a un chemin entre l'entrée et la sortie, retournez le chemin, sinon, retournez une liste vide:

public List solve(Maze maze) { List path = new ArrayList(); if ( explore( maze, maze.getEntry().getX(), maze.getEntry().getY(), path ) ) { return path; } return Collections.emptyList(); }

Définissons la méthode d' exploration référencée ci-dessus. S'il y a un chemin, retournez true, avec la liste des coordonnées dans le chemin de l'argument . Cette méthode comporte trois blocs principaux.

Tout d'abord, nous rejetons les nœuds invalides, c'est-à-dire les nœuds qui sont à l'extérieur du labyrinthe ou qui font partie du mur. Après cela, nous marquons le nœud actuel comme visité afin de ne pas visiter le même nœud encore et encore.

Enfin, on se déplace récursivement dans toutes les directions si la sortie n'est pas trouvée:

private boolean explore( Maze maze, int row, int col, List path) { if ( !maze.isValidLocation(row, col) || maze.isWall(row, col) || maze.isExplored(row, col) ) { return false; } path.add(new Coordinate(row, col)); maze.setVisited(row, col, true); if (maze.isExit(row, col)) { return true; } for (int[] direction : DIRECTIONS) { Coordinate coordinate = getNextCoordinate( row, col, direction[0], direction[1]); if ( explore( maze, coordinate.getX(), coordinate.getY(), path ) ) { return true; } } path.remove(path.size() - 1); return false; }

Cette solution utilise la taille de la pile jusqu'à la taille du labyrinthe.

4. Variante - Chemin le plus court (BFS)

4.1. Algorithme

L'algorithme récursif décrit ci-dessus trouve le chemin, mais ce n'est pas nécessairement le chemin le plus court. Pour trouver le chemin le plus court, nous pouvons utiliser une autre approche de traversée de graphe appelée recherche en largeur d'abord.

In DFS, one child and all its grandchildren were explored first, before moving on to another child. Whereas in BFS, we'll explore all the immediate children before moving on to the grandchildren. This will ensure that all nodes at a particular distance from the parent node, are explored at the same time.

The algorithm can be outlined as follows:

  1. Add the starting node in queue
  2. While the queue is not empty, pop a node, do following:
    1. If we reach the wall or the node is already visited, skip to next iteration
    2. If exit node is reached, backtrack from current node till start node to find the shortest path
    3. Else, add all immediate neighbors in the four directions in queue

One important thing here is that the nodes must keep track of their parent, i.e. from where they were added to the queue. This is important to find the path once exit node is encountered.

Following animation shows all the steps when exploring a maze using this algorithm. We can observe that all the nodes at same distance are explored first before moving onto the next level:

4.2. Implementation

Lets now implement this algorithm in Java. We will reuse the DIRECTIONS variable defined in previous section.

Lets first define a utility method to backtrack from a given node to its root. This will be used to trace the path once exit is found:

private List backtrackPath( Coordinate cur) { List path = new ArrayList(); Coordinate iter = cur; while (iter != null) { path.add(iter); iter = iter.parent; } return path; }

Définissons maintenant la méthode de base résoudre. Nous réutiliserons les trois blocs utilisés dans l'implémentation DFS, c'est-à-dire valider le nœud, marquer le nœud visité et traverser les nœuds voisins.

Nous allons juste faire une légère modification. Au lieu d'un parcours récursif, nous utiliserons une structure de données FIFO pour suivre les voisins et les parcourir:

public List solve(Maze maze) { LinkedList nextToVisit = new LinkedList(); Coordinate start = maze.getEntry(); nextToVisit.add(start); while (!nextToVisit.isEmpty()) { Coordinate cur = nextToVisit.remove(); if (!maze.isValidLocation(cur.getX(), cur.getY()) || maze.isExplored(cur.getX(), cur.getY()) ) { continue; } if (maze.isWall(cur.getX(), cur.getY())) { maze.setVisited(cur.getX(), cur.getY(), true); continue; } if (maze.isExit(cur.getX(), cur.getY())) { return backtrackPath(cur); } for (int[] direction : DIRECTIONS) { Coordinate coordinate = new Coordinate( cur.getX() + direction[0], cur.getY() + direction[1], cur ); nextToVisit.add(coordinate); maze.setVisited(cur.getX(), cur.getY(), true); } } return Collections.emptyList(); }

5. Conclusion

Dans ce didacticiel, nous avons décrit deux algorithmes graphiques majeurs: la recherche en profondeur d'abord et la recherche en largeur d'abord pour résoudre un labyrinthe. Nous avons également abordé la manière dont BFS donne le chemin le plus court de l'entrée à la sortie.

Pour plus d'informations, recherchez d'autres méthodes pour résoudre un labyrinthe, comme l'algorithme A * et Dijkstra.

Comme toujours, le code complet peut être trouvé sur GitHub.