Generator labirinta Kruskalovega algoritma

Kruskalov algoritem je minimalni algoritem vpetega drevesa, ki ga je mogoče prilagoditi za generiranje labirinta. Še posebej je učinkovit pri ustvarjanju popolnih labirintov. Alternativa Kruskalovemu algoritmu je Primov algoritem, ki je tudi minimalni algoritem vpetega drevesa, a ker ustvarjajo enake labirinte in Kruskalov teče hitreje, se nisem trudil implementirati Primovega.

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, mlajši, ameriški matematik, statistik in računalničar. Algoritem je prvič opisal leta 1956 v svojem članku "O najkrajšem vpetem poddrevesu grafa in problemu trgovskega potnika."

Algoritem je zasnovan tako, da najde minimalno vpeto drevo (MST) grafa, pri čemer zagotavlja, da so vse točke povezane z najmanjšo možno skupno težo robov, pri čemer se izogiba ciklom.

Kako deluje Kruskalov algoritem za ustvarjanje labirinta

1. korak: Inicializacija

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

2. korak: Razvrstite stene

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

3. korak: Obdelajte stene

• Ponavljajte skozi premešane stene.
• Če celici, ki ju deli stena, pripadata različnima nizoma (tj. še nista povezani v labirintu), odstranite steno in niza združite.
• Č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 vpeto drevo.
• Na koncu je vsaka celica povezana z drugimi brez zank ali izoliranih odsekov.

Ker Kruskalov algoritem temelji na združevanju nizov, ga je mogoče optimizirati z uporabo algoritma Union-Find, ki zagotavlja učinkovit način za sledenje povezanim celicam med ustvarjanjem labirinta. Tukaj si lahko ogledate mojo PHP implementacijo algoritma Union-Find: Disjointna množica (algoritem Union-Find) v PHP