class doing pathfinding More...

Collaboration diagram for Pathfinder:

Public Member Functions
	Pathfinder ()=delete

	Pathfinder (Map map, const NodeDefManager ndef)

	~Pathfinder ()

std::vector< v3s16 >	getPath (v3s16 source, v3s16 destination, unsigned int searchdistance, unsigned int max_jump, unsigned int max_drop, PathAlgorithm algo)
	path evaluation function

Private Member Functions
v3s16	getRealPos (v3s16 ipos)
	transform index pos to mappos

v3s16	getIndexPos (v3s16 pos)
	transform mappos to index pos

PathGridnode &	getIndexElement (v3s16 ipos)
	get gridnode at a specific index position

PathGridnode &	getIdxElem (s16 x, s16 y, s16 z)
	Get gridnode at a specific index position.

v3s16	invert (v3s16 pos)
	invert a 3D position (change sign of coordinates)

bool	isValidIndex (v3s16 index)
	check if an index is within current search area

int	getXZManhattanDist (v3s16 pos)
	calculate 2D Manhattan distance to target

PathCost	calcCost (v3s16 pos, v3s16 dir)
	calculate cost of movement

bool	updateAllCosts (v3s16 ipos, v3s16 srcdir, int current_cost, int level)
	recursive update whole search areas total cost information

bool	updateCostHeuristic (v3s16 isource, v3s16 idestination)
	try to find a path to destination using a heuristic function to estimate distance to target (A* search algorithm)

bool	buildPath (std::vector< v3s16 > &path, v3s16 ipos)
	build a vector containing all nodes from destination to source; to be called after the node costs have been processed

v3s16	walkDownwards (v3s16 pos, unsigned int max_down)
	go downwards from a position until some barrier is hit.

Private Attributes
int	m_max_index_x = 0
	max index of search area in x direction

int	m_max_index_y = 0
	max index of search area in y direction

int	m_max_index_z = 0
	max index of search area in z direction

int	m_maxdrop = 0
	maximum number of blocks a path may drop

int	m_maxjump = 0
	maximum number of blocks a path may jump

int	m_min_target_distance = 0
	current smalest path to target

bool	m_prefetch = true
	prefetch cost data

v3s16	m_start
	source position

v3s16	m_destination
	destination position

core::aabbox3d< s16 >	m_limits {{0, 0, 0}}
	position limits in real map coordinates

GridNodeContainer *	m_nodes_container = nullptr

Map *	m_map = nullptr

const NodeDefManager *	m_ndef = nullptr

Friends
class	GridNodeContainer
	contains all map data already collected and analyzed.

class	PathfinderCompareHeuristic

Detailed Description

class doing pathfinding

Constructor & Destructor Documentation

◆ Pathfinder() [1/2]

Pathfinder::Pathfinder ( )

delete

◆ Pathfinder() [2/2]

Pathfinder::Pathfinder	(	Map *	map,
		const NodeDefManager *	ndef )

inline

◆ ~Pathfinder()

Pathfinder::~Pathfinder ( )

References m_nodes_container.

Member Function Documentation

◆ buildPath()

bool Pathfinder::buildPath	(	std::vector< v3s16 > &	path,
		v3s16	ipos )

private

build a vector containing all nodes from destination to source; to be called after the node costs have been processed

Parameters

path	vector to add nodes to
ipos	initial pos to check (index pos)

Returns: true/false path has been fully built

References ERROR_TARGET, getIndexElement(), PathGridnode::is_element, PATHFINDER_MAX_WAYPOINTS, PathGridnode::source, PathGridnode::sourcedir, and PathGridnode::valid.

Referenced by getPath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calcCost()

PathCost Pathfinder::calcCost	(	v3s16	pos,
		v3s16	dir )

private

calculate cost of movement

Parameters

pos	real world position to start movement
dir	direction to move to

Returns: cost information

References CONTENT_IGNORE, DEBUG_OUT, dir(), NodeDefManager::get(), Map::getNode(), INFO_TARGET, m_limits, m_map, m_maxdrop, m_maxjump, m_ndef, MapNode::param0, PathCost::updated, PathCost::valid, PathCost::value, VERBOSE_TARGET, ContentFeatures::walkable, and PathCost::y_change.

Referenced by GridNodeContainer::initNode(), and updateCostHeuristic().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getIdxElem()

PathGridnode & Pathfinder::getIdxElem	(	s16	x,
		s16	y,
		s16	z )

inlineprivate

Get gridnode at a specific index position.

Returns: gridnode for index

References GridNodeContainer::access(), m_nodes_container, x, y, and z.

Here is the call graph for this function:

