Kruskalov algoritam generator labirinta

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

Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.

Ovdje generirane karte labirinta 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 labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.

O Kruskalovom algoritmu

Kruskalov algoritam stvorio je Joseph Bernard Kruskal Jr., američki matematičar, statističar i računalni znanstvenik. Prvi put je opisao algoritam 1956. u svom radu "O najkraćem rasponu podstabla grafa i problemu trgovačkog putnika".

Algoritam je osmišljen za pronalaženje minimalnog razapinjućeg stabla (MST) grafa, osiguravajući da su svi vrhovi povezani s minimalnom mogućom ukupnom težinom bridova, a istovremeno izbjegavajući cikluse.

Kako Kruskalov algoritam funkcionira za generiranje labirinta

Korak 1: Inicijalizacija

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

Korak 2: Sortiranje zidova

• Promiješaj ili nasumično poredaj zidove. Ako se implementira kao pravi Kruskalov algoritam, sortiraj zidove nasumičnim redoslijedom (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 učinkovit način praćenja povezanih ćelija tijekom generiranja labirinta. 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:

• Rekurzivni Backtracker Maze Generator
• Generator labirinta Ellerovog algoritma
• Algoritam rastućeg stabla Generator labirinta