Wilson algoritam Lavirint Generator
Objavio: 19. mart 2025. 20:34:54 UTC
Generator lavirinta koji koristi Vilsonov algoritam za stvaranje savršenog lavirinta. Ovaj algoritam generiše sve moguće lavirinte date veličine sa istom verovatnoćom, tako da u teoriji može generisati lavirinte mnogih mešovitih rasporeda, ali kako postoji više mogućih lavirinta sa kraćim koridorima nego dužim, češće ćete ih videti.Wilson's Algorithm Maze Generator
Vilsonov algoritam je metoda slučajne šetnje izbrisana petljom koja generiše uniformna stabla za stvaranje lavirinta. To znači da su svi mogući lavirinti određene veličine podjednako verovatno da će biti generisani, što ga čini nepristrasnom tehnikom generisanja lavirinta. Vilsonov algoritam se može smatrati poboljšanom verzijom Aldous-Broder algoritma, jer generiše lavirint sa identičnim karakteristikama, ali radi mnogo brže, tako da se nisam potrudio da implementiram Aldous-Broder algoritam ovde.
Savršen lavirint je lavirint u kojem postoji tačno jedan put od bilo koje tačke u lavirintu do bilo koje druge tačke. To znači da ne možete završiti u krugovima, ali ćete često naići na ćorsokak, prisiljavajući vas da se okrenete i vratite.
Mape lavirinta generisane ovde uključuju podrazumevanu verziju bez ikakvih početnih i završnih pozicija, tako da možete sami da odlučite o njima: biće rešenje od bilo koje tačke u lavirintu do bilo koje druge tačke. Ako želite inspiraciju, možete da omogućite predloženu početnu i završnu poziciju - pa čak i da vidite rešenje između ova dva.
O Vilsonovom algoritmu
Vilsonov algoritam za generisanje uniformnih stablâ obuhvatajući nasumične zidove pomoću izbrisane petlje stvorio je Dejvid Brus Vilson.
Vilson je prvi put predstavio ovaj algoritam 1996. godine dok je istraživao nasumična stabla obuhvata i Markovljeve lance u teoriji verovatnoće. Iako je njegov rad bio prvenstveno u matematici i statističkoj fizici, algoritam je od tada široko usvojen za generisanje labirinta zbog svoje sposobnosti da proizvodi savršeno uniformne labirinte.
Kako Vilsonov algoritam funkcioniše za generisanje labirinata
Vilsonov algoritam osigurava da finalni labirint bude potpuno povezan bez ikakvih petlji tako što iterativno pravi staze od neposećenih ćelija koristeći nasumične šetnje.
Korak 1: Inicijalizacija
- Počnite sa mrežom popunjenom zidovima.
- Definišite listu svih mogućih prolaznih ćelija.
Korak 2: Izbor nasumične početne ćelije
- Odaberite bilo koju nasumičnu ćeliju i označite je kao posećenu. Ovo će služiti kao početna tačka labirinta tokom generacije.
Korak 3: Nasumična šetnja sa brisanjem petlji
- Odaberite neposećenu ćeliju i započnite nasumičnu šetnju (krećući se u nasumičnim pravcima).
- Ako šetnja dosegne već posećenu ćeliju, obrišite sve petlje na putu.
- Kada šetnja poveže sa posećenom regijom, označite sve ćelije na putu kao posećene.
Korak 4: Ponoviti dok sve ćelije nisu posećene:
- Nastavite sa selektovanjem neposećenih ćelija i obavljanjem nasumičnih šetnji dok svaka ćelija ne postane deo labirinta.