L-system library
For background information see this and "The Algorithmic Beauty of Plants" available here
An L-system is a production system that repeatedly rewrites symbols according to a set of rules. It is used to draw or model organic systems and fractals. An L-system takes an initial list of symbols and iteratively produces a new list of symbols based on a set of production rules. It can also operate on lists with structure - lists of lists. These are called branching or tree L-systems.
L-systems come in a few different varieties and each is supported by this library. They can be:
- parametric or non-parametric,
- deterministic or non-deterministic,
- context-free or context-sensitive,
- branching (tree) or non-branching (flat)
Each L-system is a combination of one of each of the four options above. For example non-parametric, context-sensitive, non-deterministic, and branching.
A parametric L-system has parameters, (also called arguments) associated with the symbols and a non-parametric one does not. The symbol plus its parameters is called a module. Typically parametric L-systems restrict the parameters to be numbers. This library allows parameters to be any JavaScript type.
A deterministic L-system will have at most one rule that can match a given input module (symbol). A non-deterministic L-system can have more than one rule that matches and a particular rule is selected randomly based on probabilities assigned to each matching rule.
A context-free L-system matches a single input module. A context-sensitive L-system matches based on an input module and its neighbors.
A branching L-system has structure in its list. Each item in the list may be itself a list. A non-branching L-system has a flat list. It seems that this is usually implemented by introducing structural symbols [ and ] but the list remains flat. This library uses a nested list for the branch. Strictly speaking the tree structure implementation is only useful for context-sensitive matching.
An L-system consists of:
- a set of symbols denoted V (traditionally the symbols are single characters such as A or + but
extended here to any unique identifying string). For the L-system to do something useful the symbols
need to have some kind of semantics or behavior. Here the behavior is given by a function associated
with each symbol. A symbol can have zero or one functions associated with it. Think of this function
along with the symbol name as the definition of the symbol. The functions can take arguments. The
symbols processed by the L-system can have any number of arguments associated with them.
The symbol along with its arguments is called a module. Think of the module as an instance of a symbol.
Note: The terms symbol and module are often used interchangeably. The only difference is that a module includes any arguments that go with the symbol. In non-parametric L-systems they are truly the same.
- an initial (starting) non empty list of modules. Each module consists of a symbol from the above set V and zero or more actual arguments. This initial list is the axiom and is denoted w.
- a current list of modules (the current generation) which the L-system is working on. Each
iteration (generation) the L-system reads the current list and replaces it with a new list as
determined by a set of production rules. The current list is initialized with the axiom.
Note: Often the term string is used rather than list. This comes from a simple implementation where the single character symbols are stored in a string. This library uses arrays to implement the lists of modules. This allows easier processing of modules that have parameters or if the symbol is more than one character. It also makes it easier and more efficient to deal with tree structures.
- a set of production rules denoted P. The production rules define how the current list of symbols
starting with the axiom is turned into the next list of symbols. The matching production rules are
applied to each symbol in the current list. A rule consist of:
- a predecessor that matches one or more modules in the current generation. A context free L-system has a single predecessor. A context sensitive L-system matches the current module in the current generation as well as its neighbors. A predecessor has to have the same symbol and same number of arguments to match.
- an optional condition which determines if the rule fires, The condition is a Boolean function which can use any of the arguments in the predecessor. The value of the arguments comes from the actual arguments in the module matched.
- one or more successors. A successor specifies what set of modules will be added to the next generation when the predecessor is matched in the current generation. If there is one successor for each rule then the L-system is deterministic. If there is more than one then it is stochastic or non-deterministic and a specific successor is chosen randomly according to its probability. The successor consists of a probability and a function that returns a list of modules. The function can set the actual arguments in each module using arbitrary expressions involving the actual arguments from the predecessor. The probability is used to determine the chance of this successor being used. The probabilities must sum to 1.
Note: It is possible that more than one rule will match a given input module. This is more common for parametric L-systems where the condition would apply in one case and not another. The first rule that matches is always used. The only way to get stochastic behavior is to specify multiple successors in a single rule.
- A set of skip symbols. These are symbols to ignore while matching context predecessors.
In some descriptions of L-systems a distinction is made between terminal (constant) and non-terminal (variable) symbols. No such distinction is made here. If you want a symbol to be a constant then don't use it on the left hand side of a production rule.
General Processing:
There are two phases in working with an L-system: generation and rendering.
Generation is the process of turning the initial or current generation into the next generation.
Rendering is also known as interpretation. Rendering applies some meaning to the list of modules in the current generation and generates some kind of output. Typically the output is in the form of a visual interpretation of the module list. Rendering is up to you. You provide a function for each symbol that you want to render. That function is given the arguments of the module if the system is parametric and the module has arguments.
The current generation is also called the input list and the next generation is called the output list. This is from the point of view of the production system.
The generation phase works like this:
for each module in the current generation find the first rule that matches if (a match is found) invoke the successor function and append the resulting list to the next generation else when no rule matches the module from the current generation is copied to the next generation
There are two reserved symbols that are always used for a specific purpose. They are [ and ]. Open square bracket ([) begins a branch point. The close square bracket (]) ends a branch level.
- source: lsystem.js
- author: John Snyders
- license: BSD
- version: 0.1
Object Lsystem implements an L-system production system.
Example:
This shows how to translate a traditional symbolic expression of an L-system into the JavaScript of this library.
Fr Fl --> Fr + Fl + Fr Fr --> Fl - Fr - Fl
becomes
var ls = new jjs.Lsystem( { // define the symbols and what they do Fl: function() { t.forward(d); }, Fr: function() { t.forward(d); }, "+": function() { t.left(60); }, "-": function() { t.right(60); } }, // the axiom [ {id: "Fr"} ], [ // the rules { p: [ {id: "Fl"} ], s: function() { return [{id:"Fr"},{id:"+"},{id:"Fl"},{id:"+"},{id:"Fr"}];} }, { p: [ {id: "Fr"} ], s: function() { return [{id:"Fl"},{id:"-"},{id:"Fr"},{id:"-"},{id:"Fl"}];} } ] );
This assumes a object t
in scope that implements turtle graphic functionality and a variable
d that provides a distance to move forward.
vars |
- defines the set of symbols (V) and their behaviors. If a symbol has no behavior then
it can be omitted from vars or the function can do nothing. This is an object where the
symbol names are the object properties and the value of each property is a function that
is called during rendering with the actual arguments of the module. The function's this
variable is the Lsystem object.
Example: { "symbol-id": function (args) { behavior },... } It is possible but not very useful for vars to be an object with no properties. You might do this if some other program consumed the current generation list directly. |
|
start |
- an array of modules that will be used for the initial generation. A module is
an object with properties "id" and "args". Id is the symbol and args is an array of
arguments. If there are no arguments then the args property can be omitted.
Example: [ { id: "symbol-id", args: [arg-values] },... ] |
|
rules |
- a list of rules. Each rule contains a predecessor match pattern p and one or more
successors functions which return the modules for the next generation.
Example: [ rule,... ]
A rule is a predecessor list, an optional condition and a list of successors as follows: Example: { p: [ { dir: direction, id: "symbol-id", a: number-of-args },... ], condition: function(args) { return-boolean-expression }, s: [ {p: probability f: function(args) { return-modules-array } },...] } The first predecessor matches the current module. It is the strict predecessor. The direction must be omitted on the first predecessor and must be present on all the others. The direction is the axis along which to match the symbol. It can be one of:
Any one of the directions can be preceeded with "." to return the starting context to the current module. Example: {id:"Q"},{dir:"<", id:"X"},{dir:".>",id:"Y"} will match symbol Q with a preceding sibling X and a following sibling Y. After the X is matched the current matching position is at the X so the "." prefix is used to set the context back to the Q before looking for the following sibling. Note: in descriptions I have seen there are just two directions that can be matched preceeding (<) and following (>). I choose to get a little more specific. So in examples where you see < used you should translate that to ^. Also make sure that the strict predecessor comes first. id is the symbol to match and a is the arity of the module (number of arguments). A predecessor matches when the ids are equal and the number of arguments (a) matches the number of actual arguments in the module. Example: predecessor { id: "X", a: 3 } matches module { id: "X", args: [1, "seven", {x: 2, y:3}] } because the symbol X is the same and the module has 3 arguments. If there is a single predecessor then the array can be omitted. Ex: p: {id: "A", a: 1} The condition is optional. If present it is a Boolean function
which can use any of the arguments in the predecessor. Arguments are passed to this function
in the same order as the predecessors that they come from. For example: If there are two predecessors,
and the first one has 2 arguments and the second one has 1 argument and the condition takes arguments
X, Y, Z then X gets the value of the first argument of the first predecessor, Y gets the second
argument of the first predecessor and Z gets the argument of the second predecessor.
The The successor defines the modules that go into the next generation. The function f
must return an array of modules. The function can take arguments from the predecessor modules in
the same way as the condition function. The If there is more than one successor then the probability p is used to select one. If there is a single successor then the probability and array can be omitted. Ex: s: function() {...} The rules for each strict predecessor will be evaluated in ranked order. Having a condition is worth a 1000 points and there is one point for each predecessor. The rules are matched from highest to lowest. The first match found is used. |
|
ignore |
- a map of symbols that should be ignored when context matching. this
is optional and can be omitted for a context free L-system. The keys are symbols
and the values are not important.
Example { X: "", Y: "" } |
- render()
- renderNextN(n)
- reset()
- generateN(n)
- generate()
- setRules(rules)
- curgenToString(sep, indent, wrap)
true if there are more modules to render. |
n | the number of modules to render. May be more than the actual number of modules left in the list. |
the number of modules actually rendered. |
n | the number of generations to produce. |
true if more modules |
n | the number of modules to process. May be more than the actual number of modules left in the current generation. |
number of modules processed. |
rules |
sep | ||
indent | ||
wrap |