Implement propagateSunlight for VoxelManipulator

6 files changed, 337 insertions, 13 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 47ff5cbb0..2f963e24d 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -153,6 +153,7 @@ configure_file(
 )
 
 set(common_SRCS
+	voxelalgorithms.cpp
 	sound.cpp
 	quicktune.cpp
 	subgame.cpp
diff --git a/src/test.cpp b/src/test.cpp
index 1b9dfcb5d..ecced33c3 100644
--- a/src/test.cpp
+++ b/src/test.cpp
@@ -36,6 +36,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "settings.h"
 #include "log.h"
 #include "utility_string.h"
+#include "voxelalgorithms.h"
 
 /*
 	Asserts that the exception occurs
@@ -483,6 +484,118 @@ struct TestVoxelManipulator
 	}
 };
 
+struct TestVoxelAlgorithms
+{
+	void Run(INodeDefManager *ndef)
+	{
+		{
+			VoxelManipulator v;
+			for(u16 z=0; z<3; z++)
+			for(u16 y=0; y<3; y++)
+			for(u16 x=0; x<3; x++)
+			{
+				v3s16 p(x,y,z);
+				v.setNodeNoRef(p, MapNode(CONTENT_AIR));
+			}
+			VoxelArea a(v3s16(0,0,0), v3s16(2,2,2));
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, true, light_sources, ndef);
+				//v.print(dstream, ndef, VOXELPRINT_LIGHT_DAY);
+				assert(res.bottom_sunlight_valid == true);
+				assert(v.getNode(v3s16(1,1,1)).getLight(LIGHTBANK_DAY, ndef)
+						== LIGHT_SUN);
+			}
+			v.setNodeNoRef(v3s16(0,0,0), MapNode(CONTENT_STONE));
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, true, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+				assert(v.getNode(v3s16(1,1,1)).getLight(LIGHTBANK_DAY, ndef)
+						== LIGHT_SUN);
+			}
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, false, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+				assert(v.getNode(v3s16(2,0,2)).getLight(LIGHTBANK_DAY, ndef)
+						== 0);
+			}
+			v.setNodeNoRef(v3s16(1,3,2), MapNode(CONTENT_STONE));
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, true, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+				assert(v.getNode(v3s16(1,1,2)).getLight(LIGHTBANK_DAY, ndef)
+						== 0);
+			}
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, false, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+				assert(v.getNode(v3s16(1,0,2)).getLight(LIGHTBANK_DAY, ndef)
+						== 0);
+			}
+			{
+				MapNode n(CONTENT_AIR);
+				n.setLight(LIGHTBANK_DAY, 10, ndef);
+				v.setNodeNoRef(v3s16(1,-1,2), n);
+			}
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, true, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+			}
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, false, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+			}
+			{
+				MapNode n(CONTENT_AIR);
+				n.setLight(LIGHTBANK_DAY, LIGHT_SUN, ndef);
+				v.setNodeNoRef(v3s16(1,-1,2), n);
+			}
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, true, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == false);
+			}
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, false, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == false);
+			}
+			v.setNodeNoRef(v3s16(1,3,2), MapNode(CONTENT_IGNORE));
+			{
+				core::map<v3s16, bool> light_sources;
+				voxalgo::setLight(v, a, 0, ndef);
+				voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
+						v, a, true, light_sources, ndef);
+				assert(res.bottom_sunlight_valid == true);
+			}
+		}
+	}
+};
+
 /*
 	NOTE: These tests became non-working then NodeContainer was removed.
 	      These should be redone, utilizing some kind of a virtual
@@ -1279,6 +1392,7 @@ void run_tests()
 	TEST(TestSerialization);
 	TESTPARAMS(TestMapNode, ndef);
 	TESTPARAMS(TestVoxelManipulator, ndef);
+	TESTPARAMS(TestVoxelAlgorithms, ndef);
 	//TEST(TestMapBlock);
 	//TEST(TestMapSector);
 	if(INTERNET_SIMULATOR == false){
diff --git a/src/voxel.cpp b/src/voxel.cpp
index bd06be877..34faccb19 100644
--- a/src/voxel.cpp
+++ b/src/voxel.cpp
@@ -63,7 +63,7 @@ void VoxelManipulator::clear()
 	m_flags = NULL;
 }
 
-void VoxelManipulator::print(std::ostream &o, INodeDefManager *nodemgr,
+void VoxelManipulator::print(std::ostream &o, INodeDefManager *ndef,
 		VoxelPrintMode mode)
 {
 	v3s16 em = m_area.getExtent();
@@ -94,8 +94,9 @@ void VoxelManipulator::print(std::ostream &o, INodeDefManager *nodemgr,
 				else
 				{
 					c = 'X';
-					content_t m = m_data[m_area.index(x,y,z)].getContent();
-					u8 pr = m_data[m_area.index(x,y,z)].param2;
+					MapNode n = m_data[m_area.index(x,y,z)];
+					content_t m = n.getContent();
+					u8 pr = n.param2;
 					if(mode == VOXELPRINT_MATERIAL)
 					{
 						if(m <= 9)
@@ -103,7 +104,7 @@ void VoxelManipulator::print(std::ostream &o, INodeDefManager *nodemgr,
 					}
 					else if(mode == VOXELPRINT_WATERPRESSURE)
 					{
-						if(nodemgr->get(m).isLiquid())
+						if(ndef->get(m).isLiquid())
 						{
 							c = 'w';
 							if(pr <= 9)
@@ -118,6 +119,21 @@ void VoxelManipulator::print(std::ostream &o, INodeDefManager *nodemgr,
 							c = '#';
 						}
 					}
+					else if(mode == VOXELPRINT_LIGHT_DAY)
+					{
+						if(ndef->get(m).light_source != 0)
+							c = 'S';
+						else if(ndef->get(m).light_propagates == false)
+							c = 'X';
+						else
+						{
+							u8 light = n.getLight(LIGHTBANK_DAY, ndef);
+							if(light < 10)
+								c = '0' + light;
+							else
+								c = 'a' + (light-10);
+						}
+					}
 				}
 				o<<c;
 			}
diff --git a/src/voxel.h b/src/voxel.h
index 291b51e03..237366756 100644
--- a/src/voxel.h
+++ b/src/voxel.h
@@ -20,7 +20,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #ifndef VOXEL_HEADER
 #define VOXEL_HEADER
 
-#include "common_irrlicht.h"
+#include "irrlichttypes.h"
 #include <iostream>
 #include "debug.h"
 #include "mapnode.h"
@@ -333,6 +333,7 @@ enum VoxelPrintMode
 	VOXELPRINT_NOTHING,
 	VOXELPRINT_MATERIAL,
 	VOXELPRINT_WATERPRESSURE,
+	VOXELPRINT_LIGHT_DAY,
 };
 
 class VoxelManipulator /*: public NodeContainer*/
@@ -394,24 +395,37 @@ public:
 			return MapNode(CONTENT_IGNORE);
 		return m_data[m_area.index(p)];
 	}
