Continuiamo a parlare di labirinti e pathfinding con Flutter. In questo secondo articolo introdurremo alcuni algoritmi di risoluzione, prima con qualche contributo teorico e poi con l'implementazione in Dart. Per chi si fosse perso la prima parte, la trova qui.
Un po' di teoria
Per trovare la soluzione dei labirinti generati possiamo far ricorso alla teoria dei grafi, immaginando come ogni casella del labirinto rappresenti un nodo di un grafo e i muri (o meglio, la loro mancanza) rappresentino i collegamenti tra i nodi. Abbiamo quindi un grafo di cui:
- conosciamo il nodo iniziale (cella di ingresso) e il nodo finale (cella di uscita)
- possiamo determinare il costo per passare da un nodo ad uno adiacente
- possiamo stimare in modo euristico il costo del percorso tra un nodo qualsiasi e il nodo finale
I fini della nostra trattazione il concetto di costo qui introdotto può essere coniugato in vari modi (tempo di percorrenza, energia necessaria, numero di passi, ...) e dipende solo da quale aspetto si voglia enfatizzare nella ricerca del percorso minimo (minimo rispetto appunto al tipo di costo considerato).
La componente euristica
L’algoritmo euristico ha il compito di stimare la distanza tra qualsiasi nodo e il nodo finale (soluzione) e la sua implementazione influenza i risultati conseguiti dall'algoritmo A*, in particolare, determinandone il tempo complessivo di esecuzione.
Un algoritmo euristico molto efficace consente ad A* di trovare velocemente la soluzione. Nel caso pessimo, una funzione euristica costante (al limite pari a zero), A* diviene un algoritmo di ricerca molto simile a Dijkstra.
L’euristica determina anche la qualità della soluzione finale. Con un'euristica ammissibile A* è in grado di identificare la soluzione ottima (e.g. percorso con il minor costo possibile). Una funzione euristica è ammissibile quando l’errore di stima non è mai in eccesso: ad esempio, la distanza in linea d’aria tra due punti su una mappa è sempre una funzione eucaristica ammissibile.Una funzione euristica monotòna semplifica ulteriormente la struttura di A* in quanto la lista dei nodi già visitati diviene superflua. In questi casi, la sola coda a priorità è sufficiente. Una funzione euristica monotona è sempre ammissibile.
Struttura dell’algoritmo
L'algoritmo A* rientra nella categoria degli algoritmi di ricerca best-first. Esso infatti esamina, passo dopo passo, i nodi che hanno il punteggio migliore, ma non è greedy in quanto il punteggio non è determinato esclusivamente dalla componente euristica. A* usa le seguenti strutture dati per mantenere traccia dello stato d’esecuzione:
- una lista di nodi già visitati;
- una coda a priorità contenente i nodi da visitare.
Nel corso dell’esecuzione, ad ogni nodo vengono associati più valori: g, h e f, dove g rappresenta il costo effettivo del percorso che separa il nodo A (partenza) e il nodo n (attuale), nel nostro caso valutato come numero di caselle che occorre attraversare . Il valore h rappresenta una stima del costo del percorso tra il nodo finale B (soluzione) e il nodo n (attuale): questo valore può essere calcolato con la funzione euristica enunciata in precedenza.
La struttura dell’algoritmo A* è molto semplice. Ad alto livello, può essere schematizzato in 8 passi:
- Inserimento nella coda del nodo di partenza con priorità pari al f;
- Se la coda è vuota, l’algoritmo termina: soluzione non trovata;
- Estrazione del miglior nodo da visitare (priorità con valore più basso);
- Se il nodo estratto ha h (distanza) nullo, l’algoritmo termina: soluzione trovata;
- Colleziona i nodi figli (quelli adiacenti al nodo corrente);
- Eliminazione dei nodi figli già visitati e con valore f maggiore;
- Inserimento dei nodi rimanenti nella coda con priorità pari al f;
- Riprendere da punto 2.
L'implementazione
Riprendiamo il progetto iniziato nell'articolo precedente e aggiungiamo quanto serve per implementare l'algoritmo A*.
Nel file maze.dart, aggiungiamo due proprietà per memorizzare la casella iniziale e quella finale desiderate sul nostro labirinto:
e quindi valorizziamo queste proprietà nel file main.dart, indicando come cella di partenza la prima (indice 0) e come cella di arrivo l'ultima:
Modifichiamo il metodo _drawCell() nel file maze.dart per evidenziare le due caselle nel labirinto:
Nel file cell.dart, aggiungiamo le tre proprietà numeriche per memorizzare i valori f, g e h, un puntatore alla casella precedente e un flag per indicare se la casella fa parte del percorso trovato, che ci torneranno comodi per ricostruire e disegnare il percorso:
Sempre file maze.dart, iniziamo a costruire un nuovo metodo che invocheremo per trovare il percorso minimo tra la casella iniziale e finale. Questo metodo ci restituirà la lista degli indici delle caselle che costituisco il percorso minimo cercato:
Come primo step azzeriamo lo stato di ogni cella:
quindi inizializziamo una coda di elaborazione, inserendo subito l'indice della casella iniziale
e ora definiamo il ciclo che elabora la coda fino a quando ci sono celle da valutare oppure è stata raggiunta la casella finale, oppure non ci sono soluzioni per il labirinto
impostiamo come visitata la casella corrente e rimuoviamola dalla coda
Ora occorre trovare tutte le caselle adiacenti. A differenza di quanto abbiamo fatto nella fase di costruzione del labirinto, occorre tener conto dei muri presenti tra una cella e l'altra e quindi due celle confinanti, possono considerarsi adiacenti solo se non c'è un muro che le separa. Per fare questo, occorre modifica la funzione _getAdjacents() che avevamo già definito, introducendo il controllo sulla presenza dei muri:
Con questa modifica, possiamo completare il metodo _findMinPath() con queste righe:
dove il metodo _getDistance() rappresenta la nostra funzione euristica e, applicando il teorema di Pitagora, può essere definita in questa modo:
Non ci resta che scrivere il codice da eseguire quando viene raggiunta la casella finale, ricostruendo il percorso usando la usando la proprietà .previous e attivando il flag .isPath:
Quindi, dopo aver costruito il labirinto, basta invocare la funzione _findMinPath() nel metodo createMaze() per avere l'elenco delle caselle che rappresentano il percorso minimo tra le due caselle individuate:
(in realtà per gli scopi di questo articolo, non useremo questa lista, ma potrebbe essere comunque interessante memorizzarla per altri usi).
Tracciamo il percorso trovato
Abbiamo tutte le informazioni che occorrono per tracciare il percorso sul labirinto. Costruiamo un metodo specifico:
e modifichiamo il metodo paint() nel file maze_painter.dart per invocare il nuovo metodo:
per ottenere la soluzione cercata:
Conclusioni
In questa seconda parte abbiamo introdotto l'algoritmo A*, il concetto di funzione euristica per valutare la distanza e visto una sua implementazione in Dart.
Il codice potrebbe essere chiaramente ottimizzato, magari introducendo una struttura più efficiente rispetto al semplice array di celle utilizzato, ma questo potrebbe essere l'oggetto di un prossimo post.
Come per gli articoli precedenti potete trovare il codice completo tra le mie repo GitHub: https://github.com/luigimicco/flutter_maze.
Il codice potrebbe essere chiaramente ottimizzato, magari introducendo una struttura più efficiente rispetto al semplice array di celle utilizzato, ma questo potrebbe essere l'oggetto di un prossimo post.
Come per gli articoli precedenti potete trovare il codice completo tra le mie repo GitHub: https://github.com/luigimicco/flutter_maze.
Commenti
Posta un commento