Translation to Portuguese of Brazil for Minetest
[oweals/minetest.git] / 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_ */