Procedural Worlds from Simple Tiles
Advertisement

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.

YouTube video

Advertisement

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.

map explanation

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.

valid pairs

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:

valid tiling

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/
Read More

Advertisement

2 Comments

  1. This is a great write up of the problem space. I've also tried an approach here that converted the tile dependencies into a Boolean constraint satisfaction problem and then used the Open Source clasp (https://potassco.org/clasp/) answer set solver to return valid tilings. The inspiration was from the paper "Answer Set Programming for Procedural Content Generation: A Design Space Approach" (https://adamsmith.as/papers/tciaig-asp4pcg.pdf) which is also a good read.

    Using an answer set solver was nice because it was so easy, I just had to encode the tile constraints and then the solver did all the work, backtracking, etc, but it could be slow, and it could also fail to return (infinite loop). I gave up because it seemed like WFC and similar could return results fast enough for "online" generation, like generating chunks in Minecraft and also because it seemed hard to encode tile probabilities (from some initial example map) like WFC does.