Kruskalov algoritam Generator labirinta
Objavljeno: 16. februar 2025. u 18:05:56 UTC
Generator labirinta koristi Kruskalov algoritam za stvaranje savršenog labirinta. Ovaj algoritam ima tendenciju da stvori labirinte sa srednjom dužinom hodnika i mnogo slijepih ulica, kao i prilično ravno rješenje.Kruskal's Algorithm Maze Generator
Kruskalov algoritam je algoritam minimalnog stabla koji se može prilagoditi za generiranje labirinta. Posebno je efikasan za stvaranje savršenih labirinta. Alternativa Kruskalovom algoritmu je Primov algoritam, koji je također algoritam minimalnog rasponskog stabla, ali budući da generiraju identične labirinte i Kruskalov radi brže, nisam se potrudio implementirati Prim-ov.
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 računarski naučnik. Prvi put je opisao algoritam 1956. godine u svom radu "On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem".
Algoritam je dizajniran da pronađe minimalno stablo raspona (MST) grafa, osiguravajući da su svi vrhovi povezani sa minimalnom mogućom ukupnom težinom ruba uz izbjegavanje ciklusa.
Kako Kruskalov algoritam radi za stvaranje labirinta
Korak 1: Inicijalizirajte
- Tretirajte svaku ćeliju u labirintu kao zaseban skup (jedinstvena komponenta).
- Navedite sve zidove između susjednih ćelija kao potencijalne rubove.
Korak 2: Sortirajte zidove
- Promiješajte ili nasumično poredajte zidove. Ako ga implementirate kao pravi Kruskalov algoritam, sortirajte zidove slučajnim redoslijedom (jer generiranje labirinta ne zahtijeva težine).
Korak 3: Procesni zidovi
- Ponavljaj kroz promiješ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 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 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 algoritma Union-Find, koji pruža efikasan način za praćenje povezanih ćelija tokom generiranja labirinta. Možete vidjeti moju PHP implementaciju Union-Find algoritma ovdje: Disjoint skup (Union-Find algoritam) u PHP-u