Projections

Following the process from the 2D World Generator the next step is to select some of the larger drainage basins and make them Endorheic basins. This requires the placement of randomly generated shapes for the bodies of water the rivers will drain into, each body should fit within the bounds of the drainage basin without it being cutoff unnaturally by the perimeter of the basin. In order to do this I plan to project the selected basin onto a plane and then use the same method for 2D feature placement that I used previously.

The projection is pretty straight-forward. I find the center of mass of the selected faces or vertices by averaging the points and rotate that position to the top pole of the sphere, from there I just do a straight projection to a plane that is on XZ axis. After the points are projected I can scale the 2D projection to whatever resolution is needed. Below are some of the larger basins in a data set. The first image in each pair is a projection of the vertices while the second image in each pair puts a point at the center of each hex/pentagon face instead. From these it is easy to compare overlays using the projection as a mask to see what features will fit inside, that feature can then be mapped back to the original vertex or hex that the pixel is representing.

These projections will also be useful later for UV mapping and procedural texture generation. The next thing to do is place some bodies of water.

Projections:

Drainage Basins on a Sphere

I haven’t been spending as much time on this project lately. I finally ported the 2D Array Drainage Basin generation code to work with the representation on a sphere. The code turned out to be more concise but it is still a bit slow as I have not written a multi-threaded version yet. This project is going to continue to follow the steps that were used in the 2D World Generator. The next thing to do will be to create endorheic basins, create the continental shelf, run rivers, place lakes and then use all of those to generate the elevation. Hopefully I will be able to get more finished and post more often in the upcoming months.

Sphere Drainage Basins:

Outlined Continents

Been working on converting more of the code to work on a sphere. Managed to get the code to outline edges and identify islands converted. Started porting the start of the drainage basin generation code but haven’t gotten too far yet. Also made some improvements to the viewer. The viewer now renders as points until zoomed in close enough to bother with rendering as polygons. This fixed the frame rates I was getting which were in the 9-14 range, now it ranges from 30 – 100 depending on how much is on the screen. The frame rate is still pretty bad but it is good enough for development purposes and I can focus on the world generation algorithms for now. Planning to continue working on the drainage basin stuff. Here are some shaded samples with the edges outlined. The elevation in these images is just leftover from the continent mask step, it will be replaced in the end by the elevation generated by the drainage basins and rivers.

Outlined Continents:

Continents on a Sphere

Managed to get most of the continent mask generation code ported to work on the surface of a sphere. The general process is the same as what was posted previously for Continent Mask. The differences are that the algorithms must be performed in three dimensions.

The nearest neighbor searching for the Voronoi distance diagram was being generated through a KDTree so no real changes needed to be make this work. The hexes are uniformly spaced so a euclidean distance metric can still be used. Even though a spherical distance calculation would be more accurate it takes longer to compute and the result is the same given the input geometry. The noise algorithms have no issues being calculated in three dimensions instead of two. The part that needed the most changes was the line drawing across the hexes. Drawing lines in a two dimensional array was done using the Bresenham line drawing algorithm. To draw a line across the hexes on a sphere a breadth first search is done where the next hex to process is determined by a choosing the one with the shortest euclidean distance to the target. The same result can be achieved using A* but it takes much longer and is unnecessary in this case because the weight for the edge are all the same.

Continents on a Sphere:

Still need to convert more code to use the graph before I can make the other steps work on a sphere. The next thing to do will be to write the code for subgraph extraction to be able to process pieces of the sphere such as a land mass or body of water independently. The continent masks on the sphere currently do not eliminate inland water which is necessary for the process of drainage basin generation that I am using.

Many Changes

I have decided to change the direction of my world generation project slightly. I am quite happy with most of the results I have created so far. I would like to expand these to work mapped onto a sphere instead of a plane. There are a few reasons for doing this:

  • I prefer the use of hexagons to squares for any game I eventually build on top of it.
  • The hexagons are superior for simulation of many things like wind or tectonic plates.
  • Haven’t seen many other projects doing it.
  • Seems like an interesting challenge.

The first step of this process is to create the base geometry for the world and its cells. I based my algorithms for this off of material collected from this link about Discrete Global Grids. To summarize I started with an Icosahedron and implemented 2 different methods to subdivide it. The next step is to subdivide into a Truncated Icosahedron. From there I can continue to subdivide using either method until I reach the desired resolution.

Subdivision Samples:

The next step is to develop a decent camera control for navigating and zooming on the map. After this is complete I will begin to port my code that I have developed in Java to C++ and use the new world structure. For now I am just coloring faces to denote different information. Eventually I plan to make it more interesting visually but that is a long ways off.

The other change I have made is switching languages from Java to C++. Currently I am using Boost and SFML with it. Some of my reasons for making this change are:

  • Make my program more accessible. Many of the results as seen with the Tiled maps are difficult to output to an easy to view format because of the scale of the data. This way I can just post executables and data files that are more suited to viewing my results.
  • People won’t need to download a JRE.
  • Access to Boost library.
  • More flexibility when tweaking for performance.
  • I do plenty of Java development at work, this keeps things interesting and sharpens my skills.

Tiled & New Features

Over the last couple days I got around to writing an encoder for my world generator to write files for Tiled. This gives a lot more detailed view of what the world looks like compared to the bitmaps i had been using previously. I created a pretty basic tile set which is similar to the one used by dwarf fortress for the overland map. I hope to find/make more attractive tiles at some point.

