Biome API: Add decoration flags for underground decorations

Add "all_floors" and "all_ceilings" flags for simple and schematic
decorations. Decorations are placed on all floor and/or ceiling surfaces.
Decorations are placed before dungeon generation so placement in dungeons
is not possible.

Add 'getSurfaces()' function to mapgen.cpp that returns 2 arrays of y
coordinates for all floor and ceiling surfaces in a specified node column.

Move 'getHeight()' checks into DecoSimple and DecoSchematic. Delete
'getHeight()' functions.

5 files changed, 199 insertions, 81 deletions

diff --git a/doc/lua_api.txt b/doc/lua_api.txt
index de4cc5029..d9a31b9f4 100644
--- a/doc/lua_api.txt
+++ b/doc/lua_api.txt
@@ -4849,12 +4849,22 @@ Definition tables
         num_spawn_by = 1,
     --  ^ Number of spawn_by nodes that must be surrounding the decoration position to occur.
     --  ^ If absent or -1, decorations occur next to any nodes.
-        flags = "liquid_surface, force_placement",
+        flags = "liquid_surface, force_placement, all_floors, all_ceilings",
     --  ^ Flags for all decoration types.
-    --  ^ "liquid_surface": Instead of placement on the highest solid surface in
-    --  ^ a mapchunk column, placement is on the highest liquid surface. Placement
-    --  ^ is disabled if solid nodes are found above the liquid surface.
-    --  ^ "force_placement": Nodes other than "air" and "ignore" are replaced by the decoration.
+    --  ^ "liquid_surface": Instead of placement on the highest solid surface
+    --  ^   in a mapchunk column, placement is on the highest liquid surface.
+    --  ^   Placement is disabled if solid nodes are found above the liquid
+    --  ^   surface.
+    --  ^ "force_placement": Nodes other than "air" and "ignore" are replaced
+    --  ^   by the decoration.
+    --  ^ "all_floors", "all_ceilings": Instead of placement on the highest
+    --  ^   surface in a mapchunk the decoration is placed on all floor and/or
+    --  ^   ceiling surfaces, for example in caves.
+    --  ^   Ceiling decorations act as an inversion of floor decorations so the
+    --  ^   effect of 'place_offset_y' is inverted.
+    --  ^   If a single decoration registration has both flags the floor and
+    --  ^   ceiling decorations will be aligned vertically and may sometimes
+    --  ^   meet to form a column.
 
         ----- Simple-type parameters
         decoration = "default:grass",
@@ -4873,9 +4883,10 @@ Definition tables
     --  ^ Upper limit of the randomly selected param2.
     --  ^ If absent, the parameter 'param2' is used as a constant.
         place_offset_y = 0,
-    --  ^ Y offset of the decoration base node relative to the standard
-    --  ^ base node position for simple decorations.
+    --  ^ Y offset of the decoration base node relative to the standard base
+    --  ^ node position.
     --  ^ Can be positive or negative. Default is 0.
+    --  ^ Effect is inverted for "all_ceilings" decorations.
     --  ^ Ignored by 'y_min', 'y_max' and 'spawn_by' checks, which always refer
     --  ^ to the 'place_on' node.
 
@@ -4908,12 +4919,13 @@ Definition tables
         rotation = "90" -- rotate schematic 90 degrees on placement
     --  ^ Rotation can be "0", "90", "180", "270", or "random".
         place_offset_y = 0,
+    --  ^ If the flag 'place_center_y' is set this parameter is ignored.
     --  ^ Y offset of the schematic base node layer relative to the 'place_on'
     --  ^ node.
     --  ^ Can be positive or negative. Default is 0.
-    --  ^ If the flag 'place_center_y' is set this parameter is ignored.
-    --  ^ If absent or 0 the schematic base node layer will be placed level
-    --  ^ with the 'place_on' node.
+    --  ^ Effect is inverted for "all_ceilings" decorations.
+    --  ^ Ignored by 'y_min', 'y_max' and 'spawn_by' checks, which always refer
+    --  ^ to the 'place_on' node.
     }
 
 ### Chat command definition (`register_chatcommand`)
