Category Archives: All

The seditious ideas on how to use vector maps as in-game maps

Lets consider how you can use vector maps in games creating and what difficulties can be in this.

Current state of affairs

The game map of the world is an essential element of many video games of various genres. But even in the most advanced in the technical plan and popular games we see rather low detailed in-game maps. The map is especially important in games with a huge world, where the player need constantly determine his position in the world on the map. In many massive multiplayer online games the game map is a plain image of relief viewed from above and very uncomfortable. There is a natural and long overdue transition from image-maps to high detail vector maps.

On the other hand, if maps must depicture a large territory (even an entire planet) and/or has a high level of details, then the procedural generation of maps has no alternatives. Always keep in mind, that the generated map can always be supplemented with new details or it can be edited manually.

For many standealone and online games, there are map generators. But such generators are designed to produce small-detailed tile maps or each generated world is monotonous and does not correspond to the spherical geometry of a planet. While in massive multiplayer games, because of the difficulty of manually drawing large and detailed maps, game-devs prefer to use the same image of the world for unrelated gaming servers. And the emergence of another world is appeared as a very big event. With procedural generation new large and detailed worlds will become an ordinary event. Furthermore, it will be possible to make the games with a mechanism for generating or loading standardized in-game maps, and the action of different games can occur in the same world. As a universal map format, I propose to use the generally accepted data formats of modern GISs.

Relief (terrain)

The terrain in many games is an integral part of them and the map of a game world is in interrelation with the terrain. During procedural generation of maps, one can build the map on the existing relief (as it is done in this project), consequently the relief and the map will be naturally related.

Output relief data of the project is represented by SRTM hgt data. SRTM data format represents a heightmap, while in the most games the relief is some polygonal mesh. Therefore, the first difficulty is the translation of a heightmap into a polygonal mesh. The most likely solution is to use a heightmap as a base mesh, which can be supplemented with details during the transition to a polygonal mesh. In this case, if details added are smaller than the size of small details of the original relief, then no map adjustment is required.

The presentation of data in the SRTM has a major drawback; it consists in the fact that the data density is changing with the latitude. But we have the entire accumulated arsenal of available tools for SRTM data format. The project internal binary representation of the data that depends on the division of the planet’s surface into rhombuses is nowhere else accepted, so currently I prefer SRTM as the output format.

Vector map

Vector maps are not only provide an opportunity to highlight every detail of the world, but also the ability to change the world itself. And thus, the emergence of games in which the world itself is not only a background, but an active element of the game is possible.

I will give several possible examples which seem to me quite feasible today.

  • Apocalyptic games of various genres. The relief and map change with the development of events: craters and volcanoes appear, continents are flooded or rise.
  • Geographical discoveriesGeographical features are multipoligons and have strictly defined coordinates.
  • Multiplayer strategies. Players themselves arbitrarily set the boundaries of their states, and do not transfer pieces of territory pre-set by a game designer manually. Trade routes can go along rivers or arbitrary roads build by players.
  • Multiplayer role-playing games. Players can build houses, fortresses, dig channels and generally change the face of the world. Player’s home houses or guild’s HQs can be finally placed on the map.
  • Many other types of games with a huge world. One or all of this: the great extent and the variety of the game world, the possibility of terraforming and changing the world itself, really spherical world.

Map presentations

Since the maps are obtained with the help of GIS and are made for GISes, various manipulations with the map are permissible, as well as various representations of maps. What you can see on this site in the section of free maps is by no means the final appearance of maps. You can use different color representations and map types of your choice.

The color style of the free maps on this site was made in the TileMill tool, with the following generation of map tiles with Mapnik.

If you were interested in maps creation, then probably you are familiar with the hillshading type of earth maps. Such a representation of maps can be made with the maps obtained with the project, but in my opinion, satisfactory hillshading maps will be received only when higher resolution maps will be enabled in the project.

Also, by the means of gdal library, you can draw a contour height map (as in a topographic maps). But applying them to the SRTM data of an entire planet can require a very long run time. In my plans to make the height contours in the project itself. Obtained contour data will be included in the standard supply of the planet’s data.

When using the Web Merkator projection area near the poles are strongly stretched horizontally. But it is always possible to choose a different projection, in which the selected territory will have minimal distortion. As an option, it is possible to divide the world into pieces with less distortion (with a suitable projection) and display the map parts instead of the full planet map.

 

The Map Generator

I think it’s time to explain the map generator design. This may shed light on the reasons for taken decisions and can explain the appearance of obtained results. Finally, I hope that the criticism of the approach will help to identify ways to improve the project.

First, the project is almost entirely written in Haskell. At the moment there are about 30,000 lines of Haskell code. The choice of language was due to the fact that it allows you to produce a productive compiled code, and the functional approach ensures a good structuring of this rather complex project.

(Earlier I had dealt with some hypostases of the functional programming, and therefore it was not so difficult for me to master the Haskell at a sufficient level.)