If you download these two files the .tmx file can be loaded and viewed in Tiled:
Tiled .tmx file
Tile set.

If you don’t have Tiled:
Warning ! Big Image (5.73 MB 16384×16384 Pixels)
Rendered Image

I have also been adding the ability to place special features on the map based on different criteria. Some of these are already in the map above:

  • Glaciers : Placed in mountain regions where there is a river source.
  • Swamp/Marsh: Placed along rivers in all biomes that have vegetation. Swamps for forest biomes, marshes for grasslands biomes.
  • Flood Plain: Placed where rivers empty to the ocean for grasslands and desert biomes.

The next steps are to add more features to make the map more interesting. Some of these features include Plateau, Valley, Oasis, Volcano, Waterfall, Pond, Peak, Dry Lake, Frozen Lake. After I run out of land form features to add I will start working on placing civilizations. Not sure yet if I want to just place them in patterns that are reasonable or evolve them over time to build a history as well.

Fast Rain Shadow

GUI isn’t progressing currently as I find it less interesting than other things I could be working on. I finally managed to get the rain shadow calculation time under control it now only takes a couple seconds to calculate instead of a couple minutes. The results seem to be better too. Here is a description the algorithm:

Previously I was examining ocean points and then simulating where the wind would carry the water. In this version I instead start by examining each land point. For each land point I use the wind direction and reverse it and keep following the vectors until I reach a water point. This creates a path from the land point to a source of water. This path is then examined and I find the highest point along it. If that point is higher than a specified cutoff there is mountains in between this land cell and its source of water indicating that it is in the rain shadow. A value is assigned to the land cell so that there is a slight falloff as the distance from the highest point is increased making the rain shadow less intense over longer distances. Some scaling and normalization are then performed as well as adding a little bit of noise to make it more interesting.

Elevation images following by their corresponding rain shadow:

Biome

This is the last step for this first phase of the project. By using the elevation, temperature and rainfall maps the biome map can be generated. This is a really simple process as it just involves matching ranges to specific biomes. The first step is to split the input maps into discrete levels:

Elevation

  • Ocean
  • Continental Shelf
  • Lakes
  • Flat Lands
  • Hills (“Non-Rocky” rises)
  • Low Mountains (“Rocky”, Peaks below tree line)
  • Medium Mountains (“Rocky”, Peaks above tree line)
  • High Mountains (“Rocky”, Peaks far above tree line)

Temperature

  • Cool
  • Moderate
  • Warm

Rain/Humidity

  • Arid
  • Semi-Arid
  • Moderate
  • Semi-Wet
  • Wet

Once the maps have been split up into discrete components it is simply a matter of matching them to the biomes based on a set of rules. In the gallery the first image is temperature, then rain/humidity and then the resulting biome.

Legend:
Legend

Notes: In the original temperature generator I used the elevation to reduce the temperature. This proved to be unnecessary as it is just easier to prefix the biome with mountain or hill to specialize it to the elevation. Elevation is not taken directly into account to generate these biome maps. Hill and Mountain are used as modifiers to the biome map.

Rainfall

I finally managed to play with the rain shadow and combining it with some noise maps enough to be (somewhat) happy with the rainfall maps that it is generating. I ended up rewriting the the temperature, wind direction, and rain fall map generators to all use the same abstract base class which generates a series of horizontal bands into a gradient. The base class then calls an abstract method to allow different noise implementations to be applied to the gradient. The method used is still the same as explained in the post for the wind direction map it is just more flexible now.

The rain fall generator works in the same way as the wind direction generator. In this case different bands are defined to create dry and wet bands which are then distorted by a noise map. The result is then biased by the rain shadow map to make it dryer in areas of rain shadow. Here are some of the results:

Legend

  • Grey = Arid
  • Dark Red = Semi-Arid
  • Yellow = Moderate
  • Light Green = Semi-Wet
  • Dark Green = Wet

I managed to speed up the rain shadow generation but it is still pretty slow. I am going to leave it for now since I have run out of ideas to make it faster for now. Next up is biomes.

Rain Shadow

Originally my plan was to combine the wind speed and wind direction maps to form vectors where the wind speed was the magnitude and the wind direction was the angle and then trace those over the elevation to create the rain shadow. The results were not very good so I discarded the wind speed maps (I wasn’t too sure about their accuracy anyways) and am now using a constant vector magnitude instead.

Here is a description of the process:

  • Initialize a 2d array to 1.0 to serve as our rain source.
  • Repeat the following for the number of iterations:
    • For each cell do the following:
      • If the rain source is 0.0 continue to the next cell, otherwise:
      • Project a series of rays to form a circular arc. Rays are projected from wind direction angle – PI/8 -> wind direction angle + PI/8.
      • Each ray is drawn using Bresenham’s line algorithm.
      • As the ray is projected the value being added to the resulting map is decayed by a set percentage.
      • As the ray is projected the elevation is evaluated, the ray continues to trace until it reaches the end or it climbs past the elevation threshold and reaches a local maximum.
    • Take the resulting map and any points that are below a threshold set the corresponding point in the rain source to 0.0.

Next I need to create the rain fall maps and combine them with the rain shadow to get the final rain maps.

Legend

  • Black = Rain Shadowed
  • White = Normal