Hey guys,
In the process of my recent mania with procedurally created content I came across an interesting system called an L-System, which can be used to generate all sorts of organic things using simple rules applied to an L-System string.
I'm not going to try and explain exactly how it works because I suck at explaining such things...
Suffice it to say that L-Systems can be used for many many things in procedural content generation.
Plants, trees, city roads, and many more things... Using the right rules for your system ofcourse.
For an example check out Introversions progress on their next game "Subversion":
http://www.introversion.co.uk/subversion/
They use modified L-Systems for, amoungst other things, the street grid generation. Looks amazing!
For a better explanation of L-Systems, check out the info on wikipedia:
http://en.wikipedia.org/wiki/L-system
And without further delay, here is my snippet which demonstrates some of the more basic L-System Strings:
Algae system (not displayed graphicaly, but it's in the source)
Koch Curve system
Fractal Plant system (the most visually interesting one)
REM *** L-System String generation.
REM *** An experiment by: Martin 'eLeit' Enderleit.
REM *** Date: 22. August, 2009.
set display mode 1680,1050,32 REM - Set display mode to something that works for you.
sync on : sync rate 0
hide mouse
REM - Create a custom type to use for the stack when drawing the fractal plant L-System.
type LSInfo
xpos as INTEGER
ypos as INTEGER
angle as INTEGER
endtype
LS as STRING
iter = 6 REM - If the image doesn't fit the screen, reduce the iterations.
LS = GenerateKoch(iter)
OutputLS(iter,LS)
DrawLSKoch(LS)
ink rgb(255,255,255),0
print "Press any key!"
sync
wait key
cls
print "Generating fractal plant L-System string. Please Wait!"
sync
iter = 7 REM - If the image doesn't fit the screen, reduce the iterations.
LS = GeneratePlant(iter)
cls
OutputLS(iter,LS)
DrawLSPlant(LS)
wait key
end
REM - INFO: Generates an Algae L-System string. The most basic L-System.
REM - Variables: A B
REM - Constants: none
REM - Start: A
REM - Rules: (A -> AB), (B -> A)
function GenerateAlgae(iter as INTEGER)
LS as STRING
TEMP1 as STRING
TEMP2 as STRING
LS = "A" REM - The starting string.
if iter < 1 then exitfunction LS REM - If less than 1 iteration, return the starting string.
for n=1 to iter REM - The number of iterations.
TEMP1$ = LS
LS = ""
LSLEN = len(TEMP1$)
for j=1 to LSLEN REM - Iterate through the current string and apply the rules.
TEMP2$ = mid$(TEMP1$,j)
select TEMP2$
case "A": REM - Rule 1: A -> AB
LS = LS + "AB"
endcase
case "B": REM - Rule 2: B -> A
LS = LS + "A"
endcase
endselect
next j
next n
endfunction LS
REM - INFO: Generates a Koch Curve L-System string.
REM - Variables: F
REM - Constants: + -
REM - Start: F
REM - Rules: (F -> F+F-F-F+F)
REM - Angle: 90 degrees.
REM - Usage: F means draw forward, + means turn right 90 degrees, - means turn left 90 degrees.
REM - NOTE: When generating the string, you have to add the constants as they are... meaning "+" adds a "+"...
REM - At first I thought they where ignored and I didn't add them, and it screwed up the string. :D
function GenerateKoch(iter as INTEGER)
LS as STRING
TEMP1 as STRING
TEMP2 as STRING
LS = "F" REM - The starting string.
if iter < 1 then exitfunction LS REM - If less than 1 iteration, return the starting string.
for n=1 to iter REM - The number of iterations.
TEMP1$ = LS
LS = ""
LSLEN = len(TEMP1$)
for j=1 to LSLEN REM - Iterate through the current string and apply the rules.
TEMP2$ = mid$(TEMP1$,j)
select TEMP2$
case "F": REM - Rule 1: F -> F+F-F-F+F
LS = LS + "F+F-F-F+F"
endcase
case "+":
LS = LS + "+"
endcase
case "-":
LS = LS + "-"
endcase
endselect
next j
next n
endfunction LS
REM - INFO: Generates fractal plant L-System string.
REM - Variables : X F
REM - Constants : + -
REM - Start : X
REM - Rules : (X ? F-[[X]+X]+F[+FX]-X), (F ? FF)
REM - Angle : 25°
REM - Usage: F means draw forward, + means turn right 25 degrees, - means turn left 25 degrees.
REM - [ and ] pushes and pops the position and angle info to and from the stack.
REM - X is only used for controlling the flow of the system, it is not used in the drawing operation.
function GeneratePlant(iter as INTEGER)
LS as STRING
TEMP1 as STRING
TEMP2 as STRING
LS = "X" REM - The starting string.
if iter < 1 then exitfunction LS REM - If less than 1 iteration, return the starting string.
for n=1 to iter REM - The number of iterations.
TEMP1$ = LS
LS = ""
LSLEN = len(TEMP1$)
for j=1 to LSLEN REM - Iterate through the current string and apply the rules.
TEMP2$ = mid$(TEMP1$,j)
select TEMP2$
case "X": REM - Rule 1: X -> F-[[X]+X]+F[+FX]-X
LS = LS + "F-[[X]+X]+F[+FX]-X"
endcase
case "F":
LS = LS + "FF"
endcase
case "+":
LS = LS + "+"
endcase
case "-":
LS = LS + "-"
endcase
case "[":
LS = LS + "["
endcase
case "]":
LS = LS + "]"
endcase
endselect
next j
next n
endfunction LS
REM - Output the L-System string.
function OutputLS(n as INTEGER, LS as STRING)
ink rgb(255,255,255),0
print "n = "+str$(n)+": ";
ink rgb(255,255,0),0
print LS
sync
endfunction
REM - Draw a graphical illustration of the Koch Curve L-System string.
function DrawLSKoch(LS as STRING)
TEMP as STRING
angle as INTEGER
xpos as INTEGER
ypos as INTEGER
oldx as INTEGER
oldy as INTEGER
angle = 0
xpos = 0
ypos = 15
for i=1 to len(LS) REM - Iterate through the L-System string.
TEMP = mid$(LS,i)
select TEMP
case "F": REM - F = Draw forward in the current angle.
oldx = xpos
oldy = ypos
inc xpos, int(cos(angle)*2)
inc ypos, int(sin(angle)*2)
ink rgb(255,0,0),0
line oldx,oldy,xpos,ypos
sync REM - Update the screen.
endcase
case "+": REM - Turn right.
inc angle,90
endcase
case "-": REM - Turn left.
dec angle,90
endcase
endselect
next i
endfunction
REM - Draw a graphical illustration of the fractal plant L-System string.
function DrawLSPlant(LS as STRING)
TEMP as STRING
angle as INTEGER
xpos as INTEGER
ypos as INTEGER
oldx as INTEGER
oldy as INTEGER
index as INTEGER
dim info(0) as LSInfo REM - Create a stack for storing position and angle.
angle = 0-45
xpos = 0
ypos = int(screen height()-1)
index = 0
for i=1 to len(LS) REM - Iterate through the L-System string.
TEMP = mid$(LS,i)
select TEMP
case "F": REM - F = Draw forward in the current angle.
oldx = xpos
oldy = ypos
inc xpos, int(cos(angle)*4)
inc ypos, int(sin(angle)*4)
ink rgb(0,255,0),0
line oldx,oldy,xpos,ypos
sync REM - Update the screen.
endcase
case "+": REM - Turn right.
inc angle,25
endcase
case "-": REM - Turn left.
dec angle,25
endcase
case "[": REM - Push the current Position and Angle to the stack.
info(index).xpos = xpos
info(index).ypos = ypos
info(index).angle = angle
add to stack info()
inc index,1
endcase
case "]": REM - Pop the previous Position and Angle from the stack.
dec index,1
xpos = info(index).xpos
ypos = info(index).ypos
angle = info(index).angle
remove from stack info()
endcase
endselect
next i
undim info()
endfunction
Have fun experimenting!
- enderleit
[href]www.eleit.dk[/href]
