Difference between revisions of "W2511 Emergence & Lindenmayer Systems (Part 1)"
(16 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
= Research = | == Prerequisites == | ||
* Read [https://en.wikipedia.org/wiki/Emergence | * [[W2261 Paths]] | ||
== Research == | |||
* Read [https://en.wikipedia.org/wiki/Emergence Emergence] | |||
* Read [https://en.wikipedia.org/wiki/L-system Lindenmayer System] | * Read [https://en.wikipedia.org/wiki/L-system Lindenmayer System] | ||
* Read [https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols Terminal and Nonterminal Symbols] | |||
* View [https://www.youtube.com/watch?v=f6ra024-ASY L-Systems - The Nature of Code] | |||
* Read [https://developer.apple.com/documentation/swift/set Swift Sets] | |||
=== Supplemental research === | |||
* Read [http://algorithmicbotany.org/papers/#abop The Algorithmic Beauty of Plants] | |||
* Read [http://paulbourke.net/fractals/lsys/ L-System User Notes] (Paul Borke) | |||
== Experiment == | |||
Begin a '''new project''': | |||
Create an empty project named Lindenmayer within your "project" directory. | |||
<syntaxhighlight lang="bash"> | |||
cd ~/projects | |||
mkdir Lindenmayer | |||
cd Lindenmayer | |||
swift package init --type executable | |||
</syntaxhighlight> | |||
Change to the source directory. | |||
<syntaxhighlight lang="bash"> | |||
cd Sources/Lindenmayer/ | |||
</syntaxhighlight> | |||
Edit the file main.swift. | |||
<syntaxhighlight lang="bash"> | |||
emacs main.swift | |||
</syntaxhighlight> | |||
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: | |||
<syntaxhighlight lang="swift"> | |||
let productionRules = [ProductionRule(predecessor:"1", successor:"11"), | |||
ProductionRule(predecessor:"0", successor:"1[0]0")] | |||
</syntaxhighlight> | |||
Design an LSystem class such that an LSystem may be constructed using the following syntax: | |||
<syntaxhighlight lang="swift"> | |||
let lSystem = LSystem(alphabet:["0", "1", "[", "]"], axiom:"0", productionRules:productionRules) | |||
</syntaxhighlight> | |||
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".) | |||
<syntaxhighlight lang="swift"> | |||
func nonTerminals() -> Set<Character> | |||
</syntaxhighlight> | |||
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 "]".) | |||
<syntaxhighlight lang="swift"> | |||
func terminals() -> Set<Character> | |||
</syntaxhighlight> | |||
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".) | |||
<syntaxhighlight lang="swift"> | |||
func produce(generationCount:Int) -> String | |||
</syntaxhighlight> | |||
As you're implementing these classes, be sure to '''validate''' input. At a ''minimum'': | |||
# Defining more than one production rule for the same predecessor is forbidden. | |||
# Defining a rule for which the predecessor is not present in the alphabet is forbidden. | |||
# 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. | |||
{{SeeAlso| | |||
[[Category:Lindenmayer system||Recursion||Production rules]]| | |||
}} | |||
== Key Concepts == | |||
{{KeyConcepts| | |||
* 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 <span style{{Equal}}"background:white;">[https://en.wikipedia.org/wiki/Tuple tuple]</span> | |||
** '''G {{Equal}} (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 == | |||
{{W2511-Exercises}} | |||
{{#set: Has primary media type=Text }} | |||
[[Category:Lindenmayer system]] | |||
[[Category:Recursion]] | |||
[[Category:Production rules]] |
Latest revision as of 20:06, 15 March 2021
Prerequisites[edit]
Research[edit]
- Read Emergence
- Read Lindenmayer System
- Read Terminal and Nonterminal Symbols
- View L-Systems - The Nature of Code
- Read Swift Sets
Supplemental research[edit]
- Read The Algorithmic Beauty of Plants
- Read L-System User Notes (Paul Borke)
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:
- Defining more than one production rule for the same predecessor is forbidden.
- Defining a rule for which the predecessor is not present in the alphabet is forbidden.
- 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]
- 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
- It is a rewriting system consisting of:
- 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]
Continuing with this project:
- Validate your class' functionality by manually testing each of the aforementioned constraints on input.
- Validate your class' functionality by testing against the following LSystems: