Voxel City Generation

Here I present another old project which I just cleaned up and pushed to GitHub. It is a script that generates a colorful voxel city. Check out the source code. It is not a particularly sophisticated algorithm, but the results look quite pretty, so I figured it would be worthy of a post.

The city is generated in several stages, ordered as shown below:

Generate the floor plan of the neatly-aligned city blocks.
Generate the buildings within each city block.
Give the buildings a random height, random color, and random placement of windows.

Note that rendering is not a part of it. Instead, the city mesh is written to a .vox file, which I render with MagicaVoxel.

Below, I explain the individual stages of generating the city.

City Blocks

The city as a whole has a predefined size for its floor plan, within which the final city should exactly fit. For the city shown above, this floor size is 2000-by-2000 voxels. The city consists of neatly-aligned city blocks. The city blocks, however, need not be equal in size. For example, all city blocks in row $A$ could be 30 voxels high, while all city blocks in row $B$ are 100 voxels high. The only limitation is that all blocks in a single row should have an equal length. Between every two city blocks is a large street, which is always 8 voxels wide. The image below illustrates this.

The height of a city block is randomly determined but should be between 30 and 100 voxels long. One particular valid set $S$ of city block heights thus satisfies:

$(\forall x \in S~.~30 \leq x \leq 100) \land ((\sum_{x \in S} x) + 8 \cdot (\left| S \right| - 1) = 2000)$

Note that the expression to the left of the conjunction constrains the heights of individuals rows, while the right side ensures their sums – combined with the sums of the intercalating streets – end up at a total of 2000 voxels in height.

I determine these bins by iteratively picking randomly-sized lengths $x$ ( $30 \leq x \leq 100$ ). It keeps picking a suitable length until it finds a solution or backtracks when it gets stuck with an invalid set of lengths (i.e., a set that does not satisfy the above expression). While this backtracking causes the worst-case time complexity to be exponential, this proves no issue in practice as the set of satisfying assignments is large enough to find a solution quickly.

After finding the rows for the city blocks, the same principle is applied to generate satisfying widths for the columns. The general layout of city blocks in a city looks akin to the following image:

Neatly-aligned city blocks in a city — City block floor plan (For small 200×200 city)

Building Floor Plan

While we now have neatly-aligned city blocks, they still lack buildings. These buildings should not be so neatly aligned, as it would result in quite an artificial-looking city. Instead, I’d like them to appear somewhat disordered. Generating a disordered building layout requires a new procedure.

The dimensions of individual buildings are constrained. Each building is between 5 and 13 voxels wide and long. Between every two adjacent buildings is a small street with a fixed width of 2 voxels. A new street repeatedly subdivides regions within the city block; this repeats until every region’s dimensions are suitable for a building. Splitting a region is illustrated below.

Splits a region twice at a random offset along a random axis — Split a city block repeatedly along a random axis

A region splits at a random point along a random axis. This procedure repeats on the sub-regions until all sub-regions are of appropriate building size. Similar to before, whenever it gets stuck, it backtracks and tries another split. This process repeats until a solution it finds a solution (or determines surely no solution exists). Finally, it produces a floor plan for a city block that looks similar to the image below.

A single city block filled with buildings — A complete city block

Building Voxels

Now that the buildings have a floor plan, the only thing remaining is to materialize the city’s buildings in a voxel model. Their heights are a random value between 5 and 29. However, as the buildings should also have windows – which can only exist on odd rows – the height of each building must also be an odd number. To illustrate this, see the image below:

The front of a building. Every row of windows is surrounded by solid blocks. — Front view of a building that is 19 voxels high. White rows contain windows.

If the very top or bottom rows had windows, it would look weird (and I don’t want a weird-looking city). Two consecutive rows with windows also look strange. So, buildings have an odd height, and only odd rows may contain windows. Note that the bottom row is row 0.

While the rows for windows are determined, it would be a bad idea to cover the entire building with windows. Generally, not every building’s side gets windows (Sides are north/east/south/west). Every side has a 50% chance of having windows at all. When a side is granted the privilege of having windows, they are randomly placed on the allowed spots. Every spot then has a 50% chance of having a window. If it is given a window, its color is one out of three choices.

Finally, the building exterior should get a nice color. Highly-saturated colors give the city a cheerful appearance. Every generated building color has a high value ( $\geq 128$ ) for at least one color channel (out of R/G/B), while the other channels get a low value ( $\leq 128$ ).

Conclusion

That concludes the general overview of my algorithm for generating a beautiful voxel city. Don’t forget to check out the source code if you’re interested in the details; I extensively documented it. Hopefully this post was useful to you. Here are three more renders of the generated city: