Kruskal algoritmus labirintus generátora

Kruskal algoritmusa egy minimális feszítőfa algoritmus, amely labirintusgenerálásra adaptálható. Különösen hatékony tökéletes labirintusok létrehozására. Kruskal algoritmusának alternatívája a Prim algoritmusa, amely szintén egy minimális feszítőfa algoritmus, de mivel azonos labirintusokat generálnak, és Kruskal algoritmusa gyorsabban fut, nem fáradtam a Prim algoritmusának implementálásával.

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.

Kruskal algoritmusáról

Kruskal algoritmusát Joseph Bernard Kruskal Jr., amerikai matematikus, statisztikus és informatikus alkotta meg. Az algoritmust először 1956-ban írta le „A gráf legrövidebb feszítőfájáról és az utazó ügynök problémájáról” című cikkében.

Az algoritmus célja, hogy megtalálja egy gráf minimális feszítőfáját (MST), biztosítva, hogy minden csúcs a lehető legkisebb élsúllyal legyen összekötve, miközben elkerüli a ciklusokat.

Hogyan működik Kruskal algoritmusa a labirintusgenerálásban?

1. lépés: Inicializálás

• A labirintusban minden egyes cellát különálló halmazként (egyedi komponensként) kezelj.
• Sorold fel a szomszédos cellák közötti összes falat potenciális élként.

2. lépés: Falak rendezése

• Keverd meg vagy rendezd véletlenszerűen a falakat. Ha valódi Kruskal-algoritmusként valósítod meg, rendezd a falakat véletlenszerű sorrendbe (mivel a labirintus generálása nem igényel súlyokat).

3. lépés: Folyamatfalak

• Ismételd át magad a megkeseredett falakon.
• Ha a fallal elválasztott két cella különböző halmazokhoz tartozik (azaz még nincsenek összekapcsolva a labirintusban), akkor távolítsd el a falat és vond össze a halmazokat.
• Ha már ugyanabban a halmazban vannak, akkor hagyd ki a falat (a ciklusok elkerülése érdekében).

4. lépés: Folytassa a befejezésig

• Ismételjük ezt a folyamatot, amíg az összes cella össze nem kapcsolódik, egyetlen feszítőfát alkotva.
• Végül minden cella hurkok vagy elszigetelt szakaszok nélkül kapcsolódik a többihez.

Mivel Kruskal algoritmusa halmazok egyesítésén alapul, optimalizálható az Union-Find algoritmussal, amely hatékony módszert kínál az összekapcsolt cellák nyomon követésére labirintusgenerálás során. Az Union-Find algoritmus PHP implementációját itt tekintheti meg: Link

További olvasmányok

Ha tetszett ez a bejegyzés, akkor ezek a javaslatok is érdekelhetik:

• Rekurzív Backtracker labirintus generátor
• Wilson algoritmus labirintus generátor
• Eller algoritmus labirintusgenerátora