Sign in to follow this  
coderWalker

~~Managing Voxel Water~~ (now with vids and source)

Recommended Posts

coderWalker    127
Hello, I'm working on a Textured Voxel engine (C++ OpenGL) with game-play similar to [url="http://chir.ag/stuff/sand/"]http://chir.ag/stuff/sand/[/url] but in 3d.
Basically a Particle (Voxel) reaction sandbox.

I'm not really having trouble at code as much as figuring out how it should work.

EDIT: Problem has changed check post #11.

[b]<Old Method>[/b]
Before each water block had it's own amount. Then it just checked if the adjacent block had less, if so then it gave it 1/5 of it's water.

[b]<New Method>[/b]
Now I am recoding the water part of the engine so that the water stays level, to make it more smooth and better looking.

My game is structured as follows:
[img]http://webstrand.comoj.com/pics/visual.png[/img]
The World is made of multuple chunks.
Each chunk having a 16x16x16 array of blocks.
Each chunk now has multiple LiquidBodys or lists of water.
Each liquidBody has one Water level so all blocks share this (average amount of all blocks in list to stay proportional)

Here is a Visual of my current problem:
[img]http://webstrand.comoj.com/pics/visual2.png[/img]

The problem is, sometimes the player can create a liquid body in one chunk and then have it connected to a liquid body in another.
Since the liquid bodys are contained in the chunks I cant just add another chunks blocks to the others list.
All that they have to share really are the WaterLevels.
I was thinking linking thier waterLevels somehow. However this will not work with more than 2 chunks, because as seen on the right
side of the map the linking would form a circle, this may be even worse with trees.

I guess this is one of those cases where you have to come up with an out of the box solution.

Does anyone have any ideas?

Share this post


Link to post
Share on other sites
smasherprog    568
What is the problem exactly? Why are you not able to allow this? What harm does it cause if players do this?
Why cant you store the water exactly as you store the ground? Do you have a problem when the ground between the grids connects? If not, then why would water cause a problem?

Share this post


Link to post
Share on other sites
coderWalker    127
The water is added to the list so that when the waterLevel changes all the blocks are updated very quickly, because they must keep the same waterLevel.
The LiquidBody's are allocated by the Chunks. So the problem is getting one chunk's Liquid Body to update ones that are touching in other chunks.

Share this post


Link to post
Share on other sites
owl    376
if you can detect when multiple liquid bodies get connected just average their levels an apply that value to all of them.

Share this post


Link to post
Share on other sites
smasherprog    568
Treat water just like land. If you want to make sure the surrounding water has the same level, then when ever a water block is created, do a check of the surrounding blocks to make sure they are the same level as the one being inserted. Then continue these checks until all the water is the same level. This will require a couple of extra checks, but how often are people going to insert water? There shouldn't be a problem with a few hundred extra iterations of a loop that is going to be called once every minute.

If this function is going to be called every game loop, then you can be concerned about it, but for insertions such as this, optimization should be last on the list of things to do because it doesn't matter how much you optimize it, there will be absolutely no noticeable difference in speed.

Share this post


Link to post
Share on other sites
coderWalker    127
[quote]
If this function is going to be called every game loop, then you can be concerned about it, but for insertions such as this, optimization should be last on the list of things to do because it doesn't matter how much you optimize it, there will be absolutely no noticeable difference in speed.
[/quote]

I have the water working as you mention right now, I'm trying to get away from that.
It does get very slow once you have alot moving,
Also causes major problems when they place 2x2 water blocks and 3 have 5/5 water and the other 3 4/5.
The problem is the time it takes to update per step increases exponentially.

This is really hard to explain, I have the game online so anyone can try it out, it's here:
[url="http://webstrand.comoj.com/betatesting.php"][img]http://webstrand.comoj.com/webStrandText2.png[/img][/url]

Registering for a beta account is required though, the invite code is "bl0ck" without quotes ofcourse.

The best way to see this is to create a path of water from the ocean threw the land. You can place lava to turn the water to steam at the end of the path, so it will keep requiring updates.
"E" access the inventory menu,

Share this post


Link to post
Share on other sites
coderWalker    127
[quote name='owl' timestamp='1307980648' post='4822811']
How are you calculating the water level?
[/quote]

[code]
//Init
waterLevel=0.0f;
//New block added
//amount = amount of new block
waterLevel = ((waterLevel*(list.size()-1))+amount)/list.size();

//same as waterlevel = amount/Blocks
[/code]

Share this post


