Kruskalov algoritam Lavirint Generator

Kruskalov algoritam je algoritam minimalnog stabla koji se može prilagoditi za generisanje lavirinta. Posebno je efikasan za stvaranje savršenih lavirinta. Alternativa Kruskalovom algoritmu je Primov algoritam, koji je takođe algoritam minimalnog obuhvatnog stabla, ali pošto oni generišu identične lavirinte i Kruskal radi brže, nisam se potrudio da implementiram Prim-ov.

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 Kruskalovom algoritmu

Kruskalov algoritam je stvorio Džozef Bernard Kruskal mlađi, američki matematičar, statističar i računar. Prvi put je opisao algoritam 1956. godine u svom radu "O najkraćem obuhvatajućem podstablu grafa i problemu putujućeg trgovca."

Algoritam je dizajniran da pronađe minimalno obuhvatajuće stablo (MST) grafa, osiguravajući da su svi čvorovi povezani sa minimalnom mogućom ukupnom težinom ivica, izbegavajući cikluse.

Kako Kruskalov algoritam funkcioniše za generisanje lavirinta

Korak 1: Inicijalizacija

• Tretirajte svaki ćeliju u lavirintu kao poseban skup (jedinstvena komponenta).
• Nabrojte sve zidove između susednih ćelija kao potencijalne ivice.

Korak 2: Sortirajte zidove

• Promešajte ili nasumično poređajte zidove. Ako ga implementirate kao pravi Kruskalov algoritam, sortirajte zidove u nasumičnom redosledu (pošto generisanje lavirinta ne zahteva težine).

Korak 3: Obrada zidova

• Prolazite kroz pomešane zidove.
• Ako dve ćelije podeljene zidom pripadaju različitim skupovima (tj. još uvek nisu povezane u lavirintu), uklonite zid i spojite skupove.
• Ako su već u istom skupu, preskočite zid (da biste izbegli cikluse).

Korak 4: Nastavite dok se ne završi

• Ponovite ovaj proces dok sve ćelije ne budu povezane, formirajući jedno obuhvatajuće stablo.
• Na kraju, svaka ćelija je povezana sa ostalim bez petlji ili izolovanih sekcija.

Pošto Kruskalov algoritam zavisi od spajanja skupova, može se optimizovati korišćenjem Union-Find algoritma, koji pruža efikasan način praćenja povezanih ćelija tokom generisanja lavirinta. Možete videti moju PHP implementaciju Union-Find algoritma ovde: Disjoint skup (algoritam za pronalaženje unije) u PHP-u