Last time I rewrote elevation painting. The next thing I wanted to work on was biomes. I'm not actually even sure I need them, but I wanted to try a variant of an approach I had tried in the 1990s and again in 2009:

Rain cycle
  1. Evaporation moves moisture from lakes and oceans into the air.
  2. Wind moves the air and moisture.
  3. Air can't hold as much moisture when it passes over mountains.
  4. When air can't hold the moisture it falls as rain.

This time I wanted to implement it on the Voronoi+Delaunay mesh instead of on a grid. The first step was to read some papers about calculations on a mesh. I read about discrete exterior calculus and Pixar's course on vector fields [PDF] and then Bridson's notes on fluid simulation [PDF]. These were overwhelming. The math was way over my head. I went to bed thinking: I could never do this. I gave up on fluid simulation.

The next morning I decided I probably could learn it, given enough time and motivation, but … I had given myself just a week for this. I'm still going to skip fluid simulation. Then I found Jamie Wong's fluid simulation page, which made me feel better about it. It might be something I could implement in a few weeks instead of after a year of studying math.

However, I decided I should stick with the decision to skip fluid simulation. I started with something simpler. Much simpler. I didn't even know if I wanted to have biomes, so I didn't want to spend a huge amount of time on it yet. I made a list of possibilities, from simplest to most complex:

  1. Use noise to randomly assign biomes, ignoring the mountains and oceans the user has painted. This is easy, only a few lines of code.
  2. Use the user to paint the biomes, just as they paint the elevation. This would be relatively easy, I think, and it would fit with the "let the user paint things" theme.
  3. Use wind in a straight line to spread moisture across the map, as described above. I judged this to be relatively easy, but I wasn't sure if the results would be interesting.
  4. Use wind in a fluid simulation to spread moisture across the map. Try the demo on Jamie Wong's blog post to see how it feels.

I tried approach 1 and decided it wasn't interesting. But it's easy, and it means I have a backup plan in case other approaches don't work. I then tried approach 3.

To make wind move across a mesh (step 2), consider the simplest case: let's try moving from west to east. The solution is simple: sort the Voronoi regions by x, and then visit them in that order. For each region, pull in the moisture from all the neighboring regions to its west. I implemented and tested this. Let's generalize this. To make wind move from any angle θ, sort the regions by cos(θ)*x + sin(θ)*y instead of x. Simple, and it works nicely.

Great! I had step 2 implemented. The rest is straightforward, but there are lots of parameters that need tweaking.

  • Wind: moisture is copied from neighboring regions.
  • Evaporation: moisture increases by some amount.
  • Mountains: moisture is limited by 1-elevation.
  • Orographic precipitation: any moisture reduced by mountains falls as rain.
  • Regular precipitation: some fraction of moisture falls as rain; I assume it all evaporates again so I don't reduce moisture.

I also made the river flow depend on rainfall.

Here's an example of the output, with wind flowing from west to east. You can see it's drier to the east of a mountain range:

Example output: rain from mountains creates a river in the desert

This differs greatly from the biomes in mapgen2. Those biomes were based on the distance to the rivers. That means you could never have a river going through a desert. Here, rainfall and river flow are related, but it can rain in a wet place and cause a river to flow through a dry place.

The straight line approach is fast and produces reasonable results but they aren't great. There are artifacts such as moisture going through a mountain pass and creating a path of green in the middle of desert. And I'm not yet sure how to handle the boundary of the map. Should it always be ocean? I don't know yet. How should I render a forest vs grassland vs desert? I don't know. What I implemented this week seems to work, so I'm going to keep it and move on to another part of the code next week.

Labels: , ,

2 comments:

Scott Turner wrote at September 15, 2018 8:33 PM

I had to laugh because I'm busy implementing on a grid instead of a mesh.

One thing I found help the "realism" of my wind model a lot was to have winds turn away from higher elevations, and to speed up on downhills and slow on uphills. Of course, this complicates the model considerably on a mesh (which is why I'm looking at a grid).

Amit wrote at September 20, 2018 11:39 AM

@Scott: Grids are so much easier for me to work with! But part of my goal here is to learn more about algorithms on meshes :-)

I think fluid flow on a grid could be a lot of fun, and I think it could give me winds that turn away from higher elevations, speed up, slow down, etc. I may explore this as a separate mini-project before trying to integrate it into the map generator.