[Wesnoth-cvs-commits] wesnoth/src actions.cpp ai.cpp ai_move.cpp cave... (December 05, 2004 - 23:20)

 

CVSROOT:	/cvsroot/wesnoth
Module name:	wesnoth
Branch: 	
Changes by:	Guillaume Melquiond <guillaume.melquiond@xxxxxxxxx>	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 <davidnwhite@xxxxxxxxxxxxxxx>
    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 <davidnwhite@xxxxxxxxxxxxxxx>
    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 <davidnwhite@xxxxxxxxxxxxxxx>
    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 <davidnwhite@xxxxxxxxxxxxxxx>
    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 <davidnwhite@xxxxxxxxxxxxxxx>
    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 <davidnwhite@xxxxxxxxxxxxxxx>
    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 <davidnwhite@xxxxxxxxxxxxxxx>
    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;
 



You are on the gna.org mail server.

Generated by mhonarc, Tue Sep 20 16:45:15 2005