Coding - District Map Generation

How about a coding article? It's been quite a long time, so let's have one.
Let's start with some simple.
If "recursive quad splitting" tells you something you can skip the article alltogether, as the algorithm is really only doing that. It's nothing special really.

DISTRICT MAP...
If you look at the structure of district surface maps they basically all look the same : blocks of buildings cut by straight roads. It's no coincidence, there is one algorithm that generate all the districts.

...GENERATION : Generating Blocks
How can we get  this blocky district plan?
Let's start with the whole district rectangle and nothing in it.

Mister District.

We want blocks.
How about cutting this district along two lines?

Cut

The blue lines would split the district in the middle.
That would be not very interesting for the player.
So let's deviate a bit and cut along the red lines.
We obtain 4 smaller rectangles, call them quads a, b, c, d.
a is topleft, b topright, c bottomleft and d bottomright.
Nice.
But b is a bit too small, so let's merge it with a instead.

b merges with a

Let's continue splitting shall we?
We apply the same process we did on the big district rectangle on the smaller quads (recursion).

After Cut+Merge on a,c,d.

We try to split a in 4, but the smaller quads are too small, so we merge the smaller quads and get only two quads a1 and a2. Same with c.
We find d is already too small and decide to not split it further.
We decide that's enough as there has to be an end to this madness.
From these quads we make blocks and give them numbers.

Blocks

... GENERATION : Assigning Blocks.
Looks like your average district map, with the roads and all.
Only thing, the blocks are empty.
So next for each block we decide what to do with them and fill them.

Assigned blocks

h for housing block, p for park.
Different algorithms are used to fill different block types.
Different district types will have different distribution of block types.
That's it.

THE ALGORITHM
The block generation algorithms in pseudo code (image).

MakeBlocks : Making Blocks since 1887

Start the recursion with calling MakeBlocks on the district rectangle.
Block is a class that has a rectangle property and various other content properties that are filled later.

QuadSplit is even more simple, choosing the split lines semi-randomly and doesn't split quads that would be too small ("merge"), enlarging one of the quads and marking the merged one as empty.

End of post.

Tweet