The whole process of planet map generating can be divided into two main stages: generating of planetary relief, and then, obtaining data and drawing the map over the existing terrain. Now we list these stages and their main divisions.

  1. Generation of the initial base relief grid by various methods (fractional brownian motion, generalization of the midpoint displacement method, and functional approach). The resulting grid is then further subjected to the further transformations.
  2. The values of the grid are taken modulo and scaled. Then the sea level value is determined from the given ocean/all planet surface ratio (usually it is around 0.7).
  3. The positions of land mass areas are determined.
  4. In the land areas there are points of local minima (pits) and a significant number of them are eliminated by raising the values of the grid to the level of surrounding points. The remaining pits will serve as a places for possible lakes.
  5. Here, we make the distribution of the height values of the land relief similar to what is observed on the Earth (see Mathematical modelling of mountain height distribution on the Earth’s surface).
  6. We build river-lines relying on the base grid height values, so that each next point of the river-line is not higher than the previous one. As a result, the set of tree like structures of the river-lines is obtained, in which a river-line is the bunch of separate pieces belonging to different rhombuses.
  7. Further, using a special procedure separately in each rhombus we build a relief based on the nearest values of the heights on the river-lines.
  8. At this stage, the values of the heights of the base grid may not coincide with the new values at these points. Therefore we correct the base grid.
  9. Here, the generation of maps begins. First, we create DEM files (Digital Elevation Model Data). Then we generate Geotiff raster tiles for one or more resolutions.
  10. We turn the river-lines into full rivers by giving them a width and smoothing their banks.
  11. The shores of the lakes are determined.
  12. We determine the outlines of land areas and inland waters (these are lakes with a height of the surface at the ocean level; named as lowlakes).
  13. The resulting data is recorded to the spatial database store (PostGIS).
  14. Then we validate all obtained map features and make their correction (with PostGIS tools) if necessary.
  15. Currently we use mapnik with the defined style to generate PNG tiles.

Finally, for visual display we can use one of the web libraries (LeafLet, OpenLayers, etc.)

Next is a few comments on the mentioned stages.

  • At the stage when the base grid of heights is build, the rhombuses is formed on the surface of the cones. In each rhombus we introduce a local grid as mentioned in one of the past posts. And then, ignoring the distortions, we consider a rhombus as a square, and the local grid becomes very similar to the usual grid in the Cartesian coordinate system (although not completely similar; we must take into account the valid proximity of the points to each other). Further we are dealing only with this simplified system of base and local grids.
  • Currentlly,  we avoid situations where planet poles are contaned in land masses. Alse, we avoid land masses laying on the time line (180 degree meridian). This is due to some complexities for the relief generation process, but even more so due to use of map display in Web Mercator projection and possibility of obtaining non-valid map features which are difficult to divide into parts (in left and right hemispheres).
  • If you still intend to locate the continents at the poles, I recommend the transformation of the map data (rotation of the sphere around an arbitrary axis) with the subsequent change of the map projection.
  • In river system constructing we place only one river source in each romb. In order to get very different types of relief on a planet, it is planned to gradually change the number of sources along with the change in numerical parameters of the relief (local fractal dimention and scale).
  • Also in the map data there is no information now to which lake or river this river flows into. While constructing river-lines, this information is available, but when we put a lake on a map, some rivers become an inflow of this lake, instead of a tributary of another river. Valid information should be obtained at the PostGIS level. Which is planned to be done.
  • The resulting map vector data is a ESRI shapefiles which is the generalization of the dBase IV format.

What’s new in ver. 0.2?

The new version of the project used for new free planet maps generation (1, 2, 3).

New cartographic features:

  • Lakes borders are correct now
  • All polygonal features are now multipolygons
  • Result map data consists of ESRI shapefiles, geotiff tiles, and png tiles
  • Almost all features are valid (conform to OGC SFSQL standard). Validity is marked by valid boolean field in a shapefile
  • Lake and landmass features in a shapefile have area field (in square meters)
  • Rivers in a shapefile have mouth flood field (relative integer value; 1 is a minimal flood). Also rivers have contstatus field which denote the feature type that a river flows into (-3 denotes the ocean, -2 denotes a lake, 0 denotes a river). The structure of shapefiles are not final and can be changed in the future
  • All geographic features in shapefiles and in raster data are in EPSG:900913 projection (Web Mercator or Google Web Mercator)
  • New map style

New relief features:

  • Better way to ensure the ocean area on the poles and on the date line

 

Poetry of Maps

Gallery of beautiful fragments of the fictional world maps.

The lakes with islands and the lake-satellites

 

Alpine lakes

 

The origins of the rivers in the snow and the islands off the continent coast

 

The islands and the mouth of the river with the coast fragment

 

The group of islands somewhere in the ocean

The mouth of a river in the bay and the large island nearby

The fragment of a strongly chopped coast

The sea enclosed on all sides

The peninsula with a narrow isthmus

