2d - Using L-Systems to procedurally generate cities

I'm currently making an app that focuses a lot on procedurally generated content. So far, I've successfully implemented the procedural generation of the terrain and shape of a map using simplex noise. I'm really pleased with how it looks. Now I'm trying to do the same for cities. I just need to generate a 2D layout of the streets and buildings. I've looked into it and it seems most people suggest using L-Systems. However I can't seem to wrap my head around them. I get the concept, but not the implementation into code. Does anyone have any code examples of L-Systems for procedurally generated cities, or suggestions on other ways to handle the cities?

Answer

L-Systems, from what I can tell*, are a set of grammar-like substitution rules that you can apply recursively to get interesting, "organic" results.

Plants are where L-Systems are often used, as they show a lot of recursive growth (i.e. branch splits off into more branches). For a simple example, I'll show a "lollipop" tree generated using an L-System:

variables : | o              (these are the things that will grow)
start  : o
         |                   (this is what we start with)
rules  : (o → o   o)         (these are the substitution rules that we apply
               \ /            one step at a time)

So at generation 1, we just have the start:

o
|

At generation 2, we follow each of the rules and substitute the existing parts according to the rules. We replace the "balls" with "two-sticks-and-balls":

o   o
 \ /
  |

Generation 3:

o o   o o
 \|   |/
   \ /
    |

Soon we'll have a pretty (crappy) big tree!

To do this in code, you can either do this recursively (i.e. DFS), continually applying the rules on the same parts until you reach some arbitrary end, or you can do this iteratively (i.e. BFS) as we've done in this example, performing one rule "pass" on all the elements and repeating a number of steps. That is:

Recursively:

tree = start
grow(tree, start)


func grow(tree, part)
    if this part of the tree is big enough
        stop
    if part is 'o'
        replace part with 'o\/o'
        grow(tree, the left 'o')
        grow(tree, the right 'o')

Iteratively:

tree = start
for a number of iterations
    for each part in tree
        if part is 'o':
            replace with 'o\/o'

A lot of uses of L-Systems perform the "grow" step using subdivision - that is, the parts keep getting smaller as they are "grown", the bigger parts just get divided. Otherwise your growing system may start to overlap on top of itself. You'll see in my lollipop tree example, I've magically ensured the two branches don't overlap in the middle by changing the shape of the new branches. Let's do the city example using subdivision:

variables: block_vertical block_horizontal road_vertical road_horizontal
start: block_vertical
rules: (block_vertical → block_horizontal road_vertical block_horizontal)

       (block_horizontal → block_vertical road_horizontal block_vertical)

This will make sense in a minute.

Generation 1:

+--------------------+
|                    |
|                    |
|                    |
|        V           |
|                    |

|                    |
|                    |
+--------------------+

A single, boring vertical block. (The V stands for vertical.)

Generation 2: we replace the vertical block with horizontal blocks with a vertical road in the middle

+--------------------+
|       r            |
|       r            |
|       r            |

|   H   r      H     |
|       r            |
|       r            |
|       r            |
+--------------------+

The r stands for road! I've randomly spaced out the split, we don't want boring regular parts in PCG.

Generation 3: we replace the horizontal blocks with vertical blocks split apart with horizontal roads. The existing roads stay; there are no rules for them.

+--------------------+
|   V   r            |

|       r            |
|rrrrrrrr            |
|       r      V     |
|   V   r            |
|       rrrrrrrrrrrrr|
|       r      V     |
+--------------------+

Notice how the roads connect to each other, which is nice. Repeat this enough times and you'll end up with something like this (blatantly ripped off a related answer):

Notice that there are a lot of details I haven't covered, and that this result looks "obviously" generated - real cities look somewhat different. That's what makes PCG fun/hard. There are endless things you can do to tweak and improve your results, but being unrelated to L-Systems, I'll leave this answer here; hope this helps you get started.

_{*- I haven't studied L-Systems formally, although I have encountered specific types like grammars and PCG vegetation; please correct me if I get any definitions or concepts wrong}