Implement grouped mode for find_nodes_in_area (#9888)

plus general improvements to find_node_* functions

4 files changed, 124 insertions, 83 deletions

diff --git a/doc/client_lua_api.txt b/doc/client_lua_api.txt
index 04815aaa4..3b0046b4f 100644
--- a/doc/client_lua_api.txt
+++ b/doc/client_lua_api.txt
@@ -768,12 +768,15 @@ Call these functions only at load time!
     * `nodenames`: e.g. `{"ignore", "group:tree"}` or `"default:dirt"`
     * `search_center` is an optional boolean (default: `false`)
       If true `pos` is also checked for the nodes
-* `minetest.find_nodes_in_area(pos1, pos2, nodenames)`: returns a list of
-  positions.
+* `minetest.find_nodes_in_area(pos1, pos2, nodenames, [grouped])`
+    * `pos1` and `pos2` are the min and max positions of the area to search.
     * `nodenames`: e.g. `{"ignore", "group:tree"}` or `"default:dirt"`
-    * First return value: Table with all node positions
-    * Second return value: Table with the count of each node with the node name
-      as index.
+    * If `grouped` is true the return value is a table indexed by node name
+      which contains lists of positions.
+    * If `grouped` is false or absent the return values are as follows:
+      first value: Table with all node positions
+      second value: Table with the count of each node with the node name
+      as index
     * Area volume is limited to 4,096,000 nodes
 * `minetest.find_nodes_in_area_under_air(pos1, pos2, nodenames)`: returns a
   list of positions.
diff --git a/doc/lua_api.txt b/doc/lua_api.txt
index d3a367b27..e0c895c97 100644
--- a/doc/lua_api.txt
+++ b/doc/lua_api.txt
@@ -4762,12 +4762,15 @@ Environment access
     * `nodenames`: e.g. `{"ignore", "group:tree"}` or `"default:dirt"`
     * `search_center` is an optional boolean (default: `false`)
       If true `pos` is also checked for the nodes
-* `minetest.find_nodes_in_area(pos1, pos2, nodenames)`: returns a list of
-  positions.
+* `minetest.find_nodes_in_area(pos1, pos2, nodenames, [grouped])`
+    * `pos1` and `pos2` are the min and max positions of the area to search.
     * `nodenames`: e.g. `{"ignore", "group:tree"}` or `"default:dirt"`
-    * First return value: Table with all node positions
-    * Second return value: Table with the count of each node with the node name
-      as index.
+    * If `grouped` is true the return value is a table indexed by node name
+      which contains lists of positions.
+    * If `grouped` is false or absent the return values are as follows:
+      first value: Table with all node positions
+      second value: Table with the count of each node with the node name
+      as index
     * Area volume is limited to 4,096,000 nodes
 * `minetest.find_nodes_in_area_under_air(pos1, pos2, nodenames)`: returns a
   list of positions.
diff --git a/src/script/lua_api/l_env.cpp b/src/script/lua_api/l_env.cpp
index 89ec9dc7e..b2bc8c5f6 100644
--- a/src/script/lua_api/l_env.cpp
+++ b/src/script/lua_api/l_env.cpp
@@ -752,29 +752,36 @@ int ModApiEnvMod::l_get_gametime(lua_State *L)
 	return 1;
 }
 