Link to post
Share on other sites
owl    376
I really fail to understand your problem. When you connect two or more liquid bodies you just add up more level to those who has less and remove from those who have more. If your problem is iterating your blocks at the time of adding/removing large amounts make that operation a task that runs over various iterations.

Share this post


Link to post
Share on other sites
coderWalker    127
I'm just getting really confused and have no idea where to go.
I'm going to start this over.

I originally had each block having it's own amount of water from 1-5. However this just gets so slow over time it's not acceptable.
The only way to have variable water was to have diffrent blockID's aka water1 water2 etc.
If I stored the floats for each that would be disastrous.
4bytes*16^3*25^3 = 256MB ram extra required!

chunk = 16x16x16 blocks
map = 25x25x25 chunks


The way I think would be most efficient to manage water is to keep a list of water that is touching.
This list should have one water-level.
So when water is added I can just loop threw the list and increase all at one. Also the water level would drop when spreading.
Basically the blocks will be set to water however the draw routine for the list will draw them at the correct height.

Are the lists a bad idea?

Whats suggested?

Also my map works as so:
The map has an array of 25x25x25 pointers to chunks.
Each chunk has 16x16x16 blocks.
The chunks are unallocated and allocated as they are visible.

Share this post


Link to post
Share on other sites
smasherprog    568
How do you plan on storing the water level then? If each block does not contain its water height, then it must be stored somewhere else right? Say for each body of water, there is a single float with the height of it. Well, How then do the water chunks know they belong to the body of water? Or should the body of water know about each individual chunk? In any case, you will have to store a pointer to each water block in a body of water, or each water block will have to store its own height. On 64 bit systems, that pointer will be 64 bit, where a float is 32 bits.

You are also going to run into problems if some evil doer --like me-- gets into your game and tries to crash the servers by connecting two large bodies of water together. So, you cannot .. CANNOT let two large bodies of water be joined in a way that causes a problem. If there are two bodies of water with a million water blocks in each and they are merged, you will have some serious issues. So, perhaps you should rethink how bodies of water affect each other when they are connected.

Share this post


Link to post
Share on other sites
coderWalker    127
Is it possible I could just link them somehow?

Add a pointer in the 4 directions to each liquid list?

Then I could just link 2 bodies of 500,000 blocks instead of joining them.

[b]Overall[/b]
How should I link bodies of water and how would I calculate the waterLevel?

Share this post


Link to post
Share on other sites
owl    376
Are you taking the time of reading what people is telling to you? Or you just wanna waste everyones time?

Share this post


Link to post
Share on other sites
coderWalker    127
I am reading everything I just haven't been quoting as much as I usually do, my apologies.
I think I am having as hard of a time understanding the answers as you all are the question.

Maby I should explain more.

[b]Old Water:
[media]http://www.youtube.com/watch?v=Jjd_0Pwl_nc[/media]

New Water:
[media]http://www.youtube.com/watch?v=0SEokIIi73w[/media]
[/b]
I guess some code snipplets would help.

[b]Chunk.cpp (partial)
[code]liquid* chunk::getLiquidBody(iVertex3d block)
{
return liquidBodys[data[block.x][block.y][block.z]];
}
liquid* chunk::createLiquidBody(iVertex3d target, float amount)
{
//Create a new Liquid Body

//Look for NULL or create new
bool found = false;
liquid* newLiquid;
short length = liquidBodys.size();
for ( short pos=0; pos<length; pos++)
{
if (liquidBodys[pos] == NULL)
{
found = true;
newLiquid = new liquid(this,pos);
liquidBodys[pos] = newLiquid;
pos = length;
}
}
if (found == false)
{
newLiquid = new liquid(this,liquidBodys.size());
liquidBodys.push_back(newLiquid);
}
//Add block to Liquid Body
newLiquid->blockAdd(target,amount);
newLiquid->stepNext();
render();
return newLiquid;
}
void chunk::liquidAdd(iVertex3d target, float amount, iVertex3d arrayPos)
{
/*world0->setTarget(target.x-1,target.y,target.z,arrayPos);
if (world0->getBlock() == water)
liquid* targetLiquid = world0->getLiquidBody();
targetLiquid->linkAdd(*/

//Add to an existing Liquid Body
if (target.x>0)
{
if (position[target.x-1][target.y][target.z] == water)
{
liquidBodys[data[target.x-1][target.y][target.z]]->blockAdd(target,amount);
liquidBodys[data[target.x-1][target.y][target.z]]->stepNext();
return;
}
}
if (target.x<15)
{
if (position[target.x+1][target.y][target.z] == water)
{
liquidBodys[data[target.x+1][target.y][target.z]]->blockAdd(target,amount);
liquidBodys[data[target.x+1][target.y][target.z]]->stepNext();
return;
}
}
if (target.y>0)
{
if (position[target.x][target.y-1][target.z] == water)
{
liquidBodys[data[target.x][target.y-1][target.z]]->blockAdd(target,amount);
liquidBodys[data[target.x][target.y-1][target.z]]->stepNext();
return;
}
}
if (target.y<15)
{
if (position[target.x][target.y+1][target.z] == water)
{
liquidBodys[data[target.x][target.y+1][target.z]]->blockAdd(target,amount);
liquidBodys[data[target.x][target.y+1][target.z]]->stepNext();
return;
}
}
createLiquidBody(target,amount);
return;
}[/code]

