Add Dijkstra A* and A* without prefetching pathfind algorithms

minetest · Apr 6, 2013 · 69367aa · 69367aa
1 parent 97f0bb0
commit 69367aa
Show file tree

Hide file tree

Showing 8 changed files with 1,540 additions and 1 deletion.
diff --git a/doc/lua_api.txt b/doc/lua_api.txt
@@ -1185,7 +1185,21 @@ methods:
 - get_perlin(seeddiff, octaves, persistence, scale)
   ^ Return world-specific perlin noise (int(worldseed)+seeddiff)
 - clear_objects()
-  ^ clear all objects in the environments 
+  ^ clear all objects in the environments
+- line_of_sight(pos1,pos2,stepsize) ->true/false
+  ^ checkif there is a direct line of sight between pos1 and pos2
+  ^ pos1 First position
+  ^ pos2 Second position
+  ^ stepsize smaller gives more accurate results but requires more computing
+             time. Default is 1.
+-find_path(pos1,pos2,searchdistance,max_jump,max_drop,algorithm) -> table containing path
+  ^ returns a table of 3d points representing a path from pos1 to pos2 or nil
+  ^ pos1: start position
+  ^ pos2: end position
+  ^ searchdistance: number of blocks to search in each direction
+  ^ max_jump: maximum height difference to consider walkable
+  ^ max_drop: maximum height difference to consider droppable
+  ^ algorithm: A*_noprefetch(default), A*, Dijkstra
 - spawn_tree (pos, {treedef})
   ^ spawns L-System tree at given pos with definition in treedef table
 treedef={

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -264,6 +264,7 @@ set(common_SRCS
 	clientserver.cpp
 	staticobject.cpp
 	serverlist.cpp
+	pathfinder.cpp
 	util/serialize.cpp
 	util/directiontables.cpp
 	util/numeric.cpp

diff --git a/src/environment.cpp b/src/environment.cpp
@@ -364,6 +364,29 @@ ServerMap & ServerEnvironment::getServerMap()
 	return *m_map;
 }
 
+bool ServerEnvironment::line_of_sight(v3f pos1, v3f pos2, float stepsize)
+{
+	float distance = pos1.getDistanceFrom(pos2);
+
+	//calculate normalized direction vector
+	v3f normalized_vector = v3f((pos2.X - pos1.X)/distance,
+								(pos2.Y - pos1.Y)/distance,
+								(pos2.Z - pos1.Z)/distance);
+
+	//find out if there's a node on path between pos1 and pos2
+	for (float i = 1; i < distance; i += stepsize) {
+		v3s16 pos = floatToInt(v3f(normalized_vector.X * i,
+				normalized_vector.Y * i,
+				normalized_vector.Z * i) +pos1,BS);
+
+		MapNode n = getMap().getNodeNoEx(pos);
+
+		if(n.param0 != CONTENT_AIR) {
+			return false;
+		}
+	}
+	return true;
+}
 
 void ServerEnvironment::serializePlayers(const std::string &savedir)
 {

diff --git a/src/environment.h b/src/environment.h
@@ -298,6 +298,9 @@ class ServerEnvironment : public Environment
 	// This makes stuff happen
 	void step(f32 dtime);
 
+	//check if there's a line of sight between two positions
+	bool line_of_sight(v3f pos1, v3f pos2, float stepsize=1.0);
+
 private:
 
 	/*