Generator labirinta Wilsonovog algoritma
Objavljeno: 16. veljače 2025. u 19:37:57 UTC
Generator labirinta koji koristi Wilsonov algoritam za stvaranje savršenog labirinta. Ovaj algoritam generira sve moguće labirinte zadane veličine s istom vjerojatnošću, tako da u teoriji može generirati labirinte s mnogo mješovitih rasporeda, ali kako postoji više mogućih labirinta s kraćim hodnicima nego duljima, češće ćete ih vidjeti.Wilson's Algorithm Maze Generator
Wilsonov algoritam je metoda nasumičnog hoda s brisanjem petlje koja generira uniformna razapinjuća stabla za stvaranje labirinta. To znači da je jednako vjerojatno da će se generirati svi mogući labirinti određene veličine, što ga čini nepristranom tehnikom generiranja labirinta. Wilsonov algoritam može se smatrati poboljšanom verzijom Aldous-Broder algoritma, budući da generira labirinte s identičnim karakteristikama, ali radi mnogo brže, tako da se nisam trudio implementirati Aldous-Broder algoritam ovdje.
Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.
Ovdje generirane karte labirinta uključuju zadanu verziju bez ikakvih početnih i završnih pozicija, tako da ih možete sami odlučiti: postojat će rješenje od bilo koje točke u labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.
O Wilsonovom algoritmu
Wilsonov algoritam za generiranje uniformnih razapinjućih stabala pomoću nasumičnog zida izbrisanog petljom stvorio je David Bruce Wilson.
Wilson je izvorno predstavio ovaj algoritam 1996. dok je istraživao nasumična razapinjuća stabla i Markovljeve lance u teoriji vjerojatnosti. Iako je njegov rad primarno bio u matematici i statističkoj fizici, algoritam je od tada naširoko prihvaćen za generiranje labirinta zbog njegove sposobnosti stvaranja savršeno jednolikih labirinata.
Kako Wilsonov algoritam radi za stvaranje labirinta
Wilsonov algoritam osigurava da je konačni labirint u potpunosti povezan bez ikakvih petlji iterativnim urezivanjem staza iz neposjećenih stanica korištenjem slučajnih šetnji.
Korak 1: Inicijalizacija
- Započnite s rešetkom ispunjenom zidovima.
- Definirajte popis svih mogućih prolaznih ćelija.
Korak 2: Odaberite nasumično početnu ćeliju
- Odaberite bilo koju ćeliju i označite je kao posjećenu. Ovo služi kao početna točka labirinta tijekom generiranja.
Korak 3: Nasumični hod s brisanjem petlje
- Odaberite neposjećenu ćeliju i počnite nasumično hodati (krećući se u nasumičnim smjerovima).
- Ako šetnja dosegne već posjećenu ćeliju, izbrišite sve petlje na stazi.
- Nakon što se šetnja poveže s posjećenom regijom, označite sve ćelije na putu kao posjećene.
Korak 4: Ponavljajte dok se ne posjete sve ćelije :
- Nastavite odabirati neposjećene ćelije i izvoditi nasumične šetnje sve dok svaka stanica ne postane dio labirinta.