Un risolutore di labirinti in Java

1. Introduzione

In questo articolo, esploreremo i possibili modi per navigare in un labirinto, usando Java.

Considera il labirinto un'immagine in bianco e nero, con pixel neri che rappresentano i muri e pixel bianchi che rappresentano un percorso. Due pixel bianchi sono speciali, uno è l'entrata al labirinto e un altro l'uscita.

Dato un tale labirinto, vogliamo trovare un percorso dall'ingresso all'uscita.

2. Modellare il labirinto

Considereremo il labirinto come un array di numeri interi 2D. Il significato dei valori numerici nella matrice sarà secondo la seguente convenzione:

  • 0 -> Strada
  • 1 -> Muro
  • 2 -> Ingresso labirinto
  • 3 -> Uscita dal labirinto
  • 4 -> Cella parte del percorso dall'ingresso all'uscita

Modelleremo il labirinto come un grafico . L'entrata e l'uscita sono i due nodi speciali, tra i quali deve essere determinato il percorso.

Un grafico tipico ha due proprietà, nodi e bordi. Un bordo determina la connettività del grafico e collega un nodo a un altro.

Quindi supporremo quattro bordi impliciti da ciascun nodo, collegando il nodo dato al suo nodo sinistro, destro, superiore e inferiore.

Definiamo la firma del metodo:

public List solve(Maze maze) { }

L'input per il metodo è un labirinto, che contiene l'array 2D, con la convenzione di denominazione definita sopra.

La risposta del metodo è un elenco di nodi, che forma un percorso dal nodo di ingresso al nodo di uscita.

3. Backtracker ricorsivo (DFS)

3.1. Algoritmo

Un approccio abbastanza ovvio è esplorare tutti i percorsi possibili, che alla fine troveranno un percorso se esiste. Ma un tale approccio avrà una complessità esponenziale e non scalerà bene.

Tuttavia, è possibile personalizzare la soluzione di forza bruta sopra menzionata, tornando indietro e contrassegnando i nodi visitati, per ottenere un percorso in un tempo ragionevole. Questo algoritmo è noto anche come ricerca in profondità.

Questo algoritmo può essere descritto come:

  1. Se siamo al muro o un nodo già visitato, restituisci fallimento
  2. Altrimenti, se siamo il nodo di uscita, restituisci successo
  3. Altrimenti, aggiungi il nodo nell'elenco dei percorsi e viaggia in modo ricorsivo in tutte e quattro le direzioni. Se viene restituito un errore, rimuovere il nodo dal percorso e restituire un errore. L'elenco dei percorsi conterrà un percorso univoco quando viene trovata l'uscita

Applichiamo questo algoritmo al labirinto mostrato nella Figura 1 (a), dove S è il punto di partenza ed E è l'uscita.

Per ogni nodo, percorriamo ciascuna direzione in ordine: destra, in basso, a sinistra, in alto.

In 1 (b), esploriamo un percorso e colpiamo il muro. Quindi torniamo indietro fino a trovare un nodo che ha vicini non wall ed esploriamo un altro percorso come mostrato in 1 (c).

Colpiamo di nuovo il muro e ripetiamo il processo per trovare finalmente l'uscita, come mostrato in 1 (d):

3.2. Implementazione

Vediamo ora l'implementazione di Java:

Per prima cosa, dobbiamo definire le quattro direzioni. Possiamo definirlo in termini di coordinate. Queste coordinate, se aggiunte a una determinata coordinata, restituiranno una delle coordinate vicine:

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

Abbiamo anche bisogno di un metodo di utilità che aggiungerà due coordinate:

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

Ora possiamo definire la risoluzione della firma del metodo . La logica qui è semplice : se c'è un percorso dall'entrata all'uscita, restituisci il percorso, altrimenti restituisci un elenco vuoto:

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

Definiamo il metodo di esplorazione a cui si fa riferimento sopra. Se è presente un percorso, restituisci true, con l'elenco delle coordinate nell'argomento percorso . Questo metodo ha tre blocchi principali.

Per prima cosa, scartiamo i nodi non validi, cioè i nodi che si trovano all'esterno del labirinto o fanno parte del muro. Dopodiché, contrassegniamo il nodo corrente come visitato in modo da non visitare lo stesso nodo più e più volte.

Infine, ci muoviamo ricorsivamente in tutte le direzioni se l'uscita non viene trovata:

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

Questa soluzione utilizza la dimensione dello stack fino alla dimensione del labirinto.

4. Variante - Percorso più breve (BFS)

4.1. Algoritmo

L'algoritmo ricorsivo descritto sopra trova il percorso, ma non è necessariamente il percorso più breve. Per trovare il percorso più breve, possiamo utilizzare un altro approccio di attraversamento del grafico noto come ricerca Breadth-first.

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

Definiamo ora il metodo principale per risolvere. Riutilizzeremo i tre blocchi utilizzati nell'implementazione di DFS, vale a dire convalidare il nodo, contrassegnare il nodo visitato e attraversare i nodi vicini.

Faremo solo una piccola modifica. Invece di attraversamento ricorsivo, useremo una struttura dati FIFO per tracciare i vicini e iterarli su di essi:

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. conclusione

In questo tutorial, abbiamo descritto due principali algoritmi di grafi Ricerca prima in profondità e Ricerca prima in larghezza per risolvere un labirinto. Abbiamo anche toccato il modo in cui BFS fornisce il percorso più breve dall'ingresso all'uscita.

Per ulteriori letture, cerca altri metodi per risolvere un labirinto, come A * e l'algoritmo Dijkstra.

Come sempre, il codice completo può essere trovato su GitHub.