code:
/*
Minetest
Copyright (C) 2014-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 "mg_decoration.h"
#include "mg_schematic.h"
#include "mapgen.h"
#include "noise.h"
#include "map.h"
#include "log.h"
#include "util/numeric.h"
#include <algorithm>

FlagDesc flagdesc_deco[] = {
	{"place_center_x",  DECO_PLACE_CENTER_X},
	{"place_center_y",  DECO_PLACE_CENTER_Y},
	{"place_center_z",  DECO_PLACE_CENTER_Z},
	{"force_placement", DECO_FORCE_PLACEMENT},
	{"liquid_surface",  DECO_LIQUID_SURFACE},
	{NULL,              0}
};

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

DecorationManager::DecorationManager(IGameDef *gamedef) :
	ObjDefManager(gamedef, OBJDEF_DECORATION)
{
}

size_t DecorationManager::placeAllDecos(Mapgen *mg, u32 blockseed,
	v3s16 nmin, v3s16 nmax)
{
	size_t nplaced = 0;

	for (size_t i = 0; i != m_objects.size(); i++) {
		Decoration *deco = (Decoration *)m_objects[i];
		if (!deco)
			continue;

		nplaced += deco->placeDeco(mg, blockseed, nmin, nmax);
		blockseed++;
	}

	return nplaced;
}

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

Decoration::Decoration()
{
	mapseed    = 0;
	fill_ratio = 0;
	sidelen    = 1;
	flags      = 0;
}

Decoration::~Decoration()
{
}

void Decoration::resolveNodeNames()
{
	getIdsFromNrBacklog(&c_place_on);
	getIdsFromNrBacklog(&c_spawnby);
}

bool Decoration::canPlaceDecoration(MMVManip *vm, v3s16 p)
{
	// Check if the decoration can be placed on this node
	u32 vi = vm->m_area.index(p);
	if (!CONTAINS(c_place_on, vm->m_data[vi].getContent()))
		return false;

	// Don't continue if there are no spawnby constraints
	if (nspawnby == -1)
		return true;

	int nneighs = 0;
	static const v3s16 dirs[16] = {
		v3s16( 0, 0,  1),
		v3s16( 0, 0, -1),
		v3s16( 1, 0,  0),
		v3s16(-1, 0,  0),
		v3s16( 1, 0,  1),
		v3s16(-1, 0,  1),
		v3s16(-1, 0, -1),
		v3s16( 1, 0, -1),

		v3s16( 0, 1,  1),
		v3s16( 0, 1, -1),
		v3s16( 1, 1,  0),
		v3s16(-1, 1,  0),
		v3s16( 1, 1,  1),
		v3s16(-1, 1,  1),
		v3s16(-1, 1, -1),
		v3s16( 1, 1, -1)
	};

	// Check these 16 neighbouring nodes for enough spawnby nodes
	for (size_t i = 0; i != ARRLEN(dirs); i++) {
		u32 index = vm->m_area.index(p + dirs[i]);
		if (!vm->m_area.contains(index))
			continue;

		if (CONTAINS(c_spawnby, vm->m_data[index].getContent()))
			nneighs++;
	}

	if (nneighs < nspawnby)
		return false;

	return true;
}

size_t Decoration::placeDeco(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax)
{
	PcgRandom ps(blockseed + 53);
	int carea_size = nmax.X - nmin.X + 1;

	// Divide area into parts
	// If chunksize is changed it may no longer be divisable by sidelen
	if (carea_size % sidelen)
		sidelen = carea_size;

	s16 divlen = carea_size / sidelen;
	int area = sidelen * sidelen;

	for (s16 z0 = 0; z0 < divlen; z0++)
	for (s16 x0 = 0; x0 < divlen; x0++) {
		v2s16 p2d_center( // Center position of part of division
			nmin.X + sidelen / 2 + sidelen * x0,
			nmin.Z + sidelen / 2 + sidelen * z0
		);
		v2s16 p2d_min( // Minimum edge of part of division
			nmin.X + sidelen * x0,
			nmin.Z + sidelen * z0
		);
		v2s16 p2d_max( // Maximum edge of part of division
			nmin.X + sidelen + sidelen * x0 - 1,
			nmin.Z + sidelen + sidelen * z0 - 1
		);

		// Amount of decorations
		float nval = (flags & DECO_USE_NOISE) ?
			NoisePerlin2D(&np, p2d_center.X, p2d_center.Y, mapseed) :
			fill_ratio;
		u32 deco_count = 0;
		float deco_count_f = (float)area * nval;
		if (deco_count_f >= 1.f) {
			deco_count = deco_count_f;
		} else if (deco_count_f > 0.f) {
			// For low density decorations calculate a chance for 1 decoration
			if (ps.range(1000) <= deco_count_f * 1000.f)
				deco_count = 1;
		}

		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 < nmin.Y || y > nmax.Y ||
				y < y_min  || y > y_max)
				continue;

			if (y + getHeight() > mg->vm->m_area.MaxEdge.Y) {
				continue;
#if 0
				printf("Decoration at (%d %d %d) cut off\n", x, y, z);
				//add to queue
				MutexAutoLock cutofflock(cutoff_mutex);
				cutoffs.push_back(CutoffData(x, y, z, height));
#endif
			}

			if (mg->biomemap) {
				UNORDERED_SET<u8>::iterator iter;

				if (!biomes.empty()) {
					iter = biomes.find(mg->biomemap[mapindex]);
					if (iter == biomes.end())
						continue;
				}
			}

			v3s16 pos(x, y, z);
			if (generate(mg->vm, &ps, pos))
				mg->gennotify.addEvent(GENNOTIFY_DECORATION, pos, index);
		}
	}

	return 0;
}

#if 0
void Decoration::placeCutoffs(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax)
{
	PcgRandom pr(blockseed + 53);
	std::vector<CutoffData> handled_cutoffs;

	// Copy over the cutoffs we're interested in so we don't needlessly hold a lock
	{
		MutexAutoLock cutofflock(cutoff_mutex);
		for (std::list<CutoffData>::iterator i = cutoffs.begin();
			i != cutoffs.end(); ++i) {
			CutoffData cutoff = *i;
			v3s16 p    = cutoff.p;
			s16 height = cutoff.height;
			if (p.X < nmin.X || p.X > nmax.X ||
				p.Z < nmin.Z || p.Z > nmax.Z)
				continue;
			if (p.Y + height < nmin.Y || p.Y > nmax.Y)
				continue;

			handled_cutoffs.push_back(cutoff);
		}
	}

	// Generate the cutoffs
	for (size_t i = 0; i != handled_cutoffs.size(); i++) {
		v3s16 p    = handled_cutoffs[i].p;
		s16 height = handled_cutoffs[i].height;

		if (p.Y + height > nmax.Y) {
			//printf("Decoration at (%d %d %d) cut off again!\n", p.X, p.Y, p.Z);
			cuttoffs.push_back(v3s16(p.X, p.Y, p.Z));
		}

		generate(mg, &pr, nmax.Y, nmin.Y - p.Y, v3s16(p.X, nmin.Y, p.Z));
	}

	// Remove cutoffs that were handled from the cutoff list
	{
		MutexAutoLock cutofflock(cutoff_mutex);
		for (std::list<CutoffData>::iterator i = cutoffs.begin();
			i != cutoffs.end(); ++i) {

			for (size_t j = 0; j != handled_cutoffs.size(); j++) {
				CutoffData coff = *i;
				if (coff.p == handled_cutoffs[j].p)
					i = cutoffs.erase(i);
			}
		}
	}
}
#endif

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

void DecoSimple::resolveNodeNames()
{
	Decoration::resolveNodeNames();
	getIdsFromNrBacklog(&c_decos);
}

size_t DecoSimple::generate(MMVManip *vm, PcgRandom *pr, v3s16 p)
{
	// Don't bother if there aren't any decorations to place
	if (c_decos.size() == 0)
		return 0;

	if (!canPlaceDecoration(vm, p))
		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;

	bool force_placement = (flags & DECO_FORCE_PLACEMENT);

	v3s16 em = vm->m_area.getExtent();
	u32 vi = vm->m_area.index(p);
	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;

		vm->m_data[vi] = MapNode(c_place, 0, deco_param2);
	}

	return 1;
}

int DecoSimple::getHeight()
{
	return (deco_height_max > 0) ? deco_height_max : deco_height;
}

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

DecoSchematic::DecoSchematic()
{
	schematic = NULL;
}

size_t DecoSchematic::generate(MMVManip *vm, PcgRandom *pr, v3s16 p)
{
	// Schematic could have been unloaded but not the decoration
	// In this case generate() does nothing (but doesn't *fail*)
	if (schematic == NULL)
		return 0;

	if (!canPlaceDecoration(vm, p))
		return 0;

	if (flags & DECO_PLACE_CENTER_X)
		p.X -= (schematic->size.X - 1) / 2;
	if (flags & DECO_PLACE_CENTER_Y)
		p.Y -= (schematic->size.Y - 1) / 2;
	if (flags & DECO_PLACE_CENTER_Z)
		p.Z -= (schematic->size.Z - 1) / 2;

	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 placed
	// sunk 1 node into the ground.
	return (flags & DECO_PLACE_CENTER_Y) ?
		(schematic->size.Y - 1) / 2 : schematic->size.Y - 1;
}


code:
/*
Minetest
Copyright (C) 2014-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 MG_DECORATION_HEADER
#define MG_DECORATION_HEADER

#include "util/cpp11_container.h"
#include "objdef.h"
#include "noise.h"
#include "nodedef.h"

class Mapgen;
class MMVManip;
class PcgRandom;
class Schematic;

enum DecorationType {
	DECO_SIMPLE,
	DECO_SCHEMATIC,
	DECO_LSYSTEM
};

#define DECO_PLACE_CENTER_X  0x01
#define DECO_PLACE_CENTER_Y  0x02
#define DECO_PLACE_CENTER_Z  0x04
#define DECO_USE_NOISE       0x08
#define DECO_FORCE_PLACEMENT 0x10
#define DECO_LIQUID_SURFACE  0x20

extern FlagDesc flagdesc_deco[];

#if 0
struct CutoffData {
	VoxelArea a;
	Decoration *deco;
	//v3s16 p;
	//v3s16 size;
	//s16 height;

	CutoffData(s16 x, s16 y, s16 z, s16 h) {
		p = v3s16(x, y, z);
		height = h;
	}
};
#endif

class Decoration : public ObjDef, public NodeResolver {
public:
	Decoration();
	virtual ~Decoration();

	virtual void resolveNodeNames();

	bool canPlaceDecoration(MMVManip *vm, v3s16 p);
	size_t placeDeco(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);
	//size_t placeCutoffs(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);

	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p) = 0;
	virtual int getHeight() = 0;

	u32 flags;
	int mapseed;
	std::vector<content_t> c_place_on;
	s16 sidelen;
	s16 y_min;
	s16 y_max;
	float fill_ratio;
	NoiseParams np;
	std::vector<content_t> c_spawnby;
	s16 nspawnby;

	UNORDERED_SET<u8> biomes;
	//std::list<CutoffData> cutoffs;
	//Mutex cutoff_mutex;
};

class DecoSimple : public Decoration {
public:
	virtual void resolveNodeNames();
	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p);
	virtual int getHeight();

	std::vector<content_t> c_decos;
	s16 deco_height;
	s16 deco_height_max;
	u8 deco_param2;
};

class DecoSchematic : public Decoration {
public:
	DecoSchematic();

	virtual size_t generate(MMVManip *vm, PcgRandom *pr, v3s16 p);
	virtual int getHeight();

	Rotation rotation;
	Schematic *schematic;
};

/*
class DecoLSystem : public Decoration {
public:
	virtual void generate(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);
};
*/

class DecorationManager : public ObjDefManager {
public:
	DecorationManager(IGameDef *gamedef);
	virtual ~DecorationManager() {}

	const char *getObjectTitle() const
	{
		return "decoration";
	}

	static Decoration *create(DecorationType type)
	{
		switch (type) {
		case DECO_SIMPLE:
			return new DecoSimple;
		case DECO_SCHEMATIC:
			return new DecoSchematic;
		//case DECO_LSYSTEM:
		//	return new DecoLSystem;
		default:
			return NULL;
		}
	}

	size_t placeAllDecos(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);
};

#endif

repo_name: pgimeno/minetest

license: unknown