diff --git a/src/mapgen.cpp b/src/mapgen.cpp
index 7b32ffab1..f73e16dd0 100644
--- a/src/mapgen.cpp
+++ b/src/mapgen.cpp
@@ -299,6 +299,41 @@ void Mapgen::updateHeightmap(v3s16 nmin, v3s16 nmax)
 	}
 }
 
+
+void Mapgen::getSurfaces(v2s16 p2d, s16 ymin, s16 ymax,
+	s16 *floors, s16 *ceilings, u16 *num_floors, u16 *num_ceilings)
+{
+	u16 floor_i = 0;
+	u16 ceiling_i = 0;
+	const v3s16 &em = vm->m_area.getExtent();
+
+	bool is_walkable = false;
+	u32 vi = vm->m_area.index(p2d.X, ymax, p2d.Y);
+	MapNode mn_max = vm->m_data[vi];
+	bool walkable_above = ndef->get(mn_max).walkable;
+	vm->m_area.add_y(em, vi, -1);
+
+	for (s16 y = ymax - 1; y >= ymin; y--) {
+		MapNode mn = vm->m_data[vi];
+		is_walkable = ndef->get(mn).walkable;
+
+		if (is_walkable && !walkable_above) {
+			floors[floor_i] = y;
+			floor_i++;
+		} else if (!is_walkable && walkable_above) {
+			ceilings[ceiling_i] = y + 1;
+			ceiling_i++;
+		}
+
+		vm->m_area.add_y(em, vi, -1);
+		walkable_above = is_walkable;
+	}
+
+	*num_floors = floor_i;
+	*num_ceilings = ceiling_i;
+}
+
+
 inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
 {
 	u32 vi_neg_x = vi;
diff --git a/src/mapgen.h b/src/mapgen.h
index 0a3f267f0..8994fdc00 100644
--- a/src/mapgen.h
+++ b/src/mapgen.h
@@ -193,6 +193,9 @@ public:
 	s16 findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax);
 	s16 findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax);
 	void updateHeightmap(v3s16 nmin, v3s16 nmax);
+	void getSurfaces(v2s16 p2d, s16 ymin, s16 ymax,
+		s16 *floors, s16 *ceilings, u16 *num_floors, u16 *num_ceilings);
+
 	void updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax);
 
 	void setLighting(u8 light, v3s16 nmin, v3s16 nmax);
diff --git a/src/mg_decoration.cpp b/src/mg_decoration.cpp
index ada37bab4..2c2fbc647 100644
--- a/src/mg_decoration.cpp
+++ b/src/mg_decoration.cpp
@@ -34,6 +34,8 @@ FlagDesc flagdesc_deco[] = {
 	{"place_center_z",  DECO_PLACE_CENTER_Z},
 	{"force_placement", DECO_FORCE_PLACEMENT},
 	{"liquid_surface",  DECO_LIQUID_SURFACE},
+	{"all_floors",      DECO_ALL_FLOORS},
+	{"all_ceilings",    DECO_ALL_CEILINGS},
 	{NULL,              0}
 };
 
