Procedural generation of planetary maps

It will be about cartography dealing with fantastic worlds.

Status of procedural map generation


At the moment, procedural generation of cards is already an extensive topic that has been developed mainly within the framework of the game industry. There are ways to automatically generate various types of cards, from simple images in role-playing and action games to tile-cards in strategy games. The former give an idea of ​​the location of the game and are characterized by a small coverage of the territory, the latter can simulate the vast areas of entire planets, but have little detail.

Methods for creating maps and reliefs for small territories have long been well known:
the median displacement method , the noise function method (Noise Functions) . More recently, an interesting way has appeared based on the division of the plane by Polygonal Map Generation for Games polygons . There is a site that contains links to various resources for the artificial generation of reliefs .

As a rule, most often, the matter is limited to creating textures for modeling the landscape, but no matter how beautiful and spectacular the landscape turns out, this is not yet a full-fledged map.

In general, we will distinguish the relief from the map in the future: we consider the relief to be a kind of texture and have the opportunity to observe it, unlike the relief, we can “touch” the map, this implies that the map objects must be separate entities and there is a certain way in which you can change them . In addition, the presence of a map does not cancel the existence and observation of the relief.

GIS and OpenStreetMap as a way to present fantastic maps


There are many software tools and standards for working with maps of the Earth. Geographic information systems are designed to capture, manipulate, analyze and present all types of geographic data. OpenStreetMap (OSM) is one example of GIS that is designed to collect geographic data and make it freely available.

A wide range of various GIS, as well as many software tools and techniques that appeared as a result of the development of the OpenStreetMap project, just begs to be used to work with maps of fantastic planets. If such already existed as the Earth exists with its surface.

Procedural planet generation


Next, I describe the proposed method for generating the planet (on the fingers). Making a relief on a planetary scale pretty quickly you come to the limits of a computer system. The number of calculations performed increases quadratically with respect to the decrease in the step between grid points on the sphere. This is the main reason why planetary-scale maps were not created. The second reason is the need to implement a global river network and link it to the relief.

Double cone as a sphere approximation


When embarking on this task, the first desire that arises is to avoid the calculation of trigonometric functions, but this is not possible on the sphere. There is a way when, to create a texture on a sphere, it is first drawn on the edges of a regular polyhedron, such as a cube, and then displayed on a sphere. It is clear that the angles of the polyhedron with such a mapping should give distortion. Applying this method to a large planet would cause too noticeable distortion. We will use another variation of this approach.

Without gaps, we display the planet’s sphere on the round cones connected at the base, the equator line, at the same time, should coincide with the line of cones connection. At the end of the process of building the relief on the cones, we do the reverse mapping to the sphere. Of course, distortions cannot be avoided, but by doing the mappings in different ways, it is possible to distribute the resulting distortions differently on the sphere. The good news is that we completely get rid of the calculation of trigonometric functions.

As a working display, we use the option in which the distances along the meridians are saved. Vertically, we avoid distortion altogether, and horizontally the distortions grow linearly, and near the poles the growth of distortions decreases, reaching a maximum of 1.57.

distortion

Such a mapping is well suited to planets with oceans or white spots near the poles. At the equator or at mid-latitudes, it is difficult to visually notice the introduced distortions (the distortions introduced by the selected main grid may be more noticeable).

Two levels of card generation


Even taking into account simplification using conic projection, calculations for the entire planet remain costly in terms of memory consumption. To solve this problem, we resort to two-level generation. First we generate the main or global grid. The main parameter of this grid is the quantity gn, which determines the number of grid divisions at a quarter of the equator equal to 2 gn . The process of generating heights on the main grid reveals the main sections of the creature. It also sets the sea level by the ratio of the number of points falling into land and ocean.

On the examples of the planets that were made, gn = 7. Which is a rather modest amount and, in the process of optimizing the algorithms and building up the hardware, it will be possible to gradually increase gn for new planets.

The process of building the main grid. Divide the equator 4 * 2 gn by points into identical segments of length l, then retreat along the zero meridian the distance l to the north and divide the parallel on which we are located into 4 * (2 gn -1) segments. We continue the process further to the pole, reducing at each iteration the number of points on each subsequent parallel by 4. We do the same with the southern hemisphere. Each global grid point defines a rhombus on a cone (exceptions: pole points that have no comparable rhombuses) and the entire double cone is divided into rhombs. Note that these are rhombuses on the surface of a round cone, and not on a plane. The following figure shows a fragment of the main network of rhombs containing a quarter of the upper cone for gn = 2 (without claiming accuracy, but useful to clarify the point).

mesh

The transition to the grid on double cones leads to an unexpected result: the points of the main grid (without poles) are arranged in an array of dimension 2 gn by 4 * 2 gn . To do this, we first enter the points of the southern cone and the equator into the array, and then place the points of the northern cone on the empty seats on the right, while unfolding them from left to right. As a result, many cone-based algorithms look simpler than their possible counterparts on the sphere.

Here, for example, how the code of a function that simply increases the height of a neighborhood of the south pole with a radius r by one may look like (the real function in the project code looks different, given the more general case).

import Data.Array.Base
    import Data.Array.ST
    typeHeight = InttypeGHeights = UArray (Int,Int) HeighttypeGHeightsMutable s = (STUArrays (Int,Int) Height)-- | Make Heights array mutable
    thawGHeightsArr :: GHeights -> ST s (GHeightsMutable s)
    thawGHeightsArr = unsafeThaw
    -- | Increase values around south pole
    shiftSouth :: GHeights -> Int -> GHeights
    shiftSouth hs r = runSTUArray $ do
        a <- thawGHeightsArr hs
        mapM_ (\y ->
            (mapM_ (\x -> do 
                v <- readArray a (x,y)
                writeArray a (x,y) (v + 1)
              ) [1..4*y])
          ) [1..r]
        return a

When generating a relief on the main grid, we strive to form several significant land areas. Achieving the separation of land into separate sections is important for parallelizing the calculations, since the river system is built for each land section independently. This is the model of the planet that depicts the distribution of the heights of the main grid.

gmesh

To go to the next level, we establish a local grid in each rhombus and build a relief based on the already known heights at the vertices of the rhombus (which belong to the main grid). Thus, the resulting relief will be a kind of multi-fractal.

The main parameter of the local grid is the ln value, which sets the number of grid steps in two directions: 2 ln +1 and 2 * 2 ln +1, respectively. The figure shows an example of a rhombus with a local grid at ln = 3.

lmesh

To generate a relief, an algorithm can be implemented in which only an array of heights of one rhombus is required in the memory . This allows the generation of planets with high resolution map objects.

When implementing projects with complex and multi-stage algorithms, there is often a need to build visual images of intermediate data. Here, for example, is the image of the average size of the island in the process of creating the planet; the division into rhombs is seen with a dashed line.

island model

Rivers and lakes


There is work devoted to the creation of a river system. But the two-level nature of the generation required the creation of specific algorithms that make up the river from separate pieces. Schematic image of the rivers for a small island, see the figure. The final image of the rivers will depend on their full flow at the mouth.

image

Lakes appear as places of local minima in the main grid. The task is to determine the polygon within which this local minimum is contained.

Poetry cards


Several beautiful fragments of maps of non-existent worlds that arise as a result of the implementation of the described algorithm.

image image

image image

image image

Also popular now: