21/08/2024

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

Anyway, back to the article.

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)

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.

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.

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.

- City center
- Mixed residential/commercial
- High density residential
- Medium density residential
- Low density residential
- Commercial
- Industrial
- Business
- Park

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.

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.

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

Move an element from

While the list

- If
*open*has elements in it, take one - Else, take an element from
*remaining* - Pick its type
- Add its area to the tally of the assigned zones
- Recalculate the global weights
- For all its neighbors, if they are present in
*remaining*, move them to*open*

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.

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.

For every edge along the block :

- Get the block
*neighbour*on the other side of that edge by querying the table - If that block already has a zone type :
- Query the adjacency table for its weights
- Add all the weights multiplied by the length of the edge

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.

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 :

- IND zones do not like being close to the center : we multiply their weight by 0 until 30% away from the center, then increase it linearly towards 1 at 50%.

- RES : 2
- COM : 1.5
- IND : 0.5

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 :

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 :

- RES : 148 * 2 = 296
- COM : 200 * 1.5 = 300
- IND : 49 * 0.5 = 24.5

- RES : 47.8%
- COM : 48.3%
- IND : 3.9%

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.

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.

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