L-systems
From GenerativeArt
(Difference between revisions)
The "L" in "L-system" refers to its inventor <em>Aristid Lindenmayer.</em> | The "L" in "L-system" refers to its inventor <em>Aristid Lindenmayer.</em> | ||
| - | An L-system is a grammar based system for describing and generating branching structures | + | An L-system is a grammar based system for describing and generating branching structures that usually exhibit fractal-like self-similarity. |
| - | Such systems produce a string expression | + | Such systems produce a string expression that can be rendered into graphics. The string is essentially a series of commands for moving a virtual pen. The commands are executed from left to right. (From a historical perspective this is similar to Logo's "turtle graphics"). |
| + | |||
| + | |||
| + | <SPAN STYLE="font-size: larger;"><u>System Constants</u></SPAN> | ||
| + | |||
| + | * δ = angle increment | ||
| + | * d = step size (length increment) | ||
<SPAN STYLE="font-size: larger;"><u>Basic Commands</u></SPAN> | <SPAN STYLE="font-size: larger;"><u>Basic Commands</u></SPAN> | ||
| - | |||
| - | |||
| - | |||
* F is move forward with length d with pen down | * F is move forward with length d with pen down | ||
* f is move forward with length d with pen up | * f is move forward with length d with pen up | ||
| - | L | + | L-systems "grow" via iterative string substitution. The system initially has three components. |
| - | |||
| - | Axiom: | + | <SPAN STYLE="font-size: larger;"><u>System Constants</u></SPAN> |
| + | |||
| + | * n = number of times to apply production rules | ||
| + | * δ = angle increment | ||
| + | * d = step size (length increment) | ||
| + | |||
| + | |||
| + | <SPAN STYLE="font-size: larger;"><u>Axiom</u></SPAN> | ||
| + | |||
| + | * an initial string expression typically labeled as "w:" | ||
| + | |||
| + | |||
| + | <SPAN STYLE="font-size: larger;"><u> Production Rules</u></SPAN> | ||
| + | |||
| + | * rules for applying string substitutions typically labeled as p#: and applied "n" times. | ||
| + | * uses the syntax "Sym1 → Str1" meaning "When Symbol 1 is found substitute String 1." | ||
| - | |||
== Null Symbols == | == Null Symbols == | ||
| - | <SPAN STYLE="font-size: larger;"> | + | <SPAN STYLE="font-size: larger;">Adding complexity to production rules</SPAN> |
| - | L Systems can also have symbols | + | L Systems can also have symbols that have no drawing operations associated with them, but add complexity when applying production rules. |
| - | == Branching Structures == | + | == Examples of Branching Structures == |
| - | <SPAN STYLE="font-size: larger;"> | + | <SPAN STYLE="font-size: larger;">How production rules create form </SPAN> |
| - | == L-systems | + | == Stochastic L-systems == |
| - | <SPAN STYLE="font-size: larger;"> | + | <SPAN STYLE="font-size: larger;">L-systems combined with chance operations </SPAN> |
| - | L | + | Like typical L-systems, but with multiple production rules for a single expression, each with a probability. The sum of all the probabilities must total to 1. |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | |||
| - | = | + | <SPAN STYLE="font-size: larger;"><u>Syntax Added to the Production Rules</u></SPAN> |
| - | + | "Sym1 (.#)→ Str1" = "When Symbol 1 is matched there is a .# probability that String 1 should be substituted" | |
| - | |||
| - | |||
<SPAN STYLE="font-size: larger;">Simulating hormones and chemical triggers </SPAN> | <SPAN STYLE="font-size: larger;">Simulating hormones and chemical triggers </SPAN> | ||
| + | |||
| + | |||
| + | Context sensitive L-systems can create signals (sub-strings) that travel the length of the branching structure string as it grows. The signals can, in turn, determine the location of new branches, flowers, buds, etc. | ||
| + | |||
| + | |||
| + | <SPAN STYLE="font-size: larger;"><u>Syntax Added to the Production Rules</u></SPAN> | ||
| + | |||
| + | "*" = matches any symbol | ||
| + | |||
| + | "Sym1 < Sym2 > Sym3 → Str1" = "When Symbol 2 has Symbol 1 to the left and Symbol 3 to the right, substitute String 1 for Symbol 2." | ||
| + | |||
{{SingleImage|imageWidthPlusTen=460|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/lsys/book4.jpg|caption=Context Sensitive L-systems}} | {{SingleImage|imageWidthPlusTen=460|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/lsys/book4.jpg|caption=Context Sensitive L-systems}} | ||
| + | |||
| + | |||
| + | == Genetic L-systems == | ||
| + | |||
| + | <SPAN STYLE="font-size: larger;">Systems that allow the evolution of form</SPAN> | ||
| + | |||
| + | |||
| + | L-systems can be combined with genetic algorithms. It is typically very difficult to start with a given plant or intended form and invent a set of production rules that will produce it. By encapsulating the L-system within an evolutionary system one can "navigate" the design space and guide the system towards the intended result without having to understand or inspect the actual production rules. | ||
| + | |||
| + | For genetic L-systems: | ||
| + | |||
| + | * Initial condition, axioms and production rules must be translated into gene representation | ||
| + | * Genetic operations must be adapted for L System genes | ||
| + | ** Mutation: mutations can be applied to a string converted to a parsed tree representation a la Karl Sims. Care must be taken to not generate syntactically incorrect command strings. | ||
| + | ** Crossover: crossover is even more prone to creating syntax problems. Note again Karl Sims' work with mathematical image processing expressions. Alternately, crossover can be achieved by swapping individual production rules without altering individual production rules. | ||
