Labyrinth-Generierung mit Tiefensuche

Labyrinth-Generierung mit Tiefensuche

🌐 Read in English
📅 20.11.2026 ✍ Andreas Wittmann đŸ‘ïž ... algorithm graphics computer-graphics maze

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:

  1. In einem beliebigen Raum beginnen und ihn als besucht markieren.
  2. Hat der aktuelle Raum unbesuchte Nachbarn, zufĂ€llig einen davon wĂ€hlen, die Wand dazwischen einreißen und dorthin gehen.
  3. Hat er keine, ist er eine Sackgasse: zurĂŒck in den Raum, aus dem man gekommen ist, und von dort aus weiterprobieren.
  4. 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);
        }
    }
}
Open in full editor →

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.