3 Copyright (C) 2013 sapier, sapier at gmx dot net
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.
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.
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.
23 /******************************************************************************/
25 /******************************************************************************/
31 /******************************************************************************/
32 /* Forward declarations */
33 /******************************************************************************/
35 class ServerEnvironment;
37 /******************************************************************************/
38 /* Typedefs and macros */
39 /******************************************************************************/
41 //#define PATHFINDER_DEBUG
50 /** List of supported algorithms */
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 */
57 /******************************************************************************/
59 /******************************************************************************/
61 /** c wrapper function to use from scriptapi */
62 std::vector<v3s16> get_Path(ServerEnvironment* env,
65 unsigned int searchdistance,
66 unsigned int max_jump,
67 unsigned int max_drop,
70 /** representation of cost in specific direction */
74 /** default constructor */
77 /** copy constructor */
78 path_cost(const path_cost& b);
80 /** assignment operator */
81 path_cost& operator= (const path_cost& b);
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 */
91 /** representation of a mapnode to be used for pathfinding */
95 /** default constructor */
98 /** copy constructor */
99 path_gridnode(const path_gridnode& b);
102 * assignment operator
103 * @param b node to copy
105 path_gridnode& operator= (const path_gridnode& b);
108 * read cost in a specific direction
109 * @param dir direction of cost to fetch
111 path_cost get_cost(v3s16 dir);
114 * set cost value for movement
115 * @param dir direction to set cost for
118 void set_cost(v3s16 dir,path_cost cost);
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 */
130 bool is_element; /**< node is element of path detected */
131 char type; /**< type of node */
134 /** class doing pathfinding */
139 * default constructor
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
153 std::vector<v3s16> get_Path(ServerEnvironment* env,
156 unsigned int searchdistance,
157 unsigned int max_jump,
158 unsigned int max_drop,
162 /** data struct for storing internal information */
174 /* helper functions */
177 * transform index pos to mappos
178 * @param ipos a index position
179 * @return map position
181 v3s16 getRealPos(v3s16 ipos);
184 * transform mappos to index pos
185 * @param pos a real pos
186 * @return index position
188 v3s16 getIndexPos(v3s16 pos);
191 * get gridnode at a specific index position
192 * @param ipos index position
193 * @return gridnode for index
195 path_gridnode& getIndexElement(v3s16 ipos);
198 * invert a 3d position
199 * @param pos 3d position
202 v3s16 invert(v3s16 pos);
205 * check if a index is within current search area
206 * @param index position to validate
209 bool valid_index(v3s16 index);
212 * translate position to float position
213 * @param pos integer position
214 * @return float position
216 v3f tov3f(v3s16 pos);
219 /* algorithm functions */
222 * calculate 2d manahttan distance to target
223 * @param pos position to calc distance
224 * @return integer distance
226 int get_manhattandistance(v3s16 pos);
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
234 v3s16 get_dir_heuristic(std::vector<v3s16>& directions,path_gridnode& g_pos);
237 * build internal data representation of search area
238 * @return true/false if costmap creation was successfull
240 bool build_costmap();
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
248 path_cost calc_cost(v3s16 pos,v3s16 dir);
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
258 bool update_all_costs(v3s16 ipos,v3s16 srcdir,int total_cost,int level);
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
268 bool update_cost_heuristic(v3s16 ipos,v3s16 srcdir,int current_cost,int level);
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
276 void build_path(std::vector<v3s16>& path,v3s16 pos, int level);
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 */
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 */
289 bool m_prefetch; /**< prefetch cost data */
291 v3s16 m_start; /**< source position */
292 v3s16 m_destination; /**< destination position */
294 limits m_limits; /**< position limits in real map coordinates */
296 /** 3d grid containing all map data already collected and analyzed */
297 std::vector<std::vector<std::vector<path_gridnode> > > m_data;
299 ServerEnvironment* m_env; /**< minetest environment pointer */
301 #ifdef PATHFINDER_DEBUG
304 * print collected cost information
309 * print collected cost information in a specific direction
310 * @param dir direction to print
312 void print_cost(path_directions dir);
315 * print type of node as evaluated
320 * print pathlenght for all nodes in search area
322 void print_pathlen();
326 * @param path path to show
328 void print_path(std::vector<v3s16> path);
331 * print y direction for all movements
336 * print y direction for moving in a specific direction
337 * @param dir direction to show data
339 void print_ydir(path_directions dir);
342 * helper function to translate a direction to speaking text
343 * @param dir direction to translate
344 * @return textual name of direction
346 std::string dir_to_name(path_directions dir);
350 #endif /* PATHFINDER_H_ */