Un solucionador de laberintos en Java

Programación

1. Introducción

En este artículo, exploraremos posibles formas de navegar por un laberinto utilizando Java.

Considere que el laberinto es una imagen en blanco y negro, con píxeles negros que representan paredes y píxeles blancos que representan un camino. Dos píxeles blancos son especiales, uno es la entrada al laberinto y otro la salida.

Dado tal laberinto, queremos encontrar un camino desde la entrada hasta la salida.

2. Modelando el laberinto

Consideraremos que el laberinto es una matriz de enteros 2D. El significado de los valores numéricos en la matriz será según la siguiente convención:

  • 0 -> Carretera
  • 1 -> Pared
  • 2 -> Entrada al laberinto
  • 3 -> Salida del laberinto
  • 4 -> Parte de la celda del camino desde la entrada hasta la salida

Modelaremos el laberinto como un gráfico . La entrada y la salida son los dos nodos especiales, entre los cuales se determinará el camino.

Un gráfico típico tiene dos propiedades, nodos y bordes. Un borde determina la conectividad del gráfico y vincula un nodo a otro.

Por lo tanto, asumiremos cuatro bordes implícitos de cada nodo, vinculando el nodo dado a su nodo izquierdo, derecho, superior e inferior.

Definamos la firma del método:

public List solve(Maze maze) { }

La entrada al método es un laberinto, que contiene la matriz 2D, con la convención de nomenclatura definida anteriormente.

La respuesta del método es una lista de nodos, que forma una ruta desde el nodo de entrada al nodo de salida.

3. Backtracker recursivo (DFS)

3.1. Algoritmo

Un enfoque bastante obvio es explorar todos los caminos posibles, que finalmente encontrarán un camino si existe. Pero tal enfoque tendrá una complejidad exponencial y no escalará bien.

Sin embargo, es posible personalizar la solución de fuerza bruta mencionada anteriormente, retrocediendo y marcando los nodos visitados, para obtener una ruta en un tiempo razonable. Este algoritmo también se conoce como búsqueda en profundidad.

Este algoritmo se puede describir como:

  1. Si estamos en la pared o en un nodo ya visitado, devuelve el error.
  2. De lo contrario, si somos el nodo de salida, devuelve el éxito
  3. De lo contrario, agregue el nodo en la lista de rutas y viaje recursivamente en las cuatro direcciones. Si se devuelve el error, elimine el nodo de la ruta y devuelva el error. La lista de rutas contendrá una ruta única cuando se encuentre la salida

Apliquemos este algoritmo al laberinto que se muestra en la Figura-1 (a), donde S es el punto de partida y E es la salida.

Para cada nodo, recorremos cada dirección en orden: derecha, abajo, izquierda, arriba.

En 1 (b), exploramos un camino y golpeamos la pared. Luego retrocedemos hasta encontrar un nodo que tiene vecinos que no son de pared y exploramos otra ruta como se muestra en 1 (c).

Nuevamente golpeamos la pared y repetimos el proceso para finalmente encontrar la salida, como se muestra en 1 (d):

3.2. Implementación

Veamos ahora la implementación de Java:

Primero, necesitamos definir las cuatro direcciones. Podemos definir esto en términos de coordenadas. Estas coordenadas, cuando se agregan a cualquier coordenada dada, devolverán una de las coordenadas vecinas:

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

También necesitamos un método de utilidad que agregará dos coordenadas:

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

Ahora podemos definir la firma del método solve. La lógica aquí es simple : si hay una ruta de entrada a salida, devuelva la ruta, de lo contrario, devuelva una lista vacía:

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

Definamos el método de exploración mencionado anteriormente. Si hay una ruta, devuelve verdadero, con la lista de coordenadas en la ruta del argumento . Este método tiene tres bloques principales.

Primero, descartamos los nodos inválidos, es decir, los nodos que están fuera del laberinto o son parte del muro. Después de eso, marcamos el nodo actual como visitado para que no visitemos el mismo nodo una y otra vez.

Finalmente, nos movemos recursivamente en todas las direcciones si no se encuentra la salida:

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; }

Esta solución utiliza un tamaño de pila hasta el tamaño del laberinto.

4. Variante: ruta más corta (BFS)

4.1. Algoritmo

El algoritmo recursivo descrito anteriormente encuentra la ruta, pero no es necesariamente la ruta más corta. Para encontrar la ruta más corta, podemos usar otro enfoque de recorrido de gráfico conocido como búsqueda primero en amplitud.

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; }

Definamos ahora el método principal solve. Reutilizaremos los tres bloques usados ​​en la implementación de DFS, es decir, validaremos el nodo, marcaremos el nodo visitado y atravesaremos los nodos vecinos.

Solo haremos una pequeña modificación. En lugar de un recorrido recursivo, usaremos una estructura de datos FIFO para rastrear vecinos e iterar sobre ellos:

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. Conclusión

En este tutorial, describimos dos algoritmos de gráficos principales: búsqueda primero en profundidad y búsqueda primero en ancho para resolver un laberinto. También mencionamos cómo BFS ofrece el camino más corto desde la entrada hasta la salida.

Para obtener más información, busque otros métodos para resolver un laberinto, como el algoritmo A * y Dijkstra.

Como siempre, el código completo se puede encontrar en GitHub.