/src/

• ../
• CMakeLists.txt
• activeobject.h
• ban.cpp
• ban.h
• camera.cpp
• camera.h
• cavegen.cpp
• cavegen.h
• chat.cpp
• chat.h
• chat_interface.h
• chatmessage.h
• client.cpp
• client.h
• client
• clientenvironment.cpp
• clientenvironment.h
• clientiface.cpp
• clientiface.h
• clientmap.cpp
• clientmap.h
• clientmedia.cpp
• clientmedia.h
• clientobject.cpp
• clientobject.h
• clientsimpleobject.h
• cloudparams.h
• clouds.cpp
• clouds.h
• cmake_config.h.in
• cmake_config_githash.h.in
• collision.cpp
• collision.h
• config.h
• constants.h
• content_cao.cpp
• content_cao.h
• content_cso.cpp
• content_cso.h
• content_mapblock.cpp
• content_mapblock.h
• content_mapnode.cpp
• content_mapnode.h
• content_nodemeta.cpp
• content_nodemeta.h
• content_sao.cpp
• content_sao.h
• convert_json.cpp
• convert_json.h
• craftdef.cpp
• craftdef.h
• database-dummy.cpp
• database-dummy.h
• database-files.cpp
• database-files.h
• database-leveldb.cpp
• database-leveldb.h
• database-postgresql.cpp
• database-postgresql.h
• database-redis.cpp
• database-redis.h
• database-sqlite3.cpp
• database-sqlite3.h
• database.cpp
• database.h
• daynightratio.h
• debug.cpp
• debug.h
• defaultsettings.cpp
• defaultsettings.h
• dungeongen.cpp
• dungeongen.h
• emerge.cpp
• emerge.h
• environment.cpp
• environment.h
• event.h
• event_manager.h
• exceptions.h
• face_position_cache.cpp
• face_position_cache.h
• filecache.cpp
• filecache.h
• filesys.cpp
• filesys.h
• fontengine.cpp
• fontengine.h
• game.cpp
• game.h
• gamedef.h
• gameparams.h
• genericobject.cpp
• genericobject.h
• gettext.cpp
• gettext.h
• gettime.h
• guiChatConsole.cpp
• guiChatConsole.h
• guiEngine.cpp
• guiEngine.h
• guiFormSpecMenu.cpp
• guiFormSpecMenu.h
• guiKeyChangeMenu.cpp
• guiKeyChangeMenu.h
• guiMainMenu.h
• guiPasswordChange.cpp
• guiPasswordChange.h
• guiPathSelectMenu.cpp
• guiPathSelectMenu.h
• guiTable.cpp
• guiTable.h
• guiVolumeChange.cpp
• guiVolumeChange.h
• guiscalingfilter.cpp
• guiscalingfilter.h
• httpfetch.cpp
• httpfetch.h
• hud.cpp
• hud.h
• imagefilters.cpp
• imagefilters.h
• intlGUIEditBox.cpp
• intlGUIEditBox.h
• inventory.cpp
• inventory.h
• inventorymanager.cpp
• inventorymanager.h
• irr_aabb3d.h
• irr_v2d.h
• irr_v3d.h
• irrlicht_changes
• irrlichttypes.h
• irrlichttypes_bloated.h
• irrlichttypes_extrabloated.h
• itemdef.cpp
• itemdef.h
• itemgroup.h
• itemstackmetadata.cpp
• itemstackmetadata.h
• keycode.cpp
• keycode.h
• light.cpp
• light.h
• localplayer.cpp
• localplayer.h
• log.cpp
• log.h
• main.cpp
• mainmenumanager.h
• map.cpp
• map.h
• map_settings_manager.cpp
• map_settings_manager.h
• mapblock.cpp
• mapblock.h
• mapblock_mesh.cpp
• mapblock_mesh.h
• mapgen.cpp
• mapgen.h
• mapgen_carpathian.cpp
• mapgen_carpathian.h
• mapgen_flat.cpp
• mapgen_flat.h
• mapgen_fractal.cpp
• mapgen_fractal.h
• mapgen_singlenode.cpp
• mapgen_singlenode.h
• mapgen_v5.cpp
• mapgen_v5.h
• mapgen_v6.cpp
• mapgen_v6.h
• mapgen_v7.cpp
• mapgen_v7.h
• mapgen_valleys.cpp
• mapgen_valleys.h
• mapnode.cpp
• mapnode.h
• mapsector.cpp
• mapsector.h
• mesh.cpp
• mesh.h
• mesh_generator_thread.cpp
• mesh_generator_thread.h
• metadata.cpp
• metadata.h
• mg_biome.cpp
• mg_biome.h
• mg_decoration.cpp
• mg_decoration.h
• mg_ore.cpp
• mg_ore.h
• mg_schematic.cpp
• mg_schematic.h
• minimap.cpp
• minimap.h
• modalMenu.h
• modifiedstate.h
• mods.cpp
• mods.h
• nameidmapping.cpp
• nameidmapping.h
• network
• nodedef.cpp
• nodedef.h
• nodemetadata.cpp
• nodemetadata.h
• nodetimer.cpp
• nodetimer.h
• noise.cpp
• noise.h
• objdef.cpp
• objdef.h
• object_properties.cpp
• object_properties.h
• particles.cpp
• particles.h
• pathfinder.cpp
• pathfinder.h
• player.cpp
• player.h
• porting.cpp
• porting.h
• porting_android.cpp
• porting_android.h
• profiler.cpp
• profiler.h
• quicktune.cpp
• quicktune.h
• quicktune_shortcutter.h
• raycast.cpp
• raycast.h
• reflowscan.cpp
• reflowscan.h
• remoteplayer.cpp
• remoteplayer.h
• rollback.cpp
• rollback.h
• rollback_interface.cpp
• rollback_interface.h
• script
• serialization.cpp
• serialization.h
• server.cpp
• server.h
• serverenvironment.cpp
• serverenvironment.h
• serverlist.cpp
• serverlist.h
• serverobject.cpp
• serverobject.h
• settings.cpp
• settings.h
• settings_translation_file.cpp
• shader.cpp
• shader.h
• sky.cpp
• sky.h
• socket.cpp
• socket.h
• sound.cpp
• sound.h
• sound_openal.cpp
• sound_openal.h
• staticobject.cpp
• staticobject.h
• subgame.cpp
• subgame.h
• terminal_chat_console.cpp
• terminal_chat_console.h
• threading
• tileanimation.cpp
• tileanimation.h
• tool.cpp
• tool.h
• touchscreengui.cpp
• touchscreengui.h
• treegen.cpp
• treegen.h
• unittest
• util
• version.cpp
• version.h
• voxel.cpp
• voxel.h
• voxelalgorithms.cpp
• voxelalgorithms.h
• wieldmesh.cpp
• wieldmesh.h

