Prírodou inšpirované algoritmy

L-systém

Rozšírená verzia L-systému je srdcom tohto systému. Interakcia medzi prostredím a L-systém sa realizuje pomocou spätnoväzobnej slučky. L-systém môže načítať zo systému nejakú hodnotu, tú spracuje a výsledok pošle späť do modulu prostredia.

L-systém je zapísaný do textového súboru a obsahuje axiómu a prepisovacie pravidlá, ktoré určujú ako sa data z prostredia spracujú a ako bude L-systém rásť.

Pri použití klasických L-systémov nastali problémy s pamäťou. Keďže sa oheň šíri rýchlo, tak sa aj L-systém rozširoval veľmi rapídne. Už pri 11 iteraciách L-systém narástol do veľkosti niekoľkých MB čo dosť ovplyvňovalo výkon a využitie pamäte. Taktiež prostredie, v ktorom sa L-systém mali vyvíjať mohlo byť veľké. Napríklad továreň o rozmeroch 1000x1500x15 kociek a každá kocka o veľkosti 20 bajtov zaberajú 450MB. Aby sa predišlo týmto problémov, tak sa použil iný prístup. V tomto prístupe sa vybudovala len tá časť L-systému, ktorá bola skúmaná. Aby to bolo možné, tak L-systém už nebol reprezentovaný ako reťazec, ale ako spojitý graf. Taktiež sú axióma aj pravidlá reprezentované pomocou grafov. Obrázok dole zobrazuje graf pre pravidlo.

Pravidlo t(f,s) -> m(f,s)[k(f,s)][t(f,s)]p(s)

Graf obsahuje uzly, ktoré sú nositeľmi informácie o parametroch, ktoré nesú (f,s) ako aj výrazov, ktoré sa na nich aplikujú. Použitím tejto metódy môže byť axióma takýto:

Axióma m(4,6)[k(4,7)][t(4,9)]p(s)

Aplikácia pravidla z obrázku na axiómu z obrázku.

Podľa spôsobu šírenia sa ohňa, je nevyhnutné zahrnúť do L-systému vetviace sa štruktúry. Tie sú reprezentované pomocou symbolov '[' a ']', ktoré tvoria vetvy a potomkov ich rodičovského uzla. Aby sa rozlíšilo, čí sa jedná o uzly potomkov alebo nasledovníkov, tak má každý uzol dve typy liniek: linka nasledovníka a množina liniek potomkov. Spracovanie pomocou L-systému sa vykonáva pomocou rekurzívneho algoritmu. Tu je uvedený jeho pseudokód:

Traverse(graphNode, depth, processor)
Process parameters of graphNode
applicable_rules = find rules applicable to graphNode;
if(depth = 0)
process graphnode
else
for every rule r in applicable_rules
copy parameters from graphNode to RHS of r
traverse(RHS of r, depth - 1, processor)
end for
end if
for every child c of graphNode
traverse(c, depth, processor)
end for
if graphNode has a follower f
traverse(f,depth,processor)
end if
end Traverse