[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Wesnoth-cvs-commits] wesnoth/src pathfind.cpp
From: |
Guillaume Melquiond |
Subject: |
[Wesnoth-cvs-commits] wesnoth/src pathfind.cpp |
Date: |
Thu, 27 Jan 2005 15:30:52 -0500 |
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,