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
26
ReflowScan(Map * map,const NodeDefManager * ndef)27 ReflowScan::ReflowScan(Map *map, const NodeDefManager *ndef) :
28 m_map(map),
29 m_ndef(ndef)
30 {
31 }
32
scan(MapBlock * block,UniqueQueue<v3s16> * liquid_queue)33 void ReflowScan::scan(MapBlock *block, UniqueQueue<v3s16> *liquid_queue)
34 {
35 m_block_pos = block->getPos();
36 m_rel_block_pos = block->getPosRelative();
37 m_liquid_queue = liquid_queue;
38
39 // Prepare the lookup which is a 3x3x3 array of the blocks surrounding the
40 // scanned block. Blocks are only added to the lookup if they are really
41 // needed. The lookup is indexed manually to use the same index in a
42 // bit-array (of uint32 type) which stores for unloaded blocks that they
43 // were already fetched from Map but were actually nullptr.
44 memset(m_lookup, 0, sizeof(m_lookup));
45 int block_idx = 1 + (1 * 9) + (1 * 3);
46 m_lookup[block_idx] = block;
47 m_lookup_state_bitset = 1 << block_idx;
48
49 // Scan the columns in the block
50 for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
51 for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
52 scanColumn(x, z);
53 }
54
55 // Scan neighbouring columns from the nearby blocks as they might contain
56 // liquid nodes that weren't allowed to flow to prevent gaps.
57 for (s16 i = 0; i < MAP_BLOCKSIZE; i++) {
58 scanColumn(i, -1);
59 scanColumn(i, MAP_BLOCKSIZE);
60 scanColumn(-1, i);
61 scanColumn(MAP_BLOCKSIZE, i);
62 }
63 }
64
lookupBlock(int x,int y,int z)65 inline MapBlock *ReflowScan::lookupBlock(int x, int y, int z)
66 {
67 // Gets the block that contains (x,y,z) relativ to the scanned block.
68 // This uses a lookup as there might be many lookups into the same
69 // neighbouring block which makes fetches from Map costly.
70 int bx = (MAP_BLOCKSIZE + x) / MAP_BLOCKSIZE;
71 int by = (MAP_BLOCKSIZE + y) / MAP_BLOCKSIZE;
72 int bz = (MAP_BLOCKSIZE + z) / MAP_BLOCKSIZE;
73 int idx = (bx + (by * 9) + (bz * 3));
74 MapBlock *result = m_lookup[idx];
75 if (!result && (m_lookup_state_bitset & (1 << idx)) == 0) {
76 // The block wasn't requested yet so fetch it from Map and store it
77 // in the lookup
78 v3s16 pos = m_block_pos + v3s16(bx - 1, by - 1, bz - 1);
79 m_lookup[idx] = result = m_map->getBlockNoCreateNoEx(pos);
80 m_lookup_state_bitset |= (1 << idx);
81 }
82 return result;
83 }
84
isLiquidFlowableTo(int x,int y,int z)85 inline bool ReflowScan::isLiquidFlowableTo(int x, int y, int z)
86 {
87 // Tests whether (x,y,z) is a node to which liquid might flow.
88 bool valid_position;
89 MapBlock *block = lookupBlock(x, y, z);
90 if (block) {
91 int dx = (MAP_BLOCKSIZE + x) % MAP_BLOCKSIZE;
92 int dy = (MAP_BLOCKSIZE + y) % MAP_BLOCKSIZE;
93 int dz = (MAP_BLOCKSIZE + z) % MAP_BLOCKSIZE;
94 MapNode node = block->getNodeNoCheck(dx, dy, dz, &valid_position);
95 if (node.getContent() != CONTENT_IGNORE) {
96 const ContentFeatures &f = m_ndef->get(node);
97 // NOTE: No need to check for flowing nodes with lower liquid level
98 // as they should only occur on top of other columns where they
99 // will be added to the queue themselves.
100 return f.floodable;
101 }
102 }
103 return false;
104 }
105
isLiquidHorizontallyFlowable(int x,int y,int z)106 inline bool ReflowScan::isLiquidHorizontallyFlowable(int x, int y, int z)
107 {
108 // Check if the (x,y,z) might spread to one of the horizontally
109 // neighbouring nodes
110 return isLiquidFlowableTo(x - 1, y, z) ||
111 isLiquidFlowableTo(x + 1, y, z) ||
112 isLiquidFlowableTo(x, y, z - 1) ||
113 isLiquidFlowableTo(x, y, z + 1);
114 }
115
scanColumn(int x,int z)116 void ReflowScan::scanColumn(int x, int z)
117 {
118 bool valid_position;
119
120 // Is the column inside a loaded block?
121 MapBlock *block = lookupBlock(x, 0, z);
122 if (!block)
123 return;
124
125 MapBlock *above = lookupBlock(x, MAP_BLOCKSIZE, z);
126 int dx = (MAP_BLOCKSIZE + x) % MAP_BLOCKSIZE;
127 int dz = (MAP_BLOCKSIZE + z) % MAP_BLOCKSIZE;
128
129 // Get the state from the node above the scanned block
130 bool was_ignore, was_liquid;
131 if (above) {
132 MapNode node = above->getNodeNoCheck(dx, 0, dz, &valid_position);
133 was_ignore = node.getContent() == CONTENT_IGNORE;
134 was_liquid = m_ndef->get(node).isLiquid();
135 } else {
136 was_ignore = true;
137 was_liquid = false;
138 }
139 bool was_checked = false;
140 bool was_pushed = false;
141
142 // Scan through the whole block
143 for (s16 y = MAP_BLOCKSIZE - 1; y >= 0; y--) {
144 MapNode node = block->getNodeNoCheck(dx, y, dz, &valid_position);
145 const ContentFeatures &f = m_ndef->get(node);
146 bool is_ignore = node.getContent() == CONTENT_IGNORE;
147 bool is_liquid = f.isLiquid();
148
149 if (is_ignore || was_ignore || is_liquid == was_liquid) {
150 // Neither topmost node of liquid column nor topmost node below column
151 was_checked = false;
152 was_pushed = false;
153 } else if (is_liquid) {
154 // This is the topmost node in the column
155 bool is_pushed = false;
156 if (f.liquid_type == LIQUID_FLOWING ||
157 isLiquidHorizontallyFlowable(x, y, z)) {
158 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, y, z));
159 is_pushed = true;
160 }
161 // Remember waschecked and waspushed to avoid repeated
162 // checks/pushes in case the column consists of only this node
163 was_checked = true;
164 was_pushed = is_pushed;
165 } else {
166 // This is the topmost node below a liquid column
167 if (!was_pushed && (f.floodable ||
168 (!was_checked && isLiquidHorizontallyFlowable(x, y + 1, z)))) {
169 // Activate the lowest node in the column which is one
170 // node above this one
171 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, y + 1, z));
172 }
173 }
174
175 was_liquid = is_liquid;
176 was_ignore = is_ignore;
177 }
178
179 // Check the node below the current block
180 MapBlock *below = lookupBlock(x, -1, z);
181 if (below) {
182 MapNode node = below->getNodeNoCheck(dx, MAP_BLOCKSIZE - 1, dz, &valid_position);
183 const ContentFeatures &f = m_ndef->get(node);
184 bool is_ignore = node.getContent() == CONTENT_IGNORE;
185 bool is_liquid = f.isLiquid();
186
187 if (is_ignore || was_ignore || is_liquid == was_liquid) {
188 // Neither topmost node of liquid column nor topmost node below column
189 } else if (is_liquid) {
190 // This is the topmost node in the column and might want to flow away
191 if (f.liquid_type == LIQUID_FLOWING ||
192 isLiquidHorizontallyFlowable(x, -1, z)) {
193 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, -1, z));
194 }
195 } else {
196 // This is the topmost node below a liquid column
197 if (!was_pushed && (f.floodable ||
198 (!was_checked && isLiquidHorizontallyFlowable(x, 0, z)))) {
199 // Activate the lowest node in the column which is one
200 // node above this one
201 m_liquid_queue->push_back(m_rel_block_pos + v3s16(x, 0, z));
202 }
203 }
204 }
205 }
206