@@ -169,33 +171,79 @@ size_t Decoration::placeDeco(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax)
 		for (u32 i = 0; i < deco_count; i++) {
 			s16 x = ps.range(p2d_min.X, p2d_max.X);
 			s16 z = ps.range(p2d_min.Y, p2d_max.Y);
-
 			int mapindex = carea_size * (z - nmin.Z) + (x - nmin.X);
 
-			s16 y = -MAX_MAP_GENERATION_LIMIT;
-			if (flags & DECO_LIQUID_SURFACE)
-				y = mg->findLiquidSurface(v2s16(x, z), nmin.Y, nmax.Y);
-			else if (mg->heightmap)
-				y = mg->heightmap[mapindex];
-			else
-				y = mg->findGroundLevel(v2s16(x, z), nmin.Y, nmax.Y);
-
-			if (y < y_min || y > y_max || y < nmin.Y || y > nmax.Y)
-				continue;
+			if ((flags & DECO_ALL_FLOORS) ||
+					(flags & DECO_ALL_CEILINGS)) {
+				// All-surfaces decorations
+				// Check biome of column
+				if (mg->biomemap && !biomes.empty()) {
+					std::unordered_set<u8>::const_iterator iter =
+						biomes.find(mg->biomemap[mapindex]);
+					if (iter == biomes.end())
+						continue;
+				}
+
+				// Get all floors and ceilings in node column
+				u16 size = (nmax.Y - nmin.Y + 1) / 2;
+				s16 floors[size];
+				s16 ceilings[size];
+				u16 num_floors = 0;
+				u16 num_ceilings = 0;
+
+				mg->getSurfaces(v2s16(x, z), nmin.Y, nmax.Y,
+					floors, ceilings, &num_floors, &num_ceilings);
+
+				if ((flags & DECO_ALL_FLOORS) && num_floors > 0) {
+					// Floor decorations
+					for (u16 fi = 0; fi < num_floors; fi++) {
+						s16 y = floors[fi];
+						if (y < y_min || y > y_max)
+							continue;
+
+						v3s16 pos(x, y, z);
+						if (generate(mg->vm, &ps, pos, false))
+							mg->gennotify.addEvent(
+									GENNOTIFY_DECORATION, pos, index);
+					}
+				}
+
+				if ((flags & DECO_ALL_CEILINGS) && num_ceilings > 0) {
+					// Ceiling decorations
+					for (u16 ci = 0; ci < num_ceilings; ci++) {
+						s16 y = ceilings[ci];
+						if (y < y_min || y > y_max)
+							continue;
+
+						v3s16 pos(x, y, z);
+						if (generate(mg->vm, &ps, pos, true))
+							mg->gennotify.addEvent(
+									GENNOTIFY_DECORATION, pos, index);
+					}
+				}
+			} else { // Heightmap decorations
+				s16 y = -MAX_MAP_GENERATION_LIMIT;
+				if (flags & DECO_LIQUID_SURFACE)
+					y = mg->findLiquidSurface(v2s16(x, z), nmin.Y, nmax.Y);
+				else if (mg->heightmap)
+					y = mg->heightmap[mapindex];
+				else
+					y = mg->findGroundLevel(v2s16(x, z), nmin.Y, nmax.Y);
+
+				if (y < y_min || y > y_max || y < nmin.Y || y > nmax.Y)
+					continue;
 
-			if (y + getHeight() > mg->vm->m_area.MaxEdge.Y)
-				continue;
+				if (mg->biomemap && !biomes.empty()) {
+					std::unordered_set<u8>::const_iterator iter =
+						biomes.find(mg->biomemap[mapindex]);
+					if (iter == biomes.end())
+						continue;
+				}
 
-			if (mg->biomemap && !biomes.empty()) {
-				std::unordered_set<u8>::const_iterator iter =
-					biomes.find(mg->biomemap[mapindex]);
-				if (iter == biomes.end())
-					continue;
+				v3s16 pos(x, y, z);
+				if (generate(mg->vm, &ps, pos, false))
+					mg->gennotify.addEvent(GENNOTIFY_DECORATION, pos, index);
 			}
-
-			v3s16 pos(x, y, z);
-			if (generate(mg->vm, &ps, pos))
-				mg->gennotify.addEvent(GENNOTIFY_DECORATION, pos, index);
 		}
 	}
 
@@ -213,58 +261,79 @@ void DecoSimple::resolveNodeNames()
 }
 
 
