I know you were burning with desire to know this, actually probably (if I'm able to re-enable comments without being spammed into oblivion, er, please don't sue me bethesda) I will get a lot of comments telling me that I don't know what a vector field is or that I'm slightly wrong. Whatever!

Take a piece of graph paper. On each square, draw a tiny arrow. It can point in any direction at all. Some arrows can be longer than others, these are "stronger".

@p You can do some fun things with vector fields, it's actually a simple concept. You could put a little bubble into it and use those arrows to apply forces to the ball, depending where it is. You could turn those arrows around randomly a bit and create some kind of turbulence (Major Tom does not do this though and I like somebody's explanation that the bad steering was not due to unseen atmospheric effects, but Space Gin.)

This is a cute example of a vector field. Remember this level in Cave Story?

Screenshot borrowed er stolen from Prof's Let's Play Cave Story.

@p VECTOR FIELD! Each tile has a water flow direction and they push you around.

Those little arrows in the vector field don't have to represent forces, though. They could represent something... else.

@p Lately you must have been thinking, "How can I use vector fields to make rivers in a terrain algorithm?" I know I sure am. I've been thinking about it every day for like 3 days or more, maybe has it even been a week?

"Oh, Richard Gere, I'm so thirsty after you rescued me!" "Here, Gwendolyn, drink the water that has accumulated on this leaf!" "You are so rugged to think of drinking water from a leaf! Let's have an awkward near-kissing moment" "Ooh that's good, but Sean Connery won't like..." YOUTUBE LINK. Consider yourself warned.

@p We think of rivers as lines of water that flow. But are they? What's a river, really? I think it's something far more elusive.

@p A raindrop falls on a leaf, but is this part of the river?

@p It joins another raindrop, and they run down in a nearly-straight line-- is it now?

@p It lands on the ground, where it mixes with soil and pushes some other water out further down hill, which forms a tiny dribble of water running over rocks. That moves along, joining another dribble, and so on, until it's a creek, and finally the mighty Elbow River that runs through my city, claiming hundreds of cattle each year (not really, but... people do lazily float on it in dinghys.)

@p I have forded the Elbow in places, which by the way is a fun hobby (fording rivers.) Leave your shoes on and point your bike up river, if you aren't going to carry it over your head.

Well it's more complex than that. But my idea is to model rivers as a vector field representing water flow. An arrow's magnitude represents the amount of water flowing, scaled in some way. An arrow's direction represents the direction of flow.

@p We iterate the algorithm over terrain like this:

@p For a randomly chosen terrain point P:

• Calculate P.downhill_normal, which is the direction traveling "downhill" (you can get this with projections and the gravity normal, Z = 1)
• Calculate a random vector cur_noise_normal, just randomly calculated in some fairly-uniform way.
• Now the fancy part:
  • For each neighbour point of NB of P, look at it's water flow vector NB.water_v and position NB.position
  • Compute cur_pointing as the normalized vector P.position - NB.position, i.e., the normal vector pointing from the neighbour point NB to the point we are looking at, P
  • Compute cur_dot, the dot product of NB.water_v and cur_pointing (if cur_dot is less than 0, set it to 0). This is a (magnitudinal) measure of how much the neighbour point NB's water vector "flows into" the point P. More powerful flow will result in a larger number here, which is what we want. A raindrop flowing directly into P will have a small effect even though it points at it directly. An obliquely traveling powerful flow will affect it greatly.
  • Now that we have everything we need, compute: P.water_v <- (P.water_v * CONSERVE_FACTOR + NB.water_v * cur_dot * FLOW_FACTOR + P.downhill_normal * DOWNHILL_FACTOR + cur_noise_normal * NOISE_FACTOR) * FRICTION_FACTOR
  • CONSERVE, FLOW, DOWNHILL and NOISE factors are balancing factors that determine how quickly the associated effects are allowed to propogate. FRICTION_FACTOR should be between 0..1 (but somewhat close to 1) and it is used to drain energy from the system, to prevent too much water accumulating too quickly.
• Based on the water volume, affect P.altitude accordingly; on the terrain height map, this is how high the point P is; we want to make it degrade (erode) as more water flows over it. This will create a feedback cycle, via the therefore-changing P.downhill_normal. I.e., as we erode the ground, it will affect which direction is downhill, which should cause the water to channel.
• Repeat this procedure for many points P. See what happens!

Eventually, we want to convert this into rivers. Not hard!! We just determine where there is water flow stronger than a certian limit, by comparing each |P.water_v| (the length or magnitude of the water flow) we can determine if the water flow at that point is strong enough that there would be visible water overtop of the terrain.

@p If there is, again we have to specify water depth. The water depth at each point should be a factor of |P.water_v|. We can use the actual direction of flow to create various effects! After all, it's a simple vector field-- step into, it could apply a force, or even just generate a frothy animation on the upstream of the object immersed, or we could put little chevrons to show the direction of flow, etc. etc.

• First, I'll do another blog post to let you know how it turns out. We are doing experiments here folks I don't pretend to know if it will work in advance.
• Notably, we do not differentiate the speed vs. the magnitude of water flow. This would make a better model but I haven't worked out how that could work. Somebody probably has!!!!!! Check arxiv, ha ha that's just a little joke never mind. Honestly though this idea has probably already been worked out by someone.
• NOW: Very important. We are NOT simulating water flow as a dynamic process. Not really. And that's the point. We are relaxing (in the Comp Sci sense) a vector field according to certian rules that seem like they might model river generation. Hopefully it results in a stable configuration, given the right balancing factors.
• We might (should) have a "sea level" which we might choose in advance. Terrain that flows below this could have it's water_v multiplied by another factor, which would be very small, so that water flow would dissapate very quickly once hitting sea level.
• Will this form pools of water? That's an interesting question.

2011-09-04

◀ Back