+#define INFO_TARGET infostream << "Pathfinder: "
+#define VERBOSE_TARGET verbosestream << "Pathfinder: "
+#define ERROR_TARGET warningstream << "Pathfinder: "
+#endif
+
+/******************************************************************************/
+/* Class definitions */
+/******************************************************************************/
+
+
+/** 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 direction = 0; /**< y-direction 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 */
+ v3s16 sourcedir; /**< origin of movement for current cost */
+ v3s16 pos; /**< real position of node */
+ PathCost directions[4]; /**< cost in different directions */
+
+ /* debug values */
+ bool is_element = false; /**< node is element of path detected */
+ char type = 'u'; /**< type of node */
+};
+
+class Pathfinder;
+
+/** 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:
+ v3s16 m_dimensions;
+
+ 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:
+ /**
+ * default constructor
+ */
+ Pathfinder() = default;
+
+ ~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(ServerEnvironment *env,
+ 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
+ * @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);
+
+ /**
+ * translate position to float position
+ * @param pos integer position
+ * @return float position
+ */
+ v3f tov3f(v3s16 pos);
+
+
+ /* algorithm functions */
+
+ /**
+ * calculate 2d manahttan distance to target on the xz plane
+ * @param pos position to calc distance
+ * @return integer distance
+ */
+ int getXZManhattanDist(v3s16 pos);
+
+ /**
+ * get best direction based uppon heuristics
+ * @param directions list of unchecked directions
+ * @param g_pos mapnode to start from
+ * @return direction to check
+ */
+ v3s16 getDirHeuristic(std::vector<v3s16> &directions, PathGridnode &g_pos);
+
+ /**
+ * build internal data representation of search area
+ * @return true/false if costmap creation was successfull
+ */
+ bool buildCostmap();
+
+ /**
+ * 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);
+
+ /**
+ * recursive try to find a patrh to destionation
+ * @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 updateCostHeuristic(v3s16 ipos, v3s16 srcdir, int current_cost, int level);
+
+ /**
+ * recursive build a vector containing all nodes from source to destination
+ * @param path vector to add nodes to
+ * @param pos pos to check next
+ * @param level recursion depth
+ */
+ void buildPath(std::vector<v3s16> &path, v3s16 pos, int level);
+
+ /* 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_searchdistance = 0; /**< max distance to search in each 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;
+
+ ServerEnvironment *m_env = 0; /**< minetest environment pointer */
+
+#ifdef PATHFINDER_DEBUG
+
+ /**
+ * print collected cost information
+ */
+ void printCost();
+
+ /**
+ * print collected cost information in a specific direction
+ * @param dir direction to print
+ */
+ void printCost(PathDirections dir);
+
+ /**
+ * print type of node as evaluated
+ */
+ void printType();
+
+ /**
+ * print pathlenght for all nodes in search area
+ */
+ void printPathLen();
+
+ /**
+ * print a path
+ * @param path path to show
+ */
+ void printPath(std::vector<v3s16> path);
+
+ /**
+ * print y direction for all movements
+ */
+ void printYdir();
+
+ /**
+ * print y direction for moving in a specific direction
+ * @param dir direction to show data
+ */
+ void printYdir(PathDirections dir);
+
+ /**
+ * helper function to translate a direction to speaking text
+ * @param dir direction to translate
+ * @return textual name of direction
+ */
+ std::string dirToName(PathDirections dir);