Dungeon League

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:

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.

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.

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.

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:

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:

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.

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.

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

Today I finished the code for generating wind speed and temperatures.

The wind speed defines bands above and below the equator where the wind speed is high while it is lower at the equator. These bands are combined with the land mask to make the wind higher over the ocean and weaker over land. Steps:

• Start with a base noise map. (FBM octaves = 5.0 and size = 4.0)
• Define bands where with varying wind values. (Strong-Weak-Strong for this example)
• For each cell the value from the band is added to the noise map multiplied by the base noise weight.
• To complete the base map the whole map is normalized between 0.0 and a base weight.
• A second noise map is created called the continent noise map. (FBM octaves = 5.0 and size = 8.0)
• Using the Voronoi operation create a map where every cell has a value equal to its distance to the nearest coast.
• For each cell I create a weight based on the distance to the coast. If the point is further than the distance threshold the weight is 1.0 if over ocean and 0.0 if over land.
• This weight is combines the the continent weight and then multiplied by the continent noise and added to the base map.
• The final map is then normalized.

The temperature map is a simple linear gradient biased by the elevation and a bit of noise to make it more interesting. Steps:

• Each row base value is equal to lerp between 0.0 and 1.0 where the poles are 0.0 and the equator is 1.0.
• For each cell in the row distort the row value by the matching cell from a noise map multiplied by the distortion factor. (In this example FBM was used octaves = 5.0 and size = 4.0)
• If the elevation for the cell is greater than a set threshold I decrease the temperature based on where the elevation lies between the threshold and the max elevation.

Next Steps: Rainfall & Rain Shadow

Wind Speed Legend:

• Black = Low Wind Speed
• White = High Wind Speed

Temperature Legend:

• Red = Hot
• Green = Moderate
• Blue = Cold

I created a simple method to simulate the wind patterns described in this image for Global Circulation. Here are the steps I used:

• Define Latitudes and wind directions to go with them. All directions are in radians. I defined the following latitudes:
  • North Pole = South
  • North Circle = North
  • North Tropic = East
  • Equator = West
  • South Tropic = East
  • South Circle = South
  • South Pole = North
• For each row of data lerp between whichever 2 latitudes the row is in between to get a value.
• For each cell in the row distort the row value by the matching cell from a noise map multiplied by the distortion factor. (In this example FBM was used octaves = 5 and size = 2)

A distortion factor from 0.15 – 0.2 is probably the best to have enough distortion to create paths like a jet stream but still maintain the general direction of the defined latitude/direction pairs. Next up: Wind Magnitude

Wind Direction Map Legend:

• Blue = East
• Green = North
• Red = West
• Yellow = South