Hlavní navigace

Pokročilejší grafické operace v Logu

Pavel Tišnovský

V desátém článku o jazyce Logo dokončíme kapitolu věnovanou použití generátoru náhodných čísel (RNG) při vykreslování grafických objektů. Ukážeme si tvorbu binárních stromů, od jejich nejzákladnější varianty až po plně parametrizovatelnou proceduru, kterou následně použijeme při generování modelu lesa.

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.

logo1001
Obrázek 1: Základ binárního stromu po vykreslení kmene a dvou větví, z nichž každá je od základu odkloněna o 30°

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.

logo1002
Obrázek 2: Binární strom po provedení několika rekurzivních volání procedury strom

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ě.

logo1003
Obrázek 3: Prvních šest iterací při generování binárního stromu
; 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 

logo1004
Obrázek 4: Binární strom po provedení sedmi iterací

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.

logo1005
Obrázek 5: Stromy vzniklé voláním zobecněné procedury strom, každý objekt měl nastaven jiný úhel větvení: 10°, 20°…90°

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 

logo1006
Obrázek 6: Stromy vzniklé voláním zobecněné procedury strom, každý objekt měl nastaven úhel větvení na 30° a koeficient zkrácení větví byl postupně nastaven na hodnoty 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.65 a 0.7

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_roz­ptyl. 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 

logo1007
Obrázek 7: Binární strom ovlivněný generátorem náhodných čísel

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.

logo1008
Obrázek 8: Původně pravidelný binární strom, ve kterém je nově prováděno větvení na dvě či tři části (nejedná se již tedy o binární strom)

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.

logo1009
Obrázek 9: Najdete mezi těmito stromy rozdíl?
; 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 

logo1010
Obrázek 10: Strom, ve kterém je generátorem náhodných čísel ovlivněn úhel větvení, délka větví i počet rozvětvení (dvě nebo tři)

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
] 

logo1011
Obrázek 11: Výsledek běhu předešlého programu (po změně barvové palety)

logo1012
Obrázek 12: Spuštění předešlého programu s odlišnými parametry (po změně barvové palety)

7. Odkazy na další informační zdroje

  1. Clayson James:
    Visual Modeling with Logo
    MIT Press
  2. Prusinkiewicz Przemyslaw and Hanan James:
    Lindenmayer Systems, Fractals, and Plants,
    Springer-Verlag, New York, 1989.
  3. Prusinkiewicz, Przemyslaw a Aristid Lindenmayer:
    The Algorithmic Beauty of Plants,
    Springer-Verlag, 1990.
  4. Mandelbrot Benoit B.:
    The Fractal Geometry of Nature,
    W. H. Freeman, New York; San Francisco, 1982, ISBN 0–7167–1186–9
  5. Pickover Clifford:
    Computers, Pattern, Chaos and Beauty: Graphics from an Unseen World,
    St. Martin's Press, New York, 1990.
  6. 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.

Našli jste v článku chybu?

28. 8. 2007 17:03

uživatel si přál zůstat v anonymitě
Diky.

28. 8. 2007 13:03

Dobrý den, když jsem poprvé dělala korekturu článku Pavla Tišnovského, také mě výraz "barvová paleta" zarazil. Gramaticky mu však není co vytknout, protože čeština je jazyk přizpůsobivý, a z významového hlediska je toto slovní spojení opravdu přiléhavější než "barevná paleta". "Paleta barev" je obvyklejší slovní spojení, takže nám připadá správnější, ve skutečnosti mezi správností spojení "paleta barev" a "barvová paleta" není rozdíl. Výraz "…
Měšec.cz: Stavební spoření: alternativa i pro seniory

Stavební spoření: alternativa i pro seniory

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

DigiZone.cz: Velká cena v Abú Dhabí: 131 ti­síc diváků

Velká cena v Abú Dhabí: 131 ti­síc diváků

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?