Wilson algoritmus labirintus generátor

Wilson algoritmusa egy ciklustörléses véletlenszerű bolyongásos módszer, amely egyenletes feszítőfákat generál labirintusok létrehozásához. Ez azt jelenti, hogy egy adott méretű összes lehetséges labirintus azonos valószínűséggel generálódik, így egy elfogulatlan labirintusgenerálási technikát alkalmaz. Wilson algoritmusa az Aldous-Broder algoritmus továbbfejlesztett változatának tekinthető, mivel azonos jellemzőkkel rendelkező labirintusokat generál, de sokkal gyorsabban fut, ezért itt nem fáradtam az Aldous-Broder algoritmus 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.

Wilson algoritmusáról

Wilson algoritmusát egyenletes feszítőfák létrehozására huroktörölt véletlenszerű fal segítségével David Bruce Wilson alkotta meg.

Wilson eredetileg 1996-ban vezette be ezt az algoritmust, miközben a valószínűségszámításban a véletlenszerű feszítőfákat és a Markov-láncokat kutatta. Bár munkássága elsősorban a matematika és a statisztikus fizika területén zajlott, az algoritmust azóta széles körben alkalmazzák labirintusgenerálásra, mivel tökéletesen egyenletes labirintusokat tud létrehozni.

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

Wilson algoritmusa biztosítja, hogy a végső labirintus teljesen összefüggő legyen hurkok nélkül azáltal, hogy iteratívan farag ösvényeket a fel nem látogatott cellákból véletlenszerű bolyongások segítségével.

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

• Kezdj egy falakkal kitöltött ráccsal.
• Definiáljon egy listát az összes lehetséges áthaladó sejtről.

2. lépés: Válasszon egy véletlenszerű kezdőcellát

• Válassz ki egy tetszőleges cellát, és jelöld meg látogatottként. Ez szolgál a labirintus kiindulópontjaként a generálás során.

3. lépés: Véletlenszerű séta huroktörléssel

• Válassz ki egy még nem látogatott cellát, és kezdj el egy véletlenszerű sétát (véletlenszerű irányokba mozogva).
• Ha a séta egy már meglátogatott cellához ér, törölj minden hurkot az útvonalból.
• Miután a séta eléri a meglátogatott régiót, jelölje meg az útvonal összes celláját meglátogatottként.

4. lépés: Ismételje meg, amíg az összes cellát fel nem kereste:

• Folytasd a fel nem keresett cellák kiválasztását és a véletlenszerű séták végrehajtását, amíg minden cella a labirintus részévé nem válik.

További olvasmányok

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

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