/*
Minetest
Copyright (C) 2013 sapier, sapier at gmx dot net

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

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

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

/******************************************************************************/
/* Includes                                                                   */
/******************************************************************************/

#include "pathfinder.h"
#include "environment.h"
#include "map.h"
#include "log.h"

#ifdef PATHFINDER_DEBUG
#include <iomanip>
#endif
#ifdef PATHFINDER_CALC_TIME
	#include <sys/time.h>
#endif

/******************************************************************************/
/* Typedefs and macros                                                        */
/******************************************************************************/

//#define PATHFINDER_CALC_TIME

/** shortcut to print a 3d pos */
#define PPOS(pos) "(" << pos.X << "," << pos.Y << "," << pos.Z << ")"

#define LVL "(" << level << ")" <<

#ifdef PATHFINDER_DEBUG
#define DEBUG_OUT(a)     std::cout << a
#define INFO_TARGET      std::cout
#define VERBOSE_TARGET   std::cout
#define ERROR_TARGET     std::cout
#else
#define DEBUG_OUT(a)     while(0)
#define INFO_TARGET      infostream << "pathfinder: "
#define VERBOSE_TARGET   verbosestream << "pathfinder: "
#define ERROR_TARGET     errorstream << "pathfinder: "
#endif

/******************************************************************************/
/* implementation                                                             */
/******************************************************************************/

std::vector<v3s16> get_Path(ServerEnvironment* env,
							v3s16 source,
							v3s16 destination,
							unsigned int searchdistance,
							unsigned int max_jump,
							unsigned int max_drop,
							algorithm algo) {

	pathfinder searchclass;

	return searchclass.get_Path(env,
				source,destination,
				searchdistance,max_jump,max_drop,algo);
}

