Kruskal algoritmus labirintus generátora
Megjelent: 2025. február 16. 17:57:34 UTC
Labirintusgenerátor Kruskal algoritmusával tökéletes labirintus létrehozásához. Ez az algoritmus általában közepes hosszúságú folyosókkal és sok zsákutcával rendelkező labirintusokat hoz létre, valamint egy meglehetősen egyenes megoldást.Kruskal's Algorithm Maze Generator
A Kruskal-féle algoritmus egy minimális feszítőfa-algoritmus, amely adaptálható labirintus generálására. Különösen hatékony tökéletes labirintusok létrehozásához. A Kruskal-algoritmus alternatívája a Prim-algoritmus, amely egyben egy minimális fedőfa-algoritmus is, de mivel azonos labirintusokat generálnak, és a Kruskal-féle gyorsabban fut, nem foglalkoztam a Prim-algoritmussal.
A tökéletes labirintus olyan labirintus, amelyben a labirintus bármely pontjából pontosan egy út vezet bármely más pontba. Ez azt jelenti, hogy a végén nem járhatsz körbe-körbe, de gyakran fogsz zsákutcába jutni, ami arra kényszerít, hogy megfordulj és visszamenj.
Az itt generált labirintustérképek tartalmaznak egy alapértelmezett verziót kezdő és végpontok nélkül, így ezeket te magad döntheted el: a labirintus bármely pontjából bármelyik másik pontba el lehet jutni. Ha inspirációra vágysz, engedélyezhetsz egy javasolt kezdő- és célpozíciót - és még a kettő közötti megoldást is láthatod.
A Kruskal-algoritmusról
Kruskal algoritmusát Joseph Bernard Kruskal, Jr. amerikai matematikus, statisztikus és informatikus készítette. Az algoritmust először 1956-ban írta le "A gráf legrövidebb fedőfájáról és az utazó kereskedő problémájáról" című tanulmányában.
Az algoritmust úgy tervezték, hogy megtalálja a gráf minimális feszítőfáját (MST), biztosítva, hogy minden csúcs a lehető legkisebb teljes élsúllyal legyen összekötve, miközben elkerüli a ciklusokat.
Hogyan működik a Kruskal-algoritmus a labirintusgeneráláshoz
1. lépés: Inicializálja
- A labirintus minden egyes sejtjét külön készletként kezelje (egyedi komponensként).
- Sorolja fel a szomszédos cellák közötti összes falat potenciális élként.
2. lépés: A falak rendezése
- Keverje meg vagy rendelje meg véletlenszerűen a falakat. Ha valódi Kruskal-algoritmusként valósítja meg, rendezze a falakat véletlenszerű sorrendbe (mivel a labirintus generálása nem igényel súlyokat).
3. lépés: A falak feldolgozása
- Iterálj át a megkevert falakon.
- Ha a fal által felosztott két cella különböző halmazokhoz tartozik (azaz még nem kapcsolódnak össze a labirintusban), távolítsa el a falat, és egyesítse a halmazokat.
- Ha már ugyanabban a készletben vannak, hagyja ki a falat (a ciklusok elkerülése érdekében).
4. lépés: Folytassa a befejezésig
- Ismételje meg ezt a folyamatot, amíg az összes cella össze nem kapcsolódik, és egyetlen átívelő fát alkot.
- A végén minden cella hurkok vagy elszigetelt szakaszok nélkül kapcsolódik a többihez.
Mivel a Kruskal algoritmusa halmazok egyesítésére támaszkodik, az Union-Find algoritmussal optimalizálható, amely hatékony módot biztosít az összekapcsolt cellák nyomon követésére a labirintus generálása során. Az Union-Find algoritmus PHP megvalósítását itt tekintheti meg: Disjunkt Set (Union-Find Algorithm) PHP-ben