Závorkové a stochastické L-systémy

Obsah

1. Větvící se struktury – zásobník v želví grafice
2. Závorkové L-systémy
3. První demonstrační příklad – fraktální stromy a keře
4. Vnesení náhody do vytváření L-systému: stochastické L-systémy
5. Náhodná změna kroku želvy
6. Náhodná změna natočení želvy
7. Druhý demonstrační příklad – stochastické fraktální stromy
8. Obsah dalšího pokračování tohoto seriálu

1. Větvící se struktury – zásobník v želví grafice

V předchozích třech částech seriálu pojednávajícího o fraktálech jsme si podrobně popisovali některé významné fraktální útvary vytvořené pomocí L-systémů. Všechny uvedené L-systémy měly jeden společný příznak – netvořily a ani nemohly tvořit rozvětvující se struktury. Buď se jednalo o spojité křivky, například o dračí křivku (dragon curve), křivku Hilbertovu či křivku Helge von Kocha, nebo o úsečku „rozbitou“ do jednotlivých bodů v případě Cantorovy množiny. Tuto žádoucí funkcionalitu – tj. tvorbu větvících se struktur – jsme nemohli splnit z toho prostého důvodu, že želva, která L-systémy na základě vytvořeného řetězce vykreslovala, neměla k dispozici žádnou paměť, do které by si ukládala svůj předchozí stav (stavy), tj. pozici v rovině a svoji orientaci.

Obrázek 1: Základní větvící se L-systém: binární strom

Samozřejmě je možné požadovanou paměť „nesystémově“ doplnit do ovládacího programu, například tak, že interpretace částí přepisovacího řetězce bude probíhat rekurzivně. Toto rozšíření má dosti závažnou nevýhodu v tom, že není popsatelné (nebo je velmi těžko popsatelné) pomocí přepisovacích pravidel v gramatice, což znamená, že pro každý L-systém by bylo zapotřebí upravit i generující program, nebo do tohoto programu kromě gramatiky předávat i další informace o tom, kdy má rekurze proběhnout. Ukazuje se však, že existuje jedno řešení, které je dostatečně jednoduché na programovou implementaci želví grafiky a přitom snadno pochopitelné i pro tvůrce L-systémů, kteří pracují s přepisovacími gramatikami. Zmiňované řešení spočívá v zavedení zásobníku (stack), do kterého je při interpretaci přepisovaného řetězce ukládán stav či více stavů želvy.

Obrázek 2: Jednoduchý model keře vytvořený pomocí L-systému

Stavy želvy uložené na zásobník mohou být kdykoli později vybrány – při této operaci se želva vrátí na zapamatované místo v ploše či prostoru a obnoví přitom i svoji orientaci, tj. natočení svého těla vůči souřadným osám. Zásobník implementovaný v želví grafice se vyznačuje tím, že jsou nad ním definovány pouze dvě základní operace: uložení stavu želvy na vrchol zásobníku (push state) a vyjmutí nejpozději uloženého stavu želvy z vrcholu zásobníku spolu s případným posunem a natočením želvy (pop state). Další typické operace pro datovou strukturu zásobník, jak je můžeme znát například z programovacího jazyku PostScript či Forth, nemusí být v případě želví grafiky implementovány. Rozšíření želví grafiky o zásobník však nedostačuje, protože musíme patřičným způsobem rozšířit i gramatiku. To je téma následující kapitoly.

Obrázek 3: Složitější model keře vytvořený pomocí L-systému

2. Závorkové L-systémy

V předchozí kapitole jsme si řekli, že pro účely větvících se struktur byla želví grafika doplněna o zásobník fungující jako lokální paměť želvy. Na straně přepisovací gramatiky musí také dojít k rozšíření, které je však velmi jednoduché. Do množiny terminálních symbolů (symbolů, které nejsou přepisovány, tj. nevyskytují se na levé straně přepisovacích pravidel) jsou doplněny dva znaky. Prvním znakem je „[“, který při interpretaci řetězce přikazuje želvě, že má na zásobník uložit svůj stav (push state). Druhým znakem je „]“, který želvě říká, že má ze zásobníku získat posledně uložený stav a přesunout se na přečtené pozice spolu se změnou natočení (pop state). Poznamenejme, že i v případě trojrozměrných L-systémů mají tyto dva terminální symboly shodný význam, ovšem s tím, že stav želvy je popsán pomocí trojice vektorů.

Obrázek 4: Větvička vytvořená závorkovým L-systémem

Tvar znaků určených pro popsání obou zmiňovaných „zásobníkových“ operací nebyl vybrán náhodně, protože při zápisu gramatik se mezi znaky [ a ] vkládají relativně samostatné sekvence příkazů, které ve výsledku neovlivní stav želvy – želva se po interpretaci řetězce uloženého mezi [] vrátí do původní pozice. Proto můžeme obě operace považovat za jakési instrukce skoku do podprogramu a návratu z podprogramu, což ostatně hranaté závorky evokují. V literatuře se L-systémy rozšířené o výše uvedenou dvojici terminálních symbolů nazývají závorkové L-systémy (bracketed L-systems), původní L-systémy popisované v předchozích dílech se pak označují jako dL0-systémy (deterministické L-systémy nultého řádu).

Obrázek 5: Variace na binární strom

3. První demonstrační příklad – fraktální stromy a keře

V dnešním prvním demonstračním příkladu je ukázána implementace závorkového L-systému, který slouží pro vytváření několika jednoduchých plošných modelů stromů a keřů. Funkce určené pro provádění příkazů želví grafiky jsou rozšířeny o uložení stavu želvy a pro získání tohoto stavu ze zásobníku. Samotný zásobník je implementován pomocí jednosměrně vázaného lineárního seznamu obsluhovaného funkcemi stack_init(), stack_push() a stack_pop(). Každý prvek v tomto seznamu, jenž je představován datovou strukturou t_state, obsahuje ukazatel na prvek uložený v zásobníku o jednu pozici níže, prvně vložený prvek obsahuje ukazatel obsahující hodnotu NULL. V proměnné nazvané sp je uložen ukazatel na vrchol zásobníku (stack base).

Místo pouhého jednoho L-systému je možné pomocí tohoto demonstračního příkladu vytvářet L-systémů sedm. Každý ze zmíněných sedmi L-systémů má různý tvar a počet přepisovacích pravidel, rozdílné axiomy (řetězce, které se mají přepisovat) i úhly, o které se želva otáčí při provádění příkazů „+“ a „-“. Výběr L-systému, který se má zobrazit, se provádí pomocí funkčních kláves F1 až F7. Zápis více L-systémů je poměrně přímočarý – axiomy se zapisují do pole axioms, úhly natáčení želvy do pole deltas a přepisovací pravidla do dvourozměrného pole rules. O indexaci správného L-systému se stará proměnná currentSystem. Zdrojový kód prvního demonstračního příkladu je dostupný jak v ASCII podobě, tak i jako HTML stránka se zvýrazněnou syntaxí. Ovládání prvního demonstračního příkladu se provádí pomocí několika kláves vypsaných v následující tabulce:

Obrázek 6: Screenshot prvního demonstračního příkladu

4. Vnesení náhody do vytváření L-systému: stochastické L-systémy

Pokud budeme pomocí prvního demonstračního příkladu vytvářet L-systémy v podobě stromů a keřů, zjistíme, že oproti přírodním objektům se algoritmicky vytvořené objekty liší především v tom, že přírodní objekty nejsou zcela pravidelné, ale obsahují jisté náhodné prvky (ty však nemění celkový geometrický ani topologický tvar objektu). V minulosti bylo navrženo i implementováno velké množství metod, které se snažily do co největší míry napodobit skutečný přírodní tvar objektů; L-systémy vybavené těmito metodami se nazývají stochastické L-systémy. Některé z metod simulujících určitou náhodnost přírodních objektů si popíšeme v následujících částech věnovaných prostorovým (3D) L-systémům. Jedná se například o takzvané mutace či simulaci vlivu gravitace při konstrukci 3D modelu. V dnešní části budou popsány dvě velmi jednoduché metody, které spočívají v úpravě příkazů pro želvu, samotná gramatika L-systému se přitom měnit nemusí.

Obrázek 7: Vliv náhodných hodnot na tvar binárního stromu

5. Náhodná změna kroku želvy

Pravděpodobně nejjednodušší metodou, kterou je možné nějaký pravidelný L-systém do určité míry „znáhodnit“ (ne znárodnit :-), je úprava funkcí, které slouží pro posun želvy. Jedná se o funkce logo_forward(), logo_backward a logo_move(), jež odpovídají znakům „F“, „B“ a „G“, které želva při čtení výsledného řetězce dokáže interpretovat. Místo pevně zadaného a v rámci jednoho L-systému neměnného kroku, který byl původně uložen v proměnné step se při každém volání výše uvedené trojice funkcí vypočte částečně náhodná hodnota kroku rndStep a tato hodnota je použita při přímém či zpětném pohybu želvy. Výpočet částečně náhodného kroku želvy zajišťuje funkce randomStep(), která může mít následující tvar:

//-----------------------------------------------------------------------------
// Výpočet kroku želvy s využitím céčkovského generátoru náhodných čísel
//-----------------------------------------------------------------------------
double randomStep(double step, double stepDelta)
{
    return step*(1.0+stepDelta*((double)rand()/RAND_MAX-1/2.0));
} 

Ze zápisu funkce randomStep() vidíme, že se při výpočtu kroku využívá funkce rand() ze standardní knihovny programovacího jazyka C. Náhodná hodnota z rozsahu <0,1) je posunuta o 1/2, tj. ve výsledku získáme náhodnou hodnotu ležící v rozsahu ← 1/2, 1/2). Tato hodnota je vynásobena obsahem proměnné stepDelta, která udává míru náhodnosti výsledného obrazce. Funkce logo_forward(), logo_backward a logo_move() se změní pouze nepatrně:

