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);
224 void VoxelManipulator::interpolate(VoxelArea area)
226 VoxelArea emerge_area = area;
227 emerge_area.MinEdge -= v3s16(1,1,1);
228 emerge_area.MaxEdge += v3s16(1,1,1);
231 SharedBuffer<u8> buf(area.getVolume());
233 for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++)
234 for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++)
235 for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++)
249 //const v3s16 *dirs = g_26dirs;
253 u8 m = CONTENT_IGNORE;
255 for(s16 i=0; i<8; i++)
256 //for(s16 i=0; i<26; i++)
258 v3s16 p2 = p + dirs[i];
260 u8 f = m_flags[m_area.index(p2)];
261 assert(!(f & VOXELFLAG_NOT_LOADED));
262 if(f & VOXELFLAG_INEXISTENT)
265 MapNode &n = m_data[m_area.index(p2)];
267 airness += (n.d == CONTENT_AIR) ? 1 : -1;
270 if(m == CONTENT_IGNORE && n.d != CONTENT_AIR)
274 // 1 if air, 0 if not
275 buf[area.index(p)] = airness > -total/2 ? CONTENT_AIR : m;
276 //buf[area.index(p)] = airness > -total ? CONTENT_AIR : m;
277 //buf[area.index(p)] = airness >= -7 ? CONTENT_AIR : m;
280 for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++)
281 for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++)
282 for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++)
285 m_data[m_area.index(p)].d = buf[area.index(p)];
290 void VoxelManipulator::clearFlag(u8 flags)
292 // 0-1ms on moderate area
293 TimeTaker timer("clearFlag", &clearflag_time);
295 v3s16 s = m_area.getExtent();
297 /*dstream<<"clearFlag clearing area of size "
298 <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
303 /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
304 for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
305 for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
307 u8 f = m_flags[m_area.index(x,y,z)];
308 m_flags[m_area.index(x,y,z)] &= ~flags;
309 if(m_flags[m_area.index(x,y,z)] != f)
313 s32 volume = m_area.getVolume();
314 for(s32 i=0; i<volume; i++)
316 m_flags[i] &= ~flags;
319 /*s32 volume = m_area.getVolume();
320 for(s32 i=0; i<volume; i++)
323 m_flags[i] &= ~flags;
328 dstream<<"clearFlag changed "<<count<<" flags out of "
329 <<volume<<" nodes"<<std::endl;*/
332 int VoxelManipulator::getWaterPressure(v3s16 p, s16 &highest_y, int recur_count)
334 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED2;
339 /*if(recur_count > 1000)
340 throw ProcessingLimitException
341 ("getWaterPressure recur_count limit reached");*/
343 if(recur_count > 10000)
350 v3s16(0,0,1), // back
351 v3s16(0,0,-1), // front
352 v3s16(1,0,0), // right
353 v3s16(-1,0,0), // left
354 v3s16(0,-1,0), // bottom
357 // Load neighboring nodes
358 emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 1);
363 v3s16 p2 = p + dirs[i];
364 u8 f = m_flags[m_area.index(p2)];
365 // Ignore inexistent or checked nodes
366 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED2))
368 MapNode &n = m_data[m_area.index(p2)];
369 // Ignore non-liquid nodes
370 if(content_liquid(n.d) == false)
375 // If at ocean surface
376 if(n.pressure == 1 && n.d == CONTENT_OCEAN)
377 //if(n.pressure == 1) // Causes glitches but is fast
381 // Otherwise recurse more
384 pr = getWaterPressure(p2, highest_y, recur_count);
389 // If block is at top, pressure here is one higher
395 // If block is at bottom, pressure here is one lower
402 // Node is on the pressure route
403 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED4;
409 // Nothing useful found
413 void VoxelManipulator::spreadWaterPressure(v3s16 p, int pr,
414 VoxelArea request_area,
415 core::map<v3s16, u8> &active_nodes,
418 //if(recur_count > 10000)
419 /*throw ProcessingLimitException
420 ("spreadWaterPressure recur_count limit reached");*/
425 /*dstream<<"spreadWaterPressure: p=("
426 <<p.X<<","<<p.Y<<","<<p.Z<<")"
427 <<", oldpr="<<(int)m_data[m_area.index(p)].pressure
429 <<", recur_count="<<recur_count
431 request_area.print(dstream);
432 dstream<<std::endl;*/
434 m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED3;
435 m_data[m_area.index(p)].pressure = pr;
439 v3s16(-1,0,0), // left
440 v3s16(1,0,0), // right
441 v3s16(0,0,-1), // front
442 v3s16(0,0,1), // back
443 v3s16(0,-1,0), // bottom
446 // Load neighboring nodes
447 emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)), 2);
452 v3s16 p2 = p + dirs[i];
454 u8 f = m_flags[m_area.index(p2)];
456 // Ignore inexistent and checked nodes
457 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
460 MapNode &n = m_data[m_area.index(p2)];
464 add to active_nodes if there is flow-causing pressure.
465 NOTE: Do not remove anything from there. We cannot know
466 here if some other neighbor of it causes flow.
468 if(liquid_replaces_content(n.d))
470 bool pressure_causes_flow = false;
471 // If empty block is at top
474 if(m_disable_water_climb)
477 //if(pr >= PRESERVE_WATER_VOLUME ? 3 : 2)
479 pressure_causes_flow = true;
481 // If block is at bottom
484 pressure_causes_flow = true;
486 // If block is at side
489 //if(pr >= PRESERVE_WATER_VOLUME ? 2 : 1)
491 pressure_causes_flow = true;
494 if(pressure_causes_flow)
496 active_nodes[p2] = 1;
502 // Ignore non-liquid nodes
503 if(content_liquid(n.d) == false)
507 // If block is at top, pressure there is lower
513 // If block is at bottom, pressure there is higher
520 /*if(m_disable_water_climb)
526 // Ignore if correct pressure is already set and is not on
528 // Thus, request_area can be used for updating as much
529 // pressure info in some area as possible to possibly
530 // make some calls to getWaterPressure unnecessary.
531 if(n.pressure == pr2 && request_area.contains(p2) == false)
534 spreadWaterPressure(p2, pr2, request_area, active_nodes, recur_count);
538 void VoxelManipulator::updateAreaWaterPressure(VoxelArea a,
539 core::map<v3s16, u8> &active_nodes,
540 bool checked3_is_clear)
542 TimeTaker timer("updateAreaWaterPressure", &updateareawaterpressure_time);
546 bool checked2_clear = false;
548 if(checked3_is_clear == false)
550 //clearFlag(VOXELFLAG_CHECKED3);
552 clearFlag(VOXELFLAG_CHECKED3 | VOXELFLAG_CHECKED2);
553 checked2_clear = true;
557 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
558 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
559 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
563 u8 f = m_flags[m_area.index(p)];
564 // Ignore inexistent or checked nodes
565 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED3))
567 MapNode &n = m_data[m_area.index(p)];
568 // Ignore non-liquid nodes
569 if(content_liquid(n.d) == false)
572 if(checked2_clear == false)
574 clearFlag(VOXELFLAG_CHECKED2);
575 checked2_clear = true;
578 checked2_clear = false;
580 s16 highest_y = -32768;
586 // 0-1ms @ recur_count <= 100
587 //TimeTaker timer("getWaterPressure", g_irrlicht);
588 pr = getWaterPressure(p, highest_y, recur_count);
590 catch(ProcessingLimitException &e)
592 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
597 assert(highest_y != -32768);
599 pr = highest_y - p.Y + 1;
603 /*dstream<<"WARNING: Pressure at ("
604 <<p.X<<","<<p.Y<<","<<p.Z<<")"
606 //<<" and highest_y == -32768"
608 assert(highest_y != -32768);
615 //TimeTaker timer("spreadWaterPressure", g_irrlicht);
616 spreadWaterPressure(p, pr, a, active_nodes, 0);
618 catch(ProcessingLimitException &e)
620 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
625 bool VoxelManipulator::flowWater(v3s16 removed_pos,
626 core::map<v3s16, u8> &active_nodes,
627 int recursion_depth, bool debugprint,
632 v3s16(0,0,-1), // front
633 v3s16(0,0,1), // back
634 v3s16(-1,0,0), // left
635 v3s16(1,0,0), // right
636 v3s16(0,-1,0), // bottom
642 bool from_ocean = false;
644 // Randomize horizontal order
650 s16 s1 = (cs & 1) ? 1 : -1;
651 s16 s2 = (cs & 2) ? 1 : -1;
652 //dstream<<"s1="<<s1<<", s2="<<s2<<std::endl;
655 TimeTaker timer1("flowWater pre", &flowwater_pre_time);
657 // Load neighboring nodes
658 emerge(VoxelArea(removed_pos - v3s16(1,1,1), removed_pos + v3s16(1,1,1)), 4);
660 // Ignore incorrect removed_pos
662 u8 f = m_flags[m_area.index(removed_pos)];
663 // Ignore inexistent or checked node
664 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
666 MapNode &n = m_data[m_area.index(removed_pos)];
667 // Ignore nodes to which the water can't go
668 if(liquid_replaces_content(n.d) == false)
675 // Don't raise water from bottom
676 if(m_disable_water_climb && i == 5)
679 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
681 u8 f = m_flags[m_area.index(p)];
682 // Inexistent or checked nodes can't move
683 if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED))
685 MapNode &n = m_data[m_area.index(p)];
686 // Only liquid nodes can move
687 if(content_liquid(n.d) == false)
689 // If block is at top, select it always
694 // If block is at bottom, select it if it has enough pressure
697 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 3 : 2)
702 // Else block is at some side. Select it if it has enough pressure
703 //if(n.pressure >= PRESERVE_WATER_VOLUME ? 2 : 1)
710 // If there is nothing to move, return
715 Move water and bubble
718 u8 m = m_data[m_area.index(p)].d;
719 u8 f = m_flags[m_area.index(p)];
721 if(m == CONTENT_OCEAN)
724 // Move air bubble if not taking water from ocean
725 if(from_ocean == false)
727 m_data[m_area.index(p)].d = m_data[m_area.index(removed_pos)].d;
728 m_flags[m_area.index(p)] = m_flags[m_area.index(removed_pos)];
732 This has to be done to copy the brightness of a light source
733 correctly. Otherwise unspreadLight will fuck up when water
734 has replaced a light source.
736 u8 light = m_data[m_area.index(removed_pos)].getLightBanksWithSource();
738 m_data[m_area.index(removed_pos)].d = m;
739 m_flags[m_area.index(removed_pos)] = f;
741 m_data[m_area.index(removed_pos)].setLightBanks(light);
743 // Mark removed_pos checked
744 m_flags[m_area.index(removed_pos)] |= VOXELFLAG_CHECKED;
746 // If block was dropped from surface, increase pressure
747 if(i == 0 && m_data[m_area.index(removed_pos)].pressure == 1)
749 m_data[m_area.index(removed_pos)].pressure = 2;
753 NOTE: This does not work as-is
754 if(m == CONTENT_OCEAN)
756 // If block was raised to surface, increase pressure of
758 if(i == 5 && m_data[m_area.index(p)].pressure == 1)
760 m_data[m_area.index(p)].pressure = 2;
766 dstream<<"VoxelManipulator::flowWater(): Moved bubble:"<<std::endl;
767 print(dstream, VOXELPRINT_WATERPRESSURE);
772 a.addPoint(p - v3s16(1,1,1));
773 a.addPoint(p + v3s16(1,1,1));
774 a.addPoint(removed_pos - v3s16(1,1,1));
775 a.addPoint(removed_pos + v3s16(1,1,1));
776 updateAreaWaterPressure(a, active_nodes);
780 dstream<<"VoxelManipulator::flowWater(): Pressure updated:"<<std::endl;
781 print(dstream, VOXELPRINT_WATERPRESSURE);
787 dstream<<"VoxelManipulator::flowWater(): step done:"<<std::endl;
788 print(dstream, VOXELPRINT_WATERPRESSURE);
794 //if(PRESERVE_WATER_VOLUME)
795 if(from_ocean == false)
797 // Flow water to the newly created empty position
798 /*flowWater(p, active_nodes, recursion_depth,
799 debugprint, counter, counterlimit);*/
800 flowWater(p, active_nodes, recursion_depth,
801 debugprint, stoptime);
806 u32 timenow = getTimeMs();
807 // Well, it is a bit hard to guess because we don't know the
809 bool overflow = timenow < stoptime - 100000;
810 if(timenow >= stoptime || overflow)
812 dstream<<"flowWater: stoptime reached"<<std::endl;
813 throw ProcessingLimitException("flowWater stoptime reached");
819 // Try flowing water to empty positions around removed_pos.
820 // They are checked in reverse order compared to the previous loop.
821 for(s32 i=5; i>=0; i--)
823 // Don't try to flow to top
824 if(m_disable_water_climb && i == 0)
827 //v3s16 p = removed_pos + dirs[i];
828 p = removed_pos + v3s16(s1*dirs[i].X, dirs[i].Y, s2*dirs[i].Z);
830 u8 f = m_flags[m_area.index(p)];
831 // Water can't move to inexistent nodes
832 if(f & VOXELFLAG_INEXISTENT)
834 MapNode &n = m_data[m_area.index(p)];
835 // Water can only move to air
836 if(liquid_replaces_content(n.d) == false)
839 // Flow water to node
841 flowWater(p, active_nodes, recursion_depth,
842 debugprint, stoptime);
843 /*flowWater(p, active_nodes, recursion_depth,
844 debugprint, counter, counterlimit);*/
848 // Search again from all neighbors
856 void VoxelManipulator::flowWater(
857 core::map<v3s16, u8> &active_nodes,
858 int recursion_depth, bool debugprint,
863 emerge_load_time = 0;
865 updateareawaterpressure_time = 0;
866 flowwater_pre_time = 0;
868 if(active_nodes.size() == 0)
870 dstream<<"flowWater: no active nodes"<<std::endl;
874 //TimeTaker timer1("flowWater (active_nodes)", g_irrlicht);
876 //dstream<<"active_nodes.size() = "<<active_nodes.size()<<std::endl;
880 stoptime = getTimeMs() + timelimit;
882 // Count of handled active nodes
883 u32 handled_count = 0;
889 Take random one at first
891 This is randomized only at the first time so that all
892 subsequent nodes will be taken at roughly the same position
895 if(active_nodes.size() != 0)
896 k = (s32)myrand() % (s32)active_nodes.size();
898 // Flow water to active nodes
900 //for(s32 h=0; h<1; h++)
902 if(active_nodes.size() == 0)
908 clearFlag(VOXELFLAG_CHECKED);
910 //dstream<<"Selecting a new active_node"<<std::endl;
914 core::map<v3s16, u8>::Node
915 *n = active_nodes.getIterator().getNode();
920 core::map<v3s16, u8>::Iterator
921 i = active_nodes.getIterator().getNode();
922 for(s32 j=0; j<k; j++)
926 core::map<v3s16, u8>::Node *n = i.getNode();
928 // Decrement index if less than 0.
929 // This keeps us in existing indices always.
934 v3s16 p = n->getKey();
935 active_nodes.remove(p);
936 flowWater(p, active_nodes, recursion_depth,
937 debugprint, stoptime);
941 catch(ProcessingLimitException &e)
943 //dstream<<"getWaterPressure ProcessingLimitException"<<std::endl;
946 /*v3s16 e = m_area.getExtent();
947 s32 v = m_area.getVolume();
948 dstream<<"flowWater (active): "
949 <<"area ended up as "
950 <<e.X<<"x"<<e.Y<<"x"<<e.Z<<" = "<<v
951 <<", handled a_node count: "<<handled_count
952 <<", active_nodes.size() = "<<active_nodes.size()
954 dstream<<"addarea_time: "<<addarea_time
955 <<", emerge_time: "<<emerge_time
956 <<", emerge_load_time: "<<emerge_load_time
957 <<", clearflag_time: "<<clearflag_time
958 <<", flowwater_pre_time: "<<flowwater_pre_time
959 <<", updateareawaterpressure_time: "<<updateareawaterpressure_time