Matteo Vignoli

Sviluppatore Web Full-Stack autodidatta, curioso per natura,
attualmente impiegato a Milano presso ContactLab per conto di Anoki S.r.L.

Algoritmo per i labirinti: Depth First Search in PHP

  Tempo di lettura:

Sono sempre stato affascinato dai labirinti, anche se la consapevolezza di questa attrazione risale al mio periodo "umanistico" dell'università, a quando lessi per la prima volta i racconti di J.L. Borges - "Il giardino dei sentieri che si biforcano", "La biblioteca di Babele" e tutti i vari riferimenti che si trovano, più o meno velati, nella altre opere.

Recentemente mi è capitato di nuovo sott'occhio questo argomento, a partire da un libro molto interessante di Jamis Buck, "Mazes for Programmers: Code Your Own Twisty Little Passages" (1), che analizza alcuni algoritmi di creazione dei labirinti in maniera molto chiara (anche per chi non ha un background matematico come me) e facile da seguire, usando Ruby come linguaggio. Tra una ricerca su Google e l'altra ho poi trovato diverse risorse interessanti, tra cui una sezione su RosettaCode in cui viene presentato, in diversi linguaggi, un sistema di generazione labirinti che utilizza la strategia di attraversamento "Depth First Search".

Mancando, stranamente, la versione in PHP mi sono dedicato a colmare questa lacuna, ed è stato davvero un piacevole esercizio: non avendo mai formalmente studiato algoritmi e strutture dati ho dovuto mettere la testa su un argomento molto importante che ho avuto modo di affrontare molto poco nella quotidianità lavorativa.

<?php
class Maze 
{
    protected $width;
    protected $heigth;
    protected $grid;
    protected $path;
    protected $horWalls;
    protected $vertWalls;
    protected $dirs;
    protected $isDebug;
 
