Flutter: labirinti e pathfinding - Parte 1

In questo e nell'articolo successivo vedremo come utilizzare Flutter per creare dei labirinti 2D e poi come risolverli implementando alcuni algoritmi di pathfinding. Nella prima tappa, ci immergeremo nella programmazione Dart, costruendo i fondamenti: labirinti casuali, imparando a generare labirinti procedurali, popolandoli di percorsi e muri.

Se siete interessati ad approfondire la teoria dei labirinti e degli algoritmi di esplorazione, vi consiglio di seguire il canale Youtube del mio amico Gianluca Lomarco  

Il progetto in Flutter

Partiamo da un nuovo progetto e sostituiamo il codice standard nel file main.dart con questo:


import 'package:flutter/material.dart';

void main() {
  runApp(const MyApp());
}

class MyApp extends StatelessWidget {
  const MyApp({Key? key}) : super(key: key);

  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      theme: ThemeData(
        colorScheme: ColorScheme.fromSeed(seedColor: Colors.deepPurple),
        useMaterial3: true,
      ),
      home: Scaffold(
        appBar: AppBar(
          title: const Text('Flutter Maze demo'),
        ),
        backgroundColor: Colors.black,
        body: Center(),
      ),
    );
  }
}

Gli elementi del labirinto

Nella cartella lib, creiamo una sottocartella logic e dentro questa un file maze.dart con una classe che ci permetterà di descrivere il labirinto che vogliamo creare, come una lista di celle :


import 'dart:math';
import 'dart:ui';

import 'package:flutter/material.dart';

import 'cell.dart';
import 'coords.dart';

class Maze {
  // dimensione della griglia (ipotesi che sia quadrata)
  final double size;
  // dimensione singola cella
  final double cellWidth;

  Maze({
    required this.size,
    required this.cellWidth,
  }) {
    // griglia iniziale
    createGrid();
  }

  // array delle celle
  final List<Cell> grid = <Cell>[];

  int get rows => (size / cellWidth).floor();
  int get columns => (size / cellWidth).floor();

  void createGrid() {
    grid.clear();

    for (var i = 0; i < rows * columns; i++) {
      final y = (i / columns).floor();
      final x = (i - y * columns).floor();

      grid.add(Cell(coords: Coords(x, y)));
    }
  }

}


Il labirinto sarà quadrato, per semplicità, e sarà costituito da celle uguali in dimensioni e disposte secondo una griglia righe/colonne. Al momento l'unico metodo implementato _createGrid() si occupa di generare le singole celle con le coordinate lungo la griglia.

Creiamo anche un file cell.dart in modo che ogni cella sia caratterizzata dalle sue coordinate (posizione x,y nella griglia) e da un elenco di bordi (sui quattro lati: top, left, bottom, right):


import 'coords.dart';

// posizione dei bordi
enum Side { t, r, b, l } // top, bottom, left, right

class Cell {
  Cell({
    required this.coords,
  });

  final Coords coords;
  bool visited = false;

  // ogni cella nasce con i bordi su tutti i lati
  final List<Side> borders = <Side>[
    Side.t,
    Side.r,
    Side.b,
    Side.l,
  ];
}


e un file coords.dart con la classe per la definizione delle coordinate:


class Coords {
  const Coords(this.x, this.y);

  final int x;
  final int y;
}

Il custom painter

Per visualizzare il labirinto nel body dell'applicazione occorre definire un painter customizzato che si occupi di disegnare il canvas con le singole celle.

Nella cartella lib, creiamo una sottocartella painter e dentro questa un file maze_painter.dart con questa classe:


import 'package:flutter/material.dart';

import '../logic/maze.dart';

class MazePainter extends CustomPainter {
  const MazePainter({required this.maze});

  final Maze maze;

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

  @override
  bool shouldRepaint(covariant CustomPainter oldDelegate) => true;
}


