An introduction to L Systems
Recently I've been taking a look at L Systems. Apparently, they are used for procedural content generation. After playing around with them for a little while, I discovered that you can create some rather cool patterns with them, like this Sierpinski Triangle for instance.
Before we get into how I made the above triangle grow, it's important to understand how an L System works first. The best way to describe an L System is to show you one. Let's start with a single letter:
fNot very interesting, is it? Let's run a few find and replace rules over it. Here are a few I found lying around:
h=f+h+f f=h-f-h
After running those, here's what we got back:
h-f-hHrm. Interesting. What happens if I do it again?
f+h+f-h-f-h-f+h+fAh. Now we're getting somewhere. Here are the next 2 runs for reference:
Run 3:
h-f-h+f+h+f+h-f-h-f+h+f-h-f-h-f+h+f-h-f-h+f+h+f+h-f-hRun 4:
f+h+f-h-f-h-f+h+f+h-f-h+f+h+f+h-f-h+f+h+f-h-f-h-f+h+f-h-f-h+f+h+f+h-f-h-f+h+f-h-f-h-f+h+f-h-f-h+f+h+f+h-f-h-f+h+f-h-f-h-f+h+f+h-f-h+f+h+f+h-f-h+f+h+f-h-f-h-f+h+fNow that we have run it a few times, it's started to really blow up in size. The proper term for the letter we started with is the axiom, and each consecutive run we did with the find and replace rules are really called generations. This is the underlying principle of an L System. While this is cool, I'm sure you're asking how I turned the long string above into the animation at the beginning of this post.
Enter the turtle
For this next part you are going to need a (virtual) pet turtle. My turtle isn't just any turtle - he's a super fast racing turtle that I've trained to follow simple instructions like "go forwards", or "turn right". Now suppose I attach a pen to my turtle so that he leaves a line everywhere he walks.
Now if I give my turtle the following rules and the output from one of the generations above, I'll get back a picture:
f means go forwards one pace
h also mean go forwards one pace
+ means turn right
− means turn left
ignore any other characters
Writing some code
Now that I've introduced how L Systems work and how you can use them to draw pretty pictures, we can start writing some code. I decided to use C♯ to simulate the L System, along with Mono.Cairo to draw the output. Mono.Cairo is a wonderful graphics drawing library that comes bundled along with the Mono runtime as standard.
I decided to split my implementation into 2 classes: the L System and the Turtle. Here's the code for the L System:
using System;
using System.Collections.Generic;
using System.IO;
using System.Runtime.InteropServices;
using System.Security.Policy;
namespace LSystem
{
public class Rule
{
public string Find;
public string Replace;
public Rule(string inFind, string inReplace)
{
Find = inFind;
Replace = inReplace;
}
}
/// <summary>
/// Simulates an L-System.
/// Implemented according to http://www.cs.unm.edu/~joel/PaperFoldingFractal/L-system-rules.html
/// </summary>
public class LSystem
{
public readonly string Root;
private List<Rule> rules = new List<Rule>();
public int GenerationCount { get; private set; }
public string CurrentGeneration { get; private set; }
public Dictionary<string, string> Definitions { get; private set; }
public LSystem(string inRoot)
{
CurrentGeneration = Root = inRoot;
Definitions = new Dictionary<string, string>();
}
public void AddRule(string find, string replace)
{
rules.Add(new Rule(find, replace));
}
public string Simulate()
{
List<KeyValuePair<int, Rule>> rulePositions = new List<KeyValuePair<int, Rule>>();
// Find all the current positions
foreach(Rule rule in rules)
{
List<int> positions = AllIndexesOf(CurrentGeneration, rule.Find);
foreach (int pos in positions)
rulePositions.Add(new KeyValuePair<int, Rule>(pos, rule));
}
rulePositions.Sort(compareRulePairs);
string nextGeneration = CurrentGeneration;
int replaceOffset = 0;
foreach(KeyValuePair<int, Rule> rulePos in rulePositions)
{
int nextPos = rulePos.Key + replaceOffset;
nextGeneration = nextGeneration.Substring(0, nextPos) + rulePos.Value.Replace + nextGeneration.Substring(nextPos + rulePos.Value.Find.Length);
replaceOffset += rulePos.Value.Replace.Length - rulePos.Value.Find.Length;
}
CurrentGeneration = nextGeneration;
GenerationCount++;
return CurrentGeneration;
}
private int compareRulePairs(KeyValuePair<int, Rule> a, KeyValuePair<int, Rule> b)
{
return a.Key - b.Key;
}
/// <summary>
/// From http://stackoverflow.com/a/2641383/1460422
/// </summary>
/// <param name="str"></param>
/// <param name="value"></param>
/// <returns></returns>
private List<int> AllIndexesOf(string str, string value) {
if (String.IsNullOrEmpty(value))
throw new ArgumentException("the string to find may not be empty", "value");
List<int> indexes = new List<int>();
for (int index = 0;; index += value.Length) {
index = str.IndexOf(value, index);
if (index == -1)
return indexes;
indexes.Add(index);
}
}
public static LSystem FromFile(string filename)
{
StreamReader source = new StreamReader(filename);
LSystem resultSystem = new LSystem(source.ReadLine());
string nextLine = string.Empty;
while (true) {
nextLine = source.ReadLine();
if (nextLine == null)
break;
if (!nextLine.Contains("=") || nextLine.StartsWith("#") || nextLine.Trim().Length == 0)
continue;
string[] parts = nextLine.Split(new char[]{'='}, 2);
if(parts[0].StartsWith("!"))
{
// This is a definition
resultSystem.Definitions.Add(parts[0].Trim('!'), parts[1]);
}
else
{
resultSystem.AddRule(parts[0].Trim(), parts[1].Trim());
}
}
return resultSystem;
}
}
}There's quite a lot of code here, so I'll break it down. The most important bit is highlighted on lines 46-69. This Simulate() function takes the current generation and runs all the find and replace rules in parallel. A regular find and replace wouldn't work here because subsequent rules would pick up on new characters are were added when the previous rules added in a single generation.
Other important bits include the Rule class at the top, which represents a single find and replace rule, and the static FromFile() method. The FromFile() method loads a ruleset from a text file like this one, which produces a Dragon Curve:
f
f=f-h
h=f+h
....or this one, which produces a Sierpinski triangle, like the one above:
f
!angle=1.0472
h=f+h+f
f=h-f-h
The line beginning with an exclamation mark is a definition or a directive, which gives the turtle an instruction on how it should do something. They are stored in the string-to-string dictionary Definitions. The turtle class (which I'll show you in a moment) picks up on these and configures itself accordingly.
The turtle class I wrote is not as neat as the above. In fact it's kind of hacky. Here's what I ended up with:
using System;
using Cairo;
using System.Text.RegularExpressions;
using System.Resources;
using System.Collections.Generic;
namespace SimpleTurtle
{
public class Area
{
public double X;
public double Y;
public double Width;
public double Height;
public Area(double inX, double inY, double inWidth, double inHeight)
{
X = inX;
Y = inY;
Width = inWidth;
Height = inHeight;
}
}
public class Turtle
{
private bool strictMode = false;
private string commandQueue;
private PointD position;
private Area bounds;
private double heading;
private double headingStep;
public double HeadingStep
{
get { return headingStep; }
set { headingStep = value; }
}
private double movementStep ;
public double MovementStep
{
get { return movementStep; }
set { movementStep = value; }
}
public Turtle ()
{
Reset();
}
public void ApplyDefinitions(Dictionary<string, string> definitions)
{
foreach(KeyValuePair<string, string> definition in definitions)
{
switch(definition.Key.ToLower())
{
case "angle":
HeadingStep = double.Parse(definition.Value);
break;
}
}
}
public bool Commands(string commandText)
{
// Remove all whitespace
commandText = Regex.Replace(commandText, @"\s+", "");
commandText = commandText.Replace("h", "f");
string okCommands = "f+-";
foreach(char ch in commandText)
{
if(okCommands.Contains(ch.ToString()))
{
switch(ch)
{
case 'f':
Forwards();
break;
case '+':
Turn(false);
break;
case '-':
Turn(true);
break;
default:
if (strictMode) {
Console.WriteLine("The unexpected character '{0}' slipped through the net!", ch);
return false;
}
break;
}
}
else if(strictMode)
{
Console.Error.WriteLine("Error: unexpected character '{0}'", ch);
return false;
}
}
commandQueue += commandText;
return true;
}
public void Draw(string filename, bool reset = true)
{
ImageSurface canvas = new ImageSurface(Format.ARGB32, (int)Math.Ceiling(bounds.Width + 10), (int)Math.Ceiling(bounds.Height + 10));
Context context = new Context(canvas);
PointD position = new PointD(-bounds.X + 5, -bounds.Y + 5);
double heading = 0;
context.LineWidth = 3;
context.MoveTo(position);
foreach(char ch in commandQueue)
{
switch(ch)
{
case 'f':
PointD newPosition = new PointD(
position.X + movementStep * Math.Sin(heading),
position.Y + movementStep * Math.Cos(heading)
);
context.LineTo(newPosition);
position = newPosition;
break;
case '+':
heading += headingStep;
break;
case '-':
heading -= headingStep;
break;
}
}
context.Stroke();
canvas.WriteToPng(string.Format(filename));
context.Dispose();
canvas.Dispose();
if(reset)
Reset();
}
public void Forwards()
{
PointD newPosition = new PointD(
position.X + MovementStep * Math.Sin(heading),
position.Y + MovementStep * Math.Cos(heading)
);
if (newPosition.X > bounds.X + bounds.Width)
bounds.Width += newPosition.X - position.X;
if (newPosition.Y > bounds.Y + bounds.Height)
bounds.Height += newPosition.Y - position.Y;
if (newPosition.X < bounds.X)
{
bounds.X = newPosition.X;
bounds.Width += position.X - newPosition.X;
}
if (newPosition.Y < bounds.Y)
{
bounds.Y = newPosition.Y;
bounds.Height += position.Y - newPosition.Y;
}
position = newPosition;
}
public void Turn(bool anticlockwise = false)
{
if (!anticlockwise)
heading += HeadingStep;
else
heading -= HeadingStep;
}
public void Reset()
{
commandQueue = string.Empty;
position = new PointD(0, 0);
bounds = new Area(position.X, position.Y, 1, 1);
heading = 0;
headingStep = Math.PI / 2;
movementStep = 25;
}
}
}
Basically, the problem I found myself with was that I had to tell Cairo how large the canvas should be ahead of time, before I'd actually finished following all the commands that had been given. In order to get around this, I implemented the commands twice (bad practice, I know!).
The first implementation are the public interface methods, like Commands() (which processes a bunch of commands all at once), and the Forwards() and Turn() methods. The Commands() method follows a bunch of commands, using the private member variables at the top of the Turtle class to keep track of it's position. Each command it understands is then added to a store of valid commands ready for processing by the Draw() function (highlighted, lines 104-140). Whilst processing all these commands, the bounds of the area that the turtle has visited are tracked in the private bounds member variable (highlighted, line 30), which is of type Area (see the class at the top of the file).
The Draw() function creates a new Cairo canvas (lines 106-107) to the size of the bounds calculated previously (plus a bit extra of a border), and replays all the processed commands back on top of it. The final image is then dumped to disk.
After all that, we are missing one last piece of the puzzle: A bridge to connect the two together and provide an interface through which we can interact with the program. This is what I used:
using System;
using System.Collections.Generic;
using System.IO;
class Program
{
public static void Main(string[] args)
{
if(args.Length < 2)
{
Console.WriteLine("Usage: ");
Console.WriteLine(@" ./Simpleturtle.exe <filename> <generations> [<stepCount> [<startingGeneration>]]");
return;
}
int generations = int.Parse(args[1]);
string filename = args[0];
int movementStep = 25;
if (args.Length > 2)
movementStep = int.Parse(args[2]);
int startingGeneration = 0;
if (args.Length > 3)
startingGeneration = int.Parse(args[3]);
LSystem lsystem = LSystem.FromFile(filename);
foreach(KeyValuePair<string, string> kvp in lsystem.Definitions)
{
Console.WriteLine("Setting {0} to {1}.", kvp.Key, kvp.Value);
}
Turtle turtle = new Turtle();
for(int i = startingGeneration; i < generations; i++)
{
turtle.ApplyDefinitions(lsystem.Definitions);
turtle.MovementStep = movementStep;
turtle.Commands(lsystem.CurrentGeneration);
turtle.Draw(string.Format("lsystem_generation_{0}.png", i));
lsystem.Simulate();
File.WriteAllText(string.Format("lsystem_generation_{0}.txt", i), lsystem.CurrentGeneration);
Console.WriteLine("Generation {0} completed.", i);
}
}
}There's nothing too interesting here, just a help message and a parameter reading code. If you put all of this code together, though, you can generate pretty pictures like the ones I showed you above.
This is only the beginning of what you can do with L Systems though. You could extend it to work in 3D, or give your turtle teleporting powers (look half way down) and draw some trees. you could even edit a few characters randomly after completing the main simulation to make every result slightly different. The possibilities are endless!