-size_t DecoSimple::generate(MMVManip *vm, PcgRandom *pr, v3s16 p)
+size_t DecoSimple::generate(MMVManip *vm, PcgRandom *pr, v3s16 p, bool ceiling)
 {
 	// Don't bother if there aren't any decorations to place
 	if (c_decos.empty())
 		return 0;
 
-	// Check for a negative place_offset_y causing placement below the voxelmanip
-	if (p.Y + 1 + place_offset_y < vm->m_area.MinEdge.Y)
-		return 0;
-
 	if (!canPlaceDecoration(vm, p))
 		return 0;
 
-	content_t c_place = c_decos[pr->range(0, c_decos.size() - 1)];
+	// Check for placement outside the voxelmanip volume
+	if (ceiling) {
+		// Ceiling decorations
+		// 'place offset y' is inverted
+		if (p.Y - place_offset_y - std::max(deco_height, deco_height_max) <
+				vm->m_area.MinEdge.Y)
+			return 0;
+
+		if (p.Y - 1 - place_offset_y > vm->m_area.MaxEdge.Y)
+			return 0;
 
+	} else { // Heightmap and floor decorations
+		if (p.Y + place_offset_y + std::max(deco_height, deco_height_max) >
+				vm->m_area.MaxEdge.Y)
+			return 0;
+
+		if (p.Y + 1 + place_offset_y < vm->m_area.MinEdge.Y)
+			return 0;
+	}
+
+	content_t c_place = c_decos[pr->range(0, c_decos.size() - 1)];
 	s16 height = (deco_height_max > 0) ?
 		pr->range(deco_height, deco_height_max) : deco_height;
-
 	u8 param2 = (deco_param2_max > 0) ?
 		pr->range(deco_param2, deco_param2_max) : deco_param2;
-
 	bool force_placement = (flags & DECO_FORCE_PLACEMENT);
 
 	const v3s16 &em = vm->m_area.getExtent();
 	u32 vi = vm->m_area.index(p);
-	vm->m_area.add_y(em, vi, place_offset_y);
 
-	for (int i = 0; i < height; i++) {
-		vm->m_area.add_y(em, vi, 1);
-		content_t c = vm->m_data[vi].getContent();
-		if (c != CONTENT_AIR && c != CONTENT_IGNORE &&
-				!force_placement)
-			break;
+	if (ceiling) {
+		// Ceiling decorations
+		// 'place offset y' is inverted
+		vm->m_area.add_y(em, vi, -place_offset_y);
 
-		vm->m_data[vi] = MapNode(c_place, 0, param2);
-	}
+		for (int i = 0; i < height; i++) {
+			vm->m_area.add_y(em, vi, -1);
+			content_t c = vm->m_data[vi].getContent();
+			if (c != CONTENT_AIR && c != CONTENT_IGNORE && !force_placement)
+				break;
 
-	return 1;
-}
+			vm->m_data[vi] = MapNode(c_place, 0, param2);
+		}
+	} else { // Heightmap and floor decorations
+		vm->m_area.add_y(em, vi, place_offset_y);
 
+		for (int i = 0; i < height; i++) {
+			vm->m_area.add_y(em, vi, 1);
+			content_t c = vm->m_data[vi].getContent();
+			if (c != CONTENT_AIR && c != CONTENT_IGNORE && !force_placement)
+				break;
 
-int DecoSimple::getHeight()
-{
-	return ((deco_height_max > 0) ? deco_height_max : deco_height)
-		+ place_offset_y;
+			vm->m_data[vi] = MapNode(c_place, 0, param2);
+		}
+	}
+
+	return 1;
 }
 
 
 ///////////////////////////////////////////////////////////////////////////////
 
 
