Labirintų generavimas

                Vienas gan įdomus uždavinys yra labirintų sprendimas – pradedant įėjimu pasiekti labirinto pabaigą. Kompiuteriai tai atlieka itin greitai, žmogui tektų kaip reikiant paprakaituoti, jei duotume sudėtingesnį atvejį. Labirintų sprendimui naudojamas paieškos į gylį metodas – breadth first search arba tiesiog BFS. Jei teko bent kiek domėtis, tai šis metodas veikia labai paprastai ir primena Flood fill metodą (tą patį kurį naudoja Photoshop, MS Paint, Gimp etc.) figūrų užpildymui tik šiek tiek modifikuotą. 

                Kitas uždavinys – labirintus ne spręsti, bet juos generuoti! Taip! Pasirodo, kad generuoti labirintą nėra taip paprasta, kaip gali pasirodyti. Šiame straipsniuke pabandysiu apžvelgti pamąstymus, kaip tai būtų galima atlikti ir galiausiai užbaigsime su realizacija. Jokiu būdu nesistengsiu sugalvoti kažko optimalaus ir minimalaus, o tiesiog parodyti, kad generavimo idėja irgi gali būti įdomi ir įtraukianti.





             Pirmiausia siekiant generuoti labirintą turbūt pirmoji šovusi mintis, kaip visada - jog reikia darbą padalinti į keletą dalių – supaprastinti uždavinį. Kadangi norime sugeneruoti tikrą labirintą, kad jį būtų galima įveikti iš tikrųjų, tai būtina surasti tik VIENĄ vienintelį atsitiktinį kelią nuo pradžios iki pabaigos, o paskui papildyti kelią įvairiais uždarais ir klaidinančiais koridoriais – nesgi kaip tik to ir reikia tikram labirintui.

               

                Taigi, naivi idėja:

1. Sugeneruoti atsitiktinį kelią jungiantį pradžią ir pabaigą

2. Sukurti papildomus klaidinančius koridorius

                Taigi, šiam uždaviniui neužteks panaudoti vieno kokio paieškos į gylį metodo, kad sudarytume labirintą, o teks paimprovizuoti dar su 2-a dalimi.

                Kelio generavimui puikiai tiks paminėtas paieškos į gylį metodas (depth first search). Žinodami labirinto dydį(matricą) bei pradžios ir pabaigos koordinates nesunkiai surandame kelią tarp šių dviejų taškų. Atrodo paprasta. Bet palaukit! Taigi surastas kelias bus tiesus! Taip, tikrai, siekiant, kad labirintas būtų įvairesnės formos, su pasisukimais ir pan., būtina įnešti kažkokios randomizacijos. Renkantis sekantį paieškos į gylį ėjimą galima jį pasirinkti atsitiktinai. Kol kas viskas puiku, bet tada susiduriame su kita problema – atskirų dalių kelio blokeliai negali eiti vienas šalia kito, todėl tenka tikrinti, ar blokelis matricoje gali būti panaudotas keliui. Vieno blokelio tarpas tarp kelio segmentų privalomas! Įgyvendinus šias idėja gavome tikrai neblogą rezultatą:

Kelio generavimas labirinte nuo pradžios iki galo.

                Na, turint kelią belieka pasunkinti gyvenimą ir labirintą papildyti klaidinančiais ir niekur nevedančiais koridoriais. Pats paprasčiausias būdas būtų pabandyti iš kiekvieno kelio blokelio pabandyti sugeneruoti koridorių atšakas – randomizuotas pasirinkimas čia tikrai pagelbės. Taip pat reikia tikrinti ir atstumus tarp gretimų blokelių ir kaip visada išlaikyti minimalų 1 blokelio atstumą tarp gretimų segmentų.

                Generuojant koridorius gali atsitikti taip, kad iš pradinio blokelio pradėtas generuoti koridorius užpildys visą likusią labirinto dalį (kaip man pradžioje ir nutiko). Tada tenka riboti labirinto koridoriaus ilgį(fiksuoti tam tikrą skaičių). Taip užtikrinama, kad bent keletas koridorių tikrai bus sukurta. Realizavus visas šias idėjas gautas neblogas labirintų generatorius, nors visada yra kur tobulinti ir optimizuoti. Labirinto pavyzdys pateikiamas toliau:

Sugeneruotas labirintas ir kelias iki finišo.

                Labirintų generavimo idėjomis jau nuo seno domimasi pasaulyje. Wikipedija duoda tikrai optimalesnių metodų jiems sukurti, tačiau pačiam paeksperimentuoti buvo pakankamai smagu. Labirintų idėją puikiai galima praplėsti 3D ar paveikslėlių viduje esantiems labirintams generuoti. 
               Beje, apie pačią realizaciją – kodas parašytas Python kalba pasinaudojus internete surastu SVG paveikslėlių generavimo skriptuku. Taip manau rezultatai matomi žymiai vaizdžiau. Pasirodo, SVG formatas tikrai neblogas dalykas – be to vektorinis, kas man labai patinka. Pilnas kodas toliau.    

maze.py failas:

svg.py failas: