Project Frontier #7: River Raid

 By Shamus Jun 20, 2011 159 comments

WARNING: This one is tough to explain without spending 5,000 words detailing the most mundane inner workings of the engine. Sorry if it’s confusing. I did what I could to balance information and readability. I tried, I really did.

When I started the project, I had a pretty good idea of how the previous features were going to work. Terrain textures, the topography, the grass, the sky. My design changed as I worked, but I always had a plan.

I don’t have a plan for rivers. This is a shame, since the whole project is pretty much a bust if I can’t solve it.

Here is what the world looks like during my default build:

frontier7_1.jpg

The world is currently 8,192Km on a side, making it about eight times larger than Oblivion, and about one eighth the size of World of Warcraft. I can make it larger (much, MUCH larger, I haven’t actually tested the upper limits yet) but at that size it’s just more time consuming to test, because I have to travel so far to see if things are working properly. Keeping it small lets me see a larger percent from a single vantage point. As I said before, in the end I’ll make the world exactly as big as it needs to be in order to feel large and varied, but without it feeling like miles of filler. Basically, the more variety I can add, the larger the the end product can be. And a big part of adding variety is putting in rivers.

You might say, “Just have the rivers follow the landscape”, but of course it doesn’t KNOW the landscape when it generates the world. The hills are generated later. If I decide I want to begin a river at the foot of a mountain, I have no idea which way it will need to flow to reach the ocean.

You might suggest that it work out the path of the river once the player enters the area and the terrain is created, but the player can approach from any angle. What if the player begins at the coast and heads inland? Once it generates the source of the river, it plots the path and finds the river needs to flow through areas where the player has already visited. Will a river suddenly poof into existence behind them? Should it flow as far as it can without disturbing what has already been seen? Both of those are unacceptable. The goal is for the world to look and behave exactly the same, regardless of how the player approaches it.

Perhaps I could pre-generate the areas around rivers? But that solution scales very, very poorly. The larger the world, the more real estate it needs to generate before you can play. This would add long pre-computation times to creating a new world, which goes against my original design. For my plan to work, the macro-scale stuff MUST be independent of the micro-scale stuff.

(Time passes.)

I think I need to break the problem down into two steps: The macro-level layout, and the micro-level topography. That’s how everything else in this world is created, and I need to stick to that design for rivers. Right now, when it generates a world it ends up shaped something like this:

The colored square in these shots is just a flashing marker to show where I'm standing. Just ignore it.
The colored square in these shots is just a flashing marker to show where I'm standing. Just ignore it.

Each pixel in the image is a region, which represents an area 64m on a side. You can see that for the most part, the world is high in the middle and then tapers off towards the ocean. Which is as it should be. For the macro-level design, I want to begin a river somewhere in the middle of the map and just let it flow naturally until it hits the ocean. The result?

frontier7_3.jpg

Crap. It attempted five rivers, and all of them dead-ended LONG before they got to the sea, trapped in a spot where they could only go uphill. The overall shape is that the island is high in the middle, but there are still spots here and there that act as pits. My “go downhill” logic is naturally going to gravitate towards these spots and get stuck. I try creating a dozen rivers, and none of them make it to the sea.

Clearly I’m going to have to flatten as I go. I turn rivers into steamrollers. While plotting a river, if it finds itself in a spot where it can’t go downhill, it turns towards the nearest coast and begins hammering down the regions until it breaks through and can begin moving down again. This happens often, and having these constant one-region canyons threatens to make ALL rivers into river canyons. To alleviate this, I have the river flatten out the regions on either side as well.

frontier7_4.jpg

Okay, so now we’ve plotted a basic path for the river without needing to generate all of the topography for where it goes. Using only the large-scale map, we’ve worked out a course where the river can theoretically flow downhill, as long as there aren’t any small hills in the way once the player arrives and the actual topography is generated. (Again, remember that each pixel is an area of 64 meters on a side. A lot can happen in that space.)

But of course, there ARE hills in the way. Often. It’s the normal scatter of hills that covers the rest of the world, and sometimes one of those hills ends up right across the path of the river. I can’t plot around them, because there isn’t always guaranteed to BE a way around them. What if a south-going river runs face-first into a ridge that runs east to west? You might say I could divert the river (say) east or west and look for a way around, but which way is shorter? What if the way around is really, really long? Will the game suddenly come screeching to a halt while it churns through all those pages of data, looking for a path around this ridge? What if the player approaches from the east, and it generates all of those pages before the player gets close enough to the river and the game realizes it needs to divert the river east, where the player has already been? What if the player comes from downstream, walking along where the river was originally planned to go, then THEN they reach the topography the requires the river to be diverted? Will it yank the river out from under them?

No, no no. I’m back to the original problem. This is un-solvable. There is no way to plot around hills in such a way as to guarantee that the map will always look the same, regardless of which areas are generated first.

Well, if we can’t make the river fit the hills, we have to make the hills fit the river. I add some code to simply dig a trench through the middle of a region. The result?

frontier7_5.jpg

Words fail me.

Obviously the river looks extremely artificial. It looks like a giant game of Pipe Dream, actually. I can loosen up the numbers generating the trench. This makes the banks more natural and likely to curve, but also allows the topography to cut off the river entirely, making the river abruptly slam into the side of a hill, and then pop out the other side. This actually happens in nature, but only to small streams and only occasionally. Here we have it happening constantly. There’s a trade-off at work here. I can make the banks look increasingly natural at the expense of having a river that gets large and small and ends abruptly, which looks horrible. Or I can have a river that will maintain a constant size, but looks like a man-made canal. There is no “sweet spot” here. I can solve one of these problems, but not both. And it looks awful either way.

Here, let me show you what this looks like so that you can see region boundaries:

frontier7_7.jpg

You can see we don’t have a lot of room to work with. I can’t do anything with the river that causes it to get too close to the edge of the region.

Here is how a region looks to the generator:

frontier7_6.jpg

When I generate a single point, the only data I have available are the region properties (how tall are the hills, where is the water level, is there a river, etc.) and my offset from the upper-left corner. It can’t “go around hills”, because it doesn’t have access to the adjacent points. Half of them aren’t even generated yet! All it knows is how far it is from the corner. Right now I’m using that to make my trench – the closer it is to the center, the deeper it digs.

(The next day.)

Hm. You know, I’ve got two values to work with here. One is X, my offset from the left edge, and Y, my offset from the top of the region. I can use one of these to modify the other. If I’m making a north-south river, I can use Y to form a sine wave and apply it to X. Likewise, if I’m making an east-west river, I can make a sine wave with X and apply it to Y.

frontier7_8.jpg

Wow. That really helps. The corners are still horrible, though. Hm. If I’m making a turn, I can replace my usual offsets with a straight-line distance from the corner at the center of the curve. If that doesn’t make sense, maybe this does:

frontier7_9.jpg

The river will cut off any hill it touches. I expected this to look awful, but I can barely notice it, even in really hilly areas. Which makes sense. I mean, that’s what rivers do, right? They cut through hills.

Since I’m not using river depth to carve through hills that may or may not be there, I can lower that depth without worrying that the landscape will just eat my river. Specifically, I can make really tiny streams:

frontier7_10.jpg

That gradually grow into mighty rivers:

frontier7_11.jpg

In the end, the grid is well-hidden:

Click for larger view.
Click for larger view.

It might still sometimes look a bit artificial from overhead, but from on foot it looks just fine. Right now it’s not smart enough to make water “flow”. The texture doesn’t move and the water doesn’t push the player. Here is the thing with that:

Right now I can have thee-way intersections. One river can merge with another. Easy. But if I want flowing water, this becomes a thorny problem. It’s hard (if not impossible) to have flowing water textures that look right at one of these merge points. It would also be messy to push the swimming player in the proper direction. Basically, I can have rivers that merge, OR flowing water, because doing both would be prohibitively time-consuming and complex. (And the texture might look wrong no matter what.)

This is a decision to be made later, once we’re talking and thinking about gameplay.

Onward!

