22/06/2024

That sounds like a huge scope, but a lot of code has already been written. Here's a peek a few months into the future if you're worried :

We'll get there eventually. Maybe. Please ignore the aliasing.

Articles about city generation however are rarer. The most influential writing I've seen about city generation outside academia was done by the late Shamus Young and his Pixel City (and its remake in Unity). There was also a lot of work done on (the unpublished) Subversion by Introversion Software.

The goal of these articles is to describe the algorithms I'm using, at a level where casually interested people don't run away screaming, but detailed enough that anyone interested can implement them and get similar results.

Just so you don't have to scroll all the way down to see the result, this is what I end up with.

Due to the nature of the project, I want to be able to generate streets inside an already existing network, *and* use the generated streets as inputs to other generators.

Due to the type of city I want to output, I can't really use a grid. I don't want planned cities like the typical US city. This of course increases the complexity by a lot. But I have something up my sleeve : planar graphs!

If you know your planar graphs, just skip to the start of the algorithm.

- The components of a
*graph*are*nodes*(also called vertices) and*edges* - An
*edge*connects two*nodes* - An
*edge*can have a direction. Ours won't. But they can. - The
*degree*of a node is equal to the amount of edges that connect to that node.

These are graphs :

One node, two nodes, two nodes connected by an edge.

An intersection, and a messy graph.

This one is less messy.

Not all graphs are suited to our purpose. Let's add a few restrictions :

- an edge must connect two
**distinct**nodes. A graph that respects this rule is called a loopless graph. - our graph must be a planar graph.

You cannot untangle this.

It is impossible on a flat plane, because this graph isn't a planar graph, so it has no embedding on the plane. You can do a little trick by bending the sheet of paper and turning it into a torus or a Möbius strip, but that's not a plane.

A city road network is *mostly* a planar graph. Nodes are intersections and edges are street segments. I'm going to completely ignore the existence of bridges and tunnels. Planar graphs have some neat properties that we can use later down the road. To illustrate, look at this map of a random part of Paris and the graph underlying its road structure.

Map overlay from OpenStreetMap

This is what we want to generate.
We create a list containing these starting nodes.

While that list has elements in it :

- Pick the first element and remove it from the list
- Check if that node splits :
- If that node has a split number
*s*>= 1, it splits - If that node has a split number
*s*> 0 and s < 1, it has probability s to split - If the node splits :
- Generate several candidates around it by picking random distances and going around in a circle (between 10 and 16 candidates in these examples)
- For each candidate :
- Check if it is distant enough from every other point (I recommend some kind of spatial structure to speed this up)
- If it is valid, add it as a Node and to the open list, with split number = s-1

Output with : 5 seed nodes, one at the center and one in each cardinal direction. Split number = 3.5

Create an "open" list with at least one point inside the boundary. You can also use the points

While that list has elements in it :

- Pick the first element and remove it from the list
- Generate several candidates around it by picking random distances and going around in a circle
- For each candidate :
*Check if it is in the boundary*- Check if it is distant enough from every other point in the boundary
- If it is valid, add it as a Node and to the open list

Output with a previously built "ring road", a slightly squished ellipse

First, we pick a node at random from the graph.

- If it already has a degree of 4 we remove it from the list.
- Create a street from the node.
- If this process does not create at least one new Edge, remove the Node from the list.
- Repeat until the list is empty

- Pick a direction.
- Pick the "best" node
- Link them together
- Repeat the process until there is no valid node

Unlike in most 3D applications, triangles are bad.

Triangles are not unheard of in cities, but they are at least uncommon. So we just don't allow them. You can if you want. Checking this is simple : does the target node and the origin node both connect to a third one? If so, then it would create a triangle.
The angle shown in red is too small.

This is ugly. Once again, they do exist, but even in real life I think they suck. This is enforced by using a simple dot product between the candidate edge and the edges starting from each of the nodes. If the candidate is too aligned with a existing edge, it is eliminated.

If this "minimum angle" parameter is set to more than 60°, this will also enforce the "no triangle" rule, since a triangle has at least one angle <= 60°.

After some testing, I've found that values between 55° and 65° have the best results. Too low and it looks bad, too high and the generator doesn't connect enough nodes, making the final graph also look bad.

