Wilsonov algoritam Generator labirinta
Objavljeno: 16. februar 2025. u 19:37:52 UTC
Generator labirinta koristi Wilsonov algoritam za stvaranje savršenog labirinta. Ovaj algoritam generira sve moguće labirinte date veličine sa istom vjerovatnoćom, tako da u teoriji može generirati labirinte mnogih mješovitih rasporeda, ali kako postoji više mogućih labirinta sa kraćim hodnicima nego dužim, češće ćete ih vidjeti.Wilson's Algorithm Maze Generator
Wilsonov algoritam je metoda slučajnog hodanja koja generira jednolična stabla za stvaranje labirinta. To znači da su svi mogući labirinti određene veličine jednako vjerovatno da će biti generirani, što ga čini nepristrasnom tehnikom generiranja labirinta. Wilsonov algoritam se može smatrati poboljšanom verzijom Aldous-Broder algoritma, jer generira labirinte sa identičnim karakteristikama, ali radi mnogo brže, tako da se nisam potrudio 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 stabala pomoću slučajnog zida izbrisanog petlje kreirao je David Bruce Wilson.
Wilson je prvobitno predstavio ovaj algoritam 1996. godine dok je istraživao slučajna 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 generiranje labirinta zbog svoje sposobnosti da proizvede savršeno ujednačene labirinte.
Kako Wilsonov algoritam radi za stvaranje labirinta
Wilsonov algoritam osigurava da je konačni labirint u potpunosti povezan bez ikakvih petlji iterativnim rezbarenjem puteva iz neposjećenih ćelija koristeći nasumične šetnje.
Korak 1: Inicijalizirajte
- Počnite s mrežom ispunjenom zidovima.
- Definišite listu svih mogućih prolaznih ćelija.
Korak 2: Odaberite nasumičnu početnu ćeliju
- Odaberite bilo koju nasumičnu ćeliju i označite je kao posjećenu. Ovo služi kao polazna tačka labirinta tokom generacije.
Korak 3: Nasumična šetnja sa brisanjem petlje
- Odaberite neposjećenu ćeliju i započnite nasumičnu šetnju (krećući se u nasumičnim smjerovima).
- Ako šetnja dođe do već posjećene ćelije, izbrišite sve petlje na putu.
- Nakon što se šetnja poveže s posjećenom regijom, označite sve ćelije na stazi kao posjećene.
Korak 4: Ponavljajte dok se ne posjete sve ćelije:
- Nastavite birati neposjećene ćelije i izvoditi nasumične šetnje dok svaka ćelija ne bude dio labirinta.