//-----------------------------------------------------------------------------
// Posun želvy dopředu s kreslením
//-----------------------------------------------------------------------------
void logo_forward(void)
{
    double rndStep=randomStep(step, stepDelta);
    glBegin(GL_LINES);
    glVertex2d(x,y);                               // původní pozice želvy
    x+=rndStep*cos(alpha);                         // posun želvy v zadaném směru
    y+=rndStep*sin(alpha);
    glVertex2d(x,y);                               // nová pozice želvy
    glEnd();
}



//-----------------------------------------------------------------------------
// Posun želvy dozadu s kreslením
//-----------------------------------------------------------------------------
void logo_backward(void)
{
    double rndStep=randomStep(step, stepDelta);
    glBegin(GL_LINES);
    glVertex2d(x,y);                               // původní pozice želvy
    x-=rndStep*cos(alpha);                         // posun želvy v zadaném směru
    y-=rndStep*sin(alpha);
    glVertex2d(x,y);                               // nová pozice želvy
    glEnd();
}



//-----------------------------------------------------------------------------
// Posun želvy dopředu bez kreslení
//-----------------------------------------------------------------------------
void logo_move(void)
{
    double rndStep=randomStep(step, stepDelta);
    x+=rndStep*cos(alpha);                         // posun želvy v zadaném směru
    y+=rndStep*sin(alpha);
} 

6. Náhodná změna natočení želvy

Podobně jako náhodnou změnu kroku želvy při interpretaci řetězce můžeme měnit i úhel jejího natočení. V předchozích příkladech se želva při přijetí příkazů „+“ a „-“ vždy natočila o předem známý úhel, například o 60° v případě křivky Helge von Kocha. Ve stochastických L-systémech je možné úhel natočení želvy (přesněji řečeno změnu úhlu natočení) modifikovat náhodnou hodnotou tak, jak je naznačeno na níže uvedené funkci randomAngle():

//-----------------------------------------------------------------------------
// Výpočet změny úhlu želvy s využitím RNG
//-----------------------------------------------------------------------------
double randomAngle(double angle, double angleDelta)
{
    return angle*(1.0+angleDelta*((double)rand()/RAND_MAX-1/2.0));
} 

Tato funkce se v mnohém podobá funkci randomStep(), ovšem s tím rozdílem, že místo nastavené hodnoty kroku a maximální změny kroku se předávají hodnoty o úhlech. Funkce provádějící natočení želvy, tj. logo_left() a logo_right() se změní pouze nepatrně – místo přečtení a použití konkrétní hodnoty úhlu z pole deltas (to obsahuje úhly pro více L-systémů) je tento úhel modifikován podle obsahu proměnné angleDelta. Pokud je hodnota této proměnné nulová, zůstane načtený úhel nezměněn:

//-----------------------------------------------------------------------------
// Otočení želvy doleva
//-----------------------------------------------------------------------------
void logo_left(void)
{
    alpha+=randomAngle(deltas[currentSystem], angleDelta);  // změna úhlu
}



//-----------------------------------------------------------------------------
// Otočení želvy doprava
//-----------------------------------------------------------------------------
void logo_right(void)
{
    alpha-=randomAngle(deltas[currentSystem], angleDelta);  // změna úhlu
} 

7. Druhý demonstrační příklad – stochastické fraktální stromy

V dnešním druhém demonstračním příkladu jsou implementovány obě výše zmíněné metody tvorby stochastických L-systémů. Jedná se jak o náhodnou změnu kroku želvy (kapitola pátá), tak i o náhodnou změnu natočení želvy (šestá kapitola). Ovládání tohoto příkladu je rozšířené o čtyři klávesy: „A“, „S“, „Z“ a „X“. Tyto klávesy slouží ke změně hodnot proměnných stepDelta a angleDelta, celé ovládání je popsáno ve druhé tabulce:

Obrázek 8: Screenshot druhého demonstračního příkladu

Zdrojový kód druhého demonstračního příkladu je dostupný jak v ASCII podobě, tak i jako HTML stránka se zvýrazněnou syntaxí.

Obrázek 9: Další screenshot druhého demonstračního příkladu

8. Obsah dalšího pokračování tohoto seriálu

V následují části tohoto seriálu se začneme zabývat pravděpodobně nejpraktičtějším využitím L-systémů. Bude se jednat o trojrozměrné (3D) L-systémy, které se dnes používají pro tvorbu mnoha 3D modelů, jak v počítačových hrách, tak i například v architektuře. Na závěr si ukážeme rozšíření gramatiky o další dva důležité symboly „@“ a „C“ a využití těchto symbolů při tvorbě různých dlaždicovitých vzo­rů.