Line data Source code
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 0 : 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_ */
|
