Prírodou inšpirované algoritmy

Príklady L-Systémov

Kochova vločka - príklad fraktálu

Skôr než pristúpime k príkladom generovania fiktívnych rastlín, je vhodné objasniť niektoré kľúčové pojmy, uvedené už v úvode podkapitoly o L-systémoch. Fraktálom nazval matematik Benoit Mandelbrot geometrický útvar s týmito vlastnosťami :

• je sebepodobný,
• má neceločíselnú dimenziu,
• má síce na pohľad veľmi zložitý tvar, je ale generovaný jednoduchými pravidlami.

Sebapodobnosťou sa rozumie to, že nech daný útvar pozorujeme v akomkoľvek merítku, vykazuje stále rovnaký charakteristický tvar. Dimenzia D je v tomto prípade definovaná ako N = L^D, kde N je počet kópií pôvodného útvaru pri L-násobnom zväčšení lineárneho rozmeru, napr. štvorec má dimenziu 2 ( 4 = 2³ ) a kocka dimenziu 3 ( 8 = 2²).

Medzi najznámejšie fraktály patrí krivka - tzv. Kochova vločka, navrhnutá H. Kochom: každá úsečka je nahradená lomenou čiarou, ktorá vznikne zámenou prostrednej tretiny pôvodnej úsečky dvomi stranami rovnoramenného trojuholníka :

Axiom = F--F--F ( rovnoramenný trojuholník )
α = 60°
F → F+F--F+F

V náhradnej lomenej čiare sa pôvodná úsečka F vyskytuje štyrikrát, lineárne zväčšenie je trojnásobné, teda platí 4 = 3^D a dimenzia Kochovej vločky je D = 1.2618. Obvod vločky konverguje k nekonečnu (O = 3 * 4/3 * 4/3 * 4/3 * 4/3 ... ), ale jej ohraničená plocha má konečný obsah, menší ako obsah kružnice, opísanej pôvodnému trojuholníku.

Pomocou predchádzajúceho appletu nastáva generovanie Kochovej vločky. Pravidlá, pomocou ktorého prebieha generovanie, boli spomenuté vyššie. Prvé tri iterácie, to jest 0, 1 a 2, sú generované automaticky, a to nasledovne:

• 0. krok. Je tu vlastne vygenerovaný axiom F--F--F. Kreslenie začína vľavo dole, pričom prvé F je vygenerované červenou farbou. Potom nasledujú --, čo znamená otočenie dvakrát o uhol alfa doprava, v tomto prípade o 120 stupňov a nasledovne je generované druhé F, tento krát zelenou farbou, nasleduje ďalšie otočenie doprava a je vygenerované posledné F modrou farbou
• 1.krok. Za každé F sa dosadí pravidlo, to jest F+F--F+F. Farby zostávajú. To čo bolo dosadené za prvé F je generované červenou farbou, za druhé F zelenou a posledné F modrou farbou.
• 2.krok. Je to posledný krok, ktorý je ešte farebne vyznačený. Znovu sa za každé F z predchádzajúceho kroku dosadí F+F--F+F, a tak vznikne príslušný reťazec. Čo sa týka farieb, generovanie začína znovu vľavo dole. Prvé štyri F sú značené žltou farbou, ďalšie štyri ružovou, ďalšie bielou, ďalšie štyri šedou. Týchto prvých 16 F vlastne odpovedá prvému F v nultom kroku, a prvým štyrom F v prvom iteračnom kroku, ktoré boli farbené červenou farbou. Ďalších 16 F je zelených, a posledných 16 modrých. Tieto farby odpovedajú F-kám v predchádzajúcich krokoch, ktoré boli nahrádzané podľa pravidla.

Sierpinského trojuholník

vznikne odstránením stredného trojuholníku s vrcholmi v stredoch hrán pôvodného trojuholníka. V ďalších iteráciách sa odstraňujú analogicky stredy zostávajúcich trojuholníkov. Nasledujúci applet umožňuje sledovať axiómu a prvé štyri iteračné kroky. Konštrukciu možno chápať tiež ako pripojenie dvoch ďalších rovnoramenných trojuholníkov k dvom vrcholom pôvodného a následné dvojnásobné zmenšenie. Platí teda (ešte pred zmenšením) 3 = 2^D a D = 1.5849625. Obsah neodstránenej plochy konverguje k nule a jej obvod konverguje k nekonečnu.

