X-Git-Url: https://ruin.nu/git/?p=icfp05.git;a=blobdiff_plain;f=botsrc%2Fbot.cpp;h=506330af60f61d415a961f4e658adfc653ade36a;hp=411d933ee50d7bab0ab689b320a753d464cb3f06;hb=aae26492dc1712e3f4783223df158ff5aa65d975;hpb=8b5e24a0d19af8af51155da4a5c8515bb3b8a7ee

diff --git a/botsrc/bot.cpp b/botsrc/bot.cpp
index 411d933..506330a 100644
--- a/botsrc/bot.cpp
+++ b/botsrc/bot.cpp
@@ -21,6 +21,8 @@ Bot::Bot(const string& name, PlayerType type){
 	_playerTypes["robber"] = robber;
 	_playerTypes["cop-foot"] = cop_foot;
 	_playerTypes["cop-car"] = cop_car;
+	//shortestPath("",robber,SimpleSPGoal(""));
+	//shortestPath("",robber,FindPlayer(hash_map<string,Player>(),robber));
 
 }
 
@@ -275,125 +277,6 @@ std::string Bot::turn(){
 	return _location;
 }
 
-struct SPInfoComp{
-	bool operator()(const SPInfo* v1, const SPInfo* v2){
-		return v1->cost > v2->cost;
-	}
-};
-
-std::list<std::string> Bot::shortestPath(const std::string& from, PlayerType type, const SPGoal& goal, bool reverse){
-
-	//cerr << "New shortest path from: " << from << endl;
-	
-	priority_queue<SPInfo*, vector<SPInfo* >, SPInfoComp > pq;
-	hash_map<string,SPInfo> nodes;
-
-	SPInfo* node = &nodes[from];
-	node->name = from;
-	node->settled = false;
-	node->parent = 0;
-	node->cost = 0;
-	pq.push(node);
-
-	int g = 0;
-	bool hascar = type == cop_car;
-	;
-	SPInfo* n = 0;
-	while(!pq.empty()){
-		node = pq.top();
-		pq.pop();
-
-		g = goal(node);
-		if (g < 0)
-			break;
-		else if (g){
-			list<string> l;
-			front_insert_iterator<list<string> > ii(l);
-			do{
-				*ii++ = node->name;
-				node = node->parent;
-			}while (node != 0);
-			return l;
-		}
-		node->settled = true;
-
-		hash_map<string,Intersection>::const_iterator intersection = _intersections.find(node->name);
-		if (intersection == _intersections.end()){ //Sanity check, should never be true..
-			cerr << "BUG: Could not find intersection: " << node->name << endl;
-			continue;
-		}
-		for (hash_map<string,StreetType>::const_iterator street = intersection->second.connections.begin();
-				street != intersection->second.connections.end(); ++street){
-			hash_map<string,SPInfo>::iterator newNode = nodes.find(street->first);
-			bool travelStreet = false;
-			if (hascar){
-				if (reverse){
-					if (street->second != foot){
-						hash_map<string,Intersection>::const_iterator newInter = _intersections.find(street->first);
-						if (newInter != _intersections.end()){
-							hash_map<string,StreetType>::const_iterator st = newInter->second.connections.find(node->name);
-							if (st != newInter->second.connections.end())
-								travelStreet = st->second != foot;
-						}
-					}else
-						travelStreet = true;
-				}else
-					travelStreet = street->second != foot;
-			}else{
-				travelStreet = street->second != car;
-			}
-			if (travelStreet){
-				//cerr << "Adding street: " << street->first << endl;
-				if (newNode == nodes.end()){
-					n = &nodes[street->first];
-					n->name = street->first;
-					n->settled = false;
-					n->parent = 0;
-					n->cost = 10000;
-				}else if (newNode->second.settled)
-					continue;
-				else
-					n = &newNode->second;
-
-				if (n->cost > node->cost + 1){
-					n->cost = node->cost + 1;
-					n->parent = node;
-					pq.push(n);
-				}
-			}
-
-		}
-		
-	}
-	
-	return list<string>();
-}
-
-SimpleSPGoal::SimpleSPGoal(const std::string& to, int limit):_to(to), _limit(limit){
-}
-
-int SimpleSPGoal::operator()(const SPInfo* node) const{
-	if (_limit > 0 && node->cost >= _limit)
-		return -1;
-	if (node->name == _to)
-		return 1;
-	return 0;
-}
-
-FindPlayer::FindPlayer(const hash_map<string, Player>& players, PlayerType type, int limit) : _players(players), _type(type), _limit(limit){
-}
-
-int FindPlayer::operator()(const SPInfo* node) const{
-	if (_limit > 0 && node->cost >= _limit)
-		return -1;
-	for(hash_map<string, Player>::const_iterator player = _players.begin();
-			player != _players.end(); ++player){
-		if (player->second.type == _type && player->second.location == node->name){
-			return 1;
-		}
-	}
-	return 0;
-}
 
 void Bot::sendInformation(){
 	cout << "inf\\" << endl;
@@ -446,3 +329,5 @@ void Bot::voteResult(){
 			++_winningPlans[winner];
 	}
 }
+
+#include "shortestPath.cpp"