Miklix

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.

Ova stranica je mašinski prevedena sa engleskog jezika kako bi bila dostupna što većem broju ljudi. Nažalost, mašinsko prevođenje još uvek nije usavršena tehnologija, tako da može doći do grešaka. Ako želite, možete pogledati originalnu englesku verziju ovde:

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.


Generišite novi lavirint








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.
Podeli na BlueskiPodeli na FejsbukuPodeli na LinkedInPodeli na TumblrPodeli na XPodeli na LinkedInPin na Pinterest

Mikkel Christensen

O autoru

Mikkel Christensen
Mikel je tvorac i vlasnik miklix.com. Ima preko 20 godina iskustva kao profesionalni kompjuterski programer / programer i trenutno je zaposlen sa punim radnim vremenom za veliku evropsku IT korporaciju. Kada ne bloguje, on provodi svoje slobodno vreme na širokom spektru interesovanja, hobija i aktivnosti, što se u određenoj meri može odraziti na različite teme koje se obrađuju na ovoj veb stranici.