From 5e0c284f3a8debdd9ebb080f80e36dceb7bc4ce2 Mon Sep 17 00:00:00 2001 From: Perttu Ahola Date: Wed, 1 Dec 2010 15:20:12 +0200 Subject: [PATCH] some work-in-progress water stuff --- Makefile | 4 +- src/main.cpp | 194 +++++++++++++++++++++++++++++++++++++ src/mapnode.h | 22 +---- src/test.cpp | 55 +++++++++-- src/voxel.cpp | 264 +++++++++++++++++++++++++++++++++----------------- src/voxel.h | 119 ++++++++++++++++------- 6 files changed, 510 insertions(+), 148 deletions(-) diff --git a/Makefile b/Makefile index 2b4e8dda..102a3dcd 100644 --- a/Makefile +++ b/Makefile @@ -13,9 +13,9 @@ JTHREADPATH = ../jthread/jthread-1.2.1 CPPFLAGS = -I$(IRRLICHTPATH)/include -I/usr/X11R6/include -I$(JTHREADPATH)/src #CXXFLAGS = -O2 -ffast-math -Wall -fomit-frame-pointer -pipe -CXXFLAGS = -O2 -ffast-math -Wall -g -pipe +#CXXFLAGS = -O2 -ffast-math -Wall -g -pipe #CXXFLAGS = -O1 -ffast-math -Wall -g -#CXXFLAGS = -Wall -g -O0 +CXXFLAGS = -Wall -g -O0 #CXXFLAGS = -O3 -ffast-math -Wall #CXXFLAGS = -O3 -ffast-math -Wall -g diff --git a/src/main.cpp b/src/main.cpp index 677f0384..938eb14e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -81,6 +81,9 @@ SUGGESTION: Use same technique for sector heightmaps as what we're using for UnlimitedHeightmap? (getting all neighbors when generating) +TODO: Proper handling of spawning place (try to find something that + is not in the middle of an ocean (some land to stand on at + least) and save it in map config. SUGG: Set server to automatically find a good spawning place in some place where there is water and land. - Map to have a getWalkableNear(p) @@ -176,6 +179,197 @@ TODO: MovingObject::move and Player::move are basically the same. Doing now: ====================================================================== +Water dynamics pseudo-code (block = MapNode): +SUGG: Create separate flag table in VoxelManipulator to allow fast +clearing of "modified" flags + +neighborCausedPressure(pos): + pressure = 0 + dirs = {down, left, right, back, front, up} + for d in dirs: + pos2 = pos + d + p = block_at(pos2).pressure + if d.Y == 1 and p > min: + p -= 1 + if d.Y == -1 and p < max: + p += 1 + if p > pressure: + pressure = p + return pressure + +# This should somehow update all changed pressure values +# in an unknown body of water +updateWaterPressure(pos): + TODO + +FIXME: This goes in an indefinite loop when there is an underwater +chamber like this: + +#111###### +#222##22## +#33333333x<- block removed from here +########## + +#111###### +#222##22## +#3333333x1 +########## + +#111###### +#222##22## +#333333x11 +########## + +#111###### +#222##2x## +#333333333 +########## + +#111###### +#222##x2## +#333333333 +########## + +Now, consider moving to the last block not allowed. + +Consider it a 3D case with a depth of 2. We're now at this situation. +Note the additional blocking ## in the second depth plane. + +z=1 z=2 +#111###### #111###### +#222##x2## #222##22## +#333333333 #33333##33 +########## ########## + +#111###### #111###### +#222##22## #222##x2## +#333333333 #33333##33 +########## ########## + +#111###### #111###### +#222##22## #222##2x## +#333333333 #33333##33 +########## ########## + +Now there is nowhere to go, without going to an already visited block, +but the pressure calculated in here from neighboring blocks is >= 2, +so it is not the final ending. + +We will back up to a state where there is somewhere to go to. +It is this state: + +#111###### #111###### +#222##22## #222##22## +#333333x33 #33333##33 +########## ########## + +Then just go on, avoiding already visited blocks: + +#111###### #111###### +#222##22## #222##22## +#33333x333 #33333##33 +########## ########## + +#111###### #111###### +#222##22## #222##22## +#3333x3333 #33333##33 +########## ########## + +#111###### #111###### +#222##22## #222##22## +#333x33333 #33333##33 +########## ########## + +#111###### #111###### +#222##22## #222##22## +#33x333333 #33333##33 +########## ########## + +#111###### #111###### +#22x##22## #222##22## +#333333333 #33333##33 +########## ########## + +#11x###### #111###### +#222##22## #222##22## +#333333333 #33333##33 +########## ########## + +"Blob". the air bubble finally got out of the water. +Then return recursively to a state where there is air next to water, +clear the visit flags and feed the neighbor of the water recursively +to the algorithm. + +#11 ###### #111###### +#222##22## #222##22## +#333333333x #33333##33 +########## ########## + +#11 ###### #111###### +#222##22## #222##22## +#33333333x3 #33333##33 +########## ########## + +...and so on. + + +# removed_pos: a position that has been changed from something to air +flowWater(removed_pos): + dirs = {top, left, right, back, front, bottom} + selected_dir = None + for d in dirs: + b2 = removed_pos + d + + # Ignore positions that don't have water + if block_at(b2) != water: + continue + + # Ignore positions that have already been checked + if block_at(b2).checked: + continue + + # If block is at top, select it always. + if d.Y == 1: + selected_dir = d + break + + # If block is at bottom, select it if it has enough pressure. + # >= 3 needed for stability (and sanity) + if d.Y == -1: + if block_at(b2).pressure >= 3: + selected_dir = d + break + continue + + # Else block is at some side. select it if it has enough pressure. + if block_at(b2).pressure >= 2: + selected_dir = d + break + + # If there is nothing to do anymore, return. + if selected_dir == None + return + + b2 = removed_pos + selected_dir + + # Move block + set_block(removed_pos, block_at(b2)) + set_block(b2, air_block) + + # Update pressure + updateWaterPressure(removed_pos) + + # Flow water to the newly created empty position + flowWater(b2) + + # Check empty positions around and try flowing water to them + for d in dirs: + b3 = removed_pos + d + # Ignore positions that are not air + if block_at(b3) is not air: + continue + flowWater(b3) + ====================================================================== diff --git a/src/mapnode.h b/src/mapnode.h index 789cedb2..02abe4e5 100644 --- a/src/mapnode.h +++ b/src/mapnode.h @@ -35,9 +35,6 @@ with this program; if not, write to the Free Software Foundation, Inc., /* Ignored node. - param is used for custom information in special containers, - like VoxelManipulator. - Anything that stores MapNodes doesn't have to preserve parameters associated with this material. @@ -67,27 +64,12 @@ enum Material MATERIAL_GRASS, - /* - For water, the param is water pressure. 0...127. - TODO: No, at least the lowest nibble is used for lighting. - - - Water will be a bit like light, but with different flow - behavior. - - Water blocks will fall down if there is empty space below. - - If there is water below, the pressure of the block below is - the pressure of the current block + 1, or higher. - - If there is any pressure in a horizontally neighboring - block, a water block will try to move away from it. - - If there is >=2 of pressure in a block below, water will - try to move upwards. - - NOTE: To keep large operations fast, we have to keep a - cache of the water-air-surfaces, just like with light - */ MATERIAL_WATER, MATERIAL_LIGHT, MATERIAL_TREE, + MATERIAL_LEAVES, MATERIAL_GRASS_FOOTSTEPS, @@ -216,6 +198,8 @@ struct MapNode */ s8 param; + u8 pressure; + MapNode(const MapNode & n) { *this = n; diff --git a/src/test.cpp b/src/test.cpp index 005db2d2..6b285e3a 100644 --- a/src/test.cpp +++ b/src/test.cpp @@ -157,17 +157,16 @@ struct TestVoxelManipulator v.print(dstream); dstream<<"*** Setting (-1,0,-1)=2 ***"<=0; y--) + for(s16 x=0; x=m_area.MinEdge.Y; y--) + { + if(em.X >= 3 && em.Y >= 3) + { + if (y==m_area.MinEdge.Y+2) o<<"^ "; + else if(y==m_area.MinEdge.Y+1) o<<"| "; + else if(y==m_area.MinEdge.Y+0) o<<"y x-> "; + else o<<" "; + } + + for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++) + { + for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++) + { + u8 f = m_flags[m_area.index(x,y,z)]; + char c; + if(f & VOXELFLAG_NOT_LOADED) + c = 'N'; + else if(f & VOXELFLAG_INEXISTENT) + c = 'I'; + else + { + c = 'X'; + u8 m = m_data[m_area.index(x,y,z)].d; + if(m <= 9) + c = m + '0'; + } + o<= 3 && em.Y >= 3) - { - if(y==m_area.MinEdge.Y+0) o<<"y x-> "; - if(y==m_area.MinEdge.Y+1) o<<"| "; - if(y==m_area.MinEdge.Y+2) o<<"V "; - } + /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data + <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<getNode(p_from + p); - m_data[m_area.index(p_to + p)] = n; - } - catch(InvalidPositionException &e) + p = removed_pos + dirs[i]; + u8 f = m_flags[m_area.index(p)]; + // Inexistent or checked nodes can't move + if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED)) + continue; + MapNode &n = m_data[m_area.index(p)]; + // Only liquid nodes can move + if(material_liquid(n.d) == false) + continue; + // If block is at top, select it always + if(i == 0) { + break; } - - /*v3s16 p(x,y,z); - MapNode n(MATERIAL_IGNORE); - try{ - n = c->getNode(p_from + p); + // If block is at bottom, select it if it has enough pressure + if(i == 5) + { + if(n.pressure >= 3) + break; + continue; } - catch(InvalidPositionException &e) + // Else block is at some side. Select it if it has enough pressure + if(n.pressure >= 2) { + break; } - m_data[m_area.index(p_to + p)] = n;*/ } -} -void VoxelManipulator::blitToNodeContainer - (v3s16 p_from, v3s16 p_to, v3s16 size, NodeContainer *c) -{ - for(s16 z=0; z=0; i--) { - v3s16 p(x,y,z); - try{ - MapNode &n = m_data[m_area.index(p_from + p)]; - if(n.d == MATERIAL_IGNORE) - continue; - c->setNode(p_to + p, n); - } - catch(InvalidPositionException &e) - { - } + p = removed_pos + dirs[i]; + u8 f = m_flags[m_area.index(p)]; + // Water can't move to inexistent nodes + if(f & VOXELFLAG_INEXISTENT) + continue; + MapNode &n = m_data[m_area.index(p)]; + // Water can only move to air + if(n.d != MATERIAL_AIR) + continue; + flowWater(p); } } -#endif /* MapVoxelManipulator @@ -254,12 +336,18 @@ void MapVoxelManipulator::emerge(VoxelArea a) for(s16 x=0; xgetNode(a.MinEdge + p); - m_data[m_area.index(a.MinEdge + p)] = n; + m_data[i] = n; + m_flags[i] = 0; } catch(InvalidPositionException &e) { + m_flags[i] = VOXELFLAG_INEXISTENT; } } } @@ -280,9 +368,11 @@ void MapVoxelManipulator::blitBack { v3s16 p(x,y,z); - MapNode &n = m_data[m_area.index(p)]; - if(n.d == MATERIAL_IGNORE) + u8 f = m_flags[m_area.index(p)]; + if(f & (VOXELFLAG_NOT_LOADED|VOXELFLAG_INEXISTENT)) continue; + + MapNode &n = m_data[m_area.index(p)]; v3s16 blockpos = getNodeBlockPos(p); diff --git a/src/voxel.h b/src/voxel.h index 2bc591d2..3a4dacd4 100644 --- a/src/voxel.h +++ b/src/voxel.h @@ -25,7 +25,7 @@ with this program; if not, write to the Free Software Foundation, Inc., #include /* - TODO: A fast voxel manipulator class + A fast voxel manipulator class Not thread-safe. */ @@ -71,16 +71,24 @@ public: if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y; if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z; } - v3s16 getExtent() + v3s16 getExtent() const { return MaxEdge - MinEdge + v3s16(1,1,1); } - s32 getVolume() + s32 getVolume() const { v3s16 e = getExtent(); return (s32)e.X * (s32)e.Y * (s32)e.Z; } - bool isInside(v3s16 p) + bool contains(VoxelArea &a) const + { + return( + a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X && + a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y && + a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z + ); + } + bool contains(v3s16 p) const { return( p.X >= MinEdge.X && p.X <= MaxEdge.X && @@ -88,7 +96,7 @@ public: p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z ); } - bool operator==(const VoxelArea &other) + bool operator==(const VoxelArea &other) const { return (MinEdge == other.MinEdge && MaxEdge == other.MaxEdge); @@ -97,7 +105,7 @@ public: /* Translates position from virtual coordinates to array index */ - s32 index(s16 x, s16 y, s16 z) + s32 index(s16 x, s16 y, s16 z) const { v3s16 em = getExtent(); v3s16 off = MinEdge; @@ -105,12 +113,12 @@ public: //dstream<<" i("<