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():
46 VoxelManipulator::~VoxelManipulator()
55 void VoxelManipulator::clear()
57 // Reset area to volume=0
67 void VoxelManipulator::print(std::ostream &o, VoxelPrintMode mode)
69 v3s16 em = m_area.getExtent();
70 v3s16 of = m_area.MinEdge;
71 o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
72 <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
74 for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
76 if(em.X >= 3 && em.Y >= 3)
78 if (y==m_area.MinEdge.Y+2) o<<"^ ";
79 else if(y==m_area.MinEdge.Y+1) o<<"| ";
80 else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
84 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
86 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
88 u8 f = m_flags[m_area.index(x,y,z)];
90 if(f & VOXELFLAG_NOT_LOADED)
92 else if(f & VOXELFLAG_INEXISTENT)
97 u8 m = m_data[m_area.index(x,y,z)].d;
98 u8 pr = m_data[m_area.index(x,y,z)].pressure;
99 if(mode == VOXELPRINT_MATERIAL)
104 else if(mode == VOXELPRINT_WATERPRESSURE)
106 if(m == MATERIAL_WATER)
112 else if(m == MATERIAL_AIR)
130 void VoxelManipulator::addArea(VoxelArea area)
132 // Cancel if requested area has zero volume
133 if(area.getExtent() == v3s16(0,0,0))
136 // Cancel if m_area already contains the requested area
137 if(m_area.contains(area))
140 TimeTaker timer("addArea", g_device, &addarea_time);
142 // Calculate new area
144 // New area is the requested area if m_area has zero volume
145 if(m_area.getExtent() == v3s16(0,0,0))
149 // Else add requested area to m_area
153 new_area.addArea(area);
156 s32 new_size = new_area.getVolume();
158 /*dstream<<"adding area ";
160 dstream<<", old area ";
161 m_area.print(dstream);
162 dstream<<", new area ";
163 new_area.print(dstream);
164 dstream<<", new_size="<<new_size;
165 dstream<<std::endl;*/
167 // Allocate and clear new data
168 MapNode *new_data = new MapNode[new_size];
169 u8 *new_flags = new u8[new_size];
170 for(s32 i=0; i<new_size; i++)
172 new_flags[i] = VOXELFLAG_NOT_LOADED;
177 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
178 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
179 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
181 // If loaded, copy data and flags
182 if((m_flags[m_area.index(x,y,z)] & VOXELFLAG_NOT_LOADED) == false)
184 new_data[new_area.index(x,y,z)] = m_data[m_area.index(x,y,z)];
185 new_flags[new_area.index(x,y,z)] = m_flags[m_area.index(x,y,z)];
189 // Replace area, data and flags
193 MapNode *old_data = m_data;
194 u8 *old_flags = m_flags;
196 /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
197 <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
207 //dstream<<"addArea done"<<std::endl;
210 void VoxelManipulator::copyFrom(MapNode *src, VoxelArea src_area,
211 v3s16 from_pos, v3s16 to_pos, v3s16 size)
213 for(s16 z=0; z<size.Z; z++)
214 for(s16 y=0; y<size.Y; y++)
216 s32 i_src = src_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
217 s32 i_local = m_area.index(to_pos.X, to_pos.Y+y, to_pos.Z+z);
218 memcpy(&m_data[i_local], &src[i_src], size.X*sizeof(MapNode));
219 memset(&m_flags[i_local], 0, size.X);
223 void VoxelManipulator::interpolate(VoxelArea area)
225 VoxelArea emerge_area = area;
226 emerge_area.MinEdge -= v3s16(1,1,1);
227 emerge_area.MaxEdge += v3s16(1,1,1);
230 SharedBuffer<u8> buf(area.getVolume());
232 for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++)
233 for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++)
234 for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++)
248 //const v3s16 *dirs = g_26dirs;
252 u8 m = MATERIAL_IGNORE;
254 for(s16 i=0; i<8; i++)
255 //for(s16 i=0; i<26; i++)
257 v3s16 p2 = p + dirs[i];
259 u8 f = m_flags[m_area.index(p2)];
260 assert(!(f & VOXELFLAG_NOT_LOADED));
261 if(f & VOXELFLAG_INEXISTENT)
264 MapNode &n = m_data[m_area.index(p2)];
266 airness += (n.d == MATERIAL_AIR) ? 1 : -1;
269 if(m == MATERIAL_IGNORE && n.d != MATERIAL_AIR)
273 // 1 if air, 0 if not
274 buf[area.index(p)] = airness > -total/2 ? MATERIAL_AIR : m;
275 //buf[area.index(p)] = airness > -total ? MATERIAL_AIR : m;
276 //buf[area.index(p)] = airness >= -7 ? MATERIAL_AIR : m;
279 for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++)
280 for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++)
281 for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++)
284 m_data[m_area.index(p)].d = buf[area.index(p)];
289 void VoxelManipulator::clearFlag(u8 flags)
291 // 0-1ms on moderate area
292 TimeTaker timer("clearFlag", g_device, &clearflag_time);
294 v3s16 s = m_area.getExtent();
296 /*dstream<<"clearFlag clearing area of size "
297 <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
302 /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
303 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
304 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
306 u8 f = m_flags[m_area.index(x,y,z)];
307 m_flags[m_area.index(x,y,z)] &= ~flags;
308 if(m_flags[m_area.index(x,y,z)] != f)
312 s32 volume = m_area.getVolume();
313 for(s32 i=0; i<volume; i++)
315 m_flags[i] &= ~flags;
318 /*s32 volume = m_area.getVolume();
319 for(s32 i=0; i<volume; i++)
322 m_flags[i] &= ~flags;
327 dstream<<"clearFlag changed "<<count<<" flags out of "
328 <<volume<<" nodes"<<std::endl;*/
331 int VoxelManipulator::getWaterPressure(v3s16 p, s16 &highest_y, int recur_count)
333 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED2;
338 /*if(recur_count > 1000)
339 throw ProcessingLimitException
340 ("getWaterPressure recur_count limit reached");*/
342 if(recur_count > 10000)
349 v3s16(0,0,1), // back
350 v3s16(0,0,-1), // front
351 v3s16(1,0,0), // right
352 v3s16(-1,0,0), // left
353 v3s16(0,-1,0), // bottom
356 // Load neighboring nodes
357 emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 1);
362 v3s16 p2 = p + dirs[i];
363 u8 f = m_flags[m_area.index(p2)];
364 // Ignore inexistent or checked nodes
365 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED2))
367 MapNode &n = m_data[m_area.index(p2)];
368 // Ignore non-liquid nodes
369 if(material_liquid(n.d) == false)
374 // If at ocean surface
375 if(n.pressure == 1 && n.d == MATERIAL_OCEAN)
379 // Otherwise recurse more
382 pr = getWaterPressure(p2, highest_y, recur_count);
387 // If block is at top, pressure here is one higher
393 // If block is at bottom, pressure here is one lower
400 // Node is on the pressure route
401 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED4;
407 // Nothing useful found
411 void VoxelManipulator::spreadWaterPressure(v3s16 p, int pr,
412 VoxelArea request_area,
413 core::map<v3s16, u8> &active_nodes,
416 //if(recur_count > 10000)
417 /*throw ProcessingLimitException
418 ("spreadWaterPressure recur_count limit reached");*/
423 /*dstream<<"spreadWaterPressure: p=("
424 <<p.X<<","<<p.Y<<","<<p.Z<<")"
425 <<", oldpr="<<(int)m_data[m_area.index(p)].pressure
427 <<", recur_count="<<recur_count
429 request_area.print(dstream);
430 dstream<<std::endl;*/
432 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED3;
433 m_data[m_area.index(p)].pressure = pr;
437 v3s16(-1,0,0), // left
438 v3s16(1,0,0), // right
439 v3s16(0,0,-1), // front
440 v3s16(0,0,1), // back
441 v3s16(0,-1,0), // bottom
444 // Load neighboring nodes
445 emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 2);
450 v3s16 p2 = p + dirs[i];
452 u8 f = m_flags[m_area.index(p2)];
454 // Ignore inexistent and checked nodes
455 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
458 MapNode &n = m_data[m_area.index(p2)];
462 add to active_nodes if there is flow-causing pressure.
463 NOTE: Do not remove anything from there. We cannot know
464 here if some other neighbor of it causes flow.
466 if(n.d == MATERIAL_AIR)
468 bool pressure_causes_flow = false;
469 // If block is at top
472 //if(pr >= PRESERVE_WATER_VOLUME ? 3 : 2)
474 pressure_causes_flow = true;
476 // If block is at bottom
479 pressure_causes_flow = true;
481 // If block is at side
484 //if(pr >= PRESERVE_WATER_VOLUME ? 2 : 1)
486 pressure_causes_flow = true;
489 if(pressure_causes_flow)
491 active_nodes[p2] = 1;
497 // Ignore non-liquid nodes
498 if(material_liquid(n.d) == false)
502 // If block is at top, pressure there is lower
508 // If block is at bottom, pressure there is higher
515 // Ignore if correct pressure is already set and is not on
517 // Thus, request_area can be used for updating as much
518 // pressure info in some area as possible to possibly
519 // make some calls to getWaterPressure unnecessary.
520 if(n.pressure == pr2 && request_area.contains(p2) == false)
523 spreadWaterPressure(p2, pr2, request_area, active_nodes, recur_count);
527 void VoxelManipulator::updateAreaWaterPressure(VoxelArea a,
528 core::map<v3s16, u8> &active_nodes,
529 bool checked3_is_clear)
531 TimeTaker timer("updateAreaWaterPressure", g_device,
532 &updateareawaterpressure_time);
536 bool checked2_clear = false;
538 if(checked3_is_clear == false)
540 //clearFlag(VOXELFLAG_CHECKED3);
542 clearFlag(VOXELFLAG_CHECKED3 | VOXELFLAG_CHECKED2);
543 checked2_clear = true;
547 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
548 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
549 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
553 u8 f = m_flags[m_area.index(p)];
554 // Ignore inexistent or checked nodes
555 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
557 MapNode &n = m_data[m_area.index(p)];
558 // Ignore non-liquid nodes
559 if(material_liquid(n.d) == false)
562 if(checked2_clear == false)
564 clearFlag(VOXELFLAG_CHECKED2);
565 checked2_clear = true;
568 checked2_clear = false;
570 s16 highest_y = -32768;
576 // 0-1ms @ recur_count <= 100
577 //TimeTaker timer("getWaterPressure", g_device);
578 pr = getWaterPressure(p, highest_y, recur_count);
580 catch(ProcessingLimitException &e)
582 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
587 assert(highest_y != -32768);
589 pr = highest_y - p.Y + 1;
593 /*dstream<<"WARNING: Pressure at ("
594 <<p.X<<","<<p.Y<<","<<p.Z<<")"
596 //<<" and highest_y == -32768"
598 assert(highest_y != -32768);
605 //TimeTaker timer("spreadWaterPressure", g_device);
606 spreadWaterPressure(p, pr, a, active_nodes, 0);
608 catch(ProcessingLimitException &e)
610 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
615 bool VoxelManipulator::flowWater(v3s16 removed_pos,
616 core::map<v3s16, u8> &active_nodes,
617 int recursion_depth, bool debugprint,
622 v3s16(0,0,-1), // front
623 v3s16(0,0,1), // back
624 v3s16(-1,0,0), // left
625 v3s16(1,0,0), // right
626 v3s16(0,-1,0), // bottom
632 bool from_ocean = false;
634 // Randomize horizontal order
640 s16 s1 = (cs & 1) ? 1 : -1;
641 s16 s2 = (cs & 2) ? 1 : -1;
642 //dstream<<"s1="<<s1<<", s2="<<s2<<std::endl;
645 TimeTaker timer1("flowWater pre", g_device, &flowwater_pre_time);
647 // Load neighboring nodes
648 emerge(VoxelArea(removed_pos - v3s16(1,1,1), removed_pos + v3s16(1,1,1)), 4);
650 // Ignore incorrect removed_pos
652 u8 f = m_flags[m_area.index(removed_pos)];
653 // Ignore inexistent or checked node
654 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
656 MapNode &n = m_data[m_area.index(removed_pos)];
657 // Water can move only to air
658 if(n.d != MATERIAL_AIR)
665 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
667 u8 f = m_flags[m_area.index(p)];
668 // Inexistent or checked nodes can't move
669 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
671 MapNode &n = m_data[m_area.index(p)];
672 // Only liquid nodes can move
673 if(material_liquid(n.d) == false)
675 // If block is at top, select it always
680 // If block is at bottom, select it if it has enough pressure
683 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 3 : 2)
688 // Else block is at some side. Select it if it has enough pressure
689 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 2 : 1)
696 // If there is nothing to move, return
701 Move water and bubble
704 u8 m = m_data[m_area.index(p)].d;
705 u8 f = m_flags[m_area.index(p)];
707 if(m == MATERIAL_OCEAN)
710 // Move air bubble if not taking water from ocean
711 if(from_ocean == false)
713 m_data[m_area.index(p)].d = m_data[m_area.index(removed_pos)].d;
714 m_flags[m_area.index(p)] = m_flags[m_area.index(removed_pos)];
717 m_data[m_area.index(removed_pos)].d = m;
718 m_flags[m_area.index(removed_pos)] = f;
720 // Mark removed_pos checked
721 m_flags[m_area.index(removed_pos)] |= VOXELFLAG_CHECKED;
723 // If block was dropped from surface, increase pressure
724 if(i == 0 && m_data[m_area.index(removed_pos)].pressure == 1)
726 m_data[m_area.index(removed_pos)].pressure = 2;
730 NOTE: This does not work as-is
731 if(m == MATERIAL_OCEAN)
733 // If block was raised to surface, increase pressure of
735 if(i == 5 && m_data[m_area.index(p)].pressure == 1)
737 m_data[m_area.index(p)].pressure = 2;
743 dstream<<"VoxelManipulator::flowWater(): Moved bubble:"<<std::endl;
744 print(dstream, VOXELPRINT_WATERPRESSURE);
749 a.addPoint(p - v3s16(1,1,1));
750 a.addPoint(p + v3s16(1,1,1));
751 a.addPoint(removed_pos - v3s16(1,1,1));
752 a.addPoint(removed_pos + v3s16(1,1,1));
753 updateAreaWaterPressure(a, active_nodes);
757 dstream<<"VoxelManipulator::flowWater(): Pressure updated:"<<std::endl;
758 print(dstream, VOXELPRINT_WATERPRESSURE);
764 dstream<<"VoxelManipulator::flowWater(): step done:"<<std::endl;
765 print(dstream, VOXELPRINT_WATERPRESSURE);
771 //if(PRESERVE_WATER_VOLUME)
772 if(from_ocean == false)
774 // Flow water to the newly created empty position
775 /*flowWater(p, active_nodes, recursion_depth,
776 debugprint, counter, counterlimit);*/
777 flowWater(p, active_nodes, recursion_depth,
778 debugprint, stoptime);
781 if(stoptime != 0 && g_device != NULL)
783 u32 timenow = g_device->getTimer()->getRealTime();
784 if(timenow >= stoptime ||
785 (stoptime < 0x80000000 && timenow > 0x80000000))
787 dstream<<"flowWater: stoptime reached"<<std::endl;
788 throw ProcessingLimitException("flowWater stoptime reached");
794 // Try flowing water to empty positions around removed_pos.
795 // They are checked in reverse order compared to the previous loop.
796 for(s32 i=5; i>=0; i--)
798 //v3s16 p = removed_pos + dirs[i];
799 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
801 u8 f = m_flags[m_area.index(p)];
802 // Water can't move to inexistent nodes
803 if(f & VOXELFLAG_INEXISTENT)
805 MapNode &n = m_data[m_area.index(p)];
806 // Water can only move to air
807 if(n.d != MATERIAL_AIR)
810 // Flow water to node
812 flowWater(p, active_nodes, recursion_depth,
813 debugprint, stoptime);
814 /*flowWater(p, active_nodes, recursion_depth,
815 debugprint, counter, counterlimit);*/
819 // Search again from all neighbors
827 void VoxelManipulator::flowWater(
828 core::map<v3s16, u8> &active_nodes,
829 int recursion_depth, bool debugprint,
834 emerge_load_time = 0;
836 updateareawaterpressure_time = 0;
837 flowwater_pre_time = 0;
839 if(active_nodes.size() == 0)
841 dstream<<"flowWater: no active nodes"<<std::endl;
845 TimeTaker timer1("flowWater (active_nodes)", g_device);
847 dstream<<"active_nodes.size() = "<<active_nodes.size()<<std::endl;
854 stoptime = g_device->getTimer()->getRealTime() + timelimit;
857 // Count of handled active nodes
858 u32 handled_count = 0;
864 Take random one at first
866 This is randomized only at the first time so that all
867 subsequent nodes will be taken at roughly the same position
870 if(active_nodes.size() != 0)
871 k = (s32)rand() % (s32)active_nodes.size();
873 // Flow water to active nodes
875 //for(s32 h=0; h<1; h++)
877 if(active_nodes.size() == 0)
883 clearFlag(VOXELFLAG_CHECKED);
885 //dstream<<"Selecting a new active_node"<<std::endl;
889 core::map<v3s16, u8>::Node
890 *n = active_nodes.getIterator().getNode();
895 core::map<v3s16, u8>::Iterator
896 i = active_nodes.getIterator().getNode();
897 for(s32 j=0; j<k; j++)
901 core::map<v3s16, u8>::Node *n = i.getNode();
903 // Decrement index if less than 0.
904 // This keeps us in existing indices always.
909 v3s16 p = n->getKey();
910 active_nodes.remove(p);
911 flowWater(p, active_nodes, recursion_depth,
912 debugprint, stoptime);
916 catch(ProcessingLimitException &e)
918 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
921 v3s16 e = m_area.getExtent();
922 s32 v = m_area.getVolume();
923 //dstream<<"flowWater (active): moved "<<counter<<" nodes, "
924 dstream<<"flowWater (active): "
925 <<"area ended up as "
926 <<e.X<<"x"<<e.Y<<"x"<<e.Z<<" = "<<v
927 <<", handled a_node count: "<<handled_count
928 <<", active_nodes.size() = "<<active_nodes.size()
931 dstream<<"addarea_time: "<<addarea_time
932 <<", emerge_time: "<<emerge_time
933 <<", emerge_load_time: "<<emerge_load_time
934 <<", clearflag_time: "<<clearflag_time
935 <<", flowwater_pre_time: "<<flowwater_pre_time
936 <<", updateareawaterpressure_time: "<<updateareawaterpressure_time