The detached large island

The planet map theory

The following describes a procedure for generating a planet map. Making planetary scale terrain quite quickly come to the limits of a computer system. Number of computations increases quadratically with respect to the decrease in distance between grid points. This is the main reason why planetary scale maps are not available so far. The second reason–the need to implement a global river network and linking it with a relief. Problems arising here are related to the Big Data problems.

The double cone as an approximation of the sphere

The first desire, which arises here, is to avoid the calculation of trigonometric functions, but when dealing with the sphere geometry it is not possible. There is a way to create spherical texture by creating it firstly on the faces of a regular polyhedron, such as the cube, and then mapping it onto a sphere. It is clear that the polyhedron corners should give distortions. Application of this method to a large planet would cause too much noticeable distortions. I’m using a different kind of this approach.

Without breaks we map the sphere of a planet surface on the two round cones conjuncted by their bases on the equator plane. On the next image is the possible sphere and double cone relation (vertical cut); cones height can be different as well as cones base radius, depending on the mapping.

We will do terrain generation process on the two cones and, on the last step, map it on the initial sphere. Of course, the distortions cannot be avoided, but by making the mapping in different ways, it is possible to distribute resulting distortions differently on the sphere. The good news: we completely get rid of the calculating trigonometric functions.

As a working mapping we use the option in which the cones conjunction line coincides with the sphere equator and the distance along meridians preserved. Then the cone length is equal to πR/2, R–the sphere radius. In vertical direction we avoid distortions at all; distortions in horizontal direction grow linearly starting from equator, and near the poles increase of distortions diminish, reaching the maximum π/2≅1.57. Distribution of the horizontal (longitude) distortions are on the figure.

This mapping is well suited to the planets in which the oceans or white spots are near the poles. At the equator or in the middle latitudes distortions are hardly visually observable (the distortion introduced by the selected basic grid may be more noticeable).

Two-level map generation

Even after simplification by using a conical projection, calculations for the entire planet have high memory consumption. To solve this problem, we resort to the two-level generation. At first we generate base or global grid of heights (global height mesh). The main parameter of the grid is gn, which defines the grid divisions number of one quarters of the equator to be equal to 2gn. The process of generating heights on the main grid identifies the planet mainlands. Also, the sea level can be defined here by the ratio of the number of grid points fall into the land or ocean.

Examples of planets made up to present time have gn=7. That is rather modest value and, in the process of algorithms optimization and hardware improvement, we will be able to significantly increase the gn value for new planets.

Now we describe the process of the base grid constructing. Divide the equator with 4*2gn points to the same segments of the length l, then skip on the zero meridian the length l to the north, and divide the current parallel with 4*(2gn-1) points to the same segments of the length l. Continue the process on to the north pole, reducing with each iteration the number of points on each of the following parallels by 4. The same should be done with the southern hemisphere. Each point of the global grid defines a rhombus on the double cones (the pole points are exceptions, they have no corresponding rhombuses), as result all the double cones is divided into rhombuses. Note that these rhombuses are on the surfaces of the round cones, but not on a plane. On the next figure is a view of the quarter of the top cone with a grid of rhombuses for gn=2 (without any claim to accuracy; but it is useful for understanding the base grid).

The transition to the specified base grid on the twin cones leads to an important result: the points of the base grid (without poles) can be arranged in an array of dimensions (2gn, 4*2gn). To do this, allocate points of the southern cone and the equator in an array maintaining their relative positions, and then put the northern cone points in empty array locations, maintaining their relative positions (I also turn each row around, but that is not necessary). As a consequence, many of the algorithms on the cones implementation look easier than their counterparts on the sphere.

A relief on the base grid are usually consists of a few large landmass areas. Achieving the division of the land into separate areas is important for parallelism, as the river system is constructed for each part of the land independently. On the figure is a model depicting the distribution of heights on the base grid.

The next level is the local grid in each rhombus where we build a relief based on the known height values at the vertices of the rhombus (they belong to the base grid). Thus, the final relief will be some type of multi-fractal.

The main parameter of the local grid is ln, which specifies the number of grid steps in two directions: 2ln+1 and 2*2ln+1 respectively. Example of a rhombus with the local grid when ln=3 is on the next figure.

Currently, examples of the planets use the local grid with ln=8.

It is possible to implement the algorithm to generate a planet relief in which only the relief data of one rhombus must be in the memory at all time. Some other data related to the nearby rhombuses also must be present, but it is not as big as compared to all relief data. This allows the generation of a high-resolution planet relief. The further development of the project will allow bigger ln values.

Model the medium-sized island. Rhombuses can be seen here.

Rivers and Lakes

Two-level generation demanded the specific algorithm for rivers which comprises individual pieces. The river construction takes place after creating base height mesh, but before the final relief generation. See schematic representation of the rivers of a small island on the figure.

Lakes emerge as places of local minimum in the base grid. The objective was to determine some polygon which contains this local minimum point.