code:
/*
Minetest
Copyright (C) 2014-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 "mg_ore.h"
#include "mapgen.h"
#include "noise.h"
#include "map.h"
#include "log.h"
#include <algorithm>

FlagDesc flagdesc_ore[] = {
	{"absheight",                 OREFLAG_ABSHEIGHT},
	{"puff_cliffs",               OREFLAG_PUFF_CLIFFS},
	{"puff_additive_composition", OREFLAG_PUFF_ADDITIVE},
	{NULL,                        0}
};

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

OreManager::OreManager(IGameDef *gamedef) :
	ObjDefManager(gamedef, OBJDEF_ORE)
{
}

size_t OreManager::placeAllOres(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax)
{
	size_t nplaced = 0;

	for (size_t i = 0; i != m_objects.size(); i++) {
		Ore *ore = (Ore *)m_objects[i];
		if (!ore)
			continue;

		nplaced += ore->placeOre(mg, blockseed, nmin, nmax);
		blockseed++;
	}

	return nplaced;
}

void OreManager::clear()
{
	for (size_t i = 0; i < m_objects.size(); i++) {
		Ore *ore = (Ore *)m_objects[i];
		delete ore;
	}
	m_objects.clear();
}

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

Ore::Ore()
{
	flags = 0;
	noise = NULL;
}

Ore::~Ore()
{
	delete noise;
}

void Ore::resolveNodeNames()
{
	getIdFromNrBacklog(&c_ore, "", CONTENT_AIR);
	getIdsFromNrBacklog(&c_wherein);
}

size_t Ore::placeOre(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax)
{
	int in_range = 0;

	in_range |= (nmin.Y <= y_max && nmax.Y >= y_min);
	if (flags & OREFLAG_ABSHEIGHT)
		in_range |= (nmin.Y >= -y_max && nmax.Y <= -y_min) << 1;
	if (!in_range)
		return 0;

	int actual_ymin, actual_ymax;
	if (in_range & ORE_RANGE_MIRROR) {
		actual_ymin = MYMAX(nmin.Y, -y_max);
		actual_ymax = MYMIN(nmax.Y, -y_min);
	} else {
		actual_ymin = MYMAX(nmin.Y, y_min);
		actual_ymax = MYMIN(nmax.Y, y_max);
	}
	if (clust_size >= actual_ymax - actual_ymin + 1)
		return 0;

	nmin.Y = actual_ymin;
	nmax.Y = actual_ymax;
	generate(mg->vm, mg->seed, blockseed, nmin, nmax, mg->biomemap);

	return 1;
}

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

void OreScatter::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed);
	MapNode n_ore(c_ore, 0, ore_param2);

	u32 sizex  = (nmax.X - nmin.X + 1);
	u32 volume = (nmax.X - nmin.X + 1) *
				 (nmax.Y - nmin.Y + 1) *
				 (nmax.Z - nmin.Z + 1);
	u32 csize     = clust_size;
	u32 cvolume    = csize * csize * csize;
	u32 nclusters = volume / clust_scarcity;

	for (u32 i = 0; i != nclusters; i++) {
		int x0 = pr.range(nmin.X, nmax.X - csize + 1);
		int y0 = pr.range(nmin.Y, nmax.Y - csize + 1);
		int z0 = pr.range(nmin.Z, nmax.Z - csize + 1);

		if ((flags & OREFLAG_USE_NOISE) &&
			(NoisePerlin3D(&np, x0, y0, z0, mapseed) < nthresh))
			continue;

		if (biomemap && !biomes.empty()) {
			u32 index = sizex * (z0 - nmin.Z) + (x0 - nmin.X);
			UNORDERED_SET<u8>::iterator it = biomes.find(biomemap[index]);
			if (it == biomes.end())
				continue;
		}

		for (u32 z1 = 0; z1 != csize; z1++)
		for (u32 y1 = 0; y1 != csize; y1++)
		for (u32 x1 = 0; x1 != csize; x1++) {
			if (pr.range(1, cvolume) > clust_num_ores)
				continue;

			u32 i = vm->m_area.index(x0 + x1, y0 + y1, z0 + z1);
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

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

void OreSheet::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed + 4234);
	MapNode n_ore(c_ore, 0, ore_param2);

	u16 max_height = column_height_max;
	int y_start_min = nmin.Y + max_height;
	int y_start_max = nmax.Y - max_height;

	int y_start = y_start_min < y_start_max ?
		pr.range(y_start_min, y_start_max) :
		(y_start_min + y_start_max) / 2;

	if (!noise) {
		int sx = nmax.X - nmin.X + 1;
		int sz = nmax.Z - nmin.Z + 1;
		noise = new Noise(&np, 0, sx, sz);
	}
	noise->seed = mapseed + y_start;
	noise->perlinMap2D(nmin.X, nmin.Z);

	size_t index = 0;
	for (int z = nmin.Z; z <= nmax.Z; z++)
	for (int x = nmin.X; x <= nmax.X; x++, index++) {
		float noiseval = noise->result[index];
		if (noiseval < nthresh)
			continue;

		if (biomemap && !biomes.empty()) {
			UNORDERED_SET<u8>::iterator it = biomes.find(biomemap[index]);
			if (it == biomes.end())
				continue;
		}

		u16 height = pr.range(column_height_min, column_height_max);
		int ymidpoint = y_start + noiseval;
		int y0 = MYMAX(nmin.Y, ymidpoint - height * (1 - column_midpoint_factor));
		int y1 = MYMIN(nmax.Y, y0 + height - 1);

		for (int y = y0; y <= y1; y++) {
			u32 i = vm->m_area.index(x, y, z);
			if (!vm->m_area.contains(i))
				continue;
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

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

OrePuff::OrePuff() :
	Ore()
{
	noise_puff_top    = NULL;
	noise_puff_bottom = NULL;
}

OrePuff::~OrePuff()
{
	delete noise_puff_top;
	delete noise_puff_bottom;
}

void OrePuff::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed + 4234);
	MapNode n_ore(c_ore, 0, ore_param2);

	int y_start = pr.range(nmin.Y, nmax.Y);

	if (!noise) {
		int sx = nmax.X - nmin.X + 1;
		int sz = nmax.Z - nmin.Z + 1;
		noise = new Noise(&np, 0, sx, sz);
		noise_puff_top = new Noise(&np_puff_top, 0, sx, sz);
		noise_puff_bottom = new Noise(&np_puff_bottom, 0, sx, sz);
	}

	noise->seed = mapseed + y_start;
	noise->perlinMap2D(nmin.X, nmin.Z);
	bool noise_generated = false;

	size_t index = 0;
	for (int z = nmin.Z; z <= nmax.Z; z++)
	for (int x = nmin.X; x <= nmax.X; x++, index++) {
		float noiseval = noise->result[index];
		if (noiseval < nthresh)
			continue;

		if (biomemap && !biomes.empty()) {
			UNORDERED_SET<u8>::iterator it = biomes.find(biomemap[index]);
			if (it == biomes.end())
				continue;
		}

		if (!noise_generated) {
			noise_generated = true;
			noise_puff_top->perlinMap2D(nmin.X, nmin.Z);
			noise_puff_bottom->perlinMap2D(nmin.X, nmin.Z);
		}

		float ntop    = noise_puff_top->result[index];
		float nbottom = noise_puff_bottom->result[index];

		if (!(flags & OREFLAG_PUFF_CLIFFS)) {
			float ndiff = noiseval - nthresh;
			if (ndiff < 1.0f) {
				ntop *= ndiff;
				nbottom *= ndiff;
			}
		}

		int ymid = y_start;
		int y0 = ymid - nbottom;
		int y1 = ymid + ntop;

		if ((flags & OREFLAG_PUFF_ADDITIVE) && (y0 > y1))
			SWAP(int, y0, y1);

		for (int y = y0; y <= y1; y++) {
			u32 i = vm->m_area.index(x, y, z);
			if (!vm->m_area.contains(i))
				continue;
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

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

void OreBlob::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed + 2404);
	MapNode n_ore(c_ore, 0, ore_param2);

	u32 sizex  = (nmax.X - nmin.X + 1);
	u32 volume = (nmax.X - nmin.X + 1) *
				 (nmax.Y - nmin.Y + 1) *
				 (nmax.Z - nmin.Z + 1);
	u32 csize  = clust_size;
	u32 nblobs = volume / clust_scarcity;

	if (!noise)
		noise = new Noise(&np, mapseed, csize, csize, csize);

	for (u32 i = 0; i != nblobs; i++) {
		int x0 = pr.range(nmin.X, nmax.X - csize + 1);
		int y0 = pr.range(nmin.Y, nmax.Y - csize + 1);
		int z0 = pr.range(nmin.Z, nmax.Z - csize + 1);

		if (biomemap && !biomes.empty()) {
			u32 bmapidx = sizex * (z0 - nmin.Z) + (x0 - nmin.X);
			UNORDERED_SET<u8>::iterator it = biomes.find(biomemap[bmapidx]);
			if (it == biomes.end())
				continue;
		}

		bool noise_generated = false;
		noise->seed = blockseed + i;

		size_t index = 0;
		for (u32 z1 = 0; z1 != csize; z1++)
		for (u32 y1 = 0; y1 != csize; y1++)
		for (u32 x1 = 0; x1 != csize; x1++, index++) {
			u32 i = vm->m_area.index(x0 + x1, y0 + y1, z0 + z1);
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			// Lazily generate noise only if there's a chance of ore being placed
			// This simple optimization makes calls 6x faster on average
			if (!noise_generated) {
				noise_generated = true;
				noise->perlinMap3D(x0, y0, z0);
			}

			float noiseval = noise->result[index];

			float xdist = (s32)x1 - (s32)csize / 2;
			float ydist = (s32)y1 - (s32)csize / 2;
			float zdist = (s32)z1 - (s32)csize / 2;

			noiseval -= (sqrt(xdist * xdist + ydist * ydist + zdist * zdist) / csize);

			if (noiseval < nthresh)
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

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

OreVein::OreVein() :
	Ore()
{
	noise2 = NULL;
}

OreVein::~OreVein()
{
	delete noise2;
}

void OreVein::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed + 520);
	MapNode n_ore(c_ore, 0, ore_param2);

	u32 sizex = (nmax.X - nmin.X + 1);

	if (!noise) {
		int sx = nmax.X - nmin.X + 1;
		int sy = nmax.Y - nmin.Y + 1;
		int sz = nmax.Z - nmin.Z + 1;
		noise  = new Noise(&np, mapseed, sx, sy, sz);
		noise2 = new Noise(&np, mapseed + 436, sx, sy, sz);
	}
	bool noise_generated = false;

	size_t index = 0;
	for (int z = nmin.Z; z <= nmax.Z; z++)
	for (int y = nmin.Y; y <= nmax.Y; y++)
	for (int x = nmin.X; x <= nmax.X; x++, index++) {
		u32 i = vm->m_area.index(x, y, z);
		if (!vm->m_area.contains(i))
			continue;
		if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
			continue;

		if (biomemap && !biomes.empty()) {
			u32 bmapidx = sizex * (z - nmin.Z) + (x - nmin.X);
			UNORDERED_SET<u8>::iterator it = biomes.find(biomemap[bmapidx]);
			if (it == biomes.end())
				continue;
		}

		// Same lazy generation optimization as in OreBlob
		if (!noise_generated) {
			noise_generated = true;
			noise->perlinMap3D(nmin.X, nmin.Y, nmin.Z);
			noise2->perlinMap3D(nmin.X, nmin.Y, nmin.Z);
		}

		// randval ranges from -1..1
		float randval   = (float)pr.next() / (pr.RANDOM_RANGE / 2) - 1.f;
		float noiseval  = contour(noise->result[index]);
		float noiseval2 = contour(noise2->result[index]);
		if (noiseval * noiseval2 + randval * random_factor < nthresh)
			continue;

		vm->m_data[i] = n_ore;
	}
}


code:
/*
Minetest
Copyright (C) 2014-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 MG_ORE_HEADER
#define MG_ORE_HEADER

#include "util/cpp11_container.h"
#include "objdef.h"
#include "noise.h"
#include "nodedef.h"

class Noise;
class Mapgen;
class MMVManip;

/////////////////// Ore generation flags

#define OREFLAG_ABSHEIGHT     0x01
#define OREFLAG_PUFF_CLIFFS   0x02
#define OREFLAG_PUFF_ADDITIVE 0x04
#define OREFLAG_USE_NOISE     0x08

#define ORE_RANGE_ACTUAL 1
#define ORE_RANGE_MIRROR 2

enum OreType {
	ORE_SCATTER,
	ORE_SHEET,
	ORE_PUFF,
	ORE_BLOB,
	ORE_VEIN,
};

extern FlagDesc flagdesc_ore[];

class Ore : public ObjDef, public NodeResolver {
public:
	static const bool NEEDS_NOISE = false;

	content_t c_ore;                  // the node to place
	std::vector<content_t> c_wherein; // the nodes to be placed in
	u32 clust_scarcity; // ore cluster has a 1-in-clust_scarcity chance of appearing at a node
	s16 clust_num_ores; // how many ore nodes are in a chunk
	s16 clust_size;     // how large (in nodes) a chunk of ore is
	s16 y_min;
	s16 y_max;
	u8 ore_param2;		// to set node-specific attributes
	u32 flags;          // attributes for this ore
	float nthresh;      // threshold for noise at which an ore is placed
	NoiseParams np;     // noise for distribution of clusters (NULL for uniform scattering)
	Noise *noise;
	UNORDERED_SET<u8> biomes;

	Ore();
	virtual ~Ore();

	virtual void resolveNodeNames();

	size_t placeOre(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);
	virtual void generate(MMVManip *vm, int mapseed, u32 blockseed,
		v3s16 nmin, v3s16 nmax, u8 *biomemap) = 0;
};

class OreScatter : public Ore {
public:
	static const bool NEEDS_NOISE = false;

	virtual void generate(MMVManip *vm, int mapseed, u32 blockseed,
		v3s16 nmin, v3s16 nmax, u8 *biomemap);
};

class OreSheet : public Ore {
public:
	static const bool NEEDS_NOISE = true;

	u16 column_height_min;
	u16 column_height_max;
	float column_midpoint_factor;

	virtual void generate(MMVManip *vm, int mapseed, u32 blockseed,
		v3s16 nmin, v3s16 nmax, u8 *biomemap);
};

class OrePuff : public Ore {
public:
	static const bool NEEDS_NOISE = true;

	NoiseParams np_puff_top;
	NoiseParams np_puff_bottom;
	Noise *noise_puff_top;
	Noise *noise_puff_bottom;

	OrePuff();
	virtual ~OrePuff();

	virtual void generate(MMVManip *vm, int mapseed, u32 blockseed,
		v3s16 nmin, v3s16 nmax, u8 *biomemap);
};

class OreBlob : public Ore {
public:
	static const bool NEEDS_NOISE = true;

	virtual void generate(MMVManip *vm, int mapseed, u32 blockseed,
		v3s16 nmin, v3s16 nmax, u8 *biomemap);
};

class OreVein : public Ore {
public:
	static const bool NEEDS_NOISE = true;

	float random_factor;
	Noise *noise2;

	OreVein();
	virtual ~OreVein();

	virtual void generate(MMVManip *vm, int mapseed, u32 blockseed,
		v3s16 nmin, v3s16 nmax, u8 *biomemap);
};

class OreManager : public ObjDefManager {
public:
	OreManager(IGameDef *gamedef);
	virtual ~OreManager() {}

	const char *getObjectTitle() const
	{
		return "ore";
	}

	static Ore *create(OreType type)
	{
		switch (type) {
		case ORE_SCATTER:
			return new OreScatter;
		case ORE_SHEET:
			return new OreSheet;
		case ORE_PUFF:
			return new OrePuff;
		case ORE_BLOB:
			return new OreBlob;
		case ORE_VEIN:
			return new OreVein;
		default:
			return NULL;
		}
	}

	void clear();

	size_t placeAllOres(Mapgen *mg, u32 blockseed, v3s16 nmin, v3s16 nmax);
};

#endif


code:
/*
Minetest
Copyright (C) 2014-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 <fstream>
#include <typeinfo>
#include "mg_schematic.h"
#include "server.h"
#include "mapgen.h"
#include "emerge.h"
#include "map.h"
#include "mapblock.h"
#include "log.h"
#include "util/numeric.h"
#include "util/serialize.h"
#include "serialization.h"
#include "filesys.h"
#include "voxelalgorithms.h"

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

SchematicManager::SchematicManager(Server *server) :
	ObjDefManager(server, OBJDEF_SCHEMATIC)
{
	m_server = server;
}

void SchematicManager::clear()
{
	EmergeManager *emerge = m_server->getEmergeManager();

	// Remove all dangling references in Decorations
	DecorationManager *decomgr = emerge->decomgr;
	for (size_t i = 0; i != decomgr->getNumObjects(); i++) {
		Decoration *deco = (Decoration *)decomgr->getRaw(i);

		try {
			DecoSchematic *dschem = dynamic_cast<DecoSchematic *>(deco);
			if (dschem)
				dschem->schematic = NULL;
		} catch (std::bad_cast) {
		}
	}

	ObjDefManager::clear();
}

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

Schematic::Schematic()
{
	schemdata   = NULL;
	slice_probs = NULL;
	flags       = 0;
	size        = v3s16(0, 0, 0);
}

Schematic::~Schematic()
{
	delete []schemdata;
	delete []slice_probs;
}

void Schematic::resolveNodeNames()
{
	getIdsFromNrBacklog(&c_nodes, true, CONTENT_AIR);

	size_t bufsize = size.X * size.Y * size.Z;
	for (size_t i = 0; i != bufsize; i++) {
		content_t c_original = schemdata[i].getContent();
		content_t c_new = c_nodes[c_original];
		schemdata[i].setContent(c_new);
	}
}

void Schematic::blitToVManip(MMVManip *vm, v3s16 p, Rotation rot, bool force_place)
{
	sanity_check(m_ndef != NULL);

	int xstride = 1;
	int ystride = size.X;
	int zstride = size.X * size.Y;

	s16 sx = size.X;
	s16 sy = size.Y;
	s16 sz = size.Z;

	int i_start, i_step_x, i_step_z;
	switch (rot) {
		case ROTATE_90:
			i_start  = sx - 1;
			i_step_x = zstride;
			i_step_z = -xstride;
			SWAP(s16, sx, sz);
			break;
		case ROTATE_180:
			i_start  = zstride * (sz - 1) + sx - 1;
			i_step_x = -xstride;
			i_step_z = -zstride;
			break;
		case ROTATE_270:
			i_start  = zstride * (sz - 1);
			i_step_x = -zstride;
			i_step_z = xstride;
			SWAP(s16, sx, sz);
			break;
		default:
			i_start  = 0;
			i_step_x = xstride;
			i_step_z = zstride;
	}

	s16 y_map = p.Y;
	for (s16 y = 0; y != sy; y++) {
		if ((slice_probs[y] != MTSCHEM_PROB_ALWAYS) &&
			(slice_probs[y] <= myrand_range(1, MTSCHEM_PROB_ALWAYS)))
			continue;

		for (s16 z = 0; z != sz; z++) {
			u32 i = z * i_step_z + y * ystride + i_start;
			for (s16 x = 0; x != sx; x++, i += i_step_x) {
				u32 vi = vm->m_area.index(p.X + x, y_map, p.Z + z);
				if (!vm->m_area.contains(vi))
					continue;

				if (schemdata[i].getContent() == CONTENT_IGNORE)
					continue;

				u8 placement_prob     = schemdata[i].param1 & MTSCHEM_PROB_MASK;
				bool force_place_node = schemdata[i].param1 & MTSCHEM_FORCE_PLACE;

				if (placement_prob == MTSCHEM_PROB_NEVER)
					continue;

				if (!force_place && !force_place_node) {
					content_t c = vm->m_data[vi].getContent();
					if (c != CONTENT_AIR && c != CONTENT_IGNORE)
						continue;
				}

				if ((placement_prob != MTSCHEM_PROB_ALWAYS) &&
					(placement_prob <= myrand_range(1, MTSCHEM_PROB_ALWAYS)))
					continue;

				vm->m_data[vi] = schemdata[i];
				vm->m_data[vi].param1 = 0;

				if (rot)
					vm->m_data[vi].rotateAlongYAxis(m_ndef, rot);
			}
		}
		y_map++;
	}
}

bool Schematic::placeOnVManip(MMVManip *vm, v3s16 p, u32 flags,
	Rotation rot, bool force_place)
{
	assert(vm != NULL);
	assert(schemdata != NULL);
	sanity_check(m_ndef != NULL);

	//// Determine effective rotation and effective schematic dimensions
	if (rot == ROTATE_RAND)
		rot = (Rotation)myrand_range(ROTATE_0, ROTATE_270);

	v3s16 s = (rot == ROTATE_90 || rot == ROTATE_270) ?
		v3s16(size.Z, size.Y, size.X) : size;

	//// Adjust placement position if necessary
	if (flags & DECO_PLACE_CENTER_X)
		p.X -= (s.X + 1) / 2;
	if (flags & DECO_PLACE_CENTER_Y)
		p.Y -= (s.Y + 1) / 2;
	if (flags & DECO_PLACE_CENTER_Z)
		p.Z -= (s.Z + 1) / 2;

	blitToVManip(vm, p, rot, force_place);

	return vm->m_area.contains(VoxelArea(p, p + s - v3s16(1,1,1)));
}

void Schematic::placeOnMap(ServerMap *map, v3s16 p, u32 flags,
	Rotation rot, bool force_place)
{
	std::map<v3s16, MapBlock *> lighting_modified_blocks;
	std::map<v3s16, MapBlock *> modified_blocks;
	std::map<v3s16, MapBlock *>::iterator it;

	assert(map != NULL);
	assert(schemdata != NULL);
	sanity_check(m_ndef != NULL);

	//// Determine effective rotation and effective schematic dimensions
	if (rot == ROTATE_RAND)
		rot = (Rotation)myrand_range(ROTATE_0, ROTATE_270);

	v3s16 s = (rot == ROTATE_90 || rot == ROTATE_270) ?
			v3s16(size.Z, size.Y, size.X) : size;

	//// Adjust placement position if necessary
	if (flags & DECO_PLACE_CENTER_X)
		p.X -= (s.X + 1) / 2;
	if (flags & DECO_PLACE_CENTER_Y)
		p.Y -= (s.Y + 1) / 2;
	if (flags & DECO_PLACE_CENTER_Z)
		p.Z -= (s.Z + 1) / 2;

	//// Create VManip for effected area, emerge our area, modify area
	//// inside VManip, then blit back.
	v3s16 bp1 = getNodeBlockPos(p);
	v3s16 bp2 = getNodeBlockPos(p + s - v3s16(1,1,1));

	MMVManip vm(map);
	vm.initialEmerge(bp1, bp2);

	blitToVManip(&vm, p, rot, force_place);

	voxalgo::blit_back_with_light(map, &vm, &modified_blocks);

	//// Carry out post-map-modification actions

	//// Create & dispatch map modification events to observers
	MapEditEvent event;
	event.type = MEET_OTHER;
	for (it = modified_blocks.begin(); it != modified_blocks.end(); ++it)
		event.modified_blocks.insert(it->first);

	map->dispatchEvent(&event);
}

bool Schematic::deserializeFromMts(std::istream *is,
	std::vector<std::string> *names)
{
	std::istream &ss = *is;
	content_t cignore = CONTENT_IGNORE;
	bool have_cignore = false;

	//// Read signature
	u32 signature = readU32(ss);
	if (signature != MTSCHEM_FILE_SIGNATURE) {
		errorstream << __FUNCTION__ << ": invalid schematic "
			"file" << std::endl;
		return false;
	}

	//// Read version
	u16 version = readU16(ss);
	if (version > MTSCHEM_FILE_VER_HIGHEST_READ) {
		errorstream << __FUNCTION__ << ": unsupported schematic "
			"file version" << std::endl;
		return false;
	}

	//// Read size
	size = readV3S16(ss);

	//// Read Y-slice probability values
	delete []slice_probs;
	slice_probs = new u8[size.Y];
	for (int y = 0; y != size.Y; y++)
		slice_probs[y] = (version >= 3) ? readU8(ss) : MTSCHEM_PROB_ALWAYS_OLD;

	//// Read node names
	u16 nidmapcount = readU16(ss);
	for (int i = 0; i != nidmapcount; i++) {
		std::string name = deSerializeString(ss);

		// Instances of "ignore" from v1 are converted to air (and instances
		// are fixed to have MTSCHEM_PROB_NEVER later on).
		if (name == "ignore") {
			name = "air";
			cignore = i;
			have_cignore = true;
		}

		names->push_back(name);
	}

	//// Read node data
	size_t nodecount = size.X * size.Y * size.Z;

	delete []schemdata;
	schemdata = new MapNode[nodecount];

	MapNode::deSerializeBulk(ss, SER_FMT_VER_HIGHEST_READ, schemdata,
		nodecount, 2, 2, true);

	// Fix probability values for nodes that were ignore; removed in v2
	if (version < 2) {
		for (size_t i = 0; i != nodecount; i++) {
			if (schemdata[i].param1 == 0)
				schemdata[i].param1 = MTSCHEM_PROB_ALWAYS_OLD;
			if (have_cignore && schemdata[i].getContent() == cignore)
				schemdata[i].param1 = MTSCHEM_PROB_NEVER;
		}
	}

	// Fix probability values for probability range truncation introduced in v4
	if (version < 4) {
		for (s16 y = 0; y != size.Y; y++)
			slice_probs[y] >>= 1;
		for (size_t i = 0; i != nodecount; i++)
			schemdata[i].param1 >>= 1;
	}

	return true;
}

bool Schematic::serializeToMts(std::ostream *os,
	const std::vector<std::string> &names)
{
	std::ostream &ss = *os;

	writeU32(ss, MTSCHEM_FILE_SIGNATURE);         // signature
	writeU16(ss, MTSCHEM_FILE_VER_HIGHEST_WRITE); // version
	writeV3S16(ss, size);                         // schematic size

	for (int y = 0; y != size.Y; y++)             // Y slice probabilities
		writeU8(ss, slice_probs[y]);

	writeU16(ss, names.size()); // name count
	for (size_t i = 0; i != names.size(); i++)
		ss << serializeString(names[i]); // node names

	// compressed bulk node data
	MapNode::serializeBulk(ss, SER_FMT_VER_HIGHEST_WRITE,
		schemdata, size.X * size.Y * size.Z, 2, 2, true);

	return true;
}

bool Schematic::serializeToLua(std::ostream *os,
	const std::vector<std::string> &names, bool use_comments, u32 indent_spaces)
{
	std::ostream &ss = *os;

	std::string indent("\t");
	if (indent_spaces > 0)
		indent.assign(indent_spaces, ' ');

	//// Write header
	{
		ss << "schematic = {" << std::endl;
		ss << indent << "size = "
			<< "{x=" << size.X
			<< ", y=" << size.Y
			<< ", z=" << size.Z
			<< "}," << std::endl;
	}

	//// Write y-slice probabilities
	{
		ss << indent << "yslice_prob = {" << std::endl;

		for (u16 y = 0; y != size.Y; y++) {
			u8 probability = slice_probs[y] & MTSCHEM_PROB_MASK;

			ss << indent << indent << "{"
				<< "ypos=" << y
				<< ", prob=" << (u16)probability * 2
				<< "}," << std::endl;
		}

		ss << indent << "}," << std::endl;
	}

	//// Write node data
	{
		ss << indent << "data = {" << std::endl;

		u32 i = 0;
		for (u16 z = 0; z != size.Z; z++)
		for (u16 y = 0; y != size.Y; y++) {
			if (use_comments) {
				ss << std::endl
					<< indent << indent
					<< "-- z=" << z
					<< ", y=" << y << std::endl;
			}

			for (u16 x = 0; x != size.X; x++, i++) {
				u8 probability   = schemdata[i].param1 & MTSCHEM_PROB_MASK;
				bool force_place = schemdata[i].param1 & MTSCHEM_FORCE_PLACE;

				ss << indent << indent << "{"
					<< "name=\"" << names[schemdata[i].getContent()]
					<< "\", prob=" << (u16)probability * 2
					<< ", param2=" << (u16)schemdata[i].param2;

				if (force_place)
					ss << ", force_place=true";

				ss << "}," << std::endl;
			}
		}

		ss << indent << "}," << std::endl;
	}

	ss << "}" << std::endl;

	return true;
}

bool Schematic::loadSchematicFromFile(const std::string &filename,
	INodeDefManager *ndef, StringMap *replace_names)
{
	std::ifstream is(filename.c_str(), std::ios_base::binary);
	if (!is.good()) {
		errorstream << __FUNCTION__ << ": unable to open file '"
			<< filename << "'" << std::endl;
		return false;
	}

	size_t origsize = m_nodenames.size();
	if (!deserializeFromMts(&is, &m_nodenames))
		return false;

	m_nnlistsizes.push_back(m_nodenames.size() - origsize);

	name = filename;

	if (replace_names) {
		for (size_t i = origsize; i < m_nodenames.size(); i++) {
			std::string &node_name = m_nodenames[i];
			StringMap::iterator it = replace_names->find(node_name);
			if (it != replace_names->end())
				node_name = it->second;
		}
	}

	if (ndef)
		ndef->pendNodeResolve(this);

	return true;
}

bool Schematic::saveSchematicToFile(const std::string &filename,
	INodeDefManager *ndef)
{
	MapNode *orig_schemdata = schemdata;
	std::vector<std::string> ndef_nodenames;
	std::vector<std::string> *names;

	if (m_resolve_done && ndef == NULL)
		ndef = m_ndef;

	if (ndef) {
		names = &ndef_nodenames;

		u32 volume = size.X * size.Y * size.Z;
		schemdata = new MapNode[volume];
		for (u32 i = 0; i != volume; i++)
			schemdata[i] = orig_schemdata[i];

		generate_nodelist_and_update_ids(schemdata, volume, names, ndef);
	} else { // otherwise, use the names we have on hand in the list
		names = &m_nodenames;
	}

	std::ostringstream os(std::ios_base::binary);
	bool status = serializeToMts(&os, *names);

	if (ndef) {
		delete []schemdata;
		schemdata = orig_schemdata;
	}

	if (!status)
		return false;

	return fs::safeWriteToFile(filename, os.str());
}

bool Schematic::getSchematicFromMap(Map *map, v3s16 p1, v3s16 p2)
{
	MMVManip *vm = new MMVManip(map);

	v3s16 bp1 = getNodeBlockPos(p1);
	v3s16 bp2 = getNodeBlockPos(p2);
	vm->initialEmerge(bp1, bp2);

	size = p2 - p1 + 1;

	slice_probs = new u8[size.Y];
	for (s16 y = 0; y != size.Y; y++)
		slice_probs[y] = MTSCHEM_PROB_ALWAYS;

	schemdata = new MapNode[size.X * size.Y * size.Z];

	u32 i = 0;
	for (s16 z = p1.Z; z <= p2.Z; z++)
	for (s16 y = p1.Y; y <= p2.Y; y++) {
		u32 vi = vm->m_area.index(p1.X, y, z);
		for (s16 x = p1.X; x <= p2.X; x++, i++, vi++) {
			schemdata[i] = vm->m_data[vi];
			schemdata[i].param1 = MTSCHEM_PROB_ALWAYS;
		}
	}

	delete vm;
	return true;
}

void Schematic::applyProbabilities(v3s16 p0,
	std::vector<std::pair<v3s16, u8> > *plist,
	std::vector<std::pair<s16, u8> > *splist)
{
	for (size_t i = 0; i != plist->size(); i++) {
		v3s16 p = (*plist)[i].first - p0;
		int index = p.Z * (size.Y * size.X) + p.Y * size.X + p.X;
		if (index < size.Z * size.Y * size.X) {
			u8 prob = (*plist)[i].second;
			schemdata[index].param1 = prob;

			// trim unnecessary node names from schematic
			if (prob == MTSCHEM_PROB_NEVER)
				schemdata[index].setContent(CONTENT_AIR);
		}
	}

	for (size_t i = 0; i != splist->size(); i++) {
		s16 y = (*splist)[i].first - p0.Y;
		slice_probs[y] = (*splist)[i].second;
	}
}

void generate_nodelist_and_update_ids(MapNode *nodes, size_t nodecount,
	std::vector<std::string> *usednodes, INodeDefManager *ndef)
{
	UNORDERED_MAP<content_t, content_t> nodeidmap;
	content_t numids = 0;

	for (size_t i = 0; i != nodecount; i++) {
		content_t id;
		content_t c = nodes[i].getContent();

		UNORDERED_MAP<content_t, content_t>::const_iterator it = nodeidmap.find(c);
		if (it == nodeidmap.end()) {
			id = numids;
			numids++;

			usednodes->push_back(ndef->get(c).name);
			nodeidmap.insert(std::make_pair(c, id));
		} else {
			id = it->second;
		}
		nodes[i].setContent(id);
	}
}


code:
/*
Minetest
Copyright (C) 2014-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 MG_SCHEMATIC_HEADER
#define MG_SCHEMATIC_HEADER

#include <map>
#include "mg_decoration.h"
#include "util/string.h"

class Map;
class ServerMap;
class Mapgen;
class MMVManip;
class PseudoRandom;
class NodeResolver;
class Server;

/*
	Minetest Schematic File Format

	All values are stored in big-endian byte order.
	[u32] signature: 'MTSM'
	[u16] version: 4
	[u16] size X
	[u16] size Y
	[u16] size Z
	For each Y:
		[u8] slice probability value
	[Name-ID table] Name ID Mapping Table
		[u16] name-id count
		For each name-id mapping:
			[u16] name length
			[u8[]] name
	ZLib deflated {
	For each node in schematic:  (for z, y, x)
		[u16] content
	For each node in schematic:
		[u8] param1
		  bit 0-6: probability
		  bit 7:   specific node force placement
	For each node in schematic:
		[u8] param2
	}

	Version changes:
	1 - Initial version
	2 - Fixed messy never/always place; 0 probability is now never, 0xFF is always
	3 - Added y-slice probabilities; this allows for variable height structures
	4 - Compressed range of node occurence prob., added per-node force placement bit
*/