Liquid.h
[code]class liquid //This will manage a source of water on the same Z level
{
public:
liquid(chunk* Chunk,char Number);
void step();
void linkAdd(liquid* otherLiquid);
void stepNext();
void blockAdd(iVertex3d target, float amount);
void blockAdd(int x, int y, int z);
void move(int otherNumber);
void render();
void destroy();
bool spreadCheck();
char number;
float waterLevel;
//Linking
void serverSet(liquid* otherLiquid);
void clientAdd(liquid* otherLiquid);
void updateClients();
bool linkExists(liquid* otherLiquid);
deque<iVertex3d> list;
liquid* master;

private:
bool blockInList(int x, int y, int z);
deque<liquid*> link;
chunk* parent;
};
[/code]

Liquid.cpp
[code]#include "Global.h"
//All up to standards

liquid::liquid(chunk* Chunk,char Number)
{
list.clear();
waterLevel=0.0f;
parent = Chunk;
number = Number;
link.clear();
master = NULL;
}
void liquid::serverSet(liquid* otherLiquid)
{
master = otherLiquid;
}
void liquid::clientAdd(liquid* otherLiquid)
{
link.push_back(otherLiquid);
}
void liquid::updateClients()
{
short length = link.size();
if (length == 0)
{
return;
}
/*
parent->liquidBodys[otherNumber]->waterLevel =
((waterLevel*list.size())+(parent->liquidBodys[otherNumber]->waterLevel*
parent->liquidBodys[otherNumber]->list.size()))/(list.size()+
parent->liquidBodys[otherNumber]->list.size());
*/

float totalWater = 0.0f;
int totalBlocks = 0;
//Calculate Massive water level
for (short pos=0; pos<length; pos++)
{
totalBlocks += link[pos]->list.size();
totalWater += link[pos]->waterLevel*link[pos]->list.size();
}
totalBlocks += list.size();
totalWater += waterLevel*list.size();

waterLevel = totalWater/totalBlocks;
parent->render();
//Set waterLevel of all connected
for (short pos=0; pos<length; pos++)
{
link[pos]->waterLevel = waterLevel;
link[pos]->parent->render();
}
}
/*
void liquid::linkAdd(liquid* otherLiquid)
{
link.push_back(otherLiquid);
}*/
bool liquid::linkExists(liquid* otherLiquid)
{
short length = link.size();
for (short pos=0; pos<length; pos++)
{
if (link[pos] == otherLiquid)
{
return true;
}
}
if (master == otherLiquid)
{
return true;
}
return false;
}
void liquid::blockAdd(iVertex3d target, float amount)
{
list.push_back(target);
//Calculate water level
parent->data[target.x][target.y][target.z] = number;
waterLevel = ((waterLevel*(list.size()-1))+amount)/list.size();
}
void liquid::blockAdd(int x, int y, int z)
{
iVertex3d target = {x,y,z};
list.push_back(target);
parent->position[x][y][z] = water;
parent->data[x][y][z] = number;
//Calculate water level
waterLevel = (waterLevel*(list.size()-1))/list.size();
}
bool liquid::blockInList(int x, int y, int z)
{
iVertex3d target = {x,y,z};
short length = list.size();
for (int pos=0; pos<length; pos++)
{
if (list[pos].x == target.x && list[pos].y == target.y && list[pos].z == target.z)
{
return true;
}
}
return false;
}
void liquid::stepNext()
{
parent->liquidBufferAdd(list[0].x,list[0].y,list[0].z);
}
void liquid::step()
{
if (waterLevel<0.10f)
{
destroy();
delete this;
}
if (spreadCheck())
{
parent->liquidBufferAdd(list[0].x,list[0].y,list[0].z);
//Update if a Client
if (master!=NULL)
{
master->updateClients();
}
//Update Clients
updateClients();
}
}
void liquid::move(int otherNumber)
{
//Calculate new waterLevel
parent->liquidBodys[otherNumber]->waterLevel = ((waterLevel*list.size())+(parent->liquidBodys[otherNumber]->waterLevel*parent->liquidBodys[otherNumber]->list.size()))/(list.size()+parent->liquidBodys[otherNumber]->list.size());
//Set block pointers
short length = list.size();
for (int pos=0; pos<length; pos++)
{
parent->data[list[pos].x][list[pos].y][list[pos].z] = otherNumber;
parent->liquidBodys[otherNumber]->list.push_back(list[pos]);
}
parent->liquidBodys[number] = NULL;
delete this;
}

