src/main.cpp

/*
Minetest-c55
Copyright (C) 2010 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 General Public License as published by
the Free Software Foundation; either version 2 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 General Public License for more details.

You should have received a copy of the GNU 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 "voxel.h"
#include "map.h"

// For TimeTaker
#include "utility.h"
#include "gettime.h"

/*
	Debug stuff
*/
u32 addarea_time = 0;
u32 emerge_time = 0;
u32 emerge_load_time = 0;
u32 clearflag_time = 0;
//u32 getwaterpressure_time = 0;
//u32 spreadwaterpressure_time = 0;
u32 updateareawaterpressure_time = 0;
u32 flowwater_pre_time = 0;


VoxelManipulator::VoxelManipulator():
	m_data(NULL),
	m_flags(NULL)
{
}

VoxelManipulator::~VoxelManipulator()
{
	clear();
	if(m_data)
		delete[] m_data;
	if(m_flags)
		delete[] m_flags;
}

void VoxelManipulator::clear()
{
	// Reset area to volume=0
	m_area = VoxelArea();
	if(m_data)
		delete[] m_data;
	m_data = NULL;
	if(m_flags)
		delete[] m_flags;
	m_flags = NULL;
}

void VoxelManipulator::print(std::ostream &o, VoxelPrintMode mode)
{
	v3s16 em = m_area.getExtent();
	v3s16 of = m_area.MinEdge;
	o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
	 <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
	
	for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
	{
		if(em.X >= 3 && em.Y >= 3)
		{
			if     (y==m_area.MinEdge.Y+2) o<<"^     ";
			else if(y==m_area.MinEdge.Y+1) o<<"|     ";
			else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
			else                           o<<"      ";
		}

		for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
		{
			for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
			{
				u8 f = m_flags[m_area.index(x,y,z)];
				char c;
				if(f & VOXELFLAG_NOT_LOADED)
					c = 'N';
				else if(f & VOXELFLAG_INEXISTENT)
					c = 'I';
				else
				{
					c = 'X';
					u8 m = m_data[m_area.index(x,y,z)].d;
					u8 pr = m_data[m_area.index(x,y,z)].param2;
					if(mode == VOXELPRINT_MATERIAL)
					{
						if(m <= 9)
							c = m + '0';
					}
					else if(mode == VOXELPRINT_WATERPRESSURE)
					{
						if(m == CONTENT_WATER)
						{
							c = 'w';
							if(pr <= 9)
								c = pr + '0';
						}
						else if(m == CONTENT_AIR)
						{
							c = ' ';
						}
						else
						{
							c = '#';
						}
					}
				}
				o<<c;
			}
			o<<' ';
		}
		o<<std::endl;
	}
}

