21 februára 2008

Náhodné bludiská

Podarí sa Vám vymyslieť spôsob, akým je možné algoritmicky generovať náhodné bludiská? Môžete sa nechať inšpirovať nasledovnými obrázkami. Ak Vás "náhodné bludiská" zaujmú, prezradím Vám, akú metódu som použil ja.

8 komentárov:

johno povedal(a)...

Stavím sa o pivo, že to budú L-systémy.

Radoslav Harman povedal(a)...

Dobry tip, ale pivo by si prehral, pretoze L-systemy to nie su. Je ale pravda, ze tie bludiska mozu pripominat space-filling curves a tiez je velmi pravdepodobne, ze pomocou L-systemov by sa pekne bludiska naozaj dali vygenerovat. Mali vsak zrejme self-similar structure, co moje bludiska nemaju. Naviac, da sa v nich naozaj zabludit, na rozdiel od linearnych space-filling curves. :-)

To, co som pouzil, je ovela primitivnejsie ako L-systemy. Hint: Zobrazene bludiska obsahuju vela "slepych uliciek", ale pritom z kazdeho bodu sa da prejst do kazdeho ineho bodu prave jednou cestou (ak nepovolime navrat po tej istej ceste.)

Lev bez hrivy povedal(a)...

Nahodne generovany strom na danej mriezke vrcholov? 2x stvorcova, raz trojuholnikova?

Radoslav Harman povedal(a)...

Lev: Máš pravdu! Je to jednoducho náhodna kostra pravouhlej, alebo trojuholníkovej mriežky. Na generovanie náhodnej kostry grafu (anglický termín pre kostru grafu je krajší: spanning tree) existuje viac algoritmov; ja som však tieto bludiská dostal ako vedľajší produkt algoritmu na Euklidovskú minimálnu kostru aplikovaného na veľmi jemne perturbované body mriežky.

Mám v pláne sa v budúcnosti trochu viac pozabávať práve s Euklidovskými minimálnymi kostrami grafov. Ak sa k tomu dostanem, dám na blog nejaké ďalšie obrázky :)

johno povedal(a)...

Ok, tak kedy ideme na to pivo?

Radoslav Harman povedal(a)...

:-) Zastav sa u mna na M246 ked bude vonku 30°C. V kancelarii budem mat 50°C a pivo bude jedine, na co sa bude dat mysliet.

misof povedal(a)...

Celkom pekná metóda je aj náhodné prehľadávanie do hĺbky toho istého grafu (náhodné v zmysle "v každom vrchole náhodne zvolím, v akom poradí budem hrany z neho spracúvať"). Tam sa potom dá napríklad pohrať s váhami -- ak sa dá väčšia pravdepodobnosť možnosti "najskôr skús pokračovať smerom, ktorým si prišiel", dostaneme bludisko s dlhšími a rovnejšími chodbami.

Tu sú nejaké narýchlo zbúchané pokusy:
blud.html

Radoslav Harman povedal(a)...

misof: To, čo navrhuješ, sa zdá byť oveľa lepšie ako tá moja metóda (aj keď ja som tie náhodné bludiská dostal skôr ako vedľajši produkt pri zabávaní sa s algoritmami minimalnej kostry, ktoré sa používajú pri vizualizácii dát v metóde "multidimensional scaling"). Tvoja metóda generovania náhodných bludísk je rýchlejšia aj variabilnejšia; veľmi fajn.