Author: alink
Date: Fri Jun 27 12:43:46 2008
New Revision: 27524
URL: http://svn.gna.org/viewcvs/wesnoth?rev=27524&view=rev
Log:
First implementation of the "linear" pathfinding idea of zookeeper:
(prefer using straight shortest path, instead of '_/' shaped ones)
This also improve roads in random map generation and maybe make some AI
decisions more "human" (move more in the apparent direction on the screen).
Modified:
trunk/src/astarnode.hpp
Modified: trunk/src/astarnode.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/astarnode.hpp?rev=27524&r1=27523&r2=27524&view=diff
==============================================================================
--- trunk/src/astarnode.hpp (original)
+++ trunk/src/astarnode.hpp Fri Jun 27 12:43:46 2008
@@ -42,7 +42,23 @@
inline double heuristic(const gamemap::location& src, const
gamemap::location& dst)
{
- return distance_between(src, dst);
+ // We will mainly use the distances in hexes
+ // but we substract a tiny bonus for shorter Euclidean distance
+ // based on how the path looks on the screen.
+ // We must substract (and not add) to keep the heuristic
'admissible'.
+
+ // 0.75 comes frome the horizontal hex imbrication
+ double xdiff = (src.x - dst.x) * 0.75;
+ // we must add 0.5 to the y coordinate when x is odd
+ double ydiff = (src.y - dst.y) + ((src.x & 1) - (dst.x & 1)) *
0.5;
+
+ // 0.0001 is to avoid interfering with the defense cost (see
shortest_path_calculator::cost)
+ return distance_between(src, dst)-(
+ 0.0001 / sqrt( xdiff*xdiff + ydiff*ydiff)
+ );
+ // TODO: move the heuristic function into the cost_calculator
+ // so we can use case-specific heuristic
+ // and clean the definition of 0.0001
}
};
_______________________________________________
Wesnoth-commits mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-commits