-
-// find_node_near(pos, radius, nodenames, search_center) -> pos or nil
-// nodenames: eg. {"ignore", "group:tree"} or "default:dirt"
-int ModApiEnvMod::l_find_node_near(lua_State *L)
+void ModApiEnvMod::collectNodeIds(lua_State *L, int idx, const NodeDefManager *ndef,
+	std::vector<content_t> &filter)
 {
-	GET_PLAIN_ENV_PTR;
-
-	const NodeDefManager *ndef = env->getGameDef()->ndef();
-	v3s16 pos = read_v3s16(L, 1);
-	int radius = luaL_checkinteger(L, 2);
-	std::vector<content_t> filter;
-	if (lua_istable(L, 3)) {
+	if (lua_istable(L, idx)) {
 		lua_pushnil(L);
-		while (lua_next(L, 3) != 0) {
+		while (lua_next(L, idx) != 0) {
 			// key at index -2 and value at index -1
 			luaL_checktype(L, -1, LUA_TSTRING);
 			ndef->getIds(readParam<std::string>(L, -1), filter);
 			// removes value, keeps key for next iteration
 			lua_pop(L, 1);
 		}
-	} else if (lua_isstring(L, 3)) {
+	} else if (lua_isstring(L, idx)) {
 		ndef->getIds(readParam<std::string>(L, 3), filter);
 	}
+}
+
+// find_node_near(pos, radius, nodenames, [search_center]) -> pos or nil
+// nodenames: eg. {"ignore", "group:tree"} or "default:dirt"
+int ModApiEnvMod::l_find_node_near(lua_State *L)
+{
+	GET_PLAIN_ENV_PTR;
+
+	const NodeDefManager *ndef = env->getGameDef()->ndef();
+	Map &map = env->getMap();
+
+	v3s16 pos = read_v3s16(L, 1);
+	int radius = luaL_checkinteger(L, 2);
+	std::vector<content_t> filter;
+	collectNodeIds(L, 3, ndef, filter);
 
 	int start_radius = (lua_isboolean(L, 4) && readParam<bool>(L, 4)) ? 0 : 1;
 
@@ -785,10 +792,10 @@ int ModApiEnvMod::l_find_node_near(lua_State *L)
 #endif
 
 	for (int d = start_radius; d <= radius; d++) {
-		std::vector<v3s16> list = FacePositionCache::getFacePositions(d);
+		const std::vector<v3s16> &list = FacePositionCache::getFacePositions(d);
 		for (const v3s16 &i : list) {
 			v3s16 p = pos + i;
-			content_t c = env->getMap().getNode(p).getContent();
+			content_t c = map.getNode(p).getContent();
 			if (CONTAINS(filter, c)) {
 				push_v3s16(L, p);
 				return 1;
@@ -798,8 +805,7 @@ int ModApiEnvMod::l_find_node_near(lua_State *L)
 	return 0;
 }
 
-// find_nodes_in_area(minp, maxp, nodenames) -> list of positions
-// nodenames: eg. {"ignore", "group:tree"} or "default:dirt"
+// find_nodes_in_area(minp, maxp, nodenames, [grouped])
 int ModApiEnvMod::l_find_nodes_in_area(lua_State *L)
 {
 	GET_PLAIN_ENV_PTR;
@@ -809,6 +815,7 @@ int ModApiEnvMod::l_find_nodes_in_area(lua_State *L)
 	sortBoxVerticies(minp, maxp);
 
 	const NodeDefManager *ndef = env->getGameDef()->ndef();
+	Map &map = env->getMap();
 
 #ifndef SERVER
 	if (Client *client = getClient(L)) {
@@ -826,45 +833,79 @@ int ModApiEnvMod::l_find_nodes_in_area(lua_State *L)
 	}
 
 	std::vector<content_t> filter;
-	if (lua_istable(L, 3)) {
-		lua_pushnil(L);
-		while (lua_next(L, 3) != 0) {
-			// key at index -2 and value at index -1
-			luaL_checktype(L, -1, LUA_TSTRING);
-			ndef->getIds(readParam<std::string>(L, -1), filter);
-			// removes value, keeps key for next iteration
-			lua_pop(L, 1);
+	collectNodeIds(L, 3, ndef, filter);
+
+	bool grouped = lua_isboolean(L, 4) && readParam<bool>(L, 4);
+
+	if (grouped) {
+		// create the table we will be returning
+		lua_createtable(L, 0, filter.size());
+		int base = lua_gettop(L);
+
+		// create one table for each filter
+		std::vector<u32> idx;
+		idx.resize(filter.size());
+		for (u32 i = 0; i < filter.size(); i++)
+			lua_newtable(L);
+
+		v3s16 p;
+		for (p.X = minp.X; p.X <= maxp.X; p.X++)
+		for (p.Y = minp.Y; p.Y <= maxp.Y; p.Y++)
+		for (p.Z = minp.Z; p.Z <= maxp.Z; p.Z++) {
+			content_t c = map.getNode(p).getContent();
+
+			auto it = std::find(filter.begin(), filter.end(), c);
+			if (it != filter.end()) {
+				// Calculate index of the table and append the position
+				u32 filt_index = it - filter.begin();
+				push_v3s16(L, p);
+				lua_rawseti(L, base + 1 + filt_index, ++idx[filt_index]);
+			}
 		}
-	} else if (lua_isstring(L, 3)) {
-		ndef->getIds(readParam<std::string>(L, 3), filter);
-	}
 
-	std::vector<u32> individual_count;
-	individual_count.resize(filter.size());
+		// last filter table is at top of stack
+		u32 i = filter.size() - 1;
+		do {
+			if (idx[i] == 0) {
+				// No such node found -> drop the empty table
+				lua_pop(L, 1);
+			} else {
+				// This node was found -> put table into the return table
+				lua_setfield(L, base, ndef->get(filter[i]).name.c_str());
+			}
+		} while (i-- != 0);
 
-	lua_newtable(L);
-	u64 i = 0;
-	for (s16 x = minp.X; x <= maxp.X; x++)
-	for (s16 y = minp.Y; y <= maxp.Y; y++)
-	for (s16 z = minp.Z; z <= maxp.Z; z++) {
-		v3s16 p(x, y, z);
-		content_t c = env->getMap().getNode(p).getContent();
-
-		std::vector<content_t>::iterator it = std::find(filter.begin(), filter.end(), c);
-		if (it != filter.end()) {
-			push_v3s16(L, p);
-			lua_rawseti(L, -2, ++i);
+		assert(lua_gettop(L) == base);
+		return 1;
+	} else {
+		std::vector<u32> individual_count;
+		individual_count.resize(filter.size());
+
+		lua_newtable(L);
+		u32 i = 0;
+		v3s16 p;
+		for (p.X = minp.X; p.X <= maxp.X; p.X++)
+		for (p.Y = minp.Y; p.Y <= maxp.Y; p.Y++)
+		for (p.Z = minp.Z; p.Z <= maxp.Z; p.Z++) {
+			content_t c = env->getMap().getNode(p).getContent();
 
-			u32 filt_index = it - filter.begin();
-			individual_count[filt_index]++;
+			auto it = std::find(filter.begin(), filter.end(), c);
+			if (it != filter.end()) {
+				push_v3s16(L, p);
+				lua_rawseti(L, -2, ++i);
+
+				u32 filt_index = it - filter.begin();
+				individual_count[filt_index]++;
+			}
 		}
+
+		lua_createtable(L, 0, filter.size());
+		for (u32 i = 0; i < filter.size(); i++) {
+			lua_pushinteger(L, individual_count[i]);
+			lua_setfield(L, -2, ndef->get(filter[i]).name.c_str());
+		}
+		return 2;
 	}
-	lua_newtable(L);
-	for (u32 i = 0; i < filter.size(); i++) {
-		lua_pushnumber(L, individual_count[i]);
-		lua_setfield(L, -2, ndef->get(filter[i]).name.c_str());
-	}
-	return 2;
 }
 
 // find_nodes_in_area_under_air(minp, maxp, nodenames) -> list of positions
@@ -885,6 +926,7 @@ int ModApiEnvMod::l_find_nodes_in_area_under_air(lua_State *L)
 	sortBoxVerticies(minp, maxp);
 
 	const NodeDefManager *ndef = env->getGameDef()->ndef();
+	Map &map = env->getMap();
 
 #ifndef SERVER
 	if (Client *client = getClient(L)) {
@@ -902,33 +944,21 @@ int ModApiEnvMod::l_find_nodes_in_area_under_air(lua_State *L)
 	}
 
 	std::vector<content_t> filter;
-
-	if (lua_istable(L, 3)) {
-		lua_pushnil(L);
-		while (lua_next(L, 3) != 0) {
-			// key at index -2 and value at index -1
-			luaL_checktype(L, -1, LUA_TSTRING);
-			ndef->getIds(readParam<std::string>(L, -1), filter);
-			// removes value, keeps key for next iteration
-			lua_pop(L, 1);
-		}
-	} else if (lua_isstring(L, 3)) {
-		ndef->getIds(readParam<std::string>(L, 3), filter);
-	}
+	collectNodeIds(L, 3, ndef, filter);
 
 	lua_newtable(L);
-	u64 i = 0;
-	for (s16 x = minp.X; x <= maxp.X; x++)
-	for (s16 z = minp.Z; z <= maxp.Z; z++) {
-		s16 y = minp.Y;
-		v3s16 p(x, y, z);
-		content_t c = env->getMap().getNode(p).getContent();
-		for (; y <= maxp.Y; y++) {
-			v3s16 psurf(x, y + 1, z);
-			content_t csurf = env->getMap().getNode(psurf).getContent();
+	u32 i = 0;
+	v3s16 p;
+	for (p.X = minp.X; p.X <= maxp.X; p.X++)
+	for (p.Z = minp.Z; p.Z <= maxp.Z; p.Z++) {
+		p.Y = minp.Y;
+		content_t c = map.getNode(p).getContent();
+		for (; p.Y <= maxp.Y; p.Y++) {
+			v3s16 psurf(p.X, p.Y + 1, p.Z);
+			content_t csurf = map.getNode(psurf).getContent();
 			if (c != CONTENT_AIR && csurf == CONTENT_AIR &&
 					CONTAINS(filter, c)) {
-				push_v3s16(L, v3s16(x, y, z));
+				push_v3s16(L, p);
 				lua_rawseti(L, -2, ++i);
 			}
 			c = csurf;
diff --git a/src/script/lua_api/l_env.h b/src/script/lua_api/l_env.h
index 9050b4306..07d4d2438 100644
--- a/src/script/lua_api/l_env.h
+++ b/src/script/lua_api/l_env.h
@@ -190,6 +190,11 @@ private:
 	// Get a string translated server side
 	static int l_get_translated_string(lua_State * L);
 
+	/* Helpers */
+
+	static void collectNodeIds(lua_State *L, int idx,
+		const NodeDefManager *ndef, std::vector<content_t> &filter);
+
 public:
 	static void Initialize(lua_State *L, int top);
 	static void InitializeClient(lua_State *L, int top);