Dungeon League

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

[Show as slideshow]

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

[Show as slideshow]

Finally got around to adding code to place lakes along rivers. I am fairly happy with the results but it still needs to be tweaked in that some smaller basins generally have too many lakes and some larger ones have too few. This code is in serious need of some performance optimization, currently it is taking a couple minutes to place all the lakes. Right now this is probably due to a large number of the source lakes being rejected when being placed. Either the source data set is being created with lakes that are too large or I am placing too many lakes on too small an area. Need to do more testing before I can say for sure.
Here is an outline of the process of placing lakes:

• Create FBM noise map, 5.0 octaves, 128×128 scale. Invert. Absolute Value. Polarize 0.5. Eliminate shapes that are too small or too large based on configured parameters. Also eliminate any shapes that are cut off by the edges.
• Split the noise map into point lists representing different lake shapes. At a resolution of 1024×1024 this gives us our source data for lake shapes of ~6000 lakes.
• For each drainage basin do the following:
  • Randomly determine number of lakes to place based on basin size.
  • For each lake to place:
    • Randomly choose a lake shape from the pool.
    • Randomly select a point on the river in the basin to place the lake.
    • If all points of the lake fit in the drainage basin interior and do not overlap any previously placed lakes add it to the basin and remove it from the source pool.
    • Otherwise choose another point to place the lake.
    • If all points are tried and the lake does not fit select another lake shape and start over. Continue until out of lakes to try.
  • Check the basin for loops created by placing lakes.
  • Eliminate loops by expanding lakes to include them.
  • Combine chosen lakes with expansion points needed to fill loops.
  • Identify individual lakes and give them unique ids within the drainage basin.

[Show as slideshow]

Other Updates:

• Improved performance for all other drainage basin related code by filtering operations down to only operate on necessary areas and leave other areas undefined instead of processing the entire data set.
• More bug fixes in drainage basin code.
• Re-factored performance profiling code to log operation times based on a threshold and reduce repeated code for timers.
• Changed the palette to be easier to understand. Uses only one color to for elevation dark -> light == low -> high.

Next Steps:

• Fix performance for lake placement.
• Update elevation builder to take new lakes into account.

Added a method to generate a continental shelf around the islands. Originally I was making this a step in creating the original continent mask by adding a buffer around the land mask. Creating the continental shelf with the same noise map as the continent resulted in there being little variation in the shelf. Instead I am creating a separate noise map to base the continental shelf off of and using a threshold to configure the size of the continental shelf. I decided not to bother with a variable ocean depth, having a continental shelf and ocean is enough differentiation for my purposes. Here are some samples:

[Show as slideshow]

I also modified the color palette for these images making the rivers easier to see as well as reducing the amount of mountains. The performance of the drainage basin code is starting to really slow things down, I tried multi-threading it but only achieved a 10% performance increase. I will need to re-evaluate the algorithm.

Next Steps:

• Minor lakes at river sources and intersections.
• Performance improvements for drainage basin code.

Added code to create endorheic basins. The same code is used to split islands into drainage basins as before but before the rivers are run the endorheic basins can be generated in places where a large body of water will fit. To do this I use FBM noise and polarize it to form the shapes of many different lakes. These lakes are then evaluated to see which will fit in the basin then one that will fit is randomly chosen based on a minimum size and placed at a random anchor point within the basin. After that the same river processing class for coastal drainage basins is used to create rivers in the endorheic basin.

The river running algorithm has been tweaked to reduce useless short tributaries. I reduced the number of tributaries being generated as well which looks better given the scale and creates a better elevation map.

Next steps:

• Generate lakes where rivers join and as sources.
• Tweak elevation, too much mountain right now (Might just need to tweak the palette).
• Generate continental shelf and ocean depth.
• Multi-thread the drainage basin splitting code.

[Show as slideshow]

I rewrote the drainage basin algorithm and fixed many problems that were in the previous version. The main problems that were fixed or mitigated are :