◆ getIndexElement()

PathGridnode & Pathfinder::getIndexElement ( v3s16 ipos )

private

get gridnode at a specific index position

Parameters

ipos	index position

Returns: gridnode for index

References GridNodeContainer::access(), and m_nodes_container.

Referenced by buildPath(), getPath(), PathfinderCompareHeuristic::operator()(), updateAllCosts(), and updateCostHeuristic().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getIndexPos()

v3s16 Pathfinder::getIndexPos ( v3s16 pos )

private

transform mappos to index pos

Parameters

pos	a real pos

Returns: index position

References m_limits.

Referenced by getPath(), PathfinderCompareHeuristic::operator()(), updateCostHeuristic(), and walkDownwards().

Here is the caller graph for this function:

◆ getPath()

std::vector< v3s16 > Pathfinder::getPath	(	v3s16	source,
		v3s16	destination,
		unsigned int	searchdistance,
		unsigned int	max_jump,
		unsigned int	max_drop,
		PathAlgorithm	algo )

path evaluation function

Parameters

env	environment to look for path
source	origin of path
destination	end position of path
searchdistance	maximum number of nodes to look in each direction
max_jump	maximum number of blocks a path may jump up
max_drop	maximum number of blocks a path may drop
algo	Algorithm to use for finding a path

References buildPath(), ERROR_TARGET, NodeDefManager::get(), getIndexElement(), getIndexPos(), Map::getNode(), getRealPos(), INFO_TARGET, m_destination, m_limits, m_map, m_max_index_x, m_max_index_y, m_max_index_z, m_maxdrop, m_maxjump, m_min_target_distance, m_ndef, m_nodes_container, m_prefetch, m_start, MYMAX, MYMIN, PA_DIJKSTRA, PA_PLAIN, PA_PLAIN_NP, PathGridnode::pos, PathGridnode::source, PathGridnode::target, PathGridnode::totalcost, updateAllCosts(), updateCostHeuristic(), PathGridnode::valid, VERBOSE_TARGET, ContentFeatures::walkable, and walkDownwards().

Referenced by get_path().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getRealPos()

v3s16 Pathfinder::getRealPos ( v3s16 ipos )

private

transform index pos to mappos

Parameters

ipos	an index position

Returns: map position

References m_limits.

Referenced by getPath(), GridNodeContainer::initNode(), updateCostHeuristic(), and walkDownwards().

Here is the caller graph for this function:

◆ getXZManhattanDist()

int Pathfinder::getXZManhattanDist ( v3s16 pos )

private

calculate 2D Manhattan distance to target

Parameters

pos	position to calc distance

Returns: integer distance

References m_destination, MYMAX, and MYMIN.

Referenced by updateCostHeuristic().

Here is the caller graph for this function:

◆ invert()

v3s16 Pathfinder::invert ( v3s16 pos )

private

invert a 3D position (change sign of coordinates)

Parameters

pos	3D position

Returns: pos *-1

Referenced by updateAllCosts(), and updateCostHeuristic().

Here is the caller graph for this function:

◆ isValidIndex()

bool Pathfinder::isValidIndex ( v3s16 index )

private

check if an index is within current search area

Parameters

index position to validate

Returns: true/false

References m_max_index_x, m_max_index_y, and m_max_index_z.

Referenced by updateAllCosts(), and updateCostHeuristic().

Here is the caller graph for this function:

◆ updateAllCosts()

bool Pathfinder::updateAllCosts	(	v3s16	ipos,
		v3s16	srcdir,
		int	current_cost,
		int	level )

private

recursive update whole search areas total cost information

Parameters

ipos	position to check next
srcdir	positionc checked last time
total_cost	cost of moving to ipos
level	current recursion depth

Returns: true/false path to destination has been found

References DEBUG_OUT, PathGridnode::getCost(), getIndexElement(), invert(), isValidIndex(), LVL, m_limits, m_min_target_distance, PathGridnode::sourcedir, PathGridnode::target, PathGridnode::totalcost, updateAllCosts(), PathCost::valid, PathGridnode::valid, PathCost::value, VERBOSE_TARGET, and PathCost::y_change.

Referenced by getPath(), and updateAllCosts().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ updateCostHeuristic()

bool Pathfinder::updateCostHeuristic	(	v3s16	isource,
		v3s16	idestination )

private

try to find a path to destination using a heuristic function to estimate distance to target (A* search algorithm)

Parameters

isource	start position (index pos)
idestination	end position (index pos)

Returns: true/false path to destination has been found

