Rivers in "Alpha"

So, rivers are in what I'd call an alpha stage right now. They need finetuning to look better, more natural, and with features (real deltas, mid-river islands, varying river width), but the harder parts are done. At least, I believe so. Unless everyone thinks they look like shit, of course. This is a short post, I just thought I would show a couple of examples of what you can come to expect.

Feedback is very much appreciated, as rivers are very hard, and I want to get them right!

Those darn rivers

For a while now, I have been implementing different approaches to river-generation. It's been pretty tricky, and there's been a lot of failures. But now finally, I seem to be on the right track. (Who knows what tomorrow brings though. My pillow insists on pitching me "good" ideas!)

It's not by any means perfect yet, but at least I feel like I am getting somewhere. I thought I would try to explain  my current approach, and why some other approaches had to be discarded.

So, what points are important for me?

• Algorithm performance. Handcrafted maps do not have this challenge, but tools that will be available online definitely do. Complete maps of decent size should be generated within seconds.
• Rivers need to have twists and turns that look somewhat "realistic" (Note the quotation marks here; Not really sure what realistic means. Looking at some real-world maps, rivers can pretty much look like anything!). 
• Rivers need to follow some rules. An example would be that all rivers need to end in a body of water. (lakes or the ocean). Another rule is that two rivers can never cross each other. They should converge to one (larger) river. 

My approach

I'm not going to describe all the approaches I tried and failed with. That's really not what I'd like to focus on.

Let's just say that realistically forming rivers from mountain tops, and continually going downhill, always searching for the steepest descent until we reach bodies of water, is .. just .. too .. darn .. slow.

It works sufficiently for 1024*1024 maps. But traversing like this on 8192 * 8192 maps just does not work.  Sorry. I might end up offering  this approach for people who have extremely good time

So what did I do?

With heightmaps as my basis, I wrote an algorithm that searches for bays/coves in the landscape. I decided these are among the locations that I will want cities in the future, and also where I want rivers to end up. From these locations with the help of the "bay algorithm", I can find optimal angles for the river mouth. Rivers have random length, but their starting point should be along the axis of the river's optimal angle. (This angle is shifted if the starting point turns out to be in water). 

The river curving itself is made through the use of Bezier splines. The pro's of using these is that the river curving will look natural without doing alot of computing (it's fast!). The largest drawback is that you cannot easily foresee all the points along the river before it is generated. So, even if a straight line from the river mouth to the river start point only crosses land, the curving river might overlap with water.

If this is the case, I search for a new start point, and I try generating again. At the same time, the river length is gradually decreased until the curving river only crosses land. In some cases though, the algorithm decides that a river does not fit, and it gives up. These are often corner cases involving the corners of an image, an island, or very thin stretches of land.

Once I've found a suitable river path, I apply another algorithm that performs some basic erosion around the river, so that it lowers its surrounding terrain.

I'm going to show some screenshots soon, I just want to fix some tiny problems first. Until then.

Template examples

So, I thought I would post two simple examples of how different color templates (in their simplest form) can make the same base map look quite different.

After creating the heightmap, I have data that for each point in the map, has a value between 0.0 and 1.0. When dealing with templates, I multiply these values with 255. This seems to be an acceptable detail range for color mappings. (It basically means that one template can offer 255 different colors for a map).

The next step is adding blending functionality, so that multiple templates can be layered on top of each other. The templates that are shown here are also ignorant when it comes to internal positioning. They process data values in the same manner, whether the point is on the edge of the map, or in the center. But that is definitely not necessary, and templates can be used for so much more, which I'll show soon!

Beyond black and white

I'm currently experimenting with color templates (or Palettes if you will) to create distinguished looks for the maps. Screenshots are coming very soon, there's just some tidying up left before it's presentable.  Beyond that, I'm interested in finding out what people would find useful to have in an autogenerated setting.

I'm thinking:

• Cities
• Climate zones (visualize this, somehow)
• Rivers
• Mountains 

Anything else that seems important for the map portion of the project?

Lore, Naming generators ++ comes at a later stage.

Algorithms for finding decent city locations in an random environment is going to be challenging, I think. Rivers are much the same; Quality rivers that look good are challenging. But that's half the fun, and part of what keeps me motivated.

Landmass and oceans

Now that I have my heightmap done, I have what I need to create a landmass and an ocean (or something equivalent, in case you're creating an extremely unique world). From past experience, creating the shape and size of the landmass and the oceans is actually a pretty difficult task. I tried doing it manually with varying results, and I also tried several photoshop variants, most of which were offered by the nice people at The cartographer's guild. And some techniques were brilliant. Few of those that produced good results were easy, however.

With my heightmap, every point in my map is a value between 0.0 and 1.0. By applying a filter, I can say that everything from 0.0 - 0.5 is ocean (black in the image shown), and everything from 0.5 - 1.0 is land (white).

1) The heightmap used

2) The result after the filter.

I like the result. It produces no visible artifacts, or any bias towards any specific direction.

This could hopefully be useful even for those of you who like to handcraft your maps. With that magic wand, you should easily be able to split land and ocean into two different layers in Photoshop.

Starting with Noise generation

At the heart of most methods for generating maps lie a layer of noise. The most famous noise generation algorithm is Perlin Noise. Algorithms like Perlin Noise offer pseudo-random results. You choose a random seed for the algorithm, and for the same seed, the algorithm will spit out the same results. For my map generation, I use a noise generation algorithm called Simplex Noise. A more in depth article which explains Simplex Noise fairly well is located here. It also contains Java source code!

Running the Simplex Noise algorithm might leave you with a result similar to what you see in the left image.

My goal with the noise is to end up with something I can use as a Heightmap. You can find plenty of example images on the web, and after looking at a couple, you'll probably agree with me that my result needs some refinement. Using something similar to what's called Fractional Brownian motion, I end up with a result similar to what you see in the right image. Now I'm getting somewhere.

Synopsis

So, what goes into the term "Generated Worlds"? Well, that depends on who you are and why you found your way here. For me, it's a passion. I've always liked playing roleplaying games, - and each of the roleplaying games I've played feature a living breathing world. Some worlds go beyond unrealistic, and some remain similar to our own earth. But the world is always there. Detailed, vivid, and full of history and lore. "Whoa, hold on!" you might be thinking. There's no way you can automatically generate a whole world. You're probably right. I've had no success before, and there's really no reason why I should succeed this time. But I'm still going to try. I appreciate company along the way, so if you'd like to urge me on, offer me constructive critisism on my latest strategy, beat me down if I fly too high, or even if you come here just to gloat over the fact that you can do better ... I welcome you!