Tuesday, October 22, 2013

Water bodies

There is a good reason why I have postponed doing water. It is not because I consider it particularly difficult. Water is bound to simpler rules than other systems I have already looked into. I had a different reason.

Water is less dense than buildings and terrain. A damn or a mountain will determine where water goes. In my mind, the heavy stuff must be there first, then comes the water. You may say water does have a significant effect in terrain features. It is true, but as you will see in my next post I think there is a way around that.

Anyway I wanted to have a better idea about my buildings and terrain. I did not want the water solution getting in the way. I think I have reached this point now, it is time to look again into the water generation.

This is about generating large water bodies like rivers and lakes. This is not about water flowing downhill. I think I will have two different systems for this. Even if the water looks the same, it will be handled by different parts of the code. Ideally you would like to make no distinction between a lake and water inside a bucket. In reality it is all the same, but sadly our hardware is eons away from that. As usual we need some clever hacks.

I am trying this system now:

You start from a heightmap. Your terrain does not have to be heightmap based. It could be full voxel with caves, overhangs, etc. The heightmap defines the surface visible to the water simulation, it must register with the terrain volume. This heightmap looks like this:


Nothing fancy here, this is your run-of-the-mill heightmap. But how you section this work is important. I chose to generate tiles approximately 50 km wide at once. That means all the rives and lakes will be enclosed in that tile. You won't have a river going for 100 km with this approach. If you want that, the tile size would have to be bigger. In my case 50 km was a good starting point.

The next step is to add some water sources to it. You do not do this everywhere, just where the terrain is high enough. For a 50 km tile I add around 200 points.

Then you find the closest path from each point to a lower plane, which you can consider to be the ocean level. You can use any path finding algorithm, like A-star. This gives you rivers, which show in blue below. You can see ocean water in a darker blue:


The red points show the water sources. As you can see the rivers follow the path of least effort over the terrain, always looking for the ocean.

I also wanted to have lakes, but did not see a simple way to add them. That until one day I was debugging the river path-finding. To find that bug (which I already forgot what was about) I chose to highlight the exploration the river algorithm was doing before selecting a particular course. I noticed the path-finding would spread its search whenever encountering flat surfaces. It was behaving pretty much just like water.

Once I added the areas where path-finding searched, I got lakes!


I liked how lakes could appear at different altitudes. Also if you notice the heightmap values in the lake shore, you will see they do not diverge by much. This means the lake surface is mostly flat. In real life often lake surfaces are not entirely flat. This is because the lake actually flows.

I will finish this topic in my next post, where you will get to see how to come up with the actual water surfaces. Also how you find out where waterfalls should go. You got to have those waterfalls.




