templates

[icfp05.git] / botsrc / bot.cpp

diff --git a/botsrc/bot.cpp b/botsrc/bot.cpp
index 411d933ee50d7bab0ab689b320a753d464cb3f06..506330af60f61d415a961f4e658adfc653ade36a 100644 (file)
--- 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"