/******************************************************************************/
path_cost::path_cost()
:	valid(false),
	value(0),
	direction(0),
	updated(false)
{
	//intentionaly empty
}

/******************************************************************************/
path_cost::path_cost(const path_cost& b) {
	valid     = b.valid;
	direction = b.direction;
	value     = b.value;
	updated   = b.updated;
}

/******************************************************************************/
path_cost& path_cost::operator= (const path_cost& b) {
	valid     = b.valid;
	direction = b.direction;
	value     = b.value;
	updated   = b.updated;

	return *this;
}

/******************************************************************************/
path_gridnode::path_gridnode()
:	valid(false),
	target(false),
	source(false),
	totalcost(-1),
	sourcedir(v3s16(0,0,0)),
	surfaces(0),
	pos(v3s16(0,0,0)),
	is_element(false),
	type('u')
{
	//intentionaly empty
}

/******************************************************************************/
path_gridnode::path_gridnode(const path_gridnode& b)
:	valid(b.valid),
	target(b.target),
	source(b.source),
	totalcost(b.totalcost),
	sourcedir(b.sourcedir),
	surfaces(b.surfaces),
	pos(b.pos),
	is_element(b.is_element),
	type(b.type)
	{

	directions[DIR_XP] = b.directions[DIR_XP];
	directions[DIR_XM] = b.directions[DIR_XM];
	directions[DIR_ZP] = b.directions[DIR_ZP];
	directions[DIR_ZM] = b.directions[DIR_ZM];
}

/******************************************************************************/
path_gridnode& path_gridnode::operator= (const path_gridnode& b) {
	valid      = b.valid;
	target     = b.target;
	source     = b.source;
	is_element = b.is_element;
	totalcost  = b.totalcost;
	sourcedir  = b.sourcedir;
	surfaces   = b.surfaces;
	pos        = b.pos;
	type       = b.type;

	directions[DIR_XP] = b.directions[DIR_XP];
	directions[DIR_XM] = b.directions[DIR_XM];
	directions[DIR_ZP] = b.directions[DIR_ZP];
	directions[DIR_ZM] = b.directions[DIR_ZM];

	return *this;
}

/******************************************************************************/
path_cost path_gridnode::get_cost(v3s16 dir) {
	if (dir.X > 0) {
		return directions[DIR_XP];
	}
	if (dir.X < 0) {
		return directions[DIR_XM];
	}
	if (dir.Z > 0) {
		return directions[DIR_ZP];
	}
	if (dir.Z < 0) {
		return directions[DIR_ZM];
	}
	path_cost retval;
	return retval;
}

/******************************************************************************/
void path_gridnode::set_cost(v3s16 dir,path_cost cost) {
	if (dir.X > 0) {
		directions[DIR_XP] = cost;
	}
	if (dir.X < 0) {
		directions[DIR_XM] = cost;
	}
	if (dir.Z > 0) {
		directions[DIR_ZP] = cost;
	}
	if (dir.Z < 0) {
		directions[DIR_ZM] = cost;
	}
}

