aboutsummaryrefslogtreecommitdiff
path: root/src/script
Commit message (Collapse)AuthorAge
* Fix some reference counters (memleak) (#8981)SmallJoker2019-09-24
| | | | | Fix some reference counters (memleak) Map::dispatchEvent: Allocation safety using references
* Punchwear (improved) (#8959)sfan52019-09-22
|
* Fix AreaStore's IDs persistence (#8888)SmallJoker2019-09-21
| | | | | Improve documentation Read old formats Fix free ID function. Return first gap in map
* Wieldhand: Specify which ItemStack to use (#8961)SmallJoker2019-09-21
| | | Makes 'get_wield_item' to return the "main" ItemStack
* Add support for per-player FOV overrides and multipliersAnand S2019-09-19
|
* Formspecs: Introduce formspec_version to modsSmallJoker2019-09-14
|
* CSM: Fix itemstack:get_meta() 'metadata' indexing errorSmallJoker2019-09-14
|
* Load CSM environment after the restrictions are knownSmallJoker2019-09-14
| | | | | | | Safety-guards for CSM callbacks to abort on a bad implementation Only run callbacks when the mods are loaded (and with it: builtin) Duplication checks inside constructors
* Inventory: Send dirty lists where appropriate (#8742)SmallJoker2019-08-24
| | | | | This change reduces the amount of sent data towards clients. Inventory lists that are already known to the player are skipped, saving quite some data over time. Raises protocol version to 38 to ensure correct backwards-compatible code.
* Add ItemStack:get_description() to get tooltip (#8847)Paul Ouellette2019-08-24
|
* Add function `minetest.read_schematic`upsilon2019-08-14
|
* Add support for set_formspec_prepend in main menu (#8611)rubenwardy2019-08-12
|
* Fix some issues with minetest.clear_craft (#8712)Paul Ouellette2019-08-10
| | | | | | | | | | | * Fix some issues with minetest.clear_craft - Fix memory leak - Fix crafts with an output count not being cleared when clearing by input. - Fix recipe list being reversed when clearing by input. * Add CraftInput::empty()
* Merge pull request #8776 from osjc/FixGetNodeJozef Behran2019-08-10
| | | Finish getNode cleanup
* Implement adding velocity to player from Luasfan52019-08-10
| | | | The intended usecase is knockback, but there's potential for more.
* Allow customizing chat message format (#8529)ANAND2019-08-08
|
* Unify wield item handling (#8677)SmallJoker2019-08-07
| | | | This moves the wield item functions to Player and the tool utils for range calculation Also 'local_inventory' was removed due to redundancy in Client
* Do not add group values of zero to group lists. (#8751)Beha2019-08-07
| | | | | | | | | | This fixes an issue where when the engine looked up groups (for example, in ABM node names), NodeDefManager's m_group_to_items would contain nodes with a group value of zero, resulting in nodes with flammable = 0 being burned by a fire mod with a group:flammable checking ABM. It brings consistency to the behaviour described in the api documentation, where zero and nil groups should be the same.
* Move the clamping of hp/breath when their maximums change to ↵Beha2019-07-30
| | | | | read_object_properties(). (#8689) This prevents set_properties() calls that have nothing to do with hp_max or breath_max overriding the saved hp before another mod has the chance to set a player's intended hp_max (such as in on_joinplayer).
* Check for 'action' field in ABMs & LBMsSmallJoker2019-07-27
|
* Removed debug.upvaluejoin to prevent leak of insecure environmenty2019-07-24
|
* HTTP API: Allow binary downloads and headers (#8573)SmallJoker2019-06-06
| | | | Add minetest.features.httpfetch_binary_data
* Fix forgotten PlayerSAO cast in a90f2efSmallJoker2019-05-21
|
* Check for out-of-bounds breath when setting breath_max (#8493)ANAND ツ2019-05-21
|
* l_mapgen.cpp: Fix LINT broken since b1b40feSmallJoker2019-05-21
|
* Allow multiple cave liquids in a biome definition (#8481)Paramat2019-05-18
| | | | | | | | | | | | | This allows games to specify biome cave liquids and avoid the old hardcoded behaviour, but preserves the ability to have multiple cave liquids in one biome, such as lava and water. When multiple cave liquids are defined by the biome definition, make each entire cave use a randomly chosen liquid, instead of every small cave segment using a randomly chosen liquid. Plus an optimisation: Don't place nodes if cave liquid is defined as 'air'
* Move HTTP request logging to infostream (#8526)ANAND ︻气デ═一2019-05-12
|
* Force send a mapblock to a player (#8140)sofar2019-04-28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Force send a mapblock to a player. Send a single mapblock to a specific remote player. This is badly needed for mods and games where players are teleported into terrain which may be not generated, loaded, or modified significantly since the last player visit. In all these cases, the player currently ends up in void, air, or inside blocks which not only looks bad, but has the effect that the player might end up falling and then the server needs to correct for the player position again later, which is a hack. The best solution is to send at least the single mapblock that the player will be teleported to. I've tested this with ITB which does this all the time, and I can see it functioning as expected (it even shows a half loaded entry hallway, as the further blocks aren't loaded yet). The parameter is a blockpos (table of x, y, z), not a regular pos. The function may return false if the call failed. This is most likely due to the target position not being generated or emerged yet, or another internal failure, such as the player not being initialized. * Always send mapblock on teleport or respawn. This avoids the need for mods to send a mapblock on teleport or respawn, since any call to `player:set_pos()` will pass this code.
* Add node field to PlayerHPChangeReason table (#8368)Paul Ouellette2019-04-11
|
* Add deprecation warnings for ObjectRef:get/set_attribute (#8443)ANAND2019-04-07
|
* HPChange Reason: Fix push after free, and type being overwritten (#8359)rubenwardy2019-03-12
| | | | | | * HPChange Reason: Fix push after free, and type being overwritten Fixes #8227 and #8344
* Abort when trying to set a not registered node (#7011)HybridDog2019-03-07
| | | | | | I removed the MapNode constructor which takes a nodename and gives the node's id or CONTENT_IGNORE The code which used this constructor (two places) now handles the situation of not registered nodes correctly: * minetest.set_node and similar functions make minetest crash when a not registered node is passed * reverting a node with rollback aborts if the node is not registered
* Hide uninstall package button on unmodifiable paths (#8255)rubenwardy2019-03-05
|
* Fix particle spawners not visible since CSM spawner implementation (#8289)Loïc Blot2019-03-01
| | | | | * Drop the ID mapper, use a big u64 instead. This will permit to resync server ids properly with the manager code * Modernize some code parts (std::unordered_map, auto) * generate id on client part on U32_MAX + 1 ids, lower are for server ids
* Revert "Revert CSM particles commit to fix particle spawner bug for 5.0.0 ↵Loïc Blot2019-02-26
| | | | | | (#8288)" This reverts commit 01cd63bd3bca0192dab2834faf414b022706a77e.
* Revert CSM particles commit to fix particle spawner bug for 5.0.0 (#8288)Paramat2019-02-26
| | | | Reverts 5dab7426451842793b183fbd961ad2ae83c8acbd "[CSM] Add functions to create particles and particlespawners."
* Fix extract zip writing lowercase files (#8221)rubenwardy2019-02-14
|
* Consistent HP and damage types (#8167)SmallJoker2019-02-10
| | | | | Remove deprecated HUDs and chat message handling. Remove unused m_damage variable (compat break). HP: s32 for setter/calculations, u16 for getter.
* Content store: Fix storage leak by storing screenshots in cache (#8137)rubenwardy2019-01-31
|
* Fix pkgmgr game install with RUN_IN_PLACE=0 (#8113)Paul Ouellette2019-01-26
|
* Fix wrong code comment (#8061)DS2019-01-06
| | | "Get core.registered_on_chat_messages" to "Get core.registered_on_player_receive_fields" where `core.registered_on_player_receive_fields` is gotten
* Fix various bugs (Anticheat, Lua helpers) (#8013)SmallJoker2019-01-06
| | | | | | | | | | | * Fix various bugs (Anticheat, Lua helpers) Anticheat: Use camera position instead of player position for shoot line calculations Lua helpers: Increase 'i' to not overwrite earlier added table values * Remove lag compensation * * 1.5 for larger selection boxes
* Proselytize the network. Use IEEE F32 (#8030)SmallJoker2019-01-03
| | | | | * Proselytize the network. Use IEEE F32 * Remove unused V2F1000 functions
* Add minetest.load_area (#8023)HybridDog2018-12-31
|
* CSM: add requested CSM_RF_READ_PLAYERINFO (#8007)Loïc Blot2018-12-24
| | | | | | | | * CSM: add requested CSM_RF_READ_PLAYERINFO This new CSM limit permit to limit PLAYERINFO read from server. It affects get_player_names call
* reportMetadataChange; Silence clang warningsSmallJoker2018-12-21
|
* Fix ContentDB packages timing out by using download_file instead (#7891)rubenwardy2018-12-11
|
* Send only changed node metadata to clients instead of whole mapblock (#5268)SmallJoker2018-12-04
| | | | | | | Includes newer style changes and fixes by est31 Improve the block position de-serialization Add type NodeMetadataMap
* Move client-specific files to 'src/client' (#7902)Quentin Bazin2018-11-28
| | | | | Update Android.mk Remove 'src/client' from include_directories
* Clean up stack after script_get_backtrace (#7854)Michael Muller2018-11-28
| | | | | | | | script_get_backtrace() was leaving its return value on the stack, corrupting subsequent lua operations for functions that did not immediately return. This problem can specifically be observed in the case of multiple "groupcaps" entries, each of which provides the legacy "maxwear" property. These cause a backtrace and thus pollute the stack for the following lua_next() call.
025' href='#n1025'>1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334
/*
Minetest
Copyright (C) 2010-2013 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 Lesser General Public License as published by
the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.

You should have received a copy of the GNU Lesser 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"
#include "mapblock.h"
#include "map.h"

namespace voxalgo
{

/*!
 * A direction.
 * 0=X+
 * 1=Y+
 * 2=Z+
 * 3=Z-
 * 4=Y-
 * 5=X-
 * 6=no direction
 * Two directions are 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 (block coordinates).
 * 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;
	//! Pointer to the node's block.
	MapBlock *block = NULL;
	/*!
	 * Direction from the node that caused this node's changing
	 * to this node.
	 */
	direction source_direction = 6;

	ChangingLight() = default;

	ChangingLight(const relative_v3 &rel_pos, const 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, const relative_v3 &rel_pos,
		const mapblock_v3 &block_pos, MapBlock *block,
		direction source_dir)
	{
		assert(light <= LIGHT_SUN);
		lights[light].emplace_back(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 step_rel_block_pos(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 unspread_light(Map *map, const NodeDefManager *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 (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
				neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
				if (neighbor_block == NULL) {
					current.block->setLightingComplete(bank, i, false);
					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 spread_light(Map *map, const NodeDefManager *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 (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
				neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
				if (neighbor_block == NULL) {
					current.block->setLightingComplete(bank, i, false);
					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;
					}
				}
			}
		}
	}
}

struct SunlightPropagationUnit{
	v2s16 relative_pos;
	bool is_sunlit;

	SunlightPropagationUnit(v2s16 relpos, bool sunlit):
		relative_pos(relpos),
		is_sunlit(sunlit)
	{}
};

struct SunlightPropagationData{
	std::vector<SunlightPropagationUnit> data;
	v3s16 target_block;
};

/*!
 * Returns true if the node gets sunlight from the
 * node above it.
 *
 * \param pos position of the node.
 */
bool is_sunlight_above(Map *map, v3s16 pos, const NodeDefManager *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_nodes(Map *map,
	std::vector<std::pair<v3s16, MapNode> > &oldnodes,
	std::map<v3s16, MapBlock*> &modified_blocks)
{
	const NodeDefManager *ndef = map->getNodeDefManager();
	// For node getter functions
	bool is_valid_position;

	// Process each light bank separately
	for (LightBank bank : banks) {
		UnlightQueue disappearing_lights(256);
		ReLightQueue light_sources(256);
		// Nodes that are brighter than the brightest modified node was
		// won't change, since they didn't get their light from a
		// modified node.
		u8 min_safe_light = 0;
		for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
				oldnodes.begin(); it < oldnodes.end(); ++it) {
			u8 old_light = it->second.getLight(bank, ndef);
			if (old_light > min_safe_light) {
				min_safe_light = old_light;
			}
		}
		// If only one node changed, even nodes with the same brightness
		// didn't get their light from the changed node.
		if (oldnodes.size() > 1) {
			min_safe_light++;
		}
		// For each changed node process sunlight and initialize
		for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
				oldnodes.begin(); it < oldnodes.end(); ++it) {
			// Get position and block of the changed node
			v3s16 p = it->first;
			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()) {
				continue;
			}
			// Get the new node
			MapNode n = block->getNodeNoCheck(rel_pos, &is_valid_position);
			if (!is_valid_position) {
				break;
			}

			// Light of the old node
			u8 old_light = it->second.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
					&& is_sunlight_above(map, p, ndef)) {
					new_light = LIGHT_SUN;
				} else {
					new_light = ndef->get(n).light_source;
					for (const v3s16 &neighbor_dir : neighbor_dirs) {
						v3s16 p2 = p + neighbor_dir;
						bool is_valid;
						MapNode n2 = map->getNode(p2, &is_valid);
						if (is_valid) {
							u8 spread = n2.getLight(bank, ndef);
							// If it is sure that the neighbor won't be
							// unlighted, its light can spread to this node.
							if (spread > new_light && spread >= min_safe_light) {
								new_light = spread - 1;
							}
						}
					}
				}
			} else {
				// If this is an opaque node, it still can emit light.
				new_light = ndef->get(n).light_source;
			}

			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.

				// 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->getNode(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 */);
					}
				}
			} 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->getNode(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);
					}
				}
			}

		}
		// Remove lights
		unspread_light(map, ndef, bank, disappearing_lights, light_sources,
			modified_blocks);
		// 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.
		spread_light(map, ndef, bank, light_sources, modified_blocks);
	}
}

/*!
 * Borders of a map block in relative node coordinates.
 * Compatible with type 'direction'.
 */
const VoxelArea block_borders[] = {
	VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
	VoxelArea(v3s16(0, 15, 0), v3s16(15, 15, 15)), //Y+
	VoxelArea(v3s16(0, 0, 15), v3s16(15, 15, 15)), //Z+
	VoxelArea(v3s16(0, 0, 0), v3s16(15, 15, 0)),   //Z-
	VoxelArea(v3s16(0, 0, 0), v3s16(15, 0, 15)),   //Y-
	VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15))    //X-
};

/*!
 * Returns true if:
 * -the node has unloaded neighbors
 * -the node doesn't have light
 * -the node's light is the same as the maximum of
 * its light source and its brightest neighbor minus one.
 * .
 */
bool is_light_locally_correct(Map *map, const NodeDefManager *ndef,
	LightBank bank, v3s16 pos)
{
	bool is_valid_position;
	MapNode n = map->getNode(pos, &is_valid_position);
	const ContentFeatures &f = ndef->get(n);
	if (f.param_type != CPT_LIGHT) {
		return true;
	}
	u8 light = n.getLightNoChecks(bank, &f);
	assert(f.light_source <= LIGHT_MAX);
	u8 brightest_neighbor = f.light_source + 1;
	for (const v3s16 &neighbor_dir : neighbor_dirs) {
		MapNode n2 = map->getNode(pos + neighbor_dir,
			&is_valid_position);
		u8 light2 = n2.getLight(bank, ndef);
		if (brightest_neighbor < light2) {
			brightest_neighbor = light2;
		}
	}
	assert(light <= LIGHT_SUN);
	return brightest_neighbor == light + 1;
}

void update_block_border_lighting(Map *map, MapBlock *block,
	std::map<v3s16, MapBlock*> &modified_blocks)
{
	const NodeDefManager *ndef = map->getNodeDefManager();
	bool is_valid_position;
	for (LightBank bank : banks) {
		// Since invalid light is not common, do not allocate
		// memory if not needed.
		UnlightQueue disappearing_lights(0);
		ReLightQueue light_sources(0);
		// Get incorrect lights
		for (direction d = 0; d < 6; d++) {
			// For each direction
			// Get neighbor block
			v3s16 otherpos = block->getPos() + neighbor_dirs[d];
			MapBlock *other = map->getBlockNoCreateNoEx(otherpos);
			if (other == NULL) {
				continue;
			}
			// Only update if lighting was not completed.
			if (block->isLightingComplete(bank, d) &&
					other->isLightingComplete(bank, 5 - d))
				continue;
			// Reset flags
			block->setLightingComplete(bank, d, true);
			other->setLightingComplete(bank, 5 - d, true);
			// The two blocks and their connecting surfaces
			MapBlock *blocks[] = {block, other};
			VoxelArea areas[] = {block_borders[d], block_borders[5 - d]};
			// For both blocks
			for (u8 blocknum = 0; blocknum < 2; blocknum++) {
				MapBlock *b = blocks[blocknum];
				VoxelArea a = areas[blocknum];
				// For all nodes
				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++) {
					MapNode n = b->getNodeNoCheck(x, y, z,
						&is_valid_position);
					u8 light = n.getLight(bank, ndef);
					// Sunlight is fixed
					if (light < LIGHT_SUN) {
						// Unlight if not correct
						if (!is_light_locally_correct(map, ndef, bank,
								v3s16(x, y, z) + b->getPosRelative())) {
							// Initialize for unlighting
							n.setLight(bank, 0, ndef);
							b->setNodeNoCheck(x, y, z, n);
							modified_blocks[b->getPos()]=b;
							disappearing_lights.push(light,
								relative_v3(x, y, z), b->getPos(), b,
								6);
						}
					}
				}
			}
		}
		// Remove lights
		unspread_light(map, ndef, bank, disappearing_lights, light_sources,
			modified_blocks);
		// 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.
		spread_light(map, ndef, bank, light_sources, modified_blocks);
	}
}

/*!
 * Resets the lighting of the given VoxelManipulator to
 * complete darkness and full sunlight.
 * Operates in one map sector.
 *
 * \param offset contains the least x and z node coordinates
 * of the map sector.
 * \param light incoming sunlight, light[x][z] is true if there
 * is sunlight above the voxel manipulator at the given x-z coordinates.
 * The array's indices are relative node coordinates in the sector.
 * After the procedure returns, this contains outgoing light at
 * the bottom of the voxel manipulator.
 */
void fill_with_sunlight(MMVManip *vm, const NodeDefManager *ndef, v2s16 offset,
	bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
{
	// Distance in array between two nodes on top of each other.
	s16 ystride = vm->m_area.getExtent().X;
	// Cache the ignore node.
	MapNode ignore = MapNode(CONTENT_IGNORE);
	// For each column of nodes:
	for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
	for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
		// Position of the column on the map.
		v2s16 realpos = offset + v2s16(x, z);
		// Array indices in the voxel manipulator
		s32 maxindex = vm->m_area.index(realpos.X, vm->m_area.MaxEdge.Y,
			realpos.Y);
		s32 minindex = vm->m_area.index(realpos.X, vm->m_area.MinEdge.Y,
			realpos.Y);
		// True if the current node has sunlight.
		bool lig = light[z][x];
		// For each node, downwards:
		for (s32 i = maxindex; i >= minindex; i -= ystride) {
			MapNode *n;
			if (vm->m_flags[i] & VOXELFLAG_NO_DATA)
				n = &ignore;
			else
				n = &vm->m_data[i];
			// Ignore IGNORE nodes, these are not generated yet.
			if(n->getContent() == CONTENT_IGNORE)
				continue;
			const ContentFeatures &f = ndef->get(n->getContent());
			if (lig && !f.sunlight_propagates)
				// Sunlight is stopped.
				lig = false;
			// Reset light
			n->setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
			n->setLight(LIGHTBANK_NIGHT, 0, f);
		}
		// Output outgoing light.
		light[z][x] = lig;
	}
}

/*!
 * Returns incoming sunlight for one map block.
 * If block above is not found, it is loaded.
 *
 * \param pos position of the map block that gets the sunlight.
 * \param light incoming sunlight, light[z][x] is true if there
 * is sunlight above the block at the given z-x relative
 * node coordinates.
 */
void is_sunlight_above_block(ServerMap *map, mapblock_v3 pos,
	const NodeDefManager *ndef, bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
{
	mapblock_v3 source_block_pos = pos + v3s16(0, 1, 0);
	// Get or load source block.
	// It might take a while to load, but correcting incorrect
	// sunlight may be even slower.
	MapBlock *source_block = map->emergeBlock(source_block_pos, false);
	// Trust only generated blocks.
	if (source_block == NULL || source_block->isDummy()
			|| !source_block->isGenerated()) {
		// But if there is no block above, then use heuristics
		bool sunlight = true;
		MapBlock *node_block = map->getBlockNoCreateNoEx(pos);
		if (node_block == NULL)
			// This should not happen.
			sunlight = false;
		else
			sunlight = !node_block->getIsUnderground();
		for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
		for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
			light[z][x] = sunlight;
	} else {
		// Dummy boolean, the position is valid.
		bool is_valid_position;
		// For each column:
		for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
		for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
			// Get the bottom block.
			MapNode above = source_block->getNodeNoCheck(x, 0, z,
				&is_valid_position);
			light[z][x] = above.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN;
		}
	}
}

/*!
 * Propagates sunlight down in a given map block.
 *
 * \param data contains incoming sunlight and shadow and
 * the coordinates of the target block.
 * \param unlight propagated shadow is inserted here
 * \param relight propagated sunlight is inserted here
 *
 * \returns true if the block was modified, false otherwise.
 */
bool propagate_block_sunlight(Map *map, const NodeDefManager *ndef,
	SunlightPropagationData *data, UnlightQueue *unlight, ReLightQueue *relight)
{
	bool modified = false;
	// Get the block.
	MapBlock *block = map->getBlockNoCreateNoEx(data->target_block);
	if (block == NULL || block->isDummy()) {
		// The work is done if the block does not contain data.
		data->data.clear();
		return false;
	}
	// Dummy boolean
	bool is_valid;
	// For each changing column of nodes:
	size_t index;
	for (index = 0; index < data->data.size(); index++) {
		SunlightPropagationUnit it = data->data[index];
		// Relative position of the currently inspected node.
		relative_v3 current_pos(it.relative_pos.X, MAP_BLOCKSIZE - 1,
			it.relative_pos.Y);
		if (it.is_sunlit) {
			// Propagate sunlight.
			// For each node downwards:
			for (; current_pos.Y >= 0; current_pos.Y--) {
				MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
				const ContentFeatures &f = ndef->get(n);
				if (n.getLightRaw(LIGHTBANK_DAY, f) < LIGHT_SUN
						&& f.sunlight_propagates) {
					// This node gets sunlight.
					n.setLight(LIGHTBANK_DAY, LIGHT_SUN, f);
					block->setNodeNoCheck(current_pos, n);
					modified = true;
					relight->push(LIGHT_SUN, current_pos, data->target_block,
						block, 4);
				} else {
					// Light already valid, propagation stopped.
					break;
				}
			}
		} else {
			// Propagate shadow.
			// For each node downwards:
			for (; current_pos.Y >= 0; current_pos.Y--) {
				MapNode n = block->getNodeNoCheck(current_pos, &is_valid);
				const ContentFeatures &f = ndef->get(n);
				if (n.getLightRaw(LIGHTBANK_DAY, f) == LIGHT_SUN) {
					// The sunlight is no longer valid.
					n.setLight(LIGHTBANK_DAY, 0, f);
					block->setNodeNoCheck(current_pos, n);
					modified = true;
					unlight->push(LIGHT_SUN, current_pos, data->target_block,
						block, 4);
				} else {
					// Reached shadow, propagation stopped.
					break;
				}
			}
		}
		if (current_pos.Y >= 0) {
			// Propagation stopped, remove from data.
			data->data[index] = data->data.back();
			data->data.pop_back();
			index--;
		}
	}
	return modified;
}

/*!
 * Borders of a map block in relative node coordinates.
 * The areas do not overlap.
 * Compatible with type 'direction'.
 */
const VoxelArea block_pad[] = {
	VoxelArea(v3s16(15, 0, 0), v3s16(15, 15, 15)), //X+
	VoxelArea(v3s16(1, 15, 0), v3s16(14, 15, 15)), //Y+
	VoxelArea(v3s16(1, 1, 15), v3s16(14, 14, 15)), //Z+
	VoxelArea(v3s16(1, 1, 0), v3s16(14, 14, 0)),   //Z-
	VoxelArea(v3s16(1, 0, 0), v3s16(14, 0, 15)),   //Y-
	VoxelArea(v3s16(0, 0, 0), v3s16(0, 15, 15))    //X-
};

/*!
 * The common part of bulk light updates - it is always executed.
 * The procedure takes the nodes that should be unlit, and the
 * full modified area.
 *
 * The procedure handles the correction of all lighting except
 * direct sunlight spreading.
 *
 * \param minblock least coordinates of the changed area in block
 * coordinates
 * \param maxblock greatest coordinates of the changed area in block
 * coordinates
 * \param unlight the first queue is for day light, the second is for
 * night light. Contains all nodes on the borders that need to be unlit.
 * \param relight the first queue is for day light, the second is for
 * night light. Contains nodes that were not modified, but got sunlight
 * because the changes.
 * \param modified_blocks the procedure adds all modified blocks to
 * this map
 */
void finish_bulk_light_update(Map *map, mapblock_v3 minblock,
	mapblock_v3 maxblock, UnlightQueue unlight[2], ReLightQueue relight[2],
	std::map<v3s16, MapBlock*> *modified_blocks)
{
	const NodeDefManager *ndef = map->getNodeDefManager();
	// dummy boolean
	bool is_valid;

	// --- STEP 1: Do unlighting

	for (size_t bank = 0; bank < 2; bank++) {
		LightBank b = banks[bank];
		unspread_light(map, ndef, b, unlight[bank], relight[bank],
			*modified_blocks);
	}

	// --- STEP 2: Get all newly inserted light sources

	// For each block:
	v3s16 blockpos;
	v3s16 relpos;
	for (blockpos.X = minblock.X; blockpos.X <= maxblock.X; blockpos.X++)
	for (blockpos.Y = minblock.Y; blockpos.Y <= maxblock.Y; blockpos.Y++)
	for (blockpos.Z = minblock.Z; blockpos.Z <= maxblock.Z; blockpos.Z++) {
		MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
		if (!block || block->isDummy())
			// Skip not existing blocks
			continue;
		// For each node in the block:
		for (relpos.X = 0; relpos.X < MAP_BLOCKSIZE; relpos.X++)
		for (relpos.Z = 0; relpos.Z < MAP_BLOCKSIZE; relpos.Z++)
		for (relpos.Y = 0; relpos.Y < MAP_BLOCKSIZE; relpos.Y++) {
			MapNode node = block->getNodeNoCheck(relpos.X, relpos.Y, relpos.Z, &is_valid);
			const ContentFeatures &f = ndef->get(node);

			// For each light bank
			for (size_t b = 0; b < 2; b++) {
				LightBank bank = banks[b];
				u8 light = f.param_type == CPT_LIGHT ?
					node.getLightNoChecks(bank, &f):
					f.light_source;
				if (light > 1)
					relight[b].push(light, relpos, blockpos, block, 6);
			} // end of banks
		} // end of nodes
	} // end of blocks

	// --- STEP 3: do light spreading

	// For each light bank:
	for (size_t b = 0; b < 2; b++) {
		LightBank bank = banks[b];
		// Sunlight is already initialized.
		u8 maxlight = (b == 0) ? LIGHT_MAX : LIGHT_SUN;
		// Initialize light values for light spreading.
		for (u8 i = 0; i <= maxlight; i++) {
			const std::vector<ChangingLight> &lights = relight[b].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);
				n.setLight(bank, i, ndef);
				it->block->setNodeNoCheck(it->rel_position, n);
			}
		}
		// Spread lights.
		spread_light(map, ndef, bank, relight[b], *modified_blocks);
	}
}

void blit_back_with_light(ServerMap *map, MMVManip *vm,
	std::map<v3s16, MapBlock*> *modified_blocks)
{
	const NodeDefManager *ndef = map->getNodeDefManager();
	mapblock_v3 minblock = getNodeBlockPos(vm->m_area.MinEdge);
	mapblock_v3 maxblock = getNodeBlockPos(vm->m_area.MaxEdge);
	// First queue is for day light, second is for night light.
	UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
	ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
	// Will hold sunlight data.
	bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
	SunlightPropagationData data;
	// Dummy boolean.
	bool is_valid;

	// --- STEP 1: reset everything to sunlight

	// For each map block:
	for (s16 x = minblock.X; x <= maxblock.X; x++)
	for (s16 z = minblock.Z; z <= maxblock.Z; z++) {
		// Extract sunlight above.
		is_sunlight_above_block(map, v3s16(x, maxblock.Y, z), ndef, lights);
		v2s16 offset(x, z);
		offset *= MAP_BLOCKSIZE;
		// Reset the voxel manipulator.
		fill_with_sunlight(vm, ndef, offset, lights);
		// Copy sunlight data
		data.target_block = v3s16(x, minblock.Y - 1, z);
		for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
		for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
			data.data.emplace_back(v2s16(x, z), lights[z][x]);
		// Propagate sunlight and shadow below the voxel manipulator.
		while (!data.data.empty()) {
			if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
					&relight[0]))
				(*modified_blocks)[data.target_block] =
					map->getBlockNoCreateNoEx(data.target_block);
			// Step downwards.
			data.target_block.Y--;
		}
	}

	// --- STEP 2: Get nodes from borders to unlight
	v3s16 blockpos;
	v3s16 relpos;

	// In case there are unloaded holes in the voxel manipulator
	// unlight each block.
	// For each block:
	for (blockpos.X = minblock.X; blockpos.X <= maxblock.X; blockpos.X++)
	for (blockpos.Y = minblock.Y; blockpos.Y <= maxblock.Y; blockpos.Y++)
	for (blockpos.Z = minblock.Z; blockpos.Z <= maxblock.Z; blockpos.Z++) {
		MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
		if (!block || block->isDummy())
			// Skip not existing blocks.
			continue;
		v3s16 offset = block->getPosRelative();
		// For each border of the block:
		for (const VoxelArea &a : block_pad) {
			// For each node of the border:
			for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
			for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
			for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {

				// Get old and new node
				MapNode oldnode = block->getNodeNoCheck(relpos, &is_valid);
				const ContentFeatures &oldf = ndef->get(oldnode);
				MapNode newnode = vm->getNodeNoExNoEmerge(relpos + offset);
				const ContentFeatures &newf = oldnode == newnode ? oldf :
					ndef->get(newnode);

				// For each light bank
				for (size_t b = 0; b < 2; b++) {
					LightBank bank = banks[b];
					u8 oldlight = oldf.param_type == CPT_LIGHT ?
						oldnode.getLightNoChecks(bank, &oldf):
						LIGHT_SUN; // no light information, force unlighting
					u8 newlight = newf.param_type == CPT_LIGHT ?
						newnode.getLightNoChecks(bank, &newf):
						newf.light_source;
					// If the new node is dimmer, unlight.
					if (oldlight > newlight) {
						unlight[b].push(
							oldlight, relpos, blockpos, block, 6);
					}
				} // end of banks
			} // end of nodes
		} // end of borders
	} // end of blocks

	// --- STEP 3: All information extracted, overwrite

	vm->blitBackAll(modified_blocks, true);

	// --- STEP 4: Finish light update

	finish_bulk_light_update(map, minblock, maxblock, unlight, relight,
		modified_blocks);
}

/*!
 * Resets the lighting of the given map block to
 * complete darkness and full sunlight.
 *
 * \param light incoming sunlight, light[x][z] is true if there
 * is sunlight above the map block at the given x-z coordinates.
 * The array's indices are relative node coordinates in the block.
 * After the procedure returns, this contains outgoing light at
 * the bottom of the map block.
 */
void fill_with_sunlight(MapBlock *block, const NodeDefManager *ndef,
	bool light[MAP_BLOCKSIZE][MAP_BLOCKSIZE])
{
	if (block->isDummy())
		return;
	// dummy boolean
	bool is_valid;
	// For each column of nodes:
	for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
	for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
		// True if the current node has sunlight.
		bool lig = light[z][x];
		// For each node, downwards:
		for (s16 y = MAP_BLOCKSIZE - 1; y >= 0; y--) {
			MapNode n = block->getNodeNoCheck(x, y, z, &is_valid);
			// Ignore IGNORE nodes, these are not generated yet.
			if (n.getContent() == CONTENT_IGNORE)
				continue;
			const ContentFeatures &f = ndef->get(n.getContent());
			if (lig && !f.sunlight_propagates) {
				// Sunlight is stopped.
				lig = false;
			}
			// Reset light
			n.setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
			n.setLight(LIGHTBANK_NIGHT, 0, f);
			block->setNodeNoCheck(x, y, z, n);
		}
		// Output outgoing light.
		light[z][x] = lig;
	}
}

void repair_block_light(ServerMap *map, MapBlock *block,
	std::map<v3s16, MapBlock*> *modified_blocks)
{
	if (!block || block->isDummy())
		return;
	const NodeDefManager *ndef = map->getNodeDefManager();
	// First queue is for day light, second is for night light.
	UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
	ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
	// Will hold sunlight data.
	bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
	SunlightPropagationData data;
	// Dummy boolean.
	bool is_valid;

	// --- STEP 1: reset everything to sunlight

	mapblock_v3 blockpos = block->getPos();
	(*modified_blocks)[blockpos] = block;
	// For each map block:
	// Extract sunlight above.
	is_sunlight_above_block(map, blockpos, ndef, lights);
	// Reset the voxel manipulator.
	fill_with_sunlight(block, ndef, lights);
	// Copy sunlight data
	data.target_block = v3s16(blockpos.X, blockpos.Y - 1, blockpos.Z);
	for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
	for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
		data.data.emplace_back(v2s16(x, z), lights[z][x]);
	}
	// Propagate sunlight and shadow below the voxel manipulator.
	while (!data.data.empty()) {
		if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
				&relight[0]))
			(*modified_blocks)[data.target_block] =
				map->getBlockNoCreateNoEx(data.target_block);
		// Step downwards.
		data.target_block.Y--;
	}

	// --- STEP 2: Get nodes from borders to unlight

	// For each border of the block:
	for (const VoxelArea &a : block_pad) {
		v3s16 relpos;
		// For each node of the border:
		for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
		for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
		for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {

			// Get node
			MapNode node = block->getNodeNoCheck(relpos, &is_valid);
			const ContentFeatures &f = ndef->get(node);
			// For each light bank
			for (size_t b = 0; b < 2; b++) {
				LightBank bank = banks[b];
				u8 light = f.param_type == CPT_LIGHT ?
					node.getLightNoChecks(bank, &f):
					f.light_source;
				// If the new node is dimmer than sunlight, unlight.
				// (if it has maximal light, it is pointless to remove
				// surrounding light, as it can only become brighter)
				if (LIGHT_SUN > light) {
					unlight[b].push(
						LIGHT_SUN, relpos, blockpos, block, 6);
				}
			} // end of banks
		} // end of nodes
	} // end of borders

	// STEP 3: Remove and spread light

	finish_bulk_light_update(map, blockpos, blockpos, unlight, relight,
		modified_blocks);
}

VoxelLineIterator::VoxelLineIterator(const v3f &start_position, const v3f &line_vector) :
	m_start_position(start_position),
	m_line_vector(line_vector)
{
	m_current_node_pos = floatToInt(m_start_position, 1);
	m_start_node_pos = m_current_node_pos;
	m_last_index = getIndex(floatToInt(start_position + line_vector, 1));

	if (m_line_vector.X > 0) {
		m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5) + 1.5
			- m_start_position.X) / m_line_vector.X;
		m_intersection_multi_inc.X = 1 / m_line_vector.X;
	} else if (m_line_vector.X < 0) {
		m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5)
			- m_start_position.X + 0.5) / m_line_vector.X;
		m_intersection_multi_inc.X = -1 / m_line_vector.X;
		m_step_directions.X = -1;
	}

	if (m_line_vector.Y > 0) {
		m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5) + 1.5
			- m_start_position.Y) / m_line_vector.Y;
		m_intersection_multi_inc.Y = 1 / m_line_vector.Y;
	} else if (m_line_vector.Y < 0) {
		m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5)
			- m_start_position.Y + 0.5) / m_line_vector.Y;
		m_intersection_multi_inc.Y = -1 / m_line_vector.Y;
		m_step_directions.Y = -1;
	}

	if (m_line_vector.Z > 0) {
		m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5) + 1.5
			- m_start_position.Z) / m_line_vector.Z;
		m_intersection_multi_inc.Z = 1 / m_line_vector.Z;
	} else if (m_line_vector.Z < 0) {
		m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5)
			- m_start_position.Z + 0.5) / m_line_vector.Z;
		m_intersection_multi_inc.Z = -1 / m_line_vector.Z;
		m_step_directions.Z = -1;
	}
}

void VoxelLineIterator::next()
{
	m_current_index++;
	if ((m_next_intersection_multi.X < m_next_intersection_multi.Y)
			&& (m_next_intersection_multi.X < m_next_intersection_multi.Z)) {
		m_next_intersection_multi.X += m_intersection_multi_inc.X;
		m_current_node_pos.X += m_step_directions.X;
	} else if ((m_next_intersection_multi.Y < m_next_intersection_multi.Z)) {
		m_next_intersection_multi.Y += m_intersection_multi_inc.Y;
		m_current_node_pos.Y += m_step_directions.Y;
	} else {
		m_next_intersection_multi.Z += m_intersection_multi_inc.Z;
		m_current_node_pos.Z += m_step_directions.Z;
	}
}

s16 VoxelLineIterator::getIndex(v3s16 voxel){
	return
		abs(voxel.X - m_start_node_pos.X) +
		abs(voxel.Y - m_start_node_pos.Y) +
		abs(voxel.Z - m_start_node_pos.Z);
}

} // namespace voxalgo