[Wesnoth-cvs-commits] wesnoth/src pathfind.cpp

[Guillaume Melquiond]

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;