code:
/*
Minetest
Copyright (C) 2010-2015 celeron55, Perttu Ahola <celeron55@gmail.com>
Copyright (C) 2013-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
Copyright (C) 2015-2017 paramat

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 "mapgen.h"
#include "voxel.h"
#include "noise.h"
#include "gamedef.h"
#include "mg_biome.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "content_sao.h"
#include "nodedef.h"
#include "emerge.h"
#include "voxelalgorithms.h"
#include "porting.h"
#include "profiler.h"
#include "settings.h"
#include "treegen.h"
#include "serialization.h"
#include "util/serialize.h"
#include "util/numeric.h"
#include "filesys.h"
#include "log.h"
#include "mapgen_flat.h"
#include "mapgen_fractal.h"
#include "mapgen_v5.h"
#include "mapgen_v6.h"
#include "mapgen_v7.h"
#include "mapgen_valleys.h"
#include "mapgen_singlenode.h"
#include "cavegen.h"
#include "dungeongen.h"

FlagDesc flagdesc_mapgen[] = {
	{"caves",       MG_CAVES},
	{"dungeons",    MG_DUNGEONS},
	{"light",       MG_LIGHT},
	{"decorations", MG_DECORATIONS},
	{NULL,       0}
};

FlagDesc flagdesc_gennotify[] = {
	{"dungeon",          1 << GENNOTIFY_DUNGEON},
	{"temple",           1 << GENNOTIFY_TEMPLE},
	{"cave_begin",       1 << GENNOTIFY_CAVE_BEGIN},
	{"cave_end",         1 << GENNOTIFY_CAVE_END},
	{"large_cave_begin", 1 << GENNOTIFY_LARGECAVE_BEGIN},
	{"large_cave_end",   1 << GENNOTIFY_LARGECAVE_END},
	{"decoration",       1 << GENNOTIFY_DECORATION},
	{NULL,               0}
};

struct MapgenDesc {
	const char *name;
	bool is_user_visible;
};

////
//// Built-in mapgens
////

static MapgenDesc g_reg_mapgens[] = {
	{"v5",         true},
	{"v6",         true},
	{"v7",         true},
	{"flat",       true},
	{"fractal",    true},
	{"valleys",    true},
	{"singlenode", true},
};

STATIC_ASSERT(
	ARRLEN(g_reg_mapgens) == MAPGEN_INVALID,
	registered_mapgens_is_wrong_size);

////
//// Mapgen
////

Mapgen::Mapgen()
{
	generating   = false;
	id           = -1;
	seed         = 0;
	water_level  = 0;
	mapgen_limit = 0;
	flags        = 0;

	vm        = NULL;
	ndef      = NULL;
	biomegen  = NULL;
	biomemap  = NULL;
	heightmap = NULL;
}

Mapgen::Mapgen(int mapgenid, MapgenParams *params, EmergeManager *emerge) :
	gennotify(emerge->gen_notify_on, &emerge->gen_notify_on_deco_ids)
{
	generating   = false;
	id           = mapgenid;
	water_level  = params->water_level;
	mapgen_limit = params->mapgen_limit;
	flags        = params->flags;
	csize        = v3s16(1, 1, 1) * (params->chunksize * MAP_BLOCKSIZE);

	/*
		We are losing half our entropy by doing this, but it is necessary to
		preserve reverse compatibility.  If the top half of our current 64 bit
		seeds ever starts getting used, existing worlds will break due to a
		different hash outcome and no way to differentiate between versions.

		A solution could be to add a new bit to designate that the top half of
		the seed value should be used, essentially a 1-bit version code, but
		this would require increasing the total size of a seed to 9 bytes (yuck)

		It's probably okay if this never gets fixed.  4.2 billion possibilities
		ought to be enough for anyone.
	*/
	seed = (s32)params->seed;

	vm        = NULL;
	ndef      = emerge->ndef;
	biomegen  = NULL;
	biomemap  = NULL;
	heightmap = NULL;
}

Mapgen::~Mapgen()
{
}

MapgenType Mapgen::getMapgenType(const std::string &mgname)
{
	for (size_t i = 0; i != ARRLEN(g_reg_mapgens); i++) {
		if (mgname == g_reg_mapgens[i].name)
			return (MapgenType)i;
	}

	return MAPGEN_INVALID;
}

const char *Mapgen::getMapgenName(MapgenType mgtype)
{
	size_t index = (size_t)mgtype;
	if (index == MAPGEN_INVALID || index >= ARRLEN(g_reg_mapgens))
		return "invalid";

	return g_reg_mapgens[index].name;
}

Mapgen *Mapgen::createMapgen(MapgenType mgtype, int mgid,
	MapgenParams *params, EmergeManager *emerge)
{
	switch (mgtype) {
	case MAPGEN_FLAT:
		return new MapgenFlat(mgid, (MapgenFlatParams *)params, emerge);
	case MAPGEN_FRACTAL:
		return new MapgenFractal(mgid, (MapgenFractalParams *)params, emerge);
	case MAPGEN_SINGLENODE:
		return new MapgenSinglenode(mgid, (MapgenSinglenodeParams *)params, emerge);
	case MAPGEN_V5:
		return new MapgenV5(mgid, (MapgenV5Params *)params, emerge);
	case MAPGEN_V6:
		return new MapgenV6(mgid, (MapgenV6Params *)params, emerge);
	case MAPGEN_V7:
		return new MapgenV7(mgid, (MapgenV7Params *)params, emerge);
	case MAPGEN_VALLEYS:
		return new MapgenValleys(mgid, (MapgenValleysParams *)params, emerge);
	default:
		return NULL;
	}
}

MapgenParams *Mapgen::createMapgenParams(MapgenType mgtype)
{
	switch (mgtype) {
	case MAPGEN_FLAT:
		return new MapgenFlatParams;
	case MAPGEN_FRACTAL:
		return new MapgenFractalParams;
	case MAPGEN_SINGLENODE:
		return new MapgenSinglenodeParams;
	case MAPGEN_V5:
		return new MapgenV5Params;
	case MAPGEN_V6:
		return new MapgenV6Params;
	case MAPGEN_V7:
		return new MapgenV7Params;
	case MAPGEN_VALLEYS:
		return new MapgenValleysParams;
	default:
		return NULL;
	}
}

void Mapgen::getMapgenNames(std::vector<const char *> *mgnames, bool include_hidden)
{
	for (u32 i = 0; i != ARRLEN(g_reg_mapgens); i++) {
		if (include_hidden || g_reg_mapgens[i].is_user_visible)
			mgnames->push_back(g_reg_mapgens[i].name);
	}
}

u32 Mapgen::getBlockSeed(v3s16 p, s32 seed)
{
	return (u32)seed   +
		p.Z * 38134234 +
		p.Y * 42123    +
		p.X * 23;
}

u32 Mapgen::getBlockSeed2(v3s16 p, s32 seed)
{
	u32 n = 1619 * p.X + 31337 * p.Y + 52591 * p.Z + 1013 * seed;
	n = (n >> 13) ^ n;
	return (n * (n * n * 60493 + 19990303) + 1376312589);
}

// Returns Y one under area minimum if not found
s16 Mapgen::findGroundLevelFull(v2s16 p2d)
{
	v3s16 em = vm->m_area.getExtent();
	s16 y_nodes_max = vm->m_area.MaxEdge.Y;
	s16 y_nodes_min = vm->m_area.MinEdge.Y;
	u32 i = vm->m_area.index(p2d.X, y_nodes_max, p2d.Y);
	s16 y;

	for (y = y_nodes_max; y >= y_nodes_min; y--) {
		MapNode &n = vm->m_data[i];
		if (ndef->get(n).walkable)
			break;

		vm->m_area.add_y(em, i, -1);
	}
	return (y >= y_nodes_min) ? y : y_nodes_min - 1;
}

// Returns -MAX_MAP_GENERATION_LIMIT if not found
s16 Mapgen::findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax)
{
	v3s16 em = vm->m_area.getExtent();
	u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
	s16 y;

	for (y = ymax; y >= ymin; y--) {
		MapNode &n = vm->m_data[i];
		if (ndef->get(n).walkable)
			break;

		vm->m_area.add_y(em, i, -1);
	}
	return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
}

// Returns -MAX_MAP_GENERATION_LIMIT if not found or if ground is found first
s16 Mapgen::findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax)
{
	v3s16 em = vm->m_area.getExtent();
	u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
	s16 y;

	for (y = ymax; y >= ymin; y--) {
		MapNode &n = vm->m_data[i];
		if (ndef->get(n).walkable)
			return -MAX_MAP_GENERATION_LIMIT;
		else if (ndef->get(n).isLiquid())
			break;

		vm->m_area.add_y(em, i, -1);
	}
	return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
}

void Mapgen::updateHeightmap(v3s16 nmin, v3s16 nmax)
{
	if (!heightmap)
		return;

	//TimeTaker t("Mapgen::updateHeightmap", NULL, PRECISION_MICRO);
	int index = 0;
	for (s16 z = nmin.Z; z <= nmax.Z; z++) {
		for (s16 x = nmin.X; x <= nmax.X; x++, index++) {
			s16 y = findGroundLevel(v2s16(x, z), nmin.Y, nmax.Y);

			heightmap[index] = y;
		}
	}
}

inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
{
	u32 vi_neg_x = vi;
	vm->m_area.add_x(em, vi_neg_x, -1);
	if (vm->m_data[vi_neg_x].getContent() != CONTENT_IGNORE) {
		const ContentFeatures &c_nx = ndef->get(vm->m_data[vi_neg_x]);
		if (c_nx.floodable && !c_nx.isLiquid())
			return true;
	}
	u32 vi_pos_x = vi;
	vm->m_area.add_x(em, vi_pos_x, +1);
	if (vm->m_data[vi_pos_x].getContent() != CONTENT_IGNORE) {
		const ContentFeatures &c_px = ndef->get(vm->m_data[vi_pos_x]);
		if (c_px.floodable && !c_px.isLiquid())
			return true;
	}
	u32 vi_neg_z = vi;
	vm->m_area.add_z(em, vi_neg_z, -1);
	if (vm->m_data[vi_neg_z].getContent() != CONTENT_IGNORE) {
		const ContentFeatures &c_nz = ndef->get(vm->m_data[vi_neg_z]);
		if (c_nz.floodable && !c_nz.isLiquid())
			return true;
	}
	u32 vi_pos_z = vi;
	vm->m_area.add_z(em, vi_pos_z, +1);
	if (vm->m_data[vi_pos_z].getContent() != CONTENT_IGNORE) {
		const ContentFeatures &c_pz = ndef->get(vm->m_data[vi_pos_z]);
		if (c_pz.floodable && !c_pz.isLiquid())
			return true;
	}
	return false;
}

