From c587459e89e9d1123425df5b42a367e7bf439e64 Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Sat, 25 Jun 2005 01:25:56 +0000 Subject: [PATCH] fixed priority queue and started to implement the robber algorithm, it needs tuning though --- bot/bot.cpp | 72 ++++++++++++++++++++++++++++++++++++-------- robber/robber.cpp | 76 ++++++++++++++++++++++++++++++++++++++++------- robber/robber.pro | 1 + 3 files changed, 127 insertions(+), 22 deletions(-) diff --git a/bot/bot.cpp b/bot/bot.cpp index 2829030..1c2b4dc 100644 --- a/bot/bot.cpp +++ b/bot/bot.cpp @@ -8,9 +8,51 @@ using namespace std; using namespace __gnu_cxx; +struct VectComp{ + bool operator()(const vector& v1, const vector& v2){ + return v1.size() > v2.size(); + } +}; Bot::Bot(string name, string type){ _name = name; _type = type; + + /* + priority_queue, vector >, VectComp> pq; + + vector v; + v.push_back("hej"); + pq.push(v); + v.push_back("hå"); + pq.push(v); + v.push_back("blaha"); + pq.push(v); + v.clear(); + v.push_back("hej hå"); + pq.push(v); + v.clear(); + v.push_back("hejsan"); + pq.push(v); + v.push_back("what?"); + pq.push(v); + v.push_back("blaha"); + pq.push(v); + + cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl; + pq.pop(); + cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl; + pq.pop(); + cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl; + pq.pop(); + cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl; + pq.pop(); + cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl; + pq.pop(); + cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl; + pq.pop(); + +*/ + } void Bot::play(){ @@ -123,11 +165,11 @@ void Bot::updateWorld(){ string input; getline(cin,input); _world = value(input); - cerr << "World: " << _world << endl; + //cerr << "World: " << _world << endl; getline(cin,input); _robbed = value(input); - cerr << "Robbed: " << _robbed << endl; + //cerr << "Robbed: " << _robbed << endl; getline(cin,input); while (true){ @@ -139,7 +181,7 @@ void Bot::updateWorld(){ bank >> input; bank >> _banks[input]; } - cerr << "Number of banks: " << _banks.size() << endl; + //cerr << "Number of banks: " << _banks.size() << endl; getline(cin,input); while (true){ @@ -160,12 +202,12 @@ void Bot::updateWorld(){ istringstream player(input); player >> input; player >> input; - cerr << "Player: " << input << endl; + //cerr << "Player: " << input << endl; Player& pl = _players[input]; player >> pl.location; player >> pl.type; } - cerr << "Number of players: " << _players.size() << endl; + //cerr << "Number of players: " << _players.size() << endl; } void Bot::move(std::string location){ @@ -189,7 +231,7 @@ std::string Bot::turn(){ std::vector Bot::shortestPath(std::string from, std::string to, std::string type){ - priority_queue, vector >, greater > > pq; + priority_queue, vector >, VectComp > pq; vector v; v.push_back(from); @@ -198,25 +240,31 @@ std::vector Bot::shortestPath(std::string from, std::string to, std hash_map settled; while(!pq.empty()){ - const vector& w = pq.top(); + const vector w = pq.top(); + pq.pop(); + //cerr << "Vector with size: " << w.size() << endl; + //cerr << "Looking at: " << w.back() << endl; + //copy(w.begin(), w.end(), ostream_iterator(cerr, " : ")); if (w.back() == to) return w; settled[w.back()] = true; Intersection& inter = _intersections[w.back()]; for (hash_map::const_iterator street = inter.connections.begin(); street != inter.connections.end(); ++street){ - if (settled.find(street->first) == settled.end()) + if (settled.find(street->first) != settled.end()) continue; - bool car = type == "cop-car"; - if ( (car && (street->second == car || street->second == both)) || - (!car && (street->second == foot || street->second == both))){ + //cerr << "Adding: " << street->first << endl; + bool hascar = type == "cop-car"; + if ( (hascar && (street->second == car || street->second == both)) || + (!hascar && (street->second == foot || street->second == both))){ + v = w; v.push_back(street->first); pq.push(v); } + } - pq.pop(); } return vector(); diff --git a/robber/robber.cpp b/robber/robber.cpp index c888362..efe40de 100644 --- a/robber/robber.cpp +++ b/robber/robber.cpp @@ -1,24 +1,80 @@ #include "robber.h" #include +#include +#include using namespace std; using namespace __gnu_cxx; string Robber::turn(){ - + hash_map streets; Intersection& inter = _intersections[_location]; - - cerr << "Number of connecting streets: " << inter.connections.size() << endl; - for (hash_map::const_iterator street = inter.connections.begin(); - street != inter.connections.end(); ++street){ - cerr << "Checking: " << street->first << endl; - if (street->second != car){ - cerr << "Moving to: " << street->first << endl; - return street->first; + street != inter.connections.end(); ++street){ + double goodness = 100; + int curx = _intersections[_location].x; + int cury = _intersections[_location].y; + + int newx = _intersections[street->first].x; + int newy = _intersections[street->first].y; + for (hash_map::const_iterator player = _players.begin(); + player != _players.end(); ++player){ + if (player->first == _name) + continue; + + int px = _intersections[player->second.location].x; + int py = _intersections[player->second.location].y; + + double dist1 = sqrt(pow((curx-px),2.0)+pow((cury-py),2.0)); + double dist2 = sqrt(pow((newx-px),2.0)+pow((newy-py),2.0)); + cerr << "Original distance: " << dist1 << endl; + cerr << "New distance: " << dist2 << endl; + + + if (dist2 > dist1) + goodness *= 4; + else + goodness /= 4; + + if (player->second.type == "cop-foot" && dist2 <= 3) + goodness /= 10; + else if (player->second.type == "cop-car" && dist2 <= 2) + goodness /= 10; + + + } + streets[street->first] = goodness; + } + + for(hash_map::const_iterator bank = _banks.begin(); + bank != _banks.end(); ++bank){ + //cerr << "Handling bank at: " << bank->first << endl; + if (bank->second > 0){ + vector v = shortestPath(_location, bank->first,_type); + if (v.size() < 2) + continue; + streets[v[1]] *= bank->second/v.size(); + + } + } + /*cerr << "Using route: "; + copy(v.begin(), v.end(), ostream_iterator(cerr, " : ")); + cerr << endl; + */ + + string destination; + 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; } } - return _location; + + return destination; } diff --git a/robber/robber.pro b/robber/robber.pro index dd31e91..027b399 100644 --- a/robber/robber.pro +++ b/robber/robber.pro @@ -5,6 +5,7 @@ TEMPLATE = app INCLUDEPATH += ../bot CONFIG -= qt +unix:LIBS += -lm # Input -- 2.39.2