stochastic Lindenmayer systems


Lindenmayer systems

Aims: To implement a graphical demonstration of stochastic Lindenmayer systems and use it to display organic-like structures.

Background:

L-systems or Lindenmayer systems (named after their originator, Aristid Lindenmayer) are grammar-based mechanisms for producing geometric figures. Like a conventional context free grammar, an L-system comprises an alphabet and a set of productions. An initial seed string is used to given as a starting sentential form. Strings are transformed by applying the productions to all viable elements, and the results strings are interpreted using a graphics engine.

Recursive rules may be used to define fractal-like objects, and by attaching probabilities to individual productions we can produce images which mimic some aspects of biological systems, including plant growth.

To succeed in this project, you need to be interested in automata and graphics; and you must possess good programming skills including the use of GUI’s with Java.

Early Deliverables

  1. A set of small worked manual examples of non-stochastic L-systems.
  2. A Java program which interprets strings and draws sequences of line segments.
  3. Write a report surveying classes of L-systems.

Final Deliverables

  1. Demonstrate a working GUI-based L-system environment.
  2. Extend your system to support stochastic productions and show how they can mimic plant growth.
  3. A final report on the project activities, fully acknowledging and citing sources.

Suggested Extensions

  • Investigate the relationship between L-systems and Semi-Thue systems.
  • Extend your system to draw 3-dimensional objects.

Reading

  • The book ‘The algorithmic beauty of plants’ available free from http://algorithmicbotany.org/papers/abop/abop.pdf .
  • Many online resources: start with Wiki