-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;
- while(!pq.empty()){
- node = pq.top();
- pq.pop();
- //cerr << "Vector with size: " << w.size() << endl;
- //cerr << "Looking at: " << node->name << endl;
- //copy(w.begin(), w.end(), ostream_iterator<string>(cerr, " : "));
-
- 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;
-
- Intersection& inter = _intersections[node->name];
- for (hash_map<string,StreetType>::const_iterator street = inter.connections.begin();
- street != inter.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,StreetType>::const_iterator st = _intersections[street->first].connections.find(node->name);
- if (st != _intersections[street->first].connections.end())
- travelStreet = st->second != foot;
- else
- travelStreet = false;
- }else
- travelStreet = true;
- }else
- travelStreet = street->second != foot;
- }else{
- travelStreet = street->second != car;
- }
- if (travelStreet){
- //cerr << "Adding street: " << street->first << endl;
- SPInfo* n = 0;
- 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);
- }
- }