- Alignment with the previous edge (we're trying to create streets, the straighter the better)
- Lower distance

- If the node now has degree 4, then no. It would create a 5-way intersection.
- If the node has degree 3, that means it is intersecting with another street. We can stop or continue.
- If the node has degree 2, the street just met an endpoint for another street. We can stop or continue.
- If the node has degree 1, then it is for now a dead end. We should continue if possible.

This is taking shape.

I mentioned an extra step.
This in essence creates new Nodes that can be used as intersections for the next part of the algorithm. Smaller streets need "anchor points" to connect to the larger streets.

Like I said earlier, a simple step.

Technically we don't

All of this should have generated faces. By its nature, any planar graph with a least one cycle divides the plane in multiple faces. Think of a face as the area the paint bucket would fill in an image editor.

The algorithm to divide our graph into faces is surprisingly simple, anyone who knows how to solve a maze should understand it quickly.

You follow a wall until you come back to your starting point.

If you want to sound cool you can say you're "finding all the chordless cycles in a planar graph".

First, let's note that an edge can be part of at most two faces. One on its right side, one on its left side. Both can be on the same face, it's fine.

Let's make a set containing all edges twice, once for each direction. For the maze analogy, think of it as both walls of the corridor. For an edge, think of it as whether you're going from point A to point B, or point B to point A.

While the set has elements in it:

- Pick an (edge,direction) element
- Follow that edge, taking every time the rightmost edge at every intersection, until you end up where you started
- That's a loop that encloses a face.
- Remove all these (edges,direction) tuples from the set, and add a face containing them to your output.

BOOM.

The power of recursion.

Neat, huh? There's a special face that needs our attention : the outer face. We can't use the method to generate nodes inside a loop here, so we just use the regular generation. The split number is up to you, a higher number means more sprawl, while a number of 0 confines the city to its inner faces.

Note that the outer face gets complicated if your graph isn't connected, so we just assume it is. A graph is *connected* if you can draw a path from any node to any other node.

If you're not happy with that, find all the subgraphs and either connect them together, or just delete the smaller ones. I would suggest doing that during the "remove unconnected Nodes" step.

THE POWER OF RECURSION.

And we're done. Hurray!

The same seed and starting ring road, but with a larger radius.

Starting with a central node and an extra node on each cardinal point.

Starting with a line creates a narrow and long city.

This one uses three seed nodes.

This one too.

A few other cities using the ring road method. I think they look neat.

*Seed*: for obvious reasons. Mostly used to randomly place or choose nodes.*Starting graph*: a set of nodes, or even existing roads, to build the city around (or inside)- (optional) a set of
*Split Numbers*, if using the "nodes around seed nodes" method of generation *Minimum angle*: used during the edge connection. If a potential edge creates an angle smaller than this angle with any other edge from the same intersection, it is eliminated. Values between 55° and 65° give good results.- For every level of recursion :
*Clearance*(node creation): no two nodes should be closer than this distance.*Extension range*(node creation) : the minimum and maximum distance away from the parent node. Should obviously be larger than the clearance value.*Connection radius*(edge creation) : the maximum length an edge can have. Reusing the maximum extension range works fine.*Edge splitting distance*: for every level except the last, this controls the length of every segment when splitting edges.

- I believe it is possible to extend the algorithm to larger structures by extending the "Nodes around seed nodes" system, creating another layer that can recursively use this process.
- We could classify the faces between each recursion level and use different settings/generators depending on their class (eg. a city center face would have denser roads than a suburban face).
- It should be easy to exclude some zones from the generation to account for terrain constraints (rivers, cliffs, lakes, the ocean). Just add some edges delimiting those zones, the no-intersection constraint will automatically route around them.
- Simple tunnels and bridges over/under other roads can be created by taking a degree 4 node and joining its neighbours in opposite pairs.
- More complex tunnels (over water, under a hill) should probably be generated before the city, and given to the generator as part of the seed node set.
- By generating the nodes on a grid instead of randomly and using a higher
*minimum angle*, it should be possible to generate something closer to planned cities (aka the typical US grid city). - We could modify the node generation or scoring function to take into account terrain data, to create variations in street density depending on slope, proximity to water or any cartographical data.

If the above is not a link to the next article, that means it hasn't been written yet. Use whatever method you want to get notified when that happens. It might take a while, I'm a slow writer.

< Back to the Index