che richiama il metodo .draw() (che definiamo di seguito) sull'istanza della classe Maze. Il metodo da aggiungere alla classe è questo:



  void draw(Canvas canvas) {
    for (var i = 0; i < grid.length; i++) {
      final cell = grid[i];
      _drawCell(canvas, cell);
    }
  }
  void _drawCell(Canvas canvas, Cell cell) {
    final backgroundPaint = Paint()
      ..color = Colors.black
      ..style = PaintingStyle.fill;

    final x = cell.coords.x * cellWidth;
    final y = cell.coords.y * cellWidth;

    canvas.drawRect(
      Rect.fromLTWH(x, y, cellWidth + 0.5, cellWidth + 0.5),
      backgroundPaint,
    );
    _drawBorders(canvas, cell.borders, x, y);
  }
  void _drawBorders(Canvas canvas, List<Side> borders, double x, double y) {
    final borderPaint = Paint()
      ..color = Colors.red
      ..strokeWidth = 2
      ..strokeCap = StrokeCap.round;

    // border top
    if (borders.contains(Side.t)) {
      canvas.drawLine(
        Offset(x, y),
        Offset(x + cellWidth, y),
        borderPaint,
      );
    }

    // border right
    if (borders.contains(Side.r)) {
      canvas.drawLine(
        Offset(x + cellWidth, y),
        Offset(x + cellWidth, y + cellWidth),
        borderPaint,
      );
    }

    // border bottom
    if (borders.contains(Side.b)) {
      canvas.drawLine(
        Offset(x + cellWidth, y + cellWidth),
        Offset(x, y + cellWidth),
        borderPaint,
      );
    }

    // border left
    if (borders.contains(Side.l)) {
      canvas.drawLine(
        Offset(x, y + cellWidth),
        Offset(x, y),
        borderPaint,
      );
    }
  }


Il metodo, disegna una alla volta le singole celle, come quadrati di colore nero e per ognuna disegna anche i bordi, come linee di colore rosso, sui quattro lati (ogni cella, al momento presenta i bordi su tutti i lati).


  void draw(Canvas canvas) {
    for (var i = 0; i < grid.length; i++) {
      final cell = grid[i];
      _drawCell(canvas, cell);
    }
  }
  void _drawCell(Canvas canvas, Cell cell) {
    final backgroundPaint = Paint()
      ..color = Colors.black
      ..style = PaintingStyle.fill;

    final x = cell.coords.x * cellWidth;
    final y = cell.coords.y * cellWidth;

    canvas.drawRect(
      Rect.fromLTWH(x, y, cellWidth + 0.5, cellWidth + 0.5),
      backgroundPaint,
    );
    _drawBorders(canvas, cell.borders, x, y);
  }
  void _drawBorders(Canvas canvas, List<Side> borders, double x, double y) {
    final borderPaint = Paint()
      ..color = Colors.red
      ..strokeWidth = 2
      ..strokeCap = StrokeCap.round;

    // border top
    if (borders.contains(Side.t)) {
      canvas.drawLine(
        Offset(x, y),
        Offset(x + cellWidth, y),
        borderPaint,
      );
    }

    // border right
    if (borders.contains(Side.r)) {
      canvas.drawLine(
        Offset(x + cellWidth, y),
        Offset(x + cellWidth, y + cellWidth),
        borderPaint,
      );
    }

    // border bottom
    if (borders.contains(Side.b)) {
      canvas.drawLine(
        Offset(x + cellWidth, y + cellWidth),
        Offset(x, y + cellWidth),
        borderPaint,
      );
    }

    // border left
    if (borders.contains(Side.l)) {
      canvas.drawLine(
        Offset(x, y + cellWidth),
        Offset(x, y),
        borderPaint,
      );
    }
  }


Il metodo, disegna una alla volta le singole celle, come quadrati di colore nero e per ognuna disegna anche i bordi, come linee di colore rosso, sui quattro lati (ogni cella, al momento presenta i bordi su tutti i lati).

Siamo pronti per visualizzare la nostra griglia.

L'istanza

Modifichiamo il codice main.dart, aggiungendo l'istanza della classe e il nostro painter customizzato e creando due costanti per assegnare facilmente le dimensioni alla griglia del labirinto:


const double size = 400;
const double cellWidth = 30;

class MyApp extends StatelessWidget {
  MyApp({super.key});

  final Maze maze = Maze(
    size: size,
    cellWidth: cellWidth,
  );

  // This widget is the root of your application.
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      theme: ThemeData(
        colorScheme: ColorScheme.fromSeed(seedColor: Colors.deepPurple),
        useMaterial3: true,
      ),
      home: Scaffold(
        appBar: AppBar(
          title: const Text('Flutter Maze demo'),
        ),
        backgroundColor: Colors.black,
        body: Center(
          child: CustomPaint(
            size: const Size.square(size),
            painter: MazePainter(maze: maze),
          ),
        ),
      ),
    );
  }
}


che produce come risultato, la visualizzazione della griglia di base del nostro labirinto:

Il labirinto

Come creiamo un labirinto partendo dalla semplice grigia ?

