From f4121d29718ebe595283200700956369776dbdca Mon Sep 17 00:00:00 2001 From: Michael Andreen Date: Sat, 25 Jun 2005 16:49:19 +0000 Subject: [PATCH] made the shortest path algorithm more modular and tuned the robber more --- bot/bot.cpp | 34 +++++++++++++++++++------------- bot/bot.h | 33 ++++++++++++++++++++++++++----- robber/robber.cpp | 50 ++++++++++++++++++++++++++++++++++++++++------- robber/robber.h | 2 +- robber/robber.pro | 2 +- 5 files changed, 93 insertions(+), 28 deletions(-) diff --git a/bot/bot.cpp b/bot/bot.cpp index 8450a63..dd51632 100644 --- a/bot/bot.cpp +++ b/bot/bot.cpp @@ -101,9 +101,6 @@ void Bot::play(){ } } -Bot::~Bot(){ -} - /** nod\ eol ( nod: loc node-tag coordinate coordinate eol )* @@ -127,7 +124,15 @@ void Bot::buildGraph(){ node >> input; node >> input; Intersection& inter = _intersections[input]; - node >> inter.type; + node >> input; + if (input == "bank") + inter.type = bank; + else if (input == "hq") + inter.type = hq; + else if (input == "robber-start") + inter.type = robber_start; + else + inter.type = ordinary; node >> inter.x; node >> inter.y; } @@ -234,20 +239,15 @@ std::string Bot::turn(){ return _location; } -struct SPInfo{ - string name; - bool settled; - SPInfo* parent; - int cost; -}; - struct SPInfoComp{ bool operator()(const SPInfo* v1, const SPInfo* v2){ return v1->cost > v2->cost; } }; -std::list Bot::shortestPath(const std::string& from, const std::string& to, PlayerType type){ +std::list Bot::shortestPath(const std::string& from, PlayerType type, const SPGoal& goal){ + + //cerr << "New shortest path from: " << from << endl; priority_queue, SPInfoComp > pq; hash_map nodes; @@ -259,13 +259,18 @@ std::list Bot::shortestPath(const std::string& from, const std::str node->cost = 0; pq.push(node); + int g = 0; while(!pq.empty()){ node = pq.top(); pq.pop(); //cerr << "Vector with size: " << w.size() << endl; - //cerr << "Looking at: " << w.back() << endl; + //cerr << "Looking at: " << node->name << endl; //copy(w.begin(), w.end(), ostream_iterator(cerr, " : ")); - if (node->name == to){ + + g = goal(node); + if (g < 0) + break; + else if (g){ list l; front_insert_iterator > ii(l); do{ @@ -283,6 +288,7 @@ std::list Bot::shortestPath(const std::string& from, const std::str bool hascar = type == cop_car; if ( (hascar && (street->second == car || street->second == both)) || (!hascar && (street->second == foot || street->second == both))){ + //cerr << "Adding street: " << street->first << endl; SPInfo* n = 0; if (newNode == nodes.end()){ n = &nodes[street->first]; diff --git a/bot/bot.h b/bot/bot.h index 7d27831..1c40b44 100644 --- a/bot/bot.h +++ b/bot/bot.h @@ -39,7 +39,7 @@ enum IntersectionType{hq, bank, robber_start, ordinary}; struct Intersection{ __gnu_cxx::hash_map connections; - std::string type; + IntersectionType type; int x; int y; }; @@ -57,19 +57,43 @@ struct Bank{ template T value(std::string input); +struct SPInfo{ + std::string name; + bool settled; + SPInfo* parent; + int cost; +}; + + +struct SPGoal{ + virtual ~SPGoal(){} + virtual int operator()(const SPInfo* node) const = 0; +}; + +struct SimpleSPGoal : public SPGoal{ + std::string _to; + SimpleSPGoal(std::string to):_to(to){}; + ~SimpleSPGoal(){} + int operator()(const SPInfo* node) const{ + if (node->name == _to) + return 1; + return 0; + } +}; + class Bot { public: Bot(const std::string& name, PlayerType type); - virtual ~Bot(); + virtual ~Bot(){}; virtual void play(); protected: void buildGraph(); void updateWorld(); - virtual std::string turn(); + virtual std::string turn() = 0; void move(std::string location); - std::list shortestPath(const std::string& from, const std::string& to, PlayerType type); + std::list shortestPath(const std::string& from, PlayerType type, const SPGoal& goal); __gnu_cxx::hash_map _intersections; __gnu_cxx::hash_map _players; @@ -84,5 +108,4 @@ class Bot { int _smell; }; - #endif diff --git a/robber/robber.cpp b/robber/robber.cpp index 4e2ec89..d8154c0 100644 --- a/robber/robber.cpp +++ b/robber/robber.cpp @@ -6,17 +6,51 @@ using namespace std; using namespace __gnu_cxx; +struct FindCop : SPGoal{ + int _limit; + const hash_map& _players; + FindCop(const hash_map& players, int limit = 0) : _players(players), _limit(limit){} + int operator()(const SPInfo* node) const{ + if (_limit > 0 && node->cost > _limit) + return -1; + for(hash_map::const_iterator player = _players.begin(); + player != _players.end(); ++player){ + if (player->second.type != robber && player->second.location == node->name){ + return 1; + } + } + return 0; + } +}; + string Robber::turn(){ 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; + } double goodness = 10; - int curx = _intersections[_location].x; - int cury = _intersections[_location].y; + Intersection& conInter = _intersections[street->first]; + + if (conInter.type == bank){ + cerr << "FOUND A BANK" << endl; + list l = shortestPath(_location, _type, FindCop(_players, 3)); + if (l.size() > 0){ + cerr << "Cop " << l.size() << " intersections away." << endl; + goodness = 0; + }else if (_banks[street->first] > 0){ + cerr << "No cop close to bank" << endl; + return street->first; + } + } + int curx = inter.x; + int cury = inter.y; - int newx = _intersections[street->first].x; - int newy = _intersections[street->first].y; + int newx = conInter.x; + int newy = conInter.y; for (hash_map::const_iterator player = _players.begin(); player != _players.end(); ++player){ if (player->first == _name) @@ -52,11 +86,13 @@ string Robber::turn(){ bank != _banks.end(); ++bank){ //cerr << "Handling bank at: " << bank->first << endl; if (bank->second > 0){ - list l = shortestPath(_location, bank->first,_type); - if (l.size() < 1) + list l = shortestPath(_location, _type, SimpleSPGoal(bank->first)); + if (l.size() < 2) continue; list::iterator i = l.begin(); - streets[*++i] += bank->second/(pow(5.0,double(l.size()))); + if (*++i == "53-and-kimbark") + cerr << "We should NOT find 53-and-kimbark here" << endl; + streets[*i] += bank->second/(pow(5.0,double(l.size()))); } } diff --git a/robber/robber.h b/robber/robber.h index 5dea90a..3ba0871 100644 --- a/robber/robber.h +++ b/robber/robber.h @@ -1,7 +1,7 @@ #ifndef __ROBBER_H__ #define __ROBBER_H__ -#include +#include "bot.h" class Robber : public Bot { public: diff --git a/robber/robber.pro b/robber/robber.pro index b3f79ad..2ad532c 100644 --- a/robber/robber.pro +++ b/robber/robber.pro @@ -10,5 +10,5 @@ unix:LIBS += -lm # Input -HEADERS += robber.h +HEADERS += robber.h ../bot/bot.h SOURCES += robber.cpp ../bot/bot.cpp -- 2.39.2