Skip to content

Commit 69367aa

Browse files
sapierkwolekr
sapier
authored and
kwolekr
committedApr 6, 2013
Add Dijkstra A* and A* without prefetching pathfind algorithms
·
5.11.00.4.7-MSVC
1 parent 97f0bb0 commit 69367aa

8 files changed

+1540
-1
lines changed
 

‎doc/lua_api.txt

+15-1
Original file line numberDiff line numberDiff line change
@@ -1185,7 +1185,21 @@ methods:
11851185
- get_perlin(seeddiff, octaves, persistence, scale)
11861186
^ Return world-specific perlin noise (int(worldseed)+seeddiff)
11871187
- clear_objects()
1188-
^ clear all objects in the environments
1188+
^ clear all objects in the environments
1189+
- line_of_sight(pos1,pos2,stepsize) ->true/false
1190+
^ checkif there is a direct line of sight between pos1 and pos2
1191+
^ pos1 First position
1192+
^ pos2 Second position
1193+
^ stepsize smaller gives more accurate results but requires more computing
1194+
time. Default is 1.
1195+
-find_path(pos1,pos2,searchdistance,max_jump,max_drop,algorithm) -> table containing path
1196+
^ returns a table of 3d points representing a path from pos1 to pos2 or nil
1197+
^ pos1: start position
1198+
^ pos2: end position
1199+
^ searchdistance: number of blocks to search in each direction
1200+
^ max_jump: maximum height difference to consider walkable
1201+
^ max_drop: maximum height difference to consider droppable
1202+
^ algorithm: A*_noprefetch(default), A*, Dijkstra
11891203
- spawn_tree (pos, {treedef})
11901204
^ spawns L-System tree at given pos with definition in treedef table
11911205
treedef={

‎src/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -264,6 +264,7 @@ set(common_SRCS
264264
clientserver.cpp
265265
staticobject.cpp
266266
serverlist.cpp
267+
pathfinder.cpp
267268
util/serialize.cpp
268269
util/directiontables.cpp
269270
util/numeric.cpp

‎src/environment.cpp

+23
Original file line numberDiff line numberDiff line change
@@ -364,6 +364,29 @@ ServerMap & ServerEnvironment::getServerMap()
364364
return *m_map;
365365
}
366366

367+
bool ServerEnvironment::line_of_sight(v3f pos1, v3f pos2, float stepsize)
368+
{
369+
float distance = pos1.getDistanceFrom(pos2);
370+
371+
//calculate normalized direction vector
372+
v3f normalized_vector = v3f((pos2.X - pos1.X)/distance,
373+
(pos2.Y - pos1.Y)/distance,
374+
(pos2.Z - pos1.Z)/distance);
375+
376+
//find out if there's a node on path between pos1 and pos2
377+
for (float i = 1; i < distance; i += stepsize) {
378+
v3s16 pos = floatToInt(v3f(normalized_vector.X * i,
379+
normalized_vector.Y * i,
380+
normalized_vector.Z * i) +pos1,BS);
381+
382+
MapNode n = getMap().getNodeNoEx(pos);
383+
384+
if(n.param0 != CONTENT_AIR) {
385+
return false;
386+
}
387+
}
388+
return true;
389+
}
367390

368391
void ServerEnvironment::serializePlayers(const std::string &savedir)
369392
{

‎src/environment.h

+3
Original file line numberDiff line numberDiff line change
@@ -298,6 +298,9 @@ class ServerEnvironment : public Environment
298298
// This makes stuff happen
299299
void step(f32 dtime);
300300

301+
//check if there's a line of sight between two positions
302+
bool line_of_sight(v3f pos1, v3f pos2, float stepsize=1.0);
303+
301304
private:
302305

303306
/*

‎src/pathfinder.cpp

+1,081
Large diffs are not rendered by default.

‎src/pathfinder.h

+345
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,345 @@
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_ */

‎src/scriptapi_env.cpp

+66
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
2626
#include "content_sao.h"
2727
#include "script.h"
2828
#include "treegen.h"
29+
#include "pathfinder.h"
2930
#include "util/pointedthing.h"
3031
#include "scriptapi_types.h"
3132
#include "scriptapi_noise.h"
@@ -647,6 +648,69 @@ int EnvRef::l_clear_objects(lua_State *L)
647648
return 0;
648649
}
649650

651+
int EnvRef::l_line_of_sight(lua_State *L) {
652+
float stepsize = 1.0;
653+
654+
//infostream<<"EnvRef::l_get_node()"<<std::endl;
655+
EnvRef *o = checkobject(L, 1);
656+
ServerEnvironment *env = o->m_env;
657+
if(env == NULL) return 0;
658+
659+
// read position 1 from lua
660+
v3f pos1 = checkFloatPos(L, 2);
661+
// read position 2 from lua
662+
v3f pos2 = checkFloatPos(L, 2);
663+
//read step size from lua
664+
if(lua_isnumber(L, 3))
665+
stepsize = lua_tonumber(L, 3);
666+
667+
return (env->line_of_sight(pos1,pos2,stepsize));
668+
}
669+
670+
int EnvRef::l_find_path(lua_State *L)
671+
{
672+
EnvRef *o = checkobject(L, 1);
673+
ServerEnvironment *env = o->m_env;
674+
675+
if(env == NULL) return 0;
676+
677+
v3s16 pos1 = read_v3s16(L, 2);
678+
v3s16 pos2 = read_v3s16(L, 3);
679+
unsigned int searchdistance = luaL_checkint(L, 4);
680+
unsigned int max_jump = luaL_checkint(L, 5);
681+
unsigned int max_drop = luaL_checkint(L, 6);
682+
algorithm algo = A_PLAIN_NP;
683+
if(! lua_isnil(L, 7)) {
684+
std::string algorithm = luaL_checkstring(L,7);
685+
686+
if (algorithm == "A*")
687+
algo = A_PLAIN;
688+
689+
if (algorithm == "Dijkstra")
690+
algo = DIJKSTRA;
691+
}
692+
693+
std::vector<v3s16> path =
694+
get_Path(env,pos1,pos2,searchdistance,max_jump,max_drop,algo);
695+
696+
if (path.size() > 0)
697+
{
698+
lua_newtable(L);
699+
int top = lua_gettop(L);
700+
unsigned int index = 1;
701+
for (std::vector<v3s16>::iterator i = path.begin(); i != path.end();i++)
702+
{
703+
lua_pushnumber(L,index);
704+
push_v3s16(L, *i);
705+
lua_settable(L, top);
706+
index++;
707+
}
708+
return 1;
709+
}
710+
711+
return 0;
712+
}
713+
650714
int EnvRef::l_spawn_tree(lua_State *L)
651715
{
652716
EnvRef *o = checkobject(L, 1);
@@ -780,6 +844,8 @@ const luaL_reg EnvRef::methods[] = {
780844
luamethod(EnvRef, get_perlin_map),
781845
luamethod(EnvRef, clear_objects),
782846
luamethod(EnvRef, spawn_tree),
847+
luamethod(EnvRef, line_of_sight),
848+
luamethod(EnvRef, find_path),
783849
{0,0}
784850
};
785851

‎src/scriptapi_env.h

+6
Original file line numberDiff line numberDiff line change
@@ -137,6 +137,12 @@ class EnvRef
137137

138138
static int l_spawn_tree(lua_State *L);
139139

140+
141+
static int l_line_of_sight(lua_State *L);
142+
143+
//find a path between two positions
144+
static int l_find_path(lua_State *L);
145+
140146
public:
141147
EnvRef(ServerEnvironment *env);
142148

0 commit comments

Comments
 (0)
Please sign in to comment.