//// Schematic constants
#define MTSCHEM_FILE_SIGNATURE 0x4d54534d // 'MTSM'
#define MTSCHEM_FILE_VER_HIGHEST_READ  4
#define MTSCHEM_FILE_VER_HIGHEST_WRITE 4

#define MTSCHEM_PROB_MASK       0x7F

#define MTSCHEM_PROB_NEVER      0x00
#define MTSCHEM_PROB_ALWAYS     0x7F
#define MTSCHEM_PROB_ALWAYS_OLD 0xFF

#define MTSCHEM_FORCE_PLACE     0x80

enum SchematicType
{
	SCHEMATIC_NORMAL,
};

enum SchematicFormatType {
	SCHEM_FMT_HANDLE,
	SCHEM_FMT_MTS,
	SCHEM_FMT_LUA,
};

class Schematic : public ObjDef, public NodeResolver {
public:
	Schematic();
	virtual ~Schematic();

	virtual void resolveNodeNames();

	bool loadSchematicFromFile(const std::string &filename, INodeDefManager *ndef,
		StringMap *replace_names=NULL);
	bool saveSchematicToFile(const std::string &filename, INodeDefManager *ndef);
	bool getSchematicFromMap(Map *map, v3s16 p1, v3s16 p2);

	bool deserializeFromMts(std::istream *is, std::vector<std::string> *names);
	bool serializeToMts(std::ostream *os, const std::vector<std::string> &names);
	bool serializeToLua(std::ostream *os, const std::vector<std::string> &names,
		bool use_comments, u32 indent_spaces);

