Given:
- A 2D array representing the water heightfield, named "watermap".
- A rate of flow, named "water_rate".
- An amount that a column of water "wants" to pass to neighbours, called
"contribution", which is scaled by the amount of time since the last update.
Note: Edge conditions are checked; "invalid" cells (at this point, cells that
would be outside of the grid) are simply ignored. Thus, in the case of the
current cell being on the north edge, its north neighbour is ignored.
Algorithm:
- Construct a 2D array with the same dimensions as watermap, called watermap_temp;
initialise each entry to 0.0. This map stores the change in height for the water map.
- For i = 0 to x-size:
- For j = 0 to z-size:
- "current_val" is the value in watermap[j]
- For each direct neighbour (north, south, east, west), calculate the difference
in height between that neighbour and current_val.
- Make a note of any that are negative.
- If any differences are negative:
- Add 1.0 to each non-negative value.
- Set each negative value to 0.0
(Note: The above originally set the negative values to 2^value, producing a value above zero but
below one. Incrementing the non-negative values by one ensured that they were greater
than the previously-negative values.)
- Calculate the sum of all differences.
- If "contribution" is greater than current_val, set it to current_val.
- For each valid neighbour, add:
contribution*(difference in that direction / total difference) -
i.e., parcel out the contribution proportionally to the relative sizes
of each difference in height.
- Subtract the contribution from watermap_temp.
- End of j-loop.
- End of i-loop.
Finally, for each element of watermap, add the corresponding element of watermap_temp.
Water heightfield calculations
I am currently working on a "2.5D" water simulation for a game that I'm developing, and the propagation of water from column to column is giving me a lot of trouble.
In my searches I came upon YannL's lecture, and, based on it, I will probably edit my method to include the "virtual pipes" that he describes.
However, I still don't know where the problem lies in my own approach. This bothers me, especially, I suppose, since my approach would seem to be simpler, and is thus more attractive. I would appreciate it if someone were to point out the presumed flaw in my logic.
The basic idea has each column of water "trying" to fall by a certain amount per unit time. The water that would be displaced by this fall is passed to its immediate neighbours (i.e. north-, south-, east- and west- neighbours), with the portion of the contribution given to any given neighbour being proportional to the difference in height between the current cell and the neighbour in question.
My algorithm, in pseudocode, is roughly as follows:
Dwarf Fortress does a similar sort of water simulation - you might want to read the end of this interview with its creator:
http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?print=1
http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?print=1
Thank you very much for your quick responses. ^_^
Ooh, that looks very useful indeed - thank you very much. ^_^
Urk, right you are! Sorry. ^^;
I'm seeing a lot of high-speed vibration and directional artefacts. The water does overall flow outwards from a high point, but seems to do so more slowly than it should.
Oddly, as I recall, if I have the results write into the original height array, the water flows wonderfully, even rippling nicely - but favouring the direction of 0,0 in the array (in fact flowing almost entirely into the quadrant that holds 0,0 in one of its corners.
[edit]
Screenshots:
Note the odd shape, diagonal troughs (these are quite deep, it seems), and oblong artefacts.
[/edit]
Hmm... True, and that may explain some of what I'm seeing. I'm not sure of how to introduce a damping term into my system, however. That is probably something that I should have thought about further - thank you. ^_^
Perhaps I should use difference_in_height*damping_factor, where 0.0 < damping_factor < 1.0? [further edit] No, that doesn't seem to help - I feel rather silly for having so much trouble with this. >_< [/further edit]
[edit] Screenshots added. [/edit]
Quote:Originally posted by swiftcoder
Dwarf Fortress does a similar sort of water simulation - you might want to read the end of this interview with its creator:
http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?print=1
Ooh, that looks very useful indeed - thank you very much. ^_^
Quote:Originally posted by Vorpy
You never said what the problem is that you're seeing with your algorithm.
Urk, right you are! Sorry. ^^;
I'm seeing a lot of high-speed vibration and directional artefacts. The water does overall flow outwards from a high point, but seems to do so more slowly than it should.
Oddly, as I recall, if I have the results write into the original height array, the water flows wonderfully, even rippling nicely - but favouring the direction of 0,0 in the array (in fact flowing almost entirely into the quadrant that holds 0,0 in one of its corners.
[edit]
Screenshots:
Note the odd shape, diagonal troughs (these are quite deep, it seems), and oblong artefacts.
[/edit]
Quote:Originally posted by Vorpy
Also the way you describe your algorithm it sounds like if the map were just two columns of water next to each other it would be possible for them to oscillate forever instead of settling down since the amount of water passed from one neighbor to another isn't limited to merely equalizing the water levels.
Hmm... True, and that may explain some of what I'm seeing. I'm not sure of how to introduce a damping term into my system, however. That is probably something that I should have thought about further - thank you. ^_^
Perhaps I should use difference_in_height*damping_factor, where 0.0 < damping_factor < 1.0? [further edit] No, that doesn't seem to help - I feel rather silly for having so much trouble with this. >_< [/further edit]
[edit] Screenshots added. [/edit]
Heh, I edited out that second part of my reply because I realized it might not actually be unintended. Rippling water does go up and down in a wave type of motion, instead of always leveling out right away.
Of course to simulate this accurately would require some fluid dynamics type simulations. I think rippling water effects often just use a sort of grid of springs, which doesn't conserve fluid volume but is an easy way to get the ripple effect with minimal processing. In that effect, each cell is like a spring constrained to movement along only the y axis, and each cell is also coupled to adjacent cells, exerting a force on them proportional to the difference between them. Getting rippling with actual volume conserving fluid mechanics would be a lot more costly.
For actual fluid simulation, you could look into Jos Stam's papers. This particular thing you're doing with the water looks like diffusion, and there are other ways of representing the problem that might give better results.
Of course to simulate this accurately would require some fluid dynamics type simulations. I think rippling water effects often just use a sort of grid of springs, which doesn't conserve fluid volume but is an easy way to get the ripple effect with minimal processing. In that effect, each cell is like a spring constrained to movement along only the y axis, and each cell is also coupled to adjacent cells, exerting a force on them proportional to the difference between them. Getting rippling with actual volume conserving fluid mechanics would be a lot more costly.
For actual fluid simulation, you could look into Jos Stam's papers. This particular thing you're doing with the water looks like diffusion, and there are other ways of representing the problem that might give better results.
Hmm... Thank you.
The spring mechanism sounds interesting, but it looks as though a simple fluid dynamics simulation is probably what's called for.
I'll look up Jos Stam - thank you again. I don't know what I'll find there, but at the least I have the system described by YannL in the lecture that I found, which looks promising.
The spring mechanism sounds interesting, but it looks as though a simple fluid dynamics simulation is probably what's called for.
I'll look up Jos Stam - thank you again. I don't know what I'll find there, but at the least I have the system described by YannL in the lecture that I found, which looks promising.
Quote:Original post by Vorpy
I think rippling water effects often just use a sort of grid of springs, which doesn't conserve fluid volume but is an easy way to get the ripple effect with minimal processing. In that effect, each cell is like a spring constrained to movement along only the y axis, and each cell is also coupled to adjacent cells, exerting a force on them proportional to the difference between them. Getting rippling with actual volume conserving fluid mechanics would be a lot more costly.
For actual fluid simulation, you could look into Jos Stam's papers. This particular thing you're doing with the water looks like diffusion, and there are other ways of representing the problem that might give better results.
I've used Jos Stams code for fluid simulations and must say it is very nice! I don't think it is suitable for rippling water surface effects, though, since it works inside a closed, predefined space. It is great for simulating dust-particles-in-moving-air and dye-in-fish-tank effects.
The spring solution sounds much better, and I think you can in fact implement volume preservation - or since this is 2d(?), area preservation. I've made some soft body "blob" sims with area preservation without much effort. Basically you find the water body's area (google for simple and fast polygon area algo) and apply a pressure normal to each spring. The pressure is defined with Hooke's law of elasticity:
pressure = constant * (area - rest area)
Here is a fairly straightforward article on pressurized soft bodys:
http://panoramix.ift.uni.wroc.pl/~maq/soft2d/howtosoftbody.pdf
I wouldn't mind helping you along - just ask!
Cheers & happy coding, Michael
Thank you very much, h4tt3n - I appreciate that. ^_^
Actually, simulating within a closed, pre-defined space is more or less what I want. Your spring-based system sounds interesting, however.
That said, I've had a shot at implementing the system from YannL's lecture (it's here, for those who might be interested - my apologies for not posting it earlier), and while I've had a few problems with it, it seems to work reasonably well. Unfortunately, I'm having a little trouble with the inclusion of terrain into the model (terrain, that is, that the water should flow over), although I think that I'm making some progress on that, and am encountering some instabilities under certain conditions, at least as I have it implemented.
If I do stick with this system, however, I'll very probably be wanting to make some optimisations... ^^;
Perhaps I should elaborate a little on my intended use for this water simulation:
I'm currently working on a little god-game project, involving a landscape constructed of a regular grid of tiles, which can be raised and lowered (as well as a small terrain heightfield on top of each, although that might go if I don't get water working properly). One of the features that I intend is that of the type of plants growing on and around a given tile being dependant on available water, and, as a visual feature, water flowing nicely over the landscape, falling down tile edges, and forming "rimfalls" where it meets the edges of the landscapes. In order to provide water to the system, the player would be allowed to place water sources.
I've considered a particle approach (using the particle positions to inform a heightmap, essentially, with positions that lack particles being defined to have a very low (possibly below zero) water height. Other than a system akin to the current system's pressure-based approach, I'm not sure of appropriate rules to govern them, I'm afraid, and am unsure of the potential performance cost. :/
Suggestions and advice would be welcome. ^_^
[edit] A few images:
Not too bad...
It doesn't seem to like being confined, however (or, for that matter, losing cpu time):
[Edited by - Thaumaturge on April 13, 2008 11:09:29 PM]
Actually, simulating within a closed, pre-defined space is more or less what I want. Your spring-based system sounds interesting, however.
That said, I've had a shot at implementing the system from YannL's lecture (it's here, for those who might be interested - my apologies for not posting it earlier), and while I've had a few problems with it, it seems to work reasonably well. Unfortunately, I'm having a little trouble with the inclusion of terrain into the model (terrain, that is, that the water should flow over), although I think that I'm making some progress on that, and am encountering some instabilities under certain conditions, at least as I have it implemented.
If I do stick with this system, however, I'll very probably be wanting to make some optimisations... ^^;
Perhaps I should elaborate a little on my intended use for this water simulation:
I'm currently working on a little god-game project, involving a landscape constructed of a regular grid of tiles, which can be raised and lowered (as well as a small terrain heightfield on top of each, although that might go if I don't get water working properly). One of the features that I intend is that of the type of plants growing on and around a given tile being dependant on available water, and, as a visual feature, water flowing nicely over the landscape, falling down tile edges, and forming "rimfalls" where it meets the edges of the landscapes. In order to provide water to the system, the player would be allowed to place water sources.
I've considered a particle approach (using the particle positions to inform a heightmap, essentially, with positions that lack particles being defined to have a very low (possibly below zero) water height. Other than a system akin to the current system's pressure-based approach, I'm not sure of appropriate rules to govern them, I'm afraid, and am unsure of the potential performance cost. :/
Suggestions and advice would be welcome. ^_^
[edit] A few images:
Not too bad...
It doesn't seem to like being confined, however (or, for that matter, losing cpu time):
[Edited by - Thaumaturge on April 13, 2008 11:09:29 PM]
Thaumaturge,
On second thought I don't think either the fluid sim or spring "sheet" method are as good as the one you already implemented. When you wrote 2.5D I thought you ment layered 2d graphics side-scroller-style.
As Vorpy said, I also think the trouble arising when you try to confine the liquid comes from the lack of friction or damping.
You could try to implement the damping used in springs, which is simply a force applied to the body beeing proportional to its speed and pointing in the opposite direction of its movement. Since this is basically a series of parallel 1d columns moving up and down (and since v = dx/dt) it should be simple:
column_vel = (last_height - this_height)/timestep
damping force = -column_vel*some_constant
From the link you posted I believe you could actually apply a vertical force to each water column, right? The damping would then be a simplified simulation of air friction and frictious eddie currents in the water.
cheers, Michael
On second thought I don't think either the fluid sim or spring "sheet" method are as good as the one you already implemented. When you wrote 2.5D I thought you ment layered 2d graphics side-scroller-style.
As Vorpy said, I also think the trouble arising when you try to confine the liquid comes from the lack of friction or damping.
You could try to implement the damping used in springs, which is simply a force applied to the body beeing proportional to its speed and pointing in the opposite direction of its movement. Since this is basically a series of parallel 1d columns moving up and down (and since v = dx/dt) it should be simple:
column_vel = (last_height - this_height)/timestep
damping force = -column_vel*some_constant
From the link you posted I believe you could actually apply a vertical force to each water column, right? The damping would then be a simplified simulation of air friction and frictious eddie currents in the water.
cheers, Michael
Quote:Originally posted by h4tt3n
When you wrote 2.5D I thought you ment layered 2d graphics side-scroller-style.
Aah, fair enough. No, this is "2.5D" because it only produces a surface, and doesn't work with fully-3D data, as opposed to a fully-3D volumetric approach (such as a voxel grid).
Quote:Originally posted by h4tt3n
As Vorpy said, I also think the trouble arising when you try to confine the liquid comes from the lack of friction or damping.
Possibly... I have tried to find a way to dampen ripples more quickly, but have yet to find a way to do so.
Your force application idea sounds good - it's simple enough to implement, since such forces are simply added to a given column's pressure.
There is, note, a damping factor applied within the "virtual pipes" that join columns.
The flow through a given pipe is calculated thusly:
flow_through_pipe += -dt*pipe_cross_section*height_diff*gravity/(pipe_length*column_area)*damping
[edit]
However, ironically, if I recall correctly reducing the value of "damping" (to dampen things further) resulted in increased instability. :/
Correction: A lower "damping" factor seems as though it might be a little more stable, but produces slower wave propagation and, for some reason, more pronounced diagonal artefacts.
[/edit]
Hmm... Given the way that it blows up when the timestep becomes too large, I wonder whether I shouldn't fix the timestep for the water - although I fear that doing so might result in propagation of slowdown from multiple iterations of water processing causing further delays between updates...
[edit2]
On further reflection, perhaps a simpler system would be better for my purposes. Something along the lines of examining terrain heights and propagating only to those that are on the same level or below...
It would be less accurate, but might serve my purposes. Some semblance of surface movement could be provided by a noise function.
While this would probably look horrible in the sorts of circumstances that YannL's system works well, it would probably be far more stable in the systems that I intend, at least as compared to my current implementation.
[Edited by - Thaumaturge on April 14, 2008 1:57:51 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement