Author: alink
Date: Thu Oct 22 02:08:22 2009
New Revision: 39406
URL: http://svn.gna.org/viewcvs/wesnoth?rev=39406&view=rev
Log:
recommit r39364 'Optimize "paths" pathfinding function'
with more comments explaining why it's a valid change.
(code could be even more simplified but didn't touch it more for now)
Modified:
trunk/src/pathfind.cpp
Modified: trunk/src/pathfind.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/pathfind.cpp?rev=39406&r1=39405&r2=39406&view=diff
==============================================================================
--- trunk/src/pathfind.cpp (original)
+++ trunk/src/pathfind.cpp Thu Oct 22 02:08:22 2009
@@ -232,9 +232,15 @@
bool next_visited = next.in - search_counter <= 1u;
- // test if the current path to locs[i] is better than
this one could possibly be.
- // we do this a couple more times below
- if (next_visited && !(n < next)) continue;
+ // Classic Dijkstra allow to skip chosen nodes (with
next.in==search_counter)
+ // But the cost function and hex grid allow to also
skip visited nodes:
+ // if next was visited, then we already have a path
'src-..-n2-next'
+ // - n2 was chosen before n, meaning that it is nearer
to src.
+ // - the cost of 'n-next' can't be smaller than
'n2-next' because
+ // cost is independent of direction and we don't have
more MP at n
+ // (important because more MP may allow to avoid
waiting next turn)
+ // Thus, 'src-..-n-next' can't be shorter.
+ if (next_visited) continue;
const int move_cost = u.movement_cost(map[locs[i]]);
@@ -248,8 +254,6 @@
t.movement_left -= move_cost;
- if (next_visited && !(t < next)) continue;
-
if (!ignore_units) {
const unit *v =
get_visible_unit(units, locs[i],
viewing_team, see_all);
@@ -261,27 +265,22 @@
&&
!u.get_ability_bool("skirmisher", locs[i])) {
t.movement_left = 0;
}
-
- if (next_visited && !(t < next)) continue;
}
- if (!next_visited)
- {
- ++nb_dest;
- int x = locs[i].x;
- if (x < xmin) xmin = x;
- if (xmax < x) xmax = x;
- int y = locs[i].y;
- if (y < ymin) ymin = y;
- if (ymax < y) ymax = y;
- }
+ ++nb_dest;
+ int x = locs[i].x;
+ if (x < xmin) xmin = x;
+ if (xmax < x) xmax = x;
+ int y = locs[i].y;
+ if (y < ymin) ymin = y;
+ if (ymax < y) ymax = y;
bool in_list = next.in == search_counter + 1;
t.in = search_counter + 1;
next = t;
// if already in the priority queue then we just update
it, else push it.
- if (in_list) {
+ if (in_list) { // never happen see next_visited above
std::push_heap(pq.begin(),
std::find(pq.begin(), pq.end(), index(locs[i])) + 1, node_comp);
} else {
pq.push_back(index(locs[i]));
_______________________________________________
Wesnoth-commits mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-commits
