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.
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: 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 :)
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.
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.
8 komentárov:
Stavím sa o pivo, že to budú L-systémy.
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.)
Nahodne generovany strom na danej mriezke vrcholov? 2x stvorcova, raz trojuholnikova?
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 :)
Ok, tak kedy ideme na to pivo?
:-) 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.
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
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.
Zverejnenie komentára