Un metodo semplice è quello di esplorare la griglia a partire da una cella (per esempio quella in alto a sinistra, con coordinate [0,0]), applicando questi semplice passi:
  • individuare tutte le celle adiacenti (cioè quelle che hanno un bordo in comune) non ancora visitate
  • decidere in modo casuale quale bordo eliminare
  • aggiungere la cella corrente ad un pila 
  • rendere corrente la nuova cella
  • ripetere l'operazione a partire dalle nuova cella
avendo cura di ricordarsi in quali celle si è già passati (per evitare di passarci due volte). Durante le fasi indicate, se non ci sono più celle adiacenti non visitate, si riparte dall'ultima cella impilata e se non ci sono celle impilate, il labirinto è completo, 

Per realizzare quanto indicato, alla classe Cell, aggiungiamo una proprietà:


  bool visited = false;

 
Nella classe Maze, definiamo un metodo per trovare l'elenco delle celle adiacente non ancora visitate che tenga anche conto dei limiti della griglia (quindi ad esempio, le celle della prima riga non hanno celle adiacenti sul bordo superiore, e così via per quelle dell'ultima riga, della prima e dell'ultima colonna):


  int adjacentCell(int index, Side side) {
    int result = -1;

    if (side == Side.t) {
      result = index - columns;
    } else if (side == Side.b) {
      result = index + columns;
    } else if (side == Side.l) {
      result = index - 1;
    } else if (side == Side.r) {
      result = index + 1;
    }

    return result;
  }

  // elenco delle celle adiacenti non ancora visitate
  List<int> _getAdjacents(int currentCell) {
    final adjacents = <int>[];
    final List<Side> borders = <Side>[];

    final y = grid[currentCell].coords.y;
    final x = grid[currentCell].coords.x;

    if (y > 0) {
      borders.add(Side.t); // top
    }
    if (y < (rows - 1)) {
      borders.add(Side.b); // bottom
    }
    if (x > 0) {
      borders.add(Side.l); // left
    }
    if (x < (columns - 1)) {
      borders.add(Side.r); // right
    }

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

      if (!grid[adjacent].visited) {
        adjacents.add(adjacent);
      }
    }

    return adjacents;
  }


Ora, sempre nella classe Maze, è possibile definire il metodo che sviluppa i passi indicati in precedenza:


  void createMaze() {
    final List<int> stack = <int>[];
    bool mazeComplete = false;

    int currentCell = 0; // cella alla posizione (0,0)
    grid[currentCell].visited = true;

    while (!mazeComplete) {
      final adjacents = _getAdjacents(currentCell);

      if (adjacents.isNotEmpty) {
        final nextCell = adjacents[Random().nextInt(adjacents.length)];

        stack.add(currentCell);
        _openBorders(currentCell, nextCell);

        currentCell = nextCell;
        grid[currentCell].visited = true;
      } else if (stack.isNotEmpty) {
        currentCell = stack.removeLast();
      } else {
        mazeComplete = true;
      }
    }
  }

  void _openBorders(int currentCell, int nextCell) {
    final x = grid[currentCell].coords.x - grid[nextCell].coords.x;
    final y = grid[currentCell].coords.y - grid[nextCell].coords.y;

    if (x == 1) {
      grid[currentCell].borders.remove(Side.l);
      grid[nextCell].borders.remove(Side.r);
    } else if (x == -1) {
      grid[currentCell].borders.remove(Side.r);
      grid[nextCell].borders.remove(Side.l);
    }

    if (y == 1) {
      grid[currentCell].borders.remove(Side.t);
      grid[nextCell].borders.remove(Side.b);
    } else if (y == -1) {
      grid[currentCell].borders.remove(Side.b);
      grid[nextCell].borders.remove(Side.t);
    }
  }

  
Il metodo _openBorders, dati gli indici di due celle adiacenti, rimuove il bordo comune.

Non ci resta che aggiungere il metodo createMaze() al costruttore della classe Maze,


  Maze({
    required this.size,
    required this.cellWidth,
  }) {
    // griglia iniziale
    createGrid();
    createMaze();
  }


per ottenere il risultato cercato:



Conclusioni

Nella seconda parte implementeremo un algoritmo che ci permetterà di risolvere il labirinto, trovando il percorso minimo tra una cella di partenza e una di arrivo.

Come per gli articoli precedenti potete trovare il codice (di questa prima parte) tra le mie repo GitHub: https://github.com/luigimicco/flutter_maze.

Commenti