Block assignment : using adjacency tables

21/08/2024
This is part 2 of a series. Reading Part 1 isn't necessary, but it helps.

Meanwhile...

I'm writing these articles at a completely different time than I write my code. Recently I've been moving all the city generating code to threads so that I can move around while multiple cities are being generated. I also added some ways to generate terrain with decent LoD and looong view distance (fighting pretty hard with depth buffer precision). Placing some hooks for future generations.

Anyway, back to the article.

What we want

We want to use the output of the previous generator : a planar graph representing a city road network.

Just a random city, picked because it's the first one generated by my current build.

We want to use it to create zoning for the blocks in the empty space, a step well known to anyone who has played SimCity or Cities Skylines. You paint the ground with various colors and the game makes buildings appear when the simulated people want them.

Looking at our image above, that would be like taking a paint bucket and filling the zones between streets with various colors. Each color means different types of buildings.

Our desired output (click for large version)

Dividing space into Blocks (again)

What's a block? We venture out of the pure mathematics of Graph Theory and into urban planning. Let's ask Wikipedia.
A city block is the smallest group of buildings that is surrounded by streets, not counting any type of thoroughfare within the area of a building or comparable structure.
That sounds exactly like a face in a planar graph. It's almost like I planned this.

a section of a planar graph with a face in the middle
The polygon in the middle is a face, and represents a city block.

We already know how to divide a planar graph into faces since the first article. It you want a reminder, it's similar to the way you would solve a maze : pick an edge and follow it until you end up back where you started, the set of edges you just followed enclose a face.

For our algorithm we also need a way to find a face's neighbours. To do that, we store for every edge which two faces it separates, and when we need a face's neighbours we look at its edges in that table.

Assigning a type to each Block

We want to divide the blocks into things like residential and commercial and other types so we can call the appropriate structure generators.

How do we do that? With a fairly simple greedy algorithm. The next part is all you really need to understand the core of the algorithm.

For every block, each of its neighbours votes for a zone type, and each neighbour's voting power is proportional to the length of their shared border. The result is picked randomly using the distribution created by the votes.

The main advantage of this algorithm is that it easy to implement and stupidly fast. No backtracking, one single iteration over every block, simple scoring function. This is possible because zoning constraints are mostly soft, making solutions easy to find, and any errors can be chalked up to "humans are weird". Cities are not optimal. They're just... there. So we take whatever solution we get and be happy about it.

There are more advanced algorithms, and the entire thing falls into Optimization problems, which is an entire field of study. I just want to put some paint on some blocks.

Parameters

Zoning types

First, we need a list of types. That's entirely up to whoever is implementing the algorithm. You can look at my list : You can make up whatever list you want. Why did I separate residential like that? I just felt like it. Huge towers usually don't get built in the same block as single-family houses. All the residential + city center types are displayed in red in my example images for clarity though.

Adjacency tables

Next, we make a table of preferences. Essentially, how much do two zones want to be adjacent to each other. A higher number means the two zones are more likely to be found next to each other. The table is commutative because it doesn't make sense for A/B to have a different weight to B/A.

For example, Residential zones have fairly high preferences with each other and themselves, but low preference towards Industrial zones. You don't want your factories next to people's homes. A park is unlikely to be next to another park, but has a preference for residential zones.

The weights in this table are very important. If you want clusters of blocks of type A, you need a high weight in the A/A case. The higher the number, the more dense the clusters for that type will be. If you absolutely cannot have B near A, you need a very negative number in the A/B case. However, too many negative weights can affect the final zone distribution as the generator struggles to find places to put that zone type.

Here's how changing the A/A weights influences clustering :

Left image has A/A weights of 20, right image has A/A weights of 100. The other (positive) weights range from 0 to 10. (click them for full size versions)

Other than the A/A weights, weights should have similar magnitudes, otherwise one zone type might end up dominating the rest, even when taking into account target proportions. There might be a way to normalize them correctly before use, but I have a feeling the words "Markov Chain" might be involved.

Target proportions

We add another set of numbers : how much total space do we want each type to occupy in the city. Want an industrial city? Just crank that dial up. If Commercial zones have a weight of 3 and Industrial a weight of 6, there should be twice as much Industrial area. They should be normalized so they all add up to 1 ; it makes them easier to use later.

Other requirements

Finally, we consider other requirements. In my implementation I have only added one of them : distance from the center. For each zone type, we can associate a function that takes the distance from the center (relative to its size) and returns a weight.

Obviously, the city center zone type will return a high value when close to the center and a low one when far from it, while the industrial zones would rather go on the edge of cities, so the exact opposite.

This is where we could use world data such as elevation, land value, distance from the sea, street traffic.

The algorithm

Gather all the blocks in list remaining, except the outer face (the outer face is the part of the graph that stretches to infinity).
Calculate the total area of the city by adding them all.
Create a tally of the assigned areas by zone type, initializing them to 0.
Create an empty list open.
Move an element from remaining to open (either randomly or by picking a specific block, for example the one closest to the center)
While the list remaining has elements :

