L-Systems

[lithander]

A while ago I started to look into L-Systems because their emergent properties really fascinated me. I like how simple rules produce great complexity. There's this great book The Algorithmic Beauty of Plants on modelling plant development through L-Systems. Once you get to parametric, context-sensitve L-Systems the technique really gets powerful beyond "some kind of recursion".

I started writing a script-interpreter so I could try and experiment with the productions from the book. In my script I don't treat L-Systems as formal grammar where commands that control the turtle are symbols in the alphabet. Instead the strings of symbols the L-Systems produces map to named sequences of commands, not unlike what you'd expect from a simple imperative programming language. So, basically you can define procedures and generate procedure calls through L-Systems. But ultimately it's the same thing.

It's fun to play with but I'm not very interested in modelling plants. Have you guys ever used L-Systems for something interesting? I'm trying to come up with ideas how this could be used for procedurally generating content for games (beyond plants) like generating dungeons or citys, monsters, behavior, talent trees, branching storylines... (I'm just making things up on the spot)

[Quendus]

As far as maps go, I've seen one person use them to generate finite Hilbert curves, which didn't look much fun to play. After a short discussion he started using them to make more varied and tactically interesting maps.

The main problem with L-systems for content generation (particularly map generation) is that making small changes to the system can produce large unpredictable changes to the output. If your gameplay puts some requirements on the output (like being bounded by a certain area, having a branching structure, or having a minimal bounding box with a certain aspect ratio) then it can be difficult to predict which L-systems will produce satisfactory output. One way to get around this would be to build the restrictions into the function that translates from strings to output.

[Quendus]