-size_t DecoSchematic::generate(MMVManip *vm, PcgRandom *pr, v3s16 p)
+size_t DecoSchematic::generate(MMVManip *vm, PcgRandom *pr, v3s16 p, bool ceiling)
 {
 	// Schematic could have been unloaded but not the decoration
 	// In this case generate() does nothing (but doesn't *fail*)
@@ -274,35 +343,35 @@ size_t DecoSchematic::generate(MMVManip *vm, PcgRandom *pr, v3s16 p)
 	if (!canPlaceDecoration(vm, p))
 		return 0;
 
+	if (flags & DECO_PLACE_CENTER_Y) {
+		p.Y -= (schematic->size.Y - 1) / 2;
+	} else {
+		// Only apply 'place offset y' if not 'deco place center y'
+		if (ceiling)
+			// Shift down so that schematic top layer is level with ceiling
+			// 'place offset y' is inverted
+			p.Y -= (place_offset_y + schematic->size.Y - 1);
+		else
+			p.Y += place_offset_y;
+	}
+
+	// Check schematic top and base are in voxelmanip
+	if (p.Y + schematic->size.Y - 1 > vm->m_area.MaxEdge.Y)
+		return 0;
+
+	if (p.Y < vm->m_area.MinEdge.Y)
+		return 0;
+
 	if (flags & DECO_PLACE_CENTER_X)
 		p.X -= (schematic->size.X - 1) / 2;
 	if (flags & DECO_PLACE_CENTER_Z)
 		p.Z -= (schematic->size.Z - 1) / 2;
 
-	if (flags & DECO_PLACE_CENTER_Y)
-		p.Y -= (schematic->size.Y - 1) / 2;
-	else
-		p.Y += place_offset_y;
-	// Check shifted schematic base is in voxelmanip
-	if (p.Y < vm->m_area.MinEdge.Y)
-		return 0;
-
 	Rotation rot = (rotation == ROTATE_RAND) ?
 		(Rotation)pr->range(ROTATE_0, ROTATE_270) : rotation;
-
 	bool force_placement = (flags & DECO_FORCE_PLACEMENT);
 
 	schematic->blitToVManip(vm, p, rot, force_placement);
 
 	return 1;
 }
-
-
-int DecoSchematic::getHeight()
-{
-	// Account for a schematic being sunk into the ground by flag.
-	// When placed normally account for how a schematic is by default placed
-	// sunk 1 node into the ground or is vertically shifted by 'y_offset'.
-	return (flags & DECO_PLACE_CENTER_Y) ?
-		(schematic->size.Y - 1) / 2 : schematic->size.Y - 1 + place_offset_y;
-}
diff --git a/src/mg_decoration.h b/src/mg_decoration.h
index 9295d1a20..1ca632f25 100644
--- a/src/mg_decoration.h
+++ b/src/mg_decoration.h
@@ -42,6 +42,8 @@ enum DecorationType {
 #define DECO_USE_NOISE       0x08
 #define DECO_FORCE_PLACEMENT 0x10
 #define DECO_LIQUID_SURFACE  0x20
+#define DECO_ALL_FLOORS      0x40
+#define DECO_ALL_CEILINGS    0x80
 
 extern FlagDesc flagdesc_deco[];
 
@@ -56,8 +58,7 @@ public:
 	bool canPlaceDecoration(MMVManip *vm, v3s16 p);
 	size_t placeDeco(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);
 
-	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p) = 0;
-	virtual int getHeight() = 0;
+	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p, bool ceiling) = 0;
 
 	u32 flags = 0;
 	int mapseed = 0;
@@ -78,8 +79,7 @@ public:
 class DecoSimple : public Decoration {
 public:
 	virtual void resolveNodeNames();
-	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p);
-	virtual int getHeight();
+	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p, bool ceiling);
 
 	std::vector<content_t> c_decos;
 	s16 deco_height;
@@ -93,8 +93,7 @@ class DecoSchematic : public Decoration {
 public:
 	DecoSchematic() = default;
 
-	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p);
-	virtual int getHeight();
+	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p, bool ceiling);
 
 	Rotation rotation;
 	Schematic *schematic = nullptr;