Library: lsystem
Overview

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
Constructors
Lsystem(vars, start, rules, ignore)

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.

parameters
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:

  • "^" previous sibling or parent
  • "<" previous sibling
  • ">" following sibling
  • "]" parent
  • "[" child

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 this reference in the condition function is the Lsystem object.

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 this reference in function f is the Lsystem object. Example: function() { return [ {id:"b"},{id:"c"} ];}.

For a branching L-system there are two choices. The reserved symbols [ and ] can be used as symbols (Ex: return [ {id:"+"},{id:"["},{id:"f"},{id:"]"}];) or you can use nested arrays (Ex: return [ {id:"+"},[{id:"f"}] ]). The only functional difference is that the first (flat) option can only use the < and > directions when doing context sensitive matches. You can effectively delete a symbol by returning an empty array.

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: "" }

methods
properties
Functions
Lsystem.render()
Render the whole current generation. If rendering is going to take a long time then consider using renderBegin, renderHasNext, renderNext[N] methods.
Lsystem.renderBegin()
Begin the render process. Call before renderHasNext, renderNext[N].
Lsystem.renderHasNext()
Determine if there are more modules in the current generation to render.
returns
true if there are more modules to render.
Lsystem.renderNext()
Render the next module in the current generation.
Lsystem.renderNextN(n)
Render the next N modules in the current generation.
parameters
n the number of modules to render. May be more than the actual number of modules left in the list.
returns
the number of modules actually rendered.
Lsystem.reset()
Return the Lsystem to the initial state by assigning the start list to the current generation (curgen). The generation count is reset to zero.
Lsystem.generateN(n)
Produce the next N generations. Use this method when you don't care about rendering the intermediate generations. If this could take a long time you may want to consider using generateBegin/generateNext.
parameters
n the number of generations to produce.
Lsystem.generate()
Produce the next generation. This could take a long time.
Lsystem.generateBegin()
Begin the generate process. Call before generateHasNext, generateNext[N].
Lsystem.generateHasNext()
Return true when there are more modules to generate.
returns
true if more modules
Lsystem.generateNext()
Generate the next generation output for the next module in this current generation.
Lsystem.generateNextN(n)
Generate output for the next n modules. If there are fewer than n modules remaining to process then it stops early.
parameters
n the number of modules to process. May be more than the actual number of modules left in the current generation.
returns
number of modules processed.
Lsystem.setRules(rules)
Set the rules. Usually the rules are set in the constructor but this can be used to change the rules after the fact.
parameters
rules
Lsystem.curgenToString(sep, indent, wrap)
Return a string representation of the current generation
parameters
sep
indent
wrap
Objects
Lsystem.curgen
Array of modules. The current generation.
Lsystem.moduleCount
Number of modules in the current generation. This includes all modules in a tree.
Generated by JsDoc Toolkit 1.3.3 on Wed, 23 Jan 2008 04:55:26 GMT.