	void blitToVManip(MMVManip *vm, v3s16 p, Rotation rot, bool force_place);
	bool placeOnVManip(MMVManip *vm, v3s16 p, u32 flags, Rotation rot, bool force_place);
	void placeOnMap(ServerMap *map, v3s16 p, u32 flags, Rotation rot, bool force_place);

	void applyProbabilities(v3s16 p0,
		std::vector<std::pair<v3s16, u8> > *plist,
		std::vector<std::pair<s16, u8> > *splist);

	std::vector<content_t> c_nodes;
	u32 flags;
	v3s16 size;
	MapNode *schemdata;
	u8 *slice_probs;
};

class SchematicManager : public ObjDefManager {
public:
	SchematicManager(Server *server);
	virtual ~SchematicManager() {}

	virtual void clear();

	const char *getObjectTitle() const
	{
		return "schematic";
	}

	static Schematic *create(SchematicType type)
	{
		return new Schematic;
	}

private:
	Server *m_server;
};

void generate_nodelist_and_update_ids(MapNode *nodes, size_t nodecount,
	std::vector<std::string> *usednodes, INodeDefManager *ndef);

#endif


code:
/*
Minetest
Copyright (C) 2010-2015 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "minimap.h"
#include "threading/mutex_auto_lock.h"
#include "threading/semaphore.h"
#include "clientmap.h"
#include "settings.h"
#include "nodedef.h"
#include "porting.h"
#include "util/numeric.h"
#include "util/string.h"
#include "mapblock.h"
#include <math.h>

////
//// MinimapUpdateThread
////

MinimapUpdateThread::~MinimapUpdateThread()
{
	for (std::map<v3s16, MinimapMapblock *>::iterator
			it = m_blocks_cache.begin();
			it != m_blocks_cache.end(); ++it) {
		delete it->second;
	}

	for (std::deque<QueuedMinimapUpdate>::iterator
			it = m_update_queue.begin();
			it != m_update_queue.end(); ++it) {
		QueuedMinimapUpdate &q = *it;
		delete q.data;
	}
}

bool MinimapUpdateThread::pushBlockUpdate(v3s16 pos, MinimapMapblock *data)
{
	MutexAutoLock lock(m_queue_mutex);

	// Find if block is already in queue.
	// If it is, update the data and quit.
	for (std::deque<QueuedMinimapUpdate>::iterator
			it = m_update_queue.begin();
			it != m_update_queue.end(); ++it) {
		QueuedMinimapUpdate &q = *it;
		if (q.pos == pos) {
			delete q.data;
			q.data = data;
			return false;
		}
	}

	// Add the block
	QueuedMinimapUpdate q;
	q.pos  = pos;
	q.data = data;
	m_update_queue.push_back(q);

	return true;
}

bool MinimapUpdateThread::popBlockUpdate(QueuedMinimapUpdate *update)
{
	MutexAutoLock lock(m_queue_mutex);

	if (m_update_queue.empty())
		return false;

	*update = m_update_queue.front();
	m_update_queue.pop_front();

	return true;
}

void MinimapUpdateThread::enqueueBlock(v3s16 pos, MinimapMapblock *data)
{
	pushBlockUpdate(pos, data);
	deferUpdate();
}

void MinimapUpdateThread::doUpdate()
{
	QueuedMinimapUpdate update;

	while (popBlockUpdate(&update)) {
		if (update.data) {
			// Swap two values in the map using single lookup
			std::pair<std::map<v3s16, MinimapMapblock*>::iterator, bool>
			    result = m_blocks_cache.insert(std::make_pair(update.pos, update.data));
			if (!result.second) {
				delete result.first->second;
				result.first->second = update.data;
			}
		} else {
			std::map<v3s16, MinimapMapblock *>::iterator it;
			it = m_blocks_cache.find(update.pos);
			if (it != m_blocks_cache.end()) {
				delete it->second;
				m_blocks_cache.erase(it);
			}
		}
	}

	if (data->map_invalidated && data->mode != MINIMAP_MODE_OFF) {
		getMap(data->pos, data->map_size, data->scan_height);
		data->map_invalidated = false;
	}
}

void MinimapUpdateThread::getMap(v3s16 pos, s16 size, s16 height)
{
	v3s16 region(size, 0, size);
	v3s16 pos_min(pos.X - size / 2, pos.Y - height / 2, pos.Z - size / 2);
	v3s16 pos_max(pos_min.X + size - 1, pos.Y + height / 2, pos_min.Z + size - 1);
	v3s16 blockpos_min = getNodeBlockPos(pos_min);
	v3s16 blockpos_max = getNodeBlockPos(pos_max);

// clear the map
	for (int z = 0; z < size; z++)
	for (int x = 0; x < size; x++) {
		MinimapPixel &mmpixel = data->minimap_scan[x + z * size];
		mmpixel.air_count = 0;
		mmpixel.height = 0;
		mmpixel.n = MapNode(CONTENT_AIR);
	}

// draw the map
	v3s16 blockpos;
	for (blockpos.Z = blockpos_min.Z; blockpos.Z <= blockpos_max.Z; ++blockpos.Z)
	for (blockpos.Y = blockpos_min.Y; blockpos.Y <= blockpos_max.Y; ++blockpos.Y)
	for (blockpos.X = blockpos_min.X; blockpos.X <= blockpos_max.X; ++blockpos.X) {
		std::map<v3s16, MinimapMapblock *>::const_iterator pblock =
			m_blocks_cache.find(blockpos);
		if (pblock == m_blocks_cache.end())
			continue;
		const MinimapMapblock &block = *pblock->second;

		v3s16 block_node_min(blockpos * MAP_BLOCKSIZE);
		v3s16 block_node_max(block_node_min + MAP_BLOCKSIZE - 1);
		// clip
		v3s16 range_min = componentwise_max(block_node_min, pos_min);
		v3s16 range_max = componentwise_min(block_node_max, pos_max);

		v3s16 pos;
		pos.Y = range_min.Y;
		for (pos.Z = range_min.Z; pos.Z <= range_max.Z; ++pos.Z)
		for (pos.X = range_min.X; pos.X <= range_max.X; ++pos.X) {
			v3s16 inblock_pos = pos - block_node_min;
			const MinimapPixel &in_pixel =
				block.data[inblock_pos.Z * MAP_BLOCKSIZE + inblock_pos.X];

			v3s16 inmap_pos = pos - pos_min;
			MinimapPixel &out_pixel =
				data->minimap_scan[inmap_pos.X + inmap_pos.Z * size];

			out_pixel.air_count += in_pixel.air_count;
			if (in_pixel.n.param0 != CONTENT_AIR) {
				out_pixel.n = in_pixel.n;
				out_pixel.height = inmap_pos.Y + in_pixel.height;
			}
		}
	}
}

////
//// Mapper
////

Minimap::Minimap(IrrlichtDevice *device, Client *client)
{
	this->client    = client;
	this->driver    = device->getVideoDriver();
	this->m_tsrc    = client->getTextureSource();
	this->m_shdrsrc = client->getShaderSource();
	this->m_ndef    = client->getNodeDefManager();

	m_angle = 0.f;

	// Initialize static settings
	m_enable_shaders = g_settings->getBool("enable_shaders");
	m_surface_mode_scan_height =
		g_settings->getBool("minimap_double_scan_height") ? 256 : 128;

	// Initialize minimap data
	data = new MinimapData;
	data->mode              = MINIMAP_MODE_OFF;
	data->is_radar          = false;
	data->map_invalidated   = true;
	data->heightmap_image   = NULL;
	data->minimap_image     = NULL;
	data->texture           = NULL;
	data->heightmap_texture = NULL;
	data->minimap_shape_round = g_settings->getBool("minimap_shape_round");

	// Get round minimap textures
	data->minimap_mask_round = driver->createImage(
		m_tsrc->getTexture("minimap_mask_round.png"),
		core::position2d<s32>(0, 0),
		core::dimension2d<u32>(MINIMAP_MAX_SX, MINIMAP_MAX_SY));
	data->minimap_overlay_round = m_tsrc->getTexture("minimap_overlay_round.png");

	// Get square minimap textures
	data->minimap_mask_square = driver->createImage(
		m_tsrc->getTexture("minimap_mask_square.png"),
		core::position2d<s32>(0, 0),
		core::dimension2d<u32>(MINIMAP_MAX_SX, MINIMAP_MAX_SY));
	data->minimap_overlay_square = m_tsrc->getTexture("minimap_overlay_square.png");

	// Create player marker texture
	data->player_marker = m_tsrc->getTexture("player_marker.png");
	// Create object marker texture
	data->object_marker_red = m_tsrc->getTexture("object_marker_red.png");

	// Create mesh buffer for minimap
	m_meshbuffer = getMinimapMeshBuffer();

	// Initialize and start thread
	m_minimap_update_thread = new MinimapUpdateThread();
	m_minimap_update_thread->data = data;
	m_minimap_update_thread->start();
}

Minimap::~Minimap()
{
	m_minimap_update_thread->stop();
	m_minimap_update_thread->wait();

	m_meshbuffer->drop();

	data->minimap_mask_round->drop();
	data->minimap_mask_square->drop();

	driver->removeTexture(data->texture);
	driver->removeTexture(data->heightmap_texture);
	driver->removeTexture(data->minimap_overlay_round);
	driver->removeTexture(data->minimap_overlay_square);
	driver->removeTexture(data->object_marker_red);

	delete data;
	delete m_minimap_update_thread;
}

void Minimap::addBlock(v3s16 pos, MinimapMapblock *data)
{
	m_minimap_update_thread->enqueueBlock(pos, data);
}

void Minimap::toggleMinimapShape()
{
	MutexAutoLock lock(m_mutex);

	data->minimap_shape_round = !data->minimap_shape_round;
	g_settings->setBool("minimap_shape_round", data->minimap_shape_round);
	m_minimap_update_thread->deferUpdate();
}

void Minimap::setMinimapShape(MinimapShape shape)
{
	MutexAutoLock lock(m_mutex);

	if (shape == MINIMAP_SHAPE_SQUARE)
		data->minimap_shape_round = false;
	else if (shape == MINIMAP_SHAPE_ROUND)
		data->minimap_shape_round = true;

	g_settings->setBool("minimap_shape_round", data->minimap_shape_round);
	m_minimap_update_thread->deferUpdate();
}

MinimapShape Minimap::getMinimapShape()
{
	if (data->minimap_shape_round) {
		return MINIMAP_SHAPE_ROUND;
	} else {
		return MINIMAP_SHAPE_SQUARE;
	}
}

void Minimap::setMinimapMode(MinimapMode mode)
{
	static const MinimapModeDef modedefs[MINIMAP_MODE_COUNT] = {
		{false, 0, 0},
		{false, m_surface_mode_scan_height, 256},
		{false, m_surface_mode_scan_height, 128},
		{false, m_surface_mode_scan_height, 64},
		{true, 32, 128},
		{true, 32, 64},
		{true, 32, 32}
	};

	if (mode >= MINIMAP_MODE_COUNT)
		return;

	MutexAutoLock lock(m_mutex);

	data->is_radar    = modedefs[mode].is_radar;
	data->scan_height = modedefs[mode].scan_height;
	data->map_size    = modedefs[mode].map_size;
	data->mode        = mode;

	m_minimap_update_thread->deferUpdate();
}

void Minimap::setPos(v3s16 pos)
{
	bool do_update = false;

	{
		MutexAutoLock lock(m_mutex);

		if (pos != data->old_pos) {
			data->old_pos = data->pos;
			data->pos = pos;
			do_update = true;
		}
	}

	if (do_update)
		m_minimap_update_thread->deferUpdate();
}

void Minimap::setAngle(f32 angle)
{
	m_angle = angle;
}

void Minimap::blitMinimapPixelsToImageRadar(video::IImage *map_image)
{
	video::SColor c(240, 0, 0, 0);
	for (s16 x = 0; x < data->map_size; x++)
	for (s16 z = 0; z < data->map_size; z++) {
		MinimapPixel *mmpixel = &data->minimap_scan[x + z * data->map_size];

		if (mmpixel->air_count > 0)
			c.setGreen(core::clamp(core::round32(32 + mmpixel->air_count * 8), 0, 255));
		else
			c.setGreen(0);

		map_image->setPixel(x, data->map_size - z - 1, c);
	}
}

void Minimap::blitMinimapPixelsToImageSurface(
	video::IImage *map_image, video::IImage *heightmap_image)
{
	// This variable creation/destruction has a 1% cost on rendering minimap
	video::SColor tilecolor;
	for (s16 x = 0; x < data->map_size; x++)
	for (s16 z = 0; z < data->map_size; z++) {
		MinimapPixel *mmpixel = &data->minimap_scan[x + z * data->map_size];

		const ContentFeatures &f = m_ndef->get(mmpixel->n);
		const TileDef *tile = &f.tiledef[0];

		// Color of the 0th tile (mostly this is the topmost)
		if(tile->has_color)
			tilecolor = tile->color;
		else
			mmpixel->n.getColor(f, &tilecolor);

		tilecolor.setRed(tilecolor.getRed() * f.minimap_color.getRed() / 255);
		tilecolor.setGreen(tilecolor.getGreen() * f.minimap_color.getGreen() / 255);
		tilecolor.setBlue(tilecolor.getBlue() * f.minimap_color.getBlue() / 255);
		tilecolor.setAlpha(240);

		map_image->setPixel(x, data->map_size - z - 1, tilecolor);

		u32 h = mmpixel->height;
		heightmap_image->setPixel(x,data->map_size - z - 1,
			video::SColor(255, h, h, h));
	}
}

video::ITexture *Minimap::getMinimapTexture()
{
	// update minimap textures when new scan is ready
	if (data->map_invalidated)
		return data->texture;

	// create minimap and heightmap images in memory
	core::dimension2d<u32> dim(data->map_size, data->map_size);
	video::IImage *map_image       = driver->createImage(video::ECF_A8R8G8B8, dim);
	video::IImage *heightmap_image = driver->createImage(video::ECF_A8R8G8B8, dim);
	video::IImage *minimap_image   = driver->createImage(video::ECF_A8R8G8B8,
		core::dimension2d<u32>(MINIMAP_MAX_SX, MINIMAP_MAX_SY));

	// Blit MinimapPixels to images
	if (data->is_radar)
		blitMinimapPixelsToImageRadar(map_image);
	else
		blitMinimapPixelsToImageSurface(map_image, heightmap_image);

	map_image->copyToScaling(minimap_image);
	map_image->drop();

	video::IImage *minimap_mask = data->minimap_shape_round ?
		data->minimap_mask_round : data->minimap_mask_square;

	if (minimap_mask) {
		for (s16 y = 0; y < MINIMAP_MAX_SY; y++)
		for (s16 x = 0; x < MINIMAP_MAX_SX; x++) {
			const video::SColor &mask_col = minimap_mask->getPixel(x, y);
			if (!mask_col.getAlpha())
				minimap_image->setPixel(x, y, video::SColor(0,0,0,0));
		}
	}

	if (data->texture)
		driver->removeTexture(data->texture);
	if (data->heightmap_texture)
		driver->removeTexture(data->heightmap_texture);

	data->texture = driver->addTexture("minimap__", minimap_image);
	data->heightmap_texture =
		driver->addTexture("minimap_heightmap__", heightmap_image);
	minimap_image->drop();
	heightmap_image->drop();

	data->map_invalidated = true;

	return data->texture;
}

v3f Minimap::getYawVec()
{
	if (data->minimap_shape_round) {
		return v3f(
			cos(m_angle * core::DEGTORAD),
			sin(m_angle * core::DEGTORAD),
			1.0);
	} else {
		return v3f(1.0, 0.0, 1.0);
	}
}

scene::SMeshBuffer *Minimap::getMinimapMeshBuffer()
{
	scene::SMeshBuffer *buf = new scene::SMeshBuffer();
	buf->Vertices.set_used(4);
	buf->Indices.set_used(6);
	static const video::SColor c(255, 255, 255, 255);

	buf->Vertices[0] = video::S3DVertex(-1, -1, 0, 0, 0, 1, c, 0, 1);
	buf->Vertices[1] = video::S3DVertex(-1,  1, 0, 0, 0, 1, c, 0, 0);
	buf->Vertices[2] = video::S3DVertex( 1,  1, 0, 0, 0, 1, c, 1, 0);
	buf->Vertices[3] = video::S3DVertex( 1, -1, 0, 0, 0, 1, c, 1, 1);

	buf->Indices[0] = 0;
	buf->Indices[1] = 1;
	buf->Indices[2] = 2;
	buf->Indices[3] = 2;
	buf->Indices[4] = 3;
	buf->Indices[5] = 0;

	return buf;
}

void Minimap::drawMinimap()
{
	video::ITexture *minimap_texture = getMinimapTexture();
	if (!minimap_texture)
		return;

	updateActiveMarkers();
	v2u32 screensize = porting::getWindowSize();
	const u32 size = 0.25 * screensize.Y;

	core::rect<s32> oldViewPort = driver->getViewPort();
	core::matrix4 oldProjMat = driver->getTransform(video::ETS_PROJECTION);
	core::matrix4 oldViewMat = driver->getTransform(video::ETS_VIEW);

	driver->setViewPort(core::rect<s32>(
		screensize.X - size - 10, 10,
		screensize.X - 10, size + 10));
	driver->setTransform(video::ETS_PROJECTION, core::matrix4());
	driver->setTransform(video::ETS_VIEW, core::matrix4());

	core::matrix4 matrix;
	matrix.makeIdentity();

	video::SMaterial &material = m_meshbuffer->getMaterial();
	material.setFlag(video::EMF_TRILINEAR_FILTER, true);
	material.Lighting = false;
	material.TextureLayer[0].Texture = minimap_texture;
	material.TextureLayer[1].Texture = data->heightmap_texture;

	if (m_enable_shaders && !data->is_radar) {
		u16 sid = m_shdrsrc->getShader("minimap_shader", 1, 1);
		material.MaterialType = m_shdrsrc->getShaderInfo(sid).material;
	} else {
		material.MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL;
	}

	if (data->minimap_shape_round)
		matrix.setRotationDegrees(core::vector3df(0, 0, 360 - m_angle));

	// Draw minimap
	driver->setTransform(video::ETS_WORLD, matrix);
	driver->setMaterial(material);
	driver->drawMeshBuffer(m_meshbuffer);

	// Draw overlay
	video::ITexture *minimap_overlay = data->minimap_shape_round ?
		data->minimap_overlay_round : data->minimap_overlay_square;
	material.TextureLayer[0].Texture = minimap_overlay;
	material.MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL;
	driver->setMaterial(material);
	driver->drawMeshBuffer(m_meshbuffer);

	// If round minimap, draw player marker
	if (!data->minimap_shape_round) {
		matrix.setRotationDegrees(core::vector3df(0, 0, m_angle));
		material.TextureLayer[0].Texture = data->player_marker;

		driver->setTransform(video::ETS_WORLD, matrix);
		driver->setMaterial(material);
		driver->drawMeshBuffer(m_meshbuffer);
	}

	// Reset transformations
	driver->setTransform(video::ETS_VIEW, oldViewMat);
	driver->setTransform(video::ETS_PROJECTION, oldProjMat);
	driver->setViewPort(oldViewPort);

	// Draw player markers
	v2s32 s_pos(screensize.X - size - 10, 10);
	core::dimension2di imgsize(data->object_marker_red->getOriginalSize());
	core::rect<s32> img_rect(0, 0, imgsize.Width, imgsize.Height);
	static const video::SColor col(255, 255, 255, 255);
	static const video::SColor c[4] = {col, col, col, col};
	f32 sin_angle = sin(m_angle * core::DEGTORAD);
	f32 cos_angle = cos(m_angle * core::DEGTORAD);
	s32 marker_size2 =  0.025 * (float)size;
	for (std::list<v2f>::const_iterator
			i = m_active_markers.begin();
			i != m_active_markers.end(); ++i) {
		v2f posf = *i;
		if (data->minimap_shape_round) {
			f32 t1 = posf.X * cos_angle - posf.Y * sin_angle;
			f32 t2 = posf.X * sin_angle + posf.Y * cos_angle;
			posf.X = t1;
			posf.Y = t2;
		}
		posf.X = (posf.X + 0.5) * (float)size;
		posf.Y = (posf.Y + 0.5) * (float)size;
		core::rect<s32> dest_rect(
			s_pos.X + posf.X - marker_size2,
			s_pos.Y + posf.Y - marker_size2,
			s_pos.X + posf.X + marker_size2,
			s_pos.Y + posf.Y + marker_size2);
		driver->draw2DImage(data->object_marker_red, dest_rect,
			img_rect, &dest_rect, &c[0], true);
	}
}

void Minimap::updateActiveMarkers()
{
	video::IImage *minimap_mask = data->minimap_shape_round ?
		data->minimap_mask_round : data->minimap_mask_square;

	const std::list<Nametag *> &nametags = client->getCamera()->getNametags();

	m_active_markers.clear();

	for (std::list<Nametag *>::const_iterator i = nametags.begin();
			i != nametags.end(); ++i) {
		v3s16 pos = floatToInt((*i)->parent_node->getPosition() +
			intToFloat(client->getCamera()->getOffset(), BS), BS);
		pos -= data->pos - v3s16(data->map_size / 2,
				data->scan_height / 2,
				data->map_size / 2);
		if (pos.X < 0 || pos.X > data->map_size ||
				pos.Y < 0 || pos.Y > data->scan_height ||
				pos.Z < 0 || pos.Z > data->map_size) {
			continue;
		}
		pos.X = ((float)pos.X / data->map_size) * MINIMAP_MAX_SX;
		pos.Z = ((float)pos.Z / data->map_size) * MINIMAP_MAX_SY;
		const video::SColor &mask_col = minimap_mask->getPixel(pos.X, pos.Z);
		if (!mask_col.getAlpha()) {
			continue;
		}
		m_active_markers.push_back(v2f(((float)pos.X / (float)MINIMAP_MAX_SX) - 0.5,
			(1.0 - (float)pos.Z / (float)MINIMAP_MAX_SY) - 0.5));
	}
}

////
//// MinimapMapblock
////

void MinimapMapblock::getMinimapNodes(VoxelManipulator *vmanip, v3s16 pos)
{

	for (s16 x = 0; x < MAP_BLOCKSIZE; x++)
	for (s16 z = 0; z < MAP_BLOCKSIZE; z++) {
		s16 air_count = 0;
		bool surface_found = false;
		MinimapPixel *mmpixel = &data[z * MAP_BLOCKSIZE + x];

		for (s16 y = MAP_BLOCKSIZE -1; y >= 0; y--) {
			v3s16 p(x, y, z);
			MapNode n = vmanip->getNodeNoEx(pos + p);
			if (!surface_found && n.getContent() != CONTENT_AIR) {
				mmpixel->height = y;
				mmpixel->n = n;
				surface_found = true;
			} else if (n.getContent() == CONTENT_AIR) {
				air_count++;
			}
		}

		if (!surface_found)
			mmpixel->n = MapNode(CONTENT_AIR);

		mmpixel->air_count = air_count;
	}
}


code:
/*
Minetest
Copyright (C) 2010-2015 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef MINIMAP_HEADER
#define MINIMAP_HEADER

#include "irrlichttypes_extrabloated.h"
#include "client.h"
#include "voxel.h"
#include "threading/mutex.h"
#include "threading/semaphore.h"
#include <map>
#include <string>
#include <vector>
#include "camera.h"

#define MINIMAP_MAX_SX 512
#define MINIMAP_MAX_SY 512

enum MinimapMode {
	MINIMAP_MODE_OFF,
	MINIMAP_MODE_SURFACEx1,
	MINIMAP_MODE_SURFACEx2,
	MINIMAP_MODE_SURFACEx4,
	MINIMAP_MODE_RADARx1,
	MINIMAP_MODE_RADARx2,
	MINIMAP_MODE_RADARx4,
	MINIMAP_MODE_COUNT,
};

enum MinimapShape {
	MINIMAP_SHAPE_SQUARE,
	MINIMAP_SHAPE_ROUND,
};

struct MinimapModeDef {
	bool is_radar;
	u16 scan_height;
	u16 map_size;
};

struct MinimapPixel {
	//! The topmost node that the minimap displays.
	MapNode n;
	u16 height;
	u16 air_count;
};

struct MinimapMapblock {
	void getMinimapNodes(VoxelManipulator *vmanip, v3s16 pos);

	MinimapPixel data[MAP_BLOCKSIZE * MAP_BLOCKSIZE];
};

struct MinimapData {
	bool is_radar;
	MinimapMode mode;
	v3s16 pos;
	v3s16 old_pos;
	u16 scan_height;
	u16 map_size;
	MinimapPixel minimap_scan[MINIMAP_MAX_SX * MINIMAP_MAX_SY];
	bool map_invalidated;
	bool minimap_shape_round;
	video::IImage *minimap_image;
	video::IImage *heightmap_image;
	video::IImage *minimap_mask_round;
	video::IImage *minimap_mask_square;
	video::ITexture *texture;
	video::ITexture *heightmap_texture;
	video::ITexture *minimap_overlay_round;
	video::ITexture *minimap_overlay_square;
	video::ITexture *player_marker;
	video::ITexture *object_marker_red;
};

struct QueuedMinimapUpdate {
	v3s16 pos;
	MinimapMapblock *data;
};

class MinimapUpdateThread : public UpdateThread {
public:
	MinimapUpdateThread() : UpdateThread("Minimap") {}
	virtual ~MinimapUpdateThread();

	void getMap(v3s16 pos, s16 size, s16 height);
	void enqueueBlock(v3s16 pos, MinimapMapblock *data);
	bool pushBlockUpdate(v3s16 pos, MinimapMapblock *data);
	bool popBlockUpdate(QueuedMinimapUpdate *update);

	MinimapData *data;

protected:
	virtual void doUpdate();

private:
	Mutex m_queue_mutex;
	std::deque<QueuedMinimapUpdate> m_update_queue;
	std::map<v3s16, MinimapMapblock *> m_blocks_cache;
};

class Minimap {
public:
	Minimap(IrrlichtDevice *device, Client *client);
	~Minimap();

	void addBlock(v3s16 pos, MinimapMapblock *data);

	v3f getYawVec();

	void setPos(v3s16 pos);
	v3s16 getPos() const { return data->pos; }
	void setAngle(f32 angle);
	f32 getAngle() const { return m_angle; }
	void setMinimapMode(MinimapMode mode);
	MinimapMode getMinimapMode() const { return data->mode; }
	void toggleMinimapShape();
	void setMinimapShape(MinimapShape shape);
	MinimapShape getMinimapShape();

	video::ITexture *getMinimapTexture();

	void blitMinimapPixelsToImageRadar(video::IImage *map_image);
	void blitMinimapPixelsToImageSurface(video::IImage *map_image,
		video::IImage *heightmap_image);

	scene::SMeshBuffer *getMinimapMeshBuffer();

	void updateActiveMarkers();
	void drawMinimap();

	video::IVideoDriver *driver;
	Client* client;
	MinimapData *data;

private:
	ITextureSource *m_tsrc;
	IShaderSource *m_shdrsrc;
	INodeDefManager *m_ndef;
	MinimapUpdateThread *m_minimap_update_thread;
	scene::SMeshBuffer *m_meshbuffer;
	bool m_enable_shaders;
	u16 m_surface_mode_scan_height;
	f32 m_angle;
	Mutex m_mutex;
	std::list<v2f> m_active_markers;
};

#endif


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef MODALMENU_HEADER
#define MODALMENU_HEADER

#include "irrlichttypes_extrabloated.h"
#ifdef HAVE_TOUCHSCREENGUI
#include "touchscreengui.h"
#endif

class GUIModalMenu;

class IMenuManager
{
public:
	// A GUIModalMenu calls these when this class is passed as a parameter
	virtual void createdMenu(gui::IGUIElement *menu) = 0;
	virtual void deletingMenu(gui::IGUIElement *menu) = 0;
};

/*
	Remember to drop() the menu after creating, so that it can
	remove itself when it wants to.
*/