    public function __construct($x, $y, $debug = false)
    {
        $this->width = $x;
        $this->height = $y;
        $this->path = [];        
        $this->dirs = [ [0, -1], [0, 1], [-1, 0], [1, 0]]; // array of coordinates of N,S,W,E
        $this->horWalls = []; // list of horizontal walls (---+)        
        $this->vertWalls = [];// list of vertical walls (|)        
        $this->isDebug = $debug; // debug flag
 
        // generate the maze:
        $this->generate();
    }
    ```

L'impostazione iniziale è abbastanza semplice:

  • $x ed $y sono le dimensioni che avrà il labirinto (sarebbe utile integrare dei controlli sulla validità delle dimensioni, ad esempio i lati devono essere > 1 ecc.)
  • $this->dirs contiene le coordinate (a tuple) dei punti a Nord, Sud, Ovest ed Est di ogni singola cella: ad esempio, la cella alla posizione x:1, y:1 (1,1) avrà a Nord la cella in posizione (x:1+0, y: 1-1), a Ovest (1-1, 1+0), ecc.
  • $this->horWalls e $this->vertWalls sono array che contengono il riferimento a quali muri inserire nella rappresentazione ASCII - questa è stata la parte che più mi ha messo in difficoltà, capire come "disegnare" nella console il labirinto.
protected function generate()
{        
    $this->initMaze(); // init the stack and an unvisited grid
    // start from a random cell and then proceed recursively
    $this->walk(mt_rand(0, $this->width-1), mt_rand(0, $this->height-1));
}

/**
* Initialzie an empty grid of $width * $height dimensions
*/
private function initMaze()
{
    for ($i=0;$i<$this->width;$i++) {
        for ($j = 0;$j<$this->height;$j++) {
            $this->grid[$i][$j] = false;
        }
    }
}

Qui inizializzo il labirinto con una matrice di celle, ciascuna delle quali ha registrato il suo stato "visitato" - pertanto sono tutte inizializzate con un false. Un'alternativa a questo approccio è andare di pieno OO e creare una classe Cella() che contiene, come proprietà interne, i riferimenti a tutti le celle collegate, a quelle vicine, allo status, ecc. Sarebbe anche l'approccio migliore ed è quello che usa Jamis Buck nel suo libro, ma viste le soluzioni postate per gli altri linguaggi ho deciso di rimanere più light e utilizzare un semplice array multidimensionale.


/**
* @param int $x
* @param int $y
* @return array
*/
private function getNeighbors($x, $y) 
{       
    $neighbors = [];
    foreach ($this->dirs as $dir) {
        $nextX = $dir[0] + $x;
        $nextY = $dir[1] + $y;
        if (($nextX >= 0 && $nextX < $this->width && $nextY >= 0 && $nextY < $this->height) && !$this->grid[$nextX][$nextY]) {
            $neighbors[] = [$nextX, $nextY];
        }
    }
    return $neighbors;
}

private function walk($x, $y)
{
    $this->log('Entering cell %d,%d', $x, $y);
    // mark current cell as visited     
    $this->grid[$x][$y] = true; 
    // add cell to path
    $this->path[] = [$x, $y];
    // get list of all neighbors
    $neighbors = $this->getNeighbors($x, $y);       
    $this->log("Valid neighbors: %s", json_encode($neighbors));

    if(empty($neighbors)) {
        // Dead end, we need now to backtrack, if there's still any cell left to be visited
        $this->log("Start backtracking along path: %s", json_encode($this->path));
        array_pop($this->path);
        if (!empty($this->path)) {
            $next = array_pop($this->path);
            return $this->walk($next[0], $next[1]);
        }
    } else {            
        // randomize neighbors, as per request
        shuffle($neighbors);

        foreach ($neighbors as $n) {
            $nextX = $n[0];
            $nextY = $n[1];
            if ($nextX == $x) {
                $wallY = max($nextY, $y);
                $this->log("New cell is on the same column (%d,%d), removing %d, (%d-1) horizontal wall", $nextX, $nextY, $x, $wallY);
                $this->horWalls[$x][min($nextY, $y)] = "   +";
            }
            if ($nextY == $y) {
                $wallX = max($nextX, $x);
                $this->log("New cell is on the same row (%d,%d), removing %d,%d vertical wall", $nextX, $nextY, $wallX, $y);
                $this->vertWalls[$wallX][$y] = "    ";              
            }
            return $this->walk($nextX, $nextY);
        }
    }
}

Questo metodo è il cuore dell'algoritmo, ed è un metodo che viene chiamato ricorsivamente per ogni cella. Come da traccia iniziale si parte da una cella casuale all'interno di tutto il labirinito e si inizia a percorrerlo.

  • Per prima cosa, si segna la cella come visitata $this->grid[$x][$y] = true;
  • La stessa cella viene quindi aggiunta allo stack che contiene il percorso fatto, $this->path[] = [$x, $y];
  • Creo un elenco di tutte le celle circostanti valide $this->getNeighbors($x, $y);. una cella è considerata "valida" se non è ancora stata visitata e se si trova all'interno dei "bordi" del labirinto (ovviamente).
  • Se la cella ha delle celle vicine, allora ne prendo una a caso (semplicemente mescolando la lista di vicini) shuffle($neighbors);, vedo se inserire un muro orizzontale (|) o verticale (---+) a seconda di dove si trova la cella e chiamo, ricorsivamente, la stessa funzione visitando la cella nuova.
  • Se la cella invece non ha più vicini disponibili (Dead end) ci troviamo al termine del "ramo" oppure alla risoluzione completa del labirinto. In quest'ultimo caso l'esecuzione finisce direttamente, altrimenti si percorre indietro lo stack (eliminando dalla pila la cella corrente e quella che visiteremo ora) fino ad arrivare a completare il labirinto.

La parte per me più complessa è stata quella della stampa del labirinto, come già ho anticipato: se avessi dovuto rappresentare ogni singola cella forse sarebbe stato più facile, ma stamparlo nel terminale, in ASCII, uniformandomi il più possibile alle altre soluzioni non è stato semplice. Ad ogni modo, questo è il metodo:

public function printOut()
{
    $this->log("Horizontal walls: %s", json_encode($this->horWalls));
    $this->log("Vertical walls: %s", json_encode($this->vertWalls));        

    $northDoor = mt_rand(0,$this->width-1);
    $eastDoor = mt_rand(0, $this->height-1);

    $str = '+';
    for ($i=0;$i<$this->width;$i++) {
        $str .= ($northDoor == $i) ? '   +' : '---+';
    }
    $str .= PHP_EOL;
    for ($i=0; $i<$this->height; $i++) {

        for ($j=0; $j<$this->width; $j++) {
            $str .= (!empty($this->vertWalls[$j][$i]) ? $this->vertWalls[$j][$i] : '|   ');
        }
        $str .= ($i == $eastDoor ? '  ' : '|').PHP_EOL.'+';
        for ($j=0; $j<$this->width; $j++) {
            $str .= (!empty($this->horWalls[$j][$i]) ? $this->horWalls[$j][$i] : '---+');
        }
        $str .= PHP_EOL;
    }
    echo $str;
}

In poche parole:

  • Creo un ingresso ed un'uscita - anche se non era nelle specifiche e sono poche le soluzioni su RosettaCode che hanno preso in considerazione questo aspetto è ancora più bello così! Le aperture sono random ma per comodità (e per risparmiarmi mille controlli) sono sempre nella facciata Nord ed in quella Est.
  • Creo per prima cosa il muro a Nord, con la porta di ingresso/uscita.
  • Per ogni fila, ciclo su tutte le celle e vedo prima se stampare un muro verticale o no e poi ciclo nuovamente per vedere se stampare un muro orizzontale o meno.

A questo punto, instanziare la classe e chiamare questo metodo dovrebbe mostrare qualcosa tipo questo (essendo casuale la figura finale differirà):

$maze = new Maze(10,12);
$maze->printOut();
$ php maze.php
$
+---+---+---+---+---+---+   +---+---+---+
|               |                       |
+   +---+---+   +   +   +   +---+---+---+
|           |   |   |   |   |           |
+   +---+   +   +---+   +---+   +---+   +
|       |   |           |       |   |   |
+---+   +   +---+---+---+   +---+   +   +
|       |                   |       |   |
+   +---+---+---+---+---+---+   +   +   +
|   |                   |       |   |   |
+   +   +---+   +---+   +   +   +---+   +
|   |   |       |           |   |       |
+   +---+   +---+---+---+---+---+   +   +
|       |       |           |       |   |
+---+   +---+   +---+---+   +   +---+---+
|   |       |           |   |           |
+   +---+   +   +   +---+   +---+   +   +
|           |   |       |       |   |     
+   +---+---+---+---+   +---+   +---+   +
|                   |       |       |   |
+---+---+---+---+   +---+   +---+   +   +
|               |       |       |   |   |
+   +---+---+   +---+   +---+   +   +   +
|           |                   |       |
+---+---+---+---+---+---+---+---+---+---+

Questo è l'approccio che ho seguito, e sicuramente avrà mille aspetti che si possono fare in maniera migliore, più efficiente o diretta, ma sono soddisfatto del risultato ottenuto e penso che procederò con l'implementazione di altri algoritmi per la creazione di labirinti. Dopotutto, una vecchia passione che si riaccende ❤️

Note:
(1) Libro: Mazes for Programmers: Code your own Twisty Little Passages
Codice completo: https://github.com/DamienPirsy/mazes
Soluzione su RosettaCode: http://rosettacode.org/wiki/Maze_generation#PHP

Ricevere una notifica Telegram quando il servizio mysql è down

Telegram, con i suoi bot e canali, è uno strumento estremamente versatile che si presta molto bene ad essere utilizzato come endpoint per ricevere warning e...

Algoritmo per la generazione di labirinti #1: il Binary Tree

Il Binary Tree  è l'algoritmo più semplice per la generazione di un labirinto ed è anche quello che necessita meno risorse: può infatti creare un labirinto...

MatteoVignoli.it   Non perderti nulla da MatteoVignoli.it, ricevi aggiornamenti via mail.