Improved lighting

This commit rewrites the procedure that is responsible for light
updating.

this commit
-provides iterative solutions for unlighting and light spreading
-introduces a new priority queue-like container for the iteration
-creates per-node MapBlock caching to reduce retrieving MapBlocks from
the map
-calculates with map block positions and in-block relative node
coordinates
-skips light updating if it is not necessary since the node's new light
will be the same as its old light was

6 files changed, 643 insertions, 443 deletions

diff --git a/src/map.cpp b/src/map.cpp
index 38f0fa37c..1694582db 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -22,6 +22,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "mapblock.h"
 #include "filesys.h"
 #include "voxel.h"
+#include "voxelalgorithms.h"
 #include "porting.h"
 #include "serialization.h"
 #include "nodemetadata.h"
@@ -234,7 +235,6 @@ void Map::setNode(v3s16 p, MapNode & n)
 	block->setNodeNoCheck(relpos, n);
 }
 
-
 /*
 	Goes recursively through the neighbours of the node.
 
@@ -414,20 +414,6 @@ void Map::unspreadLight(enum LightBank bank,
 }
 
 /*
-	A single-node wrapper of the above
-*/
-void Map::unLightNeighbors(enum LightBank bank,
-		v3s16 pos, u8 lightwas,
-		std::set<v3s16> & light_sources,
-		std::map<v3s16, MapBlock*>  & modified_blocks)
-{
-	std::map<v3s16, u8> from_nodes;
-	from_nodes[pos] = lightwas;
-
-	unspreadLight(bank, from_nodes, light_sources, modified_blocks);
-}
-
-/*
 	Lights neighbors of from_nodes, collects all them and then
 	goes on recursively.
 */
@@ -568,108 +554,6 @@ void Map::spreadLight(enum LightBank bank,
 		spreadLight(bank, lighted_nodes, modified_blocks);
 }
 
-/*
-	A single-node source variation of the above.
-*/
-void Map::lightNeighbors(enum LightBank bank,
-		v3s16 pos,
-		std::map<v3s16, MapBlock*> & modified_blocks)
-{
-	std::set<v3s16> from_nodes;
-	from_nodes.insert(pos);
-	spreadLight(bank, from_nodes, modified_blocks);
-}
-
-v3s16 Map::getBrightestNeighbour(enum LightBank bank, v3s16 p)
-{
-	INodeDefManager *nodemgr = m_gamedef->ndef();
-
-	v3s16 dirs[6] = {
-		v3s16(0,0,1), // back
-		v3s16(0,1,0), // top
-		v3s16(1,0,0), // right
-		v3s16(0,0,-1), // front
-		v3s16(0,-1,0), // bottom
-		v3s16(-1,0,0), // left
-	};
-
-	u8 brightest_light = 0;
-	v3s16 brightest_pos(0,0,0);
-	bool found_something = false;
-
-	// Loop through 6 neighbors
-	for(u16 i=0; i<6; i++){
-		// Get the position of the neighbor node
-		v3s16 n2pos = p + dirs[i];
-		MapNode n2;
-		bool is_valid_position;
-		n2 = getNodeNoEx(n2pos, &is_valid_position);
-		if (!is_valid_position)
-			continue;
-
-		if(n2.getLight(bank, nodemgr) > brightest_light || found_something == false){
-			brightest_light = n2.getLight(bank, nodemgr);
-			brightest_pos = n2pos;
-			found_something = true;
-		}
-	}
-
-	if(found_something == false)
-		throw InvalidPositionException();
-
-	return brightest_pos;
-}
-
-/*
-	Propagates sunlight down from a node.
-	Starting point gets sunlight.
-
-	Returns the lowest y value of where the sunlight went.
-
-	Mud is turned into grass in where the sunlight stops.
-*/
-s16 Map::propagateSunlight(v3s16 start,
-		std::map<v3s16, MapBlock*> & modified_blocks)
-{
-	INodeDefManager *nodemgr = m_gamedef->ndef();
-
-	s16 y = start.Y;
-	for(; ; y--)
-	{
-		v3s16 pos(start.X, y, start.Z);
-
-		v3s16 blockpos = getNodeBlockPos(pos);
-		MapBlock *block;
-		try{
-			block = getBlockNoCreate(blockpos);
-		}
-		catch(InvalidPositionException &e)
-		{
-			break;
-		}
-
-		v3s16 relpos = pos - blockpos*MAP_BLOCKSIZE;
-		bool is_valid_position;
-		MapNode n = block->getNode(relpos, &is_valid_position);
-		if (!is_valid_position)
-			break;
-
-		if(nodemgr->get(n).sunlight_propagates)
-		{
-			n.setLight(LIGHTBANK_DAY, LIGHT_SUN, nodemgr);
-			block->setNode(relpos, n);
-
-			modified_blocks[blockpos] = block;
-		}
-		else
-		{
-			// Sunlight goes no further
-			break;
-		}
-	}
-	return y + 1;
-}
-
 void Map::updateLighting(enum LightBank bank,
 		std::map<v3s16, MapBlock*> & a_blocks,
 		std::map<v3s16, MapBlock*> & modified_blocks)
@@ -922,150 +806,29 @@ void Map::updateLighting(std::map<v3s16, MapBlock*> & a_blocks,
 	}
 }
 
