diff options
Diffstat (limited to 'src/pathfinder.h')
| -rw-r--r-- | src/pathfinder.h | 284 |
1 files changed, 0 insertions, 284 deletions
diff --git a/src/pathfinder.h b/src/pathfinder.h index dd41227f7..31ea2f285 100644 --- a/src/pathfinder.h +++ b/src/pathfinder.h @@ -24,10 +24,8 @@ with this program; if not, write to the Free Software Foundation, Inc., /* Includes */ /******************************************************************************/ #include <vector> - #include "irr_v3d.h" - /******************************************************************************/ /* Forward declarations */ /******************************************************************************/ @@ -38,8 +36,6 @@ class ServerEnvironment; /* Typedefs and macros */ /******************************************************************************/ -//#define PATHFINDER_DEBUG - typedef enum { DIR_XP, DIR_XM, @@ -67,284 +63,4 @@ std::vector<v3s16> get_Path(ServerEnvironment* env, unsigned int max_drop, algorithm algo); -/** representation of cost in specific direction */ -class path_cost { -public: - - /** default constructor */ - path_cost(); - - /** copy constructor */ - path_cost(const path_cost& b); - - /** assignment operator */ - path_cost& operator= (const path_cost& b); - - bool valid; /**< movement is possible */ - int value; /**< cost of movement */ - int direction; /**< y-direction of movement */ - bool updated; /**< this cost has ben calculated */ - -}; - - -/** representation of a mapnode to be used for pathfinding */ -class path_gridnode { - -public: - /** default constructor */ - path_gridnode(); - - /** copy constructor */ - path_gridnode(const path_gridnode& b); - - /** - * assignment operator - * @param b node to copy - */ - path_gridnode& operator= (const path_gridnode& b); - - /** - * read cost in a specific direction - * @param dir direction of cost to fetch - */ - path_cost get_cost(v3s16 dir); - - /** - * set cost value for movement - * @param dir direction to set cost for - * @cost cost to set - */ - void set_cost(v3s16 dir,path_cost cost); - - bool valid; /**< node is on surface */ - bool target; /**< node is target position */ - bool source; /**< node is stating position */ - int totalcost; /**< cost to move here from starting point */ - v3s16 sourcedir; /**< origin of movement for current cost */ - int surfaces; /**< number of surfaces with same x,z value*/ - v3s16 pos; /**< real position of node */ - path_cost directions[4]; /**< cost in different directions */ - - /* debug values */ - bool is_element; /**< node is element of path detected */ - char type; /**< type of node */ -}; - -/** class doing pathfinding */ -class pathfinder { - -public: - /** - * default constructor - */ - 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> get_Path(ServerEnvironment* env, - v3s16 source, - v3s16 destination, - unsigned int searchdistance, - unsigned int max_jump, - unsigned int max_drop, - algorithm algo); - -private: - /** data struct for storing internal information */ - struct limits { - struct limit { - int min; - int max; - }; - - limit X; - limit Y; - limit Z; - }; - - /* 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 - */ - path_gridnode& getIndexElement(v3s16 ipos); - - /** - * 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 valid_index(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 - * @param pos position to calc distance - * @return integer distance - */ - int get_manhattandistance(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 get_dir_heuristic(std::vector<v3s16>& directions,path_gridnode& g_pos); - - /** - * build internal data representation of search area - * @return true/false if costmap creation was successfull - */ - bool build_costmap(); - - /** - * calculate cost of movement - * @param pos real world position to start movement - * @param dir direction to move to - * @return cost information - */ - path_cost calc_cost(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 update_all_costs(v3s16 ipos,v3s16 srcdir,int total_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 update_cost_heuristic(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 build_path(std::vector<v3s16>& path,v3s16 pos, int level); - - /* variables */ - int m_max_index_x; /**< max index of search area in x direction */ - int m_max_index_y; /**< max index of search area in y direction */ - int m_max_index_z; /**< max index of search area in z direction */ - - - int m_searchdistance; /**< max distance to search in each direction */ - int m_maxdrop; /**< maximum number of blocks a path may drop */ - int m_maxjump; /**< maximum number of blocks a path may jump */ - int m_min_target_distance; /**< current smalest path to target */ - - bool m_prefetch; /**< prefetch cost data */ - - v3s16 m_start; /**< source position */ - v3s16 m_destination; /**< destination position */ - - limits m_limits; /**< position limits in real map coordinates */ - - /** 3d grid containing all map data already collected and analyzed */ - std::vector<std::vector<std::vector<path_gridnode> > > m_data; - - ServerEnvironment* m_env; /**< minetest environment pointer */ - -#ifdef PATHFINDER_DEBUG - - /** - * print collected cost information - */ - void print_cost(); - - /** - * print collected cost information in a specific direction - * @param dir direction to print - */ - void print_cost(path_directions dir); - - /** - * print type of node as evaluated - */ - void print_type(); - - /** - * print pathlenght for all nodes in search area - */ - void print_pathlen(); - - /** - * print a path - * @param path path to show - */ - void print_path(std::vector<v3s16> path); - - /** - * print y direction for all movements - */ - void print_ydir(); - - /** - * print y direction for moving in a specific direction - * @param dir direction to show data - */ - void print_ydir(path_directions dir); - - /** - * helper function to translate a direction to speaking text - * @param dir direction to translate - * @return textual name of direction - */ - std::string dir_to_name(path_directions dir); -#endif -}; - #endif /* PATHFINDER_H_ */ |