From ea7c6c2755a89718e1396c1c3f8061886861ff4c Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Sun, 10 Jul 2005 13:08:00 +0000 Subject: [PATCH] initial implementation of new robber --- botsrc/bot.h | 4 +- newrobber/{robbersrc.pro => newrobber.pro} | 2 +- newrobber/robber.cpp | 155 ++++++++------------- newrobber/robber.h | 5 +- 4 files changed, 68 insertions(+), 98 deletions(-) rename newrobber/{robbersrc.pro => newrobber.pro} (95%) diff --git a/botsrc/bot.h b/botsrc/bot.h index 15be234..62f2556 100644 --- a/botsrc/bot.h +++ b/botsrc/bot.h @@ -85,9 +85,9 @@ class Bot { virtual void voteResult(); void getPlayers(); template - std::list shortestPath(const std::string& from, PlayerType type, const Goal& goal, const Cost& cost, bool reverse = false); + std::list shortestPath(const std::string& from, PlayerType type, const Goal& goal, const Cost& cost, bool reverse = false) const; template - std::list shortestPath(const std::string& from, PlayerType type, const Goal& goal, bool reverse = false); + std::list shortestPath(const std::string& from, PlayerType type, const Goal& goal, bool reverse = false) const; __gnu_cxx::hash_map _intersections; __gnu_cxx::hash_map _players; diff --git a/newrobber/robbersrc.pro b/newrobber/newrobber.pro similarity index 95% rename from newrobber/robbersrc.pro rename to newrobber/newrobber.pro index e95eca1..d8e180d 100644 --- a/newrobber/robbersrc.pro +++ b/newrobber/newrobber.pro @@ -6,7 +6,7 @@ TEMPLATE = app CONFIG -= qt #CONFIG += debug unix:LIBS += -lm -TARGET = ../robber +TARGET = ../nrobber # Input diff --git a/newrobber/robber.cpp b/newrobber/robber.cpp index 32124a8..ccac7d9 100644 --- a/newrobber/robber.cpp +++ b/newrobber/robber.cpp @@ -12,115 +12,82 @@ string Robber::turn(){ //Ignore bribing for now cout << "nobribe:" << endl; string input; + cerr << "New turn" << endl; getline(cin,input); + _time = clock(); - hash_map streets; - Intersection& inter = _intersections[_location]; - for (hash_map::const_iterator street = inter.connections.begin(); - street != inter.connections.end(); ++street){ - if (street->second == car){ - //cerr << "Discarding: " << street->first << " since car is needed" << endl; - continue; - } - //cerr << "Looking at street: " << street->first << endl; - Intersection& conInter = _intersections[street->first]; - double goodness = conInter.connections.size()*5; + cerr << "Starting to calculate shortest path" << endl; + list l = shortestPath(_location, robber,*this, *this); + _oldLocation = _location; + if (l.size() > 0){ + cerr << "Found a route" << endl; + list::iterator i = l.begin(); + _location = *++i; + } + cerr << "Moving to: " << _location << endl; + return _location; +} - list closestFootCop = shortestPath(street->first, cop_foot, FindPlayer(_players, cop_foot, 6), true); - unsigned int closestCop = closestFootCop.size(); - bool copInCar = false; - //cerr << "Cop on fot " << closestCop << " intersections away." << endl; +int Robber::operator()(const SPInfo* node) const{ + //cerr << "Goal for " << node->name << endl; + if (node->cost > 10 || (clock()-_time)/CLOCKS_PER_SEC > 2.4) + return 1; + return 0; +} - if (closestCop > 0 && closestCop < 3) - continue; +int Robber::cost(const std::string& from, const std::string& to) const{ - list closestCarCop = shortestPath(street->first, cop_car, FindPlayer(_players, cop_car, closestCop - 1 > 0 ? closestCop : 5), true); - //cerr << "Cop in car " << closestCarCop.size() << " intersections away." << endl; + //cerr << "Calculating cost between " << from << " and " << to << endl; + hash_map::const_iterator conInter = _intersections.find(to); + if (conInter == _intersections.end()) + return 1000000; //Should never happen - if (closestCarCop.size() > 0){ - closestCop = closestCarCop.size(); - copInCar = true; - } + int cost = 1; - //cerr << "Cop " << closestCop << " intersections away." << endl; - if (closestCop > 0 && closestCop < 3) - continue; - - priority_queue banks; - for(hash_map::const_iterator bank = _banks.begin(); - bank != _banks.end(); ++bank){ - //cerr << "Handling bank at: " << bank->first << endl; - if (bank->second > 0){ - list cop = shortestPath(bank->first, cop_car, FindPlayer(_players, cop_car, 3), true); - if (cop.size() > 0) - continue; - else{ - cop = shortestPath(bank->first, cop_foot, FindPlayer(_players, cop_foot, 3), true); - if (cop.size() > 0) - continue; - } - list l = shortestPath(street->first, _type, SimpleSPGoal(bank->first)); - if (l.size() < 1) - continue; - //list::iterator i = l.begin(); - //++i; - banks.push(bank->second/(pow(l.size(),4.0))); - } - } - //sort(banks.begin(),banks.end(),greater()); + list closestFootCop = shortestPath(to, cop_foot, FindPlayer(_players, cop_foot, 10), true); + unsigned int closestCop = closestFootCop.size(); + bool copInCar = false; + //cerr << "Cop on fot " << closestCop << " intersections away." << endl; - for (unsigned int i = 0; i < 2 && banks.size() > 0;++i){ - goodness += banks.top(); - banks.pop(); - } - - //cerr << "Goodness before cop: " << goodness << endl; - if (closestCop > 2){ - //cerr << "Cop " << closestCop << " intersections away." << endl; - goodness *= 1 - 1/(copInCar ? closestCop : closestCop - 1); - } - //cerr << "Goodness after cop: " << goodness << endl; - - if (conInter.type == bank){ - //cerr << "FOUND A BANK" << endl; - if (closestCop > 0 && closestCop < 4) - continue; - else if (_banks[street->first] > 0){ - //cerr << "No cop close to bank" << endl; - return street->first; - } - } - - //cerr << "Street: " << street->first << " goodness: " << goodness << endl; - streets[street->first] = goodness; - } - streets[_oldLocation] /= 10; + if (closestCop > 0 && closestCop < 3) + return 100; + list closestCarCop = shortestPath(to, cop_car, FindPlayer(_players, cop_car, closestCop - 1 > 0 ? closestCop : 5), true); + //cerr << "Cop in car " << closestCarCop.size() << " intersections away." << endl; + if (closestCarCop.size() > 0){ + closestCop = closestCarCop.size(); + copInCar = true; + } - /*cerr << "Using route: "; - copy(v.begin(), v.end(), ostream_iterator(cerr, " : ")); - cerr << endl; - */ + //cerr << "Cop " << closestCop << " intersections away." << endl; + if (closestCop > 0 && closestCop < 3) + return 100; - //stand still if we can't find a better choice.. - string destination = _location; - double goodness = 0; - for (hash_map::const_iterator dest = streets.begin(); - dest != streets.end(); ++dest){ - //cerr << "Goodness: " << dest->second << endl; - if (dest->second > goodness){ - //cerr << "New Goodness: " << dest->second << endl; - goodness = dest->second; - destination = dest->first; + //cerr << "Goodness before cop: " << goodness << endl; + if (closestCop > 2){ + //cerr << "Cop " << closestCop << " intersections away." << endl; + cost += 8 - (copInCar ? closestCop : closestCop - 1); + } + //cerr << "Goodness after cop: " << goodness << endl; + + if (conInter->second.type == bank){ + //cerr << "FOUND A BANK" << endl; + if (closestCop > 0 && closestCop < 4) + return 1000; + else if (_banks.find(to)->second > 0){ + //cerr << "No cop close to bank" << endl; + return 1; } } - _oldLocation = _location; - //cerr << "Moving to: " << destination << endl; - - return destination; - + + if (to == _oldLocation) + cost *= 2; + cerr << "Street: " << to << " cost: " << cost << endl; + + return cost; } + void Robber::move(std::string location){ cout << "rmov\\" << endl; Bot::move(location); diff --git a/newrobber/robber.h b/newrobber/robber.h index 7624986..53b1e6f 100644 --- a/newrobber/robber.h +++ b/newrobber/robber.h @@ -2,16 +2,19 @@ #define __ROBBER_H__ #include "../botsrc/bot.h" +#include class Robber : public Bot { public: Robber(std::string name):Bot(name,robber){}; std::string turn(); + int cost(const std::string& from,const std::string& to) const; + int operator()(const SPInfo* node) const; protected: std::string _oldLocation; - std::string _maybeNextLocation; virtual void move(std::string location); + clock_t _time; }; #endif -- 2.39.2