[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: |
Sat, 04 Jun 2005 18:46:32 -0400 |
CVSROOT: /cvsroot/wesnoth
Module name: wesnoth
Branch:
Changes by: Guillaume Melquiond <address@hidden> 05/06/04 22:46:32
Modified files:
src : pathfind.cpp
Log message:
Speed up the pathfinder by using a heap for the open list instead of a
sorted vector. Although the patch is big, it is mostly identation cleanup
(death to the 200 char long lines). The only code changes are: 1. removal of
a_star_stable_sort_and_merge since it is no more a sorted vector, 2.
modification of a_star_explore_neighbours so that it restores the heap
structure on return, 3. trivial changes in a_star_search so that it pops the
heap. Shortcoming: in order for the patch to stay trivial,
a_star_explore_neighbours makes the heap anew in case of node modification,
instead of doing an incremental rebuild.
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.cpp.diff?tr1=1.67&tr2=1.68&r1=text&r2=text
Patches:
Index: wesnoth/src/pathfind.cpp
diff -u wesnoth/src/pathfind.cpp:1.67 wesnoth/src/pathfind.cpp:1.68
--- wesnoth/src/pathfind.cpp:1.67 Sat Jun 4 19:16:05 2005
+++ wesnoth/src/pathfind.cpp Sat Jun 4 22:46:32 2005
@@ -1,4 +1,4 @@
-/* $Id: pathfind.cpp,v 1.67 2005/06/04 19:16:05 ott Exp $ */
+/* $Id: pathfind.cpp,v 1.68 2005/06/04 22:46:32 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://www.wesnoth.org/
@@ -31,22 +31,20 @@
typedef std::vector<a_star_node*> vector_a_star_node;
typedef std::set<gamemap::location> set_location;
-bool compare_strict_sup_a_star_node(const a_star_node* node1, const
a_star_node* node2) {
+// heaps give the biggest element for free, so we want the biggest element to
+// have the smallest cost
+static bool compare_lt_a_star_node(const a_star_node* node1, const
a_star_node* node2) {
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 + node1->h >= node2->g + node2->h;
-}
-
-void a_star_init(gamemap::location const &src, gamemap::location const &dst,
-
vector_a_star_node& openList, a_star_world& aStarGameWorld,
- const size_t
parWidth, const size_t parHeight,
-
vector_location& vectLocation, std::set<gamemap::location> const *teleports,
- size_t&
parNbTeleport)
+static void a_star_init(gamemap::location const &src, gamemap::location const
&dst,
+ vector_a_star_node &openList, a_star_world
&aStarGameWorld,
+ const size_t parWidth, const size_t parHeight,
+ vector_location &vectLocation,
std::set<gamemap::location> const *teleports,
+ size_t &parNbTeleport)
{
- a_star_node* locStartNode = NULL;
- bool locIsCreated = false;
+ a_star_node *locStartNode = NULL;
+ bool locIsCreated = false;
aStarGameWorld.resize_IFN(parWidth, parHeight);
wassert(aStarGameWorld.empty());
@@ -94,52 +92,13 @@
}
}
-void a_star_sort_and_merge(vector_a_star_node& openList, const size_t
locNbAdded)
-{
- std::stable_sort(openList.end() - locNbAdded, openList.end(),
compare_strict_sup_a_star_node);
-
-#ifdef _PARANO_ASTAR_
- for (vector_a_star_node::iterator iter = openList.begin(); iter !=
openList.end(); ++iter)
- wassert((*iter)->isInCloseList == false);
- if (openList.size() > locNbAdded) {
- for (vector_a_star_node::iterator iter = openList.begin() + 1;
iter != openList.end() - locNbAdded; ++iter)
- {
- vector_a_star_node::iterator iterPrev = iter - 1;
- wassert(compare_sup_equal_a_star_node(*iterPrev,
*iter));
- }
- }
- if (locNbAdded > 0) {
- for (vector_a_star_node::iterator iter = openList.end() -
locNbAdded + 1; iter != openList.end(); ++iter)
- {
- vector_a_star_node::iterator iterPrev = iter - 1;
- wassert(compare_sup_equal_a_star_node(*iterPrev,
*iter));
- }
- }
-#endif
-
- std::inplace_merge(openList.begin(), openList.end() - locNbAdded,
openList.end(), compare_strict_sup_a_star_node);
-
-#ifdef _PARANO_ASTAR_
- if (openList.size() > 0) {
- vector_a_star_node::iterator iter;
- for (iter = openList.begin() + 1; iter != openList.end();
++iter)
- {
- vector_a_star_node::iterator iterPrev = iter - 1;
- wassert(compare_sup_equal_a_star_node(*iterPrev,
*iter));
- }
- for (iter = openList.begin(); iter != openList.end(); ++iter)
- wassert((*iter)->isInCloseList == false);
- }
-#endif
-}
-
-void a_star_explore_neighbours(gamemap::location const &dst, const double
stop_at,
-
cost_calculator const *costCalculator,
-
const size_t parWidth, const size_t
parHeight,
-
std::set<gamemap::location> const
*teleports,
-
vector_location& vectLocation,
vector_a_star_node& openList,
-
a_star_world& aStarGameWorld, size_t&
locNbAdded,
-
a_star_node* parCurNode, const
size_t parNbTeleport)
+static void a_star_explore_neighbours(gamemap::location const &dst, const
double stop_at,
+ cost_calculator const *costCalculator,
+ const size_t parWidth, const size_t
parHeight,
+ std::set<gamemap::location> const
*teleports,
+ vector_location &vectLocation,
vector_a_star_node &openList,
+ a_star_world &aStarGameWorld,
+ a_star_node *parCurNode, const size_t
parNbTeleport)
{
//----------------- PRE_CONDITIONS ------------------
wassert(parCurNode != NULL);
@@ -147,12 +106,12 @@
typedef std::pair<vector_a_star_node::iterator,
vector_a_star_node::iterator> pair_node_iter;
- a_star_node* locNextNode;
- double locCost;
+ a_star_node *locNextNode;
+ double locCost;
pair_node_iter locPlace;
- size_t locSize;
- bool locIsCreated = false;
- const double locCostFather = parCurNode->g;
+ size_t locSize;
+ bool locIsCreated;
+ const double locCostFather = parCurNode->g;
get_adjacent_tiles(parCurNode->loc, &vectLocation[0]);
@@ -169,6 +128,9 @@
locSize = 6;
}
+ bool broken_heap = false;
+ int locNbAdded = 0;
+
for (size_t i = 0; i != locSize; ++i)
{
const gamemap::location& locLocation = vectLocation[i];
@@ -177,45 +139,40 @@
continue;
locNextNode = aStarGameWorld.getNodeFromLocation(locLocation,
locIsCreated);
locCost = locCostFather + costCalculator->cost(locLocation,
locCostFather, locLocation == dst);
- if (locIsCreated)
- {
+ if (locIsCreated) {
locNextNode->initNode(locLocation, dst, locCost,
parCurNode, teleports);
if (locNextNode->g + locNextNode->h < stop_at) {
openList.push_back(locNextNode);
++locNbAdded;
- }
- else
- {
- wassert(locNextNode->isInCloseList == false);
+ } else
locNextNode->isInCloseList = true;
- }
- }
- else
- {
- // If this path is better that the previous for this
node
- if (locCost < locNextNode->g)
- {
- if (locNextNode->isInCloseList) {
- locNextNode->isInCloseList = false;
- }
- else
- {
- locPlace =
std::equal_range(openList.begin(), openList.end() - locNbAdded, locNextNode,
compare_strict_sup_a_star_node);
-
assertParanoAstar(*(std::find(locPlace.first, locPlace.second, locNextNode)) ==
locNextNode);
-
openList.erase(std::find(locPlace.first, locPlace.second, locNextNode));
- }
+
+ } else if (locCost < locNextNode->g) {
+
+ if (locNextNode->isInCloseList) {
+ locNextNode->isInCloseList = false;
openList.push_back(locNextNode);
++locNbAdded;
- locNextNode->g = locCost;
- locNextNode->nodeParent = parCurNode;
- }
+ } else
+ broken_heap = true;
+
+ locNextNode->g = locCost;
+ locNextNode->nodeParent = parCurNode;
}
}
+
+ vector_a_star_node::iterator openList_begin = openList.begin(),
+ openList_end = openList.end();
+ if (broken_heap)
+ std::make_heap(openList_begin, openList_end,
compare_lt_a_star_node);
+ else
+ for(; locNbAdded > 0; --locNbAdded)
+ std::push_heap(openList_begin, openList_end -
(locNbAdded - 1), compare_lt_a_star_node);
}
-paths::route a_star_search( gamemap::location const &src, gamemap::location
const &dst,
-
double stop_at, cost_calculator const
*costCalculator, const size_t parWidth,
-
const size_t parHeight,
std::set<gamemap::location> const *teleports)
+paths::route a_star_search(gamemap::location const &src, gamemap::location
const &dst,
+ double stop_at, cost_calculator const
*costCalculator, const size_t parWidth,
+ const size_t parHeight, std::set<gamemap::location>
const *teleports)
{
//----------------- PRE_CONDITIONS ------------------
wassert(parWidth > 0);
@@ -225,16 +182,15 @@
wassert(costCalculator != NULL);
wassert(stop_at <= costCalculator->getNoPathValue());
//---------------------------------------------------
- static a_star_world aStarGameWorld;
- static poss_a_star_node POSS_AStarNode;
+ static a_star_world aStarGameWorld;
+ static poss_a_star_node POSS_AStarNode;
- vector_a_star_node openList;
- vector_location vectLocation;
- paths::route locRoute;
- size_t
locNbTeleport;
- size_t
locNbAdded;
- a_star_node* locDestNode =
NULL;
- a_star_node* locCurNode =
NULL;
+ vector_a_star_node openList;
+ vector_location vectLocation;
+ paths::route locRoute;
+ size_t locNbTeleport;
+ a_star_node *locDestNode = NULL;
+ a_star_node *locCurNode = NULL;
wassert(openList.empty());
wassert(aStarGameWorld.empty());
@@ -255,7 +211,7 @@
while (!openList.empty())
{
- locCurNode = openList.back();
+ locCurNode = openList.front();
wassert(locCurNode != NULL);
//if we have found a solution
@@ -279,16 +235,15 @@
goto label_AStarSearch_end;
}
+ std::pop_heap(openList.begin(), openList.end(),
compare_lt_a_star_node);
openList.pop_back();
wassert(locCurNode->isInCloseList == false);
- locCurNode->isInCloseList = true ;
+ locCurNode->isInCloseList = true;
- locNbAdded = 0;
a_star_explore_neighbours(dst, stop_at, costCalculator,
parWidth, parHeight, teleports, vectLocation,
-
openList, aStarGameWorld, locNbAdded,
locCurNode, locNbTeleport);
+ openList, aStarGameWorld, locCurNode,
locNbTeleport);
- a_star_sort_and_merge(openList, locNbAdded);
}
LOG_PF << "aborted a* search\n";
@@ -387,8 +342,8 @@
get_tiles_radius_internal(a,radius,res,visited);
}
-void get_tiles_radius(const gamemap& map, const
std::vector<gamemap::location>& locs, size_t radius,
-
std::set<gamemap::location>& res)
+void get_tiles_radius(gamemap const &map, std::vector<gamemap::location> const
&locs,
+ size_t radius, std::set<gamemap::location> &res)
{
typedef std::set<gamemap::location> location_set;
location_set not_visited(locs.begin(), locs.end()), must_visit;
@@ -417,10 +372,10 @@
}
}
-bool enemy_zoc(const gamemap& map, const gamestatus& status,
- const
std::map<gamemap::location,unit>& units,
- const
std::vector<team>& teams,
- const
gamemap::location& loc, const team& current_team, int side)
+bool enemy_zoc(gamemap const &map, gamestatus const &status,
+ std::map<gamemap::location, unit> const &units,
+ std::vector<team> const &teams,
+ gamemap::location const &loc, team const ¤t_team, int
side)
{
gamemap::location locs[6];
get_adjacent_tiles(loc,locs);
@@ -540,12 +495,12 @@
} //end anon namespace
-paths::paths(const gamemap& map, const gamestatus& status,
- const game_data& gamedata,
- const
std::map<gamemap::location,unit>& units,
- const gamemap::location& loc,
- std::vector<team>& teams,
- bool ignore_zocs, bool
allow_teleport, int additional_turns)
+paths::paths(gamemap const &map, gamestatus const &status,
+ game_data const &gamedata,
+ std::map<gamemap::location, unit> const &units,
+ gamemap::location const &loc,
+ std::vector<team> &teams,
+ bool ignore_zocs, bool allow_teleport, int additional_turns)
{
const std::map<gamemap::location,unit>::const_iterator i =
units.find(loc);
if(i == units.end()) {
@@ -559,8 +514,7 @@
ignore_zocs,allow_teleport,additional_turns,true);
}
-int route_turns_to_complete(const unit& u, const gamemap& map,
-
const paths::route& rt)
+int route_turns_to_complete(unit const &u, gamemap const &map, paths::route
const &rt)
{
if(rt.steps.empty())
return 0;
@@ -584,13 +538,11 @@
}
-shortest_path_calculator::shortest_path_calculator(const unit& u, const team&
t,
-
const unit_map& units,
-
const std::vector<team>& teams,
-
const gamemap& map,
-
const gamestatus& status)
-
: unit_(u), team_(t), units_(units),
teams_(teams),
-
map_(map), status_(status)
+shortest_path_calculator::shortest_path_calculator(unit const &u, team const
&t, unit_map const &units,
+ std::vector<team> const
&teams, gamemap const &map,
+ gamestatus const &status)
+ : unit_(u), team_(t), units_(units), teams_(teams),
+ map_(map), status_(status)
{
}
- [Wesnoth-cvs-commits] wesnoth/src pathfind.cpp,
Guillaume Melquiond <=