(This is the same reason we don't tend to use iterated function systems like Julia sets to produce game maps)

[lithander]

Hilbert Curves and Julia Sets are really basic. The L-Systems as presented in the book I linked can do a lot more.
For example you can provide conditions that have to be fulfilled before a production triggers. I guess you could put most of the necessary checks (like boundaries) into the conditions. If the structure you want to generate isn't valid it won't be generated.

Lack or unpredictability of variations shouldn't be an issue, either. I wouldn't change the productions at all but tweak the conditions and parameters.

Foo : (rnd() > 0.3) -> Bar
Foo -> Boo


30% of Foo would evolve to Bar and 70% to Boo.

Different seeds would yield different maps with exactly the same rules. Or you could change the threshold (0.3) slightly. If not all seeds produce maps you like you could provide a list of seeds that you know work well. Elite did that.

I guess the biggest problem is, that the idea of turtle-graphics doesn't work to well if you want to operate on a grid and can't have overlapping structures. How would you check for let alone prevent collisions?

But the constraints of Turtle Graphics are not a limitation of L-Systems. I'm sure one could come up with more suited backend (set of available commands and functions that can be used in the condition) if map generation were the purpose.

[Quendus]

Try some experiments and let us know what you come up with!

[naughty]

One of the issues with L-systems is that they are tree-based (data structure tree not real world tree) and a major feature of roguelike maps and most game maps is inter-connectivity which trees are not really great at. Also they are great for making fractals but it can be a big chore to make the rules to generate good plants. A fairly recent idea for plant generation that seems to have many benefits over L-systems is Space Colonisation. It also seems applicable to level generation or could be used along side L-systems.

If you have a solution for the connectivity issue then try it out, because we really do need some more algorithms and techniques for level generation.

I've been working on a level generation system for a while now that is based on Graph Grammars and force based Graph Drawing, which aren't a million miles away from L-systems. Like L-systems you use a set of rules with left-hand patterns and right-hand substitutions but they are graphs instead of sequences or trees of symbols. This does have the benefit of dealing with inter-connectivity quite naturally but has been a challenge to get working (all algorithms for drawing graphs are really bad for trying to make levels with). The paper that originally gave me the idea to use Graph Grammars is Automatic Generation of Dungeons for Computer Games. It only creates graphs from a logical point of view though, it's doesn't layout where the rooms and corridors actually go. That's the bit I have been working on :^)

Here's some screenshots of levels generated from the same ruleset.

[JohnK]

If you want to work on a 2D grid without overlaps you can use the L-System to partition space, rather than picking anywhere to place things. You can do straight binary split or more interesting splits (like get it to generate a grid and/or using only some of the available space).

You then nest the space partitions and eventually convert them into actual things, like rooms(which could be further split for placing items/furniture/monsters). You may need to resort to something else for corridors, or expand the scope of your grammar a bit.

[Paul Jeffries]

Heh, I love that book - I've got an old hardback copy on my coffee table!

Despite that I haven't really used exactly L-systems for generation in a game yet, although my standard method of dungeon generation is based around recursive growth and so is similar in some ways, just not as explicitly rule-based.

I have used them at work though, for generating the architectural geometry of a museum.  Sadly the project was never built but there are some renders of the concept in my presentation at last year's IRDC:

http://prezi.com/m6kameqffgam/real-life-dungeon-generation-procedural-generation-in-architectural-design/

See the three images of the slightly death-star-esque blocky structures in the 'Meta-patterning' section.  Those were generated by starting from a single cuboid and then recursively substituting in other tesselating patterns of cuboids.

[lithander]

Damn, I'm glad I asked. I was close to shelve the project. Now, I got so much new input my vigor is restored!

@Naughty: Hadn't heard of Space Colonisation. (Awesome name) But the longer I think about it the more I see that the problem that technique tries to adress is indeed a problem. At first I thought that something similar could be integrated into the L-System production conditions but the two-passes process of first generating a string of symbols, then executing it is a problem. The conditions for phase one would require knowledge from phase two. Also this approach seems to be based on a breath first execution. Not sure if that's true for all L-System based systems but my implementation is depth first.
The screenshots you posted remind me of Voronoi diagrams. Is this due to how you render the graphs you generated?

@John: Not sure I can follow. Wouldn't interesting splits suffer from the same problem that they overlap in a manner that's hard to control and work with?

@Paul: Looks like you got a real interesting job! Reminds me of this guy: http://www.ted.com/talks/michael_hansmeyer_building_unimaginable_shapes.html

[requerent]

It looks like L-Systems in R-squared have some interesting potential.


You might consider using an L-System for generating hierarchical relationships between rules as a form of procedural rule generation. Or even as a way of generating diverse ecological systems (whereby any given leaf can have a unique algorithm for determining it's relationships with other leaves).


This sort of stuff makes my head hurt though.

[naughty]

@lithander: Well spotted, I am indeed using voronoi diagrams. I use the graph generation phase to create the room-corridor structure then build a set of points for them. Then empty space is filled and voronoi is run over it all.

There are algorithms for adding connections to sets of points that might help solve some of the issues with L-systems. A previous version of my generation system used Relative Neighbourhood Graphs which are quite simple to implement and will add in potential corridors that don;t cross each other. The self-intersection problem with L-systems is a bit trickier though.

Also I think it's totally possible to mix the ideas behind L-systems and Space Colonisation.

[JohnK]

@John: Not sure I can follow. Wouldn't interesting splits suffer from the same problem that they overlap in a manner that's hard to control and work with?

There cannot be any overlap because each rule can only assign out the space it has itself been given (its current 'scope'). Really what I described is just a BSP powered by an L-system (although if you represented space as polygons instead of just rectangles you'd get more variety in how you could split them).

http://johnwhigham.blogspot.co.uk/2012/12/procedural-castle.html and http://procworld.blogspot.co.uk/search/label/L-System have a good exploration of the concept (and are both based on the same paper). They make 3D buildings but 2D should be easier.

[lithander]

If I am to shift my projects goal from rendering fractals to game-map generation I'll have to refactor my code anyway. So why not decouple the L-System code from the domain specific commands and functions completely? Is there anyone interested in some general purpose L-System interpreter in form of a small C++ library? I don't want to make the extra effort in vain but if there's an interest I don't mind to open source it.

[lithander]

I've been thinking a bit on the connectivity problem. Before I can even start thinking about how L-Systems fit into the picture (if at all) I need to find some theory of how connections in cities and dungeons would form.

Consider the picture below. Think of the black lines as roads or tunnels. Now you start building a new one (the red line). Where would you need to stop so the result you generate makes sense in the big picture. I mean we know how a city looks like but what are the rules? Do you know any theories/algorithms regarding that problem? Is this a variant of the "Space Colonisation" approach we discussed earlier? (I see how it applies to trees but don't think the same would work to build web-like structures)



My guess is that you'd continue to build the red line segment until the distance to other segments (green line) become closer then the distance to the origin of the red line. I think you could calulate the point - not locally but if you know the existing line segments (black). I guess that results in an algorithm that will hierarchically partition the space in an efficient and hierarchical way. Has it been done before? (Usually I just keep reinventing wheels with thoughs like that...)

[JohnK]

It's a little unclear, are you trying to make a tree like structure then? How are you determining where the red line starts?

Whatever the goals, putting in a square of fake roads around the edge of your map usually helps with things like this.

This has an air of delaunay triangulation about it, which could split space up and then connect regions with roads in a similar manner.