Algoritmo per la generazione di labirinti #2: Sidewinder

Labirinto • set 28, 2018

Il secondo algoritmo che affronto in questo mio ciclo personale di algoritmi per la generazione di labirinti è il Sidewinder, la cui difficoltà è di poco superiore a quella del Binary Tree. C'è da dire che ho trovato pochissimi riferimenti in giro sull'origine di questo algoritmo, e la maggior paarte di essi alla fine va a puntare alle solite due risorse, il blog di Jamis Buck(2) e il sito Think Labyrinth(3).

Anche il nome, "Sidewinder", è particolare: al di là di essere una specie di serpente a sonagli (il Crotalo ceraste), nella descrizione data su Think Labyrinth sembra che il nome possa derivare dal suo percorso, il quale "wind from side to side" ("si snoda da un lato all'altro") - simile quindi a quello del rettile. In un commento sul blog di Buck un utente fa notare come esista un altro algoritmo con lo stesso nome anche se relativamente ad un ambito completamente diverso.

Ma tornando a noi: le istruzioni, come dicevo, sono poco più complesse del Binary Tree e generano un labirinto con un basso utilizzo di memoria (viene affrontata una cella alla volta e bisogna tenere traccia, al massimo, di tutte le celle della riga) in cui abbiamo solo un lato completamente aperto (al contrario dei due dell'altra implementazione) e quindi un aspetto finale un po' più interessante. Anche qui si procede scegliendo in maniera casuale fra due direzioni, Nord oppure Est, ma le azioni da intraprendere cambiano a seconda dell'esito:

1) Si crea una griglia (m*n) che rappresenta il labirinto. Ad esempio, 4x4:

2) Si parte dalla cella in alto a sinistra (con coordinate [0,0], ma si può partire anche da quella in basso a destra [m,n]) e si decide, randomicamente, che direzione prendere fra Nord o Est. La prima riga, come si può notare, è un caso particolare molto semplice: non potendo scegliere Nord come direzione possiamo solo andare verso Est, fino alla parete di destra:

3) Si passa ora alla riga successiva: aggiungiamo la cella ad una lista (qui rappresentata in azzurro) di celle visitate in questo "giro" e scegliamo una direzione a caso; ci capita Est, quindi abbattiamo il muro verso la cella di destra e la aggiungiamo alla lista.

4) Peschiamo a caso ancora quale direzione prendere ed ora esce Nord - e qui arriva la particolarità: non abbattiamo il "soffitto" di questa cella, ma semplicemente ci fermiamo e scegliamo, anche qui a caso, una cella appartenente alla lista del giro appena effettuato (ad esempio la seconda), e rimuoviamo la barriera a quella cella:

5) Azzeriamo ora la lista di celle visitate e ricominciamo il giro; aggiungiamo la nuova cella alla lista e scegliamo una direzione: esce Est, abbattiamo quindi il muro ed arriviamo alla cella successiva, che però è l'ultima della fila:

6) Non potendo proseguire ulteriormente ad Est anche qui siamo di fronte ad una scelta obbligata: come appena successo dobbiamo quindi prendere una cella a caso dalla lista di questo "giro" e aprire un soffitto lì:

7) Abbiamo così completato la riga ed è tempo di passare a quella successiva: azzeriamo la lista del "giro" fatto e ripartiamo dal punto 3) e così via fino al termine del labirinto:

Il codice php per generare un labirinto con l'algoritmo Sidewinder è semplice: come nel caso del Binary Tree tutto si concentra nel metodo $this->generate():

public function generate()
{
    for ($y = 0; $y < $this->height; $y++) {
        $runSet = [];
        for ($x = 0; $x < $this->width; $x++) {
            $this->log('Adding current cell to runSet', $x);
            array_push($runSet, $x);
            if ($y === 0) {
                // first row, can only go east
                $this->log('First row, can only go east. No need to keep track of the current set');
                $this->grid[$y][$x] = ($x == $this->width-1) ? 'X|' : 'E';
            }  else {
                if ($x === $this->width-1 || (mt_rand(0, $this->weight) === 0)) {
                    $this->grid[$y][$x] = 'X|';
                    $this->log("Stop - Current set: %s", json_encode($runSet));
                    $selected = $runSet[array_rand($runSet)];
                    $this->log('Removing N wall from element at $x %d', $selected);
                    $this->grid[$y][$selected] = $x == $selected ?  'N|' : 'N';
                    $runSet = [];
                } else {
                    $this->log('Current set: %s', json_encode($runSet));
                    $this->grid[$y][$x] = 'E';
                }
            }
        }
    }
    return $this;
}

