botsrc/shortestPath.cpp

   1 #include "bot.h"
   2 #include <queue>
   3 #include <string>
   4 #include <ext/hash_map>
   5 using namespace std;
   6 using namespace __gnu_cxx;
   7
   8 struct SPCost{
   9         inline int cost(std::string from, std::string to) const{
  10                 return 1;
  11         }
  12 };
  13
  14 template<class Goal>
  15 std::list<std::string> Bot::shortestPath(const std::string& from, PlayerType type, const Goal& goal, bool reverse) const{
  16         return shortestPath(from, type, goal, SPCost(), reverse);
  17 }
  18
  19 template<class Goal, class Cost>
  20 std::list<std::string> Bot::shortestPath(const std::string& from, PlayerType type, const Goal& goal, const Cost& cost,bool reverse) const{
  21
  22         //cerr << "New shortest path from: " << from << endl;
  23
  24         priority_queue<SPInfo*, vector<SPInfo* >, SPInfoComp > pq;
  25         hash_map<string,SPInfo> nodes;
  26
  27         SPInfo* node = &nodes[from];
  28         node->name = from;
  29         node->settled = false;
  30         node->parent = 0;
  31         node->cost = 0;
  32         pq.push(node);
  33
  34         int g = 0;
  35         bool hascar = type == cop_car;
  36         ;
  37         SPInfo* n = 0;
  38         while(!pq.empty()){
  39                 node = pq.top();
  40                 pq.pop();
  41
  42                 g = goal(node);
  43                 if (g < 0)
  44                         break;
  45                 else if (g){
  46                         list<string> l;
  47                         front_insert_iterator<list<string> > ii(l);
  48                         do{
  49                                 *ii++ = node->name;
  50                                 node = node->parent;
  51                         }while (node != 0);
  52                         return l;
  53                 }
  54                 node->settled = true;
  55                 //cerr << "Settled " << node->name << endl;
  56
  57                 hash_map<string,Intersection>::const_iterator intersection = _intersections.find(node->name);
  58                 if (intersection == _intersections.end()){ //Sanity check, should never be true..
  59                         cerr << "BUG: Could not find intersection: " << node->name << endl;
  60                         continue;
  61                 }
  62                 for (hash_map<string,StreetType>::const_iterator street = intersection->second.connections.begin();
  63                                 street != intersection->second.connections.end(); ++street){
  64                         hash_map<string,SPInfo>::iterator newNode = nodes.find(street->first);
  65                         bool travelStreet = false;
  66                         if (hascar){
  67                                 if (reverse){
  68                                         if (street->second != foot){
  69                                                 hash_map<string,Intersection>::const_iterator newInter = _intersections.find(street->first);
  70                                                 if (newInter != _intersections.end()){
  71                                                         hash_map<string,StreetType>::const_iterator st = newInter->second.connections.find(node->name);
  72                                                         if (st != newInter->second.connections.end())
  73                                                                 travelStreet = st->second != foot;
  74                                                 }
  75                                         }else
  76                                                 travelStreet = true;
  77                                 }else
  78                                         travelStreet = street->second != foot;
  79                         }else{
  80                                 travelStreet = street->second != car;
  81                         }
  82                         if (travelStreet){
  83                                 //cerr << "Adding street: " << street->first << endl;
  84                                 if (newNode == nodes.end()){
  85                                         n = &nodes[street->first];
  86                                         n->name = street->first;
  87                                         n->settled = false;
  88                                         n->parent = 0;
  89                                         n->cost = 10000;
  90                                 }else if (newNode->second.settled)
  91                                         continue;
  92                                 else
  93                                         n = &newNode->second;
  94
  95                                 int c = cost.cost(node->name, n->name);
  96                                 if (n->cost > node->cost + c){
  97                                         n->cost = node->cost + c;
  98                                         n->parent = node;
  99                                         pq.push(n);
 100                                 }
 101                         }
 102
 103                 }
 104
 105         }
 106
 107         return list<string>();
 108 }