References calcCost(), DEBUG_OUT, PathGridnode::estimated_cost, PathGridnode::getCost(), getIndexElement(), getIndexPos(), getRealPos(), getXZManhattanDist(), invert(), PathGridnode::is_closed, PathGridnode::is_open, isValidIndex(), LVL, m_limits, PathfinderCompareHeuristic, PathGridnode::setCost(), PathGridnode::source, PathGridnode::sourcedir, PathGridnode::target, PathGridnode::totalcost, PathCost::updated, PathCost::valid, PathGridnode::valid, PathCost::value, and PathCost::y_change.

Referenced by getPath().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ walkDownwards()

v3s16 Pathfinder::walkDownwards	(	v3s16	pos,
		unsigned int	max_down )

private

go downwards from a position until some barrier is hit.

Parameters

pos	position from which to go downwards
max_down	maximum distance to go downwards

Returns: new position after movement; if too far down, pos is returned

References CONTENT_IGNORE, DEBUG_OUT, NodeDefManager::get(), getIndexPos(), Map::getNode(), getRealPos(), m_limits, m_map, m_ndef, MapNode::param0, VERBOSE_TARGET, and ContentFeatures::walkable.

Referenced by getPath().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Symbol Documentation

◆ GridNodeContainer

friend class GridNodeContainer

friend

contains all map data already collected and analyzed.

Access it via the getIndexElement/getIdxElem methods.

◆ PathfinderCompareHeuristic

friend class PathfinderCompareHeuristic

friend

Referenced by updateCostHeuristic().

Member Data Documentation

◆ m_destination

v3s16 Pathfinder::m_destination

private

destination position

Referenced by getPath(), and getXZManhattanDist().

◆ m_limits

core::aabbox3d<s16> Pathfinder::m_limits {{0, 0, 0}}

private

position limits in real map coordinates

Referenced by calcCost(), getIndexPos(), getPath(), getRealPos(), updateAllCosts(), updateCostHeuristic(), and walkDownwards().

◆ m_map

Map* Pathfinder::m_map = nullptr

private

Referenced by calcCost(), getPath(), GridNodeContainer::initNode(), and walkDownwards().

◆ m_max_index_x

int Pathfinder::m_max_index_x = 0

private

max index of search area in x direction

Referenced by getPath(), and isValidIndex().

◆ m_max_index_y

int Pathfinder::m_max_index_y = 0

private

max index of search area in y direction

Referenced by getPath(), and isValidIndex().

◆ m_max_index_z

int Pathfinder::m_max_index_z = 0

private

max index of search area in z direction

Referenced by getPath(), and isValidIndex().

◆ m_maxdrop

int Pathfinder::m_maxdrop = 0

private

maximum number of blocks a path may drop

Referenced by calcCost(), and getPath().

◆ m_maxjump

int Pathfinder::m_maxjump = 0

private

maximum number of blocks a path may jump

Referenced by calcCost(), and getPath().

◆ m_min_target_distance

int Pathfinder::m_min_target_distance = 0

private

current smalest path to target

Referenced by getPath(), and updateAllCosts().

◆ m_ndef

const NodeDefManager* Pathfinder::m_ndef = nullptr

private

Referenced by calcCost(), getPath(), GridNodeContainer::initNode(), and walkDownwards().

◆ m_nodes_container

GridNodeContainer* Pathfinder::m_nodes_container = nullptr

private

Referenced by ~Pathfinder(), getIdxElem(), getIndexElement(), and getPath().

◆ m_prefetch

bool Pathfinder::m_prefetch = true

private

prefetch cost data

Referenced by getPath(), and GridNodeContainer::initNode().

◆ m_start

v3s16 Pathfinder::m_start

private

source position

Referenced by getPath().

The documentation for this class was generated from the following file:

pathfinder.cpp

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Pathfinder() [1/2]

◆ Pathfinder() [2/2]

◆ ~Pathfinder()

Member Function Documentation

◆ buildPath()

◆ calcCost()

◆ getIdxElem()

◆ getIndexElement()

◆ getIndexPos()

◆ getPath()

◆ getRealPos()

◆ getXZManhattanDist()

◆ invert()

◆ isValidIndex()

◆ updateAllCosts()

◆ updateCostHeuristic()

◆ walkDownwards()

Friends And Related Symbol Documentation

◆ GridNodeContainer

◆ PathfinderCompareHeuristic

Member Data Documentation

◆ m_destination

◆ m_limits

◆ m_map

◆ m_max_index_x

◆ m_max_index_y

◆ m_max_index_z

◆ m_maxdrop

◆ m_maxjump

◆ m_min_target_distance

◆ m_ndef

◆ m_nodes_container

◆ m_prefetch

◆ m_start