void Mapgen::updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax)
{
	bool isignored, isliquid, wasignored, wasliquid, waschecked, waspushed;
	v3s16 em  = vm->m_area.getExtent();

	for (s16 z = nmin.Z + 1; z <= nmax.Z - 1; z++)
	for (s16 x = nmin.X + 1; x <= nmax.X - 1; x++) {
		wasignored = true;
		wasliquid = false;
		waschecked = false;
		waspushed = false;

		u32 vi = vm->m_area.index(x, nmax.Y, z);
		for (s16 y = nmax.Y; y >= nmin.Y; y--) {
			isignored = vm->m_data[vi].getContent() == CONTENT_IGNORE;
			isliquid = ndef->get(vm->m_data[vi]).isLiquid();

			if (isignored || wasignored || isliquid == wasliquid) {
				// Neither topmost node of liquid column nor topmost node below column
				waschecked = false;
				waspushed = false;
			} else if (isliquid) {
				// This is the topmost node in the column
				bool ispushed = false;
				if (isLiquidHorizontallyFlowable(vi, em)) {
					trans_liquid->push_back(v3s16(x, y, z));
					ispushed = true;
				}
				// Remember waschecked and waspushed to avoid repeated
				// checks/pushes in case the column consists of only this node
				waschecked = true;
				waspushed = ispushed;
			} else {
				// This is the topmost node below a liquid column
				u32 vi_above = vi;
				vm->m_area.add_y(em, vi_above, 1);
				if (!waspushed && (ndef->get(vm->m_data[vi]).floodable ||
						(!waschecked && isLiquidHorizontallyFlowable(vi_above, em)))) {
					// Push back the lowest node in the column which is one
					// node above this one
					trans_liquid->push_back(v3s16(x, y + 1, z));
				}
			}

			wasliquid = isliquid;
			wasignored = isignored;
			vm->m_area.add_y(em, vi, -1);
		}
	}
}

void Mapgen::setLighting(u8 light, v3s16 nmin, v3s16 nmax)
{
	ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
	VoxelArea a(nmin, nmax);

	for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
		for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
			u32 i = vm->m_area.index(a.MinEdge.X, y, z);
			for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++)
				vm->m_data[i].param1 = light;
		}
	}
}

void Mapgen::lightSpread(VoxelArea &a, v3s16 p, u8 light)
{
	if (light <= 1 || !a.contains(p))
		return;

	u32 vi = vm->m_area.index(p);
	MapNode &n = vm->m_data[vi];

	// Decay light in each of the banks separately
	u8 light_day = light & 0x0F;
	if (light_day > 0)
		light_day -= 0x01;

	u8 light_night = light & 0xF0;
	if (light_night > 0)
		light_night -= 0x10;

	// Bail out only if we have no more light from either bank to propogate, or
	// we hit a solid block that light cannot pass through.
	if ((light_day  <= (n.param1 & 0x0F) &&
		light_night <= (n.param1 & 0xF0)) ||
		!ndef->get(n).light_propagates)
		return;

	// Since this recursive function only terminates when there is no light from
	// either bank left, we need to take the max of both banks into account for
	// the case where spreading has stopped for one light bank but not the other.
	light = MYMAX(light_day, n.param1 & 0x0F) |
			MYMAX(light_night, n.param1 & 0xF0);

	n.param1 = light;

	lightSpread(a, p + v3s16(0, 0, 1), light);
	lightSpread(a, p + v3s16(0, 1, 0), light);
	lightSpread(a, p + v3s16(1, 0, 0), light);
	lightSpread(a, p - v3s16(0, 0, 1), light);
	lightSpread(a, p - v3s16(0, 1, 0), light);
	lightSpread(a, p - v3s16(1, 0, 0), light);
}

void Mapgen::calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
	bool propagate_shadow)
{
	ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
	//TimeTaker t("updateLighting");

	propagateSunlight(nmin, nmax, propagate_shadow);
	spreadLight(full_nmin, full_nmax);

	//printf("updateLighting: %dms\n", t.stop());
}

void Mapgen::propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow)
{
	//TimeTaker t("propagateSunlight");
	VoxelArea a(nmin, nmax);
	bool block_is_underground = (water_level >= nmax.Y);
	v3s16 em = vm->m_area.getExtent();

	// NOTE: Direct access to the low 4 bits of param1 is okay here because,
	// by definition, sunlight will never be in the night lightbank.

	for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
		for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++) {
			// see if we can get a light value from the overtop
			u32 i = vm->m_area.index(x, a.MaxEdge.Y + 1, z);
			if (vm->m_data[i].getContent() == CONTENT_IGNORE) {
				if (block_is_underground)
					continue;
			} else if ((vm->m_data[i].param1 & 0x0F) != LIGHT_SUN &&
					propagate_shadow) {
				continue;
			}
			vm->m_area.add_y(em, i, -1);

			for (int y = a.MaxEdge.Y; y >= a.MinEdge.Y; y--) {
				MapNode &n = vm->m_data[i];
				if (!ndef->get(n).sunlight_propagates)
					break;
				n.param1 = LIGHT_SUN;
				vm->m_area.add_y(em, i, -1);
			}
		}
	}
	//printf("propagateSunlight: %dms\n", t.stop());
}

void Mapgen::spreadLight(v3s16 nmin, v3s16 nmax)
{
	//TimeTaker t("spreadLight");
	VoxelArea a(nmin, nmax);

	for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
		for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
			u32 i = vm->m_area.index(a.MinEdge.X, y, z);
			for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++) {
				MapNode &n = vm->m_data[i];
				if (n.getContent() == CONTENT_IGNORE)
					continue;

				const ContentFeatures &cf = ndef->get(n);
				if (!cf.light_propagates)
					continue;

				// TODO(hmmmmm): Abstract away direct param1 accesses with a
				// wrapper, but something lighter than MapNode::get/setLight

				u8 light_produced = cf.light_source;
				if (light_produced)
					n.param1 = light_produced | (light_produced << 4);

				u8 light = n.param1;
				if (light) {
					lightSpread(a, v3s16(x,     y,     z + 1), light);
					lightSpread(a, v3s16(x,     y + 1, z    ), light);
					lightSpread(a, v3s16(x + 1, y,     z    ), light);
					lightSpread(a, v3s16(x,     y,     z - 1), light);
					lightSpread(a, v3s16(x,     y - 1, z    ), light);
					lightSpread(a, v3s16(x - 1, y,     z    ), light);
				}
			}
		}
	}

	//printf("spreadLight: %dms\n", t.stop());
}

////
//// MapgenBasic
////

MapgenBasic::MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge)
	: Mapgen(mapgenid, params, emerge)
{
	this->m_emerge = emerge;
	this->m_bmgr   = emerge->biomemgr;

	//// Here, 'stride' refers to the number of elements needed to skip to index
	//// an adjacent element for that coordinate in noise/height/biome maps
	//// (*not* vmanip content map!)

	// Note there is no X stride explicitly defined.  Items adjacent in the X
	// coordinate are assumed to be adjacent in memory as well (i.e. stride of 1).

	// Number of elements to skip to get to the next Y coordinate
	this->ystride = csize.X;

	// Number of elements to skip to get to the next Z coordinate
	this->zstride = csize.X * csize.Y;

	// Z-stride value for maps oversized for 1-down overgeneration
	this->zstride_1d = csize.X * (csize.Y + 1);

	// Z-stride value for maps oversized for 1-up 1-down overgeneration
	this->zstride_1u1d = csize.X * (csize.Y + 2);

	//// Allocate heightmap
	this->heightmap = new s16[csize.X * csize.Z];

	//// Initialize biome generator
	// TODO(hmmmm): should we have a way to disable biomemanager biomes?
	biomegen = m_bmgr->createBiomeGen(BIOMEGEN_ORIGINAL, params->bparams, csize);
	biomemap = biomegen->biomemap;

	//// Look up some commonly used content
	c_stone              = ndef->getId("mapgen_stone");
	c_desert_stone       = ndef->getId("mapgen_desert_stone");
	c_sandstone          = ndef->getId("mapgen_sandstone");
	c_water_source       = ndef->getId("mapgen_water_source");
	c_river_water_source = ndef->getId("mapgen_river_water_source");
	c_lava_source        = ndef->getId("mapgen_lava_source");

	// Fall back to more basic content if not defined
	// river_water_source cannot fallback to water_source because river water
	// needs to be non-renewable and have a short flow range.
	if (c_desert_stone == CONTENT_IGNORE)
		c_desert_stone = c_stone;
	if (c_sandstone == CONTENT_IGNORE)
		c_sandstone = c_stone;

	//// Content used for dungeon generation
	c_cobble                = ndef->getId("mapgen_cobble");
	c_mossycobble           = ndef->getId("mapgen_mossycobble");
	c_stair_cobble          = ndef->getId("mapgen_stair_cobble");
	c_stair_desert_stone    = ndef->getId("mapgen_stair_desert_stone");
	c_sandstonebrick        = ndef->getId("mapgen_sandstonebrick");
	c_stair_sandstone_block = ndef->getId("mapgen_stair_sandstone_block");

	// Fall back to more basic content if not defined
	if (c_mossycobble == CONTENT_IGNORE)
		c_mossycobble = c_cobble;
	if (c_stair_cobble == CONTENT_IGNORE)
		c_stair_cobble = c_cobble;
	if (c_stair_desert_stone == CONTENT_IGNORE)
		c_stair_desert_stone = c_desert_stone;
	if (c_sandstonebrick == CONTENT_IGNORE)
		c_sandstonebrick = c_sandstone;
	if (c_stair_sandstone_block == CONTENT_IGNORE)
		c_stair_sandstone_block = c_sandstonebrick;
}

MapgenBasic::~MapgenBasic()
{
	delete biomegen;
	delete []heightmap;
}

MgStoneType MapgenBasic::generateBiomes()
{
	// can't generate biomes without a biome generator!
	assert(biomegen);
	assert(biomemap);

	v3s16 em = vm->m_area.getExtent();
	u32 index = 0;
	MgStoneType stone_type = MGSTONE_STONE;

	noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);

	for (s16 z = node_min.Z; z <= node_max.Z; z++)
	for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
		Biome *biome = NULL;
		u16 depth_top = 0;
		u16 base_filler = 0;
		u16 depth_water_top = 0;
		u16 depth_riverbed = 0;
		u32 vi = vm->m_area.index(x, node_max.Y, z);

		// Check node at base of mapchunk above, either a node of a previously
		// generated mapchunk or if not, a node of overgenerated base terrain.
		content_t c_above = vm->m_data[vi + em.X].getContent();
		bool air_above = c_above == CONTENT_AIR;
		bool river_water_above = c_above == c_river_water_source;
		bool water_above = c_above == c_water_source || river_water_above;

		biomemap[index] = BIOME_NONE;

		// If there is air or water above enable top/filler placement, otherwise force
		// nplaced to stone level by setting a number exceeding any possible filler depth.
		u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;

		for (s16 y = node_max.Y; y >= node_min.Y; y--) {
			content_t c = vm->m_data[vi].getContent();

			// Biome is recalculated each time an upper surface is detected while
			// working down a column. The selected biome then remains in effect for
			// all nodes below until the next surface and biome recalculation.
			// Biome is recalculated:
			// 1. At the surface of stone below air or water.
			// 2. At the surface of water below air.
			// 3. When stone or water is detected but biome has not yet been calculated.
			bool is_stone_surface = (c == c_stone) &&
				(air_above || water_above || !biome);

			bool is_water_surface =
				(c == c_water_source || c == c_river_water_source) &&
				(air_above || !biome);

			if (is_stone_surface || is_water_surface) {
				biome = biomegen->getBiomeAtIndex(index, y);

				if (biomemap[index] == BIOME_NONE && is_stone_surface)
					biomemap[index] = biome->index;

				depth_top = biome->depth_top;
				base_filler = MYMAX(depth_top +
					biome->depth_filler +
					noise_filler_depth->result[index], 0.f);
				depth_water_top = biome->depth_water_top;
				depth_riverbed = biome->depth_riverbed;

				// Detect stone type for dungeons during every biome calculation.
				// This is more efficient than detecting per-node and will not
				// miss any desert stone or sandstone biomes.
				if (biome->c_stone == c_desert_stone)
					stone_type = MGSTONE_DESERT_STONE;
				else if (biome->c_stone == c_sandstone)
					stone_type = MGSTONE_SANDSTONE;
			}

			if (c == c_stone) {
				content_t c_below = vm->m_data[vi - em.X].getContent();

				// If the node below isn't solid, make this node stone, so that
				// any top/filler nodes above are structurally supported.
				// This is done by aborting the cycle of top/filler placement
				// immediately by forcing nplaced to stone level.
				if (c_below == CONTENT_AIR
						|| c_below == c_water_source
						|| c_below == c_river_water_source)
					nplaced = U16_MAX;

				if (river_water_above) {
					if (nplaced < depth_riverbed) {
						vm->m_data[vi] = MapNode(biome->c_riverbed);
						nplaced++;
					} else {
						nplaced = U16_MAX;  // Disable top/filler placement
						river_water_above = false;
					}
				} else if (nplaced < depth_top) {
					vm->m_data[vi] = MapNode(biome->c_top);
					nplaced++;
				} else if (nplaced < base_filler) {
					vm->m_data[vi] = MapNode(biome->c_filler);
					nplaced++;
				} else {
					vm->m_data[vi] = MapNode(biome->c_stone);
				}

				air_above = false;
				water_above = false;
			} else if (c == c_water_source) {
				vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
						? biome->c_water_top : biome->c_water);
				nplaced = 0;  // Enable top/filler placement for next surface
				air_above = false;
				water_above = true;
			} else if (c == c_river_water_source) {
				vm->m_data[vi] = MapNode(biome->c_river_water);
				nplaced = 0;  // Enable riverbed placement for next surface
				air_above = false;
				water_above = true;
				river_water_above = true;
			} else if (c == CONTENT_AIR) {
				nplaced = 0;  // Enable top/filler placement for next surface
				air_above = true;
				water_above = false;
			} else {  // Possible various nodes overgenerated from neighbouring mapchunks
				nplaced = U16_MAX;  // Disable top/filler placement
				air_above = false;
				water_above = false;
			}

			vm->m_area.add_y(em, vi, -1);
		}
	}

	return stone_type;
}

