Author: silene
Date: Sat May 2 14:22:20 2009
New Revision: 35411
URL: http://svn.gna.org/viewcvs/wesnoth?rev=35411&view=rev
Log:
Separated A* routes from Dijkstra routes. Renamed move_left to move_cost along
the way.
Modified:
trunk/src/actions.cpp
trunk/src/ai/ai.cpp
trunk/src/ai/ai_actions.hpp
trunk/src/ai/ai_move.cpp
trunk/src/ai/formula_ai.cpp
trunk/src/ai/formula_ai.hpp
trunk/src/astarsearch.cpp
trunk/src/cavegen.cpp
trunk/src/game_events.cpp
trunk/src/mapgen.cpp
trunk/src/mouse_events.cpp
trunk/src/pathfind.cpp
trunk/src/pathfind.hpp
Modified: trunk/src/actions.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/actions.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/actions.cpp (original)
+++ trunk/src/actions.cpp Sat May 2 14:22:20 2009
@@ -120,12 +120,8 @@
// The limit computed in the third argument is more than enough for
// any convex castle on the map. Strictly speaking it could be
// reduced to sqrt(map.w()**2 + map.h()**2).
- const paths::route& rt = a_star_search(leader, loc, map.w()+map.h(),
&calc, map.w(), map.h());
-
- if(rt.steps.empty())
- return false;
-
- return true;
+ plain_route rt = a_star_search(leader, loc, map.w()+map.h(), &calc,
map.w(), map.h());
+ return !rt.steps.empty();
}
std::string recruit_unit(const gamemap& map, const int side, unit_map& units,
Modified: trunk/src/ai/ai.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/ai/ai.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/ai/ai.cpp (original)
+++ trunk/src/ai/ai.cpp Sat May 2 14:22:20 2009
@@ -1381,12 +1381,12 @@
for(std::vector<target>::const_iterator t = targets.begin(); t
!= targets.end(); ++t) {
LOG_AI << "analyzing '" << *i << "' getting to
target...\n";
- const paths::route& route = a_star_search(start,
t->loc, 100.0, &calc,
+ plain_route route = a_star_search(start, t->loc, 100.0,
&calc,
get_info().map.w(), get_info().map.h());
- if(route.steps.empty() == false) {
- LOG_AI << "made it: " << route.move_left <<
"\n";
- cost += route.move_left;
+ if (!route.steps.empty()) {
+ LOG_AI << "made it: " << route.move_cost <<
"\n";
+ cost += route.move_cost;
++targets_reached;
} else {
LOG_AI << "failed\n";
@@ -1570,7 +1570,7 @@
do_recruitment();
shortest_path_calculator calc(leader->second, current_team(), units_,
teams_, map_);
- const paths::route route = a_star_search(leader->first, dst, 1000.0,
&calc,
+ plain_route route = a_star_search(leader->first, dst, 1000.0, &calc,
get_info().map.w(), get_info().map.h());
if(route.steps.empty()) {
LOG_AI << "route empty";
Modified: trunk/src/ai/ai_actions.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/ai/ai_actions.hpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/ai/ai_actions.hpp (original)
+++ trunk/src/ai/ai_actions.hpp Sat May 2 14:22:20 2009
@@ -159,7 +159,7 @@
const map_location& from_;
const map_location& to_;
bool remove_movement_;
- paths::route route_;
+ plain_route route_;
};
class ai_recruit_result : public ai_action_result {
Modified: trunk/src/ai/ai_move.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/ai/ai_move.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/ai/ai_move.cpp (original)
+++ trunk/src/ai/ai_move.cpp Sat May 2 14:22:20 2009
@@ -437,7 +437,7 @@
assert(map_.on_board(ittg->loc));
}
- paths::route best_route;
+ plain_route best_route;
unit_map::iterator best = units_.end();
double best_rating = 0.1;
@@ -480,32 +480,32 @@
// to it seeming futile. Be very cautious about changing this
value,
// as it can cause the AI to give up on searches and just do
nothing.
const double locStopValue = 500.0;
- paths::route cur_route = a_star_search(u->first, tg->loc,
locStopValue, &cost_calc, map_.w(), map_.h());
-
- if (cur_route.move_left == cost_calc.getNoPathValue()) {
+ plain_route cur_route = a_star_search(u->first, tg->loc,
locStopValue, &cost_calc, map_.w(), map_.h());
+
+ if (cur_route.steps.empty()) {
LOG_AI << "Can't reach target: " << locStopValue << " =
" << tg->value << "/" << best_rating << "\n";
continue;
}
- if (cur_route.move_left < locStopValue)
+ if (cur_route.move_cost < locStopValue)
{
// if this unit can move to that location this turn, it
has a very very low cost
typedef
std::multimap<map_location,map_location>::const_iterator multimapItor;
std::pair<multimapItor,multimapItor> locRange =
dstsrc.equal_range(u->first);
while (locRange.first != locRange.second) {
if (locRange.first->second == u->first) {
- cur_route.move_left = 0;
+ cur_route.move_cost = 0;
}
++locRange.first;
}
}
- double rating = tg->value/std::max<int>(1,cur_route.move_left);
+ double rating = tg->value / std::max<int>(1,
cur_route.move_cost);
//for 'support' targets, they are rated much higher if we can
get there within two turns,
//otherwise they are worthless to go for at all.
if(tg->type == target::SUPPORT) {
- if(cur_route.move_left <= u->second.movement_left()*2) {
+ if(cur_route.move_cost <= u->second.movement_left()*2) {
rating *= 10.0;
} else {
rating = 0.0;
@@ -538,7 +538,7 @@
}
}
- LOG_AI << tg->value << "/" << cur_route.move_left << " = " <<
rating << "\n";
+ LOG_AI << tg->value << "/" << cur_route.move_cost << " = " <<
rating << "\n";
if(best_target == targets.end() || rating > best_rating) {
best_rating = rating;
best_target = tg;
@@ -585,27 +585,27 @@
const move_cost_calculator calc(u->second, map_,
units_, u->first, dstsrc, enemy_dstsrc);
const double locStopValue = std::min(best_target->value
/ best_rating, 100.0);
- paths::route cur_route = a_star_search(u->first,
best_target->loc, locStopValue, &calc, map_.w(), map_.h());
-
- if (cur_route.move_left < locStopValue)
+ plain_route cur_route = a_star_search(u->first,
best_target->loc, locStopValue, &calc, map_.w(), map_.h());
+
+ if (cur_route.move_cost < locStopValue)
{
// if this unit can move to that location this
turn, it has a very very low cost
typedef
std::multimap<map_location,map_location>::const_iterator multimapItor;
std::pair<multimapItor,multimapItor> locRange =
dstsrc.equal_range(u->first);
while (locRange.first != locRange.second) {
if (locRange.first->second == u->first)
{
- cur_route.move_left = 0;
+ cur_route.move_cost = 0;
}
++locRange.first;
}
}
- double rating =
best_target->value/std::max<int>(1,cur_route.move_left);
+ double rating = best_target->value / std::max<int>(1,
cur_route.move_cost);
//for 'support' targets, they are rated much higher if
we can get there within two turns,
//otherwise they are worthless to go for at all.
if(best_target->type == target::SUPPORT) {
- if(cur_route.move_left <=
u->second.movement_left()*2) {
+ if (cur_route.move_cost <=
u->second.movement_left()*2) {
rating *= 10.0;
} else {
rating = 0.0;
@@ -857,7 +857,7 @@
const location& loc = i->second;
if (int(distance_between(loc,dst)) <=
u_it->second.total_movement()) {
shortest_path_calculator calc(u_it->second,
current_team(), units_, teams_, map_);
- const paths::route& rt = a_star_search(loc, dst,
u_it->second.total_movement(), &calc, map_.w(), map_.h());
+ plain_route rt = a_star_search(loc, dst,
u_it->second.total_movement(), &calc, map_.w(), map_.h());
if(rt.steps.empty() == false) {
out.push_back(loc);
}
Modified: trunk/src/ai/formula_ai.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/ai/formula_ai.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/ai/formula_ai.cpp (original)
+++ trunk/src/ai/formula_ai.cpp Sat May 2 14:22:20 2009
@@ -696,7 +696,7 @@
std::set<map_location> allowed_teleports =
ai_.get_allowed_teleports(unit_it);
- paths::route route = ai_.shortest_path_calculator( src, dst,
unit_it, allowed_teleports );
+ plain_route route = ai_.shortest_path_calculator( src, dst,
unit_it, allowed_teleports );
if( route.steps.size() < 2 ) {
return variant(&locations);
@@ -747,7 +747,7 @@
emergency_path_calculator em_calc(unit_it->second,
ai_.get_info().map);
- paths::route route = a_star_search(src, dst, 1000.0, &em_calc,
ai_.get_info().map.w(), ai_.get_info().map.h(), &allowed_teleports);
+ plain_route route = a_star_search(src, dst, 1000.0, &em_calc,
ai_.get_info().map.w(), ai_.get_info().map.h(), &allowed_teleports);
if( route.steps.size() < 2 ) {
return variant(&locations);
@@ -1915,8 +1915,10 @@
return res;
}
-paths::route formula_ai::shortest_path_calculator(const map_location& src,
const map_location& dst, unit_map::iterator& unit_it, std::set<map_location>&
allowed_teleports) const {
-
+plain_route formula_ai::shortest_path_calculator(const map_location &src,
+ const map_location &dst, unit_map::iterator &unit_it,
+ std::set<map_location> & allowed_teleports) const
+{
map_location destination = dst;
::shortest_path_calculator calc(unit_it->second, current_team(), units_,
get_info().teams, get_info().map);
@@ -1960,7 +1962,7 @@
destination = res;
}
- paths::route route = a_star_search(src, destination, 1000.0, &calc,
+ plain_route route = a_star_search(src, destination, 1000.0, &calc,
get_info().map.w(), get_info().map.h(), &allowed_teleports);
return route;
@@ -1997,7 +1999,7 @@
std::set<map_location> allowed_teleports =
get_allowed_teleports(unit_it);
//destination is too far, check where unit can go
- paths::route route = shortest_path_calculator( src, dst, unit_it,
allowed_teleports );
+ plain_route route = shortest_path_calculator( src, dst,
unit_it, allowed_teleports );
if( route.steps.size() == 0 ) {
emergency_path_calculator em_calc(unit_it->second,
get_info().map);
Modified: trunk/src/ai/formula_ai.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/ai/formula_ai.hpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/ai/formula_ai.hpp (original)
+++ trunk/src/ai/formula_ai.hpp Sat May 2 14:22:20 2009
@@ -113,7 +113,7 @@
void handle_exception(game_logic::formula_error& e, const std::string&
failed_operation) const;
std::set<map_location> get_allowed_teleports(unit_map::iterator&
unit_it) const;
- paths::route shortest_path_calculator(const map_location& src, const
map_location& dst, unit_map::iterator& unit_it, std::set<map_location>&
allowed_teleports) const;
+ plain_route shortest_path_calculator(const map_location& src, const
map_location& dst, unit_map::iterator& unit_it, std::set<map_location>&
allowed_teleports) const;
void invalidate_move_maps() const { move_maps_valid_ = false; }
Modified: trunk/src/astarsearch.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/astarsearch.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/astarsearch.cpp (original)
+++ trunk/src/astarsearch.cpp Sat May 2 14:22:20 2009
@@ -107,7 +107,7 @@
}
-paths::route a_star_search(const map_location& src, const map_location& dst,
+plain_route a_star_search(const map_location& src, const map_location& dst,
double stop_at, const cost_calculator *calc, const
size_t width,
const size_t height, const std::set<map_location>*
teleports_ptr) {
//----------------- PRE_CONDITIONS ------------------
@@ -122,8 +122,8 @@
if (calc->cost(src,dst, 0) >= stop_at) {
LOG_PF << "aborted A* search because Start or Dest is
invalid\n";
- paths::route locRoute;
- locRoute.move_left = int(calc->getNoPathValue());
+ plain_route locRoute;
+ locRoute.move_cost = int(calc->getNoPathValue());
return locRoute;
}
@@ -180,12 +180,11 @@
}
}
}
-
-
- paths::route route;
+
+ plain_route route;
if (nodes[index(dst)].g < stop_at) {
DBG_PF << "found solution; calculating it...\n";
- route.move_left = (int)nodes[index(dst)].g;
+ route.move_cost = (int)nodes[index(dst)].g;
for (node curr = nodes[index(dst)]; curr.prev !=
map_location::null_location; curr = nodes[index(curr.prev)]) {
route.steps.push_back(curr.curr);
}
@@ -193,11 +192,10 @@
std::reverse(route.steps.begin(), route.steps.end());
} else {
LOG_PF << "aborted a* search " << "\n";
- route.move_left = (int)calc->getNoPathValue();
+ route.move_cost = (int)calc->getNoPathValue();
}
return route;
-
}
static void get_tiles_radius_internal(const map_location& a, size_t radius,
Modified: trunk/src/cavegen.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/cavegen.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/cavegen.cpp (original)
+++ trunk/src/cavegen.cpp Sat May 2 14:22:20 2009
@@ -325,7 +325,7 @@
passage_path_calculator calc(map_,wall_,laziness,windiness);
- const paths::route rt = a_star_search(p.src, p.dst, 10000.0, &calc,
width_, height_);
+ plain_route rt = a_star_search(p.src, p.dst, 10000.0, &calc, width_,
height_);
const size_t width = std::max<size_t>(1,atoi(p.cfg["width"].c_str()));
Modified: trunk/src/game_events.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/game_events.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/game_events.cpp (original)
+++ trunk/src/game_events.cpp Sat May 2 14:22:20 2009
@@ -1092,7 +1092,7 @@
break;
}
- paths::route route = a_star_search(src, dst,
10000, &calc,
+ plain_route route = a_star_search(src, dst,
10000, &calc,
game_map->w(), game_map->h());
if (route.steps.size() == 0) {
Modified: trunk/src/mapgen.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/mapgen.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/mapgen.cpp (original)
+++ trunk/src/mapgen.cpp Sat May 2 14:22:20 2009
@@ -1057,7 +1057,7 @@
}
// Search a path out for the road
- const paths::route rt = a_star_search(src, dst, 10000.0, &calc,
width, height);
+ plain_route rt = a_star_search(src, dst, 10000.0, &calc, width,
height);
std::string road_base_name;
const std::string& name = generate_name(name_generator,
"road_name", &road_base_name);
Modified: trunk/src/mouse_events.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/mouse_events.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/mouse_events.cpp (original)
+++ trunk/src/mouse_events.cpp Sat May 2 14:22:20 2009
@@ -322,7 +322,7 @@
allowed_teleports.insert(*i);
}
}
- paths::route route = a_star_search(un->first, go_to, 10000.0, &calc,
map_.w(), map_.h(), &allowed_teleports);
+ plain_route route = a_star_search(un->first, go_to, 10000.0, &calc,
map_.w(), map_.h(), &allowed_teleports);
return mark_route(route, un->second, viewing_team(),
units_,teams_,map_);
}
Modified: trunk/src/pathfind.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/pathfind.cpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/pathfind.cpp (original)
+++ trunk/src/pathfind.cpp Sat May 2 14:22:20 2009
@@ -297,7 +297,7 @@
see_all, ignore_units);
}
-marked_route mark_route(const paths::route &rt, const unit &u,
+marked_route mark_route(const plain_route &rt, const unit &u,
const team &viewing_team, const unit_map &units,
const std::vector<team> &teams, const gamemap &map)
{
Modified: trunk/src/pathfind.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/pathfind.hpp?rev=35411&r1=35410&r2=35411&view=diff
==============================================================================
--- trunk/src/pathfind.hpp (original)
+++ trunk/src/pathfind.hpp Sat May 2 14:22:20 2009
@@ -136,9 +136,18 @@
};
-std::ostream& operator << (std::ostream& os, const paths::route& rt);
-
-paths::route a_star_search(map_location const &src, map_location const &dst,
+//std::ostream& operator << (std::ostream& os, const paths::route& rt);
+
+/** Structure which holds a single route between one location and another. */
+struct plain_route
+{
+ plain_route() : steps(), move_cost(0) {}
+ std::vector<map_location> steps;
+ /** Movement cost for reaching the end of the route. */
+ int move_cost;
+};
+
+plain_route a_star_search(map_location const &src, map_location const &dst,
double stop_at, cost_calculator const
*costCalculator,
const size_t parWidth, const size_t parHeight,
std::set<map_location> const *teleports = NULL);
@@ -146,7 +155,7 @@
/**
* Marks a route @a rt with waypoints assuming that a @unit u travels along it.
*/
-marked_route mark_route(const paths::route &rt, const unit &u,
+marked_route mark_route(const plain_route &rt, const unit &u,
const team &viewing_team, const unit_map &units,
const std::vector<team> &teams, const gamemap &map);
_______________________________________________
Wesnoth-commits mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-commits
