{"id":12076,"date":"2011-06-20T05:13:56","date_gmt":"2011-06-20T10:13:56","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=12076"},"modified":"2011-06-20T05:13:56","modified_gmt":"2011-06-20T10:13:56","slug":"project-frontier-7-river-raid","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=12076","title":{"rendered":"Project Frontier #7: River Raid"},"content":{"rendered":"

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. <\/em><\/p>\n

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.<\/p>\n

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.<\/p>\n

Here is what the world looks like during my default build:<\/p>\n

frontier7_1.jpg<\/td><\/tr><\/table><\/p>\n

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.<\/p>\n

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. <\/p>\n

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.<\/p>\n

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. <\/p>\n

(Time passes.)<\/p>\n

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:<\/p>\n

The colored square in these shots is just a flashing marker to show where I’m standing. Just ignore it.<\/td><\/tr>
The colored square in these shots is just a flashing marker to show where I’m standing. Just ignore it.<\/td><\/tr><\/table><\/p>\n

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?<\/p>\n

frontier7_3.jpg<\/td><\/tr><\/table><\/p>\n

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<\/em> 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. <\/p>\n

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. <\/p>\n

frontier7_4.jpg<\/td><\/tr><\/table><\/p>\n

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<\/em> 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.) <\/p>\n

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? <\/p>\n

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. <\/p>\n

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?<\/p>\n

frontier7_5.jpg<\/td><\/tr><\/table><\/p>\n

Words fail me. <\/p>\n

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.<\/p>\n

Here, let me show you what this looks like so that you can see region boundaries:<\/p>\n

frontier7_7.jpg<\/td><\/tr><\/table><\/p>\n

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. <\/p>\n

Here is how a region looks to the generator:<\/p>\n

frontier7_6.jpg<\/td><\/tr><\/table><\/p>\n

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. <\/p>\n

(The next day.)<\/p>\n

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.<\/p>\n

frontier7_8.jpg<\/td><\/tr><\/table><\/p>\n

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:<\/p>\n

frontier7_9.jpg<\/td><\/tr><\/table><\/p>\n

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. <\/p>\n

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:<\/p>\n

frontier7_10.jpg<\/td><\/tr><\/table><\/p>\n

That gradually grow into mighty rivers: <\/p>\n

frontier7_11.jpg<\/td><\/tr><\/table><\/p>\n

In the end, the grid is well-hidden:<\/p>\n

Click for larger view.<\/a><\/td><\/tr>
Click for larger view.<\/td><\/tr><\/table><\/p>\n

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:<\/p>\n

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.) <\/p>\n

This is a decision to be made later, once we’re talking and thinking about gameplay. <\/p>\n

Onward!<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-12076","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/12076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=12076"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/12076\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=12076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=12076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=12076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}