Kruskalov algoritam Generator labirinta

Kruskalov algoritam je algoritam minimalnog razapinjućeg stabla koji se može prilagoditi za generiranje lavirinata. Posebno je efikasan za kreiranje savršenih lavirinata. Alternativa Kruskalovom algoritmu je Primov algoritam, koji je također algoritam minimalnog razapinjućeg stabla, ali budući da generiraju identične lavirinte, a Kruskalov radi brže, nisam se trudio implementirati Primov algoritam.

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

Kruskalov algoritam je kreirao Joseph Bernard Kruskal Jr., američki matematičar, statističar i informatičar. 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 razapinjuće stablo (MST) grafa, osiguravajući da su svi vrhovi povezani s minimalnom mogućom ukupnom težinom ivica, izbjegavajući pritom cikluse.

Kako Kruskalov algoritam funkcioniše za generisanje lavirinta

Korak 1: Inicijalizacija

• Tretirajte svaku ćeliju u lavirintu kao zaseban skup (jedinstvenu komponentu).
• Navedite sve zidove između susjednih ćelija kao potencijalne ivice.

Korak 2: Sortiranje zidova

• Promiješaj ili nasumično poredaj zidove. Ako se implementira kao pravi Kruskalov algoritam, sortiraj zidove nasumično (budući da generiranje labirinta ne zahtijeva težine).

Korak 3: Obrada zidova

• Ponavljajte kroz izmiješane zidove.
• Ako dvije ćelije odvojene zidom pripadaju različitim skupovima (tj. još nisu povezane u labirintu), uklonite zid i spojite skupove.
• Ako su već u istom setu, preskočite zid (kako biste izbjegli cikluse).

Korak 4: Nastavite do završetka

• Ponavljajte ovaj postupak dok se sve ćelije ne povežu, formirajući jedno razapinjuće stablo.
• Na kraju, svaka ćelija je povezana s ostalima bez petlji ili izoliranih dijelova.

Budući da se Kruskalov algoritam oslanja na spajanje skupova, može se optimizirati korištenjem Union-Find algoritma, koji pruža efikasan način praćenja povezanih ćelija tokom generiranja lavirinta. Moju PHP implementaciju Union-Find algoritma možete vidjeti ovdje: Link

Dodatno čitanje

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

• Generator labirinta za lov i ubijanje
• Rekurzivni Backtracker Maze Generator
• Wilsonov algoritam Generator labirinta