void MapgenBasic::dustTopNodes()
{
	if (node_max.Y < water_level)
		return;

	v3s16 em = vm->m_area.getExtent();
	u32 index = 0;

	for (s16 z = node_min.Z; z <= node_max.Z; z++)
	for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
		Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);

		if (biome->c_dust == CONTENT_IGNORE)
			continue;

		u32 vi = vm->m_area.index(x, full_node_max.Y, z);
		content_t c_full_max = vm->m_data[vi].getContent();
		s16 y_start;

		if (c_full_max == CONTENT_AIR) {
			y_start = full_node_max.Y - 1;
		} else if (c_full_max == CONTENT_IGNORE) {
			vi = vm->m_area.index(x, node_max.Y + 1, z);
			content_t c_max = vm->m_data[vi].getContent();

			if (c_max == CONTENT_AIR)
				y_start = node_max.Y;
			else
				continue;
		} else {
			continue;
		}

		vi = vm->m_area.index(x, y_start, z);
		for (s16 y = y_start; y >= node_min.Y - 1; y--) {
			if (vm->m_data[vi].getContent() != CONTENT_AIR)
				break;

			vm->m_area.add_y(em, vi, -1);
		}

		content_t c = vm->m_data[vi].getContent();
		NodeDrawType dtype = ndef->get(c).drawtype;
		// Only place on walkable cubic non-liquid nodes
		// Dust check needed due to vertical overgeneration
		if ((dtype == NDT_NORMAL ||
				dtype == NDT_ALLFACES_OPTIONAL ||
				dtype == NDT_GLASSLIKE_FRAMED_OPTIONAL ||
				dtype == NDT_GLASSLIKE ||
				dtype == NDT_GLASSLIKE_FRAMED ||
				dtype == NDT_ALLFACES) &&
				ndef->get(c).walkable && c != biome->c_dust) {
			vm->m_area.add_y(em, vi, 1);
			vm->m_data[vi] = MapNode(biome->c_dust);
		}
	}
}

void MapgenBasic::generateCaves(s16 max_stone_y, s16 large_cave_depth)
{
	if (max_stone_y < node_min.Y)
		return;

	CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
		&np_cave1, &np_cave2, seed, cave_width);

	caves_noise.generateCaves(vm, node_min, node_max, biomemap);

	if (node_max.Y > large_cave_depth)
		return;

	PseudoRandom ps(blockseed + 21343);
	u32 bruises_count = ps.range(0, 2);
	for (u32 i = 0; i < bruises_count; i++) {
		CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
			c_water_source, CONTENT_IGNORE);

		cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
	}
}

bool MapgenBasic::generateCaverns(s16 max_stone_y)
{
	if (node_min.Y > max_stone_y || node_min.Y > cavern_limit)
		return false;

	CavernsNoise caverns_noise(ndef, csize, &np_cavern,
		seed, cavern_limit, cavern_taper, cavern_threshold);

	return caverns_noise.generateCaverns(vm, node_min, node_max);
}

void MapgenBasic::generateDungeons(s16 max_stone_y, MgStoneType stone_type)
{
	if (max_stone_y < node_min.Y)
		return;

	DungeonParams dp;

	dp.seed             = seed;
	dp.c_water          = c_water_source;
	dp.c_river_water    = c_river_water_source;

	dp.only_in_ground   = true;
	dp.corridor_len_min = 1;
	dp.corridor_len_max = 13;
	dp.rooms_min        = 2;
	dp.rooms_max        = 16;
	dp.y_min            = -MAX_MAP_GENERATION_LIMIT;
	dp.y_max            = MAX_MAP_GENERATION_LIMIT;

	dp.np_density       = nparams_dungeon_density;
	dp.np_alt_wall      = nparams_dungeon_alt_wall;

	switch (stone_type) {
	default:
	case MGSTONE_STONE:
		dp.c_wall              = c_cobble;
		dp.c_alt_wall          = c_mossycobble;
		dp.c_stair             = c_stair_cobble;

		dp.diagonal_dirs       = false;
		dp.holesize            = v3s16(1, 2, 1);
		dp.room_size_min       = v3s16(4, 4, 4);
		dp.room_size_max       = v3s16(8, 6, 8);
		dp.room_size_large_min = v3s16(8, 8, 8);
		dp.room_size_large_max = v3s16(16, 16, 16);
		dp.notifytype          = GENNOTIFY_DUNGEON;
		break;
	case MGSTONE_DESERT_STONE:
		dp.c_wall              = c_desert_stone;
		dp.c_alt_wall          = CONTENT_IGNORE;
		dp.c_stair             = c_stair_desert_stone;

		dp.diagonal_dirs       = true;
		dp.holesize            = v3s16(2, 3, 2);
		dp.room_size_min       = v3s16(6, 9, 6);
		dp.room_size_max       = v3s16(10, 11, 10);
		dp.room_size_large_min = v3s16(10, 13, 10);
		dp.room_size_large_max = v3s16(18, 21, 18);
		dp.notifytype          = GENNOTIFY_TEMPLE;
		break;
	case MGSTONE_SANDSTONE:
		dp.c_wall              = c_sandstonebrick;
		dp.c_alt_wall          = CONTENT_IGNORE;
		dp.c_stair             = c_stair_sandstone_block;

		dp.diagonal_dirs       = false;
		dp.holesize            = v3s16(2, 2, 2);
		dp.room_size_min       = v3s16(6, 4, 6);
		dp.room_size_max       = v3s16(10, 6, 10);
		dp.room_size_large_min = v3s16(10, 8, 10);
		dp.room_size_large_max = v3s16(18, 16, 18);
		dp.notifytype          = GENNOTIFY_DUNGEON;
		break;
	}

	DungeonGen dgen(ndef, &gennotify, &dp);
	dgen.generate(vm, blockseed, full_node_min, full_node_max);
}

////
//// GenerateNotifier
////

GenerateNotifier::GenerateNotifier()
{
	m_notify_on = 0;
}

GenerateNotifier::GenerateNotifier(u32 notify_on,
	std::set<u32> *notify_on_deco_ids)
{
	m_notify_on = notify_on;
	m_notify_on_deco_ids = notify_on_deco_ids;
}

void GenerateNotifier::setNotifyOn(u32 notify_on)
{
	m_notify_on = notify_on;
}

void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
{
	m_notify_on_deco_ids = notify_on_deco_ids;
}

bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
{
	if (!(m_notify_on & (1 << type)))
		return false;

	if (type == GENNOTIFY_DECORATION &&
		m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
		return false;

	GenNotifyEvent gne;
	gne.type = type;
	gne.pos  = pos;
	gne.id   = id;
	m_notify_events.push_back(gne);

	return true;
}

void GenerateNotifier::getEvents(
	std::map<std::string, std::vector<v3s16> > &event_map,
	bool peek_events)
{
	std::list<GenNotifyEvent>::iterator it;

	for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
		GenNotifyEvent &gn = *it;
		std::string name = (gn.type == GENNOTIFY_DECORATION) ?
			"decoration#"+ itos(gn.id) :
			flagdesc_gennotify[gn.type].name;

		event_map[name].push_back(gn.pos);
	}

	if (!peek_events)
		m_notify_events.clear();
}

////
//// MapgenParams
////

MapgenParams::~MapgenParams()
{
	delete bparams;
}

void MapgenParams::readParams(const Settings *settings)
{
	std::string seed_str;
	const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";

	if (settings->getNoEx(seed_name, seed_str)) {
		if (!seed_str.empty())
			seed = read_seed(seed_str.c_str());
		else
			myrand_bytes(&seed, sizeof(seed));
	}

	std::string mg_name;
	if (settings->getNoEx("mg_name", mg_name)) {
		mgtype = Mapgen::getMapgenType(mg_name);
		if (mgtype == MAPGEN_INVALID)
			mgtype = MAPGEN_DEFAULT;
	}

	settings->getS16NoEx("water_level", water_level);
	settings->getS16NoEx("mapgen_limit", mapgen_limit);
	settings->getS16NoEx("chunksize", chunksize);
	settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);

	delete bparams;
	bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
	if (bparams) {
		bparams->readParams(settings);
		bparams->seed = seed;
	}
}

void MapgenParams::writeParams(Settings *settings) const
{
	settings->set("mg_name", Mapgen::getMapgenName(mgtype));
	settings->setU64("seed", seed);
	settings->setS16("water_level", water_level);
	settings->setS16("mapgen_limit", mapgen_limit);
	settings->setS16("chunksize", chunksize);
	settings->setFlagStr("mg_flags", flags, flagdesc_mapgen, U32_MAX);

	if (bparams)
		bparams->writeParams(settings);
}