-/*
-*/
 void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 		std::map<v3s16, MapBlock*> &modified_blocks,
 		bool remove_metadata)
 {
 	INodeDefManager *ndef = m_gamedef->ndef();
 
-	/*PrintInfo(m_dout);
-	m_dout<<"Map::addNodeAndUpdate(): p=("
-			<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;*/
-
-	/*
-		From this node to nodes underneath:
-		If lighting is sunlight (1.0), unlight neighbours and
-		set lighting to 0.
-		Else discontinue.
-	*/
-
-	v3s16 toppos = p + v3s16(0,1,0);
-	//v3s16 bottompos = p + v3s16(0,-1,0);
-
-	bool node_under_sunlight = true;
-	std::set<v3s16> light_sources;
-
-	/*
-		Collect old node for rollback
-	*/
+	// Collect old node for rollback
 	RollbackNode rollback_oldnode(this, p, m_gamedef);
 
-	/*
-		If there is a node at top and it doesn't have sunlight,
-		there has not been any sunlight going down.
-
-		Otherwise there probably is.
-	*/
-
-	bool is_valid_position;
-	MapNode topnode = getNodeNoEx(toppos, &is_valid_position);
-
-	if(is_valid_position && topnode.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN)
-		node_under_sunlight = false;
-
-	/*
-		Remove all light that has come out of this node
-	*/
-
-	enum LightBank banks[] =
-	{
-		LIGHTBANK_DAY,
-		LIGHTBANK_NIGHT
-	};
-	for(s32 i=0; i<2; i++)
-	{
-		enum LightBank bank = banks[i];
+	// This is needed for updating the lighting
+	MapNode oldnode = getNodeNoEx(p);
 
-		u8 lightwas = getNodeNoEx(p).getLight(bank, ndef);
-
-		// Add the block of the added node to modified_blocks
-		v3s16 blockpos = getNodeBlockPos(p);
-		MapBlock * block = getBlockNoCreate(blockpos);
-		assert(block != NULL);
-		modified_blocks[blockpos] = block;
-
-		assert(isValidPosition(p));
-
-		// Unlight neighbours of node.
-		// This means setting light of all consequent dimmer nodes
-		// to 0.
-		// This also collects the nodes at the border which will spread
-		// light again into this.
-		unLightNeighbors(bank, p, lightwas, light_sources, modified_blocks);
-
-		n.setLight(bank, 0, ndef);
-	}
-
-	/*
-		If node lets sunlight through and is under sunlight, it has
-		sunlight too.
-	*/
-	if(node_under_sunlight && ndef->get(n).sunlight_propagates)
-	{
-		n.setLight(LIGHTBANK_DAY, LIGHT_SUN, ndef);
-	}
-
-	/*
-		Remove node metadata
-	*/
+	// Remove node metadata
 	if (remove_metadata) {
 		removeNodeMetadata(p);
 	}
 
-	/*
-		Set the node on the map
-	*/
-
+	// Set the node on the map
 	setNode(p, n);
 
-	/*
-		If node is under sunlight and doesn't let sunlight through,
-		take all sunlighted nodes under it and clear light from them
-		and from where the light has been spread.
-		TODO: This could be optimized by mass-unlighting instead
-			  of looping
-	*/
-	if(node_under_sunlight && !ndef->get(n).sunlight_propagates)
-	{
-		s16 y = p.Y - 1;
-		for(;; y--){
-			//m_dout<<"y="<<y<<std::endl;
-			v3s16 n2pos(p.X, y, p.Z);
-
-			MapNode n2;
-
-			n2 = getNodeNoEx(n2pos, &is_valid_position);
-			if (!is_valid_position)
-				break;
-
-			if(n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN)
-			{
-				unLightNeighbors(LIGHTBANK_DAY,
-						n2pos, n2.getLight(LIGHTBANK_DAY, ndef),
-						light_sources, modified_blocks);
-				n2.setLight(LIGHTBANK_DAY, 0, ndef);
-				setNode(n2pos, n2);
-			}
-			else
-				break;
-		}
-	}
+	// Update lighting
+	voxalgo::update_lighting_node(this, ndef, p, oldnode, modified_blocks);
 
-	for(s32 i=0; i<2; i++)
-	{
-		enum LightBank bank = banks[i];
-
-		/*
-			Spread light from all nodes that might be capable of doing so
-		*/
-		spreadLight(bank, light_sources, modified_blocks);
-	}
-
-	/*
-		Update information about whether day and night light differ
-	*/
 	for(std::map<v3s16, MapBlock*>::iterator
 			i = modified_blocks.begin();
 			i != modified_blocks.end(); ++i)
@@ -1073,9 +836,7 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 		i->second->expireDayNightDiff();
 	}
 
-	/*
-		Report for rollback
-	*/
+	// Report for rollback
 	if(m_gamedef->rollback())
 	{
 		RollbackNode rollback_newnode(this, p, m_gamedef);
@@ -1085,22 +846,23 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 	}
 
 	/*
-		Add neighboring liquid nodes and the node itself if it is
-		liquid (=water node was added) to transform queue.
-	*/
+		Add neighboring liquid nodes and this node to transform queue.
+		(it's vital for the node itself to get updated last, if it was removed.)
+	 */
 	v3s16 dirs[7] = {
-		v3s16(0,0,0), // self
 		v3s16(0,0,1), // back
 		v3s16(0,1,0), // top
 		v3s16(1,0,0), // right
 		v3s16(0,0,-1), // front
 		v3s16(0,-1,0), // bottom
 		v3s16(-1,0,0), // left
+		v3s16(0,0,0), // self
 	};
 	for(u16 i=0; i<7; i++)
 	{
 		v3s16 p2 = p + dirs[i];
 
+		bool is_valid_position;
 		MapNode n2 = getNodeNoEx(p2, &is_valid_position);
 		if(is_valid_position
 				&& (ndef->get(n2).isLiquid() || n2.getContent() == CONTENT_AIR))
@@ -1110,183 +872,10 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 	}
 }
 
