Den Ausgang finden: BFS und A* im Labyrinth

Den Ausgang finden: BFS und A* im Labyrinth

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

Der Artikel zur Labyrinth-Generierung hat ein Labyrinth gebaut, indem er einen zufÀlligen Tiefensuche-Pfad durch ein Raster aus RÀumen gegraben hat. Dieser Artikel findet den Weg wieder hinaus: vom Eingang oben links zum Ausgang unten rechts, im selben Labyrinth. Zwei klassische Algorithmen erledigen das, die Breitensuche und A*. Spannend ist dabei weniger, wie sie funktionieren, als vielmehr, wann einer von beiden tatsÀchlich besser ist als der andere.

Breitensuche

Die Breitensuche (englisch Breadth-First Search, BFS) beginnt am Eingang und erkundet das Labyrinth in Ringen wachsender Entfernung: zuerst jede Zelle einen Schritt entfernt, dann jede Zelle zwei Schritte entfernt und so weiter. Sie fĂŒhrt eine Front — eine Warteschlange von Zellen, die schon gefunden, aber noch nicht erkundet wurden — und erkundet immer die Zelle, die zuerst gefunden wurde.

Wem das bekannt vorkommt: Das ist wieder der Flood-Fill-Algorithmus, nur mit einer Warteschlange statt eines Stacks. Die FĂŒllung breitet sich gleichmĂ€ĂŸig nach außen aus, statt in langen Streifen davonzulaufen, und genau diese eine Änderung sorgt dafĂŒr, dass BFS den kĂŒrzesten Weg findet: Weil die Zellen in der Reihenfolge ihrer Entfernung vom Start erkundet werden, ist die Breitensuche beim ersten Erreichen des Ausgangs auf dem kĂŒrzestmöglichen Weg dorthin gelangt. Um diesen Weg wiederherzustellen, merkt sich jede Zelle, von welchem Nachbarn aus sie gefunden wurde; folgt man diesen Verweisen vom Ausgang aus rĂŒckwĂ€rts, landet man direkt wieder am Eingang.

A*

Die Breitensuche hat keine Ahnung, wo der Ausgang liegt. Sie breitet sich gleichmĂ€ĂŸig in alle Richtungen aus, auch vom Ziel weg. A* behebt das, indem es die nĂ€chste zu erkundende Zelle anhand zweier Zahlen auswĂ€hlt:

A* erkundet als NĂ€chstes immer die Zelle der Front mit dem kleinsten f = g + h — bevorzugt also Zellen, die sowohl nah am Start liegen als auch, soweit die SchĂ€tzung das beurteilen kann, nah am Ziel. Als SchĂ€tzung dient hier die Manhattan-Distanz, |x - ausgangX| + |y - ausgangY|: die Zahl der Schritte, die es ganz ohne WĂ€nde brĂ€uchte. WĂ€nde können den echten Weg nur verlĂ€ngern, nie verkĂŒrzen, die SchĂ€tzung ist also nie zu hoch. Genau diese Eigenschaft garantiert, dass A* weiterhin den kĂŒrzesten Weg findet, genau wie BFS.

Haben mehrere Zellen dasselbe f, wĂ€hlt diese Implementierung die mit dem kleineren h — die, die schĂ€tzungsweise nĂ€her am Ausgang liegt. Diese kleine Gleichstandsregel macht, wie die Zahlen weiter unten zeigen, einen erstaunlich großen Unterschied.

Implementierung

#include "plot.hpp"
#include <stdint.h>
#include <stdlib.h>

// false: breadth-first search, true: A*
const bool ASTAR = false;

// Extra walls to knock down after generating the maze. 0 gives the
// perfect maze from the maze generation article (exactly one path);
// anything above 0 adds loops, so there are shorter and longer routes.
const int EXTRA_OPENINGS = 30;

const uint32_t SEED = 1;

const int MW = 19, MH = 14;
const int GW = 2 * MW + 1, GH = 2 * MH + 1;
const int CELL = 15;

enum { WALL, UNVISITED, ON_STACK, OPEN };
int grid[GH][GW];

// ---- Maze generation (same as in the maze generation article) ----

uint32_t rng = SEED;
uint32_t next_random() {
    rng ^= rng << 13;
    rng ^= rng >> 17;
    rng ^= rng << 5;
    return rng;
}

