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"
33 A fast voxel manipulator class
41 extern u32 emerge_time;
42 extern u32 emerge_load_time;
45 This class resembles aabbox3d<s16> a lot, but has inclusive
46 edges for saner handling of integer sizes
51 // Starts as zero sized
57 VoxelArea(v3s16 min_edge, v3s16 max_edge):
72 void addArea(VoxelArea &a)
74 if(getExtent() == v3s16(0,0,0))
79 if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
80 if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
81 if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
82 if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
83 if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
84 if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
86 void addPoint(v3s16 p)
88 if(getExtent() == v3s16(0,0,0))
94 if(p.X < MinEdge.X) MinEdge.X = p.X;
95 if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
96 if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
97 if(p.X > MaxEdge.X) MaxEdge.X = p.X;
98 if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
99 if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
109 /*void operator+=(v3s16 off)
115 void operator-=(v3s16 off)
125 v3s16 getExtent() const
127 return MaxEdge - MinEdge + v3s16(1,1,1);
129 s32 getVolume() const
131 v3s16 e = getExtent();
132 return (s32)e.X * (s32)e.Y * (s32)e.Z;
134 bool contains(const VoxelArea &a) const
136 // No area contains an empty area
137 // NOTE: Algorithms depend on this, so do not change.
138 if(a.getExtent() == v3s16(0,0,0))
142 a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
143 a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
144 a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
147 bool contains(v3s16 p) const
150 p.X >= MinEdge.X && p.X <= MaxEdge.X &&
151 p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
152 p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
155 bool operator==(const VoxelArea &other) const
157 return (MinEdge == other.MinEdge
158 && MaxEdge == other.MaxEdge);
161 VoxelArea operator+(v3s16 off) const
163 return VoxelArea(MinEdge+off, MaxEdge+off);
166 VoxelArea operator-(v3s16 off) const
168 return VoxelArea(MinEdge-off, MaxEdge-off);
172 Returns 0-6 non-overlapping areas that can be added to
173 a to make up this area.
177 void diff(const VoxelArea &a, core::list<VoxelArea> &result)
180 This can result in a maximum of 6 areas
183 // If a is an empty area, return the current area as a whole
184 if(a.getExtent() == v3s16(0,0,0))
187 if(b.getVolume() != 0)
194 // Take back area, XY inclusive
196 v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
197 v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
198 VoxelArea b(min, max);
199 if(b.getVolume() != 0)
203 // Take front area, XY inclusive
205 v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
206 v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
207 VoxelArea b(min, max);
208 if(b.getVolume() != 0)
212 // Take top area, X inclusive
214 v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
215 v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
216 VoxelArea b(min, max);
217 if(b.getVolume() != 0)
221 // Take bottom area, X inclusive
223 v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
224 v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
225 VoxelArea b(min, max);
226 if(b.getVolume() != 0)
230 // Take left area, non-inclusive
232 v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
233 v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
234 VoxelArea b(min, max);
235 if(b.getVolume() != 0)
239 // Take right area, non-inclusive
241 v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
242 v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
243 VoxelArea b(min, max);
244 if(b.getVolume() != 0)
251 Translates position from virtual coordinates to array index
253 s32 index(s16 x, s16 y, s16 z) const
255 v3s16 em = getExtent();
257 s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
258 //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
261 s32 index(v3s16 p) const
263 return index(p.X, p.Y, p.Z);
266 void print(std::ostream &o) const
268 v3s16 e = getExtent();
276 <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
279 // Edges are inclusive
284 // Hasn't been copied from source (emerged)
285 #define VOXELFLAG_NOT_LOADED (1<<0)
286 // Checked as being inexistent in source
287 #define VOXELFLAG_INEXISTENT (1<<1)
288 // Algorithm-dependent
289 // flowWater: "visited"
290 #define VOXELFLAG_CHECKED (1<<2)
291 // Algorithm-dependent
292 // getWaterPressure: "visited"
293 #define VOXELFLAG_CHECKED2 (1<<3)
294 // Algorithm-dependent
295 // spreadWaterPressure: "visited"
296 #define VOXELFLAG_CHECKED3 (1<<4)
297 // Algorithm-dependent
298 // water: "pressure check route node"
299 #define VOXELFLAG_CHECKED4 (1<<5)
305 VOXELPRINT_WATERPRESSURE,
308 class VoxelManipulator /*: public NodeContainer*/
312 virtual ~VoxelManipulator();
315 Virtuals from NodeContainer
317 /*virtual u16 nodeContainerId() const
319 return NODECONTAINER_ID_VOXELMANIPULATOR;
321 bool isValidPosition(v3s16 p)
324 return !(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT);
328 These are a bit slow and shouldn't be used internally.
329 Use m_data[m_area.index(p)] instead.
331 MapNode getNode(v3s16 p)
335 if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
337 dstream<<"EXCEPT: VoxelManipulator::getNode(): "
338 <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
339 <<", index="<<m_area.index(p)
340 <<", flags="<<(int)m_flags[m_area.index(p)]
341 <<" is inexistent"<<std::endl;
342 throw InvalidPositionException
343 ("VoxelManipulator: getNode: inexistent");
346 return m_data[m_area.index(p)];
348 void setNode(v3s16 p, MapNode &n)
352 m_data[m_area.index(p)] = n;
353 m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
354 m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
356 void setNodeNoRef(v3s16 p, MapNode n)
361 /*void setExists(VoxelArea a)
364 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
365 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
366 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
368 m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_INEXISTENT;
372 /*MapNode & operator[](v3s16 p)
374 //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
375 if(isValidPosition(p) == false)
376 emerge(VoxelArea(p));
378 return m_data[m_area.index(p)];
385 virtual void clear();
387 void print(std::ostream &o, VoxelPrintMode mode=VOXELPRINT_MATERIAL);
389 void addArea(VoxelArea area);
392 Copy data and set flags to 0
393 dst_area.getExtent() <= src_area.getExtent()
395 void copyFrom(MapNode *src, VoxelArea src_area,
396 v3s16 from_pos, v3s16 to_pos, v3s16 size);
402 void clearFlag(u8 flag);
404 void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
405 core::map<v3s16, bool> & light_sources);
406 void unspreadLight(enum LightBank bank,
407 core::map<v3s16, u8> & from_nodes,
408 core::map<v3s16, bool> & light_sources);
410 void spreadLight(enum LightBank bank, v3s16 p);
411 void spreadLight(enum LightBank bank,
412 core::map<v3s16, bool> & from_nodes);
415 // VOXELFLAG_CHECKED2s must usually be cleared before calling
416 // -1: dead end, 0-255: pressure
417 // highest_y: Highest found water y is stored here.
418 // Must be initialized to -32768
419 int getWaterPressure(v3s16 p, s16 &highest_y, int recur_count);
422 VOXELFLAG_CHECKED3s must usually be cleared before calling.
424 active_nodes: surface-touching air nodes with flow-causing
425 pressure. set-like dummy map container.
427 Spreads pressure pr at node p to request_area or as far as
428 there is invalid pressure.
430 void spreadWaterPressure(v3s16 p, int pr,
431 VoxelArea request_area,
432 core::map<v3s16, u8> &active_nodes,
436 VOXELFLAG_CHECKED3s must usually be cleared before calling.
438 void updateAreaWaterPressure(VoxelArea a,
439 core::map<v3s16, u8> &active_nodes,
440 bool checked3_is_clear=false);
443 Returns true if moved something
445 bool flowWater(v3s16 removed_pos,
446 core::map<v3s16, u8> &active_nodes,
447 int recursion_depth=0,
448 bool debugprint=false,
453 To flow some water, call this with the target node in
455 TODO: Make the active_nodes map to contain some vectors
456 that are properly sorted according to water flow order.
457 The current order makes water flow strangely if the
458 first one is always taken.
459 No, active_nodes should preserve the order stuff is
460 added to it, in addition to adhering the water flow
463 void flowWater(core::map<v3s16, u8> &active_nodes,
464 int recursion_depth=0,
465 bool debugprint=false,
475 Get the contents of the requested area from somewhere.
476 Shall touch only nodes that have VOXELFLAG_NOT_LOADED
477 Shall reset VOXELFLAG_NOT_LOADED
479 If not found from source, add with VOXELFLAG_INEXISTENT
481 virtual void emerge(VoxelArea a, s32 caller_id=-1)
483 //dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
485 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
486 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
487 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
489 s32 i = m_area.index(x,y,z);
490 // Don't touch nodes that have already been loaded
491 if(!(m_flags[i] & VOXELFLAG_NOT_LOADED))
493 m_flags[i] = VOXELFLAG_INEXISTENT;
502 The area that is stored in m_data.
503 addInternalBox should not be used if getExtent() == v3s16(0,0,0)
504 MaxEdge is 1 higher than maximum allowed position
509 NULL if data size is 0 (extent (0,0,0))
510 Data is stored as [z*h*w + y*h + x]
519 //TODO: Use these or remove them
520 //TODO: Would these make any speed improvement?
521 //bool m_pressure_route_valid;
522 //v3s16 m_pressure_route_surface;
527 bool m_disable_water_climb;