-/*
-*/
 void Map::removeNodeAndUpdate(v3s16 p,
 		std::map<v3s16, MapBlock*> &modified_blocks)
 {
-	INodeDefManager *ndef = m_gamedef->ndef();
-
-	/*PrintInfo(m_dout);
-	m_dout<<"Map::removeNodeAndUpdate(): p=("
-			<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;*/
-
-	bool node_under_sunlight = true;
-
-	v3s16 toppos = p + v3s16(0,1,0);
-
-	// Node will be replaced with this
-	content_t replace_material = CONTENT_AIR;
-
-	/*
-		Collect old node for rollback
-	*/
-	RollbackNode rollback_oldnode(this, p, m_gamedef);
-
-	/*
-		If there is a node at top and it doesn't have sunlight,
-		there will be no sunlight going down.
-	*/
-	bool is_valid_position;
-	MapNode topnode = getNodeNoEx(toppos, &is_valid_position);
-
-	if(is_valid_position && topnode.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN)
-		node_under_sunlight = false;
-
-	std::set<v3s16> light_sources;
-
-	enum LightBank banks[] =
-	{
-		LIGHTBANK_DAY,
-		LIGHTBANK_NIGHT
-	};
-	for(s32 i=0; i<2; i++)
-	{
-		enum LightBank bank = banks[i];
-
-		/*
-			Unlight neighbors (in case the node is a light source)
-		*/
-		unLightNeighbors(bank, p,
-				getNodeNoEx(p).getLight(bank, ndef),
-				light_sources, modified_blocks);
-	}
-
-	/*
-		Remove node metadata
-	*/
-
-	removeNodeMetadata(p);
-
-	/*
-		Remove the node.
-		This also clears the lighting.
-	*/
-
-	MapNode n(replace_material);
-	setNode(p, n);
-
-	for(s32 i=0; i<2; i++)
-	{
-		enum LightBank bank = banks[i];
-
-		/*
-			Recalculate lighting
-		*/
-		spreadLight(bank, light_sources, modified_blocks);
-	}
-
-	// Add the block of the removed node to modified_blocks
-	v3s16 blockpos = getNodeBlockPos(p);
-	MapBlock * block = getBlockNoCreate(blockpos);
-	assert(block != NULL);
-	modified_blocks[blockpos] = block;
-
-	/*
-		If the removed node was under sunlight, propagate the
-		sunlight down from it and then light all neighbors
-		of the propagated blocks.
-	*/
-	if(node_under_sunlight)
-	{
-		s16 ybottom = propagateSunlight(p, modified_blocks);
-		/*m_dout<<"Node was under sunlight. "
-				"Propagating sunlight";
-		m_dout<<" -> ybottom="<<ybottom<<std::endl;*/
-		s16 y = p.Y;
-		for(; y >= ybottom; y--)
-		{
-			v3s16 p2(p.X, y, p.Z);
-			/*m_dout<<"lighting neighbors of node ("
-					<<p2.X<<","<<p2.Y<<","<<p2.Z<<")"
-					<<std::endl;*/
-			lightNeighbors(LIGHTBANK_DAY, p2, modified_blocks);
-		}
-	}
-	else
-	{
-		// Set the lighting of this node to 0
-		// TODO: Is this needed? Lighting is cleared up there already.
-		MapNode n = getNodeNoEx(p, &is_valid_position);
-		if (is_valid_position) {
-			n.setLight(LIGHTBANK_DAY, 0, ndef);
-			setNode(p, n);
-		} else {
-			FATAL_ERROR("Invalid position");
-		}
-	}
-
-	for(s32 i=0; i<2; i++)
-	{
-		enum LightBank bank = banks[i];
-
-		// Get the brightest neighbour node and propagate light from it
-		v3s16 n2p = getBrightestNeighbour(bank, p);
-		try{
-			//MapNode n2 = getNode(n2p);
-			lightNeighbors(bank, n2p, modified_blocks);
-		}
-		catch(InvalidPositionException &e)
-		{
-		}
-	}
-
-	/*
-		Update information about whether day and night light differ
-	*/
-	for(std::map<v3s16, MapBlock*>::iterator
-			i = modified_blocks.begin();
-			i != modified_blocks.end(); ++i)
-	{
-		i->second->expireDayNightDiff();
-	}
-
-	/*
-		Report for rollback
-	*/
-	if(m_gamedef->rollback())
-	{
-		RollbackNode rollback_newnode(this, p, m_gamedef);
-		RollbackAction action;
-		action.setSetNode(p, rollback_oldnode, rollback_newnode);
-		m_gamedef->rollback()->reportAction(action);
-	}
-
-	/*
-		Add neighboring liquid nodes and this node to transform queue.
-		(it's vital for the node itself to get updated last.)
-	*/
-	v3s16 dirs[7] = {
-		v3s16(0,0,1), // back
-		v3s16(0,1,0), // top
-		v3s16(1,0,0), // right
-		v3s16(0,0,-1), // front
-		v3s16(0,-1,0), // bottom
-		v3s16(-1,0,0), // left
-		v3s16(0,0,0), // self
-	};
-	for(u16 i=0; i<7; i++)
-	{
-		v3s16 p2 = p + dirs[i];
-
-		bool is_position_valid;
-		MapNode n2 = getNodeNoEx(p2, &is_position_valid);
-		if (is_position_valid
-				&& (ndef->get(n2).isLiquid() || n2.getContent() == CONTENT_AIR))
-		{
-			m_transforming_liquid.push_back(p2);
-		}
-	}
+	addNodeAndUpdate(p, MapNode(CONTENT_AIR), modified_blocks, true);
 }
 
 bool Map::addNodeWithEvent(v3s16 p, MapNode n, bool remove_metadata)
