+/** representation of cost in specific direction */
+class PathCost {
+public:
+
+ /** default constructor */
+ PathCost() = default;
+
+ /** copy constructor */
+ PathCost(const PathCost &b);
+
+ /** assignment operator */
+ PathCost &operator= (const PathCost &b);
+
+ bool valid = false; /**< movement is possible */
+ int value = 0; /**< cost of movement */
+ int y_change = 0; /**< change of y position of movement */
+ bool updated = false; /**< this cost has ben calculated */
+
+};
+
+
+/** representation of a mapnode to be used for pathfinding */
+class PathGridnode {
+
+public:
+ /** default constructor */
+ PathGridnode() = default;
+
+ /** copy constructor */
+ PathGridnode(const PathGridnode &b);
+
+ /**
+ * assignment operator
+ * @param b node to copy
+ */
+ PathGridnode &operator= (const PathGridnode &b);
+
+ /**
+ * read cost in a specific direction
+ * @param dir direction of cost to fetch
+ */
+ PathCost getCost(v3s16 dir);
+
+ /**
+ * set cost value for movement
+ * @param dir direction to set cost for
+ * @cost cost to set
+ */
+ void setCost(v3s16 dir, const PathCost &cost);
+
+ bool valid = false; /**< node is on surface */
+ bool target = false; /**< node is target position */
+ bool source = false; /**< node is stating position */
+ int totalcost = -1; /**< cost to move here from starting point */
+ int estimated_cost = -1; /**< totalcost + heuristic cost to end */
+ v3s16 sourcedir; /**< origin of movement for current cost */
+ v3s16 pos; /**< real position of node */
+ PathCost directions[4]; /**< cost in different directions */
+ bool is_closed = false; /**< for A* search: if true, is in closed list */
+ bool is_open = false; /**< for A* search: if true, is in open list */
+
+ /* debug values */
+ bool is_element = false; /**< node is element of path detected */
+ char type = 'u'; /**< Type of pathfinding node.
+ * u = unknown
+ * i = invalid
+ * s = surface (walkable node)
+ * - = non-walkable node (e.g. air) above surface
+ * g = other non-walkable node
+ */
+};
+
+class Pathfinder;
+class PathfinderCompareHeuristic;
+
+/** Abstract class to manage the map data */
+class GridNodeContainer {
+public:
+ virtual PathGridnode &access(v3s16 p)=0;
+ virtual ~GridNodeContainer() = default;
+
+protected:
+ Pathfinder *m_pathf;
+
+ void initNode(v3s16 ipos, PathGridnode *p_node);
+};
+
+class ArrayGridNodeContainer : public GridNodeContainer {
+public:
+ virtual ~ArrayGridNodeContainer() = default;
+
+ ArrayGridNodeContainer(Pathfinder *pathf, v3s16 dimensions);
+ virtual PathGridnode &access(v3s16 p);
+
+private:
+ int m_x_stride;
+ int m_y_stride;
+ std::vector<PathGridnode> m_nodes_array;
+};
+
+class MapGridNodeContainer : public GridNodeContainer {
+public:
+ virtual ~MapGridNodeContainer() = default;
+
+ MapGridNodeContainer(Pathfinder *pathf);
+ virtual PathGridnode &access(v3s16 p);
+private:
+ std::map<v3s16, PathGridnode> m_nodes;
+};
+
+/** class doing pathfinding */
+class Pathfinder {
+
+public:
+ Pathfinder() = delete;
+ Pathfinder(Map *map, const NodeDefManager *ndef) : m_map(map), m_ndef(ndef) {}
+
+ ~Pathfinder();
+
+ /**
+ * path evaluation function
+ * @param env environment to look for path
+ * @param source origin of path
+ * @param destination end position of path
+ * @param searchdistance maximum number of nodes to look in each direction
+ * @param max_jump maximum number of blocks a path may jump up
+ * @param max_drop maximum number of blocks a path may drop
+ * @param algo Algorithm to use for finding a path
+ */
+ std::vector<v3s16> getPath(v3s16 source,
+ v3s16 destination,
+ unsigned int searchdistance,
+ unsigned int max_jump,
+ unsigned int max_drop,
+ PathAlgorithm algo);
+
+private:
+ /* helper functions */
+
+ /**
+ * transform index pos to mappos
+ * @param ipos a index position
+ * @return map position
+ */
+ v3s16 getRealPos(v3s16 ipos);
+
+ /**
+ * transform mappos to index pos
+ * @param pos a real pos
+ * @return index position
+ */
+ v3s16 getIndexPos(v3s16 pos);
+
+ /**
+ * get gridnode at a specific index position
+ * @param ipos index position
+ * @return gridnode for index
+ */
+ PathGridnode &getIndexElement(v3s16 ipos);
+
+ /**
+ * Get gridnode at a specific index position
+ * @return gridnode for index
+ */
+ PathGridnode &getIdxElem(s16 x, s16 y, s16 z);
+
+ /**
+ * invert a 3D position (change sign of coordinates)
+ * @param pos 3D position
+ * @return pos *-1
+ */
+ v3s16 invert(v3s16 pos);
+
+ /**
+ * check if a index is within current search area
+ * @param index position to validate
+ * @return true/false
+ */
+ bool isValidIndex(v3s16 index);
+
+
+ /* algorithm functions */
+
+ /**
+ * calculate 2D Manhattan distance to target
+ * @param pos position to calc distance
+ * @return integer distance
+ */
+ int getXZManhattanDist(v3s16 pos);
+
+ /**
+ * calculate cost of movement
+ * @param pos real world position to start movement
+ * @param dir direction to move to
+ * @return cost information
+ */
+ PathCost calcCost(v3s16 pos, v3s16 dir);
+
+ /**
+ * recursive update whole search areas total cost information
+ * @param ipos position to check next
+ * @param srcdir positionc checked last time
+ * @param total_cost cost of moving to ipos
+ * @param level current recursion depth
+ * @return true/false path to destination has been found
+ */
+ bool updateAllCosts(v3s16 ipos, v3s16 srcdir, int current_cost, int level);
+
+ /**
+ * try to find a path to destination using a heuristic function
+ * to estimate distance to target (A* search algorithm)
+ * @param isource start position (index pos)
+ * @param idestination end position (index pos)
+ * @return true/false path to destination has been found
+ */
+ bool updateCostHeuristic(v3s16 isource, v3s16 idestination);
+
+ /**
+ * build a vector containing all nodes from destination to source;
+ * to be called after the node costs have been processed
+ * @param path vector to add nodes to
+ * @param ipos initial pos to check (index pos)
+ * @return true/false path has been fully built
+ */
+ bool buildPath(std::vector<v3s16> &path, v3s16 ipos);
+
+ /**
+ * go downwards from a position until some barrier
+ * is hit.
+ * @param pos position from which to go downwards
+ * @param max_down maximum distance to go downwards
+ * @return new position after movement; if too far down,
+ * pos is returned
+ */
+ v3s16 walkDownwards(v3s16 pos, unsigned int max_down);
+
+ /* variables */
+ 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 */
+
+ /** contains all map data already collected and analyzed.
+ Access it via the getIndexElement/getIdxElem methods. */
+ friend class GridNodeContainer;
+ GridNodeContainer *m_nodes_container = nullptr;
+
+ Map *m_map = nullptr;
+
+ const NodeDefManager *m_ndef = nullptr;
+
+ friend class PathfinderCompareHeuristic;