• Proper result data generated to create elevation from
• Proper result data generated to create rivers from
• Faster performance
• No more long drainage basins that run parallel to the coast line

Next steps:

• Major refactoring of drainage basin code, since it now basically works how I want it needs to be properly organized. Currently the drainage basin creation, river running, and elevation creation are all happening together in one class. Each step needs to be separated so that they can be controlled independently.
• Still need to deal with creating bodies of water inland.
• Tweak/Change river running algorithm. The current one gets the job done but it could look better.
• Not sure if I like the elevation being generated yet. Need to play with it more.
• Should work on a better color palette for rendering elevation.

[Show as slideshow]

To be able to create drainage basins in the manner described in my previous post I need to be able to traverse the coast of an island in order as a path. I already have code to extract a coastline from a map but it is simply a brute force match which processes the entire map. To solve this problem I implemented a marching squares algorithm. To test it I plotted the paths it generated with increasing intensity to see that the points are in order.

[Show as slideshow]

To deal with endorheic basins I have eliminated the ones that were formed in the continent mask. Instead I am planning to add them in after the basins have been created by randomly selecting certain basins and have them drain inland instead. After the coast is closed that basin can be processed in the same way as an island but inverted. Also the drainage basin code needs to be tweaked. Instead of choosing the next point by selecting the one farthest from the current divide it may be better to pre-select points with a more even distribution on the coast and then connect the farthest in this set. This should eliminate the wide basins that are difficult to place river networks on. Hopefully I can test this later this week. For now here is a set of continents with drainage basins with the interior water removed.

[Show as slideshow]

The following images are examples of randomly generated drainage basins. The plan is to use these to develop elevation ranges as well as plot rivers. Here is a description of the steps used in the algorithm:

• Create a land/ocean mask using the process described earlier.
• For each island in the map do the following:
  • Randomly choose a point on the outside coast.
  • Choose a point by selecting the coastal point that is furthest away from the random point. This will be the first start point.
  • Choose a point by selecting the coastal point that is furthest away from the start point. This will be the end point.
  • Generate a RidgedMultifractal noise map and process it as follows: Invert, Absolute Value, Normalize from 1.0 – 25.0, Exponentiate by 5.0.
  • Find the path from start point to end point by using Dijkstra’s algorithm with the RidgedMultifractal pattern providing the traversal costs.
  • Create a collection to store all drainage boundary points in and add all points in the path to it. This collection will be referred to as “allPoints”.
  • Repeat the following steps based on the size of the current island:
    • Find the coastal point whose nearest neighbor in allPoints is the furthest distance away. This will be the start point.
    • Find the nearest point in allPoints from the start point. This will be the end point.
    • Using Dijkstra’s algorithm and the previously defined noise pattern find the path from the start point to the end point.
    • Add this path to allPoints and repeat.
  • Using allPoints and the original land/ocean mask uniquely identify each drainage basin.

The next step will be figure out how to create endorheic basins for large bodies of water that are inside an island.

[Show as slideshow]

My current goal is to generate mountain ranges that are interesting and do not always end up in the middle of the land mass which seems to happen in many world generators I have seen. The mountains in the center of the land mass works nicely for islands but does not make much sense for continents. The results of this first experiment are not very good but I will describe the process anyways.

• Generate a voronoi diagram (A) based off of 32 randomly selected points.
• Make the voronoi diagram (A) “noisy”.
• Select all points that are on the border of a segment.
• Use the selected points to create another voronoi diagram (B) based where each cell has a value equal to the distance to the nearest border point.
• Generate 2 FBM noise patterns (C) and (D).
• Process voronoi diagram (B) as follows: add 1 to every value, exponentiate every value by 0.3, add (C), invert, normalize, max of (B) and 0.25, multiply by (D).
• Use the process in the previous post to generate a continent mask (E).
• Add (B) and (E) then multiply by (E)

[Show as slideshow]