I recently got interested in Lindenmayer systems or L-system for short and I also wrote some code. These are generative
systems that generate strings, that in turn can be interpreted as turtle graphics. For example,
you can model koch curves and the famous dragon curve. This book describes how to generate plants which you can see below.
Implementation
For example, given a initial string $+A-Bf$, we have terminal symbols $\{+,-,f\}$ and non terminals $\{A, B\}$ that can still be replaced by rules like $A \rightarrow AfA$, which reads: each A can be replaced in the string. Furthermore, the string $+A-Bf$ can be interpreted by a turtle as $+$: turning right, $-$: turning left, all capital letters mean moving forward drawing a line, and all lower case letters mean moving silently to the next position. We start by defining a symbol class.
case class Symbol(id: Char) {
def isSilent: Boolean = id.isLower
def isTerminal: Boolean = !id.isLetter || id.isLower
}
Next we define a Lindenmayer system as a start string and a set of rules. Given the start string and a depth limit, we can recursively replace all non terminal symbols with the associated rules. This enables us to generate string.
case class LSystem(start: List[Symbol], rules: Map[Symbol, List[Symbol]]) {
private def produce(symbol: Symbol): List[Symbol] =
if(symbol.isTerminal) List(symbol)
else rules(symbol)
@tailrec
private def produce(current: List[Symbol], result: List[Symbol]): List[Symbol] = current match {
case Nil => result
case head :: tail => {
produce(tail, result ::: produce(head))
}
}
@tailrec
private def produce(current: List[Symbol], stepsLeft: Int): List[Symbol] =
if(stepsLeft == 0) current
else produce(produce(current, Nil), stepsLeft - 1)
def produce(depth: Int): List[Symbol] = produce(start, depth)
}
Now we are done with the definition of the grammar system. The only thing left is to define a turtle and
an interpreter that converts strings from L-systems to a sequence of turtles. I define a turtle
by it's posture $[x, y, \alpha]$ where $x,y$ is the turtle's position and the orientation is defined
by the angle $\alpha$. For moving forward the next positions are defined as:
- $x + \delta * cos(\alpha)$
- $y + \delta * sin(\alpha)$
case class Turtle(x: Int, y: Int, angle: Double, sil: Boolean) {
def move(distance: Int): Turtle =
Turtle(
math.round(x + distance * math.cos(math.toRadians(angle))).toInt,
math.round(y + distance * math.sin(math.toRadians(angle))).toInt, angle, false)
def moveSil(distance: Int): Turtle =
Turtle(
math.round(x + distance * math.cos(math.toRadians(angle))).toInt,
math.round(y + distance * math.sin(math.toRadians(angle))).toInt, angle, true)
def turn(by: Double): Turtle = {
Turtle(x, y, (angle + by) % 360, false)
}
def silence: Turtle = Turtle(x, y, angle, true)
Then given a string, we can recursively build a sequence of positions by
applying the action associated with each symbol.
class TurtleInterpreter(moveBy: Int, turnBy: Double) {
import TurtleInterpreter._
private def execute(cmd: List[Symbol], state: Turtle, stack: List[Turtle], drawable: List[Turtle]): List[Turtle] = cmd match {
case Nil => drawable
case RotateRight :: tail => execute(tail, state.turn(turnBy), stack, drawable)
case RotateLeft :: tail => execute(tail, state.turn(-turnBy), stack, drawable)
case PushStack :: tail => execute(tail, state, state :: stack, drawable)
case PopStack :: tail => execute(tail, stack.head.silence, stack.tail, stack.head.silence :: drawable)
case head :: tail => {
val next = if (head.isSilent) state.moveSil(moveBy) else state.move(moveBy)
execute(tail, next, stack, next :: drawable)
}
}
def execute(cmd: List[Symbol], init: Turtle): List[Turtle] =
execute(cmd, init, List.empty[Turtle], List(init))
}
object TurtleInterpreter {
final val RotateRight = Symbol('+')
final val RotateLeft = Symbol('-')
final val PushStack = Symbol('[')
final val PopStack = Symbol(']')
Given that we can define grammars and paint pictures as the ones shown above. I wrote some code that
plots all the above images that can be found on github.