diff --git a/src/map.h b/src/map.h
index c73fa92bf..e8d40e982 100644
--- a/src/map.h
+++ b/src/map.h
@@ -211,24 +211,10 @@ public:
 			std::set<v3s16> & light_sources,
 			std::map<v3s16, MapBlock*> & modified_blocks);
 
-	void unLightNeighbors(enum LightBank bank,
-			v3s16 pos, u8 lightwas,
-			std::set<v3s16> & light_sources,
-			std::map<v3s16, MapBlock*> & modified_blocks);
-
 	void spreadLight(enum LightBank bank,
 			std::set<v3s16> & from_nodes,
 			std::map<v3s16, MapBlock*> & modified_blocks);
-
-	void lightNeighbors(enum LightBank bank,
-			v3s16 pos,
-			std::map<v3s16, MapBlock*> & modified_blocks);
-
-	v3s16 getBrightestNeighbour(enum LightBank bank, v3s16 p);
-
-	s16 propagateSunlight(v3s16 start,
-			std::map<v3s16, MapBlock*> & modified_blocks);
-
+	
 	void updateLighting(enum LightBank bank,
 			std::map<v3s16, MapBlock*>  & a_blocks,
 			std::map<v3s16, MapBlock*> & modified_blocks);
diff --git a/src/mapnode.cpp b/src/mapnode.cpp
index eba47446d..5efebf3d8 100644
--- a/src/mapnode.cpp
+++ b/src/mapnode.cpp
@@ -54,10 +54,10 @@ MapNode::MapNode(INodeDefManager *ndef, const std::string &name,
 	param2 = a_param2;
 }
 