/******************************************************************************/
std::vector<v3s16> pathfinder::get_Path(ServerEnvironment* env,
							v3s16 source,
							v3s16 destination,
							unsigned int searchdistance,
							unsigned int max_jump,
							unsigned int max_drop,
							algorithm algo) {
#ifdef PATHFINDER_CALC_TIME
	timespec ts;
	clock_gettime(CLOCK_REALTIME, &ts);
#endif
	std::vector<v3s16> retval;

	//check parameters
	if (env == 0) {
		ERROR_TARGET << "missing environment pointer" << std::endl;
		return retval;
	}

	m_searchdistance = searchdistance;
	m_env = env;
	m_maxjump = max_jump;
	m_maxdrop = max_drop;
	m_start       = source;
	m_destination = destination;
	m_min_target_distance = -1;
	m_prefetch = true;

	if (algo == A_PLAIN_NP) {
		m_prefetch = false;
	}

	int min_x = MYMIN(source.X,destination.X);
	int max_x = MYMAX(source.X,destination.X);

	int min_y = MYMIN(source.Y,destination.Y);
	int max_y = MYMAX(source.Y,destination.Y);

	int min_z = MYMIN(source.Z,destination.Z);
	int max_z = MYMAX(source.Z,destination.Z);

	m_limits.X.min = min_x - searchdistance;
	m_limits.X.max = max_x + searchdistance;
	m_limits.Y.min = min_y - searchdistance;
	m_limits.Y.max = max_y + searchdistance;
	m_limits.Z.min = min_z - searchdistance;
	m_limits.Z.max = max_z + searchdistance;

	m_max_index_x = m_limits.X.max - m_limits.X.min;
	m_max_index_y = m_limits.Y.max - m_limits.Y.min;
	m_max_index_z = m_limits.Z.max - m_limits.Z.min;

	//build data map
	if (!build_costmap()) {
		ERROR_TARGET << "failed to build costmap" << std::endl;
		return retval;
	}
#ifdef PATHFINDER_DEBUG
	print_type();
	print_cost();
	print_ydir();
#endif

	//validate and mark start and end pos
	v3s16 StartIndex  = getIndexPos(source);
	v3s16 EndIndex    = getIndexPos(destination);

	path_gridnode& startpos = getIndexElement(StartIndex);
	path_gridnode& endpos   = getIndexElement(EndIndex);

	if (!startpos.valid) {
		VERBOSE_TARGET << "invalid startpos" <<
				"Index: " << PPOS(StartIndex) <<
				"Realpos: " << PPOS(getRealPos(StartIndex)) << std::endl;
		return retval;
	}
	if (!endpos.valid) {
		VERBOSE_TARGET << "invalid stoppos" <<
				"Index: " << PPOS(EndIndex) <<
				"Realpos: " << PPOS(getRealPos(EndIndex)) << std::endl;
		return retval;
	}

	endpos.target      = true;
	startpos.source    = true;
	startpos.totalcost = 0;

	bool update_cost_retval = false;

	switch (algo) {
		case DIJKSTRA:
			update_cost_retval = update_all_costs(StartIndex,v3s16(0,0,0),0,0);
			break;
		case A_PLAIN_NP:
		case A_PLAIN:
			update_cost_retval = update_cost_heuristic(StartIndex,v3s16(0,0,0),0,0);
			break;
		default:
			ERROR_TARGET << "missing algorithm"<< std::endl;
			break;
	}

	if (update_cost_retval) {

#ifdef PATHFINDER_DEBUG
		std::cout << "Path to target found!" << std::endl;
		print_pathlen();
#endif

		//find path
		std::vector<v3s16> path;
		build_path(path,EndIndex,0);

#ifdef PATHFINDER_DEBUG
		std::cout << "Full index path:" << std::endl;
		print_path(path);
#endif

		//finalize path
		std::vector<v3s16> full_path;
		for (std::vector<v3s16>::iterator i = path.begin();
					i != path.end(); ++i) {
			full_path.push_back(getIndexElement(*i).pos);
		}

#ifdef PATHFINDER_DEBUG
		std::cout << "full path:" << std::endl;
		print_path(full_path);
#endif
#ifdef PATHFINDER_CALC_TIME
		timespec ts2;
		clock_gettime(CLOCK_REALTIME, &ts2);

		int ms = (ts2.tv_nsec - ts.tv_nsec)/(1000*1000);
		int us = ((ts2.tv_nsec - ts.tv_nsec) - (ms*1000*1000))/1000;
		int ns = ((ts2.tv_nsec - ts.tv_nsec) - ( (ms*1000*1000) + (us*1000)));


		std::cout << "Calculating path took: " << (ts2.tv_sec - ts.tv_sec) <<
				"s " << ms << "ms " << us << "us " << ns << "ns " << std::endl;
#endif
		return full_path;
	}
	else {
#ifdef PATHFINDER_DEBUG
		print_pathlen();
#endif
		ERROR_TARGET << "failed to update cost map"<< std::endl;
	}


	//return
	return retval;
}

/******************************************************************************/
pathfinder::pathfinder() :
	m_max_index_x(0),
	m_max_index_y(0),
	m_max_index_z(0),
	m_searchdistance(0),
	m_maxdrop(0),
	m_maxjump(0),
	m_min_target_distance(0),
	m_prefetch(true),
	m_start(0,0,0),
	m_destination(0,0,0),
	m_limits(),
	m_data(),
	m_env(0)
{
	//intentionaly empty
}