Tento fraktál sa môže generovať i pomocou 1D CA (1-rozmerný celulárny automat) (zvoľte sadu pravidiel 90).

Nasledujúci applet umožňuje sledovať axiómu a prvé štyri iteračné kroky. X je pomocný, tzv. negrafický symbol, ktorý korytnačia grafika jednoducho ignoruje. Jeho náhradou sa vytvárajú v ďalších iteráciách vpísané menšie trojuholníky.

Applet sa ovláda tlačidlami

• +1 - ďalší iteračný krok
• -1 - predošlý iteračný krok
• 0 - axióm
• Generuj - vygeneruje reťazec pre i-tý iteračný krok a vykreslí jeho grafickú interpretáciu (i sa zadáva v okne Iterácia).

L-systém nie je editovateľný.

Na predchádzajúcom applete je generovaný Sierpinskeho trojuholník. Je generovaný pomocou nasledovných pravidiel:

Axiom = FXF++F++F
α = 60°
X → ++FXF--FXF--FXF++
F → FF

Tieto pravidlá sa líšia od pravidiel použitých vo veľkom aplete:

Axiom = X
α = 60°
X → ++FXF++FXF++FXF
F → FF

Pri použití týchto pravidiel dochádza ku prekresľovaniu niektorých F, inak povedané cez niektoré F-ká sa kreslí dva krát, čo by pri použití farebného kreslenia mohlo spôsobiť problémy a menší chaos u používateľov, preto sme zvolili iné pravidlá, kde takéto problémy nenastávajú.

Farebné kreslenie znovu prebieha v prvých troch krokoch:

• 0. krok. Každý znak v reťazci je kreslený osobitnou farbou. Kreslenie začína vpravo dole červeným F. Za ním nasleduje X, čo je symbol, ktorý sa nekreslí (my sme ho pre lepšie pochopenie vykreslili malým štvorčekom) a korytnačia grafika ho ignoruje. Z neho potom budú vychádzať menšie trojuholníky.
• 1. krok. Kreslenie znovu začína vpravo dole dvoma červenými F-kami. Teraz sme sa dostali do pôvodného X. Tu začína generovanie malého trojuholníka v pôvodnom väčšom. Generuje sa postupne, najprv ružová strana, skladá sa z FXF, potom šedá a svetlo modrá. Teraz sme sa vrátili znovu do pôvodného X. A postupne cez oranžovú, zelenú a modrú sa vrátime na začiatok kreslenia.
• 2. krok. Z každého X v prvom iteračnom kroku nastáva vykreslenie menšieho rovnostranného trojuholníka s farbou aké malo X, z ktorého bol menší trojuholník vygenerovaný.

Použitie zásobníka pri generovaní rastlín

Doterajšie krivky bolo možné nakresliť jediným ťahom (neprerušovaným pohybom korytnačky). Pre štruktúru rastlín sú ale typické vetvenia, t.j. korytnačka sa musí vrátiť po nakreslení jednej vetvy bez kreslenia čiary. Pre takýto pohyb "naprázdno" býva definovaný symbol f. Vetvenia rastlín majú ale obyčajne rekurzívny charakter a pre tento účel je viac vhodné použiť zásobník. Do neho sa v mieste vetvenia uložia parametre korytnačky (smer, prípadne ďalšie údaje : farba, hrúbka čiary...) a z neho sa potom vyberú po nakreslení prvej vetvy a použijú sa pre začiatok kreslenia vetvy druhej. Obvykle sa pre operáciu vkladania a výberu používajú otváracia a zatváracia hranatá zátvorka.

Jednoduché "krovie" je možné generovať napríklad L-systémom :

Applet sa ovláda rovnako ako predošlý. Rozdiel je v tom že, L-systém je editovateľný (možno meniť napríklad uhol, pridať, resp ubrať úsek v jednej z vetví, ...). Tlačidlom Reset sa obnoví pôvodný L-systém.

Aplet je generovaný podľa:

Axiom = F
α = 22.5°
F → FF-[-F+F+F]+[+F-F-F]

Farebne je generovaný v dvoch iteračných krokoch:

• 1. krok. V tomto kroku je každé F z FF-[-F+F+F]+[+F-F-F] vygenerované osobitnou farbou.
• 2. krok. Každé F z prvého iteračného kroku je nahradené reťazcom FF-[-F+F+F]+[+F-F-F], pričom farba reťazca odpovedá farbe F, ktoré nahradil.