Kruskalův Algorithm Maze Generator

Kruskalův algoritmus je algoritmus minimální kostry, který lze upravit pro generování bludišť. Je obzvláště efektivní pro vytváření dokonalých bludišť. Alternativou ke Kruskalovu algoritmu je Primův algoritmus, který je také algoritmem minimální kostry, ale protože generují identická bludiště a Kruskalův algoritmus běží rychleji, neobtěžoval jsem se implementovat Primův algoritmus.

Dokonalé bludiště je bludiště, ve kterém existuje přesně jedna cesta z kteréhokoli bodu bludiště do kteréhokoli jiného bodu. To znamená, že nemůžete skončit v kruhu, ale často narazíte na slepé uličky, které vás donutí se otočit a vrátit se zpět.

Zde vygenerované mapy bludiště obsahují výchozí verzi bez počátečních a cílových pozic, takže si je můžete určit sami: z jakéhokoli bodu v bludišti do jakéhokoli jiného bodu existuje řešení. Pokud se chcete inspirovat, můžete zapnout navrhovanou startovní a cílovou pozici - a dokonce si prohlédnout řešení mezi nimi.

O Kruskalově algoritmu

Kruskalův algoritmus vytvořil Joseph Bernard Kruskal Jr., americký matematik, statistik a informatik. Poprvé jej popsal v roce 1956 ve svém článku „O nejkratším podstromu grafu a problému obchodního cestujícího“.

Algoritmus je navržen tak, aby našel minimální kostru (MST) grafu a zajistil, že všechny vrcholy jsou propojeny s minimální možnou celkovou vahou hran a zároveň se vyhnul cyklům.

Jak Kruskalův algoritmus funguje pro generování bludiště

Krok 1: Inicializace

• S každou buňkou v bludišti zacházejte jako se samostatnou sadou (jedinečnou komponentou).
• Vypište všechny stěny mezi sousedními buňkami jako potenciální hrany.

Krok 2: Seřazení stěn

• Promíchejte nebo náhodně uspořádejte stěny. Pokud to implementujete jako skutečný Kruskalův algoritmus, seřaďte stěny v náhodném pořadí (protože generování bludiště nevyžaduje váhy).

Krok 3: Zpracování stěn

• Projděte si zamíchané zdi.
• Pokud dvě buňky oddělené zdí patří do různých množin (tj. ještě nejsou v bludišti propojeny), odstraňte zeď a množiny sloučte.
• Pokud jsou již ve stejné sadě, zeď přeskočte (abyste se vyhnuli cyklům).

Krok 4: Pokračujte až do dokončení

• Tento postup opakujte, dokud nebudou všechny buňky propojeny a nevytvoří jeden kostrový strom.
• Nakonec je každá buňka propojena s ostatními bez smyček nebo izolovaných úseků.

Protože Kruskalův algoritmus spoléhá na slučování množin, lze jej optimalizovat pomocí algoritmu Union-Find, který poskytuje efektivní způsob sledování propojených buněk během generování bludiště. Svou implementaci algoritmu Union-Find v PHP si můžete prohlédnout zde: Odkaz

Další čtení

Pokud se vám tento příspěvek líbil, mohly by se vám líbit i tyto návrhy:

• Generátor lovu a zabíjení bludiště
• Rostoucí strom Algoritmus bludiště generátor
• Wilsonův Algorithm Maze Generator