src/reflowscan.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2016 MillersMan <millersman@users.noreply.github.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "reflowscan.h"
  21 #include "map.h"
  22 #include "mapblock.h"
  23 #include "nodedef.h"
  24 #include "util/timetaker.h"
  25 #include "util/cpp11.h"
  26
  27
  28 ReflowScan::ReflowScan(Map *map, INodeDefManager *ndef) :
  29         m_map(map),
  30         m_ndef(ndef),
  31         m_liquid_queue(nullptr)
  32 {
  33 }
  34
  35 void ReflowScan::scan(MapBlock *block, UniqueQueue<v3s16> *liquid_queue)
  36 {
  37         m_block_pos = block->getPos();
  38         m_rel_block_pos = block->getPosRelative();
  39         m_liquid_queue = liquid_queue;
  40
  41         // Prepare the lookup which is a 3x3x3 array of the blocks surrounding the
  42         // scanned block. Blocks are only added to the lookup if they are really
  43         // needed. The lookup is indexed manually to use the same index in a
  44         // bit-array (of uint32 type) which stores for unloaded blocks that they
  45         // were already fetched from Map but were actually nullptr.
  46         memset(m_lookup, 0, sizeof(m_lookup));
  47         int block_idx = 1 + (1 * 9) + (1 * 3);
  48         m_lookup[block_idx] = block;
  49         m_lookup_state_bitset = 1 << block_idx;
  50
  51         // Scan the columns in the block
  52         for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
  53         for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
  54                 scanColumn(x, z);
  55         }
  56
  57         // Scan neighbouring columns from the nearby blocks as they might contain
  58         // liquid nodes that weren't allowed to flow to prevent gaps.
  59         for (s16 i = 0; i < MAP_BLOCKSIZE; i++) {
  60                 scanColumn(i, -1);
  61                 scanColumn(i, MAP_BLOCKSIZE);
  62                 scanColumn(-1, i);
  63                 scanColumn(MAP_BLOCKSIZE, i);
  64         }
  65 }
  66
  67 inline MapBlock *ReflowScan::lookupBlock(int x, int y, int z)
  68 {
  69         // Gets the block that contains (x,y,z) relativ to the scanned block.
  70         // This uses a lookup as there might be many lookups into the same
  71         // neighbouring block which makes fetches from Map costly.
  72         int bx = (MAP_BLOCKSIZE + x) / MAP_BLOCKSIZE;
  73         int by = (MAP_BLOCKSIZE + y) / MAP_BLOCKSIZE;
  74         int bz = (MAP_BLOCKSIZE + z) / MAP_BLOCKSIZE;
  75         int idx = (bx + (by * 9) + (bz * 3));
  76         MapBlock *result = m_lookup[idx];
  77         if (!result && (m_lookup_state_bitset & (1 << idx)) == 0) {
  78                 // The block wasn't requested yet so fetch it from Map and store it
  79                 // in the lookup
  80                 v3s16 pos = m_block_pos + v3s16(bx - 1, by - 1, bz - 1);
  81                 m_lookup[idx] = result = m_map->getBlockNoCreateNoEx(pos);
  82                 m_lookup_state_bitset |= (1 << idx);
  83         }
  84         return result;
  85 }
  86
  87 inline bool ReflowScan::isLiquidFlowableTo(int x, int y, int z)
  88 {
  89         // Tests whether (x,y,z) is a node to which liquid might flow.
  90         bool valid_position;
  91         MapBlock *block = lookupBlock(x, y, z);
  92         if (block) {
  93                 int dx = (MAP_BLOCKSIZE + x) % MAP_BLOCKSIZE;
  94                 int dy = (MAP_BLOCKSIZE + y) % MAP_BLOCKSIZE;
  95                 int dz = (MAP_BLOCKSIZE + z) % MAP_BLOCKSIZE;
  96                 MapNode node = block->getNodeNoCheck(dx, dy, dz, &valid_position);
  97                 if (node.getContent() != CONTENT_IGNORE) {
  98                         const ContentFeatures &f = m_ndef->get(node);
  99                         // NOTE: No need to check for flowing nodes with lower liquid level
 100                         // as they should only occur on top of other columns where they
 101                         // will be added to the queue themselves.
 102                         return f.floodable;
 103                 }
 104         }
 105         return false;
 106 }
 107
 108 inline bool ReflowScan::isLiquidHorizontallyFlowable(int x, int y, int z)
 109 {
 110         // Check if the (x,y,z) might spread to one of the horizontally
 111         // neighbouring nodes
 112         return isLiquidFlowableTo(x - 1, y, z) ||
 113                 isLiquidFlowableTo(x + 1, y, z) ||
 114                 isLiquidFlowableTo(x, y, z - 1) ||
 115                 isLiquidFlowableTo(x, y, z + 1);
 116 }
 117
 118 void ReflowScan::scanColumn(int x, int z)
 119 {
 120         bool valid_position;
 121
 122         // Is the column inside a loaded block?
 123         MapBlock *block = lookupBlock(x, 0, z);
 124         if (!block)
 125                 return;
 126
 127         MapBlock *above = lookupBlock(x, MAP_BLOCKSIZE, z);
 128         int dx = (MAP_BLOCKSIZE + x) % MAP_BLOCKSIZE;
 129         int dz = (MAP_BLOCKSIZE + z) % MAP_BLOCKSIZE;
 130
 131         // Get the state from the node above the scanned block
 132         bool was_ignore, was_liquid;
 133         if (above) {
 134                 MapNode node = above->getNodeNoCheck(dx, 0, dz, &valid_position);
 135                 was_ignore = node.getContent() == CONTENT_IGNORE;
 136                 was_liquid = m_ndef->get(node).isLiquid();
 137         } else {
 138                 was_ignore = true;
 139                 was_liquid = false;
 140         }
 141         bool was_checked = false;
 142         bool was_pushed = false;
 143
 144         // Scan through the whole block
 145         for (s16 y = MAP_BLOCKSIZE - 1; y >= 0; y--) {
 146                 MapNode node = block->getNodeNoCheck(dx, y, dz, &valid_position);
 147                 const ContentFeatures &f = m_ndef->get(node);
 148                 bool is_ignore = node.getContent() == CONTENT_IGNORE;
 149                 bool is_liquid = f.isLiquid();
 150
 151                 if (is_ignore || was_ignore || is_liquid == was_liquid) {
 152                         // Neither topmost node of liquid column nor topmost node below column
 153                         was_checked = false;
 154                         was_pushed = false;
 155                 } else if (is_liquid) {
 156                         // This is the topmost node in the column
 157                         bool is_pushed = false;
 158                         if (f.liquid_type == LIQUID_FLOWING ||
 159                                         isLiquidHorizontallyFlowable(x, y, z)) {
 160                                 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, y, z));
 161                                 is_pushed = true;
 162                         }
 163                         // Remember waschecked and waspushed to avoid repeated
 164                         // checks/pushes in case the column consists of only this node
 165                         was_checked = true;
 166                         was_pushed = is_pushed;
 167                 } else {
 168                         // This is the topmost node below a liquid column
 169                         if (!was_pushed && (f.floodable ||
 170                                         (!was_checked && isLiquidHorizontallyFlowable(x, y + 1, z)))) {
 171                                 // Activate the lowest node in the column which is one
 172                                 // node above this one
 173                                 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, y + 1, z));
 174                         }
 175                 }
 176
 177                 was_liquid = is_liquid;
 178                 was_ignore = is_ignore;
 179         }
 180
 181         // Check the node below the current block
 182         MapBlock *below = lookupBlock(x, -1, z);
 183         if (below) {
 184                 MapNode node = below->getNodeNoCheck(dx, MAP_BLOCKSIZE - 1, dz, &valid_position);
 185                 const ContentFeatures &f = m_ndef->get(node);
 186                 bool is_ignore = node.getContent() == CONTENT_IGNORE;
 187                 bool is_liquid = f.isLiquid();
 188
 189                 if (is_ignore || was_ignore || is_liquid == was_liquid) {
 190                         // Neither topmost node of liquid column nor topmost node below column
 191                 } else if (is_liquid) {
 192                         // This is the topmost node in the column and might want to flow away
 193                         if (f.liquid_type == LIQUID_FLOWING ||
 194                                         isLiquidHorizontallyFlowable(x, -1, z)) {
 195                                 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, -1, z));
 196                         }
 197                 } else {
 198                         // This is the topmost node below a liquid column
 199                         if (!was_pushed && (f.floodable ||
 200                                         (!was_checked && isLiquidHorizontallyFlowable(x, 0, z)))) {
 201                                 // Activate the lowest node in the column which is one
 202                                 // node above this one
 203                                 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, 0, z));
 204                         }
 205                 }
 206         }
 207 }