bool liquid::spreadCheck()
{
//Check for expanding
bool reStep = false;
short length = list.size();
for (int pos=0; pos<length; pos++)
{
//Right
if (list[pos].x<15)
{
switch (parent->position[list[pos].x+1][list[pos].y][list[pos].z])
{
case air:
blockAdd(list[pos].x+1,list[pos].y,list[pos].z);
reStep = true;
break;
case water:
if (blockInList(list[pos].x+1,list[pos].y,list[pos].z)== false)
{
parent->liquidBodys[parent->data[list[pos].x+1][list[pos].y][list[pos].z]]->move(number);
reStep = true;
}
break;
}
}
else
{
world0->setTarget(list[pos].x+1,list[pos].y,list[pos].z,parent->arrayPos);
liquid* otherLiquid;
switch (world0->getBlock() )
{
case air:
iVertex3d target;
target = list[pos];
list[pos].x=0;
otherLiquid = world0->Chunk[parent->arrayPos.x+1][parent->arrayPos.y][parent->arrayPos.z]->createLiquidBody(list[pos],waterLevel);
otherLiquid->serverSet(this);
clientAdd(otherLiquid);
reStep = true;
break;
case water:
otherLiquid = world0->getLiquidBody();
if (otherLiquid->linkExists(this)== false)
{
//Create the connection!
otherLiquid->serverSet(this);
clientAdd(otherLiquid);
//Level that water!
updateClients();

reStep = true;
}
break;
}
}
//Left
if (list[pos].x>0)
{
switch (parent->position[list[pos].x-1][list[pos].y][list[pos].z])
{
case air:
blockAdd(list[pos].x-1,list[pos].y,list[pos].z);
reStep = true;
break;
case water:
if (blockInList(list[pos].x-1,list[pos].y,list[pos].z)== false)
{
parent->liquidBodys[parent->data[list[pos].x-1][list[pos].y][list[pos].z]]->move(number);
reStep = true;
}
break;
}
}
else
{
world0->setTarget(list[pos].x-1,list[pos].y,list[pos].z,parent->arrayPos);
liquid* otherLiquid;
switch (world0->getBlock() )
{
case air:
iVertex3d target;
target = list[pos];
list[pos].x=16;
otherLiquid = world0->createLiquidBody(waterLevel);
otherLiquid->serverSet(this);
clientAdd(otherLiquid);
reStep = true;
break;
case water:
otherLiquid = world0->getLiquidBody();
if (otherLiquid->linkExists(this)== false)
{
otherLiquid->serverSet(this);
clientAdd(otherLiquid);
//Level that water!
updateClients();

reStep = true;
}
break;
}
}
/*
//Up
if (list[pos].y<15)
{
switch (parent->position[list[pos].x][list[pos].y+1][list[pos].z])
{
case air:
blockAdd(list[pos].x,list[pos].y+1,list[pos].z);
reStep = true;
break;
case water:
if (blockInList(list[pos].x,list[pos].y+1,list[pos].z)== false)
{
parent->liquidBodys[parent->data[list[pos].x][list[pos].y+1][list[pos].z]]->move(number);
reStep = true;
}
break;
}
}
//Down
if (list[pos].y>0)
{
switch (parent->position[list[pos].x][list[pos].y-1][list[pos].z])
{
case air:
blockAdd(list[pos].x,list[pos].y-1,list[pos].z);
reStep = true;
break;
case water:
if (blockInList(list[pos].x,list[pos].y-1,list[pos].z)== false)
{
parent->liquidBodys[parent->data[list[pos].x][list[pos].y-1][list[pos].z]]->move(number);
reStep = true;
}
break;
}
}*/
}
return reStep;
}
void liquid::destroy()
{
short length = list.size();
for (short pos=0; pos<length; pos++)
{
parent->position[list[pos].x][list[pos].y][list[pos].z] = air;
}
parent->liquidBodys[number] = NULL;
}
void liquid::render()
{
short length = list.size();
for (short pos=0; pos<length; pos++)
{
parent->renderAddLiquidOut(list[pos].x,list[pos].y,list[pos].z,water,waterLevel);
}
}[/code]

