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.
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():
44 m_disable_water_climb = false;
47 VoxelManipulator::~VoxelManipulator()
56 void VoxelManipulator::clear()
58 // Reset area to volume=0
68 void VoxelManipulator::print(std::ostream &o, VoxelPrintMode mode)
70 v3s16 em = m_area.getExtent();
71 v3s16 of = m_area.MinEdge;
72 o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
73 <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
75 for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
77 if(em.X >= 3 && em.Y >= 3)
79 if (y==m_area.MinEdge.Y+2) o<<"^ ";
80 else if(y==m_area.MinEdge.Y+1) o<<"| ";
81 else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
85 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
87 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
89 u8 f = m_flags[m_area.index(x,y,z)];
91 if(f & VOXELFLAG_NOT_LOADED)
93 else if(f & VOXELFLAG_INEXISTENT)
98 u8 m = m_data[m_area.index(x,y,z)].d;
99 u8 pr = m_data[m_area.index(x,y,z)].pressure;
100 if(mode == VOXELPRINT_MATERIAL)
105 else if(mode == VOXELPRINT_WATERPRESSURE)
107 if(m == CONTENT_WATER)
113 else if(liquid_replaces_content(m))
131 void VoxelManipulator::addArea(VoxelArea area)
133 // Cancel if requested area has zero volume
134 if(area.getExtent() == v3s16(0,0,0))
137 // Cancel if m_area already contains the requested area
138 if(m_area.contains(area))
141 TimeTaker timer("addArea", &addarea_time);
143 // Calculate new area
145 // New area is the requested area if m_area has zero volume
146 if(m_area.getExtent() == v3s16(0,0,0))
150 // Else add requested area to m_area
154 new_area.addArea(area);
157 s32 new_size = new_area.getVolume();
159 /*dstream<<"adding area ";
161 dstream<<", old area ";
162 m_area.print(dstream);
163 dstream<<", new area ";
164 new_area.print(dstream);
165 dstream<<", new_size="<<new_size;
166 dstream<<std::endl;*/
168 // Allocate and clear new data
169 MapNode *new_data = new MapNode[new_size];
170 u8 *new_flags = new u8[new_size];
171 for(s32 i=0; i<new_size; i++)
173 new_flags[i] = VOXELFLAG_NOT_LOADED;
178 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
179 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
180 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
182 // If loaded, copy data and flags
183 if((m_flags[m_area.index(x,y,z)] & VOXELFLAG_NOT_LOADED) == false)
185 new_data[new_area.index(x,y,z)] = m_data[m_area.index(x,y,z)];
186 new_flags[new_area.index(x,y,z)] = m_flags[m_area.index(x,y,z)];
190 // Replace area, data and flags
194 MapNode *old_data = m_data;
195 u8 *old_flags = m_flags;
197 /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
198 <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
208 //dstream<<"addArea done"<<std::endl;
211 void VoxelManipulator::copyFrom(MapNode *src, VoxelArea src_area,
212 v3s16 from_pos, v3s16 to_pos, v3s16 size)
214 for(s16 z=0; z<size.Z; z++)
215 for(s16 y=0; y<size.Y; y++)
217 s32 i_src = src_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
218 s32 i_local = m_area.index(to_pos.X, to_pos.Y+y, to_pos.Z+z);
219 memcpy(&m_data[i_local], &src[i_src], size.X*sizeof(MapNode));
220 memset(&m_flags[i_local], 0, size.X);
225 void VoxelManipulator::clearFlag(u8 flags)
227 // 0-1ms on moderate area
228 TimeTaker timer("clearFlag", &clearflag_time);
230 v3s16 s = m_area.getExtent();
232 /*dstream<<"clearFlag clearing area of size "
233 <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
238 /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
239 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
240 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
242 u8 f = m_flags[m_area.index(x,y,z)];
243 m_flags[m_area.index(x,y,z)] &= ~flags;
244 if(m_flags[m_area.index(x,y,z)] != f)
248 s32 volume = m_area.getVolume();
249 for(s32 i=0; i<volume; i++)
251 m_flags[i] &= ~flags;
254 /*s32 volume = m_area.getVolume();
255 for(s32 i=0; i<volume; i++)
258 m_flags[i] &= ~flags;
263 dstream<<"clearFlag changed "<<count<<" flags out of "
264 <<volume<<" nodes"<<std::endl;*/
268 int VoxelManipulator::getWaterPressure(v3s16 p, s16 &highest_y, int recur_count)
270 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED2;
275 /*if(recur_count > 1000)
276 throw ProcessingLimitException
277 ("getWaterPressure recur_count limit reached");*/
279 if(recur_count > 10000)
286 v3s16(0,0,1), // back
287 v3s16(0,0,-1), // front
288 v3s16(1,0,0), // right
289 v3s16(-1,0,0), // left
290 v3s16(0,-1,0), // bottom
293 // Load neighboring nodes
294 emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 1);
299 v3s16 p2 = p + dirs[i];
300 u8 f = m_flags[m_area.index(p2)];
301 // Ignore inexistent or checked nodes
302 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED2))
304 MapNode &n = m_data[m_area.index(p2)];
305 // Ignore non-liquid nodes
306 if(content_liquid(n.d) == false)
311 // If at ocean surface
312 if(n.pressure == 1 && n.d == CONTENT_WATERSOURCE)
313 //if(n.pressure == 1) // Causes glitches but is fast
317 // Otherwise recurse more
320 pr = getWaterPressure(p2, highest_y, recur_count);
325 // If block is at top, pressure here is one higher
331 // If block is at bottom, pressure here is one lower
338 // Node is on the pressure route
339 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED4;
345 // Nothing useful found
349 void VoxelManipulator::spreadWaterPressure(v3s16 p, int pr,
350 VoxelArea request_area,
351 core::map<v3s16, u8> &active_nodes,
354 //if(recur_count > 10000)
355 /*throw ProcessingLimitException
356 ("spreadWaterPressure recur_count limit reached");*/
361 /*dstream<<"spreadWaterPressure: p=("
362 <<p.X<<","<<p.Y<<","<<p.Z<<")"
363 <<", oldpr="<<(int)m_data[m_area.index(p)].pressure
365 <<", recur_count="<<recur_count
367 request_area.print(dstream);
368 dstream<<std::endl;*/
370 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED3;
371 m_data[m_area.index(p)].pressure = pr;
375 v3s16(-1,0,0), // left
376 v3s16(1,0,0), // right
377 v3s16(0,0,-1), // front
378 v3s16(0,0,1), // back
379 v3s16(0,-1,0), // bottom
382 // Load neighboring nodes
383 emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 2);
388 v3s16 p2 = p + dirs[i];
390 u8 f = m_flags[m_area.index(p2)];
392 // Ignore inexistent and checked nodes
393 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
396 MapNode &n = m_data[m_area.index(p2)];
400 add to active_nodes if there is flow-causing pressure.
401 NOTE: Do not remove anything from there. We cannot know
402 here if some other neighbor of it causes flow.
404 if(liquid_replaces_content(n.d))
406 bool pressure_causes_flow = false;
407 // If empty block is at top
410 if(m_disable_water_climb)
413 //if(pr >= PRESERVE_WATER_VOLUME ? 3 : 2)
415 pressure_causes_flow = true;
417 // If block is at bottom
420 pressure_causes_flow = true;
422 // If block is at side
425 //if(pr >= PRESERVE_WATER_VOLUME ? 2 : 1)
427 pressure_causes_flow = true;
430 if(pressure_causes_flow)
432 active_nodes[p2] = 1;
438 // Ignore non-liquid nodes
439 if(content_liquid(n.d) == false)
443 // If block is at top, pressure there is lower
449 // If block is at bottom, pressure there is higher
456 /*if(m_disable_water_climb)
462 // Ignore if correct pressure is already set and is not on
464 // Thus, request_area can be used for updating as much
465 // pressure info in some area as possible to possibly
466 // make some calls to getWaterPressure unnecessary.
467 if(n.pressure == pr2 && request_area.contains(p2) == false)
470 spreadWaterPressure(p2, pr2, request_area, active_nodes, recur_count);
474 void VoxelManipulator::updateAreaWaterPressure(VoxelArea a,
475 core::map<v3s16, u8> &active_nodes,
476 bool checked3_is_clear)
478 TimeTaker timer("updateAreaWaterPressure", &updateareawaterpressure_time);
482 bool checked2_clear = false;
484 if(checked3_is_clear == false)
486 //clearFlag(VOXELFLAG_CHECKED3);
488 clearFlag(VOXELFLAG_CHECKED3 | VOXELFLAG_CHECKED2);
489 checked2_clear = true;
493 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
494 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
495 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
499 u8 f = m_flags[m_area.index(p)];
500 // Ignore inexistent or checked nodes
501 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
503 MapNode &n = m_data[m_area.index(p)];
504 // Ignore non-liquid nodes
505 if(content_liquid(n.d) == false)
508 if(checked2_clear == false)
510 clearFlag(VOXELFLAG_CHECKED2);
511 checked2_clear = true;
514 checked2_clear = false;
516 s16 highest_y = -32768;
522 // 0-1ms @ recur_count <= 100
523 //TimeTaker timer("getWaterPressure", g_irrlicht);
524 pr = getWaterPressure(p, highest_y, recur_count);
526 catch(ProcessingLimitException &e)
528 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
533 assert(highest_y != -32768);
535 pr = highest_y - p.Y + 1;
539 /*dstream<<"WARNING: Pressure at ("
540 <<p.X<<","<<p.Y<<","<<p.Z<<")"
542 //<<" and highest_y == -32768"
544 assert(highest_y != -32768);
551 //TimeTaker timer("spreadWaterPressure", g_irrlicht);
552 spreadWaterPressure(p, pr, a, active_nodes, 0);
554 catch(ProcessingLimitException &e)
556 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
561 bool VoxelManipulator::flowWater(v3s16 removed_pos,
562 core::map<v3s16, u8> &active_nodes,
563 int recursion_depth, bool debugprint,
568 v3s16(0,0,-1), // front
569 v3s16(0,0,1), // back
570 v3s16(-1,0,0), // left
571 v3s16(1,0,0), // right
572 v3s16(0,-1,0), // bottom
578 bool from_ocean = false;
580 // Randomize horizontal order
586 s16 s1 = (cs & 1) ? 1 : -1;
587 s16 s2 = (cs & 2) ? 1 : -1;
588 //dstream<<"s1="<<s1<<", s2="<<s2<<std::endl;
591 TimeTaker timer1("flowWater pre", &flowwater_pre_time);
593 // Load neighboring nodes
594 emerge(VoxelArea(removed_pos - v3s16(1,1,1), removed_pos + v3s16(1,1,1)), 4);
596 // Ignore incorrect removed_pos
598 u8 f = m_flags[m_area.index(removed_pos)];
599 // Ignore inexistent or checked node
600 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
602 MapNode &n = m_data[m_area.index(removed_pos)];
603 // Ignore nodes to which the water can't go
604 if(liquid_replaces_content(n.d) == false)
611 // Don't raise water from bottom
612 if(m_disable_water_climb && i == 5)
615 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
617 u8 f = m_flags[m_area.index(p)];
618 // Inexistent or checked nodes can't move
619 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
621 MapNode &n = m_data[m_area.index(p)];
622 // Only liquid nodes can move
623 if(content_liquid(n.d) == false)
625 // If block is at top, select it always
630 // If block is at bottom, select it if it has enough pressure
633 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 3 : 2)
638 // Else block is at some side. Select it if it has enough pressure
639 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 2 : 1)
646 // If there is nothing to move, return
651 Move water and bubble
654 u8 m = m_data[m_area.index(p)].d;
655 u8 f = m_flags[m_area.index(p)];
657 if(m == CONTENT_WATERSOURCE)
660 // Move air bubble if not taking water from ocean
661 if(from_ocean == false)
663 m_data[m_area.index(p)].d = m_data[m_area.index(removed_pos)].d;
664 m_flags[m_area.index(p)] = m_flags[m_area.index(removed_pos)];
668 This has to be done to copy the brightness of a light source
669 correctly. Otherwise unspreadLight will fuck up when water
670 has replaced a light source.
672 u8 light = m_data[m_area.index(removed_pos)].getLightBanksWithSource();
674 m_data[m_area.index(removed_pos)].d = m;
675 m_flags[m_area.index(removed_pos)] = f;
677 m_data[m_area.index(removed_pos)].setLightBanks(light);
679 // Mark removed_pos checked
680 m_flags[m_area.index(removed_pos)] |= VOXELFLAG_CHECKED;
682 // If block was dropped from surface, increase pressure
683 if(i == 0 && m_data[m_area.index(removed_pos)].pressure == 1)
685 m_data[m_area.index(removed_pos)].pressure = 2;
689 NOTE: This does not work as-is
690 if(m == CONTENT_WATERSOURCE)
692 // If block was raised to surface, increase pressure of
694 if(i == 5 && m_data[m_area.index(p)].pressure == 1)
696 m_data[m_area.index(p)].pressure = 2;
702 dstream<<"VoxelManipulator::flowWater(): Moved bubble:"<<std::endl;
703 print(dstream, VOXELPRINT_WATERPRESSURE);
708 a.addPoint(p - v3s16(1,1,1));
709 a.addPoint(p + v3s16(1,1,1));
710 a.addPoint(removed_pos - v3s16(1,1,1));
711 a.addPoint(removed_pos + v3s16(1,1,1));
712 updateAreaWaterPressure(a, active_nodes);
716 dstream<<"VoxelManipulator::flowWater(): Pressure updated:"<<std::endl;
717 print(dstream, VOXELPRINT_WATERPRESSURE);
723 dstream<<"VoxelManipulator::flowWater(): step done:"<<std::endl;
724 print(dstream, VOXELPRINT_WATERPRESSURE);
730 //if(PRESERVE_WATER_VOLUME)
731 if(from_ocean == false)
733 // Flow water to the newly created empty position
734 /*flowWater(p, active_nodes, recursion_depth,
735 debugprint, counter, counterlimit);*/
736 flowWater(p, active_nodes, recursion_depth,
737 debugprint, stoptime);
742 u32 timenow = getTimeMs();
743 // Well, it is a bit hard to guess because we don't know the
745 bool overflow = timenow < stoptime - 100000;
746 if(timenow >= stoptime || overflow)
748 dstream<<"flowWater: stoptime reached"<<std::endl;
749 throw ProcessingLimitException("flowWater stoptime reached");
755 // Try flowing water to empty positions around removed_pos.
756 // They are checked in reverse order compared to the previous loop.
757 for(s32 i=5; i>=0; i--)
759 // Don't try to flow to top
760 if(m_disable_water_climb && i == 0)
763 //v3s16 p = removed_pos + dirs[i];
764 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
766 u8 f = m_flags[m_area.index(p)];
767 // Water can't move to inexistent nodes
768 if(f & VOXELFLAG_INEXISTENT)
770 MapNode &n = m_data[m_area.index(p)];
771 // Water can only move to air
772 if(liquid_replaces_content(n.d) == false)
775 // Flow water to node
777 flowWater(p, active_nodes, recursion_depth,
778 debugprint, stoptime);
779 /*flowWater(p, active_nodes, recursion_depth,
780 debugprint, counter, counterlimit);*/
784 // Search again from all neighbors
792 void VoxelManipulator::flowWater(
793 core::map<v3s16, u8> &active_nodes,
794 int recursion_depth, bool debugprint,
799 emerge_load_time = 0;
801 updateareawaterpressure_time = 0;
802 flowwater_pre_time = 0;
804 if(active_nodes.size() == 0)
806 dstream<<"flowWater: no active nodes"<<std::endl;
810 //TimeTaker timer1("flowWater (active_nodes)", g_irrlicht);
812 //dstream<<"active_nodes.size() = "<<active_nodes.size()<<std::endl;
816 stoptime = getTimeMs() + timelimit;
818 // Count of handled active nodes
819 u32 handled_count = 0;
825 Take random one at first
827 This is randomized only at the first time so that all
828 subsequent nodes will be taken at roughly the same position
831 if(active_nodes.size() != 0)
832 k = (s32)myrand() % (s32)active_nodes.size();
834 // Flow water to active nodes
836 //for(s32 h=0; h<1; h++)
838 if(active_nodes.size() == 0)
844 clearFlag(VOXELFLAG_CHECKED);
846 //dstream<<"Selecting a new active_node"<<std::endl;
850 core::map<v3s16, u8>::Node
851 *n = active_nodes.getIterator().getNode();
856 core::map<v3s16, u8>::Iterator
857 i = active_nodes.getIterator().getNode();
858 for(s32 j=0; j<k; j++)
862 core::map<v3s16, u8>::Node *n = i.getNode();
864 // Decrement index if less than 0.
865 // This keeps us in existing indices always.
870 v3s16 p = n->getKey();
871 active_nodes.remove(p);
872 flowWater(p, active_nodes, recursion_depth,
873 debugprint, stoptime);
877 catch(ProcessingLimitException &e)
879 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
882 /*v3s16 e = m_area.getExtent();
883 s32 v = m_area.getVolume();
884 dstream<<"flowWater (active): "
885 <<"area ended up as "
886 <<e.X<<"x"<<e.Y<<"x"<<e.Z<<" = "<<v
887 <<", handled a_node count: "<<handled_count
888 <<", active_nodes.size() = "<<active_nodes.size()
890 dstream<<"addarea_time: "<<addarea_time
891 <<", emerge_time: "<<emerge_time
892 <<", emerge_load_time: "<<emerge_load_time
893 <<", clearflag_time: "<<clearflag_time
894 <<", flowwater_pre_time: "<<flowwater_pre_time
895 <<", updateareawaterpressure_time: "<<updateareawaterpressure_time