/******************************************************************************/
v3s16 pathfinder::getRealPos(v3s16 ipos) {

	v3s16 retval = ipos;

	retval.X += m_limits.X.min;
	retval.Y += m_limits.Y.min;
	retval.Z += m_limits.Z.min;

	return retval;
}

/******************************************************************************/
bool pathfinder::build_costmap()
{
	INFO_TARGET << "Pathfinder build costmap: (" << m_limits.X.min << ","
												<< m_limits.Z.min << ") ("
												<< m_limits.X.max << ","
												<< m_limits.Z.max << ")"
												<< std::endl;
	m_data.resize(m_max_index_x);
	for (int x = 0; x < m_max_index_x; x++) {
		m_data[x].resize(m_max_index_z);
		for (int z = 0; z < m_max_index_z; z++) {
			m_data[x][z].resize(m_max_index_y);

			int surfaces = 0;
			for (int y = 0; y < m_max_index_y; y++) {
				v3s16 ipos(x,y,z);

				v3s16 realpos = getRealPos(ipos);

				MapNode current = m_env->getMap().getNodeNoEx(realpos);
				MapNode below   = m_env->getMap().getNodeNoEx(realpos + v3s16(0,-1,0));


				if ((current.param0 == CONTENT_IGNORE) ||
						(below.param0 == CONTENT_IGNORE)) {
					DEBUG_OUT("Pathfinder: " << PPOS(realpos) <<
							" current or below is invalid element" << std::endl);
					if (current.param0 == CONTENT_IGNORE) {
						m_data[x][z][y].type = 'i';
						DEBUG_OUT(x << "," << y << "," << z << ": " << 'i' << std::endl);
					}
					continue;
				}

				//don't add anything if it isn't an air node
				if ((current.param0 != CONTENT_AIR) ||
						(below.param0 == CONTENT_AIR )) {
						DEBUG_OUT("Pathfinder: " << PPOS(realpos)
								<< " not on surface" << std::endl);
						if (current.param0 != CONTENT_AIR) {
							m_data[x][z][y].type = 's';
							DEBUG_OUT(x << "," << y << "," << z << ": " << 's' << std::endl);
						}
						else {
							m_data[x][z][y].type   = '-';
							DEBUG_OUT(x << "," << y << "," << z << ": " << '-' << std::endl);
						}
						continue;
				}

				surfaces++;

				m_data[x][z][y].valid  = true;
				m_data[x][z][y].pos    = realpos;
				m_data[x][z][y].type   = 'g';
				DEBUG_OUT(x << "," << y << "," << z << ": " << 'a' << std::endl);

				if (m_prefetch) {
				m_data[x][z][y].directions[DIR_XP] =
											calc_cost(realpos,v3s16( 1,0, 0));
				m_data[x][z][y].directions[DIR_XM] =
											calc_cost(realpos,v3s16(-1,0, 0));
				m_data[x][z][y].directions[DIR_ZP] =
											calc_cost(realpos,v3s16( 0,0, 1));
				m_data[x][z][y].directions[DIR_ZM] =
											calc_cost(realpos,v3s16( 0,0,-1));
				}

			}

			if (surfaces >= 1 ) {
				for (int y = 0; y < m_max_index_y; y++) {
					if (m_data[x][z][y].valid) {
						m_data[x][z][y].surfaces = surfaces;
					}
				}
			}
		}
	}
	return true;
}