// Calculate edges of outermost generated mapchunks (less than
// 'mapgen_limit'), and corresponding exact limits for SAO entities.
void MapgenParams::calcMapgenEdges()
{
	if (m_mapgen_edges_calculated)
		return;

	// Central chunk offset, in blocks
	s16 ccoff_b = -chunksize / 2;
	// Chunksize, in nodes
	s32 csize_n = chunksize * MAP_BLOCKSIZE;
	// Minp/maxp of central chunk, in nodes
	s16 ccmin = ccoff_b * MAP_BLOCKSIZE;
	s16 ccmax = ccmin + csize_n - 1;
	// Fullminp/fullmaxp of central chunk, in nodes
	s16 ccfmin = ccmin - MAP_BLOCKSIZE;
	s16 ccfmax = ccmax + MAP_BLOCKSIZE;
	// Effective mapgen limit, in blocks
	// Uses same calculation as ServerMap::blockpos_over_mapgen_limit(v3s16 p)
	s16 mapgen_limit_b = rangelim(mapgen_limit,
		0, MAX_MAP_GENERATION_LIMIT) / MAP_BLOCKSIZE;
	// Effective mapgen limits, in nodes
	s16 mapgen_limit_min = -mapgen_limit_b * MAP_BLOCKSIZE;
	s16 mapgen_limit_max = (mapgen_limit_b + 1) * MAP_BLOCKSIZE - 1;
	// Number of complete chunks from central chunk fullminp/fullmaxp
	// to effective mapgen limits.
	s16 numcmin = MYMAX((ccfmin - mapgen_limit_min) / csize_n, 0);
	s16 numcmax = MYMAX((mapgen_limit_max - ccfmax) / csize_n, 0);
	// Mapgen edges, in nodes
	mapgen_edge_min = ccmin - numcmin * csize_n;
	mapgen_edge_max = ccmax + numcmax * csize_n;
	// SAO position limits, in Irrlicht units
	m_sao_limit_min = mapgen_edge_min * BS - 3.0f;
	m_sao_limit_max = mapgen_edge_max * BS + 3.0f;

	m_mapgen_edges_calculated = true;
}

bool MapgenParams::saoPosOverLimit(const v3f &p)
{
	if (!m_mapgen_edges_calculated)
		calcMapgenEdges();

	return p.X < m_sao_limit_min ||
		p.X > m_sao_limit_max ||
		p.Y < m_sao_limit_min ||
		p.Y > m_sao_limit_max ||
		p.Z < m_sao_limit_min ||
		p.Z > m_sao_limit_max;
}

s32 MapgenParams::getSpawnRangeMax()
{
	calcMapgenEdges();

	return MYMIN(-mapgen_edge_min, mapgen_edge_max);
}


code:
/*
Minetest
Copyright (C) 2010-2015 celeron55, Perttu Ahola <celeron55@gmail.com>
Copyright (C) 2013-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
Copyright (C) 2015-2017 paramat

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.
*/

#ifndef MAPGEN_HEADER
#define MAPGEN_HEADER

#include "noise.h"
#include "nodedef.h"
#include "mapnode.h"
#include "util/string.h"
#include "util/container.h"

#define MAPGEN_DEFAULT MAPGEN_V7
#define MAPGEN_DEFAULT_NAME "v7"

/////////////////// Mapgen flags
#define MG_TREES       0x01  // Deprecated. Moved into mgv6 flags
#define MG_CAVES       0x02
#define MG_DUNGEONS    0x04
#define MG_FLAT        0x08  // Deprecated. Moved into mgv6 flags
#define MG_LIGHT       0x10
#define MG_DECORATIONS 0x20

typedef u8 biome_t;  // copy from mg_biome.h to avoid an unnecessary include

class Settings;
class MMVManip;
class INodeDefManager;

extern FlagDesc flagdesc_mapgen[];
extern FlagDesc flagdesc_gennotify[];

class Biome;
class BiomeGen;
struct BiomeParams;
class BiomeManager;
class EmergeManager;
class MapBlock;
class VoxelManipulator;
struct BlockMakeData;
class VoxelArea;
class Map;

enum MapgenObject {
	MGOBJ_VMANIP,
	MGOBJ_HEIGHTMAP,
	MGOBJ_BIOMEMAP,
	MGOBJ_HEATMAP,
	MGOBJ_HUMIDMAP,
	MGOBJ_GENNOTIFY
};

enum GenNotifyType {
	GENNOTIFY_DUNGEON,
	GENNOTIFY_TEMPLE,
	GENNOTIFY_CAVE_BEGIN,
	GENNOTIFY_CAVE_END,
	GENNOTIFY_LARGECAVE_BEGIN,
	GENNOTIFY_LARGECAVE_END,
	GENNOTIFY_DECORATION,
	NUM_GENNOTIFY_TYPES
};

// TODO(hmmmm/paramat): make stone type selection dynamic
enum MgStoneType {
	MGSTONE_STONE,
	MGSTONE_DESERT_STONE,
	MGSTONE_SANDSTONE,
};

struct GenNotifyEvent {
	GenNotifyType type;
	v3s16 pos;
	u32 id;
};

class GenerateNotifier {
public:
	GenerateNotifier();
	GenerateNotifier(u32 notify_on, std::set<u32> *notify_on_deco_ids);

	void setNotifyOn(u32 notify_on);
	void setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids);

	bool addEvent(GenNotifyType type, v3s16 pos, u32 id=0);
	void getEvents(std::map<std::string, std::vector<v3s16> > &event_map,
		bool peek_events=false);

private:
	u32 m_notify_on;
	std::set<u32> *m_notify_on_deco_ids;
	std::list<GenNotifyEvent> m_notify_events;
};

enum MapgenType {
	MAPGEN_V5,
	MAPGEN_V6,
	MAPGEN_V7,
	MAPGEN_FLAT,
	MAPGEN_FRACTAL,
	MAPGEN_VALLEYS,
	MAPGEN_SINGLENODE,
	MAPGEN_INVALID,
};

struct MapgenParams {
	MapgenType mgtype;
	s16 chunksize;
	u64 seed;
	s16 water_level;
	s16 mapgen_limit;
	u32 flags;

	BiomeParams *bparams;

	s16 mapgen_edge_min;
	s16 mapgen_edge_max;

	MapgenParams() :
		mgtype(MAPGEN_DEFAULT),
		chunksize(5),
		seed(0),
		water_level(1),
		mapgen_limit(MAX_MAP_GENERATION_LIMIT),
		flags(MG_CAVES | MG_LIGHT | MG_DECORATIONS),
		bparams(NULL),

		mapgen_edge_min(-MAX_MAP_GENERATION_LIMIT),
		mapgen_edge_max(MAX_MAP_GENERATION_LIMIT),
		m_sao_limit_min(-MAX_MAP_GENERATION_LIMIT * BS),
		m_sao_limit_max(MAX_MAP_GENERATION_LIMIT * BS),
		m_mapgen_edges_calculated(false)
	{
	}

	virtual ~MapgenParams();

	virtual void readParams(const Settings *settings);
	virtual void writeParams(Settings *settings) const;

	bool saoPosOverLimit(const v3f &p);
	s32 getSpawnRangeMax();

private:
	void calcMapgenEdges();

	float m_sao_limit_min;
	float m_sao_limit_max;
	bool m_mapgen_edges_calculated;
};

/*
	Generic interface for map generators.  All mapgens must inherit this class.
	If a feature exposed by a public member pointer is not supported by a
	certain mapgen, it must be set to NULL.

	Apart from makeChunk, getGroundLevelAtPoint, and getSpawnLevelAtPoint, all
	methods can be used by constructing a Mapgen base class and setting the
	appropriate public members (e.g. vm, ndef, and so on).
*/
class Mapgen {
public:
	s32 seed;
	int water_level;
	int mapgen_limit;
	u32 flags;
	bool generating;
	int id;

	MMVManip *vm;
	INodeDefManager *ndef;

	u32 blockseed;
	s16 *heightmap;
	biome_t *biomemap;
	v3s16 csize;

	BiomeGen *biomegen;
	GenerateNotifier gennotify;

	Mapgen();
	Mapgen(int mapgenid, MapgenParams *params, EmergeManager *emerge);
	virtual ~Mapgen();

	virtual MapgenType getType() const { return MAPGEN_INVALID; }

	static u32 getBlockSeed(v3s16 p, s32 seed);
	static u32 getBlockSeed2(v3s16 p, s32 seed);
	s16 findGroundLevelFull(v2s16 p2d);
	s16 findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax);
	s16 findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax);
	void updateHeightmap(v3s16 nmin, v3s16 nmax);
	void updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax);

	void setLighting(u8 light, v3s16 nmin, v3s16 nmax);
	void lightSpread(VoxelArea &a, v3s16 p, u8 light);
	void calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
		bool propagate_shadow = true);
	void propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow);
	void spreadLight(v3s16 nmin, v3s16 nmax);

	virtual void makeChunk(BlockMakeData *data) {}
	virtual int getGroundLevelAtPoint(v2s16 p) { return 0; }

	// getSpawnLevelAtPoint() is a function within each mapgen that returns a
	// suitable y co-ordinate for player spawn ('suitable' usually meaning
	// within 16 nodes of water_level). If a suitable spawn level cannot be
	// found at the specified (X, Z) 'MAX_MAP_GENERATION_LIMIT' is returned to
	// signify this and to cause Server::findSpawnPos() to try another (X, Z).
	virtual int getSpawnLevelAtPoint(v2s16 p) { return 0; }

	// Mapgen management functions
	static MapgenType getMapgenType(const std::string &mgname);
	static const char *getMapgenName(MapgenType mgtype);
	static Mapgen *createMapgen(MapgenType mgtype, int mgid,
		MapgenParams *params, EmergeManager *emerge);
	static MapgenParams *createMapgenParams(MapgenType mgtype);
	static void getMapgenNames(std::vector<const char *> *mgnames, bool include_hidden);

private:
	// isLiquidHorizontallyFlowable() is a helper function for updateLiquid()
	// that checks whether there are floodable nodes without liquid beneath
	// the node at index vi.
	inline bool isLiquidHorizontallyFlowable(u32 vi, v3s16 em);
	DISABLE_CLASS_COPY(Mapgen);
};

/*
	MapgenBasic is a Mapgen implementation that handles basic functionality
	the majority of conventional mapgens will probably want to use, but isn't
	generic enough to be included as part of the base Mapgen class (such as
	generating biome terrain over terrain node skeletons, generating caves,
	dungeons, etc.)

	Inherit MapgenBasic instead of Mapgen to add this basic functionality to
	your mapgen without having to reimplement it.  Feel free to override any of
	these methods if you desire different or more advanced behavior.

	Note that you must still create your own generateTerrain implementation when
	inheriting MapgenBasic.
*/
class MapgenBasic : public Mapgen {
public:
	MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge);
	virtual ~MapgenBasic();

	virtual void generateCaves(s16 max_stone_y, s16 large_cave_depth);
	virtual bool generateCaverns(s16 max_stone_y);
	virtual void generateDungeons(s16 max_stone_y, MgStoneType stone_type);
	virtual MgStoneType generateBiomes();
	virtual void dustTopNodes();

protected:
	EmergeManager *m_emerge;
	BiomeManager *m_bmgr;

	Noise *noise_filler_depth;

	v3s16 node_min;
	v3s16 node_max;
	v3s16 full_node_min;
	v3s16 full_node_max;

	// Content required for generateBiomes
	content_t c_stone;
	content_t c_desert_stone;
	content_t c_sandstone;
	content_t c_water_source;
	content_t c_river_water_source;
	content_t c_lava_source;

	// Content required for generateDungeons
	content_t c_cobble;
	content_t c_stair_cobble;
	content_t c_mossycobble;
	content_t c_stair_desert_stone;
	content_t c_sandstonebrick;
	content_t c_stair_sandstone_block;

	int ystride;
	int zstride;
	int zstride_1d;
	int zstride_1u1d;

	u32 spflags;

	NoiseParams np_cave1;
	NoiseParams np_cave2;
	NoiseParams np_cavern;
	float cave_width;
	float cavern_limit;
	float cavern_taper;
	float cavern_threshold;
};

#endif

repo_name: pgimeno/minetest

license: unknown


