Wilson algoritmus labirintus generátor
Megjelent: 2025. február 16. 19:31:54 UTC
Labirintusgenerátor Wilson algoritmusával tökéletes labirintus létrehozásához. Ez az algoritmus egy adott méretű összes lehetséges útvesztőt azonos valószínűséggel generál, így elméletileg sok vegyes elrendezésű útvesztőt is generálhat, de mivel több lehetséges útvesztő rövidebb, mint hosszabb, ezért gyakrabban látni fogja ezeket.Wilson's Algorithm Maze Generator
A Wilson-algoritmus egy huroktörlésű véletlenszerű sétamódszer, amely egységes fedőfákat generál a labirintus létrehozásához. Ez azt jelenti, hogy egy adott méretű összes lehetséges labirintus létrejön, így ez egy elfogulatlan labirintusgenerálási technika. A Wilson-féle algoritmus az Aldous-Broder algoritmus továbbfejlesztett változatának tekinthető, mivel azonos karakterisztikájú labirintusokat generál, de sokkal gyorsabban fut, így itt nem vettem a fáradságot 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.
A Wilson-algoritmusról
David Bruce Wilson készítette el Wilson algoritmusát, amely egy huroktörlésű véletlenszerű fal segítségével egyenletes feszülő fákat generál.
Wilson eredetileg 1996-ban vezette be ezt az algoritmust, miközben véletlenszerűen átívelő fákat és Markov-láncokat kutatott a valószínűségszámításban. Bár munkája elsősorban a matematikával és a statisztikai fizikával foglalkozott, az algoritmust azóta széles körben alkalmazzák labirintusgenerálásra, mivel képes tökéletesen egyenletes labirintusokat előállítani.
Hogyan működik a Wilson-algoritmus a labirintusgeneráláshoz
A Wilson-algoritmus biztosítja, hogy a végső labirintus hurkok nélkül teljesen össze legyen kötve azáltal, hogy a nem látogatott cellákból véletlenszerű séták segítségével iteratív útvonalakat farag ki.
1. lépés: Inicializálja
- Kezdje falakkal teli ráccsal.
- Adja meg az összes lehetséges áthaladási cella listáját.
2. lépés: Válasszon ki egy véletlenszerű kezdőcellát
- Válasszon ki egy véletlenszerű cellát, és jelölje 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álasszon ki egy nem látogatott cellát, és kezdjen el egy véletlenszerű sétát (véletlen irányban mozogva).
- Ha a séta elér egy már meglátogatott cellát, törölje az összes hurkot az útvonalból.
- Miután a séta csatlakozik a meglátogatott régióhoz, jelölje meg az útvonal összes celláját látogatottként.
4. lépés: Ismételje addig, amíg az összes sejtet meg nem látogatja :
- Folytassa a nem látogatott cellák kiválasztását és a véletlenszerű sétákat, amíg minden cella a labirintus része lesz.