This post describes the algorithm used in Generate Worlds , a tool that allows users to create and explore procedural worlds by building small sets of voxel tiles. I will give a brief description of the algorithm, and in the following posts I will talk about its advantages in speed and flexibility compared to other methods. To learn more about what constraint-based procedural generation is and what it is interesting in, I recommend reading my previous post .
If you want to test your strengths in creating procedural worlds using this system, you can purchase Generate Worlds. If the price is too high for you, then continue reading: this post will give you information on how to independently implement the Generate Worlds algorithm.
Tile sets
In Generate Worlds, each world is assembled from a set of tiles (tileset). In essence, tiles are just small voxel models. Let's start with an example. The image below is made up of 9 tiles. As you can see, each tile consists of voxels that appear as colored cubes.
If you arrange these voxel models in a logical way, you can create a beautiful pastoral scene, as in the animation shown below. By "logic" I mean that tiles fit together if their colors along the edge of the junction match.
The goal of the Generate Worlds algorithm is to quickly and automatically complete such an assembly. Before embarking on the algorithm, let's look at the statement of the problem.
We connect tiles among themselves
Take a look at the tileset containing 4 tiles:
These tiles are similar to the three-dimensional tiles shown above.
The Generate Worlds algorithm creates valid tile combinations using one simple rule: if two tiles touch each other, all colors along the edge of the touch must match . This rule formalizes the approach used by a living designer to create a 3D world from voxel tiles.
In a permissible combination of the 4 tiles presented above, light cells along the borders should touch only light cells, and a dark cell should touch only dark cells. For example:
Examples of correct and incorrect connections.
The example on the right is unacceptable, because along the edge of the tile touch, the light square touches the dark square. The following are two valid combinations generated for this tileset:
In the general case, creating valid tile combinations is not a trivial task. For example, consider the following simple “greedy” strategy: we start with an empty grid. In each iteration, we place the tile at some point, choosing a tile that is acceptable taking into account the already placed tiles. The diagram below shows the problems of such a strategy.
If we will place tiles without foreseeing how the placement will affect future choices, then the “greedy” algorithm quickly comes to a standstill; in the diagram above, no valid tile can be placed in the red square. And this is the main problem: previous posted tiles can reduce the number of current options to zero. We need some way to protect against placing tiles, which can lead us into a dead end. The algorithm implemented in Generate Worlds starts by considering all the tiles as possible to place at all grid points. If we place one tile in the grid, then it is obvious that some of the future options become inaccessible. After the algorithm eliminates these options, we can reexamine the remaining options and eliminate other tiles that are now incompatible with the smaller number of remaining possible tiles at neighboring points.
Consider the following example. The algorithm starts with a 3x3 grid, in the center of which there is a single tile. The location of this tile implies that 9 possible tiles at neighboring grid points are not allowed, so he discards them and no longer considers them. After deleting these tiles, he can remove the tiles that are incompatible with all the tiles considered to be candidates for placement at neighboring grid points. The red squares in the diagram mark the points at which the tiles are deleted, because they are incompatible with all neighbors that are still being considered. If the algorithm continues this process until there are tiles that can be deleted, then it will come to the state shown in the lower left corner of the circuit. As you can see, many tiles were excluded from consideration. If the strategy for placing tiles consisted only in selecting tiles from these remaining groups, then the probability of getting into a dead end would be much lower than in the “greedy” approach described above.
The problem with this approach is that each time a tile is placed, it requires a costly iterative process. But note that every time I place a tile with an inverted T, those 19 tiles that I removed in the example above can be removed from consideration around this placement. I call the collection of tiles, which remain valid options around the hosted tile, a valid neighborhood of this tile.
Fast tile placement thanks to information caching
The most important principle of the Generate Worlds algorithm is that the information collected about possible tile neighbors can be reused every time this tile is placed. For example, in the case of an inverted T for the eight surrounding squares of the grid, we can remove 19 tiles from consideration immediately after placing this tile by looking at the cached version of the permissible neighborhood for this tile.
For example, in the example below, the algorithm fills the 5x5 grid with tiles using a cached allowable neighborhood of 4 tiles. After placing the first tile, he removes from consideration 19 tiles that were impossible in the example above. After placing each tile, all options that are absent in the acceptable neighborhood of the placed tile are removed from consideration.
Continuing in this way, we can fill the entire grid with only fast local updates to the set of tiles, which are still valid options for each of the points.
Allowable neighborhoods can be any size you need, so you can remove distant incompatible tiles from consideration every time you place a tile. Although the generation of an acceptable neighborhood is rather slow, it needs to be done only once, after which time each linearly depends on the size of the neighborhood to accommodate each tile.
Expanding the system in 3D
The Generate Worlds algorithm naturally expands to worlds having a third dimension. Instead of 2D tiles matching in color with 4 neighboring tiles along common faces, we now have 3D tiles that should match in color with their neighbors along 6 faces. Consider the following 3D tiles:
The assembly of these tiles in 3D is as follows:
In this case, admissible neighborhoods are not two-dimensional, but three-dimensional grids, and the algorithm generates them in a similar 2D case.
Results Gallery
Shown below are the worlds generated by implementations of this algorithm along with brief descriptions.
Screenshot from Generate Worlds showing room with exit. The ledges on the ceiling coincide with the borders of the tiles.
A screenshot from another tool I create that also uses the Generate Worlds algorithm; different types of rooms and corridors are shown.
A world similar to the previous one, but now in a beautiful isometric view
The world, the creation of which I was inspired by the ninth circle of Dante's Hell: sinners who were frozen into the ice. Rendered in MagicaVoxel.
The world, the creation of which I was inspired by the second round of Dante's hell: the landscape irrigated by burning rain, which crosses the bridge. Rendered in MagicaVoxel.
A world of grassy platforms with waterfalls and rivers. Rendered in MagicaVoxel.
Landscape of a medieval city with buildings and walls. Rendered in MagicaVoxel.