code:
/*
Minetest
Copyright (C) 2015-2017 paramat
Copyright (C) 2015-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

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 "mapgen.h"
#include "voxel.h"
#include "noise.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "content_sao.h"
#include "nodedef.h"
#include "voxelalgorithms.h"
//#include "profiler.h" // For TimeTaker
#include "settings.h" // For g_settings
#include "emerge.h"
#include "dungeongen.h"
#include "cavegen.h"
#include "mg_biome.h"
#include "mg_ore.h"
#include "mg_decoration.h"
#include "mapgen_flat.h"

FlagDesc flagdesc_mapgen_flat[] = {
	{"lakes", MGFLAT_LAKES},
	{"hills", MGFLAT_HILLS},
	{NULL,    0}
};

///////////////////////////////////////////////////////////////////////////////////////

MapgenFlat::MapgenFlat(int mapgenid, MapgenFlatParams *params, EmergeManager *emerge)
	: MapgenBasic(mapgenid, params, emerge)
{
	this->spflags          = params->spflags;
	this->ground_level     = params->ground_level;
	this->large_cave_depth = params->large_cave_depth;
	this->cave_width       = params->cave_width;
	this->lake_threshold   = params->lake_threshold;
	this->lake_steepness   = params->lake_steepness;
	this->hill_threshold   = params->hill_threshold;
	this->hill_steepness   = params->hill_steepness;

	// 2D noise
	noise_filler_depth = new Noise(&params->np_filler_depth, seed, csize.X, csize.Z);

	if ((spflags & MGFLAT_LAKES) || (spflags & MGFLAT_HILLS))
		noise_terrain = new Noise(&params->np_terrain, seed, csize.X, csize.Z);
	// 3D noise
	MapgenBasic::np_cave1 = params->np_cave1;
	MapgenBasic::np_cave2 = params->np_cave2;
}

MapgenFlat::~MapgenFlat()
{
	delete noise_filler_depth;

	if ((spflags & MGFLAT_LAKES) || (spflags & MGFLAT_HILLS))
		delete noise_terrain;
}

MapgenFlatParams::MapgenFlatParams()
{
	spflags          = 0;
	ground_level     = 8;
	large_cave_depth = -33;
	cave_width       = 0.09;
	lake_threshold   = -0.45;
	lake_steepness   = 48.0;
	hill_threshold   = 0.45;
	hill_steepness   = 64.0;

	np_terrain      = NoiseParams(0, 1,   v3f(600, 600, 600), 7244,  5, 0.6, 2.0);
	np_filler_depth = NoiseParams(0, 1.2, v3f(150, 150, 150), 261,   3, 0.7, 2.0);
	np_cave1        = NoiseParams(0, 12,  v3f(61,  61,  61),  52534, 3, 0.5, 2.0);
	np_cave2        = NoiseParams(0, 12,  v3f(67,  67,  67),  10325, 3, 0.5, 2.0);
}

void MapgenFlatParams::readParams(const Settings *settings)
{
	settings->getFlagStrNoEx("mgflat_spflags",      spflags, flagdesc_mapgen_flat);
	settings->getS16NoEx("mgflat_ground_level",     ground_level);
	settings->getS16NoEx("mgflat_large_cave_depth", large_cave_depth);
	settings->getFloatNoEx("mgflat_cave_width",     cave_width);
	settings->getFloatNoEx("mgflat_lake_threshold", lake_threshold);
	settings->getFloatNoEx("mgflat_lake_steepness", lake_steepness);
	settings->getFloatNoEx("mgflat_hill_threshold", hill_threshold);
	settings->getFloatNoEx("mgflat_hill_steepness", hill_steepness);

	settings->getNoiseParams("mgflat_np_terrain",      np_terrain);
	settings->getNoiseParams("mgflat_np_filler_depth", np_filler_depth);
	settings->getNoiseParams("mgflat_np_cave1",        np_cave1);
	settings->getNoiseParams("mgflat_np_cave2",        np_cave2);
}

void MapgenFlatParams::writeParams(Settings *settings) const
{
	settings->setFlagStr("mgflat_spflags",      spflags, flagdesc_mapgen_flat, U32_MAX);
	settings->setS16("mgflat_ground_level",     ground_level);
	settings->setS16("mgflat_large_cave_depth", large_cave_depth);
	settings->setFloat("mgflat_cave_width",     cave_width);
	settings->setFloat("mgflat_lake_threshold", lake_threshold);
	settings->setFloat("mgflat_lake_steepness", lake_steepness);
	settings->setFloat("mgflat_hill_threshold", hill_threshold);
	settings->setFloat("mgflat_hill_steepness", hill_steepness);

	settings->setNoiseParams("mgflat_np_terrain",      np_terrain);
	settings->setNoiseParams("mgflat_np_filler_depth", np_filler_depth);
	settings->setNoiseParams("mgflat_np_cave1",        np_cave1);
	settings->setNoiseParams("mgflat_np_cave2",        np_cave2);
}

/////////////////////////////////////////////////////////////////

int MapgenFlat::getSpawnLevelAtPoint(v2s16 p)
{
	s16 level_at_point = ground_level;
	float n_terrain = 0.0f;
	if ((spflags & MGFLAT_LAKES) || (spflags & MGFLAT_HILLS))
		n_terrain = NoisePerlin2D(&noise_terrain->np, p.X, p.Y, seed);

	if ((spflags & MGFLAT_LAKES) && n_terrain < lake_threshold) {
		level_at_point = ground_level -
			(lake_threshold - n_terrain) * lake_steepness;
	} else if ((spflags & MGFLAT_HILLS) && n_terrain > hill_threshold) {
		level_at_point = ground_level +
			(n_terrain - hill_threshold) * hill_steepness;
	}

	if (ground_level < water_level)  // Ocean world, allow spawn in water
		return MYMAX(level_at_point, water_level);
	else if (level_at_point > water_level)
		return level_at_point;  // Spawn on land
	else
		return MAX_MAP_GENERATION_LIMIT;  // Unsuitable spawn point
}

void MapgenFlat::makeChunk(BlockMakeData *data)
{
	// Pre-conditions
	assert(data->vmanip);
	assert(data->nodedef);
	assert(data->blockpos_requested.X >= data->blockpos_min.X &&
		data->blockpos_requested.Y >= data->blockpos_min.Y &&
		data->blockpos_requested.Z >= data->blockpos_min.Z);
	assert(data->blockpos_requested.X <= data->blockpos_max.X &&
		data->blockpos_requested.Y <= data->blockpos_max.Y &&
		data->blockpos_requested.Z <= data->blockpos_max.Z);

	this->generating = true;
	this->vm   = data->vmanip;
	this->ndef = data->nodedef;
	//TimeTaker t("makeChunk");

	v3s16 blockpos_min = data->blockpos_min;
	v3s16 blockpos_max = data->blockpos_max;
	node_min = blockpos_min * MAP_BLOCKSIZE;
	node_max = (blockpos_max + v3s16(1, 1, 1)) * MAP_BLOCKSIZE - v3s16(1, 1, 1);
	full_node_min = (blockpos_min - 1) * MAP_BLOCKSIZE;
	full_node_max = (blockpos_max + 2) * MAP_BLOCKSIZE - v3s16(1, 1, 1);

	blockseed = getBlockSeed2(full_node_min, seed);

	// Generate base terrain, mountains, and ridges with initial heightmaps
	s16 stone_surface_max_y = generateTerrain();

	// Create heightmap
	updateHeightmap(node_min, node_max);

	// Init biome generator, place biome-specific nodes, and build biomemap
	biomegen->calcBiomeNoise(node_min);
	MgStoneType stone_type = generateBiomes();

	if (flags & MG_CAVES)
		generateCaves(stone_surface_max_y, large_cave_depth);

	if (flags & MG_DUNGEONS)
		generateDungeons(stone_surface_max_y, stone_type);

	// Generate the registered decorations
	if (flags & MG_DECORATIONS)
		m_emerge->decomgr->placeAllDecos(this, blockseed, node_min, node_max);

	// Generate the registered ores
	m_emerge->oremgr->placeAllOres(this, blockseed, node_min, node_max);

	// Sprinkle some dust on top after everything else was generated
	dustTopNodes();

	//printf("makeChunk: %dms\n", t.stop());

	updateLiquid(&data->transforming_liquid, full_node_min, full_node_max);

	if (flags & MG_LIGHT)
		calcLighting(node_min - v3s16(0, 1, 0), node_max + v3s16(0, 1, 0),
			full_node_min, full_node_max);

	//setLighting(node_min - v3s16(1, 0, 1) * MAP_BLOCKSIZE,
	//			node_max + v3s16(1, 0, 1) * MAP_BLOCKSIZE, 0xFF);

	this->generating = false;
}

s16 MapgenFlat::generateTerrain()
{
	MapNode n_air(CONTENT_AIR);
	MapNode n_stone(c_stone);
	MapNode n_water(c_water_source);

	v3s16 em = vm->m_area.getExtent();
	s16 stone_surface_max_y = -MAX_MAP_GENERATION_LIMIT;
	u32 ni2d = 0;

	bool use_noise = (spflags & MGFLAT_LAKES) || (spflags & MGFLAT_HILLS);
	if (use_noise)
		noise_terrain->perlinMap2D(node_min.X, node_min.Z);

	for (s16 z = node_min.Z; z <= node_max.Z; z++)
	for (s16 x = node_min.X; x <= node_max.X; x++, ni2d++) {
		s16 stone_level = ground_level;
		float n_terrain = use_noise ? noise_terrain->result[ni2d] : 0.0f;

		if ((spflags & MGFLAT_LAKES) && n_terrain < lake_threshold) {
			s16 depress = (lake_threshold - n_terrain) * lake_steepness;
			stone_level = ground_level - depress;
		} else if ((spflags & MGFLAT_HILLS) && n_terrain > hill_threshold) {
			s16 rise = (n_terrain - hill_threshold) * hill_steepness;
		 	stone_level = ground_level + rise;
		}

		u32 vi = vm->m_area.index(x, node_min.Y - 1, z);
		for (s16 y = node_min.Y - 1; y <= node_max.Y + 1; y++) {
			if (vm->m_data[vi].getContent() == CONTENT_IGNORE) {
				if (y <= stone_level) {
					vm->m_data[vi] = n_stone;
					if (y > stone_surface_max_y)
						stone_surface_max_y = y;
				} else if (y <= water_level) {
					vm->m_data[vi] = n_water;
				} else {
					vm->m_data[vi] = n_air;
				}
			}
			vm->m_area.add_y(em, vi, 1);
		}
	}

	return stone_surface_max_y;
}


code:
/*
Minetest
Copyright (C) 2015-2017 paramat
Copyright (C) 2015-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

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.
*/

#ifndef MAPGEN_FLAT_HEADER
#define MAPGEN_FLAT_HEADER

#include "mapgen.h"

/////// Mapgen Flat flags
#define MGFLAT_LAKES 0x01
#define MGFLAT_HILLS 0x02

class BiomeManager;

extern FlagDesc flagdesc_mapgen_flat[];

struct MapgenFlatParams : public MapgenParams
{
	u32 spflags;
	s16 ground_level;
	s16 large_cave_depth;
	float cave_width;
	float lake_threshold;
	float lake_steepness;
	float hill_threshold;
	float hill_steepness;
	NoiseParams np_terrain;
	NoiseParams np_filler_depth;
	NoiseParams np_cave1;
	NoiseParams np_cave2;

	MapgenFlatParams();
	~MapgenFlatParams() {}

	void readParams(const Settings *settings);
	void writeParams(Settings *settings) const;
};

class MapgenFlat : public MapgenBasic
{
public:
	MapgenFlat(int mapgenid, MapgenFlatParams *params, EmergeManager *emerge);
	~MapgenFlat();

	virtual MapgenType getType() const { return MAPGEN_FLAT; }

