3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 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 General Public License for more details.
15 You should have received a copy of the GNU 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.
23 #include "common_irrlicht.h"
29 A fast voxel manipulator class
37 extern u32 emerge_time;
38 extern u32 emerge_load_time;
41 This class resembles aabbox3d<s16> a lot, but has inclusive
42 edges for saner handling of integer sizes
47 // Starts as zero sized
53 VoxelArea(v3s16 min_edge, v3s16 max_edge):
68 void addArea(VoxelArea &a)
70 if(getExtent() == v3s16(0,0,0))
75 if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
76 if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
77 if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
78 if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
79 if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
80 if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
82 void addPoint(v3s16 p)
84 if(getExtent() == v3s16(0,0,0))
90 if(p.X < MinEdge.X) MinEdge.X = p.X;
91 if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
92 if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
93 if(p.X > MaxEdge.X) MaxEdge.X = p.X;
94 if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
95 if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
105 /*void operator+=(v3s16 off)
111 void operator-=(v3s16 off)
121 v3s16 getExtent() const
123 return MaxEdge - MinEdge + v3s16(1,1,1);
125 s32 getVolume() const
127 v3s16 e = getExtent();
128 return (s32)e.X * (s32)e.Y * (s32)e.Z;
130 bool contains(const VoxelArea &a) const
132 // No area contains an empty area
133 // NOTE: Algorithms depend on this, so do not change.
134 if(a.getExtent() == v3s16(0,0,0))
138 a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
139 a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
140 a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
143 bool contains(v3s16 p) const
146 p.X >= MinEdge.X && p.X <= MaxEdge.X &&
147 p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
148 p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
151 bool operator==(const VoxelArea &other) const
153 return (MinEdge == other.MinEdge
154 && MaxEdge == other.MaxEdge);
157 VoxelArea operator+(v3s16 off) const
159 return VoxelArea(MinEdge+off, MaxEdge+off);
162 VoxelArea operator-(v3s16 off) const
164 return VoxelArea(MinEdge-off, MaxEdge-off);
168 Returns 0-6 non-overlapping areas that can be added to
169 a to make up this area.
173 void diff(const VoxelArea &a, core::list<VoxelArea> &result)
176 This can result in a maximum of 6 areas
179 // If a is an empty area, return the current area as a whole
180 if(a.getExtent() == v3s16(0,0,0))
183 if(b.getVolume() != 0)
190 // Take back area, XY inclusive
192 v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
193 v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
194 VoxelArea b(min, max);
195 if(b.getVolume() != 0)
199 // Take front area, XY inclusive
201 v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
202 v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
203 VoxelArea b(min, max);
204 if(b.getVolume() != 0)
208 // Take top area, X inclusive
210 v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
211 v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
212 VoxelArea b(min, max);
213 if(b.getVolume() != 0)
217 // Take bottom area, X inclusive
219 v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
220 v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
221 VoxelArea b(min, max);
222 if(b.getVolume() != 0)
226 // Take left area, non-inclusive
228 v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
229 v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
230 VoxelArea b(min, max);
231 if(b.getVolume() != 0)
235 // Take right area, non-inclusive
237 v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
238 v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
239 VoxelArea b(min, max);
240 if(b.getVolume() != 0)
247 Translates position from virtual coordinates to array index
249 s32 index(s16 x, s16 y, s16 z) const
251 v3s16 em = getExtent();
253 s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
254 //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
257 s32 index(v3s16 p) const
259 return index(p.X, p.Y, p.Z);
262 void print(std::ostream &o) const
264 v3s16 e = getExtent();
272 <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
275 // Edges are inclusive
280 // Hasn't been copied from source (emerged)
281 #define VOXELFLAG_NOT_LOADED (1<<0)
282 // Checked as being inexistent in source
283 #define VOXELFLAG_INEXISTENT (1<<1)
284 // Algorithm-dependent
285 // flowWater: "visited"
286 #define VOXELFLAG_CHECKED (1<<2)
287 // Algorithm-dependent
288 // getWaterPressure: "visited"
289 #define VOXELFLAG_CHECKED2 (1<<3)
290 // Algorithm-dependent
291 // spreadWaterPressure: "visited"
292 #define VOXELFLAG_CHECKED3 (1<<4)
293 // Algorithm-dependent
294 // water: "pressure check route node"
295 #define VOXELFLAG_CHECKED4 (1<<5)
301 VOXELPRINT_WATERPRESSURE,
304 class VoxelManipulator /*: public NodeContainer*/
308 virtual ~VoxelManipulator();
311 Virtuals from NodeContainer
313 /*virtual u16 nodeContainerId() const
315 return NODECONTAINER_ID_VOXELMANIPULATOR;
317 bool isValidPosition(v3s16 p)
320 return !(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT);
322 // These are a bit slow and shouldn't be used internally
323 MapNode getNode(v3s16 p)
327 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
329 dstream<<"EXCEPT: VoxelManipulator::getNode(): "
330 <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
331 <<", index="<<m_area.index(p)
332 <<", flags="<<(int)m_flags[m_area.index(p)]
333 <<" is inexistent"<<std::endl;
334 throw InvalidPositionException
335 ("VoxelManipulator: getNode: inexistent");
338 return m_data[m_area.index(p)];
340 void setNode(v3s16 p, MapNode &n)
344 m_data[m_area.index(p)] = n;
345 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
346 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
348 void setNodeNoRef(v3s16 p, MapNode n)
353 /*void setExists(VoxelArea a)
356 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
357 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
358 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
360 m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
364 /*MapNode & operator[](v3s16 p)
366 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
367 if(isValidPosition(p) == false)
368 emerge(VoxelArea(p));
370 return m_data[m_area.index(p)];
377 virtual void clear();
379 void print(std::ostream &o, VoxelPrintMode mode=VOXELPRINT_MATERIAL);
381 void addArea(VoxelArea area);
384 Copy data and set flags to 0
385 dst_area.getExtent() <= src_area.getExtent()
387 void copyFrom(MapNode *src, VoxelArea src_area,
388 v3s16 from_pos, v3s16 to_pos, v3s16 size);
394 void interpolate(VoxelArea area);
396 void clearFlag(u8 flag);
398 // VOXELFLAG_CHECKED2s must usually be cleared before calling
399 // -1: dead end, 0-255: pressure
400 // highest_y: Highest found water y is stored here.
401 // Must be initialized to -32768
402 int getWaterPressure(v3s16 p, s16 &highest_y, int recur_count);
405 VOXELFLAG_CHECKED3s must usually be cleared before calling.
407 active_nodes: surface-touching air nodes with flow-causing
408 pressure. set-like dummy map container.
410 Spreads pressure pr at node p to request_area or as far as
411 there is invalid pressure.
413 void spreadWaterPressure(v3s16 p, int pr,
414 VoxelArea request_area,
415 core::map<v3s16, u8> &active_nodes,
419 VOXELFLAG_CHECKED3s must usually be cleared before calling.
421 void updateAreaWaterPressure(VoxelArea a,
422 core::map<v3s16, u8> &active_nodes,
423 bool checked3_is_clear=false);
426 Returns true if moved something
428 bool flowWater(v3s16 removed_pos,
429 core::map<v3s16, u8> &active_nodes,
430 int recursion_depth=0,
431 bool debugprint=false,
436 To flow some water, call this with the target node in
438 TODO: Make the active_nodes map to contain some vectors
439 that are properly sorted according to water flow order.
440 The current order makes water flow strangely if the
441 first one is always taken.
442 No, active_nodes should preserve the order stuff is
443 added to it, in addition to adhering the water flow
446 void flowWater(core::map<v3s16, u8> &active_nodes,
447 int recursion_depth=0,
448 bool debugprint=false,
457 Get the contents of the requested area from somewhere.
458 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
459 Shall reset VOXELFLAG_NOT_LOADED
461 If not found from source, add with VOXELFLAG_INEXISTENT
463 virtual void emerge(VoxelArea a, s32 caller_id=-1)
465 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
467 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
468 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
469 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
471 s32 i = m_area.index(x,y,z);
472 // Don't touch nodes that have already been loaded
473 if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
475 m_flags[i] = VOXELFLAG_INEXISTENT;
484 The area that is stored in m_data.
485 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
486 MaxEdge is 1 higher than maximum allowed position
491 NULL if data size is 0 (extent (0,0,0))
492 Data is stored as [z*h*w + y*h + x]
501 //TODO: Use these or remove them
502 //TODO: Would these make any speed improvement?
503 //bool m_pressure_route_valid;
504 //v3s16 m_pressure_route_surface;