Author: alink
Date: Sun May 10 19:16:36 2009
New Revision: 35548
URL: http://svn.gna.org/viewcvs/wesnoth?rev=35548&view=rev
Log:
backport the equivalent of r35521 (small A* optimization)
also backport r35520 (fix dummy_path_calculator not respecting A* assumption)
Modified:
branches/1.6/src/astarsearch.cpp
branches/1.6/src/pathfind.cpp
Modified: branches/1.6/src/astarsearch.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/branches/1.6/src/astarsearch.cpp?rev=35548&r1=35547&r2=35548&view=diff
==============================================================================
--- branches/1.6/src/astarsearch.cpp (original)
+++ branches/1.6/src/astarsearch.cpp Sun May 10 19:16:36 2009
@@ -105,8 +105,9 @@
if (locLocation.valid(int(parWidth), int(parHeight)) == false)
continue;
locNextNode = aStarGameWorld.getNodeFromLocation(locLocation,
locIsCreated);
- locCost = locCostFather +
costCalculator->cost(parCurNode->loc,locLocation, locCostFather);
if (locIsCreated) {
+ locCost = locCostFather +
costCalculator->cost(parCurNode->loc,locLocation, locCostFather);
+
locNextNode->initNode(locLocation, dst, locCost,
parCurNode, teleports);
if (locNextNode->g + locNextNode->h < stop_at) {
openList.push_back(locNextNode);
@@ -114,17 +115,20 @@
} else
locNextNode->isInCloseList = true;
- } else if (locCost < locNextNode->g) {
-
- if (locNextNode->isInCloseList) {
- locNextNode->isInCloseList = false;
- openList.push_back(locNextNode);
- ++locNbAdded;
- } else
- broken_heap = true;
-
- locNextNode->g = locCost;
- locNextNode->nodeParent = parCurNode;
+ } else if (locCostFather + 1 < locNextNode->g) { // cost()
always >= 1 (see below)
+ locCost = locCostFather +
costCalculator->cost(parCurNode->loc,locLocation, locCostFather);
+
+ if (locCost < locNextNode->g) {
+ if (locNextNode->isInCloseList) {
+ locNextNode->isInCloseList = false;
+ openList.push_back(locNextNode);
+ ++locNbAdded;
+ } else
+ broken_heap = true;
+
+ locNextNode->g = locCost;
+ locNextNode->nodeParent = parCurNode;
+ }
}
}
Modified: branches/1.6/src/pathfind.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/branches/1.6/src/pathfind.cpp?rev=35548&r1=35547&r2=35548&view=diff
==============================================================================
--- branches/1.6/src/pathfind.cpp (original)
+++ branches/1.6/src/pathfind.cpp Sun May 10 19:16:36 2009
@@ -390,7 +390,7 @@
double dummy_path_calculator::cost(const map_location&, const map_location&,
const double) const
{
- return 0.0;
+ return 1.0;
}
int dummy_path_calculator::get_max_cost() const
_______________________________________________
Wesnoth-commits mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-commits
