Obsah
1. Vykreslení pravidelného binárního stromu s využitím lokálních proměnných
2. Binární strom vytvořený bez použití pomocných proměnných
3. Volba úhlu větvení a koeficientu zkrácení větví
4. Binární strom a role generátoru náhodných čísel
5. Vícenásobné větvení ovládané generátorem náhodných čísel
6. Vykreslení lesa
7. Odkazy na další informační zdroje
8. Obsah následující části tohoto seriálu
1. Vykreslení pravidelného binárního stromu s využitím lokálních proměnných
V předchozích dvou částech tohoto seriálu jsme si vysvětlili, jakým způsobem je možné použít želví grafiku pro vykreslování složitějších objektů, které byly vytvářeny rekurzivně volanou procedurou (a byly tedy soběpodobné). Dnes si ukážeme několik verzí procedury, kterou je možné použít pro vykreslení takzvaných binárních stromů (binary tree) i obecných stromů (n-ary tree). Princip vykreslení základní verze binárního stromu je velmi jednoduchý. Želva nejprve vykreslí kmen stromu, což je pro jednoduchost vertikální úsečka. Potom se vykreslí dvě větve, které jsou oproti kmenu zkráceny na poloviční délku. První větev je od svislého kmene odkloněna o 30° doleva, druhá větev naopak o 30° doprava. Tento postup vede k vytvoření základu budoucího stromu.
Pro další vykreslování stromu můžeme každou větev považovat za kmen menšího stromu a provést s ní naprosto stejnou operaci rozvětvení – na konci každé větve se želva otočí o 30° doleva, vykreslí se první menší větev, následně se želva otočí o 30° doprava a vykreslí druhou menší větev. Vykreslování se zastaví v případě, že je délka větví menší než zadaný limit, například pět kroků želvy.
Výše zmíněný postup je poměrně jednoduché převést do programové podoby s rekurzivně volanou procedurou. Nesmíme však zapomenout na jednu důležitou věc: želva se musí po vykreslení větve vrátit na původní místo a obnovit i svoji orientaci. To znamená, že potřebujeme nějaký nástroj pro zapamatování stavu želvy (její polohy a orientace), aby se tento stav dal pomocí příkazů setpos a setheading obnovit.
Existuje větší množství řešení tohoto problému, například vytvoření pomocné datové struktury zásobník. My si však ukážeme pouze dvě nejjednodušší varianty. První varianta spočívá v použití lokálních proměnných, do kterých bude ukládána pozice a orientace želvy (pro zjištění aktuálních vlastností želvy v Logu existují procedury pos a heading). Globální proměnné nelze použít, protože by se hodnota v nich uložená neustále přepisovala. Lokální proměnné se vytváří pomocí procedury localmake, jejíž syntaxe je naprosto stejná, jako u procedury make, tj. nejdříve je uvedeno jméno proměnné začínající uvozovkami a potom její hodnota nebo funkce, která se zavolá pro získání hodnoty (v našem případě se jedná o funkce pos a heading).
Výsledný program pro vykreslení binárního stromu má tvar:
; procedura pro vykreslení binárního stromu s využitím lokálních proměnných
to strom :delka
; zajistit ukončení vykreslování v případě malého kroku
if :delka > 5 [
; zapamatování pozice a orientace želvy
localmake "k pos
localmake "l heading
; vykreslení kmene či větve
forward :delka
; první větev - rekurzivní volání
left 30
strom :delka/2
; druhá větev - rekurzivní volání
right 60
strom :delka/2
; obnovení pozice želvy
setpos :k
setheading :l
]
end
; příkaz pro změnu velikosti grafické plochy - platné pouze pro Turtle Tracks
(draw 400 400)
; spuštění vykreslování
strom 150
2. Binární strom vytvořený bez použití pomocných proměnných
Ve druhé variantě procedury pro vykreslení binárního stromu se pro zapamatování pozice a orientace želvy používají další parametry předávané rekurzivně volané proceduře. Pokud ve dvojici parametrů předáme současnou pozici a orientaci želvy, může se na konci procedury stav želvy jednoduše obnovit, přitom ve volající proceduře není nutné používal lokální proměnné (parametry ve své podstatě nahrazují datovou strukturu zásobník (stack).
Vzhledem k tomu, že není potřebné uvádět typy proměnných, je použití parametrů velmi jednoduché, což je ostatně ukázáno i na následujícím příkladu (ve skutečnosti je pozice želvy reprezentována seznamem a ne jednou hodnotou, v některých jazycích – především těch, které seznamy či struktury nepovažují za plnohodnotné datové typy – by se tedy celý program nutně zkomplikoval)
Všimněte si, že je zapotřebí pozměnit i způsob nastartování celého vykreslování, protože je nutné proceduře strom předat i počáteční stav želvy. To je možné provést opět dvěma způsoby – buď do parametrů předat přímo konstanty [0 0] (poloha) a 0 (orientace), nebo opět použít návratové hodnoty funkcí pos (vrací seznam souřadnic) a heading (vrací jedno reálné číslo). Pokud by někomu bylo předávání dalších parametrů nepříjemné – například proto, že se odhaluje vnitřní chování procedury, což by se ve větších programech stávat nemělo – může si vytvořit „obalovou“ proceduru s hlavičkou kresli_strom :delka, která další dva parametry automaticky doplní a následně zavolá proceduru strom, jejíž tělo již zůstane v nezměněné podobě.
; procedura pro vykreslení binárního stromu bez použití lokálních proměnných
to strom :delka :pozice :uhel
; zajistit ukončení vykreslování v případě malého kroku
if :delka > 5 [
; vykreslení kmene či větve
forward :delka
; první větev - rekurzivní volání
left 30
strom :delka/2 pos heading
; druhá větev - rekurzivní volání
right 60
strom :delka/2 pos heading
; obnovení pozice želvy
setpos :pozice
setheading :uhel
]
end
; příkaz pro změnu velikosti grafické plochy - platné pouze pro Turtle Tracks
(draw 400 400)
; spuštění vykreslování
strom 100 [0 0] 0
; korektnější spuštění vykreslování
; strom 100 pos heading 
3. Volba úhlu větvení a koeficientu zkrácení větví
Pokud budeme pomocí demonstračních příkladů vypsaných v první či ve druhé kapitole vytvářet jednoduché obrázky stromů, brzy zjistíme, že se tyto obrázky oproti přírodním objektům odlišují především v tom, že přírodní objekty, tj. reálné stromy a keře, nejsou zcela pravidelné, ale obsahují jisté náhodné prvky. 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 stromů (viz kapitola sedmá s doporučenou literaturou). My si zde ukážeme jednoduchou modifikaci předchozího algoritmu, která spočívá v tom, že jak úhel jednotlivých větví, tak i jejich délka jsou náhodně měněny, takže výsledný obrázek dostane poněkud přirozenější tvar. Nebudeme se přitom zabývat takovými „detaily“, jakými jsou změna šířky a tvaru kmene i větví, přidání listů atd.
Nejprve si však ukažme rozšíření předchozích procedur strom o možnost parametrické změny úhlu větvení a také koeficientu zkrácení větví. V původní proceduře byl úhel větvení trvale nastaven na 30° a větve se spolu s rostoucím rekurzivním zanořením zkracovaly na polovinu. Nová procedura strom má přidány další dva parametry, kterými je možné úhel větvení i koeficient zkrácení zadat. Tento koeficient musí ležet v rozsahu 0..1, pokud by nabýval jiné hodnoty, došlo by k nekonečné rekurzi, která by skončila interní chybou interpreteru. Zájemci si mohou vyzkoušet použít i záporný koeficient v rozsahu –1..0, přitom se však musí do podmínky ukončení procedury vložit výraz if (abs :delka) > 2 [ (kdyby podmínka nebyla změněna, vykreslil by se pouze kmen).
; procedura pro vykreslení binárního stromu s využitím lokálních proměnných
to strom :delka :uhel :koeficient
if :delka > 5 [
; zapamatování pozice a orientace želvy
localmake "k pos
localmake "l heading
; vykreslení kmene či větve
forward :delka
; první větev - rekurzivní volání
left :uhel
strom :delka*:koeficient :uhel :koeficient
; druhá větev - rekurzivní volání
right 2 * :uhel
strom :delka*:koeficient :uhel :koeficient
; obnovení pozice želvy
setpos :k
setheading :l
]
end
; příkaz pro změnu velikosti grafické plochy - platné pouze pro Turtle Tracks
(draw 400 400)
; spuštění vykreslování
strom 150 45 0.8 
4. Binární strom a role generátoru náhodných čísel
Nyní, když víme, jakým způsobem je možné parametricky měnit úhel větvení i koeficient zkrácení větví, si můžeme ukázat upravenou proceduru strom, ve které jsou při výpočtech používána náhodná čísla. Pomocí minule popsané procedury rnd je spočítán náhodný úhel větvení tak, aby ležel v rozsahu zadaném uživatelem pomocí parametrů :uhel a :uhel_rozptyl. Z těchto hodnot je vždy vypočítán úhel větvení, který leží v rozsahu uhel-uhel_rozptyl..uhel+uhel_rozptyl. Podobným, i když poněkud komplikovanějším způsobem je specifikována základní délka větví, ze které se odvozují i délky navazujících větví. Komplikace spočívá v tom, že i zadaný rozptyl délky je zapotřebí zmenšovat o zadaný koeficient zmenšení.
Vzhledem k tomu, že parametrem procedury random musí být celé číslo, je nutné rozptyl délky, který je vlivem násobení koeficientem zmenšení obecně reálné číslo, zaokrouhlit. Čím větší jsou hodnoty obou rozptylů, tj. počátečních hodnot parametrů uhel_rozptyl a delka_rozptyl, tím náhodnější tvar má výsledný obrazec. Pokud jsou oba parametry rozptylu nulové, je vykreslen pravidelný strom, podobně jako v případě procedur uvedených v předchozích kapitolách.
; procedura pro vykreslení náhodného binárního stromu s využitím lokálních proměnných
to strom :delka :uhel :koeficient :uhel_rozptyl :delka_rozptyl
; zajistit ukončení vykreslování v případě malého kroku
if :delka > 3 [
; zapamatování pozice a orientace želvy
localmake "k pos
localmake "l heading
; vykreslení kmene či větve
forward :delka
; první větev - rekurzivní volání
make "skut_uhel :uhel - :uhel_rozptyl + 2*random :uhel_rozptyl
left :skut_uhel
make "skut_delka :delka - :delka_rozptyl + 2*random (round :delka_rozptyl)
strom :skut_delka*:koeficient :uhel :koeficient :uhel_rozptyl :delka_rozptyl*:koeficient
; druhá větev - rekurzivní volání
make "skut_uhel 2*:uhel - :uhel_rozptyl + 2*random :uhel_rozptyl
right :skut_uhel
make "skut_delka :delka - :delka_rozptyl + 2*random (round :delka_rozptyl)
strom :skut_delka*:koeficient :uhel :koeficient :uhel_rozptyl :delka_rozptyl*:koeficient
; obnovení pozice želvy
setpos :k
setheading :l
]
end
; příkaz pro změnu velikosti grafické plochy - platné pouze pro Turtle Tracks
draw
pu
setpos [0 -170]
pd
ht
; spuštění vykreslování
strom 150 30 0.5 20 40 
5. Vícenásobné větvení ovládané generátorem náhodných čísel
Proceduru vysvětlenou v předchozí kapitole můžeme ještě více „znáhodnit“. Všechny prozatím vykreslené stromy byly binární, tj. v každém kroku rekurze se provádělo rozvětvení na dvě části – existoval tedy jeden kmen, dvě větve na úrovni 1, čtyři větve na úrovni 2 atd. V předchozí proceduře jsme sice pomocí generátoru náhodných čísel ovlivnili jak délku větví, tak i úhel jejich rozvětvení, avšak základní tvar stromu (přesněji řečeno jeho topologie) zůstala zachována.
Pojďme si nyní ukázat, jak lze pomocí generátoru náhodných čísel zajistit, aby se strom v daném místě větvil na dvě nebo tři části. Princip je jednoduchý: provedeme větvení levé části podstromu a poté vygenerujeme náhodné číslo 0 nebo 1. Podle výsledku volání generátoru náhodných čísel se vytvoří buď pouze pravá část podstromu, nebo se ještě přidá prostřední větev.
Poněkud složitější je výpočet odklonu pravé větve, jehož základem je buď hodnota 1×uhel či 2×uhel, podle toho, zda se vytvoří i prostřední větev (procedury left a right natáčí želvu relativně). Proto je i ta část výpočtu, která se týká vytváření pravé větve v programu uvedena dvakrát, v obou blocích podmíněného příkazu ifelse.
; procedura pro vykreslení náhodného stromu s využitím lokálních proměnných
; počet větvení je ovlivněn generátorem náhodných čísel
to strom :delka :uhel :koeficient :uhel_rozptyl :delka_rozptyl
; zajistit ukončení vykreslování v případě malého kroku
if :delka >1 [
; zapamatování pozice a orientace želvy
localmake "k pos
localmake "l heading
; vykreslení kmene či větve
forward :delka
; první větev - rekurzivní volání
make "skut_uhel :uhel - :uhel_rozptyl + 2*random :uhel_rozptyl
left :skut_uhel
make "skut_delka :delka - :delka_rozptyl + 2*random (round :delka_rozptyl)
strom :skut_delka*:koeficient :uhel :koeficient :uhel_rozptyl :delka_rozptyl*:koeficient
; rozhodnutí, na kolik částí se má podstrom rozdělit
ifelse (random 2) = 1 [
; "pouze" dvě části
; druhá větev - rekurzivní volání
make "skut_uhel 2*:uhel - :uhel_rozptyl + 2*random :uhel_rozptyl
right :skut_uhel
make "skut_delka :delka - :delka_rozptyl + 2*random (round :delka_rozptyl)
strom :skut_delka*:koeficient :uhel :koeficient :uhel_rozptyl :delka_rozptyl*:koeficient
] [
; tři části
; druhá větev - rekurzivní volání
make "skut_uhel :uhel - :uhel_rozptyl + 2*random :uhel_rozptyl
right :skut_uhel
make "skut_delka :delka - :delka_rozptyl + 2*random (round :delka_rozptyl)
strom :skut_delka*:koeficient :uhel :koeficient :uhel_rozptyl :delka_rozptyl*:koeficient
; třetí větev - rekurzivní volání
make "skut_uhel :uhel - :uhel_rozptyl + 2*random :uhel_rozptyl
right :skut_uhel
make "skut_delka :delka - :delka_rozptyl + 2*random (round :delka_rozptyl)
strom :skut_delka*:koeficient :uhel :koeficient :uhel_rozptyl :delka_rozptyl*:koeficient
]
; obnovení pozice želvy
setpos :k
setheading :l
]
end
; příkaz pro změnu velikosti grafické plochy - platné pouze pro Turtle Tracks
(draw 400 400)
; spuštění vykreslování
strom 200 30 0.5 0 0 
6. Vykreslení lesa
S využitím zobecněné procedury strom uvedené v předchozí kapitole již můžeme vykreslit jednoduchou scénu s lesem. Princip tvorby lesa je jednoduchý: v programové smyčce se želva (bez kreslení) přesunuje na náhodnou pozici v ploše a od této pozice se začíná vykreslovat strom, jehož parametry, a tím i vizuální podoba, jsou ovlivněny generátorem náhodných čísel. Kromě toho se pomocí procedury setpencolor, jejíž funkci si podrobněji vysvětlíme příště, mění i barva vykreslování.
Změnou počtu opakování smyčky se ovlivňuje celkový počet vykreslených stromů, hodnoty předávané proceduře setpos jsou zvoleny s ohledem na velikost grafické plochy a význam parametrů procedury strom jsme si již vysvětlili v předchozí kapitole. Část programu, která zajistí vytvoření lesa, má následující tvar (proceduru strom zde již nebudu uvádět):
; příkaz pro změnu velikosti grafické plochy - platné pouze pro Turtle Tracks
(draw 400 400)
; vykreslí se celkem 10 stromů
repeat 10 [
pu
; posun želvy (kmen stromu)
setpos list (-200+random 400) (-200+random 400)
pd
ht
; nastavení náhodné barvy
setpencolor 1 + random 7
strom 150 45 0.6 20 40
] 
7. Odkazy na další informační zdroje
- Clayson James:
Visual Modeling with Logo
MIT Press - Prusinkiewicz Przemyslaw and Hanan James:
Lindenmayer Systems, Fractals, and Plants,
Springer-Verlag, New York, 1989. - Prusinkiewicz, Przemyslaw a Aristid Lindenmayer:
The Algorithmic Beauty of Plants,
Springer-Verlag, 1990. - Mandelbrot Benoit B.:
The Fractal Geometry of Nature,
W. H. Freeman, New York; San Francisco, 1982, ISBN 0–7167–1186–9 - Pickover Clifford:
Computers, Pattern, Chaos and Beauty: Graphics from an Unseen World,
St. Martin's Press, New York, 1990. - Weber J., Penn J.:
Creation and Rendering of Realistic Trees,
Proceedings of SIGGRAPH '95, volume 22(4), ACM SIGGRAPH, New York, 1995.
8. Obsah následující části tohoto seriálu
V další části seriálu o programovacím jazyce Logo si vysvětlíme pokročilejší operace želví grafiky, pomocí kterých je možné vykreslovat vícebarevné obrazce, použít několik želv současně, vyplňovat plochy, dopisovat do obrázků texty atd.
ČLÁNKY DO MAILU