Generator labirinta Kruskalovega algoritma

Kruskalov algoritem je algoritem minimalnega razteznega drevesa, ki ga je mogoče prilagoditi za generiranje labirintov. Še posebej je učinkovit za ustvarjanje popolnih labirintov. Alternativa Kruskalovemu algoritmu je Primov algoritem, ki je prav tako algoritem minimalnega razteznega drevesa, vendar ker generirata enake labirinte in Kruskalov teče hitreje, se Primovega nisem trudil implementirati.

Popoln labirint je labirint, v katerem obstaja natanko ena pot od katere koli točke v labirintu do katere koli druge točke. To pomeni, da se ne morete vrteti v krogu, vendar boste pogosto naleteli na slepe ulice, zaradi česar se boste morali obrniti in vrniti nazaj.

Tukaj ustvarjeni zemljevidi labirintov vključujejo privzeto različico brez začetnih in končnih položajev, tako da jih lahko določite sami: iz katere koli točke v labirintu do katere koli druge točke obstaja rešitev. Če želite navdih, lahko omogočite predlagana začetni in končni položaj - in si celo ogledate rešitev med njima.

O Kruskalovem algoritmu

Kruskalov algoritem je ustvaril Joseph Bernard Kruskal ml., ameriški matematik, statistik in računalniški znanstvenik. Algoritem je prvič opisal leta 1956 v svojem članku "O najkrajšem razteznem poddrevesu grafa in problemu potujočega prodajalca".

Algoritem je zasnovan tako, da poišče minimalno raztezno drevo (MST) grafa, pri čemer zagotovi, da so vsa vozlišča povezana z najmanjšo možno skupno težo robov, hkrati pa se izogne ciklom.

Kako deluje Kruskalov algoritem za ustvarjanje labirinta

1. korak: Inicializacija

• Vsako celico v labirintu obravnavajte kot ločen niz (edinstveno komponento).
• Kot potencialne robove navedite vse stene med sosednjimi celicami.

2. korak: Razvrstite stene

• Stene premešajte ali naključno razvrstite. Če ga izvajate kot pravi Kruskalov algoritem, razvrstite stene v naključnem vrstnem redu (ker generiranje labirinta ne zahteva uteži).

3. korak: Obdelava sten

• Ponavljajte skozi premešane stene.
• Če dve celici, ki ju ločuje stena, pripadata različnim množicam (tj. še nista povezani v labirintu), odstranite steno in združite množice.
• Če so že v istem nizu, preskočite steno (da se izognete ciklom).

4. korak: Nadaljujte do zaključka

• Ta postopek ponavljajte, dokler niso vse celice povezane in tvorijo eno samo raztezno drevo.
• Na koncu je vsaka celica povezana z drugimi brez zank ali izoliranih odsekov.

Ker Kruskalov algoritem temelji na združevanju množic, ga je mogoče optimizirati z uporabo algoritma Union-Find, ki zagotavlja učinkovit način sledenja povezanim celicam med generiranjem labirinta. Mojo implementacijo algoritma Union-Find v PHP si lahko ogledate tukaj: Povezava

Nadaljnje branje

Če vam je bila ta objava všeč, vam bodo morda všeč tudi ti predlogi:

• Generator labirinta Ellerjevega algoritma
• Generator labirinta Wilsonovega algoritma
• Generator Labirinta Lov in Ubij