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

[Guillaume Melquiond]

CVSROOT:        /cvsroot/wesnoth
Module name:    wesnoth
Branch:         
Changes by:     Guillaume Melquiond <address@hidden>    05/06/05 07:03:43

Modified files:
        src            : pathfind.cpp pathfind.hpp 

Log message:
        Fixes bug #11480, #13295, indentation of prototypes, and some constness 
issue. Also improves performance of cost calculation by caching the values that 
are needed for each hex. As for the bug fixes: the cost calculator now 
correctly handles unreachable hex; if the terrain cost is 100, it doesn't say 
aymore that a 5mp unit can reach it in 20 turns.

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.cpp.diff?tr1=1.68&tr2=1.69&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.hpp.diff?tr1=1.37&tr2=1.38&r1=text&r2=text

Patches:
Index: wesnoth/src/pathfind.cpp
diff -u wesnoth/src/pathfind.cpp:1.68 wesnoth/src/pathfind.cpp:1.69
--- wesnoth/src/pathfind.cpp:1.68       Sat Jun  4 22:46:32 2005
+++ wesnoth/src/pathfind.cpp    Sun Jun  5 07:03:43 2005
@@ -1,4 +1,4 @@
-/* $Id: pathfind.cpp,v 1.68 2005/06/04 22:46:32 silene Exp $ */
+/* $Id: pathfind.cpp,v 1.69 2005/06/05 07:03:43 silene Exp $ */
 /*
 Copyright (C) 2003 by David White <address@hidden>
 Part of the Battle for Wesnoth Project http://www.wesnoth.org/
@@ -403,14 +403,14 @@
                const gamemap::location& loc,
                int move_left,
                std::map<gamemap::location,paths::route>& routes,
-               std::vector<team>& teams,
+               std::vector<team> const &teams,
                bool ignore_zocs, bool allow_teleport, int turns_left, bool 
starting_pos)
        {
                if(size_t(u.side()-1) >= teams.size()) {
                        return;
                }
 
-               team& current_team = teams[u.side()-1];
+               team const &current_team = teams[u.side()-1];
 
                //find adjacent tiles
                std::vector<gamemap::location> locs(6);
@@ -499,7 +499,7 @@
              game_data const &gamedata,
              std::map<gamemap::location, unit> const &units,
              gamemap::location const &loc,
-             std::vector<team> &teams,
+             std::vector<team> const &teams,
              bool ignore_zocs, bool allow_teleport, int additional_turns)
 {
        const std::map<gamemap::location,unit>::const_iterator i = 
units.find(loc);
@@ -541,8 +541,11 @@
 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)
+       : unit_(u), team_(t), units_(units), teams_(teams), map_(map),
+         lawful_bonus_(status.get_time_of_day().lawful_bonus),
+         unit_is_skirmisher_(unit_.type().is_skirmisher()),
+         movement_left_(unit_.movement_left()),
+         total_movement_(unit_.total_movement())
 {
 }
 
@@ -550,46 +553,51 @@
 {
        wassert(map_.on_board(loc));
 
+       //the location is not valid
+       //1. if the loc is shrouded, or
+       //2. if moving in it costs more than the total movement of the unit, or
+       //3. if there is a visible enemy on the hex, or
+       //4. if the unit is not a skirmisher and there is a visible enemy with
+       //   a ZoC on an adjacent hex in the middle of the route
+
        if (team_.shrouded(loc.x, loc.y))
-               return (getNoPathValue());
+               return getNoPathValue();
 
-       const unit_map::const_iterator enemy_unit = find_visible_unit(units_, 
loc, map_, status_.get_time_of_day().lawful_bonus, teams_, team_);
+       int const base_cost = unit_.movement_cost(map_, map_[loc.x][loc.y]);
+       wassert(base_cost >= 1); // pathfinding heuristic: the cost must be at 
least 1
+       if (total_movement_ < base_cost)
+               return getNoPathValue();
+
+       unit_map::const_iterator
+               enemy_unit = find_visible_unit(units_, loc, map_, 
lawful_bonus_, teams_, team_),
+               units_end = units_.end();
 
-       if (enemy_unit != units_.end() && 
team_.is_enemy(enemy_unit->second.side()))
-               return (getNoPathValue());
+       if (enemy_unit != units_end && 
team_.is_enemy(enemy_unit->second.side()))
+               return getNoPathValue();
 
-       if ((isDst == false) && (unit_.type().is_skirmisher() == false))
-       {
+       if (!isDst && !unit_is_skirmisher_) {
                gamemap::location adj[6];
-               get_adjacent_tiles(loc,adj);
+               get_adjacent_tiles(loc, adj);
 
                for (size_t i = 0; i != 6; ++i) {
-                       const unit_map::const_iterator u = 
find_visible_unit(units_, adj[i],map_, status_.get_time_of_day().lawful_bonus, 
teams_, team_);
+                       enemy_unit = find_visible_unit(units_, adj[i], map_, 
lawful_bonus_, teams_, team_);
 
-                       if (u != units_.end() && 
team_.is_enemy(u->second.side()) &&
-                           !team_.fogged(adj[i].x, adj[i].y) && 
u->second.emits_zoc()) {
-                               return (getNoPathValue());
-                       }
+                       if (enemy_unit != units_end && 
team_.is_enemy(enemy_unit->second.side()) &&
+                           !team_.fogged(adj[i].x, adj[i].y) && 
enemy_unit->second.emits_zoc())
+                               return getNoPathValue();
                }
        }
 
-       int const base_cost = unit_.movement_cost(map_, map_[loc.x][loc.y]);
+       //compute how many movement points are left in the game turn needed to
+       //reach the previous hex
+       //total_movement_ is not zero, thanks to the pathfinding heuristic
+       int remaining_movement = movement_left_ - static_cast<int>(so_far);
+       if (remaining_movement < 0)
+               remaining_movement = total_movement_ - (-remaining_movement) % 
total_movement_;
 
        //supposing we had 2 movement left, and wanted to move onto a hex which
        //takes 3 movement, it's going to cost us 5 movement in total, since we
        //sacrifice this turn's movement. Take that into account here.
-       const int current_cost(static_cast<int>(so_far));
-
-       const int starting_movement = unit_.movement_left();
-       int remaining_movement = starting_movement - current_cost;
-       if (remaining_movement < 0) {
-               const int total = unit_.total_movement();
-               if (total != 0) {
-                       remaining_movement = total - (-remaining_movement) % 
total;
-               }
-       }
-
        int additional_cost = base_cost > remaining_movement ? 
remaining_movement : 0;
-
        return base_cost + additional_cost;
 }
Index: wesnoth/src/pathfind.hpp
diff -u wesnoth/src/pathfind.hpp:1.37 wesnoth/src/pathfind.hpp:1.38
--- wesnoth/src/pathfind.hpp:1.37       Sat Jun  4 19:16:05 2005
+++ wesnoth/src/pathfind.hpp    Sun Jun  5 07:03:43 2005
@@ -1,4 +1,4 @@
-/* $Id: pathfind.hpp,v 1.37 2005/06/04 19:16:05 ott Exp $ */
+/* $Id: pathfind.hpp,v 1.38 2005/06/05 07:03:43 silene Exp $ */
 /*
    Copyright (C) 2003 by David White <address@hidden>
    Part of the Battle for Wesnoth Project http://www.wesnoth.org/
@@ -51,10 +51,10 @@
                                    VACANT_TILE_TYPE vacancy=VACANT_ANY);
 
 //function which determines if a given location is an enemy zone of control
-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 &current_team, int side);
 
 struct cost_calculator
 {
@@ -75,11 +75,11 @@
        //additional_turns: if 0, paths for how far the unit can move this turn
        //will be calculated. If 1, paths for how far the unit can move by the
        //end of next turn will be calculated, and so forth.
-       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=0);
+       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> const &teams,
+             bool ignore_zocs, bool allow_teleport, int additional_turns = 0);
 
        //structure which holds a single route between one location and another.
        struct route
@@ -94,9 +94,9 @@
 };
 
 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 = NULL);
+                           double stop_at, cost_calculator const 
*costCalculator,
+                           const size_t parWidth, const size_t parHeight,
+                           std::set<gamemap::location> const *teleports = 
NULL);
 
 //function which, given a unit and a route the unit can move on, will
 //return the number of turns it will take the unit to traverse the route.
@@ -111,12 +111,15 @@
        virtual double cost(const gamemap::location& loc, const double so_far, 
const bool isDst) const;
 
 private:
-       const unit& unit_;
-       const team& team_;
-       const unit_map& units_;
-       const std::vector<team>& teams_;
-       const gamemap& map_;
-       const gamestatus& status_;
+       unit const &unit_;
+       team const &team_;
+       unit_map const &units_;
+       std::vector<team> const &teams_;
+       gamemap const &map_;
+       int const lawful_bonus_;
+       bool const unit_is_skirmisher_;
+       int const movement_left_;
+       int const total_movement_;
 };
 
 #endif