Strona domowa ... |
By narysować liść paproci nie musimy kreślić łodyżki czy owalnych listków.
Możemy wymyśleć recepturę hodowli obrazu paproci.
Zrazu prosta receptura powinna się komplikować w miarę rozwijania hodowli.
Ponadto powinna udostępniać do ingerencji jakieś swoje parametry, odpowiadające np.
za długość listków, ich mniej lub bardziej zasuszoną barwę, wysokość, kąt wyrastania, ....
Zamykając taki algorytm w pętli mamy okazję wyhodować cały paprociowy las,
niezwykle bogaty w swej sparametryzowanej różnorodności, bardziej prawdziwy
niż wszystkie prawdziwe, jurajskie lasy paprociowe.
|
Definicja formy roślinnej
|
Recepturą formy roślinnej będzie prosta fraza tekstowa. Na początek ograniczymy się
do formuł zbudowanych z trzech znaków, które będą posiadały następującą interpretację:
ˇ A - kreśl odcinek o długości - powiedzmy - 100 pikseli,
ˇ R - skręć w prawo o kąt - powiedzmy - 90 stopni,
ˇ L - skręć w lewo o 90 stopni.
Symbole A, R, L możemy interpretować jako rozkazy dla jakiegoś bardzo prostego żółwia z języka logo.
Przez chwilę poćwiczmy wyobraźnię, oswajając się z formułami, zbudowanymi z trzech powyższych liter.
Formuła "A" oznacza wykreślenie odcinka o długości 100 pikseli.
Formuła "ARARARA" oznacza wykreślenie kwadratu o boku 100 pikseli.
Formuła "ALALALA" też oznacza wykreślenie kwadratu o boku 100 pikseli, tyle że kreślenie odbywa się w przeciwnym kierunku.
Szkic algorytmu wykreślania formuły roślinnej, zbudowanej z trzech symboli, powinien wyglądać następująco:
PROGRAM interpretacja_formuły ()
Stałe:
STRING formula = "ARARARA";
Zmienne:
double x1=0, y1=0, x2, y2, kąt=0, długość=100;
for i=1 to strlen( formula)
switch( formula[ i])
{case 'A': x2=x1+długość * cos( kąt);
y2=y1+długość * sin( kąt);
odcinek( x1, y1, x2, y2);
x1=x2, y1=y2;
break;
case 'R': kąt = kąt - 90; //w lewo
break;
case 'L': kąt = kąt + 90; //w prawo
break;
}
next i
Tu są pliki programu interpretującego formułę w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
|
Algorytm rozwijania formuły
|
U podstaw algorytmu wzrostu formy roślinnej będzie leżał pewien nieskomplikowany algorytm,
operujący na skrawku tekstu.
Tekst początkowy, złożony z niewielu znaków, zostanie wydłużony w niezbyt wymyślny sposób.
Każdy znak zostanie zastąpiony kilkoma nowymi znakami, zgodnie z jakąś wcześniej umówioną recepturą.
Zacznijmy od prostego przykładu. Niech pierwotny tekst ma brzmienie "AB" - nieważne, za jakie elementy obrazu rośliny odpowiadają symbole "A" i "B".
Jeśli w pierwotnym tekście gdziekolwiek były litery "A" (widzimy, że jedna jest), to niech wszystkie zostaną zastąpione sekwencją znaków "AB".
Jeśli w pierwotnym tekście były litery "B" (też jest jedna), niech zostaną zastąpione sekwencją "BAB".
Początkowy tekst "AB" zmienia się zatem w tekst "ABBAB". Wydłuża się.
Oto szkic programu rozwijającego formułę tekstową:
PROGRAM rozwijanie_formuły ()
Stałe:
STRING formula = "AB";
STRING rozwiniecie_A = "AB", rozwiniecie_B = "BAB";
Zmienne:
STRING nowa_formula;
for i=1 to strlen( formula)
switch( formula[ i])
{case 'A': nowa_formula += rozwiniecie_A;
break;
case 'B': nowa_formula += rozwiniecie_B;
break;
}
next i
formula = nowa_formula;
Po zdefiniowaniu pierwotnego tekstu i rozwinięć, mających zastąpić występujące w nim znaki,
przystępujemy do przeglądania formuły. Pętla for() odczytuje tekst znak po znaku,
a instrukcja switch() podejmuje decyzję, jakim rozwinięciem zastąpić napotkany znak.
Nowe brzmienie tekstu pojawia się w zmiennej nowa_formula, ale na koniec algorytmu
ta nowa formuła jest przepisywana do starej.
Oczywiście rozwijanych znaków może być więcej niż dwie występujące powyżej literki "A" i "B".
Ponadto taki rozwinięty tekst można na powót skierować do powyższego algorytmu i ponownie go rozwinąć.
A potem trzeci raz, czwarty i tak dalej, i tak dalej.
W efekcie otrzymamy programistyczne narzędzie do dziwnego, szybkiego wydłużania tekstów.
Tu są pliki programu rozwijającego formułę w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
|
Przykłady
|
Zastosowanie dwóch poprzednich elementów programu (algorytmu interpretacji formuły tekstowej
i algorytmu jej rozwijania) prowadzi do bardzo ciekawych form graficznych,
co prawda jeszcze niezbyt przypominających rośliny.
Pierwszy przykład operuje symbolami "A" (prosto), "L" (skręć o 90 st. w lewo) i "R" (o 90 st. w prawo).
Pierwotna formuła ma brzmienie "A", czyli na początku mamy odcinek. Reguły rozwijania są następujące:
"A" -> "ALARARALA"
"L" -> "L"
"R" -> "R"
Ponieważ wielokrotne zastosowanie algorytmu wzrostu coraz bardziej powiększa rysunek,
w każdym kroku poszerzania formuły zastosowano zmniejszanie odcinka, kreślonego na polecenie "A".
Dzięki temu rysunek jest coraz bardziej złożony, ale nie coraz większy.
Tu są pliki programu "hodującego" element tzw. kwadratu Kocha w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
Na następnym rysunku jest ilustracja tego samego algorytmu, ale zastosowana do pierwotnej formuły "ARARARA", czyli do kwadratu.
Reguły interpretacji symboli i ich rozwijania są identyczne. Krzywa nazywa się kwadratem Kocha.
Tu są pliki programu "hodującego" kwadrat Kocha w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
Tu są pliki programu "hodującego" płatek śniegu Kocha w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
Tu są pliki programu "hodującego" linię Peano w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
Tu są pliki programu "hodującego" zbiór Cantora w C++ Builder (5 kB)
A tutaj gotowy program (139 kB)
|
Boczne gałązki i rekurencja
|
Nasz algorytm wzrostu jeszcze nie nadaje się do opisu form biologicznych.
Brakuje w nim bardzo ważnego elementu - możliwości generacji form rozgałęzionych.
Sprawa jest dość skomplikowana, choć na pierwszy rzut oka na taką nie wygląda.
Dodajmy do naszego systemu symboli dwa nowe znaki:
ˇ "( " - początek odrostu,
ˇ ") " - koniec odrostu.
Typowa formuła będzie miała teraz choćby takie brzmienie:
"B(A)B(A)A"
Formuła ta powinna być zinterpretowana następująco:
ˇ Wykreśl gałązkę typu "B" (cokolwiek by ten typ oznaczał - kolor, styl linii, grubość, ...).
ˇ Rozpocznij odrost, wykreśl gałązkę typu "A" i wróć na pień główny.
ˇ Wykreśl gałązkę typu "B".
ˇ Rozpocznij odrost, wykreśl gałązkę typu "A" i wróć na pień główny.
ˇ Wykreśl gałązkę typu "A".
Z powyższego powinniśmy dostrzec, że pień główny składa się z trzech odcinków "BBA"
i że dodatkowo ma dwie boczne gałązki - odcinki typu "A".
Rozwijanie pierwotnej formuły nie sprawi nam żadnych kłopotów:
void TForm1 :: rozwin( void)
{
String tmp;
int i, dlg = formula.Length();
char c;
for( i = 1; i <= dlg; i ++)
{
c = formula[ i];
switch( c)
{
case 'A': //gałązka typu A
tmp += "B(A)B(A)A";
break;
case 'B': //gałązka typu B
tmp += "BB";
break;
case '(': //boczny odrost
tmp += "(";
break;
case ')': //koniec odrostu
tmp += ")";
break;
...
// Ewentualne rozwinięcia ewentualnych innych symboli
}
}
formula = tmp;
}
Jest to znany już algorytm zastępowania każdego napotkanego znaku nową sekwencją znaków.
Nowy tekst początkowo pojawia się w zmiennej pomocniczej,
ale w końcu jest przepisywany do głównej zmiennej formula.
Akurat tutaj nietrywialne sekwencje rozwinięć pojawiają się po napotkaniu znaków "A" i "B"
i nie pojawiają się po napotkaniu symboli sterujących odrastaniem bocznych pędów,
ale jest to ograniczone wyłącznie naszą fantazją. Nie ma powodu,
by odrost bocznej gałązki nie był zastępowany jakąś skomplikowaną, nową sekwencją.
W przeciwieństwie do funkcji rozwin(), algorytm rysuj() jest teraz istotnie inny.
Zauważmy, że boczny odrost jest - rzecz biorąc formalnie - tym samym, czym cała roślina.
Dobrze byłoby nie komplikować sprawy odrostu bardziej, niż wywołanie do jego wykreślenia funkcji rysuj().
Ale to oznacza, że funkcja rysuj(), napotkawszy symbol odrostu, ma wywołać samą siebie ...
Nie każdy język programowania potrafi sobie poradzić z takim zagadnieniem.
Jeśli funkcja wywołuje samą siebie, oznacza to, że całe jej obecne środowisko,
stany wszystkich zmiennych, cały jej bieżący ustrój muszą być odłożone gdzieś w pamięci,
bo za chwilę trzeba będzie zająć się czymś zupełnie innym (tutaj inną roślinką).
Po zakończeniu tego nowego zadania trzeba będzie wrócić do pierwotnych zmiennych
i kontynuować pierwotne zadanie.
Łatwo sobie wyobrazić stopień komplikacji takich algorytmów - przecież boczna
gałązka może też zawierać boczną gałązkę, która też może zawierać, ... i tak dalej, i tak dalej.
Rekurencyjne wywoływania funkcji - bo tak to się nazywa - są narażone na duże
niebezpieczeństwo wyczerpania zasobów pamięciowych komputera.
Każdy stan funkcji musi być odłożony w pamięci, gdy nadchodzi nowe wywołanie samej siebie.
Pamięci może zabraknąć ...
Oto funkcja rysuj(), wywołująca samą siebie, gdy pojawi się symbol "(" odrostu bocznej gałązki:
void TForm1 :: rysuj( double x0, double y0, double kat, double dlg)
{
int len = formula.Length();
char c;
double dkat = 45; //modyfikacja kąta odrostu
double k = M_PI / 180.; //stopnie na radiany
Canvas -> Pen -> Width = 2;
while( POZYCJA < len)
{
c = formula[ ++POZYCJA];
switch( c)
{
case 'A': //wykreśl odcinek biały
Canvas -> Pen -> Color = clWhite;
Canvas -> MoveTo( x0, ClientHeight-y0);
x0 += dlg * cos( k * kat);
y0 += dlg * sin( k * kat);
Canvas -> LineTo( x0, ClientHeight-y0);
break;
case 'B': //wykreśl odcinek czarny
Canvas -> Pen -> Color = clBlack;
Canvas -> MoveTo( x0, ClientHeight-y0);
x0 += dlg * cos( k * kat);
y0 += dlg * sin( k * kat);
Canvas -> LineTo( x0, ClientHeight-y0);
break;
case '(': //odrost
dkat = -dkat; //raz w lewo, raz w prawo ...
rysuj( x0, y0, kat + dkat, dlg);
break;
case ')': //koniec odrostu
return;
}
}
return;
}
Tu są pliki pierwszej rośliny (bez zmniejszania wymiaru) w C++ Builder (5 kB)
A tutaj gotowy program (133 kB)
Tu są pliki drugiej rośliny (ze zmniejszaniem długości odcinka) w C++ Builder (5 kB)
A tutaj gotowy program (133 kB)
|
Czynnik losowy
|
Poszukując realizmu kształtów hodowanych form musimy zwrócić uwagę na bardzo istotny
szczegół - algorytm wzrostu zawsze prowadzi do takich samych form, tymczasem w otaczającej
nas rzeczywistości nie znajdziemy dwóch takich samych roślinek. Każdy organizm jest inny,
nawet jeśli należy do tego samego podgatunku. Jak zatem pogodzić jednoznaczny wynik działania
algorytmu wzrostu z różnorodnością obserwowanych form?
Na każdy organizm działa nieprzeliczalny zbiór czynników zewnętrznych,
bezustannie modyfikujący ich algorytmiczny, idealny, genotypowy wzorzec - w efekcie
każdy organizm jest inny. Nie mamy żadnych szans zaprogramowania presji tego środowiska,
ale możemy do formuł wzrostu wprowadzić czynniki losowe. Na fotografii obok
zastosowano wcześniej opisaną formułę wzrostu, ale boczne pędy odrastają pod kątami
niedokładnie równymi +/- 45 stopni. Gałązka typu "A" ma biały kolor i szerokość dwóch pikseli.
Gałązka typu "B" jest czarna i ma szerokość jednego piksela.
Oto propozycja funkcji rysuj() z udziałem czynników losowych, dostarczanych funkcją random():
void TForm1 :: rysuj( double x0, double y0, double kat, double dlg)
{
int len = formula.Length();
char c;
double dkat, ddlg; //zmodyfikowane parametry funkcji
double dkatodrostu = random(90); //losowa modyfikacja kąta odrostu
double k = M_PI / 180.; //stopnie na radiany
while( POZYCJA < len)
{
c = formula[ ++POZYCJA];
dkat = kat+(random(40)-20); //losowa modyfikacja kąta wyrastania
ddlg = random(100*dlg)/100.0; //losowa modyfikacja długości
switch( c)
{
case 'A': //wykreśl odcinek biały
Canvas -> Pen -> Width = 2;
Canvas -> Pen -> Color = clWhite;
Canvas -> MoveTo( x0, ClientHeight-y0);
x0 += ddlg * cos( k * dkat);
y0 += ddlg * sin( k * dkat);
Canvas -> LineTo( x0, ClientHeight-y0);
Canvas -> Pixels[x0][ClientHeight-y0] = clBlue;
break;
case 'B': //wykreśl odcinek czarny
Canvas -> Pen -> Width = 1;
Canvas -> Pen -> Color = clGreen;
Canvas -> MoveTo( x0, ClientHeight-y0);
x0 += ddlg * cos( k * dkat);
y0 += ddlg * sin( k * dkat);
Canvas -> LineTo( x0, ClientHeight-y0);
Canvas -> Pixels[x0][ClientHeight-y0] = clRed;
break;
case '(': //odrost
dkatodrostu = -dkatodrostu;
rysuj( x0, y0, dkat + dkatodrostu, dlg);
break;
case ')': //koniec odrostu
return;
}
}
return;
}
Budulcem Natury jest świat niewyobrażalnie małych atomów.
Dlatego faktura powierzchni prawdziwych obiektów na ogół jest poskręcana, poplątana,
pozawijana aż do granic najlepszej mikroskopii. Próbą oddania nieregularności rysu prawdziwych
powierzchni jest stosowanie geometrii fraktalnej, niejako wbudowanej w algorytm wzrostu.
Na drugiej fotografii nałożono na siebie trzy roślinki z poprzedniej fotografii,
a każda z nich miała losowo modyfikowane kąty odrostów i długości gałązek.
Natura lubi proste reguły, ale nie lubi regularnych form. Widocznie w jej algorytmach
wzrostu duży udział mają współczynniki losowe. Niekoniecznie znaczy to, że Pan Bóg rzuca
w niebie kośćmi do gry. Na kształt drzewka ma wpływ taki ogrom rzadko kiedy znanych czynników,
że wygodniej w swej niewiedzy mówić nam o częściowo losowym charakterze praw wzrostu.
W tych wiotkich, kwitnących gałązkach trudno rozpoznać omówioną już prostą sadzonkę z poprzedniej fotografii.
Na każdym etapie interpretacji symboli lekko zmieniano długość witki,
kąt jej prowadzenia i kąt ewentualnego odrastu. Sama gałązka typu "A" jest linią białą,
zakończoną jednym niebieskim pikselem. Linia typu "B" jest zielona, ale na końcu ma punkt czerwony.
Roślina nr 1 w C++ Builder (5 kB)
A tutaj gotowy program (133 kB)
Roślina nr 2 w C++ Builder (5 kB)
A tutaj gotowy program (133 kB)
Roślina nr 3 w C++ Builder (5 kB)
A tutaj gotowy program (133 kB)
|
Więcej elementów opisu rośliny
|
Niech nośnikiem parametru - powiedzmy długości witki, kąta, pod jakim ona rośnie, jej grubości,
i tak dalej, będzie następująca klasa:
const double NIEOKRESLONY = -9999999;
//...
// Parametr rośliny (kąt, długość, kolor, co tam jeszcze),
// z wbudowanym procesem modyfikacji na szerokość +/- mutacja.
class TGen
{
private:
double g; //wartość genu (kąt, długość, kolor, ...)
double mutacja; //szerokość mutacji
double min, max; //zakres dopuszczalnych wartości
double mutuj( double Ag, double Amut, double Amin, double Amax) const;
public:
TGen( double Ag, //konstruktor merytoryczny
double Amutacja,
double Amin=NIEOKRESLONY, double Amax=NIEOKRESLONY);
double daj_zmutowany_parametr( void) const; //funkcje odczytu genu
TColor daj_zmutowany_kolor( void) const;
void daj_min_max( double &Amin, double &Amax) const;
void daj_mut( double &Amut) const;
};
Klasa ta nazywa się TGen - to przez nawiązanie i szacunek do genu - elementarnego nośnika informacji
o każdym organiźmie. Najważniejszą zmienną w klasie TGen jest parametr g.
Parametr ten będzie oznaczał numeryczną wartość długości gałązki, kąta jej odrostu, grubości,
czegokolwiek innego.
Klasa TGen implementuje wartość pojedynczego parametru rośliny, takiego jak długość gałązki
czy kolor listka. Oprócz wartości implementuje też jej zmienność w zadanej rozpiętości.
Zmiennych typu TGen (genów?) wprowadzić do gry możemy dowolnie dużo. Roślina na pierwszej fotografii
operuje dwiema gałązkami, z których każda jest opisana trójką genów, reprezentujących długość,
grubość, kolor. Dodatkowo w definicji rośliny znalazł się gen kąta wzrostu, dwa geny jego zmiany
(w lewo i w prawo) i gen kąta odrostu. Algorytm powtórzono trzykrotnie, uzyskując ten bukiet delikatnych ziół.
Najbardziej złożona roślina w C++ Builder (5 kB)
A tutaj gotowy program (135 kB)
|
