[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Wesnoth-cvs-commits] wesnoth/src actions.cpp ai.cpp ai_move.cpp cave...
|
From: |
Guillaume Melquiond |
|
Subject: |
[Wesnoth-cvs-commits] wesnoth/src actions.cpp ai.cpp ai_move.cpp cave... |
|
Date: |
Sun, 05 Dec 2004 17:20:50 -0500 |
CVSROOT: /cvsroot/wesnoth
Module name: wesnoth
Branch:
Changes by: Guillaume Melquiond <address@hidden> 04/12/05 22:14:30
Modified files:
src : actions.cpp ai.cpp ai_move.cpp cavegen.cpp
game_events.cpp mapgen.cpp pathfind.cpp
pathfind.hpp playturn.cpp
Log message:
Remove A* from the header and put it into a single object file. It
reduces compile time, and it could speed up the AI.
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/actions.cpp.diff?tr1=1.171&tr2=1.172&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/ai.cpp.diff?tr1=1.127&tr2=1.128&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/ai_move.cpp.diff?tr1=1.52&tr2=1.53&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/cavegen.cpp.diff?tr1=1.9&tr2=1.10&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/game_events.cpp.diff?tr1=1.115&tr2=1.116&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/mapgen.cpp.diff?tr1=1.46&tr2=1.47&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.cpp.diff?tr1=1.47&tr2=1.48&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.hpp.diff?tr1=1.33&tr2=1.34&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/playturn.cpp.diff?tr1=1.308&tr2=1.309&r1=text&r2=text
Patches:
Index: wesnoth/src/actions.cpp
diff -u wesnoth/src/actions.cpp:1.171 wesnoth/src/actions.cpp:1.172
--- wesnoth/src/actions.cpp:1.171 Sun Dec 5 18:37:36 2004
+++ wesnoth/src/actions.cpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: actions.cpp,v 1.171 2004/12/05 18:37:36 silene Exp $ */
+/* $Id: actions.cpp,v 1.172 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -42,12 +42,12 @@
#define LOG_NG lg::info(lg::engine)
#define ERR_NW lg::err(lg::network)
-struct castle_cost_calculator
+struct castle_cost_calculator : cost_calculator
{
castle_cost_calculator(const gamemap& map) : map_(map)
{}
- double cost(const gamemap::location& loc, double cost_so_far) const
+ virtual double cost(const gamemap::location& loc, double) const
{
if(!map_.is_castle(loc))
return 10000;
@@ -104,8 +104,8 @@
}
if(need_castle && map.on_board(recruit_location)) {
- const paths::route& rt =
a_star_search(u->first,recruit_location,
-
100.0,castle_cost_calculator(map));
+ castle_cost_calculator calc(map);
+ const paths::route& rt = a_star_search(u->first,
recruit_location, 100.0, &calc);
if(rt.steps.empty() || units.find(recruit_location) !=
units.end() ||
!map.is_castle(recruit_location))
recruit_location = gamemap::location();
@@ -448,8 +448,8 @@
if (strings && resist != 0) {
std::stringstream str_resist;
str_resist << gettext(resist < 0 ? N_("defender resistance vs")
: N_("defender vulnerability vs"))
- << ' ' << gettext(attack.type().c_str()) << EMPTY_COLUMN
- << (resist > 0 ? "+" : "") << resist << '%';
+ << ' ' << gettext(attack.type().c_str()) <<
EMPTY_COLUMN
+ << (resist > 0 ? "+" : "") << resist << '%';
strings->attack_calculations.push_back(str_resist.str());
}
@@ -468,7 +468,7 @@
if (under_leadership(units,attacker,&leader_bonus).valid()) {
percent += leader_bonus;
- if(strings) {
+ if (strings) {
std::stringstream str;
str << _("leadership") << EMPTY_COLUMN << '+' <<
leader_bonus << '%';
strings->attack_calculations.push_back(str.str());
Index: wesnoth/src/ai.cpp
diff -u wesnoth/src/ai.cpp:1.127 wesnoth/src/ai.cpp:1.128
--- wesnoth/src/ai.cpp:1.127 Sun Dec 5 18:37:36 2004
+++ wesnoth/src/ai.cpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: ai.cpp,v 1.127 2004/12/05 18:37:36 silene Exp $ */
+/* $Id: ai.cpp,v 1.128 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -1504,7 +1504,7 @@
const shortest_path_calculator
calc(temp_unit,current_team(),units,teams_,map_,state_);
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);
+ const paths::route& route = a_star_search(start,
t->loc, 100.0, &calc);
if(route.steps.empty() == false) {
LOG_AI << "made it: " << route.move_left <<
"\n";
cost += route.move_left;
@@ -1651,7 +1651,8 @@
do_recruitment();
- const paths::route route =
a_star_search(leader->first,dst,1000.0,shortest_path_calculator(leader->second,current_team(),units_,teams_,map_,state_));
+ shortest_path_calculator calc(leader->second, current_team(), units_,
teams_, map_, state_);
+ const paths::route route = a_star_search(leader->first, dst, 1000.0,
&calc);
if(route.steps.empty()) {
LOG_AI << "route empty";
return;
Index: wesnoth/src/ai_move.cpp
diff -u wesnoth/src/ai_move.cpp:1.52 wesnoth/src/ai_move.cpp:1.53
--- wesnoth/src/ai_move.cpp:1.52 Thu Nov 18 22:00:12 2004
+++ wesnoth/src/ai_move.cpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: ai_move.cpp,v 1.52 2004/11/18 22:00:12 ydirson Exp $ */
+/* $Id: ai_move.cpp,v 1.53 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -24,7 +24,7 @@
#define LOG_AI lg::info(lg::ai)
-struct move_cost_calculator
+struct move_cost_calculator : cost_calculator
{
move_cost_calculator(const unit& u, const gamemap& map,
const game_data& data,
@@ -37,7 +37,7 @@
avoid_enemies_(u.type().usage() == "scout")
{}
- double cost(const gamemap::location& loc, double so_far) const
+ virtual double cost(const gamemap::location& loc, double) const
{
if(!map_.on_board(loc))
return 1000.0;
@@ -425,7 +425,7 @@
assert(map_.on_board(tg->loc));
const paths::route cur_route = a_star_search(u->first,tg->loc,
-
minimum(tg->value/best_rating,500.0),cost_calc);
+ minimum(tg->value/best_rating,500.0),
&cost_calc);
double rating = tg->value/maximum<int>(1,cur_route.move_left);
@@ -493,7 +493,7 @@
const move_cost_calculator
calc(u->second,map_,gameinfo_,units_,u->first,dstsrc,enemy_dstsrc);
const paths::route cur_route =
a_star_search(u->first,best_target->loc,
-
minimum(best_target->value/best_rating,100.0),calc);
+ minimum(best_target->value /
best_rating, 100.0), &calc);
double rating =
best_target->value/maximum<int>(1,cur_route.move_left);
//for 'support' targets, they are rated much higher if
we can get there within two turns,
@@ -742,7 +742,8 @@
for(move_map::const_iterator i = locs.first; i != locs.second; ++i) {
const location& loc = i->second;
if(distance_between(loc,dst) <= u_it->second.total_movement()) {
- const paths::route& rt =
a_star_search(loc,dst,u_it->second.total_movement(),shortest_path_calculator(u_it->second,current_team(),units_,teams_,map_,state_));
+ shortest_path_calculator calc(u_it->second,
current_team(), units_, teams_, map_, state_);
+ const paths::route& rt = a_star_search(loc, dst,
u_it->second.total_movement(), &calc);
if(rt.steps.empty() == false) {
out.push_back(loc);
}
Index: wesnoth/src/cavegen.cpp
diff -u wesnoth/src/cavegen.cpp:1.9 wesnoth/src/cavegen.cpp:1.10
--- wesnoth/src/cavegen.cpp:1.9 Thu Nov 18 04:08:32 2004
+++ wesnoth/src/cavegen.cpp Sun Dec 5 22:14:29 2004
@@ -262,13 +262,13 @@
}
}
-struct passage_path_calculator
+struct passage_path_calculator : cost_calculator
{
passage_path_calculator(const std::vector<std::vector<gamemap::TERRAIN>
>& mapdata, gamemap::TERRAIN wall, double laziness, size_t windiness)
: map_(mapdata), wall_(wall), laziness_(laziness),
windiness_(windiness)
{}
- double cost(const gamemap::location& loc, double so_far) const;
+ virtual double cost(const gamemap::location& loc, double so_far) const;
private:
const std::vector<std::vector<gamemap::TERRAIN> >& map_;
gamemap::TERRAIN wall_;
@@ -276,7 +276,7 @@
size_t windiness_;
};
-double passage_path_calculator::cost(const gamemap::location& loc, double
so_far) const
+double passage_path_calculator::cost(const gamemap::location& loc, double)
const
{
if(loc.x < 0 || loc.y < 0 || size_t(loc.x) >= map_.size() ||
map_.empty() || size_t(loc.y) >= map_.front().size()) {
return 100000.0;
@@ -307,7 +307,7 @@
passage_path_calculator calc(map_,wall_,laziness,windiness);
- const paths::route rt = a_star_search(p.src,p.dst,10000.0,calc);
+ const paths::route rt = a_star_search(p.src, p.dst, 10000.0, &calc);
const size_t width = maximum<size_t>(1,atoi(p.cfg["width"].c_str()));
const size_t jagged = atoi(p.cfg["jagged"].c_str());
Index: wesnoth/src/game_events.cpp
diff -u wesnoth/src/game_events.cpp:1.115 wesnoth/src/game_events.cpp:1.116
--- wesnoth/src/game_events.cpp:1.115 Sat Dec 4 23:44:09 2004
+++ wesnoth/src/game_events.cpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: game_events.cpp,v 1.115 2004/12/04 23:44:09 isaaccp Exp $ */
+/* $Id: game_events.cpp,v 1.116 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -481,7 +481,7 @@
dst.x = atoi(xvals[i].c_str())-1;
dst.y = atoi(yvals[i].c_str())-1;
- paths::route
route=a_star_search(src,dst,10000,calc,0);
+ paths::route route=a_star_search(src, dst,
10000, &calc, 0);
unit_display::move_unit(*screen, *game_map,
route.steps,
dummy_unit,status_ptr->get_time_of_day(), *units, *teams);
Index: wesnoth/src/mapgen.cpp
diff -u wesnoth/src/mapgen.cpp:1.46 wesnoth/src/mapgen.cpp:1.47
--- wesnoth/src/mapgen.cpp:1.46 Thu Nov 18 04:08:32 2004
+++ wesnoth/src/mapgen.cpp Sun Dec 5 22:14:29 2004
@@ -338,14 +338,14 @@
//an object that will calculate the cost of building a road over terrain
//for use in the a_star_search algorithm.
-struct road_path_calculator
+struct road_path_calculator : cost_calculator
{
road_path_calculator(const terrain_map& terrain, const config& cfg)
: calls(0), map_(terrain), cfg_(cfg),
//find out how windy roads should be.
windiness_(maximum<int>(1,atoi(cfg["road_windiness"].c_str()))) {}
- double cost(const location& loc, double so_far) const;
+ virtual double cost(const location& loc, double so_far) const;
void terrain_changed(const location& loc) { loc_cache_.erase(loc); }
mutable int calls;
@@ -357,7 +357,7 @@
mutable std::map<char,double> cache_;
};
-double road_path_calculator::cost(const location& loc, double so_far) const
+double road_path_calculator::cost(const location& loc, double) const
{
++calls;
if(loc.x < 0 || loc.y < 0 || loc.x >= map_.size() || loc.y >=
map_.front().size())
@@ -394,17 +394,6 @@
return windiness*res;
}
-struct road_path_calculator_wrapper
-{
- explicit road_path_calculator_wrapper(const road_path_calculator& calc)
: calc_(&calc)
- {}
-
- double cost(const location& loc, double so_far) const { return
calc_->cost(loc,so_far); }
-
-private:
- const road_path_calculator* calc_;
-};
-
struct is_valid_terrain
{
is_valid_terrain(const std::vector<std::vector<gamemap::TERRAIN> >&
map, const std::string& terrain_list);
@@ -911,7 +900,6 @@
std::set<location> bridges;
road_path_calculator calc(terrain,cfg);
- const road_path_calculator_wrapper calc_wrapper(calc);
for(size_t road = 0; road != nroads; ++road) {
log_scope("creating road");
@@ -947,7 +935,7 @@
}
//search a path out for the road
- const paths::route rt =
a_star_search(src,dst,10000.0,calc_wrapper);
+ const paths::route rt = a_star_search(src, dst, 10000.0, &calc);
const std::string& name =
generate_name(name_generator,"road_name");
const int name_frequency = 20;
Index: wesnoth/src/pathfind.cpp
diff -u wesnoth/src/pathfind.cpp:1.47 wesnoth/src/pathfind.cpp:1.48
--- wesnoth/src/pathfind.cpp:1.47 Thu Nov 18 22:00:12 2004
+++ wesnoth/src/pathfind.cpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: pathfind.cpp,v 1.47 2004/11/18 22:00:12 ydirson Exp $ */
+/* $Id: pathfind.cpp,v 1.48 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -14,12 +14,175 @@
#include "global.hpp"
#include "game.hpp"
+#include "log.hpp"
#include "pathfind.hpp"
#include "util.hpp"
#include <cmath>
#include <iostream>
-#include <set>
+
+#define LOG_PF lg::info(lg::engine)
+
+namespace {
+struct node {
+ static double heuristic(const gamemap::location& src,
+ const gamemap::location& dst) {
+ return distance_between(src,dst);
+ }
+
+ node(const gamemap::location& pos, const gamemap::location& dst,
+ double cost, const gamemap::location& parent,
+ const std::set<gamemap::location>* teleports)
+ : loc(pos), parent(parent), g(cost), h(heuristic(pos,dst))
+ {
+
+ //if there are teleport locations, correct the heuristic to
+ //take them into account
+ if(teleports != NULL) {
+ double srch = h, dsth = h;
+ std::set<gamemap::location>::const_iterator i;
+ for(i = teleports->begin(); i != teleports->end(); ++i)
{
+ const double new_srch = heuristic(pos,*i);
+ const double new_dsth = heuristic(*i,dst);
+ if(new_srch < srch) {
+ srch = new_srch;
+ }
+
+ if(new_dsth < dsth) {
+ dsth = new_dsth;
+ }
+ }
+
+ if(srch + dsth + 1.0 < h) {
+ h = srch + dsth + 1.0;
+ }
+ }
+
+ f = g + h;
+ }
+
+ gamemap::location loc, parent;
+ double g, h, f;
+};
+
+}
+
+paths::route a_star_search(gamemap::location const &src, gamemap::location
const &dst,
+ double stop_at, cost_calculator const *obj,
+ std::set<gamemap::location> const *teleports)
+{
+ LOG_PF << "a* search: " << src.x << ", " << src.y << " -> " << dst.x <<
", " << dst.y << "\n";
+ typedef gamemap::location location;
+
+ typedef std::map<location,node> list_map;
+ typedef std::pair<location,node> list_type;
+
+ std::multimap<double,location> open_list_ordered;
+ list_map open_list, closed_list;
+
+ open_list.insert(list_type(src,node(src,dst,0.0,location(),teleports)));
+ open_list_ordered.insert(std::pair<double,location>(0.0,src));
+
+ std::vector<location> locs;
+ while(!open_list.empty()) {
+
+ assert(open_list.size() == open_list_ordered.size());
+
+ const list_map::iterator lowest_in_open =
open_list.find(open_list_ordered.begin()->second);
+ assert(lowest_in_open != open_list.end());
+
+ //move the lowest element from the open list to the closed list
+ closed_list.erase(lowest_in_open->first);
+ const list_map::iterator lowest =
closed_list.insert(*lowest_in_open).first;
+
+ open_list.erase(lowest_in_open);
+ open_list_ordered.erase(open_list_ordered.begin());
+
+ //find nodes we can go to from this node
+ locs.resize(6);
+ get_adjacent_tiles(lowest->second.loc,&locs[0]);
+ if(teleports != NULL && teleports->count(lowest->second.loc) !=
0) {
+
std::copy(teleports->begin(),teleports->end(),std::back_inserter(locs));
+ }
+
+ for(size_t j = 0; j != locs.size(); ++j) {
+
+ //if we have found a solution
+ if(locs[j] == dst) {
+ LOG_PF << "found solution; calculating it...\n";
+ paths::route rt;
+
+ for(location loc = lowest->second.loc;
loc.valid(); ) {
+ rt.steps.push_back(loc);
+ list_map::const_iterator itor =
open_list.find(loc);
+ if(itor == open_list.end()) {
+ itor = closed_list.find(loc);
+ assert(itor !=
closed_list.end());
+ }
+
+ loc = itor->second.parent;
+ }
+
+ 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));
+
+ assert(rt.steps.front() == src);
+
+ LOG_PF << "exiting a* search (solved)\n";
+
+ return rt;
+ }
+
+ list_map::iterator current_best =
open_list.find(locs[j]);
+ const bool in_open = current_best != open_list.end();
+ if(!in_open) {
+ current_best = closed_list.find(locs[j]);
+ }
+
+ if(current_best != closed_list.end() &&
current_best->second.g <= lowest->second.g+1.0) {
+ continue;
+ }
+
+ const double new_cost =
obj->cost(locs[j],lowest->second.g);
+
+ const node nd(locs[j],dst,lowest->second.g+new_cost,
+ lowest->second.loc,teleports);
+
+ if(current_best != closed_list.end()) {
+ if(current_best->second.g <= nd.g) {
+ continue;
+ } else if(in_open) {
+ typedef
std::multimap<double,location>::iterator Itor;
+ std::pair<Itor,Itor> itors =
open_list_ordered.equal_range(current_best->second.f);
+ while(itors.first != itors.second) {
+ if(itors.first->second ==
current_best->second.loc) {
+
open_list_ordered.erase(itors.first);
+ break;
+ }
+ ++itors.first;
+ }
+
+ open_list.erase(current_best);
+ } else {
+ closed_list.erase(current_best);
+ }
+ }
+
+ if(nd.f < stop_at) {
+ open_list.insert(list_type(nd.loc,nd));
+
open_list_ordered.insert(std::pair<double,location>(nd.f,nd.loc));
+ } else {
+ closed_list.insert(list_type(nd.loc,nd));
+ }
+ }
+ }
+
+ LOG_PF << "aborted a* search\n";
+ paths::route val;
+ val.move_left = 100000;
+ return val;
+}
namespace {
gamemap::location find_vacant(const gamemap& map,
Index: wesnoth/src/pathfind.hpp
diff -u wesnoth/src/pathfind.hpp:1.33 wesnoth/src/pathfind.hpp:1.34
--- wesnoth/src/pathfind.hpp:1.33 Sun Sep 19 11:13:56 2004
+++ wesnoth/src/pathfind.hpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: pathfind.hpp,v 1.33 2004/09/19 11:13:56 silene Exp $ */
+/* $Id: pathfind.hpp,v 1.34 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -20,16 +20,11 @@
#include "pathutils.hpp"
#include "unit.hpp"
-#include <algorithm>
-#include <cassert>
-#include <cmath>
-#include <iostream>
#include <map>
#include <list>
+#include <set>
#include <vector>
-#define LOG_PF lg::info(lg::engine)
-
//this module contains various pathfinding functions and utilities.
//a convenient type for storing a list of tiles adjacent to a certain tile
@@ -96,14 +91,18 @@
int route_turns_to_complete(const unit& u, const gamemap& map,
const paths::route& rt);
-struct shortest_path_calculator
+struct cost_calculator
+{
+ virtual double cost(const gamemap::location& loc, double so_far) const
= 0;
+ virtual ~cost_calculator() {}
+};
+
+struct shortest_path_calculator : cost_calculator
{
shortest_path_calculator(const unit& u, const team& t,
- const unit_map& units,
- const
std::vector<team>& teams,
- const
gamemap& map,
- const
gamestatus& status);
- double cost(const gamemap::location& loc, double so_far) const;
+ const unit_map& units, const
std::vector<team>& teams,
+ const gamemap& map, const gamestatus& status);
+ virtual double cost(const gamemap::location& loc, double so_far) const;
private:
const unit& unit_;
@@ -114,169 +113,8 @@
const gamestatus& status_;
};
-namespace detail {
-struct node {
- static double heuristic(const gamemap::location& src,
- const gamemap::location& dst) {
- return distance_between(src,dst);
- }
-
- node(const gamemap::location& pos, const gamemap::location& dst,
- double cost, const gamemap::location& parent,
- const std::set<gamemap::location>* teleports)
- : loc(pos), parent(parent), g(cost), h(heuristic(pos,dst))
- {
-
- //if there are teleport locations, correct the heuristic to
- //take them into account
- if(teleports != NULL) {
- double srch = h, dsth = h;
- std::set<gamemap::location>::const_iterator i;
- for(i = teleports->begin(); i != teleports->end(); ++i)
{
- const double new_srch = heuristic(pos,*i);
- const double new_dsth = heuristic(*i,dst);
- if(new_srch < srch) {
- srch = new_srch;
- }
-
- if(new_dsth < dsth) {
- dsth = new_dsth;
- }
- }
-
- if(srch + dsth + 1.0 < h) {
- h = srch + dsth + 1.0;
- }
- }
-
- f = g + h;
- }
-
- gamemap::location loc, parent;
- double g, h, f;
-};
-
-}
-
-template<typename T>
-paths::route a_star_search(const gamemap::location& src,
- const gamemap::location& dst, double stop_at, T obj,
- const std::set<gamemap::location>* teleports=NULL)
-{
- LOG_PF << "a* search: " << src.x << ", " << src.y << " -> " << dst.x <<
", " << dst.y << "\n";
- using namespace detail;
- typedef gamemap::location location;
-
- typedef std::map<location,node> list_map;
- typedef std::pair<location,node> list_type;
-
- std::multimap<double,location> open_list_ordered;
- list_map open_list, closed_list;
-
- open_list.insert(list_type(src,node(src,dst,0.0,location(),teleports)));
- open_list_ordered.insert(std::pair<double,location>(0.0,src));
-
- std::vector<location> locs;
- while(!open_list.empty()) {
-
- assert(open_list.size() == open_list_ordered.size());
-
- const list_map::iterator lowest_in_open =
open_list.find(open_list_ordered.begin()->second);
- assert(lowest_in_open != open_list.end());
-
- //move the lowest element from the open list to the closed list
- closed_list.erase(lowest_in_open->first);
- const list_map::iterator lowest =
closed_list.insert(*lowest_in_open).first;
-
- open_list.erase(lowest_in_open);
- open_list_ordered.erase(open_list_ordered.begin());
-
- //find nodes we can go to from this node
- locs.resize(6);
- get_adjacent_tiles(lowest->second.loc,&locs[0]);
- if(teleports != NULL && teleports->count(lowest->second.loc) !=
0) {
-
std::copy(teleports->begin(),teleports->end(),std::back_inserter(locs));
- }
-
- for(size_t j = 0; j != locs.size(); ++j) {
-
- //if we have found a solution
- if(locs[j] == dst) {
- LOG_PF << "found solution; calculating it...\n";
- paths::route rt;
-
- for(location loc = lowest->second.loc;
loc.valid(); ) {
- rt.steps.push_back(loc);
- list_map::const_iterator itor =
open_list.find(loc);
- if(itor == open_list.end()) {
- itor = closed_list.find(loc);
- assert(itor !=
closed_list.end());
- }
-
- loc = itor->second.parent;
- }
-
- 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));
-
- assert(rt.steps.front() == src);
-
- LOG_PF << "exiting a* search (solved)\n";
-
- return rt;
- }
-
- list_map::iterator current_best =
open_list.find(locs[j]);
- const bool in_open = current_best != open_list.end();
- if(!in_open) {
- current_best = closed_list.find(locs[j]);
- }
-
- if(current_best != closed_list.end() &&
current_best->second.g <= lowest->second.g+1.0) {
- continue;
- }
-
- const double new_cost =
obj.cost(locs[j],lowest->second.g);
-
- const node nd(locs[j],dst,lowest->second.g+new_cost,
- lowest->second.loc,teleports);
-
- if(current_best != closed_list.end()) {
- if(current_best->second.g <= nd.g) {
- continue;
- } else if(in_open) {
- typedef
std::multimap<double,location>::iterator Itor;
- std::pair<Itor,Itor> itors =
open_list_ordered.equal_range(current_best->second.f);
- while(itors.first != itors.second) {
- if(itors.first->second ==
current_best->second.loc) {
-
open_list_ordered.erase(itors.first);
- break;
- }
- ++itors.first;
- }
-
- open_list.erase(current_best);
- } else {
- closed_list.erase(current_best);
- }
- }
-
- if(nd.f < stop_at) {
- open_list.insert(list_type(nd.loc,nd));
-
open_list_ordered.insert(std::pair<double,location>(nd.f,nd.loc));
- } else {
- closed_list.insert(list_type(nd.loc,nd));
- }
- }
- }
-
- LOG_PF << "aborted a* search\n";
- paths::route val;
- val.move_left = 100000;
- return val;
-}
-
-#undef LOG_PF
+paths::route a_star_search(gamemap::location const &src, gamemap::location
const &dst,
+ double stop_at, cost_calculator const *obj,
+ std::set<gamemap::location> const *teleports =
NULL);
#endif
Index: wesnoth/src/playturn.cpp
diff -u wesnoth/src/playturn.cpp:1.308 wesnoth/src/playturn.cpp:1.309
--- wesnoth/src/playturn.cpp:1.308 Sun Dec 5 19:54:26 2004
+++ wesnoth/src/playturn.cpp Sun Dec 5 22:14:29 2004
@@ -1,4 +1,4 @@
-/* $Id: playturn.cpp,v 1.308 2004/12/05 19:54:26 silene Exp $ */
+/* $Id: playturn.cpp,v 1.309 2004/12/05 22:14:29 silene Exp $ */
/*
Copyright (C) 2003 by David White <address@hidden>
Part of the Battle for Wesnoth Project http://wesnoth.whitevine.net
@@ -352,8 +352,7 @@
allowed_teleports.insert(un->first);
}
- current_route_ =
a_star_search(selected_hex_,dest,
-
10000.0,calc,teleports);
+ current_route_ = a_star_search(selected_hex_,
dest, 10000.0, &calc, teleports);
current_route_.move_left =
route_turns_to_complete(un->second,map_,current_route_);
@@ -835,8 +834,7 @@
}
- paths::route route =
a_star_search(it->first,go_to,
-
10000.0,calc,teleports);
+ paths::route route = a_star_search(it->first,
go_to, 10000.0, &calc, teleports);
route.move_left =
route_turns_to_complete(it->second,map_,route);
gui_.set_route(&route);
}
@@ -918,7 +916,7 @@
allowed_teleports.insert(ui->first);
}
- paths::route route =
a_star_search(ui->first,target,10000.0,calc,teleports);
+ paths::route route = a_star_search(ui->first, target, 10000.0, &calc,
teleports);
if(route.steps.empty())
return;
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Wesnoth-cvs-commits] wesnoth/src actions.cpp ai.cpp ai_move.cpp cave...,
Guillaume Melquiond <=