This article is only about street generation. However, this is the first part of a longer series that will explore several generation algorithms to create an entire city, down to individual apartments.
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.
Objectives
Motivation
There are quite a few articles about terrain generation. The "Hello, world!" of procedural generation is "Make a heightmap using Perlin/value/gradient/simplex noise". Some people then take the concept up to entire planets, add biomes, oceans, weather, which is very cool.
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.
Desired results
For this algorithm, I want to be able to generate a set of streets that looks like a city map.
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!
I'm not going to bore you with an entire course on graph theory, and you don't even need to understand all of it to understand what I'm doing.
But here's the gist :
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.
It's just a bunch of dots and lines connecting them. Seriously that's it.
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.
What's a planar graph ? It's a graph you can draw on a flat plane (an infinite sheet of paper) without any edges crossing each other. Such a drawing is called an embedding of the graph on the plane.
You might be familiar with the three utilities problem. Draw lines so that each red house is connected to each blue utility without any line crossing.
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.
It can be applied recursively by adding an extra step (splitting edges), we'll see how later.
Generate Nodes
This is the easy part. The goal is to create a bunch of Nodes that are not too close to each other. Here I've detailed two ways to do this.
Nodes around seed points
For this, we start with a set of nodes. We can use any number of them. We also associate a number to each of them, the Split Number. It corresponds to the maximum number of generations this node can create. A node with split number 2 will create nodes with split number 1 which will create nodes with split number 0. A decimal number like 0.4 means that node has a 40% chance to be able to split.
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
Nodes inside a loop
The algorithm is similar, except we remove split numbers and add a boundary check instead.
Create an "open" list with at least one point inside the boundary. You can also use the points on the boundary.
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
Create the Edges
This is the difficult part. But it's not that hard. It's just playing connect the dots to make a pretty shape.
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
Create a street from the Node
From the node :
Pick a direction.
Pick the "best" node
Link them together
Repeat the process until there is no valid node
Picking the best node
This is the core of the algorithm. We evaluate each node within the connection radius and choose one to create an Edge. To do this, we apply multiple constraints.
No crossings
If connecting the two nodes crosses another edge, then it is invalid. This is the only true hard constraint. It's also annoyingly expensive to check, but it's just a bunch of segment-segment intersection tests. This is probably the part that should be optimized the hardest, if you care about speed of generation.
No doubling up
If the two nodes are already connected, don't link them again! Technically this is enforced by the no crossing rule, but this is much faster to check.
No triangles
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.
No small angles
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.
No 5+-way intersections
Once again, not an impossibility, just not very pretty. It's an optional constraint and more up to your sense of aesthetics. It's a very simple check : look at the degree of the candidate node, reject it if it already has degree 4 or more. Done.
Scoring
If there are multiple candidates after all the constraints are applied, we can score each node and pick the best one. What makes a node better?
Alignment with the previous edge (we're trying to create streets, the straighter the better)
Lower distance
We can add other metrics here, but just those two are sufficient. It's actually not that important, the constraints are doing the heavy lifting here.
Repeat the process
Once we have the new node, we move over to that node and record the direction we just took.
Should the street be extended again? We check the degree of the new node.
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.
Remove unconnected Nodes
After this process, sometimes some Nodes are unreachable and unconnected. Those are called isolated nodes. We remove them for the next part.
The Algorithm, Part 2
Don't worry, this is almost over. After everything we have a graph like this :
This is taking shape.
I mentioned an extra step.
Edge Splitting
Let's pick a smaller size for edges, and split all existing edges to that size.
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.
Divide
Now we're going to take advantage of the planar nature of our graph.
Technically we don't have to, but dividing the plane makes it more optimizable.
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.
Conquer
For each face, we do what we did for Part 1, but with smaller distances, using the "nodes inside a loop" algorithm to generate the nodes, and we connect them again. I draw these new edges with a thinner line.
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.
AGAIN
Divide the existing edges into even shorter Edges. Do it again.
THE POWER OF RECURSION.
And we're done. Hurray!
Gallery
Here's a few more outputs, on a larger scale :
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.
Parameters and inputs
This is a generator, so it's better if there's a bunch of knobs to twist and turn to tune the output. Here are the ones I've found were useful :
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.
Further improvements
I haven't had time to explore some possibilities, or I thought they were too distant from my original scope. Here are some of them.
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.