And we're done!

Using the neighbours of the current block after each step creates a flood fill effect : this allows each picked block to have at least one edge connected to an already assigned block, instead of assigning random blocks. We want the adjacency table to be used.

Which element of open should be picked at the start of the loop? Depending on your choice, you can end up with a depth-first or breath-first pattern of assignment. I would recommend testing for yourself, one might be better depending on your extra constraints. You could pick depending on a chosen metric (such as "percentage of neighbouring edges already assigned"), but that adds processing time.

Global weights

The global weights are the constantly updated weights that try to nudge the algorithm towards the zone distribution described earlier in "Target Proportions". We want something that increases the weight for a zone if it is underrepresented, and decreases it if it is overrepresented.

With the Target Proportions we calculate how much area each zone type should be assigned.

weight = remainingZoneArea% / remainingTotalArea%

So for example, if for the residential zones, 40% of it is left to assign, but there is only 20% of the remaining city area to be assigned, the global weight for residential zones will be 2.

What does not work is using the target proportions directly in the weights. You'd think that a zone type A with double the area of zone type B should have double the weight, but it screws up clustering on less common types.

Pick a type, any type

We need the table that takes an edge and returns the two blocks it is separating. We also create a table weights that keeps a tally of every zone type we can give our block. It starts at 0 for everything.

For every edge along the block :

For every requirement, multiply each zone type weight by the result of the function for that type.
For every zone type, multiply it by the corresponding global weight.

Finally, pick a zone type using the weights table.

To summarize, every edge along the block influences it proportionally to its length, by looking at the block on the other side. Then the weights are adjusted by their requirements (eg. distance to center) and the desired global distribution.

An example

This might be clearer with an example.

We have a simplified zone type table that only has three types : Residential (RES), Industrial (IND), Commercial (COM). We build the following adjacency table :

RES COM IND
RES 1 0.5 -0.5
COM 0.5 1 0.5
IND -0.5 0.5 1

All three zones like clustering with themselves, RES and IND are incompatible, everything else is average. The table is symmetric along the diagonal.

We also have the following requirement :

And after taking into account already assigned blocks and target proportions, we have these global weights :

Both RES and COM have been under-assigned, while IND has been over-assigned.

Next we want to assign a block marked X, who has 4 neighbours :

part of a graph centered on a face surrounded by 4 other faces, 3 of them colored red,blue and green
A is a Residential Block, B is a Commercial Block, C is an Industrial Block, and D is Unassigned.

We take every neighbouring block and add the weights corresponding to their type, multiplied by the length of the edge connecting them, and we then add them all together.

Block Border Length Type Weight RES Weight COM Weight IND
A 168px RES +168 +84 -84
B 100px COM +50 +100 +50
C 140px IND -70 +70 +140
D 117px None 0 0 0
Total 148 200 140

As additional information, it is 37% away from the center, so we apply the special requirement for IND zones, and end up with a multiplier of 0.35. This brings the weight for IND to 140 * 0.35 = 49.

We then apply the Global Distribution multipliers :

Here they are normalized. We pick one using this distribution and assign it to block X.

COM and RES end up with similar likelihoods : COM has more "votes", but RES has been underrepresented and gets a bigger boost from the global weights.

Finally, we add block D to our list of blocks to process.

Results

These use the same color scheme as the previous screenshots. The green blocks (Industrial) and red blocks (Residential) have negative weights towards each other, so they will avoid clustering, but the weights aren't too negative, so they will sometimes end up as neighbours. It just means the other types of blocks were even less likely, or the random generation picked a low-probability outcome.

Further improvements, limitations and comments

This algorithm is fine for basic zoning, but will fall short on some things. Namely, when using strict "other requirements", the target proportions may not be respected. A "city center" zone type that can only exist in the center, but has no blocks left to be assigned to, is screwed. This can be partly remedied by making their weights roughly inversely proportional to the area they allow the zone to occupy (eg. a zone type that can exist in 50% of the assignable area should have its weight doubled in that area).

For this reason, rare or special blocks should be pre-assigned by another algorithm, since the one presented here does not care if blocks have already been assigned in good spots for other types. These special blocks should still appear in adjacency tables to make their surroundings better.

This process is compatible with manual intervention. You can "seed" the process by placing initial blocks, or modify them after the fact.

This algorithm is order-dependent, preventing use in "infinite" generation. There is a way around this, as you can simply treat the outer faces as "unassigned" or even a special zone type with its own adjacency table. This obviously degrades the quality of the assignements around the edges, but allows you to generate it as independent parts.

One thing I haven't tried is to assign the blocks in order of distance from the center, mimicking a real city. Something to think about.

Next time

A Street is an Edge, a Intersection is a Node. But Streets have width, they're not mathematical objects! Intersections aren't just a dimensionless point!

How do we go from this :

To this?

No grid required.

Next time : Streets and Intersections - Dividing Space and Mesh Generation

That's not a link to the next article? That means I haven't written it yet. Use one of the links below to get notified when something new is published here.

< Back to the Index