void VoxelManipulator::addArea(VoxelArea area)
{
	// Cancel if requested area has zero volume
	if(area.getExtent() == v3s16(0,0,0))
		return;
	
	// Cancel if m_area already contains the requested area
	if(m_area.contains(area))
		return;
	
	TimeTaker timer("addArea", &addarea_time);

	// Calculate new area
	VoxelArea new_area;
	// New area is the requested area if m_area has zero volume
	if(m_area.getExtent() == v3s16(0,0,0))
	{
		new_area = area;
	}
	// Else add requested area to m_area
	else
	{
		new_area = m_area;
		new_area.addArea(area);
	}

	s32 new_size = new_area.getVolume();

	/*dstream<<"adding area ";
	area.print(dstream);
	dstream<<", old area ";
	m_area.print(dstream);
	dstream<<", new area ";
	new_area.print(dstream);
	dstream<<", new_size="<<new_size;
	dstream<<std::endl;*/

	// Allocate and clear new data
	MapNode *new_data = new MapNode[new_size];
	u8 *new_flags = new u8[new_size];
	for(s32 i=0; i<new_size; i++)
	{
		new_flags[i] = VOXELFLAG_NOT_LOADED;
	}
	
	// Copy old data
	
	for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
	for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
	for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
	{
		// If loaded, copy data and flags
		if((m_flags[m_area.index(x,y,z)] & VOXELFLAG_NOT_LOADED) == false)
		{
			new_data[new_area.index(x,y,z)] = m_data[m_area.index(x,y,z)];
			new_flags[new_area.index(x,y,z)] = m_flags[m_area.index(x,y,z)];
		}
	}

	// Replace area, data and flags
	
	m_area = new_area;
	
	MapNode *old_data = m_data;
	u8 *old_flags = m_flags;

	/*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
	<<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/

	m_data = new_data;
	m_flags = new_flags;
	
	if(old_data)
		delete[] old_data;
	if(old_flags)
		delete[] old_flags;

	//dstream<<"addArea done"<<std::endl;
}

void VoxelManipulator::copyFrom(MapNode *src, VoxelArea src_area,
		v3s16 from_pos, v3s16 to_pos, v3s16 size)
{
	for(s16 z=0; z<size.Z; z++)
	for(s16 y=0; y<size.Y; y++)
	{
		s32 i_src = src_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
		s32 i_local = m_area.index(to_pos.X, to_pos.Y+y, to_pos.Z+z);
		memcpy(&m_data[i_local], &src[i_src], size.X*sizeof(MapNode));
		memset(&m_flags[i_local], 0, size.X);
	}
}

void VoxelManipulator::copyTo(MapNode *dst, VoxelArea dst_area,
		v3s16 dst_pos, v3s16 from_pos, v3s16 size)
{
	for(s16 z=0; z<size.Z; z++)
	for(s16 y=0; y<size.Y; y++)
	{
		s32 i_dst = dst_area.index(dst_pos.X, dst_pos.Y+y, dst_pos.Z+z);
		s32 i_local = m_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
		memcpy(&dst[i_dst], &m_data[i_local], size.X*sizeof(MapNode));
	}
}

/*
	Algorithms
	-----------------------------------------------------
*/

void VoxelManipulator::clearFlag(u8 flags)
{
	// 0-1ms on moderate area
	TimeTaker timer("clearFlag", &clearflag_time);

	v3s16 s = m_area.getExtent();

	/*dstream<<"clearFlag clearing area of size "
			<<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
			<<std::endl;*/

	//s32 count = 0;

	/*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
	for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
	for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
	{
		u8 f = m_flags[m_area.index(x,y,z)];
		m_flags[m_area.index(x,y,z)] &= ~flags;
		if(m_flags[m_area.index(x,y,z)] != f)
			count++;
	}*/

	s32 volume = m_area.getVolume();
	for(s32 i=0; i<volume; i++)
	{
		m_flags[i] &= ~flags;
	}

	/*s32 volume = m_area.getVolume();
	for(s32 i=0; i<volume; i++)
	{
		u8 f = m_flags[i];
		m_flags[i] &= ~flags;
		if(m_flags[i] != f)
			count++;
	}

	dstream<<"clearFlag changed "<<count<<" flags out of "
			<<volume<<" nodes"<<std::endl;*/
}

void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
		core::map<v3s16, bool> & light_sources)
{
	v3s16 dirs[6] = {
		v3s16(0,0,1), // back
		v3s16(0,1,0), // top
		v3s16(1,0,0), // right
		v3s16(0,0,-1), // front
		v3s16(0,-1,0), // bottom
		v3s16(-1,0,0), // left
	};
	
	emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));

	// Loop through 6 neighbors
	for(u16 i=0; i<6; i++)
	{
		// Get the position of the neighbor node
		v3s16 n2pos = p + dirs[i];
		
		u32 n2i = m_area.index(n2pos);

		if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
			continue;

		MapNode &n2 = m_data[n2i];
		
		/*
			If the neighbor is dimmer than what was specified
			as oldlight (the light of the previous node)
		*/
		if(n2.getLight(bank) < oldlight)
		{
			/*
				And the neighbor is transparent and it has some light
			*/
			if(n2.light_propagates() && n2.getLight(bank) != 0)
			{
				/*
					Set light to 0 and add to queue
				*/

				u8 current_light = n2.getLight(bank);
				n2.setLight(bank, 0);
				
				unspreadLight(bank, n2pos, current_light, light_sources);
				
				/*
					Remove from light_sources if it is there
					NOTE: This doesn't happen nearly at all
				*/
				/*if(light_sources.find(n2pos))
				{
					std::cout<<"Removed from light_sources"<<std::endl;
					light_sources.remove(n2pos);
				}*/
			}
		}
		else{
			light_sources.insert(n2pos, true);
		}
	}
}