39 comments:

  1. I am excited and can't wait until next post!

    Anyway, can't you have all the water be generated like the lakes? That way you can have land below sea-level. Because right now, Ocean water appears even dis-connected from the main ocean, which isn't what happens in real life. Furthermore, this would allow for 'seas' at different levels.

    ReplyDelete
    Replies
    1. It would take too long for an ocean. This method takes time proportionally to the size of lakes. I think oceans can be placed in an earlier phase. The ocean placement from this post is not very good, but it does not change the approach for rivers and lakes.

      Delete
  2. Very interesting idea using the A* search space to produce the lakes.

    ReplyDelete
  3. Man, you are awesome! I love your work for a long time now and I am waiting for every blog-post like a child is waiting for christmas. Can't wait to see some waterfalls :)

    ReplyDelete
  4. This approach is very, very dangerous in a voxel based world. You are using a creation method that is perfectly fine, but this is not what I'm worried about. Try to think about these questions:
    - Is there are source from which water flows (thing about waterfalls)
    - Is a water-voxel from a river different then that of a water-voxel (or do you not describe water as voxel-volumes?)
    - Is it possible to create a river from a single water-voxel?

    If you do not define water as voxels, strange effects may occur (filling a lake with mud, dig in the place where there used to be a lake). If you do want to use water-voxels, how are you going to describe flow from height differences?

    Think about some of the silly things you can do with water in minecraft. Now think about about your voxel based models where gaps may occure even if the voxels say there is no gap (because of smoothing of voxels).

    Will you address these problems in a way that will result in better water physics compared to minecraft? For example: will it become possible to fool the world in thinking that some water should flow upwards?

    Note that I'm just saying that it's 'dangerous' and offer no good alternative (as I don't have one). I'm just wondering if you have some ideas on this subject.

    ReplyDelete
  5. Excellent results, especially with the lakes at different elevations... and of course you are right, gotta have them waterfalls!

    I can say that this has exceeded my expectations for run-time procedural generation, and with the same flair you've shown over and over with the systems you continue to put into place.

    I feel the same as when I was first devouring the posts on city-states and towns... procedural generation can be made to produce amazing and realistic results, but it requires a critical eye combined with the analytical skills to define the real world algorithmicly, without bringing current technology to its knees... it is so FUN to watch it unfold here.

    Thanks for including us all in the ride! :)

    ReplyDelete
  6. I like it!
    I really want to see your next post. Do you fill the river's volume similar to lakes so that the river gets wider as forks join (that could produce islands in the middle of large rivers then! :)

    How do you render this and is it screenshot worthy yet?

    ReplyDelete
    Replies
    1. I think there are some islands on the last picture. : )

      Delete
  7. Am I correct in assuming that what you are describing here is the seeding of water in the environment and that it is but the first tiny step and there will, once a world is loaded, be real-time simulation of water flow?

    This simulation step you describe here appears to be quite shallow (No pun intended!) in terms of what water features it would create. What of underground lakes, interaction with temperature (frozen lakes), etc?

    ReplyDelete
  8. The only problem with this river generation algorithm is that these are all "young" rivers. They're freshly placed on the world and the route they follow is only the best in the present state of the world.

    Rivers need to "age" and, to some degree, create (erode) their own best route, or they won't look convincing.

    ReplyDelete
    Replies
    1. Imagine this river eroded a canyon. Then the river dries up for 100 years. Then it starts raining again. The new river will follow the same path as the old one. It is already the path of least resistance. If the terrain already has fluvial erosion baked into it, the new rivers will follow the course of the old rivers. It will be the old river.

      Delete
    2. Maybe mr. pdurdin just meant the same path of least resistance would look different if no river ever flowed on it or (for example) a small river flowed for 100 years or a large river flowed for 1000 years, so he's probably asking for simulating erosion before putting water in it.

      Delete
    3. I am simulating erosion before putting the water in it.

      Delete
    4. Are you placing the springs in places which make sense in terms of the erosion? Or is it just random?

      Delete
    5. What I showed here is random, just above a height value.

      Delete
    6. I forgot that you're already simulating erosion. :)

      Delete
  9. Here is a recent SIGGRAPH 2013 paper that I found very interesting and covers exactly what you're trying to do, might give some ideas.

    PDF (10MB) : http://hpcg.purdue.edu/pubs/2013/Genevaux2013sigg.pdf
    YouTube video : https://www.youtube.com/watch?v=JCsj0v-wmIM

    ReplyDelete
  10. Perhaps longer rivers, larger lakes and oceans could be placed onto a course-grained, planet-sized overlay, that can be superimposed onto the hightmap generation, before the placing of these water sources for smaller rivers and lakes.

    The same goes for icy poles, plains of grass, tundra, forrests, desserts, canyons, mountain ranges, and other dominant terrain features.

    Apart from solid matter and fluids, real-world terrain is also influenced by gasses, humidity and temperature(-fluctuations) which all interrelates and fluctuates per 'area'.

    Also, the core of a planet rotates, tectonic plates move, moons and other large bodies influence gravity, which causes oceanic waves, shifts in groundlayers, resulting in vulcanic eruptions and earthquakes, which on it's turn alters the landscape in various ways, like mudslides, deterioration and creation of mountains, etc. This causes changes in rivers, lakes and even the local flora and fauna. Also there's weather patterns, migrations of herds, fertilization of land, freezing and melting of poles, and so on, and so on - it's extremely complex system, which we humans probably won't ever fully understand.

    It's therefore near impossible to generate accurately, but you can approuch it with a representation of the real thing, like Outerra is doing. I wonder when procedural generation will incorporate enough factors to generate enough detail into something that might be mildly acceptable. (This reminds me a bit of your reference to the Pandora planet from the Avatar movie - we only got to see the good-looking parts. How would it come across once we got to explore the entire planet?)

    ReplyDelete
  11. I'm so glad to see you finally adding water. I've been waiting patiently for this since I started following your blog, and I must echo the previous comments about the clever way you've handled lake-filling.

    Does this a* trick you use give you a way to determine to what depth the lake fills? Can you specify deep lakes, shallow lakes? What happens if a lake overflows its geography and begins a new river?

    ReplyDelete
    Replies
    1. No, I do not get the water depth from the A*, only coverage. I will post later how I am coming up with it.

      Delete
  12. Is water going to be interactive, i.e. ripples? And if so, how much of the effect is going to be in geometry and how much in pixel shader?

    ReplyDelete
  13. Originally this was going to be a quick explanation of an idea but I felt like expanding on it. This is not necessarily a new idea but something I think might be a system for dynamically tracking quantities of water as they flow over the landscape.

    The idea is to split a given stream or lake into segments that each keep track of the volume of water they contain. Since the goal is not to simulate water at the voxel level, these segments should be as large as possible to still accommodate the purposes described below. The basic idea behind this system is that each segment knows the rate at which water should be moving in and out of it and adjusts the upstream and downstream segments accordingly. The rate of flow should be dynamic, as in based on not only the change in height but also on the volume of water upstream and downstream that may be putting pressure on it.
    For this system to work, the terrain generation would have to define places where water is created and where it is destroyed. A simple source is to have randomly placed springs. More complicated but also important is to have rainfall calculations. I imagine an iterative algorithm could be run to find where rainfall would initially collect in the landscape before significant enough to form a stream, and this algorithm would only need to be run once per generation or major modification of the terrain. The result would be a map of how much volume of water is added to each segment. The final step is for water to be deleted, which would require some sort of evaporation that removes volume based on surface area.
    The result, ideally, would be a system of streams that can dry up, flood, or change course when paths are dig by the user.

    ReplyDelete
    Replies
    1. Don't forget that water also disappears into the ground, and pops up in actual springs =P. (Speaking of springs, if the spring is also a cave, you can have some impressive and mildly scary locations, I've one in real life, basically you just follow this nice calm river upstream, then suddenly BWAM 50 meter deep hole under water with water flowing up from it (In crystal clear water) =P.)

      Delete
    2. I read a paper somewhere doing water simulation as "tall" voxels. It is very similar to the idea you have described. I will try to find it and post a link.

      Putting a spring in the origin of rivers should be no problem. This is where the red dots are in the second image from this post.

      Delete
    3. http://youtu.be/Jl54WZtm0QE?t=1m3s
      I don't know if this what you're referring to miguel - cell size this small I am expecting is beyond the reach of current processing power on real time world simulation, but it does demonstrate how 'tall' cells can be ignored with regard to simulation.

      Delete
    4. I played with water on heightmaps a while ago. What I did was a two step approach: First I seeded water on the surface, and followed the particles downhill until I found a point where the water no longer could flow down. Doing so, I kept track of flow strength over the map, and used the flow stength later to carve/erode where the rivers should flow.
      Then using these "sinkpoints", I started filling "ponds" until an outflow position was found, (or alternatively: pond surface exceeded a function of inflow strenght) (evaporation balance). Not very optimized approach, but one that kept track of the water. Please reply If you would like to know any more.

      Delete
  14. "Scrap Heap", that's exactly what I am talking about.
    Did it allow water to flow across the surface, meaning water that is higher than the point it would drain to?

    Since the discussion is finally going towards dynamic simulations of physics of various sorts in the voxel grid, I have a few questions that have been sticking in the back of my mind.

    Would it be possible to use a more general, less resource intensive approach for the land overall but use resource-intensive methods for rendering these voxel mechanics when right next to the player? This might be a problem, of course, if the player's position decides with what accuracy something is simulated with when the thing being simulated is 'real' in the sense that it is part of the voxel world and not just graphical tricks such as LOD.

    And finally. Could something be simulated once or twice with the accurate but expensive simulation (mainly I am talking about CA rules for fluid flow) and then have the engine analyze its overall behavior and then have it recreate that behavior without the individual simulations. This might make it possible for a user to create a system of pipes, that, in the end, only checks the inflow and outflow points and stops simulating the interior contents, until a voxel that is part of the pipes is changed.

    Of course the big problem here is the potential for a great deal of wonk in the physics if the 'faked' simulations do not perfectly match the real ones. It could be a bit of a problem if a user creates a contraption that works one way and then begins to work another way when the engine switches to the 'faked' simulations. Maybe correcting this is just a matter of the algorithm checking for all cases and being forced to resimulate as new cases come up.

    ReplyDelete
    Replies
    1. I started writing something on this a long time ago.
      Not very readable, but something you can look into:
      http://purple.worldforge.org/~munin/Procedural_World/waterflow.txt
      In the following movie, I was testing the pondfilling algorithm. The contours denote the heightmap, the colored blocks denote different Pond ID ( sinkpoints:
      http://purple.worldforge.org/~munin/Procedural_World/Mercator/pondfill5.avi

      Anyway, I am sure that this site will demonstrate a much more elegant solution very soon.

      Delete
  15. I only just noticed: What are the black bits?

    ReplyDelete
  16. Nice simple approach with nice results :), helpfull explanation.

    ReplyDelete
  17. I've come to this project late and frankly, I am utterly amazed at what you are achieving. I really can't wait for this to be released in some form. Just the ability to wander around these landscapes would be fantastic. Driving, flying, skiing, sailing, swimming, scuba diving etc would be even better :)

    I don't know if you are going for some kind of kickstarter funding, but I'd be in like a shot if you were; or have I missed the boat?

    ReplyDelete
  18. Hello,
    I was wondering if the Voxel Farm engine (its terrain generator) is flexible enough to create the Moon, Mars, or any random planet in it?
    If this was possible we could have a colonization game in which you go to other planets and terraform them. You could see how the planet changes when contents of the atmosphere change, how oceans rise and how the plants you brought with you mutate and adapt to the environment. There would have to be some kind od deamon process going around the planet all the time and introducing erosion effects, making plants grow, spread and die etc.
    It might be difficult to do, but it would be neat and every game would be different.

    ReplyDelete
    Replies
    1. Once again, the current terrain is flat and using it to represent a planet's surface would be a bit of a challenge, although there are a few ways to deal with it. While a full voxel representation of the planet might seem the simplest, I'l bet a bunch of algorithms that go into this engine depend on down in gravity being down in the voxels. Maybe planets can be accomplished by having small geodesically tiled sections of terrain.

      Delete
  19. Just re-read the post and I'm marveling that water is in progress... it's been such an holy grail for the engine, and to know that Miguel is working on it is so heartening.

    One minor thing I noticed was that many of the rivers in the screen shots had significantly large segments that appear very straight, and almost take 90 deg. turns to other straight segments... I'm sure you already noticed this and it's probably just a byproduct of the search algorithm, but I thought I'd mention that those would look pretty out of place.

    Still amazing, and I'm sure we're getting close to the Water-Part 2 post so I'll be quiet now and let you get back to work! ;)

    ReplyDelete
    Replies
    1. They don't look that out of place to me. Have a look at the rivers in this area of Tasmania which is a nice bit of wild, empty terrain with rivers and mountains:
      http://goo.gl/maps/YtR4X

      Delete
    2. @pdurden, I think you misunderstood me, I meant there are vast areas.of Miguel's rivers that are literally straight, and I should have mentioned they flow predominantly east west north south, straight lines.. here's a section (https://db.tt/RyunaEnF).

      I think it's a byproduct of the * search, unless it's due to the map resolution or heightmap, used to generate them, a little meandering would help... Many other areas of rivers look great in the sample image.

      Best to all!

      P.S. I know what I'm dreaming about... that I want to "be thankful" for... A demo? *wink* I can dream can't I :)

      Delete
  20. You may need a drain voxel to prevent flooding of structures and to remove water at boundaries of Everquest Landmark properties, etc. If water and lava flows it creates griefing problems. I've seen that in Minecraft and Terraria and in one other voxel demo. A drain block would destroy water above it at a size related rate.
    If the water is voxel based thats easy. If it flows by volume and mass it then drains harmlessly. Scatter a few drains around an your builds to safeguard against such griefing and a hydraulic cut paste disaster. There are plenty of free drain textures but it should be a state that can apply to many types of materials. Gravel, cobbles, cracked stone, marsh, wood and metal grill would all work in fantacy. Grates are a dime a dozen in modern and science fiction texture packs.
    A drain may also have application eventually in under water content creation.

    ReplyDelete