Generator labirinta Wilsonovog algoritma

Wilsonov algoritam je metoda slučajnog hoda s brisanjem petlje koja generira uniformna razapinjujuća stabla za stvaranje labirinta. To znači da je vjerojatnost generiranja svih mogućih labirinta zadane veličine jednaka, što ga čini nepristranom tehnikom generiranja labirinta. Wilsonov algoritam može se smatrati poboljšanom verzijom Aldous-Broderovog algoritma, jer generira labirinte s identičnim karakteristikama, ali radi mnogo brže, pa se nisam trudio implementirati Aldous-Broderov 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 korištenjem slučajnog zida s brisanjem petlje stvorio je David Bruce Wilson.

Wilson je izvorno predstavio ovaj algoritam 1996. godine dok je istraživao slučajna razapinjuća stabla i Markovljeve lance u teoriji vjerojatnosti. Iako je njegov rad prvenstveno bio u matematici i statističkoj fizici, algoritam je od tada široko prihvaćen za generiranje labirinata zbog svoje sposobnosti stvaranja savršeno ujednačenih labirinata.

Kako Wilsonov algoritam funkcionira za generiranje labirinta

Wilsonov algoritam osigurava da je konačni labirint potpuno povezan bez ikakvih petlji iterativnim rezbarenjem putova iz neposjećenih ćelija korištenjem slučajnih šetnji.

Korak 1: Inicijalizacija

• Započnite s mrežom ispunjenom zidovima.
• Definirajte popis svih mogućih ćelija prolaza.

Korak 2: Odaberite slučajnu početnu ćeliju

• Odaberite bilo koju slučajnu ćeliju i označite je kao posjećenu. To služi kao početna točka labirinta tijekom generiranja.

Korak 3: Slučajno hodanje s brisanjem petlje

• Odaberite neposjećenu ćeliju i započnite slučajnu šetnju (kretanje u slučajnim smjerovima).
• Ako šetnja dođe do već posjećene ćelije, izbrišite sve petlje u putanji.
• 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 dok svaka ćelija ne bude dio labirinta.

Dodatno čitanje

Ako vam se svidio ovaj post, možda će vam se svidjeti i ovi prijedlozi:

• Kruskalov algoritam generator labirinta
• Generator labirinta Ellerovog algoritma
• Rekurzivni Backtracker Maze Generator