Labyrinth-Generierung mit Tiefensuche
Der Flood-Fill-Algorithmus hat sich als verkleidete Graphensuche entpuppt: Zellen sind Knoten, benachbarte leere Zellen sind verbunden, und eine FlĂ€che zu fĂŒllen heiĂt, alles zu besuchen, was von einem Startpunkt aus erreichbar ist. Die Labyrinth-Generierung dreht diese Idee um. Statt einen vorhandenen Graphen zu erkunden, baut sie einen â indem sie entscheidet, welche WĂ€nde zwischen benachbarten RĂ€umen eingerissen werden.
Was ein perfektes Labyrinth ausmacht
Man stelle sich ein Raster aus RĂ€umen vor, mit einer Wand zwischen je zwei Nachbarn. Ein Labyrinth ist das, was ĂŒbrig bleibt, wenn man einige dieser WĂ€nde entfernt. Perfekt heiĂt es, wenn jeder Raum erreichbar ist und es von jedem Raum zu jedem anderen genau einen Weg gibt: keine Schleifen, keine abgeschlossenen Bereiche.
In der Sprache der Graphen ist das ein Spannbaum: Die RĂ€ume sind die
Knoten, eine Ăffnung in einer Wand ist eine Kante, und ein Baum, der n
Knoten verbindet, hat immer genau n - 1 Kanten. Ein perfektes Labyrinth
mit 266 RĂ€umen braucht also genau 265 Ăffnungen, nie mehr und nie weniger.
Jeder Algorithmus, der einen zufÀlligen Spannbaum auf dem Raster erzeugt,
erzeugt damit ein perfektes Labyrinth.
Der Recursive Backtracker
Der einfachste dieser Algorithmen ist eine zufÀllige Tiefensuche, meist Recursive Backtracker genannt:
- In einem beliebigen Raum beginnen und ihn als besucht markieren.
- Hat der aktuelle Raum unbesuchte Nachbarn, zufĂ€llig einen davon wĂ€hlen, die Wand dazwischen einreiĂen und dorthin gehen.
- Hat er keine, ist er eine Sackgasse: zurĂŒck in den Raum, aus dem man gekommen ist, und von dort aus weiterprobieren.
- Aufhören, sobald man wieder am Start ist und nichts mehr zu besuchen bleibt.
Schritt 2 kann nie eine Schleife erzeugen, weil er eine Wand immer nur zu einem Raum öffnet, der noch nicht besucht wurde. Und weil Schritt 3 so lange zurĂŒckgeht, bis jeder Raum ausprobiert ist, bleibt kein Raum ĂŒbrig. Zusammen ergibt das genau einen Spannbaum.
Implementierung
#include "plot.hpp"
#include <stdint.h>
// Change the seed to get a different maze.
const uint32_t SEED = 1;
const int MW = 19; // rooms per row
const int MH = 14; // rooms per column
const int GW = 2 * MW + 1; // grid width: rooms plus the walls between them
const int GH = 2 * MH + 1;
const int CELL = 16;
enum { WALL, UNVISITED, ON_STACK, DONE };
int grid[GH][GW];
// The path from the start to the current room. Every room is pushed
// exactly once, so MW * MH entries are always enough.
int stackX[MW * MH];
int stackY[MW * MH];
int top = -1;
// A small xorshift generator instead of rand(), so the same seed gives
// the same maze everywhere, not just with one particular C library.
uint32_t rng = SEED;
uint32_t next_random() {
rng ^= rng << 13;
rng ^= rng >> 17;
rng ^= rng << 5;
return rng;
}
void push(int x, int y) {
top++;
stackX[top] = x;
stackY[top] = y;
grid[y][x] = ON_STACK;
}
// One step of the depth-first search: look at the room on top of the
// stack. If it has unvisited neighbors, pick one at random, knock down
// the wall in between and move there. If not, it is finished: step back.
void step() {
int x = stackX[top];
int y = stackY[top];
int dx[4] = {2, -2, 0, 0};
int dy[4] = {0, 0, 2, -2};
int options[4];
int n = 0;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx > 0 && nx < GW && ny > 0 && ny < GH && grid[ny][nx] == UNVISITED) {
options[n++] = k;
}
}
if (n == 0) {
// Dead end: this room is finished. Step back to the previous one,
// and the opening we came through is finished as well.
grid[y][x] = DONE;
top--;
if (top >= 0) {
grid[(y + stackY[top]) / 2][(x + stackX[top]) / 2] = DONE;
}
return;
}
int k = options[next_random() % n];
grid[y + dy[k] / 2][x + dx[k] / 2] = ON_STACK; // knock down the wall
push(x + dx[k], y + dy[k]);
}
void setup() {
PlotCanvas(640, 480);
// Rooms sit on odd coordinates, everything else starts out as wall.
for (int y = 0; y < GH; y++) {
for (int x = 0; x < GW; x++) {
grid[y][x] = (x % 2 == 1 && y % 2 == 1) ? UNVISITED : WALL;
}
}
push(1, 1);
}
void frame() {
// Two steps per frame: carving forward and backtracking both count.
for (int n = 0; n < 2 && top >= 0; n++) step();
// Entrance top left, exit bottom right, once the maze is complete.
if (top < 0) {
grid[1][0] = DONE;
grid[GH - 2][GW - 1] = DONE;
}
PlotBackground(250, 250, 250);
int ox = (640 - GW * CELL) / 2;
int oy = (480 - GH * CELL) / 2;
for (int y = 0; y < GH; y++) {
for (int x = 0; x < GW; x++) {
int c = grid[y][x];
if (c == WALL) PlotColor(40, 44, 52); // wall
else if (c == UNVISITED) PlotColor(30, 100, 200); // not visited yet
else if (c == ON_STACK) PlotColor(220, 60, 60); // on the current path
else PlotColor(70, 170, 90); // finished
PlotFilledRectangle(ox + x * CELL, oy + y * CELL,
ox + x * CELL + CELL - 1, oy + y * CELL + CELL - 1);
}
}
}
Das Raster speichert RĂ€ume und WĂ€nde gemeinsam: RĂ€ume liegen auf ungeraden Koordinaten, die Zellen dazwischen sind WĂ€nde, die eingerissen werden können. Ein Labyrinth aus 19Ă14 RĂ€umen wird so zu einem Raster von 39Ă29 Zellen, das sich einfach Zelle fĂŒr Zelle zeichnen lĂ€sst und die WĂ€nde gleich mit abbildet. Dunkle Zellen sind WĂ€nde, blaue RĂ€ume wurden noch nicht besucht, Rot markiert den aktuellen Weg vom Start aus, und grĂŒne RĂ€ume sind fertig.
Wie beim Flood Fill liegt die Rekursion in einem expliziten Stack statt
auf dem Aufruf-Stack, sodass die Animation pro Aufruf einen Schritt machen
kann. Jedes step geht entweder vorwĂ€rts in einen neuen Raum oder zurĂŒck
aus einem fertigen. Jeder Raum wird einmal betreten und einmal verlassen,
auĂer dem Startraum, der von nirgendwo aus betreten wird â das ganze
Labyrinth braucht also genau 2 Ă 266 - 1 = 531 Schritte, egal wie die
Zufallsentscheidungen ausfallen.
Die Zufallszahlen kommen aus einem winzigen Xorshift-Generator statt aus
rand(), weil rand() mit unterschiedlichen C-Bibliotheken
unterschiedliche Folgen liefert und derselbe Seed ĂŒberall dasselbe
Labyrinth ergeben soll. Ăndere SEED im Code oben und klicke auf âCompile
& Runâ, um ein neues zu bekommen.
Lange GĂ€nge, wenige Sackgassen
Die Tiefensuche geht immer so weit wie möglich, bevor sie umkehrt, und das
sieht man dem Ergebnis an. Mit SEED = 1 erreicht der Pfad-Stack an einer
Stelle eine Tiefe von 191 von 266 RĂ€umen, und der Weg vom Eingang oben
links zum Ausgang unten rechts windet sich durch 102 RĂ€ume. Wie beim
naiven rekursiven Flood Fill wĂŒrde eine echt rekursive Variante genauso
tief auf dem Aufruf-Stack landen â hier kein Problem, bei Labyrinthen mit
Millionen von RĂ€umen aber schon.
Andere Algorithmen, die ebenfalls perfekte Labyrinthe bauen, erzeugen eine merklich andere Struktur. Der zufĂ€llige Algorithmus von Prim lĂ€sst das Labyrinth vom Start aus nach auĂen wachsen, indem er immer wieder einen zufĂ€lligen Raum am Rand des bisher gebauten Labyrinths wĂ€hlt, statt einem Weg so weit wie möglich zu folgen. Gemittelt ĂŒber 200 Seeds auf demselben 19Ă14-Raster:
| Sackgassen | Weg von Ecke zu Ecke | |
|---|---|---|
| Recursive Backtracker | 28,4 RĂ€ume (11 %) | 109,8 RĂ€ume |
| Algorithmus von Prim | 92,7 RĂ€ume (35 %) | 33,9 RĂ€ume |
Der Backtracker erzeugt lange, gewundene GĂ€nge mit wenigen Abzweigungen. Prims Algorithmus erzeugt viele kurze Sackgassen und einen deutlich direkteren Lösungsweg. Beides sind perfekte Labyrinthe â gleich viele RĂ€ume, gleich viele Ăffnungen, nur ganz anders angeordnet.
Fazit
Ein perfektes Labyrinth ist ein zufĂ€lliger Spannbaum, auf ein Raster gezeichnet, und der Recursive Backtracker baut einen mit nichts weiter als einem Stack und einer Zufallsentscheidung pro Schritt. Das Labyrinth zu erzeugen ist allerdings nur die halbe Geschichte. Den Weg hindurch zu finden ist wieder eine eigene Graphensuche â und genau dort kommen Breitensuche und A* ins Spiel.