Ciclo la griglia riga per riga e per ogni cella scelgo una delle due direzioni possibili (a parte la prima riga, $y === 0, dove per tutte le celle sono obbligato ad andare ad Est).

if ($x === $this->width-1 || (mt_rand(0, $this->weight) === 0)) {

Essendo solo due le** possibilità di movimento** è molto più semplice usare due valori numerici per decidere dove andare; qui, inoltre, inserisco un fattore di personalizzazione dell'algoritmo, $this->weight, il "peso", che va ad influire sulla probabilità che esca Nord come direzione. Aumentando questo valore è più difficile che esca 0 (che ho arbitrariamente identificato con il Nord) e quindi il labirinto tenderà a contenere più passaggi orizzonali rispetto a quelli verticali.

Le diverse lettere assegnate alla cella sono un artificio per aiutarmi nella rappresentazione grafica nella command line: poichè alcune celle del "giro" potevano essere sovrascritte con l'indicazione su dove aprire l'apertura a Nord ho cercato di differenziarle per non perdere alcuna informazione:

public function printOut()
{
    $northDoor = mt_rand(0, $this->width-1);
    $southDoor = mt_rand(0, $this->width-1);

    $str = '';
    for ($i=0; $i<$this->height; $i++) {

        $str .= "\n+";
        for ($j=0; $j<$this->width; $j++) {
            $str .= ($this->grid[$i][$j] == 'N' || $this->grid[$i][$j] == 'N|' || ($i===0 && $j==$northDoor)) ? '   +' : '---+';
        }
        $str .=  "\n|";
        for ($j=0; $j<$this->width; $j++) {
            $str .= ($this->grid[$i][$j] == 'E' || $this->grid[$i][$j] == 'N') ? '    ' : '   |';
        }
    }
    $str .= "\n+";
    for ($i=0;$i<$this->width;$i++) {
        $str .= $i == $southDoor ? '   +' : '---+';
    }        
    echo "\n$str\n";
}

Come negli altri labirinti anche qui ho messo un ingresso ed un'uscita per rendere il tutto più piacevole da vedere 😊

Questo è quanto generato da una configurazione di default, ovvero con $weight = 1:

$maze = new Sidewinder(12, 8);
$maze->generate()->printOut();

+---+   +---+---+---+---+---+---+---+---+---+---+
|                                               |
+---+   +---+---+   +   +   +   +---+---+---+   +
|           |       |   |   |               |   |
+   +---+   +   +   +---+---+   +   +   +   +   +
|   |       |   |   |           |   |   |   |   |
+   +---+   +   +---+   +---+---+---+   +   +---+
|   |       |   |           |           |       |
+   +---+---+   +---+---+   +   +   +   +   +---+
|       |       |           |   |   |   |       |
+---+   +---+   +---+---+---+   +   +   +---+   +
|       |                   |   |   |   |       |
+   +   +---+   +   +   +   +   +   +---+   +---+
|   |   |       |   |   |   |   |   |           |
+   +---+---+---+   +---+   +---+   +   +---+   +
|   |               |       |       |       |   |
+---+---+---+---+---+---+   +---+---+---+---+---+

Mentre se impostiamo ad esempio a 10 il peso ecco che notiamo subito le differenze:

$maze = new Sidewinder(12, 8);
$maze->setWeight(10);
$maze->generate()->printOut();

+---+   +---+---+---+---+---+---+---+---+---+---+
|                                               |
+---+---+---+---+---+---+   +---+---+---+---+---+
|                                               |
+---+---+---+   +---+---+---+---+---+---+---+---+
|                                               |
+---+---+   +---+---+---+---+---+---+---+---+---+
|                                               |
+   +---+   +---+   +---+---+---+   +---+---+   +
|       |       |   |                       |   |
+---+---+   +---+---+---+---+---+---+---+---+---+
|                                               |
+   +---+---+---+---+---+---+---+   +---+---+---+
|           |                                   |
+---+---+---+---+---+   +---+---+---+   +   +---+
|                                   |   |       |
+---+   +---+---+---+---+---+---+---+---+---+---+

Quasi tutti passaggi orizzontali, essendo diventata 1/10 la possibilità di aprirne uno verticale.