3 Copyright (C) 2016 MillersMan <millersman@users.noreply.github.com>
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.
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.
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.
20 #include "reflowscan.h"
24 #include "util/timetaker.h"
27 ReflowScan::ReflowScan(Map
*map
, const NodeDefManager
*ndef
) :
33 void ReflowScan::scan(MapBlock
*block
, UniqueQueue
<v3s16
> *liquid_queue
)
35 m_block_pos
= block
->getPos();
36 m_rel_block_pos
= block
->getPosRelative();
37 m_liquid_queue
= liquid_queue
;
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
;
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
++) {
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
++) {
59 scanColumn(i
, MAP_BLOCKSIZE
);
61 scanColumn(MAP_BLOCKSIZE
, i
);
65 inline MapBlock
*ReflowScan::lookupBlock(int x
, int y
, int z
)
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
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
);
85 inline bool ReflowScan::isLiquidFlowableTo(int x
, int y
, int z
)
87 // Tests whether (x,y,z) is a node to which liquid might flow.
89 MapBlock
*block
= lookupBlock(x
, y
, z
);
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.
106 inline bool ReflowScan::isLiquidHorizontallyFlowable(int x
, int y
, int z
)
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);
116 void ReflowScan::scanColumn(int x
, int z
)
120 // Is the column inside a loaded block?
121 MapBlock
*block
= lookupBlock(x
, 0, z
);
125 MapBlock
*above
= lookupBlock(x
, MAP_BLOCKSIZE
, z
);
126 int dx
= (MAP_BLOCKSIZE
+ x
) % MAP_BLOCKSIZE
;
127 int dz
= (MAP_BLOCKSIZE
+ z
) % MAP_BLOCKSIZE
;
129 // Get the state from the node above the scanned block
130 bool was_ignore
, was_liquid
;
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();
139 bool was_checked
= false;
140 bool was_pushed
= false;
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();
149 if (is_ignore
|| was_ignore
|| is_liquid
== was_liquid
) {
150 // Neither topmost node of liquid column nor topmost node below column
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
));
161 // Remember waschecked and waspushed to avoid repeated
162 // checks/pushes in case the column consists of only this node
164 was_pushed
= is_pushed
;
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
));
175 was_liquid
= is_liquid
;
176 was_ignore
= is_ignore
;
179 // Check the node below the current block
180 MapBlock
*below
= lookupBlock(x
, -1, z
);
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();
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
));
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
));