#if 1
/*
	Goes recursively through the neighbours of the node.

	Alters only transparent nodes.

	If the lighting of the neighbour is lower than the lighting of
	the node was (before changing it to 0 at the step before), the
	lighting of the neighbour is set to 0 and then the same stuff
	repeats for the neighbour.

	The ending nodes of the routine are stored in light_sources.
	This is useful when a light is removed. In such case, this
	routine can be called for the light node and then again for
	light_sources to re-light the area without the removed light.

	values of from_nodes are lighting values.
*/
void VoxelManipulator::unspreadLight(enum LightBank bank,
		core::map<v3s16, u8> & from_nodes,
		core::map<v3s16, bool> & light_sources)
{
	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, u8>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();
		
		//MapNode &n = m_data[m_area.index(pos)];
		
		u8 oldlight = j.getNode()->getValue();

		unspreadLight(bank, pos, oldlight, light_sources);
	}
}
#endif

#if 0
/*
	Goes recursively through the neighbours of the node.

	Alters only transparent nodes.

	If the lighting of the neighbour is lower than the lighting of
	the node was (before changing it to 0 at the step before), the
	lighting of the neighbour is set to 0 and then the same stuff
	repeats for the neighbour.

	The ending nodes of the routine are stored in light_sources.
	This is useful when a light is removed. In such case, this
	routine can be called for the light node and then again for
	light_sources to re-light the area without the removed light.

	values of from_nodes are lighting values.
*/
void VoxelManipulator::unspreadLight(enum LightBank bank,
		core::map<v3s16, u8> & from_nodes,
		core::map<v3s16, bool> & light_sources)
{
	v3s16 dirs[6] = {
		v3s16(0,0,1), // back
		v3s16(0,1,0), // top
		v3s16(1,0,0), // right
		v3s16(0,0,-1), // front
		v3s16(0,-1,0), // bottom
		v3s16(-1,0,0), // left
	};
	
	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, u8> unlighted_nodes;
	core::map<v3s16, u8>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();
		
		emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));

		//MapNode &n = m_data[m_area.index(pos)];
		
		u8 oldlight = j.getNode()->getValue();
		
		// Loop through 6 neighbors
		for(u16 i=0; i<6; i++)
		{
			// Get the position of the neighbor node
			v3s16 n2pos = pos + dirs[i];
			
			u32 n2i = m_area.index(n2pos);

			if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
				continue;

			MapNode &n2 = m_data[n2i];
			
			/*
				If the neighbor is dimmer than what was specified
				as oldlight (the light of the previous node)
			*/
			if(n2.getLight(bank) < oldlight)
			{
				/*
					And the neighbor is transparent and it has some light
				*/
				if(n2.light_propagates() && n2.getLight(bank) != 0)
				{
					/*
						Set light to 0 and add to queue
					*/

					u8 current_light = n2.getLight(bank);
					n2.setLight(bank, 0);

					unlighted_nodes.insert(n2pos, current_light);
					
					/*
						Remove from light_sources if it is there
						NOTE: This doesn't happen nearly at all
					*/
					/*if(light_sources.find(n2pos))
					{
						std::cout<<"Removed from light_sources"<<std::endl;
						light_sources.remove(n2pos);
					}*/
				}
			}
			else{
				light_sources.insert(n2pos, true);
			}
		}
	}

	/*dstream<<"unspreadLight(): Changed block "
			<<blockchangecount<<" times"
			<<" for "<<from_nodes.size()<<" nodes"
			<<std::endl;*/
	
	if(unlighted_nodes.size() > 0)
		unspreadLight(bank, unlighted_nodes, light_sources);
}
#endif

