Was ist ein guter Algorithmus zur Erstellung eines Labyrinths?

Question

Nehmen wir an, Sie wollen ein einfaches Labyrinth auf einem N x M-Raster, mit einem Weg durch, und eine gute Anzahl von Sackgassen, aber das sieht "richtig" (d.h. wie jemand es von Hand ohne zu viele kleine winzige Sackgassen und all das gemacht). Gibt es eine bekannte Methode, dies zu tun?

Answer 1

Rekursives Backtracking ist der am einfachsten zu implementierende Algorithmus.

Hier ist eine Java-Implementierung:

Hier Zelle ist eine Klasse, die eine Zelle in einem 2D-Gitter darstellt, und Zellen ist ein 2D-Array aus Zelle Objekte. Zelle hat boolesche Variablen top , unten , links y rechts um anzuzeigen, ob eine Zelle an diesen Seiten Wände hat, eine boolesche Variable besucht um zu überprüfen, ob wir sie durchquert haben, und zwei ganzzahlige Variablen Zeile y Spalte um seine Position im Raster anzugeben.

Cell current = cells[0][0] , next;
    current.visited=true;
    do{
        next = getNeighbour(current);
        if(next!=null){
            removeWall(current , next);
            st.push(current);
            current = next;
            current.visited = true;
        }
        else {
            current = st.pop();
        }
    }
    while (!st.empty());

    private Cell getNeighbour(Cell cell){
    ArrayList<Cell> ara = new ArrayList<>();
    if(cell.col>0 && !cells[cell.col-1][cell.row].visited)
         ara.add(cells[cell.col-1][cell.row]);

    if(cell.row>0 && !cells[cell.col][cell.row-1].visited)
         ara.add(cells[cell.col][cell.row-1]);

    if(cell.col<col-1 && !cells[cell.col+1][cell.row].visited)
         ara.add(cells[cell.col+1][cell.row]);
    if(cell.row<row-1 && !cells[cell.col][cell.row+1].visited)
         ara.add(cells[cell.col][cell.row+1]); 

    if(ara.size()>0){
        return ara.get(new Random().nextInt(ara.size()));
    }else{
        return null;
    }
}
private void removeWall(Cell curr , Cell nxt){
    if((curr.col == nxt.col) && (curr.row == nxt.row+1)){/// top
        curr.top=nxt.botttom=false;
    }
    if(curr.col==nxt.col && curr.row == nxt.row-1){///bottom
        curr.botttom = nxt.top = false;
    }
    if(curr.col==nxt.col-1 && curr.row==nxt.row ){///right
        curr.right = nxt.left = false;
    }
    if(curr.col == nxt.col+1 && curr.row == nxt.row){///left
        curr.left = nxt.right = false;
    }
}

Answer 2

Eine der Methoden zur Erzeugung eines Labyrinths ist die randomisierte Version des Algorithmus von Prim.

Beginne mit einem Gitter voller Wände. Wähle eine Zelle und markiere sie als Teil des Labyrinths. Füge die Wände der Zelle zur Wandliste hinzu. Solange es Wände in der Liste gibt:

Wählen Sie eine beliebige Wand aus der Liste. Wenn sich die Zelle auf der gegenüberliegenden Seite noch nicht im Labyrinth befindet:

(i) Mache die Wand zu einem Durchgang und markiere die Zelle auf der gegenüberliegenden Seite als Teil des Labyrinths.

(ii) Fügen Sie die benachbarten Wände der Zelle in die Wandliste ein.

Wenn die Zelle auf der gegenüberliegenden Seite bereits im Labyrinth war, streiche die Wand aus der Liste.

Answer 3

Hier ist der DFS-Algorithmus als Pseudocode geschrieben:

einen CellStack (LIFO) erstellen, der eine Liste von Zellenstandorten enthält
set TotalCells = Anzahl der Zellen im Gitter
eine Zelle nach dem Zufallsprinzip auswählen und sie CurrentCell nennen
set VisitedCells = 1

while VisitedCells < TotalCells alle Nachbarn von CurrentCell finden, bei denen alle Wände intakt sind
wenn eine oder mehrere gefundene wähle einen nach dem Zufallsprinzip
die Mauer zwischen ihr und CurrentCell niederreißen
Verschieben der Position von CurrentCell auf dem CellStack
die neue Zelle zu CurrentCell machen
1 zu VisitedCells hinzufügen sonst den letzten Zelleneintrag aus dem CellStack entfernen
CurrentCell daraus machen endIf endWhile

Answer 4

Ich bevorzuge eine Version des Algorithmus der rekursiven Division. Er wird im Detail beschrieben hier.

Ich werde einen kurzen Überblick geben:
Der ursprüngliche rekursive Divisionsalgorithmus funktioniert wie folgt. Beginnen Sie mit einem leeren Bereich für das Labyrinth. Fügen Sie eine gerade Wand hinzu, um die Kammer in zwei Teile zu unterteilen, und setzen Sie irgendwo ein Loch in diese Wand. Dann wiederholen Sie diesen Vorgang rekursiv für jede der beiden neuen Kammern, bis die gewünschte Durchgangsgröße erreicht ist. Das ist einfach und funktioniert gut, aber es gibt offensichtliche Engpässe, durch die das Labyrinth leicht zu lösen ist.

Die Variante löst dieses Problem, indem sie keine geraden, sondern zufällig angeordnete, "gekrümmte" Wände zeichnet, wodurch die Engpässe weniger offensichtlich sind.