class GUIModalMenu : public gui::IGUIElement
{
public:
	GUIModalMenu(gui::IGUIEnvironment* env, gui::IGUIElement* parent, s32 id,
			IMenuManager *menumgr):
		IGUIElement(gui::EGUIET_ELEMENT, env, parent, id,
				core::rect<s32>(0,0,100,100))
	{
		//m_force_regenerate_gui = false;

		m_menumgr = menumgr;
		m_allow_focus_removal = false;
		m_screensize_old = v2u32(0,0);

		setVisible(true);
		Environment->setFocus(this);
		m_menumgr->createdMenu(this);
	}

	virtual ~GUIModalMenu()
	{
		m_menumgr->deletingMenu(this);
	}

	void allowFocusRemoval(bool allow)
	{
		m_allow_focus_removal = allow;
	}

	bool canTakeFocus(gui::IGUIElement *e)
	{
		return (e && (e == this || isMyChild(e))) || m_allow_focus_removal;
	}

	void draw()
	{
		if(!IsVisible)
			return;

		video::IVideoDriver* driver = Environment->getVideoDriver();
		v2u32 screensize = driver->getScreenSize();
		if(screensize != m_screensize_old /*|| m_force_regenerate_gui*/)
		{
			m_screensize_old = screensize;
			regenerateGui(screensize);
			//m_force_regenerate_gui = false;
		}

		drawMenu();
	}

