Algorithms of the game Planet

Short description

Planet is a game created by developer Oskar Stalberg which uses procedural generation to create a geodesic sphere as the game’s world. The triangles of the sphere are covered with hand-made tiles that form the surface of the planet, and changes are made to the hidden variables stored for each vertex to create different terrain heights and types. Modules are used to create the different types of terrain, and the game uses tricks to minimize the number of modules needed. The game also includes options for cliffs, coasts, forests, bridges, and cities to create a more immersive world.

Algorithms of the game Planet

I already

more than a year

did not write articles analyzing procedural generation in games. Today we will learn

Planet

is a 2016 game with cozy design by one of my favorite developers, Oskar Stalberg.

Other screenshots

Planet is half technology demo, half game, which creates real magic as a result. It’s not that easy to figure out how it works, but luckily I was able to learn the basic details from Twitter posts and articles from Oskar himself.

It uses many good techniques, most of which were used in subsequent Stalberg projects such as

Bad North

and

Townscaper

. Let’s take a look at how this game works.

Around the World

The most unique feature

Planet

in that its action takes place on the “globe”. It looks round, but in fact the whole world is

geodetic sphere

.

A geodesic sphere is an approximation of a true sphere consisting of single triangles. Triangles have different shapes, but they are approximately equilateral.

IN Planet the triangles of this base geodesic sphere are covered with hand-made tiles that form the surface of the planet. If you look closely at the ocean, you can see these tiles.

The surface of the planet with an approximate indication of individual triangles

All handmade tiles are based on equilateral triangles, so they need to be slightly distorted to match the base sphere, but it’s almost invisible. Since the original tiles are equilateral, they can be connected to each other in a grid of triangles, which simplifies their creation for a seamless connection: at the same time, there is no need to worry about the curvature of the planet at all.

In fact, during the development stage, Oscar experimented with placing tiles on a flat surface.

Planet at the design stage. Unfortunately, the churches did not make it to the final version of the game

Double grid

When a user makes changes to

Planet

, it doesn’t actually change the tiles in use directly. The cursor automatically snaps to the nearest vertex (corner of the triangle) of the base sphere, and each click changes the hidden variables stored for each vertex. There are two variables – height and terrain type.

After changing a vertex, Planet recalculates all the tiles related to that vertex—each triangle has three corners, so we get three sets of two variables to choose which tile to place.

There are usually six triangles with each vertex, but there are rare places with only five. They are easiest to find on the “city” terrain type, because there will only be five gates in these special squares on the city wall.

This style of selection, where the user changes the data in the corners, after which the tiles are selected based on this, is constantly found in Oscar’s works, starting with

Brick Block

. He wrote about him

good twitter post

.

He calls it a “dual grid”, meaning a grid that is made up of a base grid (also called a “primary”). To create a double mesh, you need to draw one vertex in the center of each face of the base mesh. Then draw an edge between two double vertices if the corresponding faces of the base mesh have a common edge. We end up with a new mesh that has one face in the dual mesh for each vertex of the parent mesh, and vice versa.

In this case, the main grid is a geodesic sphere, so the double grid is called a Goldberg sphere.

As you can see, the Goldberg sphere consists of hexagons and 12 pentagons, like a soccer ball. These pentagons correspond to those places

Planet

, where only five triangles surround the point. In fact, the circular outline used in the game simply shows which face of the dual grid the mouse is over.

Selection of tiles

In the earlier Brick Block project, the selection process that takes the data stored in the underlying vertices (or dual faces) and chooses which tile to use is a common algorithm

Marching Cubes

About which I already wrote.

However, Planet works differently. There are 8 possible terrain heights and 4 different terrain types for each of the three corners of the triangle. To account for all the combinations, it is necessary to create different tiles. Even with rotations and reflections, this is too much to create manually and even load the game.

So instead, the game assembles what should cover the entire triangle from a bunch of different hand-crafted pieces called modules. To minimize the number of modules in Planet many tricks are used.