void generate_maze() {
    static int sx[MW * MH], sy[MW * MH];
    int top = -1;
    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;

    top++; sx[top] = 1; sy[top] = 1; grid[1][1] = ON_STACK;
    while (top >= 0) {
        int x = sx[top], y = sy[top];
        int dx[4] = {2, -2, 0, 0}, dy[4] = {0, 0, 2, -2};
        int options[4], n = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx > 0 && nx < GW && ny > 0 && ny < GH && grid[ny][nx] == UNVISITED)
                options[n++] = k;
        }
        if (n == 0) {
            grid[y][x] = OPEN;
            top--;
            if (top >= 0) grid[(y + sy[top]) / 2][(x + sx[top]) / 2] = OPEN;
            continue;
        }
        int k = options[next_random() % n];
        grid[y + dy[k] / 2][x + dx[k] / 2] = ON_STACK;
        top++; sx[top] = x + dx[k]; sy[top] = y + dy[k]; grid[sy[top]][sx[top]] = ON_STACK;
    }
    grid[1][0] = OPEN;           // entrance
    grid[GH - 2][GW - 1] = OPEN; // exit

    // Knock down random inner walls that sit between two rooms.
    int count = EXTRA_OPENINGS;
    while (count > 0) {
        int x = 1 + next_random() % (GW - 2);
        int y = 1 + next_random() % (GH - 2);
        bool between = (x % 2 == 0 && y % 2 == 1) || (x % 2 == 1 && y % 2 == 0);
        if (between && grid[y][x] == WALL) {
            grid[y][x] = OPEN;
            count--;
        }
    }
}

// ---- The search ----

const int SX = 0, SY = 1;            // start: the entrance
const int TX = GW - 1, TY = GH - 2;  // target: the exit

enum { NEW, FRONTIER, EXPLORED };
int state[GH][GW];
int cost[GH][GW];      // steps from the start
int parentX[GH][GW];   // where we came from, to rebuild the path
int parentY[GH][GW];
bool onPath[GH][GW];

// The frontier: cells that have been found but not explored yet.
int frontX[GW * GH];
int frontY[GW * GH];
int frontCount = 0;
int frontHead = 0; // BFS only: index of the oldest entry

bool found = false;
bool done = false;
int exploredCount = 0;

int estimate(int x, int y) {
    return abs(x - TX) + abs(y - TY); // Manhattan distance to the exit
}

// The only real difference between BFS and A*: which cell to explore next.
int pick_next() {
    if (!ASTAR) return frontHead++; // BFS: the one found first

    // A*: lowest cost-so-far + estimated cost-to-go. On a tie, prefer the
    // one that is estimated to be closer to the exit.
    int best = 0;
    for (int i = 1; i < frontCount; i++) {
        int fi = cost[frontY[i]][frontX[i]] + estimate(frontX[i], frontY[i]);
        int fb = cost[frontY[best]][frontX[best]] + estimate(frontX[best], frontY[best]);
        if (fi < fb || (fi == fb && estimate(frontX[i], frontY[i]) < estimate(frontX[best], frontY[best])))
            best = i;
    }
    return best;
}

bool frontier_empty() {
    return ASTAR ? frontCount == 0 : frontHead == frontCount;
}

void add_to_frontier(int x, int y, int fromX, int fromY, int newCost) {
    state[y][x] = FRONTIER;
    cost[y][x] = newCost;
    parentX[y][x] = fromX;
    parentY[y][x] = fromY;
    frontX[frontCount] = x;
    frontY[frontCount] = y;
    frontCount++;
}

void step() {
    if (frontier_empty()) { done = true; return; }

    int i = pick_next();
    int x = frontX[i], y = frontY[i];
    if (ASTAR) { // remove it by moving the last entry into its place
        frontCount--;
        frontX[i] = frontX[frontCount];
        frontY[i] = frontY[frontCount];
    }
    state[y][x] = EXPLORED;
    exploredCount++;

    if (x == TX && y == TY) {
        // Walk the parent links back to the start to mark the path.
        while (!(x == SX && y == SY)) {
            onPath[y][x] = true;
            int px = parentX[y][x], py = parentY[y][x];
            x = px; y = py;
        }
        onPath[SY][SX] = true;
        found = done = true;
        return;
    }

    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= GW || ny < 0 || ny >= GH) continue;
        if (grid[ny][nx] == WALL || state[ny][nx] != NEW) continue;
        add_to_frontier(nx, ny, x, y, cost[y][x] + 1);
    }
}

void setup() {
    PlotCanvas(640, 480);
    generate_maze();
    add_to_frontier(SX, SY, SX, SY, 0);
}

void frame() {
    for (int n = 0; n < 2 && !done; n++) step();

    PlotBackground(250, 250, 250);
    int ox = (640 - GW * CELL) / 2;
    int oy = 480 - GH * CELL - 8; // leave room for the status line on top
    for (int y = 0; y < GH; y++) {
        for (int x = 0; x < GW; x++) {
            if (grid[y][x] == WALL)            PlotColor(40, 44, 52);    // wall
            else if (onPath[y][x])             PlotColor(220, 60, 60);   // the path found
            else if (state[y][x] == EXPLORED || (done && state[y][x] == FRONTIER))
                                               PlotColor(70, 170, 90);   // explored
            else if (state[y][x] == FRONTIER)  PlotColor(220, 60, 60);   // frontier
            else                               PlotColor(30, 100, 200);  // not reached
            PlotFilledRectangle(ox + x * CELL, oy + y * CELL,
                                ox + x * CELL + CELL - 1, oy + y * CELL + CELL - 1);
        }
    }

    if (done) {
        PlotColor(40, 44, 52);
        PlotText(ox, 8, found ? "%s: path %d cells, explored %d cells"
                              : "%s: no path, explored %d cells",
                 ASTAR ? "A*" : "BFS",
                 found ? cost[TY][TX] + 1 : exploredCount, exploredCount);
    }
}
Open in full editor →

