Tuesday, July 20, 2010
Regular Expressions and L-Systems
Regular Expressions refer to the use of a formal language which can be read by a processor which examines the text and can identify what parts match the provided phrases. Its like a uniform way to parse text and to get information.
AS3 has a RegExp class, for which there are also characters, metacharacters, metasequences(characters or sequences of characters which have special meaning in regular expression), and flags and properties (settings for the matching of the regular expressions).
You can probably see where I'm going with this: if we are going to make an L-system generator, RegExp comes in rather handy:
A sample grammar could be like
F : draw straight forward
L : move forward by this algorithm
+ : rotate right by R degrees (clockwise)
- : rotate left by R degrees (counterclockwise)
[ : PUSH [saves current position, starts new branch]
] : POP [resume last saved position, starts growing again]
N : number of generations
R : rotation (degrees)
X : start point
! : reverse the rotation angle
< : increase line segment length
> : decrease line segment length
my observation from playing around with another recursive ruleset generator, contextfree, is that putting odd shaped boxes on the ends of L systems of 90 degrees gives the resemblance of a city. the end of the "pop" that is where the leaf or cherry of the L system tree is usually placed, so that is where generic box-buildings are placed (if all buildings were to be generic rather than landmarks)
In a similar way one could create a notation for the algorithms for dérives and other exploratory walks around a city:
W : walk straight forward ignoring any turns
+ : next right turn
- : next left turn
EXAMPLE: WWW+W-
(walk down three streets, take a right turn, walk down one street, take a left)
Additional rules could be added, such as for staying on right side or left side of the road pavement, or for the direction that one is to observe, or the manner of one's walk (running, brisk walking, slow meander).
I am beginning to understand why when I first met Vladimir to ask his advice on building a generative map for a tangible touch table, he asked me whether I could do Natural Language Processing. It so happened that a few weeks before that I had just picked up a book on the Natural Language Toolkit and tried to play around with it out of curiosity, so the idea was not alien to me.
Generative code is based on grammars or rules which must be followed - basically in order to program anything, one first has to learn or create the language. It sort of makes me wish I took more linguistics classes back at uni. Linguistics! Something that could have combined both my love for english and my interest in learning programming!
Other links and libraries:
- More info on RegExp here: Regular Expressions Info
- Collision Detection: Port of Grant Skinner's Collision Detection in AS3
- Collision Detection: Corey O'Neil's Collision Detection Kit (CDK) [Example]
- Isometric Projection: Isometric Library for creating isometrically projected content
Iterating an l-system requires only string substitution. Regular expressions provide this functionality, but are overpowered for the task.