Table of Contents

lsystem  

Summary

A simple implementation of Lindenmayer systems (also called L-systems, substitution systems) is provided. In basic form, a Lindenmayer system consists of a starting string of symbols from an alphabet, and has repeated transitions applied to it, specified by a list of transition search-and-replace rules.

In addition to the standard formulation, two alternative implementations are included: sequential systems, in which at most one rule is applied; and tag systems, in which the transition only takes place at the beginning and end of the string.

Despite being implemented entirely in Python, for reasonable rules on a modern machine the system is capable of running thousands of generations per second. Lindenmayer systems are found in artificial intelligence and artificial life and can be used to generate fractal patterns (usually via mapping symbols from the alphabet to turtle commands), organic looking patterns that can simulate plants or other living things, or even music.

Getting the software

The software is available in a tarball here: http://www.alcyone.com/pyos/lsystem/lsystem-latest.tar.gz.

The official URL for this Web site is http://www.alcyone.com/pyos/lsystem/.

Introduction

Lindenmayer systems consist of strings of symbols from an "alphabet"; in this case, the alphabet is all 8-bit characters. The starting string is called the axiom (and is simply a string). Each generation, zero or more transitions are applied to the string, based on a list of rules. Each rule consists of an "input" and an "output"; the input is the search substring and the output is the substring it is to be replaced with. The ordering of the rules is significant. Null strings are legal as both input and output; if at the input, they will match at every location, and if at the output, the search-and-replace will amount to a delete.

In the basic implementation (the LSystem class), these transitions are done in order. The system scans through the string, checking the substring starting with the current position against each rule's input in order. If that rule's input matches, that substring is substituted with the output string for that rule; thus, the ordering of rules is significant. If no rule matches, that character is left alone and scanning continues.

The first alternative, the SequentialLSystem class, alters this by first scanning rule by rule for any matches, and then only substituting the leftmost. In this way, at most one transition takes place per generation.

The second alternative, the TagLSystem class, also involves only allowing at most one transition per generation, but does it differently: The rules are iterated through in sequence, and the inputs are compared against the beginning of the string; if matched, the output is substituted at the end of the string. In effect the string acts as a read-write head, with the reads at the beginning and the writes at the end.

Use

The LSystem class (and its subclass) implement the following members and functions instance:

.axiom
The initial string that the system is initialized to at generation zero.
.rules
A list of tuples of strings, which represent the transition rules. The order of the elements is significant; each tuple consists of an (input, output) pair.
.string
The current string for this implementation.
.generation
The current generation number. When newly created, the generation starts with zero.
.done
A Boolean variable which indicates whether the system has reached a stable situation, i.e., no more changes will occur.
.reset()
Resets the string back to the axiom.
.step()
Advance one generation through the system.

An LSystem instance, when converted to a string via str, evaluates to its L-system string. Subject objects also act as sequences and can be iterated over, e.g., for char in system: ....

Known issues

  • Python strings (namely their .find and .startswith methods) are used in the implementation as the implementation for the strings; with Unicode strings, this allows a very large alphabet of characters.

Wish list

  • Sample implementations of fractal patterns is an obvious enhancement.

  • Conversion of evolved strings to "file formats," such as turtle commands (via Logo) and other formats would also be in order.

  • Variances of rules over generations is a possibility.

References

  • The Algorithmic Beauty of Plants, Prusinkiewicz, Lindenmayer.

  • A New Kind of Science, Wolfram.

License

This code is released under the GPL. If you use this software, I'd like to know about it.

Release history

  • 1.0; 2002 Jul 29. Initial release.

Author

This module was written by Erik Max Francis.

Version

Version 1.0 $Date: 2002/07/29 $ $Author: max $

Modules and Packages   
lsystem

Lindenmeyer system (L-system) simulator in Python.


Table of Contents

This document was automatically generated on Tue Jul 30 20:51:04 2002 by HappyDoc version 2.0.1