A Hundred!202019We've got 159 comments. But one more probably won't hurt.


  1. sab says:

    Awesomage. Not just the problemsolving, but the writing as well. For most part of the post you make it feel like an unsolvable problem, only to solve it in the end. Well, mostly anyways.

    One thought though; wouldn’t it be better to add a bit more variation to the sine waves? They do look a bit repetitious from overhead, and while it might not be the initial purpose to never have the player rise that high, who knows what the future might bring. Maybe playing with the amplitude and wavelength might help? After all, half or one and a half sine wave should end up to the same Y value.

  2. James says:

    So, you’ve got your rivers working now. But it seems to me that the river is the same size from start to finish. Surely you could make it scale a little more – have it start small, and finish huge, using a scalar value that was dependant on the distance from the ocean or similar? But, for that to work, you’d have to plot the river’s course first, and then input the scaling.

    A second thing. If you do get long rivers, they are generally straight. Couldn’t the sineitude of the river be dependant on the distance it can travel unopposed?

    But then these will probably be horrible coding snafus. So feel free to ignore them.

    • Shamus says:

      That’s exactly how the rivers work: Small stream to huge river. It does the macro planning when the world is generated, and that’s when it sets the river width.

    • Magnus Falk says:

      Actually, straight rivers are almost always a result of human intervention. All the large rivers in continental Europe have been dug straight some time during the eighteen hundreds or so to facilitate barges transporting stuff. Natural rivers are almost always of the really “windy” variety.

      The problem though is reflected in your post, people have lived with these straight rivers so long now that they’ve become the natural state for most people. And in the end you’re not really looking to create something that is 100% natural, rather you want something that looks natural… =)

      • Blanko2 says:

        that’s not strictly true.
        it’s a combination of several factors, the nile, for example, plows through really soft soil for a good part of its trajectory and thus is fairly straight, the faster and stronger a river is, the straighter it’ll be given a long enough timeline.
        rivers that have to erode tough rock also tend to meander more, rivers that go through sand or limestone end up being a lot straighter…
        the general trend is still wider/faster = straighter

        • Kaeltik says:

          Huh. I don’t know if that sounds 100% correct. Is there an empirical relationship between straightness & flow rate?

          • Blanko2 says:

            it’s a tendency, not a certainty.
            like i said, it depends on how the soil reacts to erosion. more easily eroded soil will make the river straighter as well, where hard rock will generate more bendy rivers.

  3. Herrsunk says:

    Very nice solution to the river conundrum!

    But if we all turn to page A35-B of the sheet and closely inspect the title… Lakes, man.

    What about lakes? Are you discriminating against the lakes? Are you anti-lake? Are you part of some sort of slandering lakeism group/tomfoolery?! The tabloids needs some answers, now (because being a impatient prick is far better than waiting for the next instalment)!

    • Manik says:

      This man has a point, why not have the dead end rivers turn into lakes?

      • Shamus says:

        Because all rivers would be a hundred meters long and end in lakes. :)

        That said, lakes are on The List.

        • LVC says:

          Until the lakes overflow right, forming new rivers?

          edit: Okay I can see some problems there.

        • Dys says:

          What occurred to me was, if a river dead ends because it would have to go up to continue, what should really happen is, it fills the dip it’s in up to the level where it can start flowing down again, and that would create a lake. River in, river out.

          I have no idea how hard that would be to implement, of course. I am guessing you would have to check the height of all the points nearby until you found the lowest, and use that as the water level. This probably has the same unavailability problem you were talking about above?

          • Dev Null says:

            The problem with this is back to the problem of the post: its a micro-level solution to a macro-level problem. When you do the macro-level planning at the outset, you have to decide at least one thing: which tiles will the river pass through. You have to do this in advance, because, as Shamus points out, the player might be working their way upstream, and you have to know that this tile has a river in it _before_ you have any idea what the detail of the upstream tiles looks like. So before you even generate the detailed terrain, you know which edge of the tile the river enters from, and which it leaves by; filling up a lake til it spills over might make it go the wrong way.

            Shamus seems to have fixed this by simply dynamiting his way through any hills between where he knows he has to start and where he knows he has to end up (and then smoothing out the surrounding edges a bit.) And frankly, it looks pretty good. I wonder if you could do it the other way round though; generate the river first, _then_ the detail terrain, starting from the known fact that everything at a river bank must go up to keep the river in its banks. I don’t know if it’ll come out looking any different, but it seems like a more natural way to think about it to me.

            • Kayle says:

              The problem is that terrain is really a global problem, and Shamus is trying to avoid doing a planetary simulation.

              Think of how terrain actually forms: geological processes (plate tectonics) cause bits of the crust to get thrust up, move, pulled down; winds form (due to differential solar and other warming, oceanic heat sinks, planetary rotation) which erodes the terrain and carries moisture which eventually precipitates, dropping water to further erode the terrain; etc…

        • Tobias says:

          I remember reading somewhere that this is how df generates rivers.
          When the lake fills it flows over and creates a new river at the lowest saddle of the surrounding hills. That stream errodes the riverbed a bit which lowers the lake again.
          Run on a micro level this would cause the river to change streamwidth depending on the underlying terrain.

          • Trix says:

            DF has the advantage of generating the entire world all in one go though I believe.

            • Joe says:

              Also of never having to render or simulate more than a small chunk of it during gameplay. And even then it is extremely slow from all the bloody simulating it’s doing. And the total lack of graphics processing is an advantage shamus doesn’t have here.

        • Zak McKracken says:

          Hmm… exactly that would have been my approach: if you reach a local ditch with your river, start forming a lake. Increase the water level until it overflows, and on that point, erode the land, so the lake becomes shallower again.

          In order to figure out where water from some region goes, there’s this method: You start raining on the map (like, on the coarse and not very detailes one), see where the water goes, so you have not only river/no river but surface water density for each spot. If it forms a lake, the amount of erosion needed depends on the amount of water that goes through there. Mass is preserved, so what goes into the lake, comes out of the lake again. In the end, every drop of rain meets the ocean, and if you trace it back (it’s just a few thousand drops, that should be possible, you can map every region on the island with a colour that tells you where it will meet the ocean. That and maybe the largest rivers can be generated in advance, and then you can generate smaller rivers and the details of their course on the fly, as you know already for each region how much water goes through it and in which direction.

          … there may be some problems with this approach though, I haven’t thought about it very much … what happens if there is some kind of “wall” in one region that’s not visible on the large map? Maybe that’s a spot where cutting through hills should be allowed? Anyways, I think there’d be a lot less terrain modification necessary for rivers this way.
          Maybe arranging mountains not in big lumps but in chains, that would also help.

          Aside: I don’t think water should always flow to the closest coast. What if there’s a mountain range close to the coast? Will a river from the middle of the island just cut through it because that’s the shortest way?

          • Atarlost says:

            The Missouri doesn’t flow to the closest coast. If it did it would be an extension of the Columbia. The Nile doesn’t either. The closest coast to the headwaters is the East. Your algorithm would leave Egypt dry. Sacramento and San Juacin wind up in the closest body of water but also run parallel to it for most of their length.

        • Steve C says:

          I find your river solution very interesting. Especially because I wouldn’t have thought to cut through things first. I would have attempted to solve rivers with no way down by creating lakes. I would have created a spot of water and had it go down. If it can’t go down it would fill the current elevation’s X and Y axis and go up 1 unit on Z axis and repeat.

          I can see problems with my approach and it wouldn’t surprise me if it completely failed. It’s also interesting that you didn’t attempt this at all when so many other people used it as their go to solution.

      • Xyllar says:

        Exactly. I’m not sure how easy this would be to implement, but as soon as I read the part about rivers dead ending in pits, I thought “that is not how rivers work!” The river wouldn’t “dead end,” it would fill the pit to create a lake until it overflowed somewhere else and continued on it’s way to the ocean. This is how lakes naturally form. I think this would solve the problem of the rivers all looking “artificial” as well.

        • FoundOnWeb says:

          Lakes, small ones, tend to be ephemeral. They fill up, overflow, and the overflow starts cutting into the basin, draining the lake. The part that isn’t drained, fills up with sediment. Ultimately, you get a river running through a flat spot with no lake, almost as if it had bulldozed its way to the sea.

          • Nick says:

            Perhaps you could incorporate the two? Just add a variably sized lake wherever you had to bulldoze through hills. Simple enough, not sure how good it would look

          • Piflik says:

            Unrelated to everything Shamus did…your ‘Ah’ is upside down…

          • Zak McKracken says:

            The question then must be how much of that can be done do procedurally, as you go along?
            I’d say that large lakes could be done on a global scale, along with determining the global elevation and stuff, so you could have a map from which region water’ll flow into which other region, and if that gives you lakes larger than a region, fine. But if you get closer, some detail in one region or another might actually prevent the intended water flow (Look at how Danube and Rhine go: The Danube starts north and west of the rhine, yet it goes far east into the Black Sea while the Rhine goes north and slightly west into the North Sea. There’s actually an artificial channel connecting both.)
            So I’d say to make these things more predictable, i.e. to align the details with the global water flow map, it’ll probably be necessary to move some geological features around. But that would then be on a relatively small scale and thus less obvious. That might actually look like erosion then, and help to make mountain areas look more believable, as what is actually fixing the water flows could look like natural erosion and create those steep valleys you see in mountains.

            • Mayhem says:

              I think a lot of it comes down to Macro vs Micro scaling.
              As I understand it, at present the world as a whole is generated at startup on a very macro scale, and then the erosion filters run over the top to give it landscape and likely climate pattern, and then it gets split to appropriate sized tiles that are textured based on the height & climate information.

              While the individual tiles are loaded on demand, the general shape of the world is created once only, under the assumption the world is a single continent

              What you need to do is add river information at the initial generation stage, so the world knows that rivers go in and out of specific tiles. Have specific ‘trickle’ seeds to trigger at every saddle point in a ridge and flow down. Each X drop in elevation adds Y to river size & flow rate. Each merge combines the flow of both. Streams flow into depressions, and start to fill based on flow rate – if rate = X, fill to depth Y, if Y < surrounding area, stream flows over the lowest edge with same output flowrate as input. Basically makes a small lake. Big rivers will make bigger lakes. Steep hills should create cascading waterfall pools. Since your original erosion simulator probably prevents there being any areas inland lower than sea level, eventually all flows will either stabilise in inland lakes, or reach the sea.
              The key is to not have a limited number of start points, rather have too many – every single saddle in the real world has water flows from the surrounding slopes. Just make the initial ones invisible (1px wide maybe) until they reach a certain size, then start rendering.

              What I think you need to do is have a dedicated ‘water’ layer. First stage does broad landscape layout of continent (mountains, hills, coastlines etc). Second stage does erosion patterns and climate data. Third stage overlays water drainage patterns, so the system knows when a given tile should contain water and how much. From that, you can start the detailed rendering based on where the viewer is.

              Yes, it kind of means you need to store a bunch more information about each tile, but once the macro level has provided the basic guidelines, the micro level can use that same information to render it prettily.

              That being said, I’m not sure how you would go about making canyons etc with this kind of system – this would only overlay water over the top of existing land. Maybe do a second pass based on volume and flow rate, so that slow wide rivers have X depth and fast rivers have 2X depth, and use that to erode hills.
              Hmm, how about if flow rate > X, the river will go right through any elevation < Y, carve alongside until elevation drops and then punch through. Every Z distance in a line, flow rate drops, and width increases by A while depth decreases by B. That might give you canyons and wide river valleys. The two pass system might give you limited oxbows as well.

  4. MadTinkerer says:

    Looking better and better!

  5. X2-Eliah says:

    Wow. Just wow. This is amazing.

  6. Sucal says:

    I swear, this looks better and better every time you post one of these articles. Now I REALLY wish you decided to release the source code. Or at least some kind of incredibly limited demo version that we could walk around and explore in. Especially if you turn that novel your working on into the main plot of the game.

    Although that kind of might ruin the concept of a novelization. You know, having it written by someone who not only wrote the main plot, but also understands video game logic and why things were sacrificed and changed.

  7. Mephane says:

    It attempted five rivers, and all of them dead-ended LONG before they got to the sea, trapped in a spot where they could only go uphill. The overall shape is that the island is high in the middle, but there are still spots here and there that act as pits.

    In real life, these pits will then be called lakes. Heh. Maybe you should have some logic to decide whether such a lake should form in this pit, filling up until it can flow out again.

    • Sumanai says:

      I don’t think you need to fill it up until it flows again (at the macro stage, anyway, where you need to plot out the route), but instead just mark it as “this area has a lake” and then pick the lowest area next to it.

  8. Carra says:

    Reading all this just wants me want to try and have a go at it.

    Well, I did already work through Project Riemers first XNA tutorial creating a simple landscape (oh, so that’s a vertex…).

  9. Rax says:

    Waaiit a second.. Maybe I missed it. Did you solve the problem of the player approaching the river’s source from the coast it then tries to get to?
    Nevertheless it looks great in the end!

    • Shamus says:

      Yes. The macro-building (when I showed the map) plans the entire path ahead of time. The bendy-river stuff (the second half of the article) makes sure it can get through those areas, even if there would have been hills in the way.

  10. Psithief says:

    Another good post about how to make trade-offs look good.

  11. Good job on finding a solution to this. I think you just created a mini-simulation of all the issues that happen with terrain and river. While in the real world it is a bit more complex essentially rivers create curves through the flood plains and winds up slicing through hills. (Actually the land lifts and the river slice through the uplift).

    One thing I found out while learning to do cartography is that if the slope of the river is such and the flow is such (the width of the river for your program) is changes shape from a meandering snake to a braided stream. For example at the end of a river when it forms a delta, It may be something to do later for you to try for extra visual kick.

    http://en.wikipedia.org/wiki/Braided_stream

    • Sucal says:

      That might get a little complicated for now. He would need to solve the merging problem first, before he can start on delta’s and braided river systems.

      Or Volcanos.

    • Dev Null says:

      “rivers create curves through the flood plains and winds up slicing through hills.”

      I’ve spent more time than is necessarily good for me hanging out on rivers, and this was the one bit that looked slightly awry with the last couple of screenshots. (And I do mean slightly; it looks pretty darn good.) Rivers on the flat (and usually therefore in soil, not rock) tend to meander in great huge curves all over the place, as the slow-moving water builds sand bars that get in its own way and then breaks them down again. Rivers in the steep (and therefore often cutting through rock) tend to go in straight lines broken up by sharper corners, as their faster momentum runs them down a weakness in the rock, only to hit a ridge and turn to follow it, etc.

      Shamus, since you are already (it sounds like) adding in some sort of sine wave to your rivers path to get the curves, perhaps you could tweak it based on macro elevation changes? If you know your upstream tile is much higher than your downstream one, make it straighter; if they’re about the same height, make it curve even more. The radius of your curves also gets bigger the more volume you’ve got, but I’m not sure how much of that you can put in in 64m detail blocks – for a big river on the plains, your curves might actually need to be bigger than the blocks, and planning curves at the macro level seems like it would be a whole nother level of (over)simulation…

    • Kaeltik says:

      This.
      This is exactly what I was trying to remember before. The link even has the numbers:

      if slope > 0.016 (unit rise/unit run)
      then create braided stream
      else if slope =/= 0
      then create meandering stream
      else create straight channel

      The equivalent meandering river link has the rest of the necessary values:
      L = meander length
      w = fullbank channel width
      r = radius of curvature at meander apex
      L = a*w
      L = b*r
      average a = 11
      a range = 10-14
      average b = 4.7
      b range = 3-5

      These numbers should work on near-flat floodplains or in deeply incised canyons. Find slope across chunk. If high, flatten a slight sine curve in to the chunk between ends, then carve shallow random walks within the flattened area. If slope low, choose some L < 64 (based on chunk size), randomly choose a and b values within given ranges, calculate r & w, plot & either flatten surroundings or incise into surroundings.

  12. Hi,
    I’ve been reading your blog since I found your procedural city project, and I find your programming articles really interesting.
    Project Frontier is particularly interesting to me because I recently finished a University project which is very similar. I was tasked with creating an infinitely scrolling, deterministic fractal landscape system, and the biggest problem I encountered was block neighbourhoods, as to finish generating one block, it needed the neighbourhood around it to make sure the lightmaps were smoothed together. In the end, I had a ‘SuperBlock’ construct which described the overall detail of the terrain for a large area (on the scale of mountains and valleys) and then I had a separate thread that would construct the geometry and lightmaps for the detail as the player travelled near a new section.

    I never got around to doing rivers, as I ran out of time, but I’m impressed with the results you’ve achieved.

    Anyway, if anyone’s interested, the full project report and source code is available at my website http://www.anonymoustipster.com
    It might prove useful for anyone trying to make their own terrain generator, as I put quite a lot of research into different methods of generation and rendering.

    Cheers.

    • psivamp says:

      Now I have four procedural terrain projects in my favorites. The worst part is that I’ll probably end up doing some procedural terrain myself much later when no one is interested in it.

      • I’m convinced that procedural content is the way forward, there’s just too much content that needs to be created by artists that players are just going to fly past.
        I spoke to some employees of Criterion games and they had teams of people from 7 different countries to make NFS: Hot Pursuit, many of whom worked on the art. One of them told me that they were looking into procedural content for their next project, so I’m sure that more and more advanced procedural content and better tool pipelines are the way to go.

        Plus, coding terrain generators are a lot of fun, feel free to sling me an email if you ever get around to it.

  13. psivamp says:

    Very nice. I can see in the final screenshot that you put dirt back in, but I’m having some difficulty in ascertaining if you river banks are dirt for shallower slopes and then rock for steeper ones or if that’s a function of something else.

    • Shamus says:

      There are dirt patches here and there, according to various rules that escape me at the moment. When land touches (river) water, it becomes “dark dirt”, to approximate wetness. (A similar thing happens along the coast, for dark sand.)

      • Kaeltik says:

        Is there any way to give the exposed rock some sort of stratification, at least on the steepest bits? Would it be possible to project stripes from the side, maybe with a randomized fractional blend?

        Don’t know if that made any sense. Just trying to think of how I would do it in 3DS Max.

        • Shamus says:

          I played around with it. I was able to do so, but the pixel stretching was murder. (Even worse than on my current cliffs.) I shelved it. I think it *can* work, but it needs more thought.

      • Kdansky says:

        Actually, river beds should be overgrown with vegetation, not dirt. You could easily just add a ton of long grass at the borders of rivers, on top of your dirt.

  14. scowdich says:

    God help me, I laughed out loud when I scrolled to the pipe dream screenshot. The creativity and skill with which you’re just solving problem after problem is extremely impressive to me. Here’s hoping it finds you employment, Shamus.

  15. Jordi says:

    It keeps getting better and better. I wonder if you plan on building in lakes and waterfalls and such. I think cool things can be done here.

    At the beginning of the article I was thinking you should move the hills around the river (and not the other way around), because that’s kind of what happens in the real world. Furthermore, I remember in your first article you mentioned how you eroded the terrain by simulating water or something like that. I wonder if you couldn’t use that system to get rivers.
    I’m also curious about whether you plan to do something about the interaction between climate and rivers, because having a river in a desert doesn’t make a lot of sense.

    Also, is it really that hard to determine the flow direction at a river intersection? Can’t you just take the (weighted) average of the flow vectors for both rivers? I know nothing about textures, so I realize that part may be hard, but the movement itself seems doable to me.

    Finally, it may just be me, but in most of these posts I have some difficulty imagining the scale of things in the screen shots. In a previous post, I thought the grass looked more like a bush, and now I thought that the river looked like it was maybe 1 or 2 meters wide (but from the region boundaries I gather that it is more like 8). I don’t know how the remedy this (if that is something you want to do), but maybe putting up a bunch of man-sized (1.8m / 6 foot) sticks at various points in the landscape would help.

    • Shamus says:

      Rivers add a bit of moisture to the surrounding regions. Not nearly as much as the ocean, but enough to bring a bit of green to the desert. I’ve actually found water that way. Wandering through the wastes, and then green grass. Hey! Must be water over there!

      Averaging the vectors wouldn’t really work. As soon as you entered a region with a “T” intersection, you’d get yanked to one side at an angle. I’d have to interpolate all over the T, which would require knowing which two connections were “in” and which one was “out”. And then there would be tracking flow through those S curves. Not impossible, but… bleh. Maybe later.

      Yes, scale is hard to judge. Partly because I have so much rock that a great deal of my small hills look like “mountains!” in terms of texturing, even though they’re only about ten meters tall. Also, tress will much better convey scale.

      • Kell says:

        “Wandering through the wastes, and then green grass. Hey! Must be water over there!”

        This is what Minecraft lacks.

      • Ander the Halfling Rogue says:

        Do you have the big, honkin’, actual mountains done yet? If so, what screenshot are they in?
        And the fact that you (presumably by accident) reproduced the real-life survival technique of using vegetation to find water in the desert is fantastic. It means, at least in this area, you’ve hit the sweet spot of practicality vs. simulation. Practicality because I’m assuming the whole thing still loads up in FIVE seconds; simulation for obvious reasons.

      • Adam P says:

        Alright, it’s a bit late and I may not be fully understanding all the issues with this. But, here’s what my brain says about the current flow of the rivers… draw a “line” or series of points down the center of the each river, these points would just be a position, direction of flow (could be determined by averaging the tangents of each bank in the direction of the coast?) and owner (each river body would have it’s own set). When the player enters the water the river’s point which the player is nearest, acts upon the player’s velocity at it’s direction at a rate figured something like (depth of river at this point * distance from player). Now when the player encounters a junction each river body would calculate it’s point (nearest the player) averaging the vectors should result in a very smooth flow. The opposing rivers in a T should increasingly cancel each other out as the player approaches the final point for the opposing river. As well the “out” movement should also smoothly begin pulling. (This is all assuming, of course that each of the three river bodies in a T junction are considered separate rivers by the function). The sharper bends in an s curve could be a little jerky as the player goes around them and if the points are spaced very far away you may experience a constant acceleration/deceleration however I think if your player physics is handled well with momentum and friction it shouldn’t be noticeable, however you could always average the nearest 2 or 3 points of each river body if it doesn’t take too many cpu cycles. Hope some of this can help in some way.

        I would also like to say (after watching your YouTube videos) that the project looks really amazing! I am profoundly interested in this sort of thing and your project is all very exciting. I look forward very much to seeing more updates on this! (After writing that last sentence I checked and saw that there have been many more updates so you’ve probably already solved this, but it’s now later than it was when I said it was late so I will just post this now and see what exciting advancements your project has made in the morning.)

        • Adam P says:

          Alright, with a few exceptions I’ve read all the “programming” posts on your blog. I have to say, very good stuff, I really love that you take the time to document your progress through different projects, very cool to see. I don’t know if you’ll even read this (I probably wouldn’t), but I thought more about this and realized some changes which could allow it to run more smoothly and also give you a way to control your textures.

          Keep the points that go down the center of your rivers. But, now instead of figuring them directly to the player’s position, when you load a nearby river, run the math for every point within, say, 5 meters of each of your triangles (of your rivers). The result isn’t going to change, so just hold onto it. Now instead of it acting as force upon your player, it should act as friction. In this way, you can keep a realistic maximum velocity without accelerating to it with the river. Now, however you decide to apply the moving textures you have some data for them to use! You can just steal the triangle’s velocity, but tie the speed to the alpha channel. The stiller portions would have almost transparent texture while the raging portions would have a much stronger look. I think this would have a great look overall. Obviously, if it would be too cpu intensive you could always scale it back, it wouldn’t need to be every triangle, it could be groups of them or whatever.

          Sorry if this just not practical I have no experience with moving textures (I didn’t even realize you could do it), so I am just treating it like a particle emitter (and even that I don’t really have a feel for where it starts bogging down your gpu).

    • Dragomok says:

      [...], because having a river in a desert doesn’t make a lot of sense.

      Isn’t the Nile techically a river flowing through a desert?

    • Tengokujin says:

      Rivers going through deserts:
      http://en.wikipedia.org/wiki/Desert#Water

      The Nile being the most common example, though Americans might think of the Colorado River (if they know the Grand Canyon is carved by it)

      • Jordi says:

        Maybe “rivers through deserts” wasn’t the best example, but I do think that generally rivers can influence the climate/ecosystem around them. And actually, when I searched for pictures of the Nile, it showed that the banks are pretty green. Of course, the desert is huge compared to the river, so we say that the river goes through the desert. But on a smaller scale, the part that the river actually goes through, doesn’t look very desert-y for the most part.

        I might be wrong, but I think that a river in a desert region should either be in a deep canyon, or surrounded by some green stuff (which fades out into the desert again). Or maybe it gets smaller in hot climates, because part of the water evaporates.

        • Tengokujin says:

          A vast volume of a river does evaporate through its trip through a desert; as such, only the largest rivers flow uninterrupted through a desert.

          The constant supply of water does two things: erode and/or make greenery grow. Green is more or less a constant, but depending on geography, canyons are less so.

        • Deserts are not defined by their moisture content, but rather by their precipitation. So while the banks of the Nile are in fact lush and fertile it is still a desert because precipitation is sparse.

          The largest desert in the world, the arctic circle, is literally covered in water in the form of ice and snow, but receives almost zero precipitation.

      • krellen says:

        Locally for me: the Rio Grande. (Note to gringos: do not say “Rio Grande River”. It makes you look silly.)

  16. S. Richmond says:

    Eh.
    I dunno. I don’t want to be the asshole here, but here goes -
    This project continues to go down hill, as it were, in my opinion. The architecture of the procedural engine isn’t up to scratch. Generating SECTIONS of a single piece of land at run-time whilst trying to overlay features like rivers that require the entire landscape is doomed to a sub-standard look and feel. Surely you saw that at the start?
    Maybe not. I do seriously like your ingenuity with the problem at hand and your solution is definitely not a complete failure. And one can look at your screenshots and nod in agreement that its passable.
    But, to me, its not really up to scratch these days. I look at games like Dwarf Fortress that can generate extremely vast entire worlds with hundreds of years of simulated societies and history in the space of a few minutes. That one world can sustain the players’ interest for probably the entire lifetime of the game for that player. Its like your favorite procedural motorbike game – The world is generated properly at the start of the game, once. And it is a rich and deep world.
    So I look back at your project and I have to wonder why you are trying so hard to create this engine that demands zero ‘loading screen’ time at the expensive cost of environment quality.

    • ben says:

      I don’t know if I missing something, but it seems obvious to me that to generate a 3D world you need way more memory that for an ascii world (even if dwarf fortress is in 3D, you don’t have any texture or 3D object to load). thus generating on the fly seems to be the only way possible to generate vast 3D environement. (and by the way, talking about Dwarf fortress, if you are familiar with the adventure mode, you should know that this is actualy how the game proceed to generate the chunk of wild landscape (this is particulary visible, and painfull, on old computer)).

      • Atarlost says:

        Textures shouldn’t need to be generated up front. Those can wait until a region is visible. DF has a minimum of ten (IIRC) bytes of information per tile. More than the single int or float Shamus needs on 32 bit machines. More in hilly regions. The tile density may be lower than Shamus’s height map pixel size in micro mode, but probably not by much. Probably a factor of 4 would, given the number of layers generated by DF where elevation changes significantly, would probably average about as much data stored.

    • scowdich says:

      Aren’t you being a little judgmental that this project, which Shamus has been building for a month on a whim, does not meet your exact expectations? If you want Shamus to do what you want precisely, pay him.

      • Esteis says:

        Richmond’s phrasing is a bit harsh, yes, but when you look past that he’s actually offering a decent argument that explains why he thinks ‘generating everything in advance’ would have been the better choice of program design. Too bad for him that it’s la ton qui fait la musique. (Is there an English equivalent of this? ‘It’s the tone that makes the music’?)

        Similarly you, scowdich, have a valid and constructive point when you say his tone comes across as judgemental, but unfortunately you paint his attitude in blacker light than his post actually supports. Of course Richmond doesn’t expect Shamus to do things Richmond’s way just because *Richmond* says so. Implying that that is his attitude, then, comes across as rather quick-to-judge.

        My own post is pretty blunt, too, I admit. I hope I’ve made it clear enough that I do not, in fact, object to either of your messages. I just think they’d be received better if you both used a more charitable tone.

        • la ton qui fait la musique. (Is there an English equivalent of this? ‘It’s the tone that makes the music’?)

          I’ve only come across it in German (Der ton macht die musik).

          ‘You catch more flies with honey than with vinegar’ is the closest English analogue I can think of, but it’s not really very similar now that I’ve written it down…

        • scowdich says:

          You make a good point, and I admit I was rather quick to leap to Shamus’s defense without fully considering my words. I publish things on the internet from time to time, so it kind of gets to me when I see someone else’s work being belittled (or if I think I do). One doesn’t really see comments on a webcomic, for instance, saying “this project is going downhill” or “it’s just not up to scratch”.
          Everyone’s entitled to their own opinion, though, so I’ll try to be more civil in future.

    • Will says:

      Dwarf Fortress has exactly the same problem with rivers though; in fact DF rivers don’t even pretend to be anything other than straight lines and often carve right through the side of a mountain when a small diversion of less than a few dozen squares would have put it right around the side.

    • Sem says:

      I never played dwarf fortress so I read the wikipedia page about it. It indeed says that Dwarf Fortress can generate a world from scratch but (1) the visual demands are a lot less steep for dwarf fortress than for Shamus and (2) it also mentions that the generating can take a few seconds up to a few hours. Now, I’m betting that most geeks are willing to wait ~2 hours to be able to play a game but most people don’t.

      So, either you create your entire world up front and just load it from a datafile (as is now usually the case) but then you have no variation. Every player has the same world. Or you can try what Shamus is trying to do and generate your world on the fly.

      Admittedly, you do have a point but you can’t have a very complex world generated on the fly. It’s either complex and static or created at the moment itself and therefore less complex.

      EDIT : Or you could generate small very complex parts of your level on the fly and use loading screens to switch between the parts but that’s rather annoying and would only work well for indoor levels.

      • Sekundaari says:

        For me at least, the longest wait in DF isn’t generating geography, but a couple of centuries of history.

        And it takes a middle road, the world is created from a random seed and some parameters, and then saved. So players have different worlds, but they can be shared.

    • Deoxy says:

      Actually, Dwarf Fortress does EXACTLY what Shamus is doing – it makes “sections” which are 16 by 16, and you pick a “play area” out of those 16×16 (3×3 up to the full 16×16, for those with sci-fi-powered computers or LOTS of patience), but you CAN’T pick a “play area” that crosses from one 16×16 “section” into another.

      Basically, what Shamus is doing is exactly what Dwarf Fortress does (make “sections” that are seed-generated, then stored), but then he goes the extra mile (or 2… or 200) and makes the sections actually work together as well.

    • John S says:

      It’s hard to take seriously a person who thinks Dwarf Fortress looks good.

  17. Kelhim says:

    So what you are doing is let the river aim for the coast and downhill, deform the current region where it is necessary by cutting through the middle of a region (because that gives both sides along the river the room it needs to not become steep canyon walls), and you “hide” some of the linearity by generating curvy erratic lines instead of straight ones, and greater curves instead of right-angled corners? The result looks very nice, if still a bit regular, but that should only be a question of numbers. Quite impressive work!

  18. Reet says:

    Nice, I really like the look of the rivers. Although that could be my brain comparing them to the horror of those pipe dream ones and thinking they look nice in comparison. However, as a few of my fellow commenters have pointed out, how is this system going to work with lakes and waterfalls? I don’t know the details but with what you outlined in the post it seems like these things wouldn’t be compatible with what you’ve already programmed. Then again you do seem quite capable of working these things out so perhaps I shouldn’t be worried.

  19. Dys says:

    Also, if you’re repeatedly running into problems with needing to know surrounding block data before the player is present, is it possible to have those blocks generated when necessary, as well as the central player occupied block, or would that take too long and cause noticeable framerate drops?

    • psivamp says:

      There is the possible scenario where you need the next block over to make the current block, then that block needs two more adjacent to it. With these type of cascading dependencies, Shamus would have to plan for them. I guess he could widen the radius so that there’s less of a chance that you run into an unfinished mesh before it’s done with all of its dependencies.

  20. Blanko2 says:

    i will say that the landscape looks fantastic!

  21. Shamus –

    I think you need to talk to a lawyer about filing a software patent on some of these solutions you are coming up with. Some of your writing is almost equivalent to giving away your source code.

    As far as rivers go, there’s one physical aspect of rivers that if you are able to incorporate would make for amazing realism – meanders and oxbows. Details:

    http://en.wikipedia.org/wiki/Meander
    http://en.wikipedia.org/wiki/Oxbow_lake

    in a nutshell, a river that is not perfectly straight will erode one bank, which will over time cause the river to flow in an oxbow shape rather than a line. Eventually the river “cuts” the oxbow and becomes essentially straight, orphaning the oxbow which then becomes either an oxbowlake or dries up.

    From the air you see these oxbows all over the place – every river has them.

    Also, keep in mind that the fundamental goal of a river is to widen its path to the sea, so if your geography is “young” then your rivers can cut channels to the ocean, but if your geography is “old” then the river valley should broaden as it approaches the coast. In fact you might even have a flare in width right at the coast (ie, a river delta or marsh).

    • MichaelG says:

      I hope Shamus stays well away from any lawyers. Software patents will be the death of this industry.

    • Simon Buchan says:

      Compare to John Carmack describing Megatextures, or Valve describing their facial animation system, or Naughty Dog describing their scripting system. It’s practically expected for game developers to describe how they do pretty much everything. And no – this is *hardly* equivalent to having his source code: I could build something that matched his description, sure, but it would have completely different results. :)

      • John Lopez says:

        And it fact this openness has lead to the game industry having *less* litigation and destruction of projects because large chunks of the technology have been publicly documented. The goal of the patent office was to get inventions publicly disseminated.

        There are two methods: wait 20 years after the patent was granted to implement some technology a patent troll acquired or describe it publicly so a wannabe patent troll can be countered at the source. I vote for the latter.

      • Otakun says:

        well, I did say *some*, not *all*. At the very least Shamus is protected by having these posts, and the timestamps on his Mercurial database checkins.

        • Unbeliever says:

          I actually read this three times as “…timestamps on his Mercurial database chickens”.

          All I could think was “Bwuh? Shamus is timestamping his chickens?”

          I am clearly tired, and should go to sleep… :)

    • Chargone says:

      the software patent remark makes me want to find you and kick you in the face and other sensitive bits repeatedly. figuratively speaking, at least.

      side effect of watching the absolute stupid that results from such things (and when corporations get hold of copyrights. and the abuse of the trademark system… and… just IP in general is a mess and software patents are one of the worst examples of things that just should not exist. they do far more to cripple the industry than help it.)

    • I’m wondering if he also has a solution in mind for building a river delta when the river gets to the ocean. But since the delta would be small (restricted to one terrain box, maybe), it’d probably be very easy just to figure out where the river terminates and plonk down delta. Well, easy compared with building the river itself, anyway.

  22. also Shamus – maybe you can use a electric current analogy for solving flow at intersections. Treat the water like current and the landscape height like potential. Kirchof’s laws might help?

    Then again i could just be misunderstanding the constraint imposed by the procedural aspect in which case never mind.

    • Ben says:

      The current analogy doesn’t really help here because in general the angle of the two wires coming into a node doesn’t matter (save for issues like PCB layout). The problem Shamus is having is that you have 2 flows coming in and they have to be interpolated into each other somehow. To do this the flows of each river has to be tracked basically from beginning to end which could get very computationally intensive very quickly.

      • Otakun says:

        i see, i misunderstood his goal I guess. but at an intersection you could try defining some general rules and then let the procedural aspect take over. Kirchoff’s law apply to water (flow into the intersection must equal flow out) and then you could have a velocity profile across both streams (laminar at the center, zero at teh edge) and do a velocity vector addition at every point where they meet.

        also if two rivers are intersecting they probably wouldn’t intersect at a T but due to teh curves Shamus incorporated it would be at some angle < 90. that should help with the abruptness.

        at any rate i dont think you need flow from teh start of the river, just teh velocity profile at the point of each river immediately porior to the intersection area. And if you dont have that, you can always make an assumption that velocity of all water is constant, and then you just need to add the directional vectors and not worry about speed.

        • You’re forgetting that the water isn’t “water”–it’s a *texture* on a flat plane. He wants to make it so the textures don’t have huge obvious ugly seams where the various rivers meet up.

          Basically to create “flowing” water in a game (in its most simplistic form) you just have the texture move in a given direction. However, if you have edges where two textures meet, there’s going to be a line where the water is flowing one direction prior to the line and a completely different direction after the line. It looks really ugly.

          Now, if it were me doing this and for some reason I absolutely *had* to have flowing water, I’d create several procedural “river joining up” terrains that do things like plonk down rocks, rapids, bridges, whirlpools, marshes, waterfalls, etc. to hide the seams, and rivers would only flow into each other when the water flow was within a certain narrow angle so that the seam wouldn’t be big, ugly, and obvious. I’d also use a very simple water-moving texture, just a few lines that would be fairly easy to line up with anything.

          They have several really nice-looking water textures in DDO, but unfortunately it doesn’t account for container, so you have little 3′ x 3′ square pools that look like they’re flowing somewhere. It’s rather odd if you watch it for any length of time. Also if you’re in a position to view the water from high above (which happens), it looks like a patchwork quilt–the tiling is REALLY obvious.

          • I didnt forget that water was a texture – I honestly didn’t know!

            so,I learned something. maybe you coudl pregenerate textures for combining streams (like chevrons?) at various angles and then use the appropriate one based on angle of intersection?

            Or, just have the bigger river dominate. Have the texture of the smaller one fade out as it enters the larger one (modulated by cosine of the angle of intersection). The larger texture would continue on unimpeded. So the textures would need to be a little transparent…

            im really way out on a limb here. Have barely any idea what I am talking about :P

  23. Mik says:

    Shamus: Perhaps you already thought through this, and I am by no means a coder, but since water seeks the lowest level, why not *start* the rivers where they join the coast (or a lake) and have them “climb” by seeking the next-highest point on the map? Basically, calculating the path by the opposite of starting at the peak and dropping.

    Each vertical increment could include a chance of branching into new tributaries as the river “climbs” its path and encounters a point with two equivalent options to exit upstream.

    You would have to find some way to get an appropriate number and spacing of river deltas and mouths on the coast, but they could be more closely spaced on the “windward” side of the terrain, and larger where the coast is flatter and sandier.

    Is that type of ‘reverse erosion’ worth considering? Anyone?

    • Danath says:

      Right up until it climbs up a cliff where there is a sudden dip. Then you either automatically dig a trench through the cliff to reconnect with ground level or get water going uphill.

    • Arkady says:

      Ooh. I like this.

      If he had an inverse function as well he could generate rivers from the top or the bottom.

    • X2-Eliah says:

      What if it climbs up to a point where the only way further is downwards? Or where there are both downwards and upwards possibilities? (e.g. a narrow bend like a saddle; two hills on either side, but also two plains in front and back, your algorithm would scale up to the curve between the hills, but then it would pass the curve and there would be down-ward sloped area in front of it..

      • Chargone says:

        well, when there’s no more ‘up’ possible then you’ve just reached a spring. unless you include some absolute minimum height for springs, in which case you cut a trench down, then continue. (need to convince it not to imediately flow back up the same hill somehow though.)

        remembering that the path is starting at the rivermouth, so the water still ‘flows’ downward. in the case of the saddle, where it has two up choices and two down choices, it Came from one of the down choices, the up is not an option, and it can/will split when given options like that, spawning two tributaries, one to each side. ‘course, i can see that particular arangement being more likely to result in the ‘spring or cutting’ result.. and the cuttings would go through the hill rather than the low point. it’s path would probably need more rules this way to prevent looping and other odd behaviour, but it seems like it would solve the problems described in the article, at least.

    • The problem with this idea is one of origins – or rather, of potential starting points. Consider that Shamus is starting from a selection of the highest points on the map (eventually mountains, I’m guessing)

      This is necessarily a limited set of places to choose from.

      Now consider how many places the river could END.

      That would be any place on the coast. At all. Around the whole map.

      Yes, you could just pick at random – but you have no guarantee that those backward tracing rivers would get to the highest points on the map.

  24. Alan says:

    Hmm, keep this up and you can add geologist to programmer/writer.

  25. Hitch says:

    Wow. I’ve been reading this series and playing Minecraft, which has gotten me thinking about the two of them. While playing Minecraft the other day I thought, “Rivers would be really neat in this.” Which led to, “I wonder if Shamus is planning to do rivers in his game? It looks like he’s going for something a bit more realistic looking. Maybe I should suggest it.” Then finally, “Rivers are probably crazy hard. I’m not going to try to add rivers to Shamus’ plate. He’ll do them himself if he wants that headache.”

    Then today, I find this article. ;-)

    Oh, and with regards to your first paragraph, Shamus… one of your great strengths is being able to translate ideas from coder to plain English comprehensible to non-programmers.

    • Chargone says:

      seriously. Shamus could get a job writing manuals or something. … of course, given how much better he’d be at that than most, they’d have to pay him a lot… an unwillingness to do so probably being how they got where they are in the first place… meh *shrugs*

  26. Mike Riddle says:

    I seems to me that your goal of a procedurally generated environment is going to run into this type of issue more than once. As I understand (possibly incorrectly) the goal is to generate terrain a region at a time as you go. Rivers are a problem because they are a detail/feature that requires coordination between the regions because their “impact” is greater than “line of sight”. There are other terrain features that will span regions (roads ?) and terrain features that are large enough to effect more than one region. A very large city for example might be impact the neighboring regions “urbanity” or large city might have more roads near it. These are feature/objects your application needs to know about before they are “in-sight”.

    Given that and your solution of a hybrid/two phase approach, it seems to me that you would want to very soon, sit down and group your region features into two categories: local and global. Then you can plan the master world completely before layering on the local regions.

    Currently you have three global features so far accounted for: Climate, general elevation, and rivers.

  27. Factoid says:

    On the subject of River Merge vs Flow, I’d say you almost have to have both.

    It’s never going to look right from eye level if the water doesn’t appear to be moving. But if you don’t have rivers that merge and join, you’ll have these bizzare, impossible rivers that start skinny and end huge, with nothing contributing to them. Maybe that’ shard to notice from eye level, but from the air it’ll look weird.

    I think the “easiest” thing to do to make the texture look right is to play with the width and speed of the river after the merge. Add in either some small rapids, or a little swirl (depending on the angle of the intersection) to hide the seam, then make the downstream river speed increase a bit, which would make sense, and would look OK with a bit of texture blending and stretching to simulate the “acceleration” of the water.

  28. Andrew says:

    Nice Job Shamus,
    Just a point on the confluence of 2 rivers, I don’t know if you have ever had the “pleasure” of swimming in the rapids caused by 2 rivers – but typically you go in the direction of the faster larger river. Textures and whatnot are designated by the bigger faster river, with a potential rapid where the 2 currents meet. Hope that helps with your texturing problem

  29. Kailvin says:

    Kind of an odd idea. But in a worst case scenario where the river can not go in any direction (All are generated) What if it just takes the ungenerated area around it and becomes a lake. Lakes can flow into lakes (See the great lakes) and on top of that. it adds lakes to it! Not just rivers! Two birds one stone

  30. Tohron says:

    Couldn’t flowing water textures just consist of a bunch of 2D particles moving along the path of whatever river line they’re currently on (if the river merges, they move along the path of the new river). Likewise, force on the player would be in the same direction as the particles.

    Also, if a river becomes trapped in a large valley, couldn’t you just form a lake with a level high enough for the river to proceed?

  31. Damn, that is a damn thing of damn beauty, dammit. Maybe a future update will make it a thing of dam beauty, as well.

    P.S. DAMN!

  32. HeroOfHyla says:

    The rivers look fantastic to me. Good luck getting it looking right while animated. It’s the rocky slopes that bug me. It just doesn’t seem right to me, at least on that small of a scale. Do note, however, that I have absolutely zero experience with how natural vegetation should look. I live in a desert, so the closest thing I get to grass around here are tiny little invasive shrubs.

  33. DaveMc says:

    “Sorry if it’s confusing. I did what I could to balance information and readability. I tried, I really did.”

    You succeeded fantastically well. I’ve really been enjoying this series, thanks for these!

  34. Futurehero says:

    I don’t understand what’s so difficult about having flowing water and merging textures?

    Can’t you have it blend the textures when they get to a crossroads?
    I’m no expert, but didn’t you do this exact thing to make it so that biome transitions don’t look as abrupt?

    Or just have textures that “fan out” water, like it’s being dumped in a lake, and add those where the river enters an intersection?

  35. Slothful says:

    What about rivers joining eachother?

  36. Duoae says:

    Really great article, Shamus, really enjoyed reading it.

    A thought or two on the future rivers problem:

    I’m no coding genius (the opposite in fact) but i’ve been around my fair share of rivers and i’ve noticed a few things – you can’t really see much “flow” in/on bigger and slower-moving rivers unless something’s floating in them to give you a reference, with smaller rivers and tributaries or where the water is flowing quickly you can see the swells and eddies much more clearly.

    Applying this logic to the textures of “water”, i’d imagine that you’d have a “flat” water texture, overlaid with a “detail” flow texture. The water texture wouldn’t flow but might ripple in place, for instance, whereas the detail texture would have “squiggly” (behold my technical genius!) lines that moved in the direction of downstream.

    To create different types of water and visual water flow effect you’d just alter the two variables over how compact each texture is and which one is less translucent. e.g. A flat, wide, slow-moving river would primarily have the water texture visible but could have a very slight detail effect that’s “zoomed in” on the squiggles, making them quite large but few and far between.
    A small, thin, fast-moving river, however, would have a mainly opaque detail texture which would be very zoomed out, so that the squiggles are very close together and barely distinguishable from foamy water as it’s churning air into itself.

    Here’s a couple of rivers that i think actually demontrate this effect nicely:

    http://www.edupic.net/Images/Rivers/potomac_river076.JPG
    http://www.jessstryker.com/national-parks/rocky-mountains/images/ColoradoRiver1.jpg
    http://blueridgeblog.blogs.com/blue_ridge_blog/images/2007/06/08/watauga_river.jpg

    You could even use the same textures on the sea as well with different effects.

    The joining flow problem could easily be solved by telling the game to assign the longest or widest river as the primary river at the junction. The other one or two rivers joining that become subsumed into it’s path (again with the textures thought about above coming into play at the intersection). With regards to movement of the player or an object within the flow, remember that in rivers, the strongest flow will win out. i.e. If you flow into a big river from a small tributary, you won’t get sling-shotted across the river to the other bank; you’ll enter the flow and continue on down its path.

    The way you could emulate this in a game is by having the primary river dictate flow but have the smaller rivers provide a “shove” of force towards the centre of the primary river at the point they meet. After that last shove, the secondary river would exert no further force and the force/movement of the primary river would instead reduce and stop any lateral movement that is perpendicular of its flow – presuming you have that coded in, of course.

    Anyway, i hope these thoughts are somewhat helpful, even if they’re just total crap :)

  37. MrGamer says:

    It looks quite cool. Any hints at what the gameplay will be like?

  38. RTBones says:

    Funny. You note that the last river picture still looks a little artificial from above. I was almost immediately reminded of the California Aqueduct.

    If you are looking for a way to model a confluence, you could “combine it” in parts. Take three rivers (Mississippi, Missouri, Illinois). Mississippi and Illinois come together. They are “one river” for a stretch, until the Missouri joins. The “one” river and Missouri join, and now you have “one more” river (which is actually the Mississippi). This doesn’t really solve your problem texture problem, unless you let the confluence be dominated by the “larger” river (which is what happens in reality). Basically, at the confluence, “stop” the smaller river and let the “larger” one take over. Your other way to solve this would be to build a “lake” that the rivers emptied into. You’d have flow “into” the lake. You’d have “still” water on the lake. Then you’d have flow “out of” the lake.

  39. Tharo says:

    It looks a lot like good old Total Annihilation. I like it.

  40. SteveDJ says:

    Maybe I missed this in all the above comments, but…

    What about a simulated Water Table under the ground? It would seem like something you would do at the macro level, when you set the overall elevations and such. Then, places where the water table is above ground, you get your lakes.

    Then could rivers be some extension of this? Just arrange the water table to ‘peak’ above ground over long stretches, which you ‘convert’ into river beds?

    Or, maybe your current river system could, instead of just heading to the ocean, just heads to points where there are these lakes (heading towards higher water table areas)?

    But this would also offer you things like swamps (water table right at ground level for large regions). Ooooh — maybe make some quicksand even? :)

    • Older games would actually do this–there’d be one “water level” for the entire level and anything that was above it was out of water while anything that was below it was underwater.

      It looked dreadful.

      Not to mention the fact that you would either a.) need a lot of micro water tables for each level of height above sea level, or you’d never have mountain lakes (which do occur in real life) or b.) you’d have a bazillion tiny lakes every time the terrain height dipped just a little bit. Which would also look dumb.

      • SteveDJ says:

        Oh, no no – I was not meaning a single, flat table level.

        I was envisioning making a second elevation layer of data (same as what is used for hills/mountains, etc), it just uses different noise or randomness. This is the water table.

        So someplaces, water is very much far below the ground (if digging for a well, you’ll have to dig deep) — this might lend to where dry/desert areas appear. Other places, even high up in mountains, the water level is close to the ground level, but just below. This could be the basis of where rivers tend to be?

        And of course, other places the water level is above ground — the data might even be plotted as if a mountain of water. This just becomes flat – with rules deciding where to put the level (lakes, or just swamps).

  41. Jeff says:

    I have a question…

    I was initially under the impression that everything was generated as you walked around, for an effectively infinite area. However, I see that the intention was to have a limited area – a large island, as it were.

    That would therefore mean you have to do a macro-level generation prior to generating the micro-level terrain that we see, right?

    So shouldn’t the water tables be dealt with in the macro-level, which would then shape hills, mountains, and assorted terrain as they’re generated?

    I kind of assumed that water would be the single greatest influence on terrain generation.

  42. Stringycustard says:

    Not sure if it’s possible with your generation algorithm, or if somebody above has already mentioned this, but is it possible to lower the maximum height of the surrounding hills or land as it approaches a river? Not all of it, just some of it, which would stop the canyon type effect that’s frustrating you. You could still have a large maximum height mayber, but just make the chance of terrain being allowed to use that height far less likely as it gets closer to a river (or, as seems to be the case here, a river gets closer to it).

  43. Alexander The 1st says:

    I was actually curious – why not, instead of going from inland-out, why not go outer edge in? Would allow for elongated deltas, for example, and you just work your way up over/past mountains.

  44. Bentusi16 says:

    I’m not sure if you have had this suggested before, but what your doing reminds me a lot of Dwarf Fortress world building. Just how it comes up with geography and things.

    This, for example, sort of popped into my head when I saw the rivers and things (not this image exactyly but the general idea behind it.)

    http://www.wuphonsreach.org/Games/DwarfFortress/WorldGen/v0.31.18/world_map-region1-550–10081-halfsize.png

  45. Joey Palzewicz says:

    Excellent, Mr. Young. Good solution, good implementation.

    Here’s hoping for at least a demo sometime soon!

  46. decius says:

    It seems like you want to be able to describe every region using nothing but the data for generating the world and the coordinates of the region. Therefore, the data for generating the world MUST contain either every feature, or a way to generate every feature. For rivers and lakes, why not include the location/route and all the vital data? Each region then gets whatever additional data is needed to interface with the adjacent region: “I have a river of this description entering at this cross-section and leaving at this cross-section”. This data will have to be generated worldwide, along with the route of each river, at some point prior to generating any region. The path the river takes within the region can still be decided when the region is generated, it just has to enter and leave that region at predetermined points (vectors?)

  47. elias says:

    Seems like it would look even better if the slope of the river banks varied…

  48. UnwiseTrout says:

    I have nothing constructive to add to this conversation, this kind of creation not being my forte, but I will say that this looks exceptionally beautiful and I’m really enjoying *watching* the process.

  49. Zaghadka says:

    Awesome. I am, however, disappointed that Rutskarn hasn’t made a wry comment about your dammed problem.

  50. James says:

    I don’t know much about coding, but I DO know a bit about rivers. The look of a river in the real world is dependent on two factors: the underlying geology and the “age” of a river.

    As far as geology goes, there are two things that are important: How hard the rock is to cut through, and how the rock is oriented. Something that’s hard to cut through and homogenous, such as granit (or blacktop) is going to have sheet flow or braided streams. There’s no way to form preferential channels, so it just goes everywhere. In contrast, something that’s easy to cut through is going to VERY quickly develop channelized flows–those “rivers in the desert” often form arroyos, steep-walled channels for rivers ranging from a few inches to a few meters in height. They can form in a few decades, as the Salton Sea demonstrates. And if you get alternating hard/soft rock you just get weird looking things (there’s a type of river, who’s name escapes me, which amounts to various tributaries running parallel to one another until they hit a more or less central channel, then turning 90 degrees and flowing out of the area).

    As far as age goes, most of the time a river is pretty straight when it’s young (near the source, or newly formed–they amount to the same thing). It gets more and more meanders as it ages/goes downhill; at the same time the floodplain gets larger (thanks to both erosion and flood deposits piling up on one another). An old stream (either ancient, or far from the source) is flowing over essentially river mud, and meanders all over the place, both in terms of being so curvy that you get dizzy navigating it and in terms of the river moving with time (the Mississippi has been trying to re-locate its delta for decades, and the Colorado River switches between ending at the Gulf of California and the Salton Trough every few centuries).

    I get why your process makes sense from a game design standpoint–but it’s nearly nonsensical from a geologic standpoint. Which isn’t bad (no one gets geology right in games). I just think that a better understanding of how rivers work (and this by no means is even an adequate introduction–fluvial processes get their own sessions at GSA, and a serious stratigrapher would laugh at my post) may help you out.

  51. Maybe this is just me getting overly excited about something I just learned… but I was thinking, maybe you could build an A* algorithm for plotting out the course of the rivers. You can add extra weight to crossing region borders, for example. Rather than just taking the cheapest path, you could take the cheapest path with a unique cost, that way it will always create the same path when using the same starting point.

  52. Shatterer says:

    I could follow the logical steps behind the previous posts, but this one went a little bit too far. Still, congratulations on the clear descriptions and apt screenshots that help immensely with understanding this particular post. If I may, I would like to help a bit with creating a less artificial environment.

    It seems that for each region where there’s a river it enters/exits at exactly the centre of each side. At least that’s what I can tell from the screenshots. Wouldn’t it look better if the entry/exit point is a random location on the side, with perhaps a weighted preference to the centre of each region’s edge? It would only happen on the micro level of generating a region, but perhaps it might add a little bit too much computation time. Especially if you want to make the river a sine wave.

    Still, it’s an impressive piece of art you’ve created there. Knowing that this detailed environment is created via procedural content really shows what it’s capable of.

    Edit: and then I see that the person above me has made the exact same comment I wanted to make. *sigh* Guess I should have been faster.

  53. andy_k says:

    Hi Shamus, I am really enjoying this series, and as UnwiseTrout said I don’t have much to add… Looking forward to the finished product, in whatever form it takes.

    However for some reason I still have an urge to comment and give some helpful advice, but I think any suggestions I have will be about as practical as the advice given here:

    http://www.youtube.com/watch?v=tNfGyIW7aHM
    (Monty Python – How To rid the world of all known diseases)

  54. Benjamin says:

    Would it be possible to do the following?

    Create a texture for river surfaces such that it can wrap seamlessly from edge to edge; when two rivers meet, treat the texturing more like you have two rivers’ surfaces now sharing an edge rather than becoming a single river.

    Next time you reach cross-river edge of the texture pair, swap in a single river surface texture, so more rivers can join up with it later.

    I’m sure this would take a lot of work, if it would work at all, and you’d only be able to have rivers join up with others one at at time, but if it did work, you’d be able to have textured branching rivers.

  55. Winter says:

    Someone has probably mentioned this, but i imagine you probably want to cop out at this stage and just not have “flow”. River flow is going to be hard, and what do you get out of it? Verisimilitude? Most rivers (up to a certain size) don’t have really obvious flow, i don’t think. Even ones that are larger may not be obviously unless you’re really looking at them–though obviously if you stand in them it becomes extremely obvious.

    If you want to add a little bit of fakery back in, keep water flow out except in two scenarios:

    1. You are near a “coast”, thus the water should go into the ocean–you can add some (graphical-only or not) flow to the water, there.
    2. Rapids, which can be pre-set along rivers and (i imagine) programmed deterministically.

    I don’t really know what i’m talking about, here. This might look super awful in practice. I do go canoeing a lot, though, so i’ve seen a lot of rivers.

  56. MaxDZ8 says:

    I don’t understand. Couldn’t you just make the river “flow up”?
    I mean, instead of tracing them mountain->sea, why not to just do the opposite, depending on player direction?
    This is mostly out of curiosity as I think the current system works just fine and so it is ok.

    • Shamus says:

      Explanation: The problem is, the rivers wouldn’t go very far inland. It would get a few hundred meters in, and run into one of those bowl-shaped depressions. It would get to the lip of the bowl and would only be able to move down. (Which would result in a river that flowed up.) I could adjust the logic so that the river would try to stay level instead of going uphill, but then they would just circle the island along the cost.

      The only way to get rivers to flow from the mountains to the sea is via bulldozing.

      • Simon Buchan says:

        Or accurate lake generation, of course. I don’t see an easy way to implement that directly with your current 2-phase design, however, since tiny height changes in your detail texture could change the correct lake size by huge regions, easily larger than your patches. Perhaps something along the lines of computing min-max heights per patch to compute ‘potential lake’ regions, then munging the region’s mins and the lake height together.

  57. Adam P says:

    The river in the last screenshot looks stiff and lifeless. Its shape isn’t very dynamic and doesn’t imply motion.

    You’re shaping the hills around the rivers, so what if you took the sine wave you have and used it as the lowest (fastest flowing) point of the river? Then, take a V and use it to shape the width, changing the offset of the top points based on how hard the earth its touching is: harder materials (rock) reduce the offset, while softer materials (dirt) increase the offset. In addition, the inside bend is more likely (but not always) to increase the offset while the outside decreases it.

    I don’t know where you’d get the hardness of the ground from or if you could reuse that information somewhere else, though.

    • Adam P says:

      (I ran out of time to edit this in.)

      I also had a thought about how you could do water flowing textures, which could also lend itself to solving the width “problem” (if you think it’s a problem) I mentioned above.

      First, you would construct an image of each river, where one 1px = 1m. Or maybe just construct an image the size of a region, for each region that contains a river. That’s probably going to be a lot more data to generate/calculate than I think it is, especially if you’re going to be scaling your world up. I’m not a programmer, so I really wouldn’t know.

      Anyway, generating the image(s). Using the red, green, and blue channels to contain different types of information, you could paint your river data. Red is river flow, green is turbulence, and blue is amount of sediment. Red affects how the texture is constructed, green affects how much the river mesh is deformed (I’m assuming that your water is a separate mesh that can be deformed in real-time), and blue affects the color of the water.

      Starting at the river’s source, paint some yellow pixels (255,255,0) going along the river towards the coast. As the river travels away from the source, decrease the amount of green and red. When the river is going downhill, increase the intensity of the red. When the slope of the river decreases, increase the intensity of the green (to simulate the effect of the water colliding with the concave shape of the river bed). When the river turns, the inside edge reduces the intensity of red and green, while the outside edge increases them. As the river runs over dirt, increase the intensity of blue. As the river slows down and the slope changes, decrease the intensity of blue.

      What this would do is effectively let you brush two (or more) rivers together. Where the rivers join, the blur function would automatically figure out how fast the water is flowing and what it would look like. You’d have your players struggling downstream with no effort!*

      As for the texture, you could have multiple texture layers. The background would be black, with each layer above that having a different brightness value (the pixels are grayscale), you could take a white spray and spray it going horizontally on a sine wave. The flowrate information would make the spray travel across faster, decreasing the frequency of the sine wave. The turbulence information could increase the number of layers, the number of spray lines, and/or the amplitude. This texture would be overlayed on the blue water mesh (so the black doesn’t show through), the sediment information change the amount of brown in the polygons. (Aside: Would it be possible to color all water based on the temperature, with warmer water being a light cyan and colder water being dark blue?)

  58. kuyo says:

    couldn’t you make it so if the river were to hit a pit it would fill it and then continue? That’s more or less what happens in nature, and it would create lakes and add another feature to the map. Though, that might result in giant continent consuming lakes and the effective rise in water levels might submerge previously generated areas.

  59. James Pope says:

    You know, even if this was just a procedural terrain generator I can see it resulting in awesomeness, especially with a “terrain alteration tool” or ten to play with the regions with modifiers. Being able to grow a natural looking map and all that, don’t people make money on those sorts of things selling them to PnP roleplayers?

    I mean if you could also churn out a game with the engine that’s fantastic and all that, but meanwhile you could churn out something something approximately between Photoshop and those CPU busting terrain rendering programs.

  60. Kdansky says:

    First picture reminds me a lot of Realm of the Mad God.

  61. Chris Louviere says:

    Dude, all I can say is that you’d be dangerous with money, time and a few minions. The things you have done in a matter of weeks look quite competitive. I’d love to see what you could do as part of a team with some money…I am just saying.

  62. Tim Gilbert says:

    Your rivers already look better than anything I could create.

    If I might make a suggestion, you’ve already solved both the river-to-the-sea problem, and the how-to-create-lakes problems separately. If you add a two multipliers to the terrain cutting code that sometimes only cuts 1/2 to 3/4 through the hill instead of cutting all the way down to the base of the river height, that would create basins for lakes to be generated at runtime. You could alter the size of the lakes by changing the random depth of the cuts, and the number of the lakes by changing how often it makes or doesn’t make the full cut.

    Unrelated and probably not useful for your simulation, but another way (besides lakes) that nature solves the problem of trapped streams is by going underground. The stream seems to disappear from one point and appear out of the ground in another as a spring.

    Something that may or may not help your rivers look more natural. While river volume normally grows steadily from origin to coast, the width of the river varies a lot with local terrain, becoming narrowing and deeper in steep terrain or where it flows straighter, and shallower and wider in more gentle terrain or where it meanders more. It doesn’t need to be calculated on the continental stage since the volume isn’t changing. But when the player is in a set of local regions, it might look nice if the width of the river varied a bit. Since the player isn’t actually checking the flow volume, you probably wouldn’t have to do anything other than add a slight randomization factor to the width of the river for each region based on the hilliness of the region and how much the river is turning.

    Anyways, I love reading about your procedurally generated projects. I hope you continue to do them for a long time.

  63. Sylvain Boisse says:

    Hi Shamus!

    I’ve been reading through many of your series with MUCH interest. For this particular water problem, I had a suggestion.

    Could you reverse the order of generation between terrain and water?

    I mean, currently you tried to do this:
    – create a height-map,
    – then tried to figure out a path for rivers
    But this failed because it’s a local solution and you want it global

    So you went back and did:
    – A height-map
    – Merge it with a procedurally generated river.

    My suggestion was to go the other way around:
    -1) Create A procedural network of river first (just like a city’s street generation), that would :
    a) start from deltas on an outer island shape
    b) climb more or less steadily, creating lakes wherever you want
    -2) Then ONLY fil in the gaps with procedural terrain, with a constraint of height (and, possibly of steepness, but that would be tricky) on the edges. To do this you should be able to multiply a random terrain with a function than goes to zero on the edges (somehow… Haven’t thought about that one yet)

    The advantages:
    -the rivers would really flow down, with lakes and deltas
    – The terrain in a patch between rivers should look just usual, so naturla enough

    The tricky parts (It wouldn’t be so funny without them):
    - Find a function that slowly zeroes on a given boundary, and is pretty much constant anywhere else
    - Match the steepness of terrain on the banks of the water.

    That’s my suggestion, of course open to improvement. (I hope someone reads this)

    Keep up the good work!

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!