Kruskalův Algorithm Maze Generator

Kruskalův algoritmus je minimální algoritmus spanning tree, který lze upravit pro generování bludiště. Je zvláště účinný pro vytváření dokonalých bludišť. Alternativou ke Kruskalovu algoritmu je Primův algoritmus, který je také minimálním algoritmem spanning tree, ale protože generuje identická bludiště a Kruskalův běh rychleji, neobtěžoval jsem se implementací Primova.

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 počítačový vědec. Algoritmus poprvé popsal v roce 1956 ve svém článku „On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem“.

Algoritmus je navržen tak, aby nalezl minimální kostru (MST) grafu, což zajišťuje, že všechny vrcholy jsou spojeny s minimální možnou celkovou hmotností hrany a zároveň se vyhýbá cyklům.

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

Krok 1: Inicializujte

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

Krok 2: Roztřiďte stěny

• Zamíchejte nebo náhodně objednejte stěny. Pokud jej 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: Zpracujte stěny

• Iterujte přes zamíchané stěny.
• Pokud dvě buňky rozdělené stěnou patří do různých sad (tj. ještě nejsou spojeny v bludišti), odstraňte stěnu a slučte sady.
• Pokud jsou již ve stejné sadě, přeskočte zeď (abyste se vyhnuli cyklům).

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

• Tento postup opakujte, dokud nejsou všechny buňky propojeny a nevytvoří jeden kostru.
• Na konci je každá buňka spojena s ostatními bez smyček nebo izolovaných sekcí.

Protože Kruskalův algoritmus spoléhá na slučování množin, lze jej optimalizovat pomocí algoritmu Union-Find, který poskytuje účinný způsob sledování spojených buněk během generování bludiště. Moji implementaci algoritmu Union-Find v PHP můžete vidět zde: Disjoint Set (Union-Find Algorithm) v PHP