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?
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:
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 \ / |
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:
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')
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.
+--------------------+ | | | | | | | 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
@congusbongus answer is excellent, let me add a few things.
Blocks needs to be splitted into building areas according to all the roads that border them. When you have road all around, the overall pattern is a ring. See this link for example : http://oldurbanist.blogspot.fr/2012/01/city-blocks-spaces-in-between.html
( Depending on the density, there might be no space in the ring center, see kowloon ).
Once you have done the blocks, you need to generate the buildings. They are a bit tricky and require a two pass generation. They are partially interdependent : your generator should not create a window that is in front of the next building side wall.
And to add life to this, you may want to influence the generation with the environments like the terrain or an economic map : Roads (except in San Francisco) tends to go around big hills, instead of going straight and the types of houses are heavily influenced by the part of the city they are in.