Procedural Generation, you so awesome.

[UPDATE 27.01.15] I’ve recently put up a repository containing code for the following algorithms, as well as working on some other generation algorithms.

So in the last few days/week I’ve been having fun with procedural generation. Specifically 2 concepts, which are L-Systems and DLAs (Diffused Limited Aggregation).

L-Systems are very simple rules imposed on a string, or sequence of stuff. In my simple version where it uses strings, rules could be like:

(X → F-[[X]+X]+F[+FX]-X), (F → FF), which means replace X with F-[[X]+X]+F[+FX]-X, and replace F with FF.

This is the basis of L-Systems. You start with X, and iterate a few times (in this case I iterate 6 times), and the resulting string quickly builds up to something really long, and if you interpet the above rules like this afterwards:

F = draw forward

-/+ = turn left/right 25°

[/] = push/pop current state

You will get:

L System Plant
A plant generated using an L-System.

Next up is DLAs. A DLA is a fancy way of saying “simulate x amount of particles doing brownian (random) motion, and have the stick to other particles that have stuck to something else”. I’m not sure if that made any sense, but here’s the low down in more detail. You have an origin and a target boundary. In the classic case (which will be the first picture), the origin is a circular boundary, and the target is just a point in the center, and then all the particles move randomly. Once a particle touches the boundary, it freezes, and other particles can stick to frozen particles, so they basically just build up around a boundary slowly. But you can of course define whatever kind of boundary you want for both origin and target, and this can make results more interesting (the 2nd picture is a DLA with a rectangular origin boundary, and the 3rd is with a small, circular origin, and a rectangular target boundary).

I’m thinking of using DLAs to generate some maps by just post-processing the points a bit more, for example make joints more rigid by rotating them to be more at 90°, and also connecting nearby points afterwards. The library I have written currently does everything geometrically instead of using pixels and colour values like most demos I found do, so it’s more flexible in terms of what it can do and represent. I definitely suggest people to check these things out, and I just love the idea of making something really simple but having it make you something beautiful and complex.


Leave a Reply

Your email address will not be published. Required fields are marked *