generate-time lighting optimization

7 files changed, 257 insertions, 184 deletions

diff --git a/src/defaultsettings.cpp b/src/defaultsettings.cpp
index e15a5b3a2..581948071 100644
--- a/src/defaultsettings.cpp
+++ b/src/defaultsettings.cpp
@@ -48,8 +48,8 @@ void set_default_settings()
 	g_settings.setDefault("ravines_amount", "1.0");
 	g_settings.setDefault("coal_amount", "1.0");*/
 	g_settings.setDefault("heightmap_blocksize", "16");
-	g_settings.setDefault("height_randmax", "linear 0 0 40");
-	g_settings.setDefault("height_randfactor", "linear 0.60 -0.10 0");
+	g_settings.setDefault("height_randmax", "linear 0 0 30");
+	g_settings.setDefault("height_randfactor", "linear 0.50 -0.10 0");
 	g_settings.setDefault("height_base", "linear 5 0 0");
 	g_settings.setDefault("plants_amount", "0.2");
 	g_settings.setDefault("ravines_amount", "0");
diff --git a/src/map.cpp b/src/map.cpp
index 119b487db..c8175c4cf 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -1692,6 +1692,8 @@ MapBlock * ServerMap::emergeBlock(
 	/*
 		If block doesn't exist, create one.
 		If it exists, it is a dummy. In that case unDummify() it.
+
+		NOTE: This already sets the map as the parent of the block
 	*/
 	if(block == NULL)
 	{
@@ -1701,13 +1703,146 @@ MapBlock * ServerMap::emergeBlock(
 	{
 		// Remove the block so that nobody can get a half-generated one.
 		sector->removeBlock(block);
-		// Allocate the block to be a proper one.
+		// Allocate the block to contain the generated data
 		block->unDummify();
 	}
 	
+	u8 water_material = CONTENT_WATER;
+	if(g_settings.getBool("endless_water"))
+		water_material = CONTENT_OCEAN;
+	
+	s32 lowest_ground_y = 32767;
+	s32 highest_ground_y = -32768;
+	
+	// DEBUG
+	//sector->printHeightmaps();
+
+	for(s16 z0=0; z0<MAP_BLOCKSIZE; z0++)
+	for(s16 x0=0; x0<MAP_BLOCKSIZE; x0++)
+	{
+		//dstream<<"emergeBlock: x0="<<x0<<", z0="<<z0<<std::endl;
+
+		float surface_y_f = sector->getGroundHeight(v2s16(x0,z0));
+		//assert(surface_y_f > GROUNDHEIGHT_VALID_MINVALUE);
+		if(surface_y_f < GROUNDHEIGHT_VALID_MINVALUE)
+		{
+			dstream<<"WARNING: Surface height not found in sector "
+					"for block that is being emerged"<<std::endl;
+			surface_y_f = 0.0;
+		}
+
+		s16 surface_y = surface_y_f;
+		//avg_ground_y += surface_y;
+		if(surface_y < lowest_ground_y)
+			lowest_ground_y = surface_y;
+		if(surface_y > highest_ground_y)
+			highest_ground_y = surface_y;
+
+		s32 surface_depth = 0;
+		
+		float slope = sector->getSlope(v2s16(x0,z0)).getLength();
+		
+		//float min_slope = 0.45;
+		//float max_slope = 0.85;
+		float min_slope = 0.60;
+		float max_slope = 1.20;
+		float min_slope_depth = 5.0;
+		float max_slope_depth = 0;
+
+		if(slope < min_slope)
+			surface_depth = min_slope_depth;
+		else if(slope > max_slope)
+			surface_depth = max_slope_depth;
+		else
+			surface_depth = (1.-(slope-min_slope)/max_slope) * min_slope_depth;
+
+		for(s16 y0=0; y0<MAP_BLOCKSIZE; y0++)
+		{
+			s16 real_y = block_y * MAP_BLOCKSIZE + y0;
+			MapNode n;
+			/*
+				Calculate lighting
+				
+				NOTE: If there are some man-made structures above the
+				newly created block, they won't be taken into account.
+			*/
+			if(real_y > surface_y)
+				n.setLight(LIGHTBANK_DAY, LIGHT_SUN);
+
+			/*
+				Calculate material
+			*/
+
+			// If node is over heightmap y, it's air or water
+			if(real_y > surface_y)
+			{
+				// If under water level, it's water
+				if(real_y < WATER_LEVEL)
+				{
+					n.d = water_material;
+					n.setLight(LIGHTBANK_DAY,
+							diminish_light(LIGHT_SUN, WATER_LEVEL-real_y+1));
+				}
+				// else air
+				else
+					n.d = CONTENT_AIR;
+			}
+			// Else it's ground or dungeons (air)
+			else
+			{
+				// If it's surface_depth under ground, it's stone
+				if(real_y <= surface_y - surface_depth)
+				{
+					n.d = CONTENT_STONE;
+				}
+				else
+				{
+					// It is mud if it is under the first ground
+					// level or under water
+					if(real_y < WATER_LEVEL || real_y <= surface_y - 1)
+					{
+						n.d = CONTENT_MUD;
+					}
+					else
+					{
+						n.d = CONTENT_GRASS;
+					}
+
+					//n.d = CONTENT_MUD;
+					
+					/*// If under water level, it's mud
+					if(real_y < WATER_LEVEL)
+						n.d = CONTENT_MUD;
+					// Only the topmost node is grass
+					else if(real_y <= surface_y - 1)
+						n.d = CONTENT_MUD;
+					else
+						n.d = CONTENT_GRASS;*/
+				}
+			}
+
+			block->setNode(v3s16(x0,y0,z0), n);
+		}
+	}
+	
+	/*
+		Calculate some helper variables
+	*/
+	
+	// Completely underground if the highest part of block is under lowest
+	// ground height.
+	// This has to be very sure; it's probably one too strict now but
+	// that's just better.
+	bool completely_underground =
+			block_y * MAP_BLOCKSIZE + MAP_BLOCKSIZE < lowest_ground_y;
+
+	bool some_part_underground = block_y * MAP_BLOCKSIZE <= highest_ground_y;
+
 	/*
-		Create dungeon making table
+		Generate dungeons
 	*/
+
+	// Initialize temporary table
 	const s32 ued = MAP_BLOCKSIZE;
 	bool underground_emptiness[ued*ued*ued];
 	for(s32 i=0; i<ued*ued*ued; i++)
@@ -1715,7 +1850,7 @@ MapBlock * ServerMap::emergeBlock(
 		underground_emptiness[i] = 0;
 	}
 	
-	// Generate dungeons
+	// Fill table
 	{
 		/*
 			Initialize orp and ors. Try to find if some neighboring
@@ -1807,7 +1942,17 @@ continue_generating:
 		/*
 			Don't always generate dungeon
 		*/
-		if(found_existing || rand() % 2 == 0)
+		bool do_generate_dungeons = true;
+		if(!some_part_underground)
+			do_generate_dungeons = false;
+		else if(!completely_underground)
+			do_generate_dungeons = rand() % 5;
+		else if(found_existing)
+			do_generate_dungeons = true;
+		else
+			do_generate_dungeons = rand() % 2;
+
+		if(do_generate_dungeons)
 		{
 			/*
 				Generate some tunnel starting from orp and ors
@@ -1820,7 +1965,7 @@ continue_generating:
 					(float)(myrand()%ued)+0.5
 				);
 				s16 min_d = 0;
-				s16 max_d = 4;
+				s16 max_d = 6;
 				s16 rs = (myrand()%(max_d-min_d+1))+min_d;
 				
 				v3f vec = rp - orp;
@@ -1855,136 +2000,33 @@ continue_generating:
 			}
 		}
 	}
-	
-	u8 water_material = CONTENT_WATER;
-	if(g_settings.getBool("endless_water"))
-		water_material = CONTENT_OCEAN;
-	
-	s32 lowest_ground_y = 32767;
-	s32 highest_ground_y = -32768;
-	
-	// DEBUG
-	//sector->printHeightmaps();
 
 	// Set to true if has caves.
 	// Set when some non-air is changed to air when making caves.
 	bool has_caves = false;
 
+	/*
+		Apply temporary cave data to block
+	*/
+
 	for(s16 z0=0; z0<MAP_BLOCKSIZE; z0++)
 	for(s16 x0=0; x0<MAP_BLOCKSIZE; x0++)
 	{
-		//dstream<<"emergeBlock: x0="<<x0<<", z0="<<z0<<std::endl;
-
-		float surface_y_f = sector->getGroundHeight(v2s16(x0,z0));
-		//assert(surface_y_f > GROUNDHEIGHT_VALID_MINVALUE);
-		if(surface_y_f < GROUNDHEIGHT_VALID_MINVALUE)
-		{
-			dstream<<"WARNING: Surface height not found in sector "
-					"for block that is being emerged"<<std::endl;
-			surface_y_f = 0.0;
-		}
-
-		s16 surface_y = surface_y_f;
-		//avg_ground_y += surface_y;
-		if(surface_y < lowest_ground_y)
-			lowest_ground_y = surface_y;
-		if(surface_y > highest_ground_y)
-			highest_ground_y = surface_y;
-
-		s32 surface_depth = 0;
-		
-		float slope = sector->getSlope(v2s16(x0,z0)).getLength();
-		
-		//float min_slope = 0.45;
-		//float max_slope = 0.85;
-		float min_slope = 0.60;
-		float max_slope = 1.20;
-		float min_slope_depth = 5.0;
-		float max_slope_depth = 0;
-
-		if(slope < min_slope)
-			surface_depth = min_slope_depth;
-		else if(slope > max_slope)
-			surface_depth = max_slope_depth;
-		else
-			surface_depth = (1.-(slope-min_slope)/max_slope) * min_slope_depth;
-
 		for(s16 y0=0; y0<MAP_BLOCKSIZE; y0++)
 		{
-			s16 real_y = block_y * MAP_BLOCKSIZE + y0;
-			MapNode n;
-			/*
-				Calculate lighting
-				
-				NOTE: If there are some man-made structures above the
-				newly created block, they won't be taken into account.
-			*/
-			if(real_y > surface_y)
-				n.setLight(LIGHTBANK_DAY, LIGHT_SUN);
-
-			/*
-				Calculate material
-			*/
+			MapNode n = block->getNode(v3s16(x0,y0,z0));
 
-			// If node is over heightmap y, it's air or water
-			if(real_y > surface_y)
-			{
-				// If under water level, it's water
-				if(real_y < WATER_LEVEL)
-				{
-					n.d = water_material;
-					n.setLight(LIGHTBANK_DAY,
-							diminish_light(LIGHT_SUN, WATER_LEVEL-real_y+1));
-				}
-				// else air
-				else
-					n.d = CONTENT_AIR;
-			}
-			// Else it's ground or dungeons (air)
-			else
+			// Create dungeons
+			if(underground_emptiness[
+					ued*ued*(z0*ued/MAP_BLOCKSIZE)
+					+ued*(y0*ued/MAP_BLOCKSIZE)
+					+(x0*ued/MAP_BLOCKSIZE)])
 			{
-				// If it's surface_depth under ground, it's stone
-				if(real_y <= surface_y - surface_depth)
-				{
-					n.d = CONTENT_STONE;
-				}
-				else
-				{
-					// It is mud if it is under the first ground
-					// level or under water
-					if(real_y < WATER_LEVEL || real_y <= surface_y - 1)
-					{
-						n.d = CONTENT_MUD;
-					}
-					else
-					{
-						n.d = CONTENT_GRASS;
-					}
-
-					//n.d = CONTENT_MUD;
-					
-					/*// If under water level, it's mud
-					if(real_y < WATER_LEVEL)
-						n.d = CONTENT_MUD;
-					// Only the topmost node is grass
-					else if(real_y <= surface_y - 1)
-						n.d = CONTENT_MUD;
-					else
-						n.d = CONTENT_GRASS;*/
-				}
-
-				// Create dungeons
-				if(underground_emptiness[
-						ued*ued*(z0*ued/MAP_BLOCKSIZE)
-						+ued*(y0*ued/MAP_BLOCKSIZE)
-						+(x0*ued/MAP_BLOCKSIZE)])
+				if(is_ground_content(n.d))
 				{
-					// Has now caves if previous content is air
-					if(n.d != CONTENT_AIR)
-					{
-						has_caves = true;
-					}
-
+					// Has now caves
+					has_caves = true;
+					// Set air to node
 					n.d = CONTENT_AIR;
 				}
 			}
@@ -1992,36 +2034,26 @@ continue_generating:
 			block->setNode(v3s16(x0,y0,z0), n);
 		}
 	}
-
+	
 	/*
-		Calculate completely_underground
+		This is used for guessing whether or not the block should
+		receive sunlight from the top if the top block doesn't exist
 	*/
-	// Completely underground if the highest part of block is under lowest
-	// ground height.
-	// This has to be very sure; it's probably one too strict now but
-	// that's just better.
-	bool completely_underground =
-			block_y * MAP_BLOCKSIZE + MAP_BLOCKSIZE < lowest_ground_y;
-
-	// This isn't used anymore (?) but set it anyway
 	block->setIsUnderground(completely_underground);
 
-	bool some_part_underground = block_y * MAP_BLOCKSIZE <= highest_ground_y;
-
 	/*
 		Force lighting update if some part of block is partly
 		underground and has caves.
 	*/
-	
-	if(some_part_underground && !completely_underground && has_caves)
+	/*if(some_part_underground && !completely_underground && has_caves)
 	{
 		//dstream<<"Half-ground caves"<<std::endl;
 		lighting_invalidated_blocks[block->getPos()] = block;
-	}
+	}*/
 	
 	// DEBUG: Always update lighting
 	//lighting_invalidated_blocks[block->getPos()] = block;
-	
+
 	/*
 		Add some minerals
 	*/
@@ -2364,6 +2396,28 @@ continue_generating:
 		objects->remove(*i);
 	}
 
+	/*
+		Initially update sunlight
+	*/
+	
+	{
+		core::map<v3s16, bool> light_sources;
+		bool black_air_left = false;
+		bool bottom_invalid =
+				block->propagateSunlight(light_sources, true, &black_air_left);
+
+		// If sunlight didn't reach everywhere and part of block is
+		// above ground, lighting has to be properly updated
+		if(black_air_left && some_part_underground)
+		{
+			lighting_invalidated_blocks[block->getPos()] = block;
+		}
+	}
+
+	/*
+		Translate sector's changed blocks to global changed blocks
+	*/
+	
 	for(core::map<s16, MapBlock*>::Iterator
 			i = changed_blocks_sector.getIterator();
 			i.atEnd() == false; i++)
diff --git a/src/mapblock.cpp b/src/mapblock.cpp
index 68b296154..252f123ac 100644
--- a/src/mapblock.cpp
+++ b/src/mapblock.cpp
@@ -934,61 +934,68 @@ bool MapBlock::propagateSunlight(core::map<v3s16, bool> & light_sources,
 		
 			s16 y = MAP_BLOCKSIZE-1;
 			
-			if(no_sunlight == false)
+			// This makes difference to diminishing in water.
+			bool stopped_to_solid_object = false;
+			
+			u8 current_light = no_sunlight ? 0 : LIGHT_SUN;
+
+			for(; y >= 0; y--)
 			{
-				// Continue spreading sunlight downwards through transparent
-				// nodes
-				for(; y >= 0; y--)
+				v3s16 pos(x, y, z);
+				MapNode &n = getNodeRef(pos);
+				
+				if(current_light == 0)
 				{
-					v3s16 pos(x, y, z);
-					
-					MapNode &n = getNodeRef(pos);
-
-					if(n.sunlight_propagates())
-					{
-						n.setLight(LIGHTBANK_DAY, LIGHT_SUN);
-
-						light_sources.insert(pos_relative + pos, true);
-					}
-					else
+					// Do nothing
+				}
+				else if(current_light == LIGHT_SUN && n.sunlight_propagates())
+				{
+					// Do nothing: Sunlight is continued
+				}
+				else if(n.light_propagates() == false)
+				{
+					// Turn mud into grass
+					if(n.d == CONTENT_MUD && current_light == LIGHT_SUN)
 					{
-						// Turn mud into grass
-						if(n.d == CONTENT_MUD)
-						{
-							n.d = CONTENT_GRASS;
-						}
-
-						// Sunlight goes no further
-						break;
+						n.d = CONTENT_GRASS;
 					}
+
+					// A solid object is on the way.
+					stopped_to_solid_object = true;
+					
+					// Light stops.
+					current_light = 0;
+				}
+				else
+				{
+					// Diminish light
+					current_light = diminish_light(current_light);
 				}
-			}
 
-			bool sunlight_should_go_down = (y==-1);
-			
-			/*
-				Check rest through to the bottom of the block
-			*/
-			for(; y >= 0; y--)
-			{
-				v3s16 pos(x, y, z);
-				MapNode &n = getNodeRef(pos);
+				u8 old_light = n.getLight(LIGHTBANK_DAY);
 
-				if(n.light_propagates())
+				if(current_light > old_light || remove_light)
+				{
+					n.setLight(LIGHTBANK_DAY, current_light);
+				}
+				
+				if(diminish_light(current_light) != 0)
+				{
+					light_sources.insert(pos_relative + pos, true);
+				}
+
+				if(current_light == 0 && stopped_to_solid_object)
 				{
 					if(black_air_left)
 					{
 						*black_air_left = true;
 					}
-
-					if(remove_light)
-					{
-						// Fill transparent nodes with black
-						n.setLight(LIGHTBANK_DAY, 0);
-					}
 				}
 			}
 
+			// Whether or not the block below should see LIGHT_SUN
+			bool sunlight_should_go_down = (current_light == LIGHT_SUN);
+
 			/*
 				If the block below hasn't already been marked invalid:
 
diff --git a/src/mapblock.h b/src/mapblock.h
index 743dad927..b3fa76bb7 100644
--- a/src/mapblock.h
+++ b/src/mapblock.h
@@ -312,7 +312,8 @@ public:
 #endif // !SERVER
 	
 	// See comments in mapblock.cpp
-	bool propagateSunlight(core::map<v3s16, bool> & light_sources);
+	bool propagateSunlight(core::map<v3s16, bool> & light_sources,
+			bool remove_light=false, bool *black_air_left=NULL);
 	
 	// Copies data to VoxelManipulator to getPosRelative()
 	void copyTo(VoxelManipulator &dst);
diff --git a/src/server.cpp b/src/server.cpp
index 2f285b6e9..9d2e9697d 100644
--- a/src/server.cpp
+++ b/src/server.cpp
@@ -3003,7 +3003,7 @@ Player *Server::emergePlayer(const char *name, const char *password)
 		// Try to find a good place a few times
 		for(s32 i=0; i<100; i++)
 		{
-			s32 range = 1 + i*5;
+			s32 range = 1 + i*2;
 			// We're going to try to throw the player to this position
 			nodepos = v2s16(-range/2 + (myrand()%range),
 					-range/2 + (myrand()%range));
@@ -3036,6 +3036,10 @@ Player *Server::emergePlayer(const char *name, const char *password)
 			break;
 		}
 #endif
+		
+		// If no suitable place was not found, go above water at least.
+		if(groundheight < WATER_LEVEL)
+			groundheight = WATER_LEVEL;
 
 		player->setPosition(intToFloat(v3s16(
 				nodepos.X,
diff --git a/src/test.cpp b/src/test.cpp
index 38c663236..f8f954742 100644
--- a/src/test.cpp
+++ b/src/test.cpp
@@ -537,7 +537,7 @@ struct TestMapBlock
 			core::map<v3s16, bool> light_sources;
 			// The block below should be valid because there shouldn't be
 			// sunlight in there either
-			assert(b.propagateSunlight(light_sources) == true);
+			assert(b.propagateSunlight(light_sources, true) == true);
 			// Should not touch nodes that are not affected (that is, all of them)
 			//assert(b.getNode(v3s16(1,2,3)).getLight() == LIGHT_SUN);
 			// Should set light of non-sunlighted blocks to 0.
diff --git a/src/utility.h b/src/utility.h
index 008a95c38..e2a6afdea 100644
--- a/src/utility.h
+++ b/src/utility.h
@@ -1323,10 +1323,17 @@ private:
 	MutexedQueue< GetRequest<Key, T, Caller, CallerData> > m_queue;
 };
 
-// Pseudo-random (VC++ rand() sucks)
+/*
+	Pseudo-random (VC++ rand() sucks)
+*/
 int myrand(void);
 void mysrand(unsigned seed);
 #define MYRAND_MAX 32767
 
+/*
+	TODO: Some kind of a thing that stores arbitary data related to
+	      2D coordinate points
+*/
+
 #endif