Náhodná procházka

Algoritmus náhodné procházky (anglicky random walk) patří mezi nejjednodušší algoritmy pro generování IFS koláží. Jeho výhodou je jednoduchost a malá paměťová náročnost. Mezi jeho nevýhody patří nutnost generování velkého množství bodů pro reprezentaci fraktálu. Některé části fraktálu se generují vícekrát, zatímco některé jen jednou. Generování IFS fraktálu se nastartuje tak, že se zvolí náhodný bod v rovině. Poloha počátečního bodu nemá na výslednou koláž žádný větší vliv, nemusí tedy nutně ležet uvnitř atraktoru IFS. Poté náhodně vybereme nějakou transformaci W_i. Při výběru transformace musíme přihlédnout k tomu, aby počet použití dané transformace odpovídal její pravděpodobnosti, jinak se bude výsledná koláž generovat neúměrně dlouho. Poté co máme vybranou nějakou transformaci, aplikujeme ji na daný bod. Souřadnice tohoto bodu se změní (bod se transformuje). Na tento nový bod potom iterativně aplikujeme další náhodně vybranou transformaci. Takto pokračujeme tak dlouho, dokud nedosáhneme zadaného maximálního počtu iterací. Jelikož první bod nemusí nutně ležet v atraktoru IFS, je nutné několik prvních iterací počátečního bodu nezobrazovat, protože první iterované body neleží v atraktoru IFS. Z teorie IFS systémů, kterou jsme uvedli v předchozích kapitolách, vyplývá, že se systém automaticky dostane po několika iteracích do atraktoru IFS, z něhož se již nemůže dostat. Při generování IFS koláže tímto algoritmem vidíme, že se obrázek jakoby vynořuje z mlhy. Kvalitu výsledného obrázku lze ovlivnit zadáním maximálního počtu iterací, které se mají provést. Malý počet iterací způsobuje, že je obrázek složený z malého počtu bodů a tím pádem je hůře viditelný. Příliš velký počet iterací naopak způsobuje dlouhou dobu generování výsledné IFS koláže. Pro první náhled na IFS koláž vystačíme s 1 000 iteracemi, ale pro generování obrázků, které se mají tisknout ve vysokém rozlišení, je zapotřebí 100 000 až 1 000 000 iterací. Doba generování se u tohoto počtu iterací pohybuje řádově v desítkách sekund. Počátečních iterací (tedy iterací, které se nevykreslují) stačí zadat několik desítek. Po tomto počtu iterací se bod nachází uvnitř atraktoru IFS. Počáteční bod se většinou volí tak, aby ležel v počátku. Jak již víme, na jeho poloze výsledný tvar IFS koláže nezávisí.