void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p)
{
	const v3s16 dirs[6] = {
		v3s16(0,0,1), // back
		v3s16(0,1,0), // top
		v3s16(1,0,0), // right
		v3s16(0,0,-1), // front
		v3s16(0,-1,0), // bottom
		v3s16(-1,0,0), // left
	};

	emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));

	u32 i = m_area.index(p);
	
	if(m_flags[i] & VOXELFLAG_INEXISTENT)
		return;

	MapNode &n = m_data[i];

	u8 oldlight = n.getLight(bank);
	u8 newlight = diminish_light(oldlight);

	// Loop through 6 neighbors
	for(u16 i=0; i<6; i++)
	{
		// Get the position of the neighbor node
		v3s16 n2pos = p + dirs[i];
		
		u32 n2i = m_area.index(n2pos);

		if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
			continue;

		MapNode &n2 = m_data[n2i];
		
		/*
			If the neighbor is brighter than the current node,
			add to list (it will light up this node on its turn)
		*/
		if(n2.getLight(bank) > undiminish_light(oldlight))
		{
			spreadLight(bank, n2pos);
		}
		/*
			If the neighbor is dimmer than how much light this node
			would spread on it, add to list
		*/
		if(n2.getLight(bank) < newlight)
		{
			if(n2.light_propagates())
			{
				n2.setLight(bank, newlight);
				spreadLight(bank, n2pos);
			}
		}
	}
}

#if 0
/*
	Lights neighbors of from_nodes, collects all them and then
	goes on recursively.

	NOTE: This is faster on small areas but will overflow the
	      stack on large areas. Thus it is not used.
*/
void VoxelManipulator::spreadLight(enum LightBank bank,
		core::map<v3s16, bool> & from_nodes)
{
	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, bool> lighted_nodes;
	core::map<v3s16, bool>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();

		spreadLight(bank, pos);
	}
}
#endif

#if 1
/*
	Lights neighbors of from_nodes, collects all them and then
	goes on recursively.
*/
void VoxelManipulator::spreadLight(enum LightBank bank,
		core::map<v3s16, bool> & from_nodes)
{
	const v3s16 dirs[6] = {
		v3s16(0,0,1), // back
		v3s16(0,1,0), // top
		v3s16(1,0,0), // right
		v3s16(0,0,-1), // front
		v3s16(0,-1,0), // bottom
		v3s16(-1,0,0), // left
	};

	if(from_nodes.size() == 0)
		return;
	
	core::map<v3s16, bool> lighted_nodes;
	core::map<v3s16, bool>::Iterator j;
	j = from_nodes.getIterator();

	for(; j.atEnd() == false; j++)
	{
		v3s16 pos = j.getNode()->getKey();

		emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));

		u32 i = m_area.index(pos);
		
		if(m_flags[i] & VOXELFLAG_INEXISTENT)
			continue;

		MapNode &n = m_data[i];

		u8 oldlight = n.getLight(bank);
		u8 newlight = diminish_light(oldlight);

		// Loop through 6 neighbors
		for(u16 i=0; i<6; i++)
		{
			// Get the position of the neighbor node
			v3s16 n2pos = pos + dirs[i];
			
			try
			{
				u32 n2i = m_area.index(n2pos);

				if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
					continue;

				MapNode &n2 = m_data[n2i];
				
				/*
					If the neighbor is brighter than the current node,
					add to list (it will light up this node on its turn)
				*/
				if(n2.getLight(bank) > undiminish_light(oldlight))
				{
					lighted_nodes.insert(n2pos, true);
				}
				/*
					If the neighbor is dimmer than how much light this node
					would spread on it, add to list
				*/
				if(n2.getLight(bank) < newlight)
				{
					if(n2.light_propagates())
					{
						n2.setLight(bank, newlight);
						lighted_nodes.insert(n2pos, true);
					}
				}
			}
			catch(InvalidPositionException &e)
			{
				continue;
			}
		}
	}

	/*dstream<<"spreadLight(): Changed block "
			<<blockchangecount<<" times"
			<<" for "<<from_nodes.size()<<" nodes"
			<<std::endl;*/
	
	if(lighted_nodes.size() > 0)
		spreadLight(bank, lighted_nodes);
}
#endif

//END
	Commit message (Expand)	Author	Age
