Algorytm wzrostu

W serii Prog&Play nauczyliśmy się już tworzyć komputerowe dywany, eksplorować nieskończoną głębię fraktali i generować grafikę za pomocą wirtualnych nici. Dzisiaj zajmiemy się tak zwanym algorytmem wzrostu i wykorzystamy go do generacji form roślinnych.

Namalować realistyczną ścianę lasu jest bardzo trudno. Ta masa zieleni nie może być utworzona kilkoma pociągnięciami pędzla. Jeśli chcemy uzyskać najwyższy stopień realizmu, musimy odtworzyć na płótnie wszystkie listki, gałązki i igiełki, strukturę pokrytej mchem kory drzew i przemykające przez zielone sito promienie światła. Tajemnica realizmu ukrywa się w najdrobniejszych szczegółach. Brak tych szczegółów pozwala natychmiast odróżnić film animowany od prawdziwego filmowania. Żaden "klasyczny" artysta nie namaluje dostatecznie realistycznej ściany lasu.

Na szczęście malarstwo to nie fotografia - realizm przedstawianej formy nie jest tym, czego oczekujemy od tej dziedziny sztuki. Niemniej jednak ogromne zapotrzebowanie na realizm zgłaszają producenci gier komputerowych i przemysł filmowy. Algorytm wzrostu - choć wymyślony na potrzeby nauk przyrodniczych - po latach tutaj znalazł swoje najważniejsze zastosowanie.

Skoro nie potrafimy narysować ściany lasu, to wyhodujmy jej komputerowy obraz wraz ze wszystkimi mikroszczegółami formy. Niech będą tam wszystkie niemożliwe do bezpośredniego narysowania listki i igiełki. Zamiast rysować jurajską paproć, zaproponujmy jej formułę wzrostu i program, który wyświetli ją na ekranie.

Program kreślenia jurajskich lasów będzie się składał z dwóch wyraźnie wyodrębnionych części: rozwijającej formułę pierwotnej, prostej roślinki w potężne, bujne drzewo i wykreślającej jej obraz na ekranie.

Niech roślina składa się z dwóch gałązek, oznaczonych symbolami A i B. Możemy sobie na przykład wyobrazić, że symbol A oznacza witkę, symbol B jakiś listek lub kwiatek - wszystko to będziemy musieli uściślić w drugiej części programu, odpowiadającej za obraz rośliny. Niech początkowa roślinka będzie zdefiniowana za pomocą symbolu A. Ot, taki badylek...

Teraz zdefiniujmy reguły wzrostu małej roślinki. Niech w każdym cyklu wzrostu każdy symbol A zostanie zastąpiony sekwencją AB, a każdy symbol B symbolem A. Nietrudno zauważyć, że w wyniku konsekwentnego stosowania tych reguł roślinka rośnie, bo jej symboliczna receptura wydłuża się:

A

AB

ABA

ABAAB

ABAABABA

...

Algorytm ten zrealizujemy z łatwością choćby za pomocą operacji tekstowych, wprowadzających zamiast jednych symboli inne ich sekwencje:

String FORMULA = "AB";

void rozwin()

{

String rozwiniecie_A = "AB";

String rozwiniecie_B = "A";

String nowa_formula;

for( int i=1; i<=FORMULA.Length(); i++)

{

switch( FORMULA[i])

{

case 'A':

nowa_formula = nowa_formula + rozwiniecie_A;

break;

case 'B':

nowa_formula = nowa_formula + rozwiniecie_B;

break;

// ewentualne inne symbole

// i ich rozwijanie...

}

}

FORMULA = nowa_formula;

}

Algorytm ten zapisaliśmy w formie funkcji o nazwie rozwin(). Funkcja ta modyfikuje zmienną tekstową FORMULA, kolejne jej znaki zastępując nowymi sekwencjami znaków. Widzimy już, dlaczego nazywa się go algorytmem wzrostu.

Rozwijanych symboli może być więcej, a dwa z nich będą miały znaczenie szczególne - będą odpowiadały za boczne odrosty. Każdy wie, że realistyczna forma roślinna musi mieć boczne gałązki, listki, kwiatki.

Niech symbol ( oznacza, że z pnia głównego roślinki gdzieś w bok wyrasta dodatkowa gałązka, a symbol ) niech kończy to odrastanie.

Teraz naszkicujmy drugą część algorytmu, odpowiadającą za wykreślanie graficznego obrazu rośliny, ukrytej w dopiero co rozwiniętej formule tekstowej. Po kolei przejrzymy wszystkie symbole i odpowiednio zamienimy je na kolorowe punkty czy linie. Spodziewamy się drobnych kłopotów w momencie realizacji odrostu bocznej gałązki - do jej wykreślenia użyjemy tego samego algorytmu, który kreśli główny pień. Mówiąc ściślej, algorytm kreślenia rośliny w momencie napotkania symbolu odrostu ( wywoła sam siebie, czyli będzie to algorytm rekurencyjny:

int POZYCJA = 1;

void rysuj(int x0, int y0, double kat, int dlg)

{

double dkat = 45;

int x1, y1;

char znak;

while( POZYCJA <= FORMULA.Length() )

{

znak = FORMULA[POZYCJA];

POZYCJA = POZYCJA + 1;

switch( znak)

{

case 'A': // gałązka A - odcinek biały

x1 = x0 + dlg * cos( kat * M_PI / 180.);

y1 = y0 + dlg * sin( kat * M_PI / 180.);

Line( x0, y0, x1, y1, White);

x0 = x1;

y0 = y1;

break;

case 'B': // gałązka B - odcinek czarny

x1 = x0 + dlg * cos( kat * M_PI / 180.);

y1 = y0 + dlg * sin( kat * M_PI / 180.);

Line( x0, y0, x1, y1, Black);

x0 = x1;

y0 = y1;

break;

case '(': // odrost

dkat = -dkat; // raz w lewo, raz w prawo

rysuj( x0, y0, kat + dkat, dlg);

break;

case ')': // koniec odrostu

return; // powrót na pień główny

}

}

}