Wilsonov algoritam Generator labirinta

Wilsonov algoritam je metoda slučajnog hoda s brisanjem petlji koja generira uniformna obuhvatna stabla za kreiranje lavirinata. To znači da je podjednako vjerovatno da će se generirati svi mogući lavirinti date veličine, što ga čini nepristrasnom tehnikom generiranja lavirinata. Wilsonov algoritam se može smatrati poboljšanom verzijom Aldous-Broder algoritma, jer generira lavirinte 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 tačno jedan put od bilo koje tačke u labirintu do bilo koje druge tačke. To znači da ne možete završiti u krugu, ali ćete često nailaziti na slijepe ulice, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta koje se ovdje generiraju 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 lavirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženi početni i ciljni položaj - pa čak i vidjeti rješenje između njih.

O Wilsonovom algoritmu

Wilsonov algoritam za generiranje uniformnih razapinjućih stabala korištenjem slučajnog zida s obrisanom petljom kreirao je David Bruce Wilson.

Wilson je prvobitno predstavio ovaj algoritam 1996. godine dok je istraživao slučajna razapinjuća stabla i Markovljeve lance u teoriji vjerovatnoće. Iako je njegov rad prvenstveno bio u matematici i statističkoj fizici, algoritam je od tada široko prihvaćen za generisanje lavirinata zbog svoje sposobnosti da proizvede savršeno ujednačene lavirinte.

Kako Wilsonov algoritam funkcionira za generiranje labirinta

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

Korak 1: Inicijalizacija

• Počnite s mrežom ispunjenom zidovima.
• Definišite listu 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. Ovo služi kao početna tačka lavirinta tokom generiranja.

Korak 3: Slučajno hodanje s brisanjem petlje

• Odaberite neposjećenu ćeliju i započnite nasumičnu šetnju (kretanje u nasumičnim smjerovima).
• Ako šetnja stigne do već posjećene ćelije, obrišite sve petlje u putanji.
• Kada se šetnja poveže sa posjećenom regijom, označite sve ćelije na putanji 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 ćelija ne bude dio labirinta.

Dodatno čitanje

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

• Generator Labirinta Algoritma Eller
• Rekurzivni Backtracker Maze Generator
• Kruskalov algoritam Generator labirinta