*	Revert the upper-case PROJECT_NAME nonsense that was part of #2402	sfan5	2015-04-27
*	Tests: Modularize unit testing	kwolekr	2015-04-26
*	Move globals from main.cpp to more sane locations	Craig Robbins	2015-04-01
*	Clean up and tweak build system	ShadowNinja	2015-03-27
*	For usages of assert() that are meant to persist in Release builds (when NDEB...	Craig Robbins	2015-03-07
*	Don't start a server for map migration	ShadowNinja	2015-03-06
*	Clean up database API and save the local map on an interval	ShadowNinja	2015-03-06
*	Rename --do-unittests to --run-unittests as @Zeno- and @sfan5 requested	Loic Blot	2015-02-24
*	Unit tests must be done at integration process.	Loic Blot	2015-02-21
*	Replace std::list by std::vector into ServerMap::listAllLoadableBlocks Server...	Loic Blot	2015-02-17
*	main.cpp rework * Move ClientLauncher class to a dedicated file * ClientLaunc...	Loic Blot	2015-02-12
*	Small changes in the style of controls	ngosang	2015-02-12
*	Reduce gettext wide/narrow and string/char* conversions	ShadowNinja	2015-02-05
*	Create minidump on fatal Win32 exceptions	kwolekr	2015-02-02
*	Reorganize supported video driver query mechanisms	kwolekr	2015-01-18
*	Performance fixes.	onkrot	2015-01-13
*	Skip further loading of client if there was an exit signal	Christophe Piveteau	2014-12-28
*	Set WM_CLASS window hint for Xorg	kwolekr	2014-12-15
*	Fix misleading error when exiting the client from the main menu	Craig Robbins	2014-12-14
*	Provide more info if a subgame is not valid/found	Craig Robbins	2014-12-13
*	Make hud use fontengine too	sapier	2014-11-30
*	Implement proper font handling	sapier	2014-11-30
*	Fix MSVC compiling error (argc/argv not available to pass to init_gettext)	SmallJoker	2014-11-29
*	Fix regression with command line --go option	Craig Robbins	2014-11-28
*	Fix Android main menu crash, and user data directory check.	Kodexky	2014-11-26
*	Fix regression with USE_REDIS (refactor_main)	Craig Robbins	2014-11-23
*	refactor main.cpp	Craig Robbins	2014-11-23
*	Refactor the_game() to make it more understandable and maintainable.	Craig Robbins	2014-11-02
*	Add video driver selection to settings menu (based uppon idea from webdesigne...	sapier	2014-08-23
*	Fix to to too two times	sapier	2014-08-22
*	Add player name length checks	sapier	2014-08-22
*	Move MapBlock (de)serializing code out of Database class	sfan5	2014-07-12
*	Fix warnings reported by clang	sfan5	2014-07-06
*	Add support for Android 2.3+	sapier	2014-06-29
*	Support for scalable font and gui elements	sapier	2014-06-22
*	Add support for directly starting a world by name from command line	sapier	2014-06-19
*	Codestyle cleanup (main.cpp)	BlockMen	2014-06-01
*	Revert "Add daemon support for linux like operating systems"	sapier	2014-06-01
*	Add daemon support for linux like operating systems	sapier	2014-05-31
*	Map irrlicht log level to minetest. Allow write them to debug file.	RealBadAngel	2014-05-14
*	Add support for dpi based HUD scaling	sapier	2014-04-27
*	Fix chat console not working anymore	sapier	2014-04-20
*	Bunch of small fixes (coding style, very unlikely errors, warning messages)	sapier	2014-04-19
*	Add redis database backend	Sfan5	2014-04-16
*	Fix all warnings reported by clang	Sfan5	2014-04-15
*	Infer ipv6_server from bind_address; fix client connect to IN(6)ADDR_ANY	Kahrl	2014-04-10
*	Replace pause and message menu by formspec ones	sapier	2014-03-05
*	Fix memory leak in database migration	Selat	2014-02-07
*	Add the option to bind to a specific address	ShadowNinja	2014-02-05
*	Revert "Fix settings to honor numeric conversion errors"	kwolekr	2014-02-05