-void MapNode::setLight(enum LightBank bank, u8 a_light, INodeDefManager *nodemgr)
+void MapNode::setLight(enum LightBank bank, u8 a_light, const ContentFeatures &f)
 {
 	// If node doesn't contain light data, ignore this
-	if(nodemgr->get(*this).param_type != CPT_LIGHT)
+	if(f.param_type != CPT_LIGHT)
 		return;
 	if(bank == LIGHTBANK_DAY)
 	{
@@ -73,6 +73,11 @@ void MapNode::setLight(enum LightBank bank, u8 a_light, INodeDefManager *nodemgr
 		assert("Invalid light bank" == NULL);
 }
 
+void MapNode::setLight(enum LightBank bank, u8 a_light, INodeDefManager *nodemgr)
+{
+	setLight(bank, a_light, nodemgr->get(*this));
+}
+
 bool MapNode::isLightDayNightEq(INodeDefManager *nodemgr) const
 {
 	const ContentFeatures &f = nodemgr->get(*this);
@@ -103,6 +108,13 @@ u8 MapNode::getLight(enum LightBank bank, INodeDefManager *nodemgr) const
 	return MYMAX(f.light_source, light);
 }
 
+u8 MapNode::getLightRaw(enum LightBank bank, const ContentFeatures &f) const
+{
+	if(f.param_type == CPT_LIGHT)
+		return bank == LIGHTBANK_DAY ? param1 & 0x0f : (param1 >> 4) & 0x0f;
+	return 0;
+}
+
 u8 MapNode::getLightNoChecks(enum LightBank bank, const ContentFeatures *f) const
 {
 	return MYMAX(f->light_source,
diff --git a/src/mapnode.h b/src/mapnode.h
index 2f6224f02..0bd61c554 100644
--- a/src/mapnode.h
+++ b/src/mapnode.h
@@ -191,6 +191,8 @@ struct MapNode
 		param2 = p;
 	}
 
+	void setLight(enum LightBank bank, u8 a_light, const ContentFeatures &f);
+
 	void setLight(enum LightBank bank, u8 a_light, INodeDefManager *nodemgr);
 
 	/**
@@ -202,6 +204,13 @@ struct MapNode
 
 	u8 getLight(enum LightBank bank, INodeDefManager *nodemgr) const;
 
+	/*!
+	 * Returns the node's light level from param1.
+	 * If the node emits light, it is ignored.
+	 * \param f the ContentFeatures of this node.
+	 */
+	u8 getLightRaw(enum LightBank bank, const ContentFeatures &f) const;
+
 	/**
 	 * This function differs from getLight(enum LightBank bank, INodeDefManager *nodemgr)
 	 * in that the ContentFeatures of the node in question are not retrieved by
diff --git a/src/voxelalgorithms.cpp b/src/voxelalgorithms.cpp
index f067a221a..019ec1bc6 100644
--- a/src/voxelalgorithms.cpp
+++ b/src/voxelalgorithms.cpp
@@ -19,6 +19,9 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 
 #include "voxelalgorithms.h"
 #include "nodedef.h"
+#include "mapblock.h"
+#include "map.h"
+#include "util/timetaker.h"
 
 namespace voxalgo
 {
@@ -153,5 +156,586 @@ SunlightPropagateResult propagateSunlight(VoxelManipulator &v, VoxelArea a,
 	return SunlightPropagateResult(bottom_sunlight_valid);
 }
 
+/*!
+ * A direction.
+ * 0=X+
+ * 1=Y+
+ * 2=Z+
+ * 3=Z-
+ * 4=Y-
+ * 5=X-
+ * 6=no direction
+ * Two directions ate opposite only if their sum is 5.
+ */
+typedef u8 direction;
+/*!
+ * Relative node position.
+ * This represents a node's position in its map block.
+ * All coordinates must be between 0 and 15.
+ */
+typedef v3s16 relative_v3;
+/*!
+ * Position of a map block.
+ * One block_pos unit is as long as 16 node position units.
+ */
+typedef v3s16 mapblock_v3;
+
+//! Contains information about a node whose light is about to change.
+struct ChangingLight {
+	//! Relative position of the node in its map block.
+	relative_v3 rel_position;
+	//! Position of the node's block.
+	mapblock_v3 block_position;
+	//! Reference to the node's block.
+	MapBlock *block;
+	/*!
+	 * Direction from the node that caused this node's changing
+	 * to this node.
+	 */
+	direction source_direction;
+
+	ChangingLight() :
+		rel_position(),
+		block_position(),
+		block(NULL),
+		source_direction(6)
+	{}
+
+	ChangingLight(relative_v3 rel_pos, mapblock_v3 block_pos,
+		MapBlock *b, direction source_dir) :
+		rel_position(rel_pos),
+		block_position(block_pos),
+		block(b),
+		source_direction(source_dir)
+	{}
+};
+
+/*!
+ * A fast, priority queue-like container to contain ChangingLights.
+ * The ChangingLights are ordered by the given light levels.
+ * The brightest ChangingLight is returned first.
+ */
+struct LightQueue {
+	//! For each light level there is a vector.
+	std::vector<ChangingLight> lights[LIGHT_SUN + 1];
+	//! Light of the brightest ChangingLight in the queue.
+	u8 max_light;
+
+	/*!
+	 * Creates a LightQueue.
+	 * \param reserve for each light level that many slots are reserved.
+	 */
+	LightQueue(size_t reserve)
+	{
+		max_light = LIGHT_SUN;
+		for (u8 i = 0; i <= LIGHT_SUN; i++) {
+			lights[i].reserve(reserve);
+		}
+	}
+
+	/*!
+	 * Returns the next brightest ChangingLight and
+	 * removes it from the queue.
+	 * If there were no elements in the queue, the given parameters
+	 * remain unmodified.
+	 * \param light light level of the popped ChangingLight
+	 * \param data the ChangingLight that was popped
+	 * \returns true if there was a ChangingLight in the queue.
+	 */
+	bool next(u8 &light, ChangingLight &data)
+	{
+		while (lights[max_light].empty()) {
+			if (max_light == 0) {
+				return false;
+			}
+			max_light--;
+		}
+		light = max_light;
+		data = lights[max_light].back();
+		lights[max_light].pop_back();
+		return true;
+	}
+
+	/*!
+	 * Adds an element to the queue.
+	 * The parameters are the same as in ChangingLight's constructor.
+	 * \param light light level of the ChangingLight
+	 */
+	inline void push(u8 light, relative_v3 &rel_pos, mapblock_v3 &block_pos,
+		MapBlock *block, direction source_dir)
+	{
+		lights[light].push_back(
+			ChangingLight(rel_pos, block_pos, block, source_dir));
+	}
+};
+
+/*!
+ * This type of light queue is for unlighting.
+ * A node can be pushed in it only if its raw light is zero.
+ * This prevents pushing nodes twice into this queue.
+ * The light of the pushed ChangingLight must be the
+ * light of the node before unlighting it.
+ */
+typedef LightQueue UnlightQueue;
+/*!
+ * This type of light queue is for spreading lights.
+ * While spreading lights, all the nodes in it must
+ * have the same light as the light level the ChangingLights
+ * were pushed into this queue with. This prevents unnecessary
+ * re-pushing of the nodes into the queue.
+ * If a node doesn't let light trough but emits light, it can be added
+ * too.
+ */
+typedef LightQueue ReLightQueue;
+
+/*!
+ * neighbor_dirs[i] points towards
+ * the direction i.
+ * See the definition of the type "direction"
+ */
+const static v3s16 neighbor_dirs[6] = {
+	v3s16(1, 0, 0), // right
+	v3s16(0, 1, 0), // top
+	v3s16(0, 0, 1), // back
+	v3s16(0, 0, -1), // front
+	v3s16(0, -1, 0), // bottom
+	v3s16(-1, 0, 0), // left
+};
+
+/*!
+ * Transforms the given map block offset by one node towards
+ * the specified direction.
+ * \param dir the direction of the transformation
+ * \param rel_pos the node's relative position in its map block
+ * \param block_pos position of the node's block
+ */
+bool stepRelBlockPos(direction dir, relative_v3 &rel_pos,
+	mapblock_v3 &block_pos)
+{
+	switch (dir) {
+	case 0:
+		if (rel_pos.X < MAP_BLOCKSIZE - 1) {
+			rel_pos.X++;
+		} else {
+			rel_pos.X = 0;
+			block_pos.X++;
+			return true;
+		}
+		break;
+	case 1:
+		if (rel_pos.Y < MAP_BLOCKSIZE - 1) {
+			rel_pos.Y++;
+		} else {
+			rel_pos.Y = 0;
+			block_pos.Y++;
+			return true;
+		}
+		break;
+	case 2:
+		if (rel_pos.Z < MAP_BLOCKSIZE - 1) {
+			rel_pos.Z++;
+		} else {
+			rel_pos.Z = 0;
+			block_pos.Z++;
+			return true;
+		}
+		break;
+	case 3:
+		if (rel_pos.Z > 0) {
+			rel_pos.Z--;
+		} else {
+			rel_pos.Z = MAP_BLOCKSIZE - 1;
+			block_pos.Z--;
+			return true;
+		}
+		break;
+	case 4:
+		if (rel_pos.Y > 0) {
+			rel_pos.Y--;
+		} else {
+			rel_pos.Y = MAP_BLOCKSIZE - 1;
+			block_pos.Y--;
+			return true;
+		}
+		break;
+	case 5:
+		if (rel_pos.X > 0) {
+			rel_pos.X--;
+		} else {
+			rel_pos.X = MAP_BLOCKSIZE - 1;
+			block_pos.X--;
+			return true;
+		}
+		break;
+	}
+	return false;
+}
+
+/*
+ * Removes all light that is potentially emitted by the specified
+ * light sources. These nodes will have zero light.
+ * Returns all nodes whose light became zero but should be re-lighted.
+ *
+ * \param bank the light bank in which the procedure operates
+ * \param from_nodes nodes whose light is removed
+ * \param light_sources nodes that should be re-lighted
+ * \param modified_blocks output, all modified map blocks are added to this
+ */
+void unspreadLight(Map *map, INodeDefManager *nodemgr, LightBank bank,
+	UnlightQueue &from_nodes, ReLightQueue &light_sources,
+	std::map<v3s16, MapBlock*> & modified_blocks)
+{
+	// Stores data popped from from_nodes
+	u8 current_light;
+	ChangingLight current;
+	// Data of the current neighbor
+	mapblock_v3 neighbor_block_pos;
+	relative_v3 neighbor_rel_pos;
+	// A dummy boolean
+	bool is_valid_position;
+	// Direction of the brightest neighbor of the node
+	direction source_dir;
+	while (from_nodes.next(current_light, current)) {
+		// For all nodes that need unlighting
+
+		// There is no brightest neighbor
+		source_dir = 6;
+		// The current node
+		const MapNode &node = current.block->getNodeNoCheck(
+			current.rel_position, &is_valid_position);
+		const ContentFeatures &f = nodemgr->get(node);
+		// If the node emits light, it behaves like it had a
+		// brighter neighbor.
+		u8 brightest_neighbor_light = f.light_source + 1;
+		for (direction i = 0; i < 6; i++) {
+			//For each neighbor
+
+			// The node that changed this node has already zero light
+			// and it can't give light to this node
+			if (current.source_direction + i == 5) {
+				continue;
+			}
+			// Get the neighbor's position and block
+			neighbor_rel_pos = current.rel_position;
+			neighbor_block_pos = current.block_position;
+			MapBlock *neighbor_block;
+			if (stepRelBlockPos(i, neighbor_rel_pos, neighbor_block_pos)) {
+				neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
+				if (neighbor_block == NULL) {
+					continue;
+				}
+			} else {
+				neighbor_block = current.block;
+			}
+			// Get the neighbor itself
+			MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
+				&is_valid_position);
+			const ContentFeatures &neighbor_f = nodemgr->get(
+				neighbor.getContent());
+			u8 neighbor_light = neighbor.getLightRaw(bank, neighbor_f);
+			// If the neighbor has at least as much light as this node, then
+			// it won't lose its light, since it should have been added to
+			// from_nodes earlier, so its light would be zero.
+			if (neighbor_f.light_propagates && neighbor_light < current_light) {
+				// Unlight, but only if the node has light.
+				if (neighbor_light > 0) {
+					neighbor.setLight(bank, 0, neighbor_f);
+					neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
+					from_nodes.push(neighbor_light, neighbor_rel_pos,
+						neighbor_block_pos, neighbor_block, i);
+					// The current node was modified earlier, so its block
+					// is in modified_blocks.
+					if (current.block != neighbor_block) {
+						modified_blocks[neighbor_block_pos] = neighbor_block;
+					}
+				}
+			} else {
+				// The neighbor can light up this node.
+				if (neighbor_light < neighbor_f.light_source) {
+					neighbor_light = neighbor_f.light_source;
+				}
+				if (brightest_neighbor_light < neighbor_light) {
+					brightest_neighbor_light = neighbor_light;
+					source_dir = i;
+				}
+			}
+		}
+		// If the brightest neighbor is able to light up this node,
+		// then add this node to the output nodes.
+		if (brightest_neighbor_light > 1 && f.light_propagates) {
+			brightest_neighbor_light--;
+			light_sources.push(brightest_neighbor_light, current.rel_position,
+				current.block_position, current.block,
+				(source_dir == 6) ? 6 : 5 - source_dir
+				/* with opposite direction*/);
+		}
+	}
+}
+
+/*
+ * Spreads light from the specified starting nodes.
+ *
+ * Before calling this procedure, make sure that all ChangingLights
+ * in light_sources have as much light on the map as they have in
+ * light_sources (if the queue contains a node multiple times, the brightest
+ * occurrence counts).
+ *
+ * \param bank the light bank in which the procedure operates
+ * \param light_sources starting nodes
+ * \param modified_blocks output, all modified map blocks are added to this
+ */
+void spreadLight(Map *map, INodeDefManager *nodemgr, LightBank bank,
+	LightQueue & light_sources, std::map<v3s16, MapBlock*> & modified_blocks)
+{
+	// The light the current node can provide to its neighbors.
+	u8 spreading_light;
+	// The ChangingLight for the current node.
+	ChangingLight current;
+	// Position of the current neighbor.
+	mapblock_v3 neighbor_block_pos;
+	relative_v3 neighbor_rel_pos;
+	// A dummy boolean.
+	bool is_valid_position;
+	while (light_sources.next(spreading_light, current)) {
+		spreading_light--;
+		for (direction i = 0; i < 6; i++) {
+			// This node can't light up its light source
+			if (current.source_direction + i == 5) {
+				continue;
+			}
+			// Get the neighbor's position and block
+			neighbor_rel_pos = current.rel_position;
+			neighbor_block_pos = current.block_position;
+			MapBlock *neighbor_block;
+			if (stepRelBlockPos(i, neighbor_rel_pos, neighbor_block_pos)) {
+				neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
+				if (neighbor_block == NULL) {
+					continue;
+				}
+			} else {
+				neighbor_block = current.block;
+			}
+			// Get the neighbor itself
+			MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
+				&is_valid_position);
+			const ContentFeatures &f = nodemgr->get(neighbor.getContent());
+			if (f.light_propagates) {
+				// Light up the neighbor, if it has less light than it should.
+				u8 neighbor_light = neighbor.getLightRaw(bank, f);
+				if (neighbor_light < spreading_light) {
+					neighbor.setLight(bank, spreading_light, f);
+					neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
+					light_sources.push(spreading_light, neighbor_rel_pos,
+						neighbor_block_pos, neighbor_block, i);
+					// The current node was modified earlier, so its block
+					// is in modified_blocks.
+					if (current.block != neighbor_block) {
+						modified_blocks[neighbor_block_pos] = neighbor_block;
+					}
+				}
+			}
+		}
+	}
+}
+
+/*!
+ * Returns true if the node gets sunlight from the
+ * node above it.
+ *
+ * \param pos position of the node.
+ */
+bool isSunlightAbove(Map *map, v3s16 pos, INodeDefManager *ndef)
+{
+	bool sunlight = true;
+	mapblock_v3 source_block_pos;
+	relative_v3 source_rel_pos;
+	getNodeBlockPosWithOffset(pos + v3s16(0, 1, 0), source_block_pos,
+		source_rel_pos);
+	// If the node above has sunlight, this node also can get it.
+	MapBlock *source_block = map->getBlockNoCreateNoEx(source_block_pos);
+	if (source_block == NULL) {
+		// But if there is no node above, then use heuristics
+		MapBlock *node_block = map->getBlockNoCreateNoEx(getNodeBlockPos(pos));
+		if (node_block == NULL) {
+			sunlight = false;
+		} else {
+			sunlight = !node_block->getIsUnderground();
+		}
+	} else {
+		bool is_valid_position;
+		MapNode above = source_block->getNodeNoCheck(source_rel_pos,
+			&is_valid_position);
+		if (is_valid_position) {
+			if (above.getContent() == CONTENT_IGNORE) {
+				// Trust heuristics
+				if (source_block->getIsUnderground()) {
+					sunlight = false;
+				}
+			} else if (above.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
+				// If the node above doesn't have sunlight, this
+				// node is in shadow.
+				sunlight = false;
+			}
+		}
+	}
+	return sunlight;
+}
+
+static const LightBank banks[] = { LIGHTBANK_DAY, LIGHTBANK_NIGHT };
+
+void update_lighting_node(Map *map, INodeDefManager *ndef, v3s16 p,
+	MapNode oldnode, std::map<v3s16, MapBlock*> & modified_blocks)
+{
+	// For node getter functions
+	bool is_valid_position;
+
+	// Get position and block of the changed node
+	relative_v3 rel_pos;
+	mapblock_v3 block_pos;
+	getNodeBlockPosWithOffset(p, block_pos, rel_pos);
+	MapBlock *block = map->getBlockNoCreateNoEx(block_pos);
+	if (block == NULL || block->isDummy()) {
+		return;
+	}
+
+	// Process each light bank separately
+	for (s32 i = 0; i < 2; i++) {
+		// Get the new node
+		MapNode n = block->getNodeNoCheck(rel_pos, &is_valid_position);
+		if (!is_valid_position) {
+			break;
+		}
+		LightBank bank = banks[i];
+
+		// Light of the old node
+		u8 old_light = oldnode.getLight(bank, ndef);
+
+		// Add the block of the added node to modified_blocks
+		modified_blocks[block_pos] = block;
+
+		// Get new light level of the node
+		u8 new_light = 0;
+		if (ndef->get(n).light_propagates) {
+			if (bank == LIGHTBANK_DAY && ndef->get(n).sunlight_propagates
+					&& isSunlightAbove(map, p, ndef)) {
+				new_light = LIGHT_SUN;
+			} else {
+				new_light = ndef->get(n).light_source;
+				for (int i = 0; i < 6; i++) {
+					v3s16 p2 = p + neighbor_dirs[i];
+					bool is_valid;
+					MapNode n2 = map->getNodeNoEx(p2, &is_valid);
+					if (is_valid) {
+						u8 spread = n2.getLight(bank, ndef);
+						// If the neighbor is at least as bright as
+						// this node then its light is not from
+						// this node.
+						// Its light can spread to this node.
+						if (spread > new_light && spread >= old_light) {
+							new_light = spread - 1;
+						}
+					}
+				}
+			}
+		} else {
+			// If this is an opaque node, it still can emit light.
+			new_light = ndef->get(n).light_source;
+		}
+
+		ReLightQueue light_sources(256);
+
+		if (new_light > 0) {
+			light_sources.push(new_light, rel_pos, block_pos, block, 6);
+		}
+
+		if (new_light < old_light) {
+			// The node became opaque or doesn't provide as much
+			// light as the previous one, so it must be unlighted.
+			LightQueue disappearing_lights(256);
+
+			// Add to unlight queue
+			n.setLight(bank, 0, ndef);
+			block->setNodeNoCheck(rel_pos, n);
+			disappearing_lights.push(old_light, rel_pos, block_pos, block, 6);
+
+			// Remove sunlight, if there was any
+			if (bank == LIGHTBANK_DAY && old_light == LIGHT_SUN) {
+				for (s16 y = p.Y - 1;; y--) {
+					v3s16 n2pos(p.X, y, p.Z);
+
+					MapNode n2;
+
+					n2 = map->getNodeNoEx(n2pos, &is_valid_position);
+					if (!is_valid_position)
+						break;
+
+					// If this node doesn't have sunlight, the nodes below
+					// it don't have too.
+					if (n2.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
+						break;
+					}
+					// Remove sunlight and add to unlight queue.
+					n2.setLight(LIGHTBANK_DAY, 0, ndef);
+					map->setNode(n2pos, n2);
+					relative_v3 rel_pos2;
+					mapblock_v3 block_pos2;
+					getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
+					MapBlock *block2 = map->getBlockNoCreateNoEx(block_pos2);
+					disappearing_lights.push(LIGHT_SUN, rel_pos2, block_pos2,
+						block2, 4 /* The node above caused the change */);
+				}
+			}
+			// Remove lights
+			unspreadLight(map, ndef, bank, disappearing_lights, light_sources,
+				modified_blocks);
+		} else if (new_light > old_light) {
+			// It is sure that the node provides more light than the previous
+			// one, unlighting is not necessary.
+			// Propagate sunlight
+			if (bank == LIGHTBANK_DAY && new_light == LIGHT_SUN) {
+				for (s16 y = p.Y - 1;; y--) {
+					v3s16 n2pos(p.X, y, p.Z);
+
+					MapNode n2;
+
+					n2 = map->getNodeNoEx(n2pos, &is_valid_position);
+					if (!is_valid_position)
+						break;
+
+					// This should not happen, but if the node has sunlight
+					// then the iteration should stop.
+					if (n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN) {
+						break;
+					}
+					// If the node terminates sunlight, stop.
+					if (!ndef->get(n2).sunlight_propagates) {
+						break;
+					}
+					relative_v3 rel_pos2;
+					mapblock_v3 block_pos2;
+					getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
+					MapBlock *block2 = map->getBlockNoCreateNoEx(block_pos2);
+					// Mark node for lighting.
+					light_sources.push(LIGHT_SUN, rel_pos2, block_pos2, block2,
+						4);
+				}
+			}
+		}
+		// Initialize light values for light spreading.
+		for (u8 i = 0; i <= LIGHT_SUN; i++) {
+			const std::vector<ChangingLight> &lights = light_sources.lights[i];
+			for (std::vector<ChangingLight>::const_iterator it = lights.begin();
+					it < lights.end(); it++) {
+				MapNode n = it->block->getNodeNoCheck(it->rel_position,
+					&is_valid_position);
+				n.setLight(bank, i, ndef);
+				it->block->setNodeNoCheck(it->rel_position, n);
+			}
+		}
+		// Spread lights.
+		spreadLight(map, ndef, bank, light_sources, modified_blocks);
+	}
+}
+
 } // namespace voxalgo
 
diff --git a/src/voxelalgorithms.h b/src/voxelalgorithms.h
index 2eba6a176..f2b2fde32 100644
--- a/src/voxelalgorithms.h
+++ b/src/voxelalgorithms.h
@@ -25,6 +25,9 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include <set>
 #include <map>
 
+class Map;
+class MapBlock;
+
 namespace voxalgo
 {
 
@@ -52,6 +55,23 @@ SunlightPropagateResult propagateSunlight(VoxelManipulator &v, VoxelArea a,
 		std::set<v3s16> & light_sources,
 		INodeDefManager *ndef);
 
+/*!
+ * Updates the lighting on the map.
+ * The result will be correct only if
+ * no nodes were changed except the given one.
+ *
+ * \param p position of the changed node
+ * \param oldnode this node was overwritten on the map
+ * \param modified_blocks output, contains all map blocks that
+ * the function modified
+ */
+void update_lighting_node(
+	Map *map,
+	INodeDefManager *ndef,
+	v3s16 p,
+	MapNode oldnode,
+	std::map<v3s16, MapBlock*> &modified_blocks);
+
 } // namespace voxalgo
 
 #endif