In the two years after publishing this, I worked on refining this algorithm to power a real-time world generator, called Generate Worlds, and it lets you design your own 2D and 3D tile sets and explore the worlds they generate in first-person. I have a post that describes it, and it’s available for purchase on itch.io.

Here’s Generate Worlds in action:

This post describes two algorithms for creating complex procedural worlds from simple sets of colored tiles and constraints on the placements of those tiles. I will show that by carefully designing these tile sets, you can create interesting procedurally generated content, such as landscapes with cities, or dungeons with complex internal structure. The video below shows the system creating a procedural world based on the rules encoded in 43 colored tiles.

The image below shows the tile set that generated the world in the video above. The world is annotated to assist in the exercise of imagination required to see it as an actual environment.

We will define a tiling as a finite grid where one of those tiles lies in each grid square. We will further define a valid world as one where the colors along the edges of adjacent tiles must be the same.

This is the only concrete rule for a tiling: tile edge colors must match up. All the higher level structure flows from this.

A valid tiling looks like this:

This is a tiling which is supposed to represent a map with water, beaches, grass, towns with buildings (blue rectangles), and snow capped mountains. The black lines show borders between tiles.

I think this is an interesting way to describe and create worlds because very often, procedural generation algorithms take a top-down approach. L-systems, for instance, rely on a recursive description of an object where the top level, large details are determined before lower level ones. There is nothing wrong with this approach, but I think that it is interesting to create tile sets that are only able to encode simple low level relationships (e.g., ocean water and grass must be separated by a beach, buildings can only have convex, 90 degree corners) and see high level patterns emerge (e.g. square buildings).

## Tiling is an NP complete Constraint Satisfaction Problem

For the reader familiar with constraint satisfaction problems (CSPs), it will already be clear that tiling a finite world is a CSP. In a CSP, we have a set of variables, a set of values that each variable can take on (called its domain), and a set of constraints. For us, the variables are locations in the map, the domain of each variable is the tile set, and the constraints are that tiles must match along their edges with their neighbors.

Intuitively, the problem of correctly creating a nontrivial tiling is hard because the tile sets can encode arbitrary, long range dependencies. Formally, this is an NP complete constraint satisfaction problem when we consider tile sets in general. A naive algorithm for creating tilings would exhaustively search the space of tilings and run in exponential time. The hope is that we can create interesting worlds using tile sets that are solvable using search accelerated by heuristics. The other option is to create tilings that are nearly correct, but may have a small number of incorrect placements. I have found two algorithms that work well with some interesting tile sets, and I describe them below.

## Method 1: Greedy Placement with Backjumping

Keep choosing random locations and place valid tiles there. If you get stuck, remove some and try again.

``````Initialize the entire map to UNDECIDED

while UNDECIDED tiles remain on the map
if any valid tile can be placed on the map
t ``````

Join the pack! Join 8000+ others registered users, and get chat, make groups, post updates and make friends around the world!
www.knowasiak.com/register/