	/*
		This should be called when the menu wants to quit.

		WARNING: THIS DEALLOCATES THE MENU FROM MEMORY. Return
		immediately if you call this from the menu itself.

		(More precisely, this decrements the reference count.)
	*/
	void quitMenu()
	{
		allowFocusRemoval(true);
		// This removes Environment's grab on us
		Environment->removeFocus(this);
		m_menumgr->deletingMenu(this);
		this->remove();
#ifdef HAVE_TOUCHSCREENGUI
		if (g_touchscreengui)
			g_touchscreengui->show();
#endif
	}

	void removeChildren()
	{
		const core::list<gui::IGUIElement*> &children = getChildren();
		core::list<gui::IGUIElement*> children_copy;
		for(core::list<gui::IGUIElement*>::ConstIterator
				i = children.begin(); i != children.end(); i++)
		{
			children_copy.push_back(*i);
		}
		for(core::list<gui::IGUIElement*>::Iterator
				i = children_copy.begin();
				i != children_copy.end(); i++)
		{
			(*i)->remove();
		}
	}

	virtual void regenerateGui(v2u32 screensize) = 0;
	virtual void drawMenu() = 0;
	virtual bool preprocessEvent(const SEvent& event) { return false; };
	virtual bool OnEvent(const SEvent& event) { return false; };
	virtual bool pausesGame(){ return false; } // Used for pause menu

protected:
	//bool m_force_regenerate_gui;
	v2u32 m_screensize_old;
private:
	IMenuManager *m_menumgr;
	// This might be necessary to expose to the implementation if it
	// wants to launch other menus
	bool m_allow_focus_removal;
};

#endif


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef MODIFIEDSTATE_HEADER
#define MODIFIEDSTATE_HEADER

enum ModifiedState
{
	// Has not been modified.
	MOD_STATE_CLEAN = 0,
	MOD_RESERVED1 = 1,
	// Has been modified, and will be saved when being unloaded.
	MOD_STATE_WRITE_AT_UNLOAD = 2,
	MOD_RESERVED3 = 3,
	// Has been modified, and will be saved as soon as possible.
	MOD_STATE_WRITE_NEEDED = 4,
	MOD_RESERVED5 = 5,
};

#endif


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include <cctype>
#include <fstream>
#include "mods.h"
#include "filesys.h"
#include "log.h"
#include "subgame.h"
#include "settings.h"
#include "convert_json.h"
#include "exceptions.h"
#include "porting.h"

static bool parseDependsLine(std::istream &is,
		std::string &dep, std::set<char> &symbols)
{
	std::getline(is, dep);
	dep = trim(dep);
	symbols.clear();
	size_t pos = dep.size();
	while(pos > 0 && !string_allowed(dep.substr(pos-1, 1), MODNAME_ALLOWED_CHARS)){
		// last character is a symbol, not part of the modname
		symbols.insert(dep[pos-1]);
		--pos;
	}
	dep = trim(dep.substr(0, pos));
	return dep != "";
}

void parseModContents(ModSpec &spec)
{
	// NOTE: this function works in mutual recursion with getModsInPath
	Settings info;
	info.readConfigFile((spec.path+DIR_DELIM+"mod.conf").c_str());

	if (info.exists("name"))
		spec.name = info.get("name");

	spec.depends.clear();
	spec.optdepends.clear();
	spec.is_modpack = false;
	spec.modpack_content.clear();

	// Handle modpacks (defined by containing modpack.txt)
	std::ifstream modpack_is((spec.path+DIR_DELIM+"modpack.txt").c_str());
	if(modpack_is.good()){ //a modpack, recursively get the mods in it
		modpack_is.close(); // We don't actually need the file
		spec.is_modpack = true;
		spec.modpack_content = getModsInPath(spec.path, true);

		// modpacks have no dependencies; they are defined and
		// tracked separately for each mod in the modpack
	}
	else{ // not a modpack, parse the dependencies
		std::ifstream is((spec.path+DIR_DELIM+"depends.txt").c_str());
		while(is.good()){
			std::string dep;
			std::set<char> symbols;
			if(parseDependsLine(is, dep, symbols)){
				if(symbols.count('?') != 0){
					spec.optdepends.insert(dep);
				}
				else{
					spec.depends.insert(dep);
				}
			}
		}
	}
}

std::map<std::string, ModSpec> getModsInPath(std::string path, bool part_of_modpack)
{
	// NOTE: this function works in mutual recursion with parseModContents

	std::map<std::string, ModSpec> result;
	std::vector<fs::DirListNode> dirlist = fs::GetDirListing(path);
	for(u32 j=0; j<dirlist.size(); j++){
		if(!dirlist[j].dir)
			continue;
		std::string modname = dirlist[j].name;
		// Ignore all directories beginning with a ".", especially
		// VCS directories like ".git" or ".svn"
		if(modname[0] == '.')
			continue;
		std::string modpath = path + DIR_DELIM + modname;

		ModSpec spec(modname, modpath);
		spec.part_of_modpack = part_of_modpack;
		parseModContents(spec);
		result.insert(std::make_pair(modname, spec));
	}
	return result;
}

std::vector<ModSpec> flattenMods(std::map<std::string, ModSpec> mods)
{
	std::vector<ModSpec> result;
	for(std::map<std::string,ModSpec>::iterator it = mods.begin();
		it != mods.end(); ++it)
	{
		ModSpec mod = (*it).second;
		if(mod.is_modpack)
		{
			std::vector<ModSpec> content = flattenMods(mod.modpack_content);
			result.reserve(result.size() + content.size());
			result.insert(result.end(),content.begin(),content.end());

		}
		else //not a modpack
		{
			result.push_back(mod);
		}
	}
	return result;
}

ModConfiguration::ModConfiguration(const std::string &worldpath):
	m_unsatisfied_mods(),
	m_sorted_mods(),
	m_name_conflicts()
{
}

void ModConfiguration::printUnsatisfiedModsError() const
{
	for (std::vector<ModSpec>::const_iterator it = m_unsatisfied_mods.begin();
		it != m_unsatisfied_mods.end(); ++it) {
		ModSpec mod = *it;
		errorstream << "mod \"" << mod.name << "\" has unsatisfied dependencies: ";
		for (UNORDERED_SET<std::string>::iterator dep_it = mod.unsatisfied_depends.begin();
			dep_it != mod.unsatisfied_depends.end(); ++dep_it)
			errorstream << " \"" << *dep_it << "\"";
		errorstream << std::endl;
	}
}

void ModConfiguration::addModsInPath(const std::string &path)
{
	addMods(flattenMods(getModsInPath(path)));
}

void ModConfiguration::addMods(const std::vector<ModSpec> &new_mods)
{
	// Maintain a map of all existing m_unsatisfied_mods.
	// Keys are mod names and values are indices into m_unsatisfied_mods.
	std::map<std::string, u32> existing_mods;
	for(u32 i = 0; i < m_unsatisfied_mods.size(); ++i){
		existing_mods[m_unsatisfied_mods[i].name] = i;
	}

	// Add new mods
	for(int want_from_modpack = 1; want_from_modpack >= 0; --want_from_modpack){
		// First iteration:
		// Add all the mods that come from modpacks
		// Second iteration:
		// Add all the mods that didn't come from modpacks

		std::set<std::string> seen_this_iteration;

		for (std::vector<ModSpec>::const_iterator it = new_mods.begin();
				it != new_mods.end(); ++it) {
			const ModSpec &mod = *it;
			if(mod.part_of_modpack != (bool)want_from_modpack)
				continue;
			if(existing_mods.count(mod.name) == 0){
				// GOOD CASE: completely new mod.
				m_unsatisfied_mods.push_back(mod);
				existing_mods[mod.name] = m_unsatisfied_mods.size() - 1;
			}
			else if(seen_this_iteration.count(mod.name) == 0){
				// BAD CASE: name conflict in different levels.
				u32 oldindex = existing_mods[mod.name];
				const ModSpec &oldmod = m_unsatisfied_mods[oldindex];
				warningstream<<"Mod name conflict detected: \""
					<<mod.name<<"\""<<std::endl
					<<"Will not load: "<<oldmod.path<<std::endl
					<<"Overridden by: "<<mod.path<<std::endl;
				m_unsatisfied_mods[oldindex] = mod;

				// If there was a "VERY BAD CASE" name conflict
				// in an earlier level, ignore it.
				m_name_conflicts.erase(mod.name);
			}
			else{
				// VERY BAD CASE: name conflict in the same level.
				u32 oldindex = existing_mods[mod.name];
				const ModSpec &oldmod = m_unsatisfied_mods[oldindex];
				warningstream<<"Mod name conflict detected: \""
					<<mod.name<<"\""<<std::endl
					<<"Will not load: "<<oldmod.path<<std::endl
					<<"Will not load: "<<mod.path<<std::endl;
				m_unsatisfied_mods[oldindex] = mod;
				m_name_conflicts.insert(mod.name);
			}
			seen_this_iteration.insert(mod.name);
		}
	}
}

void ModConfiguration::addModsFormConfig(const std::string &settings_path, const std::set<std::string> &mods)
{
	Settings conf;
	std::set<std::string> load_mod_names;

	conf.readConfigFile(settings_path.c_str());
	std::vector<std::string> names = conf.getNames();
	for (std::vector<std::string>::iterator it = names.begin();
		it != names.end(); ++it) {
		std::string name = *it;
		if (name.compare(0,9,"load_mod_")==0 && conf.getBool(name))
			load_mod_names.insert(name.substr(9));
	}

	std::vector<ModSpec> addon_mods;
	for (std::set<std::string>::const_iterator i = mods.begin();
			i != mods.end(); ++i) {
		std::vector<ModSpec> addon_mods_in_path = flattenMods(getModsInPath(*i));
		for (std::vector<ModSpec>::const_iterator it = addon_mods_in_path.begin();
				it != addon_mods_in_path.end(); ++it) {
			const ModSpec& mod = *it;
			if (load_mod_names.count(mod.name) != 0)
				addon_mods.push_back(mod);
			else
				conf.setBool("load_mod_" + mod.name, false);
		}
	}
	conf.updateConfigFile(settings_path.c_str());

	addMods(addon_mods);
	checkConflictsAndDeps();

	// complain about mods declared to be loaded, but not found
	for (std::vector<ModSpec>::iterator it = addon_mods.begin();
			it != addon_mods.end(); ++it)
		load_mod_names.erase((*it).name);
	std::vector<ModSpec> UnsatisfiedMods = getUnsatisfiedMods();
	for (std::vector<ModSpec>::iterator it = UnsatisfiedMods.begin();
			it != UnsatisfiedMods.end(); ++it)
		load_mod_names.erase((*it).name);
	if (!load_mod_names.empty()) {
		errorstream << "The following mods could not be found:";
		for (std::set<std::string>::iterator it = load_mod_names.begin();
				it != load_mod_names.end(); ++it)
			errorstream << " \"" << (*it) << "\"";
		errorstream << std::endl;
	}
}

void ModConfiguration::checkConflictsAndDeps()
{
	// report on name conflicts
	if (!m_name_conflicts.empty()) {
		std::string s = "Unresolved name conflicts for mods ";
		for (UNORDERED_SET<std::string>::const_iterator it = m_name_conflicts.begin();
			it != m_name_conflicts.end(); ++it) {
			if (it != m_name_conflicts.begin()) s += ", ";
			s += std::string("\"") + (*it) + "\"";
		}
		s += ".";
		throw ModError(s);
	}

	// get the mods in order
	resolveDependencies();
}

void ModConfiguration::resolveDependencies()
{
	// Step 1: Compile a list of the mod names we're working with
	std::set<std::string> modnames;
	for(std::vector<ModSpec>::iterator it = m_unsatisfied_mods.begin();
		it != m_unsatisfied_mods.end(); ++it){
		modnames.insert((*it).name);
	}

	// Step 2: get dependencies (including optional dependencies)
	// of each mod, split mods into satisfied and unsatisfied
	std::list<ModSpec> satisfied;
	std::list<ModSpec> unsatisfied;
	for (std::vector<ModSpec>::iterator it = m_unsatisfied_mods.begin();
			it != m_unsatisfied_mods.end(); ++it) {
		ModSpec mod = *it;
		mod.unsatisfied_depends = mod.depends;
		// check which optional dependencies actually exist
		for (UNORDERED_SET<std::string>::iterator it_optdep = mod.optdepends.begin();
				it_optdep != mod.optdepends.end(); ++it_optdep) {
			std::string optdep = *it_optdep;
			if (modnames.count(optdep) != 0)
				mod.unsatisfied_depends.insert(optdep);
		}
		// if a mod has no depends it is initially satisfied
		if (mod.unsatisfied_depends.empty())
			satisfied.push_back(mod);
		else
			unsatisfied.push_back(mod);
	}

	// Step 3: mods without unmet dependencies can be appended to
	// the sorted list.
	while(!satisfied.empty()){
		ModSpec mod = satisfied.back();
		m_sorted_mods.push_back(mod);
		satisfied.pop_back();
		for(std::list<ModSpec>::iterator it = unsatisfied.begin();
				it != unsatisfied.end(); ){
			ModSpec& mod2 = *it;
			mod2.unsatisfied_depends.erase(mod.name);
			if(mod2.unsatisfied_depends.empty()){
				satisfied.push_back(mod2);
				it = unsatisfied.erase(it);
			}
			else{
				++it;
			}
		}
	}

	// Step 4: write back list of unsatisfied mods
	m_unsatisfied_mods.assign(unsatisfied.begin(), unsatisfied.end());
}

