Continent Maps (Part 4): Wind Model

As mentioned last time, at continent size the Dragons Abound maps start showing some odd (unrealistic) weather and biome patterns.  In this example, you can see that the forest line up in stripes along the prevailing wind direction:

This isn't broken code, it's more that that weather and biomes model is too simple and the seams start to be obvious at this scale.  To address these problems, I'll start by revising the wind model.

I'd like my wind model to better reflect the kinds of wind dynamics you see on Earth:  circulation cells, trade winds, and the like.  These dynamics might help address the odd weather patterns on continent-sized maps.  However, working to add these re-opened my festering discontent with the Dragons Abound wind model, which is slow and seems overly complicated.  (You can read about my original implementation of the wind model starting here.)  Thinking about it for a few days, I decided that most of the problems ultimately trace to the fact that the Dragons Abound map is represented as a Voronoi diagram.  (Or more accurately the Delauney triangulation of the Voronoi diagram.)  This has many advantages for terrain generation -- combined with noise it can produce pleasingly natural looking land masses -- which is why you see it used so often for terrain generation.  But because the individual triangles are various sizes and orientations, any calculations like the wind model that rely on affecting neighbor cells can become quite complicated.  It would be much easier to model wind across a grid of equally spaced, identical regions.  Also, the wind model probably doesn't need to be at as fine a scale as the land. 

But I don't want to abandon the Voronoi diagram that underlies Dragons Abound completely.  (For one thing, that would require rewriting almost the entire program!)  Instead, I want to experiment with mapping (heh) the map onto a regular grid, running the wind model there, and then mapping back.  If the expense of copying back and forth to the regular grid isn't too bad, this might make the wind model faster and simpler.

What sort of grid should I use?  Ideally, the grid would consist of identical regions, all equidistant from their neighbors.  And that sounds like a hexagonal grid.

And in fact, a hexagonal grid is the best way to divide a flat surface into equal-size regions.

The next step is to figure out how to represent a hex grid in my program.  I searched around for some guidance on how to best do this, and every link pointed back to Amit Patel's hex grid page.  Which is probably where I should have thought to start; it isn't a bad rule of thumb to check Red Blob Games first if you're looking for info on implementing a game mechanic.  Amit does a better job of explaining this than I can, so if anything seems unclear, go read his page.