+	// Stuff explodes if non-emerged area is touched with this.
+	// Emerge first, and check VOXELFLAG_INEXISTENT if appropriate.
+	MapNode & getNodeRefUnsafe(v3s16 p)
+	{
+		return m_data[m_area.index(p)];
+	}
+	u8 & getFlagsRefUnsafe(v3s16 p)
+	{
+		return m_flags[m_area.index(p)];
+	}
+	bool exists(v3s16 p)
+	{
+		return m_area.contains(p) &&
+			!(getFlagsRefUnsafe(p) & VOXELFLAG_INEXISTENT);
+	}
 	MapNode & getNodeRef(v3s16 p)
 	{
 		emerge(p);
-
-		if(m_flags[m_area.index(p)] & VOXELFLAG_INEXISTENT)
+		if(getFlagsRefUnsafe(p) & VOXELFLAG_INEXISTENT)
 		{
 			/*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
 					<<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
 					<<", index="<<m_area.index(p)
-					<<", flags="<<(int)m_flags[m_area.index(p)]
+					<<", flags="<<(int)getFlagsRefUnsafe(p)
 					<<" is inexistent"<<std::endl;*/
 			throw InvalidPositionException
 			("VoxelManipulator: getNode: inexistent");
 		}
-
-		return m_data[m_area.index(p)];
+		return getNodeRefUnsafe(p);
 	}
-	void setNode(v3s16 p, MapNode &n)
+	void setNode(v3s16 p, const MapNode &n)
 	{
 		emerge(p);
 		
@@ -419,7 +433,8 @@ public:
 		m_flags[m_area.index(p)] &= ~VOXELFLAG_INEXISTENT;
 		m_flags[m_area.index(p)] &= ~VOXELFLAG_NOT_LOADED;
 	}
-	void setNodeNoRef(v3s16 p, MapNode n)
+	// TODO: Should be removed and replaced with setNode
+	void setNodeNoRef(v3s16 p, const MapNode &n)
 	{
 		setNode(p, n);
 	}
@@ -498,7 +513,9 @@ public:
 	*/
 
 	void clearFlag(u8 flag);
