Kruskalov algoritam generator labirinta

Kruskalov algoritam je minimalni algoritam razapinjućeg stabla koji se može prilagoditi za generiranje labirinta. Posebno je učinkovit za stvaranje savršenih labirinata. Alternativa Kruskalovom algoritmu je Primov algoritam, koji je također minimalni algoritam razapinjućeg stabla, ali budući da generiraju identične labirinte i 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 informatičar. Prvi put je opisao algoritam 1956. u svom radu "O najkraćem razapetom podstablu grafa i problemu trgovačkog putnika".

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

Kako Kruskalov algoritam radi za stvaranje labirinta

Korak 1: Inicijalizacija

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

Korak 2: Razvrstajte zidove

• Pomiješajte ili nasumično rasporedite zidove. Ako ga implementirate kao pravi Kruskalov algoritam, sortirajte zidove nasumičnim redoslijedom (budući da generiranje labirinta ne zahtijeva težine).

Korak 3: Obradite zidove

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

Korak 4: Nastavite do završetka

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

Budući da se Kruskalov algoritam oslanja na spajanje skupova, može se optimizirati pomoću algoritma Union-Find, koji pruža učinkovit način praćenja povezanih stanica tijekom generiranja labirinta. Ovdje možete vidjeti moju PHP implementaciju algoritma Union-Find: Dizjunktni skup (Algoritam za pronalaženje unije) u PHP-u