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