Der erste Teil ist der Labyrinth-Generator aus dem vorigen Artikel, unverĂ€ndert und mit demselben Seed — es ist also exakt dasselbe Labyrinth. Danach kann das Programm zufĂ€llig ein paar zusĂ€tzliche WĂ€nde einreißen, wodurch Schleifen entstehen (mehr dazu weiter unten).

Die Suche selbst hĂ€lt die Front in einem einzigen Array. pick_next ist die einzige Stelle, an der sich BFS und A* unterscheiden: BFS nimmt den Ă€ltesten Eintrag, A* sucht in der Front nach dem kleinsten f. Blaue Zellen wurden noch nicht erreicht, rote Zellen liegen auf der Front, und grĂŒne Zellen wurden erkundet. Ist der Ausgang erreicht, wird der Weg ĂŒber die Elternverweise zurĂŒckverfolgt und rot angezeigt, zusammen mit einer Statuszeile, die angibt, wie lang der Weg ist und wie viele Zellen dafĂŒr erkundet werden mussten.

Oben gibt es zwei Schalter: ASTAR wĂ€hlt den Algorithmus, und EXTRA_OPENINGS legt fest, wie viele zusĂ€tzliche WĂ€nde eingerissen werden. Probiere mit „Compile & Run“ alle vier Kombinationen aus.

Wann A* hilft und wann nicht

Mit den Standardwerten — BFS auf einem Labyrinth mit 30 zusĂ€tzlichen Öffnungen — fĂ€chert sich die Suche gleichmĂ€ĂŸig auf und erkundet fast das gesamte Labyrinth, bevor sie den Ausgang erreicht. Ein Wechsel zu A* auf demselben Labyrinth ergibt ein ganz anderes Bild:

Labyrinth (SEED = 1) kĂŒrzester Weg von BFS erkundet von A* erkundet
30 zusĂ€tzliche Öffnungen 77 Zellen 560 von 563 259
perfekt (EXTRA_OPENINGS = 0) 205 Zellen 257 von 533 256

Mit Schleifen erkundet A* fĂŒr denselben 77-Zellen-Weg weniger als halb so viele Zellen wie BFS und steuert auf den Ausgang zu, statt jeden Winkel des Labyrinths abzusuchen. Ohne die Gleichstandsregel erkundet ein einfaches A* 329 Zellen: immer noch deutlich besser als BFS, aber viel weniger zielgerichtet.

Im perfekten Labyrinth aus dem vorigen Artikel erkundet A* 256 statt 257 Zellen — praktisch kein Unterschied. Der Grund: Es gibt kaum etwas einzusparen. Ein perfektes Labyrinth hat genau einen Weg vom Eingang zum Ausgang, und der ist bei diesem Labyrinth 205 Zellen lang. Jeder Algorithmus muss mindestens diese 205 Zellen erkunden, BFS verschwendet also von vornherein nur 52 Zellen an SeitengĂ€nge. Ein mit Tiefensuche erzeugtes Labyrinth wie dieses fĂŒhrt A* mit seinen langen, gewundenen GĂ€ngen außerdem stĂ€ndig von der geraden Linie weg, die es schĂ€tzt — die SchĂ€tzung hilft also wenig. Gemittelt ĂŒber 200 verschiedene Seeds erkundet A* im perfekten Labyrinth 297,1 statt 334,0 Zellen bei BFS, etwa 11 % weniger. Mit 30 zusĂ€tzlichen Öffnungen sinkt der Durchschnitt von 525,4 Zellen bei BFS auf 276,7 bei A* — fast die HĂ€lfte.

In jedem dieser 400 DurchlĂ€ufe fanden BFS und A* exakt gleich lange Wege. A* findet keinen besseren Weg, sondern denselben kĂŒrzesten Weg mit weniger Aufwand — und wie viel weniger, hĂ€ngt ganz davon ab, wie viel Raum das Labyrinth fĂŒr AbkĂŒrzungen lĂ€sst.

Fazit

Damit endet ein kleiner Bogen von Artikeln, die sich alle als dasselbe Thema herausgestellt haben. Flood Fill besucht jede Zelle, die von einem Startpunkt aus erreichbar ist. Die Labyrinth-Generierung baut mit einer zufĂ€lligen Tiefensuche einen Spannbaum. Die Breitensuche ist Flood Fill mit einer Warteschlange, die aus „alles Erreichbare“ den „kĂŒrzesten Weg“ macht. Und A* ist eine Breitensuche mit Orientierungssinn: dieselbe Front, nur in einer klĂŒgeren Reihenfolge abgearbeitet.