[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: |
Fri, 10 Dec 2004 18:31:01 -0500 |
CVSROOT: /cvsroot/wesnoth
Module name: wesnoth
Branch:
Changes by: Guillaume Melquiond <address@hidden> 04/12/10 23:20:07
Modified files:
src : pathfind.cpp
Log message:
A bit of documentation for A*, before doing perhaps an optimized
version.
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.cpp.diff?tr1=1.48&tr2=1.49&r1=text&r2=text
Patches:
Index: wesnoth/src/pathfind.cpp
diff -u wesnoth/src/pathfind.cpp:1.48 wesnoth/src/pathfind.cpp:1.49
--- wesnoth/src/pathfind.cpp:1.48 Sun Dec 5 22:14:29 2004
+++ wesnoth/src/pathfind.cpp Fri Dec 10 23:20:06 2004
@@ -1,4 +1,4 @@
-/* $Id: pathfind.cpp,v 1.48 2004/12/05 22:14:29 silene Exp $ */
+/* $Id: pathfind.cpp,v 1.49 2004/12/10 23:20:06 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -62,6 +62,7 @@
}
gamemap::location loc, parent;
+ // g: already traveled time, h: estimated time still to travel, f:
estimated full time
double g, h, f;
};
@@ -105,6 +106,8 @@
std::copy(teleports->begin(),teleports->end(),std::back_inserter(locs));
}
+ double const lowest_gcost = lowest->second.g;
+
for(size_t j = 0; j != locs.size(); ++j) {
//if we have found a solution
@@ -125,7 +128,7 @@
std::reverse(rt.steps.begin(),rt.steps.end());
rt.steps.push_back(dst);
- rt.move_left = int(lowest->second.g +
obj->cost(dst,lowest->second.g));
+ rt.move_left = int(lowest_gcost +
obj->cost(dst, lowest_gcost));
assert(rt.steps.front() == src);
@@ -136,21 +139,25 @@
list_map::iterator current_best =
open_list.find(locs[j]);
const bool in_open = current_best != open_list.end();
- if(!in_open) {
+ bool in_lists = in_open;
+ if (!in_lists) {
current_best = closed_list.find(locs[j]);
+ in_lists = current_best != closed_list.end();
}
-
- if(current_best != closed_list.end() &&
current_best->second.g <= lowest->second.g+1.0) {
- continue;
+ double current_gcost = 0;
+ if (in_lists) {
+ current_gcost = current_best->second.g;
+ if (current_gcost <= lowest_gcost + 1.0)
+ continue;
}
- const double new_cost =
obj->cost(locs[j],lowest->second.g);
+ double const new_cost = obj->cost(locs[j],
lowest_gcost);
- const node nd(locs[j],dst,lowest->second.g+new_cost,
+ node const nd(locs[j], dst, lowest_gcost + new_cost,
lowest->second.loc,teleports);
- if(current_best != closed_list.end()) {
- if(current_best->second.g <= nd.g) {
+ if (in_lists) {
+ if (current_gcost <= nd.g) {
continue;
} else if(in_open) {
typedef
std::multimap<double,location>::iterator Itor;
- [Wesnoth-cvs-commits] wesnoth/src pathfind.cpp,
Guillaume Melquiond <=