hex::move::Topography

hex::move::Topography Class Reference

#include <hexmove.h>

List of all members.

Detailed Description

Models movement costs in a hex grid.

Definition at line 49 of file hexmove.h.

Public Member Functions

 Topography ()
 Topography (Cost default_hex_cost)
virtual ~Topography ()
std::set< hex::Hex * > accessible (void) const
 Calculate set of accessible hexes.
void increase_hex_cost (hex::Hex *h, Cost c)
 Increases the cost of hex h by c.
void override_hex_cost (hex::Hex *h, Cost c)
 Set the cost of hex h to c.
void increase_edge_cost (hex::Edge *e, Cost c)
 Increases the cost of edge e by c.
void override_edge_cost (hex::Edge *e, Cost c)
 Set the cost of edge e to c.
void increase_cost (const hex::Area &a, Cost c)
void override_cost (const hex::Area &a, Cost c)
void increase_cost (const hex::Boundary &b, Cost c)
void override_cost (const hex::Boundary &b, Cost c)
hex::Path best_path (hex::Hex *start, hex::Hex *goal) const throw (no_solution)
 Finds the least-cost hex::Path from start to goal.
hex::Area horizon (hex::Hex *start, Cost budget) const throw (no_solution)
 Finds the hex::Area that can be reached from start with budget.

Protected Member Functions

Step step (hex::Hex *from_hex, Direction direction) const
 Calculates the cost to move one step from_hex in direction.

Classes

struct  Step

Constructor & Destructor Documentation

hex::move::Topography::Topography (  ) 

Definition at line 33 of file move.cc.

00034   : _has_default(false), _default(0.0), _hexes(), _edges()
00035   {}

hex::move::Topography::Topography ( Cost  default_hex_cost  ) 

Definition at line 38 of file move.cc.

00039   : _has_default(true), _default(default_hex_cost), _hexes(), _edges()
00040   {}

virtual hex::move::Topography::~Topography (  )  [inline, virtual]

Definition at line 63 of file hexmove.h.

00063 {}

Member Function Documentation

std::set< hex::Hex * > hex::move::Topography::accessible ( void   )  const

Calculate set of accessible hexes.

Definition at line 44 of file move.cc.

00045 {
00046   using namespace std;
00047   set<hex::Hex*> result;
00048   for(map<hex::Hex*,Cost>::const_iterator i=_hexes.begin(); i!=_hexes.end();++i)
00049     result.insert(i->first);
00050   for(map<hex::Edge*,Cost>::const_iterator i=_edges.begin();i!=_edges.end();++i)
00051     result.insert(i->first->hex());
00052   return result;
00053 }

void hex::move::Topography::increase_hex_cost ( hex::Hex *  h,
Cost  c 
)

Increases the cost of hex h by c.

Definition at line 57 of file move.cc.

References hex::A, hex::DIRECTIONS, and hex::Hex::edge().

Referenced by increase_cost().

00058 {
00059   {
00060     std::map<hex::Hex*,Cost>::iterator pos = _hexes.find(h);
00061     if(pos==_hexes.end())
00062         _hexes[h] = _default + c;
00063     else
00064         pos->second += c;
00065   }
00066   for(int d=0; d<DIRECTIONS; ++d)
00067   {
00068     hex::Edge* e =h->edge(hex::A+d);
00069     std::map<hex::Edge*,Cost>::iterator pos = _edges.find(e);
00070     if(pos!=_edges.end())
00071         pos->second += c;
00072   }
00073 }

void hex::move::Topography::override_hex_cost ( hex::Hex *  h,
Cost  c 
)

Set the cost of hex h to c.

Definition at line 77 of file move.cc.

References hex::A, hex::DIRECTIONS, and hex::Hex::edge().

Referenced by override_cost().

00078 {
00079   _hexes[h] = c;
00080   for(int d=0; d<DIRECTIONS; ++d)
00081   {
00082     hex::Edge* e =h->edge(hex::A+d);
00083     _edges.erase(e);
00084   }
00085 }

void hex::move::Topography::increase_edge_cost ( hex::Edge *  e,
Cost  c 
)

Increases the cost of edge e by c.

Definition at line 87 of file move.cc.

References hex::Edge::hex().

Referenced by increase_cost().

00088 {
00089   if(!e)
00090     return;
00091   std::map<hex::Edge*,Cost>::iterator epos = _edges.find(e);
00092   if(epos==_edges.end())
00093   {
00094     std::map<hex::Hex*,Cost>::iterator hpos = _hexes.find( e->hex() );
00095     if(hpos!=_hexes.end())
00096       _edges[e] = hpos->second + c;
00097     else if(_has_default)
00098       _edges[e] = _default + c;
00099   }
00100   else
00101   {
00102     epos->second += c;
00103   }
00104 }

void hex::move::Topography::override_edge_cost ( hex::Edge *  e,
Cost  c 
)

Set the cost of edge e to c.

Definition at line 108 of file move.cc.

Referenced by override_cost().

00109 {
00110   if(e)
00111     _edges[e] = c;
00112 }

void hex::move::Topography::increase_cost ( const hex::Area &  a,
Cost  c 
)

Definition at line 116 of file move.cc.

References hex::Area::hexes(), and increase_hex_cost().

Referenced by main().