ServerModConfiguration::ServerModConfiguration(const std::string &worldpath):
	ModConfiguration(worldpath)
{
	SubgameSpec gamespec = findWorldSubgame(worldpath);

	// Add all game mods and all world mods
	addModsInPath(gamespec.gamemods_path);
	addModsInPath(worldpath + DIR_DELIM + "worldmods");

	// Load normal mods
	std::string worldmt = worldpath + DIR_DELIM + "world.mt";
	addModsFormConfig(worldmt, gamespec.addon_mods_paths);
}

#ifndef SERVER
ClientModConfiguration::ClientModConfiguration(const std::string &path):
	ModConfiguration(path)
{
	std::set<std::string> paths;
	std::string path_user = porting::path_user + DIR_DELIM + "clientmods";
	paths.insert(path);
	paths.insert(path_user);

	std::string settings_path = path_user + DIR_DELIM + "mods.conf";
	addModsFormConfig(settings_path, paths);
}
#endif

#if USE_CURL
Json::Value getModstoreUrl(const std::string &url)
{
	std::vector<std::string> extra_headers;

	bool special_http_header = true;

	try {
		special_http_header = g_settings->getBool("modstore_disable_special_http_header");
	} catch (SettingNotFoundException) {}

	if (special_http_header) {
		extra_headers.push_back("Accept: application/vnd.minetest.mmdb-v1+json");
	}
	return fetchJsonValue(url, special_http_header ? &extra_headers : NULL);
}

#endif

ModMetadata::ModMetadata(const std::string &mod_name):
	m_mod_name(mod_name),
	m_modified(false)
{
	m_stringvars.clear();
}

void ModMetadata::clear()
{
	Metadata::clear();
	m_modified = true;
}

bool ModMetadata::save(const std::string &root_path)
{
	Json::Value json;
	for (StringMap::const_iterator it = m_stringvars.begin();
			it != m_stringvars.end(); ++it) {
		json[it->first] = it->second;
	}

	if (!fs::PathExists(root_path)) {
		if (!fs::CreateAllDirs(root_path)) {
			errorstream << "ModMetadata[" << m_mod_name << "]: Unable to save. '"
				<< root_path << "' tree cannot be created." << std::endl;
			return false;
		}
	} else if (!fs::IsDir(root_path)) {
		errorstream << "ModMetadata[" << m_mod_name << "]: Unable to save. '"
			<< root_path << "' is not a directory." << std::endl;
		return false;
	}

	bool w_ok = fs::safeWriteToFile(root_path + DIR_DELIM + m_mod_name,
		Json::FastWriter().write(json));

	if (w_ok) {
		m_modified = false;
	} else {
		errorstream << "ModMetadata[" << m_mod_name << "]: failed write file." << std::endl;
	}
	return w_ok;
}

bool ModMetadata::load(const std::string &root_path)
{
	m_stringvars.clear();

	std::ifstream is((root_path + DIR_DELIM + m_mod_name).c_str(), std::ios_base::binary);
	if (!is.good()) {
		return false;
	}

	Json::Reader reader;
	Json::Value root;
	if (!reader.parse(is, root)) {
		errorstream << "ModMetadata[" << m_mod_name << "]: failed read data "
			"(Json decoding failure)." << std::endl;
		return false;
	}

	const Json::Value::Members attr_list = root.getMemberNames();
	for (Json::Value::Members::const_iterator it = attr_list.begin();
			it != attr_list.end(); ++it) {
		Json::Value attr_value = root[*it];
		m_stringvars[*it] = attr_value.asString();
	}

	return true;
}

bool ModMetadata::setString(const std::string &name, const std::string &var)
{
	m_modified = Metadata::setString(name, var);
	return m_modified;
}


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef MODS_HEADER
#define MODS_HEADER

#include "irrlichttypes.h"
#include <list>
#include <set>
#include <vector>
#include <string>
#include <map>
#include <json/json.h>
#include "util/cpp11_container.h"
#include "config.h"
#include "metadata.h"

#define MODNAME_ALLOWED_CHARS "abcdefghijklmnopqrstuvwxyz0123456789_"

struct ModSpec
{
	std::string name;
	std::string path;
	//if normal mod:
	UNORDERED_SET<std::string> depends;
	UNORDERED_SET<std::string> optdepends;
	UNORDERED_SET<std::string> unsatisfied_depends;

	bool part_of_modpack;
	bool is_modpack;
	// if modpack:
	std::map<std::string,ModSpec> modpack_content;
	ModSpec(const std::string &name_="", const std::string &path_=""):
		name(name_),
		path(path_),
		depends(),
		optdepends(),
		unsatisfied_depends(),
		part_of_modpack(false),
		is_modpack(false),
		modpack_content()
	{}
};

// Retrieves depends, optdepends, is_modpack and modpack_content
void parseModContents(ModSpec &mod);

std::map<std::string,ModSpec> getModsInPath(std::string path, bool part_of_modpack = false);

// replaces modpack Modspecs with their content
std::vector<ModSpec> flattenMods(std::map<std::string,ModSpec> mods);

// a ModConfiguration is a subset of installed mods, expected to have
// all dependencies fullfilled, so it can be used as a list of mods to
// load when the game starts.
class ModConfiguration
{
public:
	// checks if all dependencies are fullfilled.
	bool isConsistent() const
	{
		return m_unsatisfied_mods.empty();
	}

	std::vector<ModSpec> getMods()
	{
		return m_sorted_mods;
	}

	const std::vector<ModSpec> &getUnsatisfiedMods() const
	{
		return m_unsatisfied_mods;
	}

	void printUnsatisfiedModsError() const;

protected:
	ModConfiguration(const std::string &worldpath);
	// adds all mods in the given path. used for games, modpacks
	// and world-specific mods (worldmods-folders)
	void addModsInPath(const std::string &path);

	// adds all mods in the set.
	void addMods(const std::vector<ModSpec> &new_mods);

	void addModsFormConfig(const std::string &settings_path, const std::set<std::string> &mods);

	void checkConflictsAndDeps();
private:
	// move mods from m_unsatisfied_mods to m_sorted_mods
	// in an order that satisfies dependencies
	void resolveDependencies();

	// mods with unmet dependencies. Before dependencies are resolved,
	// this is where all mods are stored. Afterwards this contains
	// only the ones with really unsatisfied dependencies.
	std::vector<ModSpec> m_unsatisfied_mods;

	// list of mods sorted such that they can be loaded in the
	// given order with all dependencies being fullfilled. I.e.,
	// every mod in this list has only dependencies on mods which
	// appear earlier in the vector.
	std::vector<ModSpec> m_sorted_mods;

	// set of mod names for which an unresolved name conflict
	// exists. A name conflict happens when two or more mods
	// at the same level have the same name but different paths.
	// Levels (mods in higher levels override mods in lower levels):
	// 1. game mod in modpack; 2. game mod;
	// 3. world mod in modpack; 4. world mod;
	// 5. addon mod in modpack; 6. addon mod.
	UNORDERED_SET<std::string> m_name_conflicts;

	// Deleted default constructor
	ModConfiguration() {}

};

class ServerModConfiguration: public ModConfiguration
{
public:
	ServerModConfiguration(const std::string &worldpath);

};

#ifndef SERVER
class ClientModConfiguration: public ModConfiguration
{
public:
	ClientModConfiguration(const std::string &path);
};
#endif

#if USE_CURL
Json::Value getModstoreUrl(const std::string &url);
#else
inline Json::Value getModstoreUrl(const std::string &url)
{
	return Json::Value();
}
#endif

struct ModLicenseInfo {
	int id;
	std::string shortinfo;
	std::string url;
};

struct ModAuthorInfo {
	int id;
	std::string username;
};

struct ModStoreMod {
	int id;
	std::string title;
	std::string basename;
	ModAuthorInfo author;
	float rating;
	bool valid;
};

struct ModStoreCategoryInfo {
	int id;
	std::string name;
};

struct ModStoreVersionEntry {
	int id;
	std::string date;
	std::string file;
	bool approved;
	//ugly version number
	int mtversion;
};

struct ModStoreTitlePic {
	int id;
	std::string file;
	std::string description;
	int mod;
};

struct ModStoreModDetails {
	/* version_set?? */
	std::vector<ModStoreCategoryInfo> categories;
	ModAuthorInfo author;
	ModLicenseInfo license;
	ModStoreTitlePic titlepic;
	int id;
	std::string title;
	std::string basename;
	std::string description;
	std::string repository;
	float rating;
	std::vector<std::string> depends;
	std::vector<std::string> softdeps;

	std::string download_url;
	std::string screenshot_url;
	std::vector<ModStoreVersionEntry> versions;
	bool valid;
};

class ModMetadata: public Metadata
{
public:
	ModMetadata(const std::string &mod_name);
	~ModMetadata() {}

	virtual void clear();

	bool save(const std::string &root_path);
	bool load(const std::string &root_path);

	bool isModified() const { return m_modified; }
	const std::string &getModName() const { return m_mod_name; }

	virtual bool setString(const std::string &name, const std::string &var);
private:
	std::string m_mod_name;
	bool m_modified;
};

#endif


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "nameidmapping.h"
#include "exceptions.h"
#include "util/serialize.h"

void NameIdMapping::serialize(std::ostream &os) const
{
	writeU8(os, 0); // version
	writeU16(os, m_id_to_name.size());
	for (UNORDERED_MAP<u16, std::string>::const_iterator i = m_id_to_name.begin();
			i != m_id_to_name.end(); ++i) {
		writeU16(os, i->first);
		os << serializeString(i->second);
	}
}

void NameIdMapping::deSerialize(std::istream &is)
{
	int version = readU8(is);
	if (version != 0)
		throw SerializationError("unsupported NameIdMapping version");
	u32 count = readU16(is);
	m_id_to_name.clear();
	m_name_to_id.clear();
	for (u32 i = 0; i < count; i++) {
		u16 id = readU16(is);
		std::string name = deSerializeString(is);
		m_id_to_name[id] = name;
		m_name_to_id[name] = id;
	}
}


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#ifndef NAMEIDMAPPING_HEADER
#define NAMEIDMAPPING_HEADER

#include <string>
#include <iostream>
#include <set>
#include "irrlichttypes_bloated.h"
#include "util/cpp11_container.h"

class NameIdMapping
{
public:
	void serialize(std::ostream &os) const;
	void deSerialize(std::istream &is);

	void clear()
	{
		m_id_to_name.clear();
		m_name_to_id.clear();
	}

	void set(u16 id, const std::string &name)
	{
		m_id_to_name[id] = name;
		m_name_to_id[name] = id;
	}
	void removeId(u16 id)
	{
		std::string name;
		bool found = getName(id, name);
		if (!found)
			return;
		m_id_to_name.erase(id);
		m_name_to_id.erase(name);
	}
	void eraseName(const std::string &name)
	{
		u16 id;
		bool found = getId(name, id);
		if (!found)
			return;
		m_id_to_name.erase(id);
		m_name_to_id.erase(name);
	}
	bool getName(u16 id, std::string &result) const
	{
		UNORDERED_MAP<u16, std::string>::const_iterator i;
		i = m_id_to_name.find(id);
		if (i == m_id_to_name.end())
			return false;
		result = i->second;
		return true;
	}
	bool getId(const std::string &name, u16 &result) const
	{
		UNORDERED_MAP<std::string, u16>::const_iterator i;
		i = m_name_to_id.find(name);
		if (i == m_name_to_id.end())
			return false;
		result = i->second;
		return true;
	}
	u16 size() const { return m_id_to_name.size(); }
private:
	UNORDERED_MAP<u16, std::string> m_id_to_name;
	UNORDERED_MAP<std::string, u16> m_name_to_id;
};

#endif


code:
set(common_network_SRCS
	${CMAKE_CURRENT_SOURCE_DIR}/connection.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/networkpacket.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/serverpackethandler.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/serveropcodes.cpp
	PARENT_SCOPE
)

if (BUILD_CLIENT)
	set(client_network_SRCS
		${CMAKE_CURRENT_SOURCE_DIR}/clientopcodes.cpp
		${CMAKE_CURRENT_SOURCE_DIR}/clientpackethandler.cpp
		PARENT_SCOPE
	)
endif()