Minetest 5.10.0-dev
 
Loading...
Searching...
No Matches
Pathfinder Class Reference

class doing pathfinding More...

+ Collaboration diagram for Pathfinder:

Public Member Functions

 Pathfinder ()=delete
 
 Pathfinder (Map *map, const NodeDefManager *ndef)
 
 ~Pathfinder ()
 
std::vector< v3s16getPath (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
 
PathGridnodegetIndexElement (v3s16 ipos)
 get gridnode at a specific index position
 
PathGridnodegetIdxElem (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
 position limits in real map coordinates

 
GridNodeContainerm_nodes_container = nullptr
 
Mapm_map = nullptr
 
const NodeDefManagerm_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
pathvector to add nodes to
iposinitial 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
posreal world position to start movement
dirdirection 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(), and m_nodes_container.

+ Here is the call graph for this function:

◆ getIndexElement()

PathGridnode & Pathfinder::getIndexElement ( v3s16 ipos)
private

get gridnode at a specific index position

Parameters
iposindex 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
posa 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
envenvironment to look for path
sourceorigin of path
destinationend position of path
searchdistancemaximum number of nodes to look in each direction
max_jumpmaximum number of blocks a path may jump up
max_dropmaximum number of blocks a path may drop
algoAlgorithm 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
iposan 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
posposition 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
pos3D 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
indexposition 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
iposposition to check next
srcdirpositionc checked last time
total_costcost of moving to ipos
levelcurrent 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
isourcestart position (index pos)
idestinationend 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
posposition from which to go downwards
max_downmaximum 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
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

◆ 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

◆ m_nodes_container

GridNodeContainer* Pathfinder::m_nodes_container = nullptr
private

◆ 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: