Archive for March 2010

Wind Direction

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

Performance Fixes

I managed to fix the performance problem with the lake placement code. I was performing an expensive operation after every single basin executed the lake placement code when the step could easily be done once at the end. Changing this sped things up about 100 times. I also factored in the lakes to the elevation code, they don't really have a big impact on things. A few other minor tweaks were added to the elevation code as well to give a higher weight to the elevation based on the rivers and water system vs that from the continental divide. I re-organized some of the classes for the drainage basin code but it still is a bit messy. Getting bored of looking at that code so I will move onto the next step which is wind patterns. Not sure what I am going to do for this yet. I am thinking about creating a vector field to give a very abstract simulation of this: Global Circulation


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, 128x128 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 1024x1024 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.
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.

More fun with Multi-threading

Over the past couple days I have been making my drainage basin code run faster by making it multi-threaded. The performance increase is ~30%. Not bad but I probably need to find an algorithmic improvement to get it to where I would really want it. Still I will move on to adding other features instead of refining this endlessly. Multi-threading the drainage basin code introduced a couple of bugs that were interesting to track down. These bugs were related to seeds not creating predictable results. By using multiple threads extra care needed to be taken to ensure results from separate threads are assembled in a consistent order. Also each thread must get its own random number generator since we no longer control when each thread might be accessing a common random number generator (Even though the implementation of the random number generator is synchronized). Lastly some places I was using a HashMap/Set instead of a TreeMap/Set resulting in unwanted randomness.

Continental Shelf

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: 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.

Endorheic Basins

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.

Bug Fixes & Multi-threading

Cleaned up the drainage basin code and split it into three components, one that splits the landmass into sections, one to run rivers and one to build elevation. Fixed a hard to track down bug that occurred once in about 200 runs of the basin generator: When a section of land is being split a path is generated to divide along. After dividing along the path there are n pieces of land and the path itself. The next step is to determine which piece of land to add each point of the divide path to. In rare situations a point on the path was being added to the wrong piece of land that it did not actually have a connection to. This resulted in coasts and divides being incorrectly chosen in the following steps. I have added the ability to call a multi-threaded version of every cell based operation. Many operations do not benefit from this since starting the threads and waiting for them to all complete takes as long or longer than the time saved. The Voronoi operations benefit the most from the multi-threading . Some of the more complex nested noise operation also show improvement. The multi-threaded execution will become more useful as I increase the size of the data being generated. Although I am posting 512x512 I am mostly generating 1024x1024. I might start posting in that size too.