-	
+
+	// TODO: Move to voxelalgorithms.h
+
 	void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 			core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr);
 	void unspreadLight(enum LightBank bank,
diff --git a/src/voxelalgorithms.cpp b/src/voxelalgorithms.cpp
new file mode 100644
index 000000000..ae609e96a
--- /dev/null
+++ b/src/voxelalgorithms.cpp
@@ -0,0 +1,126 @@
+/*
+Minetest-c55
+Copyright (C) 2010-2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#include "voxelalgorithms.h"
+#include "nodedef.h"
+
+namespace voxalgo
+{
+
+void setLight(VoxelManipulator &v, VoxelArea a, u8 light,
+		INodeDefManager *ndef)
+{
+	for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
+	for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
+	for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
+	{
+		v3s16 p(x,y,z);
+		MapNode &n = v.getNodeRefUnsafe(p);
+		n.setLight(LIGHTBANK_DAY, light, ndef);
+		n.setLight(LIGHTBANK_NIGHT, light, ndef);
+	}
+}
+
+SunlightPropagateResult propagateSunlight(VoxelManipulator &v, VoxelArea a,
+		bool inexistent_top_provides_sunlight,
+		core::map<v3s16, bool> & light_sources,
+		INodeDefManager *ndef)
+{
+	// Return values
+	bool bottom_sunlight_valid = true;
+
+	// The full area we shall touch extends one extra at top and bottom
+	VoxelArea required_a = a;
+	required_a.pad(v3s16(0,1,0));
+	// Make sure we have access to it
+	v.emerge(a);
+	
+	s16 max_y = a.MaxEdge.Y;
+	s16 min_y = a.MinEdge.Y;
+	
+	for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
+	for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
+	{
+		v3s16 p_overtop(x, max_y+1, z);
+		bool overtop_has_sunlight = false;
+		// If overtop node does not exist, trust heuristics
+		if(!v.exists(p_overtop))
+			overtop_has_sunlight = inexistent_top_provides_sunlight;
+		else if(v.getNodeRefUnsafe(p_overtop).getContent() == CONTENT_IGNORE)
+			overtop_has_sunlight = inexistent_top_provides_sunlight;
+		// Otherwise refer to it's light value
+		else
+			overtop_has_sunlight = (v.getNodeRefUnsafe(p_overtop).getLight(
+					LIGHTBANK_DAY, ndef) == LIGHT_SUN);
+
+		dstream<<"inexistent_top_provides_sunlight="
+				<<inexistent_top_provides_sunlight<<std::endl;
+		dstream<<"v.exists(p_overtop)="
+				<<v.exists(p_overtop)<<std::endl;
+
+		// Copy overtop's sunlight all over the place
+		u8 incoming_light = overtop_has_sunlight ? LIGHT_SUN : 0;
+		for(s32 y=max_y; y>=min_y; y--)
+		{
+			v3s16 p(x,y,z);
+			MapNode &n = v.getNodeRefUnsafe(p);
+			if(incoming_light == 0){
+				// Do nothing
+			} else if(incoming_light == LIGHT_SUN &&
+					ndef->get(n).sunlight_propagates){
+				// Do nothing
+			} else if(ndef->get(n).sunlight_propagates == false){
+				incoming_light = 0;
+			} else {
+				incoming_light = diminish_light(incoming_light);
+			}
+			u8 old_light = n.getLight(LIGHTBANK_DAY, ndef);
+
+			if(incoming_light > old_light)
+				n.setLight(LIGHTBANK_DAY, incoming_light, ndef);
+			
+			if(diminish_light(incoming_light) != 0)
+				light_sources.insert(p, true);
+		}
+		
+		// Check validity of sunlight at top of block below if it
+		// hasn't already been proven invalid
+		if(bottom_sunlight_valid)
+		{
+			bool sunlight_should_continue_down = (incoming_light == LIGHT_SUN);
+			v3s16 p_overbottom(x, min_y-1, z);
+			if(!v.exists(p_overbottom) ||
+					v.getNodeRefUnsafe(p_overbottom
+							).getContent() == CONTENT_IGNORE){
+				// Is not known, cannot compare
+			} else {
+				bool overbottom_has_sunlight = (v.getNodeRefUnsafe(p_overbottom
+						).getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN);
+				if(sunlight_should_continue_down != overbottom_has_sunlight){
+					bottom_sunlight_valid = false;
+				}
+			}
+		}
+	}
+
+	return SunlightPropagateResult(bottom_sunlight_valid);
+}
+
+} // namespace voxalgo
+
diff --git a/src/voxelalgorithms.h b/src/voxelalgorithms.h
new file mode 100644
index 000000000..3dea233dc
--- /dev/null
+++ b/src/voxelalgorithms.h
@@ -0,0 +1,50 @@
+/*
+Minetest-c55
+Copyright (C) 2010-2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#ifndef VOXELALGORITHMS_HEADER
+#define VOXELALGORITHMS_HEADER
+
+#include "voxel.h"
+
+namespace voxalgo
+{
+
+// TODO: Move unspreadLight and spreadLight from VoxelManipulator to here
+
+void setLight(VoxelManipulator &v, VoxelArea a, u8 light,
+		INodeDefManager *ndef);
+
+struct SunlightPropagateResult
+{
+	bool bottom_sunlight_valid;
+
+	SunlightPropagateResult(bool bottom_sunlight_valid_):
+		bottom_sunlight_valid(bottom_sunlight_valid_)
+	{}
+};
+
+SunlightPropagateResult propagateSunlight(VoxelManipulator &v, VoxelArea a,
+		bool inexistent_top_provides_sunlight,
+		core::map<v3s16, bool> & light_sources,
+		INodeDefManager *ndef);
+
+} // namespace voxalgo
+
+#endif
+