	virtual void makeChunk(BlockMakeData *data);
	int getSpawnLevelAtPoint(v2s16 p);
	s16 generateTerrain();

private:
	s16 ground_level;
	s16 large_cave_depth;
	float lake_threshold;
	float lake_steepness;
	float hill_threshold;
	float hill_steepness;
	Noise *noise_terrain;
};

#endif


code:
/*
Minetest
Copyright (C) 2015-2017 paramat
Copyright (C) 2015-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

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 "mapgen.h"
#include "voxel.h"
#include "noise.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "content_sao.h"
#include "nodedef.h"
#include "voxelalgorithms.h"
//#include "profiler.h" // For TimeTaker
#include "settings.h" // For g_settings
#include "emerge.h"
#include "dungeongen.h"
#include "cavegen.h"
#include "mg_biome.h"
#include "mg_ore.h"
#include "mg_decoration.h"
#include "mapgen_fractal.h"

FlagDesc flagdesc_mapgen_fractal[] = {
	{NULL,    0}
};

///////////////////////////////////////////////////////////////////////////////////////

MapgenFractal::MapgenFractal(int mapgenid, MapgenFractalParams *params, EmergeManager *emerge)
	: MapgenBasic(mapgenid, params, emerge)
{
	this->spflags    = params->spflags;
	this->cave_width = params->cave_width;
	this->fractal    = params->fractal;
	this->iterations = params->iterations;
	this->scale      = params->scale;
	this->offset     = params->offset;
	this->slice_w    = params->slice_w;
	this->julia_x    = params->julia_x;
	this->julia_y    = params->julia_y;
	this->julia_z    = params->julia_z;
	this->julia_w    = params->julia_w;

	//// 2D terrain noise
	noise_seabed       = new Noise(&params->np_seabed, seed, csize.X, csize.Z);
	noise_filler_depth = new Noise(&params->np_filler_depth, seed, csize.X, csize.Z);

	MapgenBasic::np_cave1 = params->np_cave1;
	MapgenBasic::np_cave2 = params->np_cave2;

	this->formula = fractal / 2 + fractal % 2;
	this->julia   = fractal % 2 == 0;
}

MapgenFractal::~MapgenFractal()
{
	delete noise_seabed;
	delete noise_filler_depth;
}

MapgenFractalParams::MapgenFractalParams()
{
	spflags    = 0;
	cave_width = 0.09;
	fractal    = 1;
	iterations = 11;
	scale      = v3f(4096.0, 1024.0, 4096.0);
	offset     = v3f(1.79, 0.0, 0.0);
	slice_w    = 0.0;
	julia_x    = 0.33;
	julia_y    = 0.33;
	julia_z    = 0.33;
	julia_w    = 0.33;

	np_seabed       = NoiseParams(-14, 9,   v3f(600, 600, 600), 41900, 5, 0.6, 2.0);
	np_filler_depth = NoiseParams(0,   1.2, v3f(150, 150, 150), 261,   3, 0.7, 2.0);
	np_cave1        = NoiseParams(0,   12,  v3f(61,  61,  61),  52534, 3, 0.5, 2.0);
	np_cave2        = NoiseParams(0,   12,  v3f(67,  67,  67),  10325, 3, 0.5, 2.0);
}

void MapgenFractalParams::readParams(const Settings *settings)
{
	settings->getFlagStrNoEx("mgfractal_spflags",  spflags, flagdesc_mapgen_fractal);
	settings->getFloatNoEx("mgfractal_cave_width", cave_width);
	settings->getU16NoEx("mgfractal_fractal",      fractal);
	settings->getU16NoEx("mgfractal_iterations",   iterations);
	settings->getV3FNoEx("mgfractal_scale",        scale);
	settings->getV3FNoEx("mgfractal_offset",       offset);
	settings->getFloatNoEx("mgfractal_slice_w",    slice_w);
	settings->getFloatNoEx("mgfractal_julia_x",    julia_x);
	settings->getFloatNoEx("mgfractal_julia_y",    julia_y);
	settings->getFloatNoEx("mgfractal_julia_z",    julia_z);
	settings->getFloatNoEx("mgfractal_julia_w",    julia_w);

	settings->getNoiseParams("mgfractal_np_seabed",       np_seabed);
	settings->getNoiseParams("mgfractal_np_filler_depth", np_filler_depth);
	settings->getNoiseParams("mgfractal_np_cave1",        np_cave1);
	settings->getNoiseParams("mgfractal_np_cave2",        np_cave2);
}

void MapgenFractalParams::writeParams(Settings *settings) const
{
	settings->setFlagStr("mgfractal_spflags",  spflags, flagdesc_mapgen_fractal, U32_MAX);
	settings->setFloat("mgfractal_cave_width", cave_width);
	settings->setU16("mgfractal_fractal",      fractal);
	settings->setU16("mgfractal_iterations",   iterations);
	settings->setV3F("mgfractal_scale",        scale);
	settings->setV3F("mgfractal_offset",       offset);
	settings->setFloat("mgfractal_slice_w",    slice_w);
	settings->setFloat("mgfractal_julia_x",    julia_x);
	settings->setFloat("mgfractal_julia_y",    julia_y);
	settings->setFloat("mgfractal_julia_z",    julia_z);
	settings->setFloat("mgfractal_julia_w",    julia_w);

	settings->setNoiseParams("mgfractal_np_seabed",       np_seabed);
	settings->setNoiseParams("mgfractal_np_filler_depth", np_filler_depth);
	settings->setNoiseParams("mgfractal_np_cave1",        np_cave1);
	settings->setNoiseParams("mgfractal_np_cave2",        np_cave2);
}

/////////////////////////////////////////////////////////////////

int MapgenFractal::getSpawnLevelAtPoint(v2s16 p)
{
	bool solid_below = false;  // Dry solid node is present below to spawn on
	u8 air_count = 0;  // Consecutive air nodes above the dry solid node
	s16 seabed_level = NoisePerlin2D(&noise_seabed->np, p.X, p.Y, seed);
	// Seabed can rise above water_level or might be raised to create dry land
	s16 search_start = MYMAX(seabed_level, water_level + 1);
	if (seabed_level > water_level)
		solid_below = true;

	for (s16 y = search_start; y <= search_start + 128; y++) {
		if (getFractalAtPoint(p.X, y, p.Y)) {  // Fractal node
			solid_below = true;
			air_count = 0;
		} else if (solid_below) {  // Air above solid node
			air_count++;
			if (air_count == 2)
				return y - 2;
		}
	}

	return MAX_MAP_GENERATION_LIMIT;  // Unsuitable spawn point
}

void MapgenFractal::makeChunk(BlockMakeData *data)
{
	// Pre-conditions
	assert(data->vmanip);
	assert(data->nodedef);
	assert(data->blockpos_requested.X >= data->blockpos_min.X &&
		data->blockpos_requested.Y >= data->blockpos_min.Y &&
		data->blockpos_requested.Z >= data->blockpos_min.Z);
	assert(data->blockpos_requested.X <= data->blockpos_max.X &&
		data->blockpos_requested.Y <= data->blockpos_max.Y &&
		data->blockpos_requested.Z <= data->blockpos_max.Z);

	this->generating = true;
	this->vm   = data->vmanip;
	this->ndef = data->nodedef;
	//TimeTaker t("makeChunk");

	v3s16 blockpos_min = data->blockpos_min;
	v3s16 blockpos_max = data->blockpos_max;
	node_min = blockpos_min * MAP_BLOCKSIZE;
	node_max = (blockpos_max + v3s16(1, 1, 1)) * MAP_BLOCKSIZE - v3s16(1, 1, 1);
	full_node_min = (blockpos_min - 1) * MAP_BLOCKSIZE;
	full_node_max = (blockpos_max + 2) * MAP_BLOCKSIZE - v3s16(1, 1, 1);

	blockseed = getBlockSeed2(full_node_min, seed);

	// Generate base terrain, mountains, and ridges with initial heightmaps
	s16 stone_surface_max_y = generateTerrain();

	// Create heightmap
	updateHeightmap(node_min, node_max);

	// Init biome generator, place biome-specific nodes, and build biomemap
	biomegen->calcBiomeNoise(node_min);
	MgStoneType stone_type = generateBiomes();

	if (flags & MG_CAVES)
		generateCaves(stone_surface_max_y, MGFRACTAL_LARGE_CAVE_DEPTH);

	if (flags & MG_DUNGEONS)
		generateDungeons(stone_surface_max_y, stone_type);

	// Generate the registered decorations
	if (flags & MG_DECORATIONS)
		m_emerge->decomgr->placeAllDecos(this, blockseed, node_min, node_max);

	// Generate the registered ores
	m_emerge->oremgr->placeAllOres(this, blockseed, node_min, node_max);

	// Sprinkle some dust on top after everything else was generated
	dustTopNodes();

	//printf("makeChunk: %dms\n", t.stop());

	updateLiquid(&data->transforming_liquid, full_node_min, full_node_max);

	if (flags & MG_LIGHT)
		calcLighting(node_min - v3s16(0, 1, 0), node_max + v3s16(0, 1, 0),
			full_node_min, full_node_max);

	//setLighting(node_min - v3s16(1, 0, 1) * MAP_BLOCKSIZE,
	//			node_max + v3s16(1, 0, 1) * MAP_BLOCKSIZE, 0xFF);

	this->generating = false;
}

bool MapgenFractal::getFractalAtPoint(s16 x, s16 y, s16 z)
{
	float cx, cy, cz, cw, ox, oy, oz, ow;

	if (julia) {  // Julia set
		cx = julia_x;
		cy = julia_y;
		cz = julia_z;
		cw = julia_w;
		ox = (float)x / scale.X - offset.X;
		oy = (float)y / scale.Y - offset.Y;
		oz = (float)z / scale.Z - offset.Z;
		ow = slice_w;
	} else {  // Mandelbrot set
		cx = (float)x / scale.X - offset.X;
		cy = (float)y / scale.Y - offset.Y;
		cz = (float)z / scale.Z - offset.Z;
		cw = slice_w;
		ox = 0.0f;
		oy = 0.0f;
		oz = 0.0f;
		ow = 0.0f;
	}

	float nx = 0.0f;
	float ny = 0.0f;
	float nz = 0.0f;
	float nw = 0.0f;

	for (u16 iter = 0; iter < iterations; iter++) {

		if (formula == 1) {  // 4D "Roundy"
			nx = ox * ox - oy * oy - oz * oz - ow * ow + cx;
			ny = 2.0f * (ox * oy + oz * ow) + cy;
			nz = 2.0f * (ox * oz + oy * ow) + cz;
			nw = 2.0f * (ox * ow + oy * oz) + cw;
		} else if (formula == 2) {  // 4D "Squarry"
			nx = ox * ox - oy * oy - oz * oz - ow * ow + cx;
			ny = 2.0f * (ox * oy + oz * ow) + cy;
			nz = 2.0f * (ox * oz + oy * ow) + cz;
			nw = 2.0f * (ox * ow - oy * oz) + cw;
		} else if (formula == 3) {  // 4D "Mandy Cousin"
			nx = ox * ox - oy * oy - oz * oz + ow * ow + cx;
			ny = 2.0f * (ox * oy + oz * ow) + cy;
			nz = 2.0f * (ox * oz + oy * ow) + cz;
			nw = 2.0f * (ox * ow + oy * oz) + cw;
		} else if (formula == 4) {  // 4D "Variation"
			nx = ox * ox - oy * oy - oz * oz - ow * ow + cx;
			ny = 2.0f * (ox * oy + oz * ow) + cy;
			nz = 2.0f * (ox * oz - oy * ow) + cz;
			nw = 2.0f * (ox * ow + oy * oz) + cw;
		} else if (formula == 5) {  // 3D "Mandelbrot/Mandelbar"
			nx = ox * ox - oy * oy - oz * oz + cx;
			ny = 2.0f * ox * oy + cy;
			nz = -2.0f * ox * oz + cz;
		} else if (formula == 6) {  // 3D "Christmas Tree"
			// Altering the formula here is necessary to avoid division by zero
			if (fabs(oz) < 0.000000001f) {
				nx = ox * ox - oy * oy - oz * oz + cx;
				ny = 2.0f * oy * ox + cy;
				nz = 4.0f * oz * ox + cz;
			} else {
				float a = (2.0f * ox) / (sqrt(oy * oy + oz * oz));
				nx = ox * ox - oy * oy - oz * oz + cx;
				ny = a * (oy * oy - oz * oz) + cy;
				nz = a * 2.0f * oy * oz + cz;
			}
		} else if (formula == 7) {  // 3D "Mandelbulb"
			if (fabs(oy) < 0.000000001f) {
				nx = ox * ox - oz * oz + cx;
				ny = cy;
				nz = -2.0f * oz * sqrt(ox * ox) + cz;
			} else {
				float a = 1.0f - (oz * oz) / (ox * ox + oy * oy);
				nx = (ox * ox - oy * oy) * a + cx;
				ny = 2.0f * ox * oy * a + cy;
				nz = -2.0f * oz * sqrt(ox * ox + oy * oy) + cz;
			}
		} else if (formula == 8) {  // 3D "Cosine Mandelbulb"
			if (fabs(oy) < 0.000000001f) {
				nx = 2.0f * ox * oz + cx;
				ny = 4.0f * oy * oz + cy;
				nz = oz * oz - ox * ox - oy * oy + cz;
			} else {
				float a = (2.0f * oz) / sqrt(ox * ox + oy * oy);
				nx = (ox * ox - oy * oy) * a + cx;
				ny = 2.0f * ox * oy * a + cy;
				nz = oz * oz - ox * ox - oy * oy + cz;
			}
		} else if (formula == 9) {  // 4D "Mandelbulb"
			float rxy = sqrt(ox * ox + oy * oy);
			float rxyz = sqrt(ox * ox + oy * oy + oz * oz);
			if (fabs(ow) < 0.000000001f && fabs(oz) < 0.000000001f) {
				nx = (ox * ox - oy * oy) + cx;
				ny = 2.0f * ox * oy + cy;
				nz = -2.0f * rxy * oz + cz;
				nw = 2.0f * rxyz * ow + cw;
			} else {
				float a = 1.0f - (ow * ow) / (rxyz * rxyz);
				float b = a * (1.0f - (oz * oz) / (rxy * rxy));
				nx = (ox * ox - oy * oy) * b + cx;
				ny = 2.0f * ox * oy * b + cy;
				nz = -2.0f * rxy * oz * a + cz;
				nw = 2.0f * rxyz * ow + cw;
			}
		}

		if (nx * nx + ny * ny + nz * nz + nw * nw > 4.0f)
			return false;

		ox = nx;
		oy = ny;
		oz = nz;
		ow = nw;
	}

	return true;
}

s16 MapgenFractal::generateTerrain()
{
	MapNode n_air(CONTENT_AIR);
	MapNode n_stone(c_stone);
	MapNode n_water(c_water_source);

	s16 stone_surface_max_y = -MAX_MAP_GENERATION_LIMIT;
	u32 index2d = 0;

	noise_seabed->perlinMap2D(node_min.X, node_min.Z);

	for (s16 z = node_min.Z; z <= node_max.Z; z++) {
		for (s16 y = node_min.Y - 1; y <= node_max.Y + 1; y++) {
			u32 vi = vm->m_area.index(node_min.X, y, z);
			for (s16 x = node_min.X; x <= node_max.X; x++, vi++, index2d++) {
				if (vm->m_data[vi].getContent() == CONTENT_IGNORE) {
					s16 seabed_height = noise_seabed->result[index2d];

					if (y <= seabed_height || getFractalAtPoint(x, y, z)) {
						vm->m_data[vi] = n_stone;
						if (y > stone_surface_max_y)
							stone_surface_max_y = y;
					} else if (y <= water_level) {
						vm->m_data[vi] = n_water;
					} else {
						vm->m_data[vi] = n_air;
					}
				}
			}
			index2d -= ystride;
		}
		index2d += ystride;
	}

	return stone_surface_max_y;
}


code:
/*
Minetest
Copyright (C) 2015-2017 paramat
Copyright (C) 2015-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

Fractal formulas from http://www.bugman123.com/Hypercomplex/index.html
by Paul Nylander, and from http://www.fractalforums.com, thank you.

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.
*/

