L-systems

[DemonWasp]

I've been reading about procedural generation recently, and one relatively simple concept I came across was L-systems. They're an easy way to generate repeated patterns, and the Wikipedia article ( http://en.wikipedia.org/wiki/L-system ) is pretty friendly. Below is a Turing implementation of the L-system for the Sierpinski triangle.

Fair warning: it's pretty much instantaneous for 2, 4, 6, 8 or 10 iterations. However, once you get to the 12th iteration, you'll find that it takes several seconds to even calculate the next sequence, then perhaps a couple of minutes to draw the entire thing. It can handle up to iteration 16, but it'll probably take about 20 minutes to draw it.

Use side-lengths of 5 at first, then 1, then about 0.05 for 10+ iterations.

Turing:

%%% % L-Systems are a way of procedurally generating a pattern from a small "seed" % and a few simple rules. This program represents an implementation that will % draw a Sierpinski triangle in increasing resolution over some number of % iterations. % % These kinds of systems are useful in procedural generation of plants (the % purpose they were originally created for) as well as other patterened natural % objects. % % For more information, see: http://en.wikipedia.org/wiki/L-system % % Author: DemonWasp %%% View.Set ("graphics:800;800;") %%% % MAX_ITERS     SEQ_MAX ( 2 * (3^iters + 1) ) % 2             20 % 4             164 % 6             1460 % 8             13124 % 10            118100 % 12            1062884 % 14            9565940 % 16            86093444 % 18            774840980   (Turing complains "size of global variables is too big") % 20            6973568804  (Turing cannot allocate an array this large, as this exceeds maxint) %%% const SEQ_MAX : int := 86093444 %%% % We represent the output of the L-system after some number of iterations as a % "sequence" of characters. We avoid using Turing's string type as it has a % built-in maximum of only 255 characters. %%% type sequence : array 0 .. SEQ_MAX of char var current, next : sequence %%% % Write the string in d to the sequence s at position i and increase i by the % number of characters written. %%% proc append_sequence (var s : sequence, var i : int, d : string)     for c : 0 .. length (d) - 1         s (i + c) := d (c + 1)     end for     i += length (d) end append_sequence %%% % Given some sequence of characters terminated by chr(0), create the % corresponding next iteration in the sequence in the output variable. % This handles applying the rules for the sequence. %%% proc iterate_sequence (s_in : sequence, var s_out : sequence)     var out_pos : int := 0     for i : 0 .. SEQ_MAX         case s_in (i) of             label 'A' :                 append_sequence (s_out, out_pos, "B-A-B")             label 'B' :                 append_sequence (s_out, out_pos, "A+B+A")             label '-', '+' :                 append_sequence (s_out, out_pos, s_in (i))             label :                 exit         end case     end for end iterate_sequence %%% % Draw the given sequence. This handles the "meanings" of each symbol. %%% proc draw_sequence (s : sequence, dist : real)     var x, y, nx, ny, angle : real := 0     for i : 0 .. SEQ_MAX         case s (i) of             label 'A', 'B' :    % draw forward                 nx := dist * cosd (angle) + x                 ny := dist * sind (angle) + y                 Draw.Line (round (x), round (y), round (nx), round (ny), black)                 x := nx                 y := ny             label '-' :         % turn left                 angle -= 60             label '+' :         % turn right                 angle += 60             label :                 exit         end case     end for end draw_sequence % START % This is the "start" under the L-system definition current (0) := 'A' var side_length : real var iteration : int := 2 loop     put "Iteration # ", iteration     put "Enter side length: " ..     get side_length     % Advance two iterations at a time, using a temporary sequence to store the     % odd-numbered sequence (the odd-numbered sequences turn down first rather     % than up and would therefore draw themselves right off the screen).     iterate_sequence (current, next)     iterate_sequence (next, current)     iteration += 2     Draw.Cls ()     draw_sequence (current, side_length) end loop

[klutzedufus]

Wow, this is really cool. Although I didn't understand the code very much, I managed to modify it to run the koch curve (also on the l-systems wikipedia page). This is the kind of thing that I really enjoy learning about and doing. Here's the code:

%%%
% L-Systems are a way of procedurally generating a pattern from a small "seed"
% and a few simple rules. This program represents an implementation that will
% draw a Sierpinski triangle in increasing resolution over some number of
% iterations.
%
% These kinds of systems are useful in procedural generation of plants (the
% purpose they were originally created for) as well as other patterened natural
% objects.
%
% For more information, see: http://en.wikipedia.org/wiki/L-system
%
% Author: DemonWasp
%%%


View.Set ("graphics:800;800;")

%%%
% MAX_ITERS SEQ_MAX ( 2 * (3^iters + 1) )
% 2 20
% 4 164
% 6 1460
% 8 13124
% 10 118100
% 12 1062884
% 14 9565940
% 16 86093444
% 18 774840980 (Turing complains "size of global variables is too big")
% 20 6973568804 (Turing cannot allocate an array this large, as this exceeds maxint)
%%%
const SEQ_MAX : int := 86093444

%%%
% We represent the output of the L-system after some number of iterations as a
% "sequence" of characters. We avoid using Turing's string type as it has a
% built-in maximum of only 255 characters.
%%%
type sequence : array 0 .. SEQ_MAX of char
var current, next : sequence

%%%
% Write the string in d to the sequence s at position i and increase i by the
% number of characters written.
%%%
proc append_sequence (var s : sequence, var i : int, d : string)
for c : 0 .. length (d) - 1
s (i + c) := d (c + 1)
end for
i += length (d)
end append_sequence

%%%
% Given some sequence of characters terminated by chr(0), create the
% corresponding next iteration in the sequence in the output variable.
% This handles applying the rules for the sequence.
%%%
proc iterate_sequence (s_in : sequence, var s_out : sequence)
var out_pos : int := 0
for i : 0 .. SEQ_MAX
case s_in (i) of
label 'F' :
append_sequence (s_out, out_pos, "F+F-F-F+F")
label '-', '+' :
append_sequence (s_out, out_pos, s_in (i))
label :
exit
end case
end for
end iterate_sequence

%%%
% Draw the given sequence. This handles the "meanings" of each symbol.
%%%
proc draw_sequence (s : sequence, dist : real)
var x, y, nx, ny, angle : real := 0
for i : 0 .. SEQ_MAX
case s (i) of
label 'F' : % draw forward
nx := dist * cosd (angle) + x
ny := dist * sind (angle) + y
Draw.Line (round (x), round (y), round (nx), round (ny), black)
x := nx
y := ny
label '-' : % turn left
angle -= 90
label '+' : % turn right
angle += 90
label :
exit
end case
end for
end draw_sequence



% START
% This is the "start" under the L-system definition
current (0) := 'F'

var side_length : real
var iteration : int := 0
loop
put "Iteration # ", iteration
put "Enter side length: " ..
get side_length

% Advance two iterations at a time, using a temporary sequence to store the
% odd-numbered sequence (the odd-numbered sequences turn down first rather
% than up and would therefore draw themselves right off the screen).
iterate_sequence (next, current)
iterate_sequence (current, next)
iteration += 1

Draw.Cls ()
draw_sequence (current, side_length)
end loop