Flutter: labirinti e pathfinding - Parte 2

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 
che rappresenta quindi una classica applicazione di ricerca del percorso minimo a cui può essere applicato l'algoritmo A* (a-star).

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:

  1. Inserimento nella coda del nodo di partenza con priorità pari al f;
  2. Se la coda è vuota, l’algoritmo termina: soluzione non trovata;
  3. Estrazione del miglior nodo da visitare (priorità con valore più basso);
  4. Se il nodo estratto ha h (distanza) nullo, l’algoritmo termina: soluzione trovata;
  5. Colleziona i nodi figli (quelli adiacenti al nodo corrente);
  6. Eliminazione dei nodi figli già visitati e con valore f maggiore;
  7. Inserimento dei nodi rimanenti nella coda con priorità pari al f;
  8. 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:


  // indice della casella iniziale
  final int start;
  // indice della casella finale
  final int end;

  Maze({
    required this.size,
    required this.cellWidth,
    required this.start,
    required this.end,
  }) {


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: 


  final Maze maze = Maze(
    size: size,
    cellWidth: cellWidth,
    start: 0,
    end: pow((size / cellWidth).floor(), 2).floor() - 1,
  );

Modifichiamo il metodo _drawCell() nel file maze.dart per evidenziare le due caselle nel labirinto:


    // in corrispondenza delle caselle di inizio e fine,
    // inserisce un cerchietto bianco
    if (cell == start || cell == end) {
      canvas.drawCircle(
        Offset(x + cellWidth / 2, y + cellWidth / 2),
        cellWidth / 4,
        Paint()..color = Colors.white,
      );
    }



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:


  double f = 0;
  double g = 0;
  double h = 0;

  int? previous;
  bool isPath = false;

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: 


  List<int> _findMinPath() {
    final result = <int>[];

Come primo step azzeriamo lo stato di ogni cella:


    for (final cell in grid) {
      cell
        ..f = 0
        ..g = 0
        ..h = 0
        ..visited = false
        ..isPath = false
        ..previous = null;
    }

quindi inizializziamo una coda di elaborazione, inserendo subito l'indice della casella iniziale


    final queue = <int>[start];

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


    while (queue.isNotEmpty) {
      // prende in esame la prima cella della coda
      var current = queue.first;

      // se esistem pate dalla cella
      // con il valore f minore
      for (final cell in queue) {
        if (grid[cell].f < grid[current].f) {
          current = cell;
        }
      }

      if (current == end) {
        // è stata raggiunta la casella finale
        // ...
      }

impostiamo come visitata la casella corrente e rimuoviamola dalla coda


      grid[current].visited = true;
      queue.remove(current);

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:


  List<int> _getAdjacents(int currentCell, {required bool checkBorders}) {
...
...

    for (final side in borders) {
      int adjacent = adjacentCell(currentCell, side);

      // se valuta i muri, verifica che non ce ne sia uno
      if (checkBorders && grid[currentCell].borders.contains(side)) {
        continue;
      }

...

 Con questa modifica, possiamo completare il metodo _findMinPath() con queste righe:


      final adjacents = _getAdjacents(current, checkBorders: true);

      for (final cell in adjacents) {
        grid[cell].previous = current;
        grid[cell].g++;
        grid[cell]
          ..h = _getDistance(cell, end)
          ..f = grid[cell].g + grid[cell].h;

        if (!queue.contains(cell) && !grid[cell].visited) {
          queue.add(cell);
        }
      }

dove il metodo _getDistance() rappresenta la nostra funzione euristica e, applicando il teorema di Pitagora, può essere definita in questa modo:


  double _getDistance(int a, int b) {
    Coords cA = grid[a].coords;
    Coords cB = grid[b].coords;

    return sqrt(pow(cA.x - cB.x, 2) + pow(cA.y - cB.y, 2));
  }

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:


      if (current == end) {
        // è stata raggiunta la casella finale
        grid[end]
          ..visited = true
          ..isPath = true;        
        int node = end;
        List<int> path = <int>[node];

        // utilizziamo la proprità previous per ricostruire
        // il percorso a ritroso
        while (grid[node].previous != null) {
          node = grid[node].previous!;
          grid[node].isPath = true;
          path.add(node);
        }

        // il percorso è a ritroso, quindi invertiamo la lista
        result = path.reversed.toList();
        return result;
      }

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:


  void createMaze() {
...
    while (!mazeComplete) {
        ...
    }

    final List<int> path = _findMinPath();
  }

(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:


  void drawPath(Canvas canvas) {
    // prendiamo solo le celle che fanno
    // parte del percroso
    final List<Cell> minPath = grid.where((Cell cell) => cell.isPath).toList();

    final paint = Paint()
      ..color = Colors.white
      ..strokeCap = StrokeCap.round
      ..strokeWidth = cellWidth / 3;

    // per ogni cella, tracciamo una linea dal suo centro
    // al centro della cella che la precede nel percorso
    for (final cell in minPath) {
      double sX = cell.coords.x * cellWidth + cellWidth / 2;
      double sY = cell.coords.y * cellWidth + cellWidth / 2;

      if (cell.previous != null) {
        double eX = grid[cell.previous!].coords.x * cellWidth + cellWidth / 2;
        double eY = grid[cell.previous!].coords.y * cellWidth + cellWidth / 2;

        canvas.drawLine(Offset(sX, sY), Offset(eX, eY), paint);
      }
    }
  }

e modifichiamo il metodo paint() nel file maze_painter.dart per  invocare il nuovo metodo:

  @override
  void paint(Canvas canvas, Size size) {
    maze
      ..draw(canvas)
      ..drawPath(canvas);
  }

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


Commenti