#ifndef MAPGEN_FRACTAL_HEADER
#define MAPGEN_FRACTAL_HEADER

#include "mapgen.h"

#define MGFRACTAL_LARGE_CAVE_DEPTH -33

class BiomeManager;

extern FlagDesc flagdesc_mapgen_fractal[];

struct MapgenFractalParams : public MapgenParams
{
	u32 spflags;
	float cave_width;
	u16 fractal;
	u16 iterations;
	v3f scale;
	v3f offset;
	float slice_w;
	float julia_x;
	float julia_y;
	float julia_z;
	float julia_w;
	NoiseParams np_seabed;
	NoiseParams np_filler_depth;
	NoiseParams np_cave1;
	NoiseParams np_cave2;

	MapgenFractalParams();
	~MapgenFractalParams() {}

	void readParams(const Settings *settings);
	void writeParams(Settings *settings) const;
};

class MapgenFractal : public MapgenBasic
{
public:
	MapgenFractal(int mapgenid, MapgenFractalParams *params, EmergeManager *emerge);
	~MapgenFractal();

	virtual MapgenType getType() const { return MAPGEN_FRACTAL; }

	virtual void makeChunk(BlockMakeData *data);
	int getSpawnLevelAtPoint(v2s16 p);
	bool getFractalAtPoint(s16 x, s16 y, s16 z);
	s16 generateTerrain();

private:
	u16 formula;
	bool julia;

	u16 fractal;
	u16 iterations;
	v3f scale;
	v3f offset;
	float slice_w;
	float julia_x;
	float julia_y;
	float julia_z;
	float julia_w;
	Noise *noise_seabed;
};

#endif


code:
/*
Minetest
Copyright (C) 2013-2015 celeron55, Perttu Ahola <celeron55@gmail.com>
Copyright (C) 2013-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
Copyright (C) 2015-2017 paramat

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 "mapgen_singlenode.h"
#include "voxel.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "nodedef.h"
#include "voxelalgorithms.h"
#include "emerge.h"

MapgenSinglenode::MapgenSinglenode(int mapgenid,
	MapgenParams *params, EmergeManager *emerge)
	: Mapgen(mapgenid, params, emerge)
{
	flags = params->flags;

	INodeDefManager *ndef = emerge->ndef;

	c_node = ndef->getId("mapgen_singlenode");
	if (c_node == CONTENT_IGNORE)
		c_node = CONTENT_AIR;

	MapNode n_node(c_node);
	set_light = (ndef->get(n_node).sunlight_propagates) ? LIGHT_SUN : 0x00;
}

MapgenSinglenode::~MapgenSinglenode()
{
}

//////////////////////// Map generator

void MapgenSinglenode::makeChunk(BlockMakeData *data)
{
	// Pre-conditions
	assert(data->vmanip);
	assert(data->nodedef);
	assert(data->blockpos_requested.X >= data->blockpos_min.X &&
		data->blockpos_requested.Y >= data->blockpos_min.Y &&
		data->blockpos_requested.Z >= data->blockpos_min.Z);
	assert(data->blockpos_requested.X <= data->blockpos_max.X &&
		data->blockpos_requested.Y <= data->blockpos_max.Y &&
		data->blockpos_requested.Z <= data->blockpos_max.Z);

	this->generating = true;
	this->vm   = data->vmanip;
	this->ndef = data->nodedef;

	v3s16 blockpos_min = data->blockpos_min;
	v3s16 blockpos_max = data->blockpos_max;

	// Area of central chunk
	v3s16 node_min = blockpos_min * MAP_BLOCKSIZE;
	v3s16 node_max = (blockpos_max + v3s16(1, 1, 1)) * MAP_BLOCKSIZE - v3s16(1, 1, 1);

	blockseed = getBlockSeed2(node_min, data->seed);

	MapNode n_node(c_node);

	for (s16 z = node_min.Z; z <= node_max.Z; z++)
	for (s16 y = node_min.Y; y <= node_max.Y; y++) {
		u32 i = vm->m_area.index(node_min.X, y, z);
		for (s16 x = node_min.X; x <= node_max.X; x++) {
			if (vm->m_data[i].getContent() == CONTENT_IGNORE)
				vm->m_data[i] = n_node;
			i++;
		}
	}

	// Add top and bottom side of water to transforming_liquid queue
	updateLiquid(&data->transforming_liquid, node_min, node_max);

	// Set lighting
	if ((flags & MG_LIGHT) && set_light == LIGHT_SUN)
		setLighting(LIGHT_SUN, node_min, node_max);

	this->generating = false;
}

int MapgenSinglenode::getSpawnLevelAtPoint(v2s16 p)
{
	return 0;
}


code:
/*
Minetest
Copyright (C) 2013-2015 celeron55, Perttu Ahola <celeron55@gmail.com>
Copyright (C) 2013-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
Copyright (C) 2015-2017 paramat

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.
*/

#ifndef MAPGEN_SINGLENODE_HEADER
#define MAPGEN_SINGLENODE_HEADER

#include "mapgen.h"

struct MapgenSinglenodeParams : public MapgenParams
{
	MapgenSinglenodeParams() {}
	~MapgenSinglenodeParams() {}

	void readParams(const Settings *settings) {}
	void writeParams(Settings *settings) const {}
};

class MapgenSinglenode : public Mapgen
{
public:
	u32 flags;
	content_t c_node;
	u8 set_light;

	MapgenSinglenode(int mapgenid, MapgenParams *params, EmergeManager *emerge);
	~MapgenSinglenode();

	virtual MapgenType getType() const { return MAPGEN_SINGLENODE; }

	void makeChunk(BlockMakeData *data);
	int getSpawnLevelAtPoint(v2s16 p);
};

#endif


