[Wesnoth-cvs-commits] wesnoth/src pathfind.cpp

[Guillaume Melquiond]

CVSROOT:        /cvsroot/wesnoth
Module name:    wesnoth
Branch:         
Changes by:     Guillaume Melquiond <address@hidden>    05/01/27 20:30:52

Modified files:
        src            : pathfind.cpp 

Log message:
        Fix plain wrong A* implementation. The computed value should be an 
underestimation of the travel time. Because g+1.3*h is not, A* is not 
guaranteed to find the best path (see 
http://www.wesnoth.org/forum/viewtopic.php?t=4411 for an example), and it is an 
understatement...

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.cpp.diff?tr1=1.60&tr2=1.61&r1=text&r2=text

Patches:
Index: wesnoth/src/pathfind.cpp
diff -u wesnoth/src/pathfind.cpp:1.60 wesnoth/src/pathfind.cpp:1.61
--- wesnoth/src/pathfind.cpp:1.60       Thu Jan 27 20:15:37 2005
+++ wesnoth/src/pathfind.cpp    Thu Jan 27 20:30:51 2005
@@ -1,4 +1,4 @@
-/* $Id: pathfind.cpp,v 1.60 2005/01/27 20:15:37 silene Exp $ */
+/* $Id: pathfind.cpp,v 1.61 2005/01/27 20:30:51 silene Exp $ */
 /*
 Copyright (C) 2003 by David White <address@hidden>
 Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -30,11 +30,11 @@
 typedef std::set<gamemap::location>    set_location;   
 
 bool compare_strict_sup_a_star_node(const a_star_node* node1, const 
a_star_node* node2) {
-       return (node1->g + (1.3 * node1->h) > node2->g + (1.3 * node2->h));     
        
+       return node1->g + node1->h > node2->g + node2->h;               
 }
 
 bool compare_sup_equal_a_star_node(const a_star_node* node1, const 
a_star_node* node2) {
-       return (node1->g + (1.3 * node1->h) >= node2->g + (1.3 * node2->h));    
        
+       return node1->g + node1->h >= node2->g + node2->h;              
 }
 
 void a_star_init(gamemap::location const &src, gamemap::location const &dst,