3 Copyright (C) 2013 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 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.
24 #include "util/timetaker.h"
25 #include <string.h> // memcpy, memset
32 u32 emerge_load_time = 0;
33 u32 clearflag_time = 0;
34 //u32 getwaterpressure_time = 0;
35 //u32 spreadwaterpressure_time = 0;
36 u32 updateareawaterpressure_time = 0;
37 u32 flowwater_pre_time = 0;
40 VoxelManipulator::VoxelManipulator():
46 VoxelManipulator::~VoxelManipulator()
51 void VoxelManipulator::clear()
53 // Reset area to volume=0
61 void VoxelManipulator::print(std::ostream &o, INodeDefManager *ndef,
64 v3s16 em = m_area.getExtent();
65 v3s16 of = m_area.MinEdge;
66 o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
67 <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
69 for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
71 if(em.X >= 3 && em.Y >= 3)
73 if (y==m_area.MinEdge.Y+2) o<<"^ ";
74 else if(y==m_area.MinEdge.Y+1) o<<"| ";
75 else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
79 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
81 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
83 u8 f = m_flags[m_area.index(x,y,z)];
85 if(f & VOXELFLAG_NO_DATA)
90 MapNode n = m_data[m_area.index(x,y,z)];
91 content_t m = n.getContent();
93 if(mode == VOXELPRINT_MATERIAL)
98 else if(mode == VOXELPRINT_WATERPRESSURE)
100 if(ndef->get(m).isLiquid())
106 else if(m == CONTENT_AIR)
115 else if(mode == VOXELPRINT_LIGHT_DAY)
117 if(ndef->get(m).light_source != 0)
119 else if(ndef->get(m).light_propagates == false)
123 u8 light = n.getLight(LIGHTBANK_DAY, ndef);
127 c = 'a' + (light-10);
139 void VoxelManipulator::addArea(const VoxelArea &area)
141 // Cancel if requested area has zero volume
142 if (area.hasEmptyExtent())
145 // Cancel if m_area already contains the requested area
146 if(m_area.contains(area))
149 TimeTaker timer("addArea", &addarea_time);
151 // Calculate new area
153 // New area is the requested area if m_area has zero volume
154 if(m_area.hasEmptyExtent())
158 // Else add requested area to m_area
162 new_area.addArea(area);
165 s32 new_size = new_area.getVolume();
167 /*dstream<<"adding area ";
169 dstream<<", old area ";
170 m_area.print(dstream);
171 dstream<<", new area ";
172 new_area.print(dstream);
173 dstream<<", new_size="<<new_size;
174 dstream<<std::endl;*/
176 // Allocate new data and clear flags
177 MapNode *new_data = new MapNode[new_size];
179 u8 *new_flags = new u8[new_size];
181 memset(new_flags, VOXELFLAG_NO_DATA, new_size);
184 s32 old_x_width = m_area.MaxEdge.X - m_area.MinEdge.X + 1;
185 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
186 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
188 unsigned int old_index = m_area.index(m_area.MinEdge.X,y,z);
189 unsigned int new_index = new_area.index(m_area.MinEdge.X,y,z);
191 memcpy(&new_data[new_index], &m_data[old_index],
192 old_x_width * sizeof(MapNode));
193 memcpy(&new_flags[new_index], &m_flags[old_index],
194 old_x_width * sizeof(u8));
197 // Replace area, data and flags
201 MapNode *old_data = m_data;
202 u8 *old_flags = m_flags;
204 /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
205 <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
213 //dstream<<"addArea done"<<std::endl;
216 void VoxelManipulator::copyFrom(MapNode *src, const VoxelArea& src_area,
217 v3s16 from_pos, v3s16 to_pos, v3s16 size)
219 /* The reason for this optimised code is that we're a member function
220 * and the data type/layout of m_data is know to us: it's stored as
221 * [z*h*w + y*h + x]. Therefore we can take the calls to m_area index
222 * (which performs the preceding mapping/indexing of m_data) out of the
223 * inner loop and calculate the next index as we're iterating to gain
226 * src_step and dest_step is the amount required to be added to our index
227 * every time y increments. Because the destination area may be larger
228 * than the source area we need one additional variable (otherwise we could
229 * just continue adding dest_step as is done for the source data): dest_mod.
230 * dest_mod is the difference in size between a "row" in the source data
231 * and a "row" in the destination data (I am using the term row loosely
232 * and for illustrative purposes). E.g.
234 * src <-------------------->|'''''' dest mod ''''''''
235 * dest <--------------------------------------------->
237 * dest_mod (it's essentially a modulus) is added to the destination index
238 * after every full iteration of the y span.
240 * This method falls under the category "linear array and incrementing
244 s32 src_step = src_area.getExtent().X;
245 s32 dest_step = m_area.getExtent().X;
246 s32 dest_mod = m_area.index(to_pos.X, to_pos.Y, to_pos.Z + 1)
247 - m_area.index(to_pos.X, to_pos.Y, to_pos.Z)
248 - dest_step * size.Y;
250 s32 i_src = src_area.index(from_pos.X, from_pos.Y, from_pos.Z);
251 s32 i_local = m_area.index(to_pos.X, to_pos.Y, to_pos.Z);
253 for (s16 z = 0; z < size.Z; z++) {
254 for (s16 y = 0; y < size.Y; y++) {
255 memcpy(&m_data[i_local], &src[i_src], size.X * sizeof(*m_data));
256 memset(&m_flags[i_local], 0, size.X);
258 i_local += dest_step;
264 void VoxelManipulator::copyTo(MapNode *dst, const VoxelArea& dst_area,
265 v3s16 dst_pos, v3s16 from_pos, v3s16 size)
267 for(s16 z=0; z<size.Z; z++)
268 for(s16 y=0; y<size.Y; y++)
270 s32 i_dst = dst_area.index(dst_pos.X, dst_pos.Y+y, dst_pos.Z+z);
271 s32 i_local = m_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
272 for (s16 x = 0; x < size.X; x++) {
273 if (m_data[i_local].getContent() != CONTENT_IGNORE)
274 dst[i_dst] = m_data[i_local];
283 -----------------------------------------------------
286 void VoxelManipulator::clearFlag(u8 flags)
288 // 0-1ms on moderate area
289 TimeTaker timer("clearFlag", &clearflag_time);
291 //v3s16 s = m_area.getExtent();
293 /*dstream<<"clearFlag clearing area of size "
294 <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
299 /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
300 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
301 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
303 u8 f = m_flags[m_area.index(x,y,z)];
304 m_flags[m_area.index(x,y,z)] &= ~flags;
305 if(m_flags[m_area.index(x,y,z)] != f)
309 s32 volume = m_area.getVolume();
310 for(s32 i=0; i<volume; i++)
312 m_flags[i] &= ~flags;
315 /*s32 volume = m_area.getVolume();
316 for(s32 i=0; i<volume; i++)
319 m_flags[i] &= ~flags;
324 dstream<<"clearFlag changed "<<count<<" flags out of "
325 <<volume<<" nodes"<<std::endl;*/
328 void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
329 std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
332 v3s16(0,0,1), // back
334 v3s16(1,0,0), // right
335 v3s16(0,0,-1), // front
336 v3s16(0,-1,0), // bottom
337 v3s16(-1,0,0), // left
340 VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
343 // Loop through 6 neighbors
344 for(u16 i=0; i<6; i++)
346 // Get the position of the neighbor node
347 v3s16 n2pos = p + dirs[i];
349 u32 n2i = m_area.index(n2pos);
351 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
354 MapNode &n2 = m_data[n2i];
357 If the neighbor is dimmer than what was specified
358 as oldlight (the light of the previous node)
360 u8 light2 = n2.getLight(bank, nodemgr);
361 if(light2 < oldlight)
364 And the neighbor is transparent and it has some light
366 if(nodemgr->get(n2).light_propagates && light2 != 0)
369 Set light to 0 and add to queue
372 n2.setLight(bank, 0, nodemgr);
374 unspreadLight(bank, n2pos, light2, light_sources, nodemgr);
377 Remove from light_sources if it is there
378 NOTE: This doesn't happen nearly at all
380 /*if(light_sources.find(n2pos))
382 std::cout<<"Removed from light_sources"<<std::endl;
383 light_sources.remove(n2pos);
388 light_sources.insert(n2pos);
395 Goes recursively through the neighbours of the node.
397 Alters only transparent nodes.
399 If the lighting of the neighbour is lower than the lighting of
400 the node was (before changing it to 0 at the step before), the
401 lighting of the neighbour is set to 0 and then the same stuff
402 repeats for the neighbour.
404 The ending nodes of the routine are stored in light_sources.
405 This is useful when a light is removed. In such case, this
406 routine can be called for the light node and then again for
407 light_sources to re-light the area without the removed light.
409 values of from_nodes are lighting values.
411 void VoxelManipulator::unspreadLight(enum LightBank bank,
412 std::map<v3s16, u8> & from_nodes,
413 std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
415 if(from_nodes.empty())
418 for(std::map<v3s16, u8>::iterator j = from_nodes.begin();
419 j != from_nodes.end(); ++j)
421 unspreadLight(bank, j->first, j->second, light_sources, nodemgr);
428 Goes recursively through the neighbours of the node.
430 Alters only transparent nodes.
432 If the lighting of the neighbour is lower than the lighting of
433 the node was (before changing it to 0 at the step before), the
434 lighting of the neighbour is set to 0 and then the same stuff
435 repeats for the neighbour.
437 The ending nodes of the routine are stored in light_sources.
438 This is useful when a light is removed. In such case, this
439 routine can be called for the light node and then again for
440 light_sources to re-light the area without the removed light.
442 values of from_nodes are lighting values.
444 void VoxelManipulator::unspreadLight(enum LightBank bank,
445 core::map<v3s16, u8> & from_nodes,
446 core::map<v3s16, bool> & light_sources)
449 v3s16(0,0,1), // back
451 v3s16(1,0,0), // right
452 v3s16(0,0,-1), // front
453 v3s16(0,-1,0), // bottom
454 v3s16(-1,0,0), // left
457 if(from_nodes.size() == 0)
460 core::map<v3s16, u8> unlighted_nodes;
461 core::map<v3s16, u8>::Iterator j;
462 j = from_nodes.getIterator();
464 for(; j.atEnd() == false; j++)
466 v3s16 pos = j.getNode()->getKey();
468 addArea(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
470 //MapNode &n = m_data[m_area.index(pos)];
472 u8 oldlight = j.getNode()->getValue();
474 // Loop through 6 neighbors
475 for(u16 i=0; i<6; i++)
477 // Get the position of the neighbor node
478 v3s16 n2pos = pos + dirs[i];
480 u32 n2i = m_area.index(n2pos);
482 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
485 MapNode &n2 = m_data[n2i];
488 If the neighbor is dimmer than what was specified
489 as oldlight (the light of the previous node)
491 if(n2.getLight(bank, nodemgr) < oldlight)
494 And the neighbor is transparent and it has some light
496 if(nodemgr->get(n2).light_propagates && n2.getLight(bank, nodemgr) != 0)
499 Set light to 0 and add to queue
502 u8 current_light = n2.getLight(bank, nodemgr);
503 n2.setLight(bank, 0);
505 unlighted_nodes.insert(n2pos, current_light);
508 Remove from light_sources if it is there
509 NOTE: This doesn't happen nearly at all
511 /*if(light_sources.find(n2pos))
513 std::cout<<"Removed from light_sources"<<std::endl;
514 light_sources.remove(n2pos);
519 light_sources.insert(n2pos, true);
524 /*dstream<<"unspreadLight(): Changed block "
525 <<blockchangecount<<" times"
526 <<" for "<<from_nodes.size()<<" nodes"
529 if(unlighted_nodes.size() > 0)
530 unspreadLight(bank, unlighted_nodes, light_sources);
534 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p,
535 INodeDefManager *nodemgr)
537 const v3s16 dirs[6] = {
538 v3s16(0,0,1), // back
540 v3s16(1,0,0), // right
541 v3s16(0,0,-1), // front
542 v3s16(0,-1,0), // bottom
543 v3s16(-1,0,0), // left
546 VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
549 u32 i = m_area.index(p);
551 if(m_flags[i] & VOXELFLAG_NO_DATA)
554 MapNode &n = m_data[i];
556 u8 oldlight = n.getLight(bank, nodemgr);
557 u8 newlight = diminish_light(oldlight);
559 // Loop through 6 neighbors
560 for(u16 i=0; i<6; i++)
562 // Get the position of the neighbor node
563 v3s16 n2pos = p + dirs[i];
565 u32 n2i = m_area.index(n2pos);
567 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
570 MapNode &n2 = m_data[n2i];
572 u8 light2 = n2.getLight(bank, nodemgr);
575 If the neighbor is brighter than the current node,
576 add to list (it will light up this node on its turn)
578 if(light2 > undiminish_light(oldlight))
580 spreadLight(bank, n2pos, nodemgr);
583 If the neighbor is dimmer than how much light this node
584 would spread on it, add to list
586 if(light2 < newlight)
588 if(nodemgr->get(n2).light_propagates)
590 n2.setLight(bank, newlight, nodemgr);
591 spreadLight(bank, n2pos, nodemgr);
599 Lights neighbors of from_nodes, collects all them and then
602 NOTE: This is faster on small areas but will overflow the
603 stack on large areas. Thus it is not used.
605 void VoxelManipulator::spreadLight(enum LightBank bank,
606 core::map<v3s16, bool> & from_nodes)
608 if(from_nodes.size() == 0)
611 core::map<v3s16, bool> lighted_nodes;
612 core::map<v3s16, bool>::Iterator j;
613 j = from_nodes.getIterator();
615 for(; j.atEnd() == false; j++)
617 v3s16 pos = j.getNode()->getKey();
619 spreadLight(bank, pos);
626 Lights neighbors of from_nodes, collects all them and then
629 void VoxelManipulator::spreadLight(enum LightBank bank,
630 std::set<v3s16> & from_nodes, INodeDefManager *nodemgr)
632 const v3s16 dirs[6] = {
633 v3s16(0,0,1), // back
635 v3s16(1,0,0), // right
636 v3s16(0,0,-1), // front
637 v3s16(0,-1,0), // bottom
638 v3s16(-1,0,0), // left
641 if(from_nodes.empty())
644 std::set<v3s16> lighted_nodes;
646 for(std::set<v3s16>::iterator j = from_nodes.begin();
647 j != from_nodes.end(); ++j)
651 VoxelArea voxel_area(pos - v3s16(1,1,1), pos + v3s16(1,1,1));
654 u32 i = m_area.index(pos);
656 if(m_flags[i] & VOXELFLAG_NO_DATA)
659 MapNode &n = m_data[i];
661 u8 oldlight = n.getLight(bank, nodemgr);
662 u8 newlight = diminish_light(oldlight);
664 // Loop through 6 neighbors
665 for(u16 i=0; i<6; i++)
667 // Get the position of the neighbor node
668 v3s16 n2pos = pos + dirs[i];
672 u32 n2i = m_area.index(n2pos);
674 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
677 MapNode &n2 = m_data[n2i];
679 u8 light2 = n2.getLight(bank, nodemgr);
682 If the neighbor is brighter than the current node,
683 add to list (it will light up this node on its turn)
685 if(light2 > undiminish_light(oldlight))
687 lighted_nodes.insert(n2pos);
690 If the neighbor is dimmer than how much light this node
691 would spread on it, add to list
693 if(light2 < newlight)
695 if(nodemgr->get(n2).light_propagates)
697 n2.setLight(bank, newlight, nodemgr);
698 lighted_nodes.insert(n2pos);
702 catch(InvalidPositionException &e)
709 /*dstream<<"spreadLight(): Changed block "
710 <<blockchangecount<<" times"
711 <<" for "<<from_nodes.size()<<" nodes"
714 if(!lighted_nodes.empty())
715 spreadLight(bank, lighted_nodes, nodemgr);