code:
/*
Minetest
Copyright (C) 2014-2017 paramat
Copyright (C) 2014-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

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 "mapgen.h"
#include "voxel.h"
#include "noise.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "content_sao.h"
#include "nodedef.h"
#include "voxelalgorithms.h"
//#include "profiler.h" // For TimeTaker
#include "settings.h" // For g_settings
#include "emerge.h"
#include "dungeongen.h"
#include "cavegen.h"
#include "mg_biome.h"
#include "mg_ore.h"
#include "mg_decoration.h"
#include "mapgen_v5.h"

FlagDesc flagdesc_mapgen_v5[] = {
	{"caverns", MGV5_CAVERNS},
	{NULL,      0}
};

MapgenV5::MapgenV5(int mapgenid, MapgenV5Params *params, EmergeManager *emerge)
	: MapgenBasic(mapgenid, params, emerge)
{
	this->spflags          = params->spflags;
	this->cave_width       = params->cave_width;
	this->cavern_limit     = params->cavern_limit;
	this->cavern_taper     = params->cavern_taper;
	this->cavern_threshold = params->cavern_threshold;

	// Terrain noise
	noise_filler_depth = new Noise(&params->np_filler_depth, seed, csize.X, csize.Z);
	noise_factor       = new Noise(&params->np_factor,       seed, csize.X, csize.Z);
	noise_height       = new Noise(&params->np_height,       seed, csize.X, csize.Z);

	// 3D terrain noise
	// 1-up 1-down overgeneration
	noise_ground = new Noise(&params->np_ground, seed, csize.X, csize.Y + 2, csize.Z);
	// 1 down overgeneration
	MapgenBasic::np_cave1  = params->np_cave1;
	MapgenBasic::np_cave2  = params->np_cave2;
	MapgenBasic::np_cavern = params->np_cavern;
}

MapgenV5::~MapgenV5()
{
	delete noise_filler_depth;
	delete noise_factor;
	delete noise_height;
	delete noise_ground;
}

MapgenV5Params::MapgenV5Params()
{
	spflags          = MGV5_CAVERNS;
	cave_width       = 0.125;
	cavern_limit     = -256;
	cavern_taper     = 256;
	cavern_threshold = 0.7;

	np_filler_depth = NoiseParams(0, 1,  v3f(150, 150, 150), 261,    4, 0.7,  2.0);
	np_factor       = NoiseParams(0, 1,  v3f(250, 250, 250), 920381, 3, 0.45, 2.0);
	np_height       = NoiseParams(0, 10, v3f(250, 250, 250), 84174,  4, 0.5,  2.0);
	np_ground       = NoiseParams(0, 40, v3f(80,  80,  80),  983240, 4, 0.55, 2.0, NOISE_FLAG_EASED);
	np_cave1        = NoiseParams(0, 12, v3f(50,  50,  50),  52534,  4, 0.5,  2.0);
	np_cave2        = NoiseParams(0, 12, v3f(50,  50,  50),  10325,  4, 0.5,  2.0);
	np_cavern       = NoiseParams(0, 1,  v3f(384, 128, 384), 723,    5, 0.63, 2.0);
}

void MapgenV5Params::readParams(const Settings *settings)
{
	settings->getFlagStrNoEx("mgv5_spflags",        spflags, flagdesc_mapgen_v5);
	settings->getFloatNoEx("mgv5_cave_width",       cave_width);
	settings->getS16NoEx("mgv5_cavern_limit",       cavern_limit);
	settings->getS16NoEx("mgv5_cavern_taper",       cavern_taper);
	settings->getFloatNoEx("mgv5_cavern_threshold", cavern_threshold);

	settings->getNoiseParams("mgv5_np_filler_depth", np_filler_depth);
	settings->getNoiseParams("mgv5_np_factor",       np_factor);
	settings->getNoiseParams("mgv5_np_height",       np_height);
	settings->getNoiseParams("mgv5_np_ground",       np_ground);
	settings->getNoiseParams("mgv5_np_cave1",        np_cave1);
	settings->getNoiseParams("mgv5_np_cave2",        np_cave2);
	settings->getNoiseParams("mgv5_np_cavern",       np_cavern);
}

void MapgenV5Params::writeParams(Settings *settings) const
{
	settings->setFlagStr("mgv5_spflags",        spflags, flagdesc_mapgen_v5, U32_MAX);
	settings->setFloat("mgv5_cave_width",       cave_width);
	settings->setS16("mgv5_cavern_limit",       cavern_limit);
	settings->setS16("mgv5_cavern_taper",       cavern_taper);
	settings->setFloat("mgv5_cavern_threshold", cavern_threshold);

	settings->setNoiseParams("mgv5_np_filler_depth", np_filler_depth);
	settings->setNoiseParams("mgv5_np_factor",       np_factor);
	settings->setNoiseParams("mgv5_np_height",       np_height);
	settings->setNoiseParams("mgv5_np_ground",       np_ground);
	settings->setNoiseParams("mgv5_np_cave1",        np_cave1);
	settings->setNoiseParams("mgv5_np_cave2",        np_cave2);
	settings->setNoiseParams("mgv5_np_cavern",       np_cavern);
}

int MapgenV5::getSpawnLevelAtPoint(v2s16 p)
{
	//TimeTaker t("getGroundLevelAtPoint", NULL, PRECISION_MICRO);

	float f = 0.55 + NoisePerlin2D(&noise_factor->np, p.X, p.Y, seed);
	if (f < 0.01)
		f = 0.01;
	else if (f >= 1.0)
		f *= 1.6;
	float h = NoisePerlin2D(&noise_height->np, p.X, p.Y, seed);

	for (s16 y = 128; y >= -128; y--) {
		float n_ground = NoisePerlin3D(&noise_ground->np, p.X, y, p.Y, seed);

		if (n_ground * f > y - h) {  // If solid
			// If either top 2 nodes of search are solid this is inside a
			// mountain or floatland with possibly no space for the player to spawn.
			if (y >= 127) {
				return MAX_MAP_GENERATION_LIMIT;  // Unsuitable spawn point
			} else {  // Ground below at least 2 nodes of empty space
				if (y <= water_level || y > water_level + 16)
					return MAX_MAP_GENERATION_LIMIT;  // Unsuitable spawn point
				else
					return y;
			}
		}
	}

	//printf("getGroundLevelAtPoint: %dus\n", t.stop());
	return MAX_MAP_GENERATION_LIMIT;  // Unsuitable spawn position, no ground found
}

void MapgenV5::makeChunk(BlockMakeData *data)
{
	// Pre-conditions
	assert(data->vmanip);
	assert(data->nodedef);
	assert(data->blockpos_requested.X >= data->blockpos_min.X &&
		data->blockpos_requested.Y >= data->blockpos_min.Y &&
		data->blockpos_requested.Z >= data->blockpos_min.Z);
	assert(data->blockpos_requested.X <= data->blockpos_max.X &&
		data->blockpos_requested.Y <= data->blockpos_max.Y &&
		data->blockpos_requested.Z <= data->blockpos_max.Z);

	this->generating = true;
	this->vm   = data->vmanip;
	this->ndef = data->nodedef;
	//TimeTaker t("makeChunk");

	v3s16 blockpos_min = data->blockpos_min;
	v3s16 blockpos_max = data->blockpos_max;
	node_min = blockpos_min * MAP_BLOCKSIZE;
	node_max = (blockpos_max + v3s16(1, 1, 1)) * MAP_BLOCKSIZE - v3s16(1, 1, 1);
	full_node_min = (blockpos_min - 1) * MAP_BLOCKSIZE;
	full_node_max = (blockpos_max + 2) * MAP_BLOCKSIZE - v3s16(1, 1, 1);

	// Create a block-specific seed
	blockseed = getBlockSeed2(full_node_min, seed);

	// Generate base terrain
	s16 stone_surface_max_y = generateBaseTerrain();

	// Create heightmap
	updateHeightmap(node_min, node_max);

	// Init biome generator, place biome-specific nodes, and build biomemap
	biomegen->calcBiomeNoise(node_min);
	MgStoneType stone_type = generateBiomes();

	// Generate caverns, tunnels and classic caves
	if (flags & MG_CAVES) {
		bool near_cavern = false;
		// Generate caverns
		if (spflags & MGV5_CAVERNS)
			near_cavern = generateCaverns(stone_surface_max_y);
		// Generate tunnels and classic caves
		if (near_cavern)
			// Disable classic caves in this mapchunk by setting
			// 'large cave depth' to world base. Avoids excessive liquid in
			// large caverns and floating blobs of overgenerated liquid.
			generateCaves(stone_surface_max_y, -MAX_MAP_GENERATION_LIMIT);
		else
			generateCaves(stone_surface_max_y, MGV5_LARGE_CAVE_DEPTH);
	}

	// Generate dungeons and desert temples
	if (flags & MG_DUNGEONS)
		generateDungeons(stone_surface_max_y, stone_type);

	// Generate the registered decorations
	if (flags & MG_DECORATIONS)
		m_emerge->decomgr->placeAllDecos(this, blockseed, node_min, node_max);

	// Generate the registered ores
	m_emerge->oremgr->placeAllOres(this, blockseed, node_min, node_max);

	// Sprinkle some dust on top after everything else was generated
	dustTopNodes();

	//printf("makeChunk: %dms\n", t.stop());

	// Add top and bottom side of water to transforming_liquid queue
	updateLiquid(&data->transforming_liquid, full_node_min, full_node_max);

	// Calculate lighting
	if (flags & MG_LIGHT) {
		calcLighting(node_min - v3s16(0, 1, 0), node_max + v3s16(0, 1, 0),
			full_node_min, full_node_max);
	}

	this->generating = false;
}

int MapgenV5::generateBaseTerrain()
{
	u32 index = 0;
	u32 index2d = 0;
	int stone_surface_max_y = -MAX_MAP_GENERATION_LIMIT;

	noise_factor->perlinMap2D(node_min.X, node_min.Z);
	noise_height->perlinMap2D(node_min.X, node_min.Z);
	noise_ground->perlinMap3D(node_min.X, node_min.Y - 1, node_min.Z);

	for (s16 z=node_min.Z; z<=node_max.Z; z++) {
		for (s16 y=node_min.Y - 1; y<=node_max.Y + 1; y++) {
			u32 vi = vm->m_area.index(node_min.X, y, z);
			for (s16 x=node_min.X; x<=node_max.X; x++, vi++, index++, index2d++) {
				if (vm->m_data[vi].getContent() != CONTENT_IGNORE)
					continue;

				float f = 0.55 + noise_factor->result[index2d];
				if (f < 0.01)
					f = 0.01;
				else if (f >= 1.0)
					f *= 1.6;
				float h = noise_height->result[index2d];

				if (noise_ground->result[index] * f < y - h) {
					if (y <= water_level)
						vm->m_data[vi] = MapNode(c_water_source);
					else
						vm->m_data[vi] = MapNode(CONTENT_AIR);
				} else {
					vm->m_data[vi] = MapNode(c_stone);
					if (y > stone_surface_max_y)
						stone_surface_max_y = y;
				}
			}
			index2d -= ystride;
		}
		index2d += ystride;
	}

	return stone_surface_max_y;
}


code:
/*
Minetest
Copyright (C) 2014-2017 paramat
Copyright (C) 2014-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

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.
*/

#ifndef MAPGEN_V5_HEADER
#define MAPGEN_V5_HEADER

#include "mapgen.h"

#define MGV5_LARGE_CAVE_DEPTH -256

///////// Mapgen V5 flags
#define MGV5_CAVERNS 0x01

class BiomeManager;

extern FlagDesc flagdesc_mapgen_v5[];

struct MapgenV5Params : public MapgenParams
{
	u32 spflags;
	float cave_width;
	s16 cavern_limit;
	s16 cavern_taper;
	float cavern_threshold;

	NoiseParams np_filler_depth;
	NoiseParams np_factor;
	NoiseParams np_height;
	NoiseParams np_ground;
	NoiseParams np_cave1;
	NoiseParams np_cave2;
	NoiseParams np_cavern;

	MapgenV5Params();
	~MapgenV5Params() {}

	void readParams(const Settings *settings);
	void writeParams(Settings *settings) const;
};

class MapgenV5 : public MapgenBasic
{
public:
	MapgenV5(int mapgenid, MapgenV5Params *params, EmergeManager *emerge);
	~MapgenV5();

	virtual MapgenType getType() const { return MAPGEN_V5; }

	virtual void makeChunk(BlockMakeData *data);
	int getSpawnLevelAtPoint(v2s16 p);
	int generateBaseTerrain();

private:
	Noise *noise_factor;
	Noise *noise_height;
	Noise *noise_ground;
};

#endif