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 la generazione di labirinti #1: il Binary Tree

  Tempo di lettura:

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 perfetto (ossia che ha un solo percorso possibile tra due celle) senza necessitare di alcun registro in cui tenere traccia degli spostamenti, ma semplicemente lavorando una cella alla volta.

Il concetto è davvero semplice: si parte da una cella qualsiasi (non importa quale, per comodità io sono partito da quella con coordinate (0,0) e sono andato in ordine) e si decide, in maniera random, quale fra due direzioni prendere. E' un procedimento così immediato che si può fare anche "manualmente": si disegna una griglia e si lancia una monetina per decidere dove spostarsi - ad esempio se esce testa si va a Sud mentre se esce croce si va ad Est, quindi si rimuove il "muro" che separa la cella corrente da quella verso cui dovremmo andare.

Schematicamente: 1) Costruiamo una matrice, ad esempio 4x4:
       
       
       
       
2) Prendiamo una cella qualsiasi, ad esempio (x:0, y:0)
       
       
       
       
3. Scegliamo in maniera casuale verso quale direzione muoverci tra Sud o Est, ad esempio Est, e rimuoviamo il muro che separa la cella corrente con quella di destinazione:
       
       
       
       
4) Ripetiamo i punti 2-4 per tutte le celle non visitate

Ripetendo questo procedimento per ogni cella (anche non in maniera ordinata, come ho già detto prima, quello che importa all'algoritmo è che vengano visitate tutte) al termine si avrà un labirinto completo che però presenterà una evidente tendenza (quella che viene chiamata bias): potendoci muovere solo in due direzioni, infatti, ci troveremo in situazioni in cui il percorso prende naturalmente la stessa piega. Ad esempio, quando arriveremo alle ultime celle a destra non potremmo far altro che andare a Sud, e lo stesso vale quando siamo all'ultima riga della griglia, in cui non potremmo che andare ad Est - verrà così sempre generato un labirinto che ha due lunghi corridoi nell'ultima colonna e nell'ultima fila (possiamo modificare questa tendenza cambiando le due direzioni "permesse" dall'algoritmo).

       
       
       
       

Implementazione in PHP

Il codice per generare questa tipologia di labirinto è abbastanza semplice; partendo dalla classe sviluppata nel precedente articolo (e rifattorizzata per crearne una astratta da cui far derivare tutte le varie implementazioni) si vede come non solo sia molto più facile generare il labirinto in sé, ma anche rappresentarlo nella console (cosa che con il Depth First Search è stato un pochino più complicato)


<?php
require_once('./maze.php'); //includo la classe astratta

class Binary extends Maze
{
	private $grid;

	public function __construct($width, $height, $debug = false)
	{
		parent::__construct($width, $height, $debug);
		$this->grid = [];
        $this->directions = [[0, -1], [1, 0]]; // S, E
	}

Come si può vedere dal costruttore qui mi interessano soltanto due direzioni, Sud ed Est.

public function generate()
{    
    for ($y=0; $y<$this->height; $y++) {
        for ($x=0; $x < $this->width; $x++) {
            if ($x == $this->width-1 && $y == $this->height-1) {
                $this->grid[$y][$x] = 'X ';
                return $this;
            }
            if ($x == $this->width-1) {
                $this->grid[$y][$x] = 'S';
            } elseif ($y == $this->height-1) {
                $this->grid[$y][$x] = 'E';
            } else {
                // pick a random direction
                $p = $this->directions[rand(0,1)][0] == 0 ? 'S' : 'E';
                $this->grid[$y][$x] = $p;
            }
        }
    }
    return $this;
}

Come accennavo prima genero la griglia del labirinto con un ciclo e ne approfitto per decidere, ad ogni cella, verso quale delle due direzioni stabilite in partenza muovermi (naturalmente non sempre potrò scegliere, purtroppo).
$p = $this->directions[rand(0,1)][0] == 0 ? 'S' : 'E'; semplicemenre verifica se il valore preso a caso dalla lista di direzioni (in base all'indice) è la tupla di coordinate della cella a Sud oppure ad Est.

Al termine della generazione avrò una semplice griglia in cui ogni cella contiene il riferimento alla direzione verso cui abbattere il muro che la divide con la cella di destinazione.

public function printOut()
{
    $northDoor = mt_rand(0,$this->width-1);
    $westDoor = 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++) {
        $str .= $i == $westDoor ? ' ' : '|';
        for ($j=0; $j<$this->width; $j++) {
            $str .= $this->grid[$i][$j] == 'E' ? '    ' : '   |';
        }
        $str .= PHP_EOL."+";
        for ($j=0; $j<$this->width; $j++) {
            $str .= $this->grid[$i][$j] == 'S' ? '   +' : '---+';
        }
        $str .= PHP_EOL;
    }
    echo $str;
}

E siamo arrivati alla rappresentazione grafica del labirinto (anche qui nella console): ciclo nuovamente su tutte le celle e, semplicemente, decido se mostrare il muro di destra se la cella contiene il riferimento alla direzione Est oppure se disegnare un "pavimento" o meno qualora la cella abbia il riferimento alla direzione Sud. Anche qui ho creato un ingresso ed un'uscita random per dare completezza al labirinto.
Sarebbe interessante vedere come sia la strategia di generazione che, soprattutto, quella di stampa finale cambino scegliendo una coppia diversa di direzioni - magari affronterò questa piccola sfida in qualche post futuro.

Tornando a noi, istanzio la classe Binary con le dimensione che voglio dare al labirinto:

$maze = new Binary(12, 10);
$maze->generate()->printOut();

e questa genererà uno schema simile a questo - si può notare il tipico corridoio ininterrotto lungo la parete Est e quella Sud, come da previsioni:

$ php binary.php
+---+   +---+---+---+---+---+---+---+---+---+---+
|   |               |   |       |           |   |
+   +---+---+---+   +   +---+   +---+---+   +   +
|   |   |       |       |       |   |   |       |
+   +   +---+   +---+   +---+   +   +   +---+   +
|                   |   |   |       |   |       |
+---+---+---+---+   +   +   +---+   +   +---+   +
|   |       |   |   |   |               |   |   |
+   +---+   +   +   +   +---+---+---+   +   +   +
|       |       |       |   |   |               |
+---+   +---+   +---+   +   +   +---+---+---+   +
|                           |       |   |   |   |
+---+---+---+---+---+---+   +---+   +   +   +   +
|   |   |           |           |       |   |   |
+   +   +---+---+   +---+---+   +---+   +   +   +
    |       |           |   |               |   |
+   +---+   +---+---+   +   +---+---+---+   +   +
|                       |               |   |   |
+---+---+---+---+---+   +---+---+---+   +   +   +
|                                               |
+---+---+---+---+---+---+---+---+---+---+---+---+

Vedi anche:

Algoritmo per i labirinti: Depth First Search in PHP

Vi sono molti algoritmi per la generazione di labirinti e traversamento di grafi, come il Depth First Search; qui illustro la mia soluzione in PHP creata per RosettaCode...

SEO, statistica e curiosità con Google Trends

Google Trends - chi mastica un po' di SEO e di statistica probabilmente già lo sa - è uno strumento molto importante ed interessante per visualizzare...

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