[/b]I can't afford to store floats for all the blocks because that would take up,
16^3 (blocks per chunk)
25^3 (chunks per map)
4 (bytes per float)
256MB of extra ram.

This is would also make the save games 5x as large making the game map load time no longer Realtime.

Currently I'm just storing a unsigned char for each block allowing me 256 blocks

Share this post


Link to post
Share on other sites
Nanoha    2682
The problem with the first water appears to be that your moving water right away. You do one cube, move the water to the adjacent cube and then when you update the next cube you do the same back. Thats going to be a problem whatever method you choose. I would do it in two steps, work out how much water you should add/remove for all cubes, then add/subract them after wards (rather than doing it as you go). I would do it something like this:
pass 1 for each cube, add up its current water level and the water level of all its neighbours (those below and to the sides). Work out the average. Each of those cubes should all have the average amount of water (You could weight it, such that less full squares get more water). Don't update the cubes yet though, work out how much you need to add/take away from each cube to get the required level (the average) and store it. Do that for all cubes.
Pass 2, add/remove the amount of water you stored.

I tried it out with some odd values, it slowly flattened out but not without bouncing a little (two high values around 1 low value) but that may look rather good, like two waves crashing together in the middle. You'll probably need some cut off value where your happy to consider squares to have equal water (even if they are slightly out). Also some value where there's so little water that it could have just evaporated (as in one of your videoes).

You probably want to treat water with nothing below it differently and just drop it all.

Share this post


Link to post
Share on other sites
coderWalker    127
[quote name='Nanoha' timestamp='1308088317' post='4823386']
The problem with the first water appears to be that your moving water right away. You do one cube, move the water to the adjacent cube and then when you update the next cube you do the same back. Thats going to be a problem whatever method you choose. I would do it in two steps, work out how much water you should add/remove for all cubes, then add/subract them after wards (rather than doing it as you go). I would do it something like this:
pass 1 for each cube, add up its current water level and the water level of all its neighbours (those below and to the sides). Work out the average. Each of those cubes should all have the average amount of water (You could weight it, such that less full squares get more water). Don't update the cubes yet though, work out how much you need to add/take away from each cube to get the required level (the average) and store it. Do that for all cubes.
Pass 2, add/remove the amount of water you stored.

I tried it out with some odd values, it slowly flattened out but not without bouncing a little (two high values around 1 low value) but that may look rather good, like two waves crashing together in the middle. You'll probably need some cut off value where your happy to consider squares to have equal water (even if they are slightly out). Also some value where there's so little water that it could have just evaporated (as in one of your videos).

You probably want to treat water with nothing below it differently and just drop it all.
[/quote]

The old water system is close to this, would you recommend dropping the new system?
All this list management and everything is getting a little out of hand.

Just realized, the goal of the new system was to keep all water that is touching in the x and y directions always level.
However this will create huge problems when the player trys to flood something large like cave.
This will result in a Large amount of allocations of new lists and merging, etc.
It seems that keeping an amount for every block is the only option.

I guess that's what was ment by this post:
[quote]Are you taking the time of reading what people is telling to you? Or you just wanna waste everyones time?[/quote]

I guess the reason it's so difficult to achieve this goal (Always level water) is because this it's not obtainable.

Also would there be a better method then just allocating 16x16x16 floats along with the blockID chars?
The problem is this could allocate [b]alot [/b]of unneeded memory.
[code]
char block[16][16][16];
float amount[16][16][16];
[/code]

Share this post


Link to post
Share on other sites
smasherprog    568
you can store it as a short. I was thinking about bad things that can happen, like if a player merges two large bodies of water. You probably have to develop some type of a system where after checking x amount of blocks, the function stops and records where it left off for the next game loop or something. This way, the amount of work will remain fixed. And, this might actually add some cool effects with water movement being slow, instead of happening instantly. This would help with your speed issues that would occur when too much work needs to be done per loop.

The work doesn't have to be done now, but over a couple of seconds is perfectly fine. Think about the cool effect, you can see the water moving in an area, either filling in or leaving.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this