W2511 Emergence & Lindenmayer Systems (Part 1)

From Coder Merlin
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

Prerequisites[edit]

Research[edit]

Supplemental research[edit]

Experiment[edit]

Begin a new project:

Create an empty project named Lindenmayer within your "project" directory.

cd ~/projects
mkdir Lindenmayer
cd Lindenmayer
swift package init --type executable

Change to the source directory.

cd Sources/Lindenmayer/

Edit the file main.swift.

emacs main.swift

Now, do the following. Be sure to think and plan BEFORE typing.

Design a ProductionRule class such that rules may be constructed using the following syntax:

let productionRules = [ProductionRule(predecessor:"1", successor:"11"),
                       ProductionRule(predecessor:"0", successor:"1[0]0")]

Design an LSystem class such that an LSystem may be constructed using the following syntax:

let lSystem = LSystem(alphabet:["0", "1", "[", "]"], axiom:"0", productionRules:productionRules)

Implement a method for the LSystem class with the below signature which will return a set of all non-terminal (variable) characters in the alphabet. (In the above example, the non-terminals are "0" and "1".)

func nonTerminals() -> Set<Character>

Implement a method for the LSystem class with the below signature which will return a set of all terminal (constant) characters in the alphabet. (In the above example, the terminals are "[" and "]".)

func terminals() -> Set<Character>

Implement a method for the LSystem class with the below signature which will recursively produce the nth generation of the system. (In the above example the third generation would be "1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0".)

func produce(generationCount:Int) -> String

As you're implementing these classes, be sure to validate input. At a minimum:

  1. Defining more than one production rule for the same predecessor is forbidden.
  2. Defining a rule for which the predecessor is not present in the alphabet is forbidden.
  3. Specifying an invalid axiom (i.e. an axiom for which any characters are not present in the alphabet) is forbidden.

If the input is invalid, the program should halt with a fatal error message.

πŸ‘€ See Also[edit]

πŸ“Ί Videos[edit]

Lindenmayer Systems and The Nature of Code
Procedural Plant Generation with L-Systems

πŸ“– Texts[edit]

W2511 Emergence & Lindenmayer Systems (Part 1)
W2512 Emergence & Lindenmayer Systems (Part 2)
W2513 Emergence & Lindenmayer Systems (Part 3)
W2514 Emergence & Lindenmayer Systems (Part 4)

πŸ“š References[edit]



Key Concepts[edit]

Key ConceptsKeyConceptsIcon.png
  • An L-System is a Lindenmayer System
    • It is a rewriting system consisting of:
      • An alphabet of symbols that are used to make strings
      • A set of production rules that are used to expand these symbols into a larger string of symbols
      • An axiom used to construct the initial string
      • A mechanism to translate the generated strings into geometric structures
    • L-systems were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist
    • L-systems are used to model plant cell behavior and growth
  • An L-System is formally defined as a tuple
    • G = (V, Ο‰, P)
    • V is the alphabet, a set of symbols including
      • those that can be replaced, termed variables or non-terminals
      • those that are not replaced, termed constants or terminals
    • Ο‰ is the axiom, a string of symbols from V defining the initial string (generation zero)
    • P is a set of production rules that are applied to generation n to produce generation n+1

Exercises[edit]

ExercisesExercisesIcon.png

Continuing with this project:

  1. Validate your class' functionality by manually testing each of the aforementioned constraints on input.
  2. Validate your class' functionality by testing against the following LSystems:
    1. Algae
    2. Fractal Tree
    3. Cantor Set
    4. Koch Curve
    5. Sierpinski Triangle