Landscaping

For now, let’s forget about different types of terrain and imagine that we have only grass. The only thing we need to take care of now is the height of the terrain. Remember what’s in the game

No

procedural generation of targets, everything is done by connecting manually created modules.

Planet converts the heightmap to a 3D grid of points and then populates that grid with a process similar to Marching Cubes. This allows us to reuse the same modules at different heights and solve the problem of large height differences thanks to vertical wall segments.

I will illustrate this with a 2D example. Suppose we have a one-dimensional array of heights.

Now let’s draw a grid stretched vertically over this height map, and for each grid point we’ll store a boolean value indicating whether it’s below the corresponding height.

Then we choose what we want to draw, as in the usual marching cubes.

In this two-dimensional case, only a small number of modules is sufficient to cover all combinations.

Extrapolating this to 3D is not very difficult

However, this will require more modules. The only consolation is that in 3D, due to the triangular nature of the base mesh, we need to fill triangular prisms, not cubes. Having only six corners instead of eight greatly reduces the number of combinations.

Cliffs

The tiles above are good for gentle hills. But for sharp cliffs, they look quite awkward, because the foot and top of each hill are at an angle. Therefore in

Planet

there are options for tiles to start and end rapids, that is, adjacent heights with a height difference of 2 or more.

Two-dimensional tiles of rapids

Elevation maps using slopes

In our 2D example we only need 4 tiles, but in 3D there will be quite a few combinations.

Some of the tiles used in Planet

Planet also has a set of tile options for coasts where the terrain meets the ocean at the bottom level of the elevation map.

Other layers

The described trick allows us to choose modules to describe any height map. To provide support for various types of relief in

Planet

it just applies the same trick multiple times, stacking all the modules on top of each other.

First, the game draws a base landscape based on the output heightmap alone. This is the same module regardless of the type of terrain (however, a texture shader is used that colors them differently).

Then a new one is created based on the old height map, all areas without glaciers are assigned a height of 0. This is used to place the glacier modules.

Glaciers follow the same rules as grassy terrain, just with a different set of modules.

Similarly, we create a heightmap to determine where to place city walls (and small houses next to the walls) and trees, filtering the output heightmap accordingly.

Not many wall modules are actually needed (options for different heights not shown)

Misha from the tops

Another trick is used for cities. If you look closely, you can see that every time you place a city, the central buildings are exactly the same.

This block of buildings is simply placed on top of each hill with the city terrain. It is not tied to a specific triangle. This trick helps to visually “break up” the grid, so that the cities look square, instead of triangular and hexagonal, which would catch the eye when connecting triangular tiles. Unfortunately, these buildings often overlap with smaller buildings that are part of the city wall modules, but this is barely noticeable.

Something similar happens with forest tiles.

Bridges

Just as rapids modules depend on the modules vertically adjacent to them, there is a special case for bridge modules that are created only in certain elevation patterns and terrain classes. However, the pattern is larger than a single triangle, so it requires special code to detect it.

In subsequent projects, Oscar used wave function collapse (Wave Function Collapse), which much more intelligently selects mutually consistent tiles without manually adjusting the algorithms. In fact, compared to his later projects, there are far fewer tiles.

Technical art

After placing the basic modules, a significant amount of artistic processing is applied to transform the world into a beautiful and organic one. You may have noticed some tricks:

  • Special ambient occlusion
  • Simulation of fluids for waves on ocean tiles
  • More snow is applied to the tiles near the poles using a shader
  • Volumetric clouds and animated moon, atmospheric glow

By the time this processing is complete, the constituents of the tile planet become almost invisible.

Let’s summarize

It seems to me that Planet is a demonstration of the author’s capabilities. In a sense, it is an intermediate stage between Brick Block and the author’s later projects based on WaveFunctionCollapse, such as Townscaper. However, I think it looks more natural than the others. It shows that it is not necessary to use WFC to implement complex tile selection.

Screenshots taken by Oscar during the development of Planet

Related posts