00117 {
00118   const std::set<hex::Hex*>& hexes = a.hexes();
00119   for(std::set<hex::Hex*>::const_iterator i=hexes.begin(); i!=hexes.end(); ++i)
00120     increase_hex_cost(*i,c);
00121 }

void hex::move::Topography::override_cost ( const hex::Area &  a,
Cost  c 
)

Definition at line 125 of file move.cc.

References hex::Area::hexes(), and override_hex_cost().

00126 {
00127   const std::set<hex::Hex*>& hexes = a.hexes();
00128   for(std::set<hex::Hex*>::const_iterator i=hexes.begin(); i!=hexes.end(); ++i)
00129     override_hex_cost(*i,c);
00130 }

void hex::move::Topography::increase_cost ( const hex::Boundary &  b,
Cost  c 
)

Definition at line 134 of file move.cc.

References hex::Boundary::edges(), and increase_edge_cost().

00135 {
00136   const std::list<hex::Edge*>& edges = b.edges();
00137   for(std::list<hex::Edge*>::const_iterator i=edges.begin(); i!=edges.end(); ++i)
00138     increase_edge_cost(*i,c);
00139 }

void hex::move::Topography::override_cost ( const hex::Boundary &  b,
Cost  c 
)

Definition at line 143 of file move.cc.

References hex::Boundary::edges(), and override_edge_cost().

00144 {
00145   const std::list<hex::Edge*>& edges = b.edges();
00146   for(std::list<hex::Edge*>::const_iterator i=edges.begin(); i!=edges.end(); ++i)
00147     override_edge_cost(*i,c);
00148 }

hex::Path hex::move::Topography::best_path ( hex::Hex *  start,
hex::Hex *  goal 
) const throw (no_solution)

Finds the least-cost hex::Path from start to goal.

Uses the A* algorithm.

Definition at line 152 of file move.cc.

References hex::A, hex::DIRECTIONS, and hex::move::_Route::factory().

Referenced by main().

00153 {
00154   std::set<hex::Hex*> visited;
00155   std::multiset<_Route> queue;
00156   queue.insert( _Route::factory(start,goal) );
00157   while(!queue.empty())
00158   {
00159     _Route curr_route = *queue.begin();
00160     queue.erase( queue.begin() );
00161     hex::Hex* curr_hex = curr_route.path.back();
00162     if(visited.count(curr_hex))
00163         continue;
00164     if(curr_hex==goal)
00165         return hex::Path(curr_route.path);
00166     visited.insert(curr_hex);
00167     for(int dir=0; dir<DIRECTIONS; ++dir)
00168     {
00169       Topography::Step s = step(curr_hex,hex::A+dir);
00170       if(s.to_hex && 0==visited.count(s.to_hex))
00171           queue.insert( curr_route.step(s.to_hex,s.cost,goal) );
00172     }
00173   }
00174   throw no_solution("best_path");
00175 }

hex::Area hex::move::Topography::horizon ( hex::Hex *  start,
Cost  budget 
) const throw (no_solution)

Finds the hex::Area that can be reached from start with budget.

Definition at line 179 of file move.cc.

References hex::A, hex::DIRECTIONS, and hex::move::_Route::factory().

Referenced by main().

00180 {
00181   std::set<hex::Hex*> visited;
00182   std::multiset<_Route> queue;
00183   queue.insert( _Route::factory(start) );
00184   while(!queue.empty())
00185   {
00186     _Route curr_route = *queue.begin();
00187     queue.erase( queue.begin() );
00188     hex::Hex* curr_hex = curr_route.path.back();
00189     if(visited.count(curr_hex))
00190         continue;
00191     if(curr_route.cost > budget)
00192         continue;
00193     visited.insert(curr_hex);
00194     for(int dir=0; dir<DIRECTIONS; ++dir)
00195     {
00196       Topography::Step s = step(curr_hex,hex::A+dir);
00197       if(s.to_hex && 0==visited.count(s.to_hex))
00198           queue.insert( curr_route.step(s.to_hex,s.cost) );
00199     }
00200   }
00201   return visited;
00202 }

Topography::Step hex::move::Topography::step ( hex::Hex *  from_hex,
Direction  direction 
) const [protected]

Calculates the cost to move one step from_hex in direction.

Returns tuple: (to_hex,cost) If the move is off-limits, then returns (None,None).

Definition at line 206 of file move.cc.

References hex::move::Topography::Step::cost, hex::Hex::edge(), hex::Hex::go(), and hex::move::Topography::Step::to_hex.

00207 {
00208   Step result = {NULL,_default};
00209   // Find destination
00210   result.to_hex = from_hex->go(direction);
00211   if(!result.to_hex)
00212     return result;
00213   // If there's an edge cost, then use that.
00214   hex::Edge* to_edge = result.to_hex->edge(direction+3);
00215   std::map<hex::Edge*,Cost>::const_iterator epos = _edges.find(to_edge);
00216   if(epos!=_edges.end())
00217   {
00218     result.cost = epos->second;
00219     return result;
00220   }
00221   // Otherwise use cost of to_hex
00222   std::map<hex::Hex*,Cost>::const_iterator hpos = _hexes.find( result.to_hex );
00223   if(hpos!=_hexes.end())
00224       result.cost = hpos->second;
00225   else if(!_has_default)
00226       result.to_hex = NULL;
00227   return result;
00228 }

The documentation for this class was generated from the following files:
Generated on Thu Feb 21 00:00:55 2008 for libhex by  doxygen 1.5.1