Matteo Vignoli
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:
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.
Matteo Vignoli