src/pathfinder.h

   1 /*
   2 Minetest
   3 Copyright (C) 2013 sapier, sapier at gmx dot net
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #ifndef PATHFINDER_H_
  21 #define PATHFINDER_H_
  22
  23 /******************************************************************************/
  24 /* Includes                                                                   */
  25 /******************************************************************************/
  26 #include <vector>
  27
  28 #include "server.h"
  29 #include "irr_v3d.h"
  30
  31
  32 /******************************************************************************/
  33 /* Typedefs and macros                                                        */
  34 /******************************************************************************/
  35
  36 //#define PATHFINDER_DEBUG
  37
  38 typedef enum {
  39         DIR_XP,
  40         DIR_XM,
  41         DIR_ZP,
  42         DIR_ZM
  43 } path_directions;
  44
  45 /** List of supported algorithms */
  46 typedef enum {
  47         DIJKSTRA,           /**< Dijkstra shortest path algorithm             */
  48         A_PLAIN,            /**< A* algorithm using heuristics to find a path */
  49         A_PLAIN_NP          /**< A* algorithm without prefetching of map data */
  50 } algorithm;
  51
  52 /******************************************************************************/
  53 /* declarations                                                               */
  54 /******************************************************************************/
  55
  56 /** c wrapper function to use from scriptapi */
  57 std::vector<v3s16> get_Path(ServerEnvironment* env,
  58                                                         v3s16 source,
  59                                                         v3s16 destination,
  60                                                         unsigned int searchdistance,
  61                                                         unsigned int max_jump,
  62                                                         unsigned int max_drop,
  63                                                         algorithm algo);
  64
  65 /** representation of cost in specific direction */
  66 class path_cost {
  67 public:
  68
  69         /** default constructor */
  70         path_cost();
  71
  72         /** copy constructor */
  73         path_cost(const path_cost& b);
  74
  75         /** assignment operator */
  76         path_cost& operator= (const path_cost& b);
  77
  78         bool valid;              /**< movement is possible         */
  79         int  value;              /**< cost of movement             */
  80         int  direction;          /**< y-direction of movement      */
  81         bool updated;            /**< this cost has ben calculated */
  82
  83 };
  84
  85
  86 /** representation of a mapnode to be used for pathfinding */
  87 class path_gridnode {
  88
  89 public:
  90         /** default constructor */
  91         path_gridnode();
  92
  93         /** copy constructor */
  94         path_gridnode(const path_gridnode& b);
  95
  96         /**
  97          * assignment operator
  98          * @param b node to copy
  99          */
 100         path_gridnode& operator= (const path_gridnode& b);
 101
 102         /**
 103          * read cost in a specific direction
 104          * @param dir direction of cost to fetch
 105          */
 106         path_cost get_cost(v3s16 dir);
 107
 108         /**
 109          * set cost value for movement
 110          * @param dir direction to set cost for
 111          * @cost cost to set
 112          */
 113         void      set_cost(v3s16 dir,path_cost cost);
 114
 115         bool      valid;               /**< node is on surface                    */
 116         bool      target;              /**< node is target position               */
 117         bool      source;              /**< node is stating position              */
 118         int       totalcost;           /**< cost to move here from starting point */
 119         v3s16     sourcedir;           /**< origin of movement for current cost   */
 120         int       surfaces;            /**< number of surfaces with same x,z value*/
 121         v3s16     pos;                 /**< real position of node                 */
 122         path_cost directions[4];       /**< cost in different directions          */
 123
 124         /* debug values */
 125         bool      is_element;          /**< node is element of path detected      */
 126         char      type;                /**< type of node                          */
 127 };
 128
 129 /** class doing pathfinding */
 130 class pathfinder {
 131
 132 public:
 133         /**
 134          * default constructor
 135          */
 136         pathfinder();
 137
 138         /**
 139          * path evaluation function
 140          * @param env environment to look for path
 141          * @param source origin of path
 142          * @param destination end position of path
 143          * @param searchdistance maximum number of nodes to look in each direction
 144          * @param max_jump maximum number of blocks a path may jump up
 145          * @param max_drop maximum number of blocks a path may drop
 146          * @param algo algorithm to use for finding a path
 147          */
 148         std::vector<v3s16> get_Path(ServerEnvironment* env,
 149                         v3s16 source,
 150                         v3s16 destination,
 151                         unsigned int searchdistance,
 152                         unsigned int max_jump,
 153                         unsigned int max_drop,
 154                         algorithm algo);
 155
 156 private:
 157         /** data struct for storing internal information */
 158         struct limits {
 159                 struct limit {
 160                         int min;
 161                         int max;
 162                 };
 163
 164                 limit X;
 165                 limit Y;
 166                 limit Z;
 167         };
 168
 169         /* helper functions */
 170
 171         /**
 172          * transform index pos to mappos
 173          * @param ipos a index position
 174          * @return map position
 175          */
 176         v3s16          getRealPos(v3s16 ipos);
 177
 178         /**
 179          * transform mappos to index pos
 180          * @param pos a real pos
 181          * @return index position
 182          */
 183         v3s16          getIndexPos(v3s16 pos);
 184
 185         /**
 186          * get gridnode at a specific index position
 187          * @param ipos index position
 188          * @return gridnode for index
 189          */
 190         path_gridnode& getIndexElement(v3s16 ipos);
 191
 192         /**
 193          * invert a 3d position
 194          * @param pos 3d position
 195          * @return pos *-1
 196          */
 197         v3s16          invert(v3s16 pos);
 198
 199         /**
 200          * check if a index is within current search area
 201          * @param index position to validate
 202          * @return true/false
 203          */
 204         bool           valid_index(v3s16 index);
 205
 206         /**
 207          * translate position to float position
 208          * @param pos integer position
 209          * @return float position
 210          */
 211         v3f            tov3f(v3s16 pos);
 212
 213
 214         /* algorithm functions */
 215
 216         /**
 217          * calculate 2d manahttan distance to target
 218          * @param pos position to calc distance
 219          * @return integer distance
 220          */
 221         int           get_manhattandistance(v3s16 pos);
 222
 223         /**
 224          * get best direction based uppon heuristics
 225          * @param directions list of unchecked directions
 226          * @param g_pos mapnode to start from
 227          * @return direction to check
 228          */
 229         v3s16         get_dir_heuristic(std::vector<v3s16>& directions,path_gridnode& g_pos);
 230
 231         /**
 232          * build internal data representation of search area
 233          * @return true/false if costmap creation was successfull
 234          */
 235         bool          build_costmap();
 236
 237         /**
 238          * calculate cost of movement
 239          * @param pos real world position to start movement
 240          * @param dir direction to move to
 241          * @return cost information
 242          */
 243         path_cost     calc_cost(v3s16 pos,v3s16 dir);
 244
 245         /**
 246          * recursive update whole search areas total cost information
 247          * @param ipos position to check next
 248          * @param srcdir positionc checked last time
 249          * @param total_cost cost of moving to ipos
 250          * @param level current recursion depth
 251          * @return true/false path to destination has been found
 252          */
 253         bool          update_all_costs(v3s16 ipos,v3s16 srcdir,int total_cost,int level);
 254
 255         /**
 256          * recursive try to find a patrh to destionation
 257          * @param ipos position to check next
 258          * @param srcdir positionc checked last time
 259          * @param total_cost cost of moving to ipos
 260          * @param level current recursion depth
 261          * @return true/false path to destination has been found
 262          */
 263         bool          update_cost_heuristic(v3s16 ipos,v3s16 srcdir,int current_cost,int level);
 264
 265         /**
 266          * recursive build a vector containing all nodes from source to destination
 267          * @param path vector to add nodes to
 268          * @param pos pos to check next
 269          * @param level recursion depth
 270          */
 271         void          build_path(std::vector<v3s16>& path,v3s16 pos, int level);
 272
 273         /* variables */
 274         int m_max_index_x;          /**< max index of search area in x direction  */
 275         int m_max_index_y;          /**< max index of search area in y direction  */
 276         int m_max_index_z;          /**< max index of search area in z direction  */
 277
 278
 279         int m_searchdistance;       /**< max distance to search in each direction */
 280         int m_maxdrop;              /**< maximum number of blocks a path may drop */
 281         int m_maxjump;              /**< maximum number of blocks a path may jump */
 282         int m_min_target_distance;  /**< current smalest path to target           */
 283
 284         bool m_prefetch;            /**< prefetch cost data                       */
 285
 286         v3s16 m_start;              /**< source position                          */
 287         v3s16 m_destination;        /**< destination position                     */
 288
 289         limits m_limits;            /**< position limits in real map coordinates  */
 290
 291         /** 3d grid containing all map data already collected and analyzed */
 292         std::vector<std::vector<std::vector<path_gridnode> > > m_data;
 293
 294         ServerEnvironment* m_env;   /**< minetest environment pointer             */
 295
 296 #ifdef PATHFINDER_DEBUG
 297
 298         /**
 299          * print collected cost information
 300          */
 301         void print_cost();
 302
 303         /**
 304          * print collected cost information in a specific direction
 305          * @param dir direction to print
 306          */
 307         void print_cost(path_directions dir);
 308
 309         /**
 310          * print type of node as evaluated
 311          */
 312         void print_type();
 313
 314         /**
 315          * print pathlenght for all nodes in search area
 316          */
 317         void print_pathlen();
 318
 319         /**
 320          * print a path
 321          * @param path path to show
 322          */
 323         void print_path(std::vector<v3s16> path);
 324
 325         /**
 326          * print y direction for all movements
 327          */
 328         void print_ydir();
 329
 330         /**
 331          * print y direction for moving in a specific direction
 332          * @param dir direction to show data
 333          */
 334         void print_ydir(path_directions dir);
 335
 336         /**
 337          * helper function to translate a direction to speaking text
 338          * @param dir direction to translate
 339          * @return textual name of direction
 340          */
 341         std::string dir_to_name(path_directions dir);
 342 #endif
 343 };
 344
 345 #endif /* PATHFINDER_H_ */