|
BWAPI
|
|
BWAPI
|
00001 #pragma once 00002 #include <list> 00003 #include <set> 00004 #include <map> 00005 #include <Heap.h> 00006 #include "Controller.h" 00007 namespace Arbitrator 00008 { 00009 template <class _Tp,class _Val> 00010 class Arbitrator 00011 { 00012 public: 00013 Arbitrator(); 00014 bool setBid(Controller<_Tp,_Val>* c, _Tp obj, _Val bid); 00015 bool setBid(Controller<_Tp,_Val>* c, std::set<_Tp> objs, _Val bid); 00016 bool removeBid(Controller<_Tp,_Val>* c, _Tp obj); 00017 bool removeBid(Controller<_Tp,_Val>* c, std::set<_Tp> objs); 00018 bool removeAllBids(Controller<_Tp,_Val>* c); 00019 bool accept(Controller<_Tp,_Val>* c, _Tp obj, _Val bid); 00020 bool accept(Controller<_Tp,_Val>* c, std::set<_Tp> objs, _Val bid); 00021 bool accept(Controller<_Tp,_Val>* c, _Tp obj); 00022 bool accept(Controller<_Tp,_Val>* c, std::set<_Tp> objs); 00023 bool decline(Controller<_Tp,_Val>* c, _Tp obj, _Val bid); 00024 bool decline(Controller<_Tp,_Val>* c, std::set<_Tp> objs, _Val bid); 00025 bool hasBid(_Tp obj) const; 00026 const std::pair<Controller<_Tp,_Val>*, _Val>& getHighestBidder(_Tp obj) const; 00027 const std::list< std::pair<Controller<_Tp,_Val>*, _Val> > getAllBidders(_Tp obj) const; 00028 const std::set<_Tp>& getObjects(Controller<_Tp,_Val>* c) const; 00029 void onRemoveObject(_Tp obj); 00030 _Val getBid(Controller<_Tp,_Val>* c, _Tp obj) const; 00031 void update(); 00032 private: 00033 std::map<_Tp,Heap<Controller<_Tp,_Val>*, _Val> > bids; 00034 std::map<_Tp,Controller<_Tp,_Val>* > owner; 00035 std::map<Controller<_Tp,_Val>*, std::set<_Tp> > objects; 00036 std::set<_Tp> updatedObjects; 00037 std::set<_Tp> objectsCanIncreaseBid; 00038 std::set<_Tp> unansweredObjected; 00039 bool inUpdate; 00040 bool inOnOffer; 00041 bool inOnRevoke; 00042 }; 00043 00044 template <class _Tp,class _Val> 00045 Arbitrator<_Tp,_Val>::Arbitrator() 00046 { 00047 inUpdate=false; 00048 inOnOffer=false; 00049 inOnRevoke=false; 00050 } 00051 00052 template <class _Tp,class _Val> 00053 bool Arbitrator<_Tp,_Val>::setBid(Controller<_Tp,_Val>* c, _Tp obj, _Val bid) 00054 { 00055 if (c == NULL || obj == NULL) 00056 return false; 00057 00058 //can only increase bids of certain objects during update() 00059 if (bids[obj].contains(c) && bid>bids[obj].get(c)) 00060 { 00061 if (inOnRevoke || (inOnOffer && objectsCanIncreaseBid.find(obj)==objectsCanIncreaseBid.end())) 00062 return false; 00063 } 00064 00065 //set the bid for this object and insert the object into the updated set 00066 bids[obj].set(c,bid); 00067 updatedObjects.insert(obj); 00068 return true; 00069 } 00070 00071 template <class _Tp,class _Val> 00072 bool Arbitrator<_Tp,_Val>::setBid(Controller<_Tp,_Val>* c, std::set<_Tp> objs, _Val bid) 00073 { 00074 bool result; 00075 for (std::set<_Tp>::const_iterator o = objs.begin(); o != objs.end(); o++) 00076 { 00077 result |= setBid(c, *o, bid); 00078 } 00079 return result; 00080 } 00081 00082 template <class _Tp,class _Val> 00083 bool Arbitrator<_Tp,_Val>::removeBid(Controller<_Tp,_Val>* c, _Tp obj) 00084 { 00085 if (c == NULL || obj == NULL) 00086 return false; 00087 if (bids[obj].contains(c)) //check to see if the bid exists 00088 { 00089 bids[obj].erase(c); //if so, remove the bid 00090 updatedObjects.insert(obj); //insert the object into the updated set 00091 } 00092 return true; 00093 } 00094 00095 template <class _Tp,class _Val> 00096 bool Arbitrator<_Tp,_Val>::removeBid(Controller<_Tp,_Val>* c, std::set<_Tp> objs) 00097 { 00098 bool result=false; 00099 for (std::set<_Tp>::const_iterator o = objs.begin(); o != objs.end(); o++) 00100 { 00101 result |= removeBid(c, *o); 00102 } 00103 return result; 00104 } 00105 00106 template <class _Tp,class _Val> 00107 bool Arbitrator<_Tp,_Val>::removeAllBids(Controller<_Tp,_Val>* c) 00108 { 00109 if (objects.find(c)==objects.end()) 00110 return false; 00111 return removeBid(c,objects[c]); 00112 } 00113 00114 template <class _Tp,class _Val> 00115 bool Arbitrator<_Tp,_Val>::decline(Controller<_Tp,_Val>* c, _Tp obj, _Val bid) 00116 { 00117 if (c == NULL || obj == NULL) 00118 return false; 00119 if (!inOnOffer) //can only call decline from the onOffer() callback 00120 return false; 00121 if (hasBid(obj)==false) 00122 return false; 00123 if (bids[obj].top().first != c) //only the top bidder/controller can decline an object 00124 return false; 00125 updatedObjects.insert(obj); 00126 unansweredObjected.erase(obj); 00127 00128 //must decrease bid via decline() 00129 if (bids[obj].contains(c) && bid>=bids[obj].get(c)) 00130 bid=0; 00131 00132 objectsCanIncreaseBid.erase(obj); 00133 00134 if (bid == 0) 00135 { 00136 bids[obj].erase(c); 00137 return true; 00138 } 00139 bids[obj].set(c, bid); 00140 return true; 00141 } 00142 00143 template <class _Tp,class _Val> 00144 bool Arbitrator<_Tp,_Val>::decline(Controller<_Tp,_Val>* c, std::set<_Tp> objs, _Val bid) 00145 { 00146 bool result; 00147 for (std::set<_Tp>::const_iterator o = objs.begin(); o != objs.end(); o++) 00148 { 00149 result |= decline(c, *o, bid); 00150 } 00151 return result; 00152 } 00153 00154 template <class _Tp,class _Val> 00155 bool Arbitrator<_Tp,_Val>::accept(Controller<_Tp,_Val>* c, _Tp obj) 00156 { 00157 if (c == NULL || obj == NULL) 00158 return false; 00159 if (!inOnOffer) //can only call accept from the onOffer() callback 00160 return false; 00161 if (bids[obj].top().first != c) //only the top bidder/controller can accept an object 00162 return false; 00163 unansweredObjected.erase(obj); 00164 if (owner[obj]) //if someone else already own this object, take it away from them 00165 { 00166 inOnOffer=false; 00167 inOnRevoke=true; 00168 owner[obj]->onRevoke(obj,bids[obj].top().second); 00169 inOnRevoke=false; 00170 inOnOffer=true; 00171 objects[owner[obj]].erase(obj); //remove this object from the set of objects owned by the former owner 00172 } 00173 owner[obj] = c; //set the new owner 00174 objects[c].insert(obj); //insert this object into the set of objects owned by this controller 00175 return true; 00176 } 00177 00178 template <class _Tp,class _Val> 00179 bool Arbitrator<_Tp,_Val>::accept(Controller<_Tp,_Val>* c, std::set<_Tp> objs) 00180 { 00181 bool result; 00182 for (std::set<_Tp>::const_iterator o = objs.begin(); o != objs.end(); o++) 00183 { 00184 result |= accept(c, *o); 00185 } 00186 return result; 00187 } 00188 00189 template <class _Tp,class _Val> 00190 bool Arbitrator<_Tp,_Val>::accept(Controller<_Tp,_Val>* c, _Tp obj, _Val bid) 00191 { 00192 //same idea as accept(Controller<_Tp,_Val>* c, _Tp obj), but the controller also specifies a new bid value 00193 if (c == NULL || obj == NULL) 00194 return false; 00195 if (!inOnOffer) //can only call accept from the onOffer() callback 00196 return false; 00197 if (bids[obj].top().first != c) //only the top bidder/controller can accept an object 00198 return false; 00199 unansweredObjected.erase(obj); 00200 if (owner[obj]) //if someone else already own this object, take it away from them 00201 { 00202 inOnOffer=false; 00203 inOnRevoke=true; 00204 owner[obj]->onRevoke(obj, bids[obj].top().second); 00205 inOnRevoke=false; 00206 inOnOffer=true; 00207 objects[owner[obj]].erase(obj); //remove this object from the set of objects owned by the former owner 00208 } 00209 owner[obj] = c; //set the new owner 00210 objects[c].insert(obj); //insert this object into the set of objects owned by this controller 00211 updatedObjects.insert(obj); //since the object was updated, insert it into the updated objects set 00212 00213 //cannot decrease bid via accept() 00214 if (bids[obj].contains(c) && bid<bids[obj].get(c)) 00215 return true; 00216 00217 //update the bid for this object 00218 bids[obj].set(c,bid); 00219 return true; 00220 } 00221 00222 template <class _Tp,class _Val> 00223 bool Arbitrator<_Tp,_Val>::accept(Controller<_Tp,_Val>* c, std::set<_Tp> objs, _Val bid) 00224 { 00225 bool result; 00226 for (std::set<_Tp>::const_iterator o = objs.begin(); o != objs.end(); o++) 00227 { 00228 result |= accept(c, *o, bid); 00229 } 00230 return result; 00231 } 00232 00233 template <class _Tp,class _Val> 00234 bool Arbitrator<_Tp,_Val>::hasBid(_Tp obj) const 00235 { 00236 //returns true if the given object exists in the bids map 00237 return (bids.find(obj)!=bids.end() && !bids.find(obj)->second.empty()); 00238 } 00239 00240 template <class _Tp,class _Val> 00241 const std::pair<Controller<_Tp,_Val>*, _Val>& Arbitrator<_Tp,_Val>::getHighestBidder(_Tp obj) const 00242 { 00243 //returns the controller at the top of the bid heap for this object 00244 return bids.find(obj)->second.top(); 00245 } 00246 00247 template <class _Tp,class _Val> 00248 const std::list< std::pair<Controller<_Tp,_Val>*, _Val> > Arbitrator<_Tp,_Val>::getAllBidders(_Tp obj) const 00249 { 00250 //returns all bidders for this object 00251 std::list< std::pair<Controller<_Tp,_Val>*, _Val> > bidders; 00252 if (bids.find(obj)==bids.end()) 00253 return bidders; //return empty list if we cannot find this object 00254 00255 Heap<Controller<_Tp,_Val>*, _Val> bid_heap=bids.find(obj)->second; //get the bid heap 00256 00257 //push the bidders into the bidders list from top to bottom 00258 while(!bid_heap.empty()) 00259 { 00260 bidders.push_back(bid_heap.top()); 00261 bid_heap.pop(); 00262 } 00263 return bidders; 00264 } 00265 00266 template <class _Tp,class _Val> 00267 const std::set<_Tp>& Arbitrator<_Tp,_Val>::getObjects(Controller<_Tp,_Val>* c) const 00268 { 00269 //returns the set of objects owned by this bidder/controller 00270 //if the bidder doesn't exist in this->objects, this will probably crash :/ 00271 return objects.find(c)->second; 00272 } 00273 00274 template <class _Tp,class _Val> 00275 void Arbitrator<_Tp,_Val>::onRemoveObject(_Tp obj) 00276 { 00277 //called from AIModule::onUnitDestroy, remove all memory of the object 00278 bids.erase(obj); 00279 owner.erase(obj); 00280 updatedObjects.erase(obj); 00281 for(std::map<Controller<_Tp,_Val>*, std::set<_Tp> >::iterator c=objects.begin();c!=objects.end();c++) 00282 { 00283 (*c).second.erase(obj); 00284 } 00285 } 00286 00287 template <class _Tp,class _Val> 00288 _Val Arbitrator<_Tp,_Val>::getBid(Controller<_Tp,_Val>* c, _Tp obj) const 00289 { 00290 //returns the bid the given controller has on the given object 00291 return bids.find(obj)->second.get(c); 00292 } 00293 00294 template <class _Tp,class _Val> 00295 void Arbitrator<_Tp,_Val>::update() 00296 { 00297 this->inUpdate=true; 00298 bool first=true; 00299 //first we construct a map for the objects to offer 00300 std::map<Controller<_Tp,_Val>*, std::set<_Tp> > objectsToOffer; 00301 00302 while(first || !objectsToOffer.empty()) 00303 { 00304 first=false; 00305 objectsToOffer.clear(); 00306 00307 this->objectsCanIncreaseBid.clear(); 00308 00309 //go through all the updated objects 00310 for(std::set<_Tp>::iterator i = updatedObjects.begin(); i != updatedObjects.end(); i++) 00311 { 00312 if (!bids[*i].empty()) //if there is a bid on this object 00313 { 00314 if (owner.find(*i) == owner.end() || bids[*i].top().first != owner[*i]) //if the top bidder is not the owner 00315 objectsToOffer[bids[*i].top().first].insert(*i); //make a note to offer it to the top bidder. 00316 } 00317 else 00318 { 00319 //no bids on this object, remove it from the owner if there is one 00320 if (owner.find(*i) != owner.end()) 00321 { 00322 _Val temp=0; 00323 owner.find(*i)->second->onRevoke(*i,temp); 00324 owner.erase(*i); 00325 } 00326 } 00327 } 00328 //reset updated objects 00329 updatedObjects.clear(); 00330 00331 //offer the objects to the top bidders 00332 for(std::map< Controller<_Tp,_Val>*, std::set<_Tp> >::iterator i = objectsToOffer.begin(); i != objectsToOffer.end(); i++) 00333 { 00334 objectsCanIncreaseBid=i->second; 00335 unansweredObjected=i->second; 00336 00337 inOnOffer=true; 00338 i->first->onOffer(i->second); 00339 inOnOffer=false; 00340 00341 //decline all unanswered objects 00342 for(std::set<_Tp>::iterator j=unansweredObjected.begin();j!=unansweredObjected.end();j++) 00343 decline(i->first,*j,0); 00344 } 00345 } 00346 this->inUpdate=false; 00347 } 00348 }
1.7.6.1