/******************************************************************************/
path_cost pathfinder::calc_cost(v3s16 pos,v3s16 dir) {
	path_cost retval;

	retval.updated = true;

	v3s16 pos2 = pos + dir;

	//check limits
	if (    (pos2.X < m_limits.X.min) ||
			(pos2.X >= m_limits.X.max) ||
			(pos2.Z < m_limits.Z.min) ||
			(pos2.Z >= m_limits.Z.max)) {
		DEBUG_OUT("Pathfinder: " << PPOS(pos2) <<
				" no cost -> out of limits" << std::endl);
		return retval;
	}

	MapNode node_at_pos2 = m_env->getMap().getNodeNoEx(pos2);

	//did we get information about node?
	if (node_at_pos2.param0 == CONTENT_IGNORE ) {
			VERBOSE_TARGET << "Pathfinder: (1) area at pos: "
					<< PPOS(pos2) << " not loaded";
			return retval;
	}

	if (node_at_pos2.param0 == CONTENT_AIR) {
		MapNode node_below_pos2 =
							m_env->getMap().getNodeNoEx(pos2 + v3s16(0,-1,0));

		//did we get information about node?
		if (node_below_pos2.param0 == CONTENT_IGNORE ) {
				VERBOSE_TARGET << "Pathfinder: (2) area at pos: "
					<< PPOS((pos2 + v3s16(0,-1,0))) << " not loaded";
				return retval;
		}

		if (node_below_pos2.param0 != CONTENT_AIR) {
			retval.valid = true;
			retval.value = 1;
			retval.direction = 0;
			DEBUG_OUT("Pathfinder: "<< PPOS(pos)
					<< " cost same height found" << std::endl);
		}
		else {
			v3s16 testpos = pos2 - v3s16(0,-1,0);
			MapNode node_at_pos = m_env->getMap().getNodeNoEx(testpos);

			while ((node_at_pos.param0 != CONTENT_IGNORE) &&
					(node_at_pos.param0 == CONTENT_AIR) &&
					(testpos.Y > m_limits.Y.min)) {
				testpos += v3s16(0,-1,0);
				node_at_pos = m_env->getMap().getNodeNoEx(testpos);
			}

			//did we find surface?
			if ((testpos.Y >= m_limits.Y.min) &&
					(node_at_pos.param0 != CONTENT_IGNORE) &&
					(node_at_pos.param0 != CONTENT_AIR)) {
				if ((pos2.Y - testpos.Y - 1) <= m_maxdrop) {
					retval.valid = true;
					retval.value = 2;
					//difference of y-pos +1 (target node is ABOVE solid node)
					retval.direction = ((testpos.Y - pos2.Y) +1);
					DEBUG_OUT("Pathfinder cost below height found" << std::endl);
				}
				else {
					INFO_TARGET << "Pathfinder:"
							" distance to surface below to big: "
							<< (testpos.Y - pos2.Y) << " max: " << m_maxdrop
							<< std::endl;
				}
			}
			else {
				DEBUG_OUT("Pathfinder: no surface below found" << std::endl);
			}
		}
	}
	else {
		v3s16 testpos = pos2;
		MapNode node_at_pos = m_env->getMap().getNodeNoEx(testpos);

		while ((node_at_pos.param0 != CONTENT_IGNORE) &&
				(node_at_pos.param0 != CONTENT_AIR) &&
				(testpos.Y < m_limits.Y.max)) {
			testpos += v3s16(0,1,0);
			node_at_pos = m_env->getMap().getNodeNoEx(testpos);
		}

		//did we find surface?
		if ((testpos.Y <= m_limits.Y.max) &&
				(node_at_pos.param0 == CONTENT_AIR)) {

			if (testpos.Y - pos2.Y <= m_maxjump) {
				retval.valid = true;
				retval.value = 2;
				retval.direction = (testpos.Y - pos2.Y);
				DEBUG_OUT("Pathfinder cost above found" << std::endl);
			}
			else {
				DEBUG_OUT("Pathfinder: distance to surface above to big: "
						<< (testpos.Y - pos2.Y) << " max: " << m_maxjump
						<< std::endl);
			}
		}
		else {
			DEBUG_OUT("Pathfinder: no surface above found" << std::endl);
		}
	}
	return retval;
}

/******************************************************************************/
v3s16 pathfinder::getIndexPos(v3s16 pos) {

	v3s16 retval = pos;
	retval.X -= m_limits.X.min;
	retval.Y -= m_limits.Y.min;
	retval.Z -= m_limits.Z.min;

	return retval;
}

/******************************************************************************/
path_gridnode& pathfinder::getIndexElement(v3s16 ipos) {
	return m_data[ipos.X][ipos.Z][ipos.Y];
}

/******************************************************************************/
bool pathfinder::valid_index(v3s16 index) {
	if (	(index.X < m_max_index_x) &&
			(index.Y < m_max_index_y) &&