Line_of_sight: Improve using VoxelLineIterator

juhdanad · paramat · commit 2153965cf92a · 2017-12-26T21:51:32.000Z
This commit rewrites line_of_sight with VoxelLineIterator.
Stepsize is no longer needed, the results will be always accurate.
diff --git a/doc/lua_api.txt b/doc/lua_api.txt
@@ -2876,13 +2876,12 @@ and `minetest.auth_reload` call the authentication handler.
     *   parameter was absent)
 * `minetest.delete_area(pos1, pos2)`
     * delete all mapblocks in the area from pos1 to pos2, inclusive
-* `minetest.line_of_sight(pos1, pos2, stepsize)`: returns `boolean, pos`
-    * Check if there is a direct line of sight between `pos1` and `pos2`
+* `minetest.line_of_sight(pos1, pos2)`: returns `boolean, pos`
+    * Checks if there is anything other than air between pos1 and pos2.
+    * Returns false if something is blocking the sight.
     * Returns the position of the blocking node when `false`
     * `pos1`: First position
     * `pos2`: Second position
-    * `stepsize`: smaller gives more accurate results but requires more computing
-      time. Default is `1`.
 * `minetest.raycast(pos1, pos2, objects, liquids)`: returns `Raycast`
     * Creates a `Raycast` object.
     * `pos1`: start of the ray
diff --git a/src/script/lua_api/l_env.cpp b/src/script/lua_api/l_env.cpp
@@ -966,24 +966,19 @@ int ModApiEnvMod::l_clear_objects(lua_State *L)
 	return 0;
 }
 
-// line_of_sight(pos1, pos2, stepsize) -> true/false, pos
+// line_of_sight(pos1, pos2) -> true/false, pos
 int ModApiEnvMod::l_line_of_sight(lua_State *L)
 {
-	float stepsize = 1.0;
-
 	GET_ENV_PTR;
 
 	// read position 1 from lua
 	v3f pos1 = checkFloatPos(L, 1);
 	// read position 2 from lua
 	v3f pos2 = checkFloatPos(L, 2);
-	//read step size from lua
-	if (lua_isnumber(L, 3)) {
-		stepsize = lua_tonumber(L, 3);
-	}
 
 	v3s16 p;
-	bool success = env->line_of_sight(pos1, pos2, stepsize, &p);
+
+	bool success = env->line_of_sight(pos1, pos2, &p);
 	lua_pushboolean(L, success);
 	if (!success) {
 		push_v3s16(L, p);
diff --git a/src/script/lua_api/l_env.h b/src/script/lua_api/l_env.h
@@ -156,7 +156,7 @@ class ModApiEnvMod : public ModApiBase {
 	// spawn_tree(pos, treedef)
 	static int l_spawn_tree(lua_State *L);
 
-	// line_of_sight(pos1, pos2, stepsize) -> true/false
+	// line_of_sight(pos1, pos2) -> true/false
 	static int l_line_of_sight(lua_State *L);
 
 	// raycast(pos1, pos2, objects, liquids) -> Raycast
diff --git a/src/serverenvironment.cpp b/src/serverenvironment.cpp
@@ -489,30 +489,21 @@ bool ServerEnvironment::removePlayerFromDatabase(const std::string &name)
 	return m_player_database->removePlayer(name);
 }
 
-bool ServerEnvironment::line_of_sight(v3f pos1, v3f pos2, float stepsize, v3s16 *p)
+bool ServerEnvironment::line_of_sight(v3f pos1, v3f pos2, v3s16 *p)
 {
-	float distance = pos1.getDistanceFrom(pos2);
-
-	//calculate normalized direction vector
-	v3f normalized_vector = v3f((pos2.X - pos1.X)/distance,
-		(pos2.Y - pos1.Y)/distance,
-		(pos2.Z - pos1.Z)/distance);
-
-	//find out if there's a node on path between pos1 and pos2
-	for (float i = 1; i < distance; i += stepsize) {
-		v3s16 pos = floatToInt(v3f(normalized_vector.X * i,
-			normalized_vector.Y * i,
-			normalized_vector.Z * i) +pos1,BS);
-
-		MapNode n = getMap().getNodeNoEx(pos);
-
-		if(n.param0 != CONTENT_AIR) {
-			if (p) {
-				*p = pos;
-			}
+	// Iterate trough nodes on the line
+	voxalgo::VoxelLineIterator iterator(pos1 / BS, (pos2 - pos1) / BS);
+	do {
+		MapNode n = getMap().getNodeNoEx(iterator.m_current_node_pos);
+
+		// Return non-air
+		if (n.param0 != CONTENT_AIR) {
+			if (p)
+				*p = iterator.m_current_node_pos;
 			return false;
 		}
-	}
+		iterator.next();
+	} while (iterator.m_current_index <= iterator.m_last_index);
 	return true;
 }
 
diff --git a/src/serverenvironment.h b/src/serverenvironment.h
@@ -328,8 +328,15 @@ class ServerEnvironment : public Environment
 	// This makes stuff happen
 	void step(f32 dtime);
 
-	//check if there's a line of sight between two positions
-	bool line_of_sight(v3f pos1, v3f pos2, float stepsize=1.0, v3s16 *p=NULL);
+	/*!
+	 * Returns false if the given line intersects with a
+	 * non-air node, true otherwise.
+	 * \param pos1 start of the line
+	 * \param pos2 end of the line
+	 * \param p output, position of the first non-air node
+	 * the line intersects
+	 */
+	bool line_of_sight(v3f pos1, v3f pos2, v3s16 *p = NULL);
 
 	u32 getGameTime() const { return m_game_time; }
 