The first choice I need to make is how to store the hexagonal grid.  The straightforward choice is to story it as a two dimensional array, but I need to be able to map the cells of the grid onto the array in a consistent way.  There are various choices (go read Amit's page) but I'm going to use what he calls odd-r:

The numbers in each cell of the grid represent the indices where the cell resides in the two dimensional array.  (This picture is stolen from Amit's page.  On his page it's interactive, and you should definitely go play with it.)

With that choice made, I now need to be able to map from the indices onto the hex grid.  For example, if I'm looking at the hex cell (3, 3), then what are it's neighbors?  If each hex cell is 5 pixels across, then what are the center coordinates for the (3, 3) hex cell?  And so on.  It might seem complicated to figure all this out -- which is why you'll be happy to know that Amit has already done it.  Have I mentioned you should go look at his page?

Assuming we can steal everything we need from Amit, what I need to do first is figure out how to layout the hexes over the map.  At this point I don't actually need to have the array, I can just pretend I have it and see where the hexes would be.  If I know the spacing of the hexes, I just divide the width of the map by the horizontal spacing to get the number of columns, and I divide the height of the map by the vertical spacing to get the number of rows and then draw a hex at each location:

Those hexes are much larger than I'll use for the wind model, but it shows that the layout is happening correctly.

Here I've exposed the edges of the map and drawn just the center hex and at the limits, to see if I'm really covering the whole map:

Top and bottom are off the map, but it doesn't really matter if I have some cells off the map as long as I don't miss part of the map, so this looks good.

The next step is to actually create an array for the hex grid and then map all the Delauney triangles to their corresponding hexes.  Since Javascript doesn't really support negative array indices, I need to shift the (0, 0) hex grid from the center of the map to the upper-left corner.  With that done, I walk through all the Delauney triangles and add them to the hex grid at their proper location.  I can check this by coloring in the hexes that contain land:

To determine if a hex is land, I'm averaging the height of all the locations that fall within the hex.  You can see that for some coastal hexes, the average is below zero even though there is some land.  An alternative is to use the maximum height of all the locations in a hex:

This overshoots in the other direction, marking a hex as land if it has any land.  Which is best depends upon what you're doing.

In either case, I can improve the accuracy by reducing the size of the hexes:

Now the shore is much better, but a new problem has arisen -- lots of inland hexes that aren't showing up as land. This happens because that when the hexes get small enough, some hexes don't have any Delauney triangles inside of them.  So they have no “height."  (This also illustrates the irregularity of the Delauney triangles.)

One solution is to take the height of the missing hexes to be the average of its neighbors, or the maximum of its neighbors.

In general, when the mapping from hexes to locations isn't at least one to one, some fix must be applied to fill in the missing information.

Now that I have a hex grid overlayed onto the map, the next step is to implement the wind model.  The basic idea of the wind model is simulate some winds (the trade winds) and propagate them across the map until they reach a steady state.  At the hex level (or location level, if I'm doing this on the Delauney triangles) this involves two steps:  (1) sum up all the winds entering this hex, and (2) determine how the summed wind leaves the hex.

The first step is fairly straightforward.  Each hex has six neighboring hexes, and each of those hexes can contribute wind.  If we treat each of the wind coming into a hex as a vector, then the total wind in the hex is the sum of those vectors, e.g., two winds of the same strength exactly opposite each other will cancel out.

The second step (determining how the summed wind leaves the hex) takes more thought.  The simplest case is a wind that blows straight across a hex:

In that case, we'd expect the wind to travel unchanged into the next hex.  (Here red is showing the original wind vector and blue the propagated wind vector.)

What about a wind that doesn't blow directly into an adjacent hex?

In this case, it seems reasonable that some of the wind should blow into the hex directly above, and some of the wind should blow into the hex counter-clockwise of that one, and the proportions should be based on where the arrow is pointing.  In this case, most of the wind will go into the hex directly above, and less into the adjacent hex.

There's also a choice to be made about the direction of the propagated wind.  One option is to maintain the direction of the source wind:

This seems like the most realistic choice, but another option is to change the direction of the wind to match the edge of the hex it crosses:

This is less accurate, but has the advantage that incoming winds will always be at one of six directions, which could simplify calculations.

A further complication arises when we consider terrain.  What should happen when there is a mountain in the way of the wind?

In this case, some of the wind goes up the mountain (possibly creating precipitation) but some of the wind is turned aside.

So how wind exits a hex depends upon it's direction as well as the terrain in the neighboring hexes.

Now let's talk about representing vectors.  There are two basic choices.  First, a vector can be represented by an X value and a Y value, like this:

If we draw the vector starting at (0, 0), then (X,Y) are the coordinates of the end points.  This representation makes it very easy to sum vectors.  You simply add together all the (X,Y) values to get a new vector:

An alternative representation is to use the angle and length of the vector:

With this representation, it is easy to do things like rotate the vector, or change it's length.

For most of what I need to do in the wind model, the first representation works well, but in some cases, the angle and length representation works better, so it may be convenient to be able to switch back and forth as necessary.  Rather than re-invent the wheel, I looked around for a Javascript vector library and Victor.js looks pretty good, so I'll use it.

I'll begin by dropping a wind vector into every hex and see if I can visualize that:

Looks good so far.  

The next step is to see if I can split a wind vector properly and propagate it into the next hex.  The first thing is to figure out the angles leading into other hexes.  Once again Amit's page provides the answer:

So a vector at 0 degrees points directly into the hex to the right, at 60 points into the hex below and to the right, and so on.  A vector that points in-between two of these directions gets split proportionally between the two hexes -- so a vector at exactly 30 degrees would get split equally between the hex to the right and the one down and right.  Every vector lies somewhere between the angles for two adjacent hex faces, so it's a matter of looking at the wind vector angle, seeing where it falls between the center angles of two hexes, and then splitting it proportionally between the two hexes.

For example, if a wind vector falls at 22 degrees:

then 38/60 is propagated into the hex to the right, and 22/60 percent of the vector is propagated into the the hex down and to the right.  If vectors are represented as an X and Y value pair, then you propagate by multiplying each value of the original vector by the proportion (e.g., 22/60) and then adding that into the wind vector in the new hex.

To test this, I can put winds at different directions coming in from the top and side of the map, and see if they get propagated properly across the map.  As the winds run into each other they should combine to take the average direction with increased velocity:

Here you can see the winds meeting along the diagonal and combining to blow down toward the bottom corner.

The next step is to take into account the effect of the land on the wind.  Real wind models are of course very complex, but my concern is primarily with how the surface winds are affected by the land geography.  At a simple level, this is just how the rise and fall of the land changes the direction and speed of the wind.  I experimented with a variety of different approaches, but in the end settled on two simple rules:

1.  Wind turns away from obstructions.
2.  Wind slows down when going uphill and speeds up when going downhill.

An obstruction happens when wind is blowing into a hex with a higher elevation, i.e., like a wind blowing towards a mountain.  When this happens, I'll look at the two hexes the wind is blowing into, and change the angle of the wind to be more towards the lower of the two hexes.  The amount the angle changes will vary depending on the height difference of the two hexes, so when a wind blows into two adjacent mountain hexes it won't change direction much, but if it blows into a mountain hex and a plains hex, it will swing strongly towards the empty hex:

How strongly the wind turns can be tuned.  The above map is probably too strong and would result in a lot of unrealistic biomes.  Here's a more reasonable value:

There's still a lot of wind movement based upon the terrain, but the big gaps and strong wind alleys have been tamed down a little bit.

Another feature that helps with realism is to add a little bit of spread to the wind.  For example, you can see in the above map the wind blowing due West just above the city of Breeches.  Although it blows quite a long ways, it never spreads out as we'd expect.  Where a blowing wind meets other air, it will tend to pull that air along with it.  To simulate this, I can take a little bit of the wind that is blowing in every hex and distribute it to all the neighboring hexes.  Here's what the above map looks like with a modest amount of spread:

You can see how the wind above Breeches has now start to spread downward.

That takes care of wind direction for the most part.  The second part is to slow down wind as it goes uphill and speed it up as it goes downhill.  I can accomplish this by looking at the relative height of the hex where the wind originates and the height of the hex where the wind is blowing, and adjust it faster or slower as necessary.

Here's what that adds:

You can see that some of the wind through the large mountains in the center part of the island has now been cut off.  Conversely, there are now some breezes on the western side of the island where air is flowing from the relatively high land down to the sea.  (An offshore breeze!  Although not really; that's a different mechanism.)

Now I can substitute the new wind into the existing precipitation algorithm.  Here's a side-by-side comparison (old winds on the left, new winds on the right):

(Click through for bigger version.)  Obviously there are differences between the wind models.  On both maps, the wind blows in from the east.  The mountains near the center of the map turn the wind there to the south, dropping a lot of precipitation and creating a swamp and forests just south of the mountains.  On the bottom part of the island the wind blows unimpeded and forests form along the eastern half of the island.  In the original wind model, enough wind comes over the center mountains and past the swamps to create a forest on the western side of the island.  With the new model most of the wind is cut off and grasslands form on the far side of the mountains.

The old model has a variety of random (within a range) parameters, and it's likely that some combination of those parameters would look more like the new map.  But it's not really important to reproduce the exact behavior of the old model, only to have a model that produces reasonable looking results.

The point of all this was to speed up and simplify the wind generation so I could add some new wind behaviors for continent-sized maps.  How did that work out?  I profiled the original wind model and the new hex-based model, and the hex-based model as about 15-20x faster than the original model (!).  A very significant speedup, with very little impact to the maps.  Some experimentation suggests that the model isn't very sensitive to the size of the hexes, either, so if necessary I can probably speed up the algorithm further by making the hexes bigger.

Next time I'll work on use the new wind model to implement some continental-scale wind patterns, and then hook that up to the precipitation model and biomes.