hex Namespace Reference

---

Detailed Description

Library for manipulating hexagonal grids.

Supports arbitrary areas and paths.

Classes
class	exception
	Base class for hex exceptions. More...
class	invalid_argument
class	out_of_range
struct	Point
	X-Y coordinate. More...
class	Grid
	A square field of hexagons that form the universe in which the other objects exist. More...
class	Edge
	The interface between a hex and one of its six neighbours. More...
class	Hex
	A single hexagonal quanta of area. More...
class	Area
	A connected set of hexes. More...
class	Path
	A sequence of adjacent hexes. More...
class	Boundary
	A sequence of adjacent edges. More...
Namespaces
namespace	move
	Find routes and movement horizons on a hex grid.
namespace	svg
	Output hex:: objects as Scalable Vector Graphics (SVG) - which you can easily convert to PNG or JPG.
Typedefs
typedef double	Distance
Enumerations
enum	Direction {   A = 0, B = 1, C = 2, D = 3,   E = 4, F = 5 }
	The six directions are labelled A to F anti-clockwise. More...
Functions
void	go (int &i, int &j, Direction d, int distance=1)
	Translates coordinates i,j in direction d.
void	go (int &i, int &j, const std::string &steps)
	Translates coordinates i,j along steps.
std::string	steps (const Hex *from, const Hex *to)
	Calculates a minimum-length path between two hexes.
int	distance (const Hex *from, const Hex *to)
	The length of the shortest path between two hexes.
std::set< Hex * >	range (Hex *h, int distance)
	Calculates the set of hexes that are range r from hex h.
std::set< Hex * >	set_difference (const std::set< Hex * > &a, const std::set< Hex * > &b)
	The set difference between a and b.
std::set< Hex * >	set_intersection (const std::set< Hex * > &a, const std::set< Hex * > &b)
	The set intersection between a and b.
std::set< Hex * >	set_union (const std::set< Hex * > &a, const std::set< Hex * > &b)
	The set union between a and b.
std::string	set_str (const std::set< Hex * > &a)
	Generates a string representation of hex-set a.
bool	bounding_box (const std::set< Hex * > &a, int &i0, int &j0, int &i1, int &j1)
	Calculate a bounding box for hex-set a.
Area	fill (const std::set< Hex * > &beyond, Hex *h)
	Calc.
Area	fill (const std::set< Hex * > &beyond, const Area &a)
	Max.
std::set< Hex * >	extract_connected_set (std::set< Hex * > &s)
	Helper: Find the connected set (Area) that contains the first hex in s.
std::list< Area >	areas (const std::set< Hex * > &s)
	Find all of the Areas (connected sets) in s.
bool	is_connected (const std::set< Hex * > &s)
	TRUE iff s is connected.
std::list< Boundary >	skeleton (const std::list< Area > &a, bool include_boundary=true)
	The skeletons of areas a.
Direction	to_direction (char c) throw (hex::invalid_argument)
char	to_char (Direction d)
Direction &	operator+= (Direction &d, int i)
Direction	operator+ (const Direction &d, int i)
Direction &	operator++ (Direction &d)
	Prefix increment.
Direction	operator++ (const Direction &d, int)
	Postfix increment.
Direction &	operator-= (Direction &d, int i)
Direction	operator- (const Direction &d, int i)
Direction &	operator-- (Direction &d)
	Prefix decrement.
Direction	operator-- (const Direction &d, int)
	Postfix decrement.
std::ostream &	operator<< (std::ostream &os, const Direction &d)
std::string	rotate (const std::string &steps, int i)
	steps is a string of characters A-F, representing a set of Directions.
Point	corner_offset (Point p, Direction d, float bias)
	Helper function.
std::list< Hex * >	path (Hex *start, const std::string &steps) throw (hex::out_of_range,hex::invalid_argument)
	Helper: populate _hexes from steps.
Variables
const Distance	M_SQRT3 = 1.73205080756887729352744634150587236
const Distance	I = 1.0
	Distance between centres of adjacent hexes.
const Distance	J = M_SQRT3/2.0
	Distance between adjacent hex rows.
const Distance	K = 1.0/M_SQRT3
	Length of hex's edge.
const int	DIRECTIONS = 6

---

Typedef Documentation

typedef double hex::Distance

Definition at line 107 of file hex.h.

---

Enumeration Type Documentation

enum hex::Direction

The six directions are labelled A to F anti-clockwise.

Direction 'A' is 'East' along the x-axis. 'B' is 'North-East' and so-on.

Enumerator:

A	--->
B
C
D	<---
E
F

Definition at line 119 of file hex.h.

{  A=0, B=1, C=2,  D=3, E=4, F=5 };

---

Function Documentation

std::list< Area > hex::areas

(

const std::set< Hex * > &

s

)

Find all of the Areas (connected sets) in s.

Definition at line 272 of file algorithm.cc.

References extract_connected_set().

Referenced by hex::Area::enclosed_areas().

{
  std::set<Hex*> unallocated = s;
  std::list<Area> result;
  while(!unallocated.empty())
  {
    result.push_back( extract_connected_set(unallocated) );
  }
  return result;
}

bool hex::bounding_box	(	const std::set< Hex * > &	a,
		int &	i0,
		int &	j0,
		int &	i1,
		int &	j1
	)

Calculate a bounding box for hex-set a.

Returns FALSE if a is empty.

Definition at line 196 of file algorithm.cc.

{
  for(std::set<Hex*>::const_iterator h=a.begin(); h!=a.end(); ++h)
  {
    if(h==a.begin())
    {
      i0 = i1 = (**h).i;
      j0 = j1 = (**h).j;
    }
    else
    {
      i0 = std::min(i0,(**h).i);
      j0 = std::min(j0,(**h).j);
      i1 = std::max(i1,(**h).i);
      j1 = std::max(j1,(**h).j);
    }
  }
  return !a.empty();
}

Point hex::corner_offset	(	Point	p,
		Direction	d,
		float	bias
	)

Helper function.

Offsets p towards the start_point of edge d.

Definition at line 74 of file edge.cc.

References A, B, C, D, E, F, I, K, and hex::Point::offset().

Referenced by hex::Edge::join_point(), and hex::Edge::start_point().

{
  Distance dx =0.0;
  Distance dy =0.0;
  switch(d)
  {
    case A: dx =  I/2.0; dy = -K/2.0; break;
    case B: dx =  I/2.0; dy =  K/2.0; break;
    case C: dx =    0.0; dy =  K    ; break;
    case D: dx = -I/2.0; dy =  K/2.0; break;
    case E: dx = -I/2.0; dy = -K/2.0; break;
    case F: dx =    0.0; dy = -K    ; break;
  }
  if(bias==0.0)
      return p.offset(dx,dy);
  else
      return p.offset(dx*(1.0+bias),dy*(1.0+bias));
}

int hex::distance	(	const Hex *	from,
		const Hex *	to
	)

The length of the shortest path between two hexes.

Definition at line 107 of file algorithm.cc.

References steps().

Referenced by hex::Area::go().

{
  return steps(from,to).size();
}

std::set<Hex*> hex::extract_connected_set

(

std::set< Hex * > &

s

)

[inline]

Helper: Find the connected set (Area) that contains the first hex in s.

Definition at line 249 of file algorithm.cc.

References range(), and set_intersection().

Referenced by areas(), and is_connected().

{
  std::set<Hex*> result;
  std::set<Hex*> queue; // Hexes in result that have not yet been checked.
  Hex* h =*s.begin(); // Just pick a random hex in s.
  while(true)
  {
    result.insert(h);
    s.erase(h);
    if(s.empty())
        break; // optimisation - not strictly necessary.
    std::set<Hex*> range1 =set_intersection( s, range(h,1) );
    queue.insert( range1.begin(), range1.end() );
    if(queue.empty())
        break;
    h = *queue.begin();
    queue.erase( queue.begin() );
  }
  return result;
}

Area hex::fill	(	const std::set< Hex * > &	beyond,
		const Area &	a
	)

Max.

area that contains hexes in a, but does not intersect beyond.

Definition at line 225 of file algorithm.cc.

References A, DIRECTIONS, and hex::Area::hexes().

{
  std::set<Hex*> queue   =a.hexes();
  std::set<Hex*> result  =a.hexes();
  while(!queue.empty())
  {
    Hex* h = *queue.begin();
    queue.erase( queue.begin() );
    for(int d=0; d<DIRECTIONS; ++d)
    {
      Hex* hd =h->go(A+d);
      if(!beyond.count(hd) && !result.count(hd))
      {
        queue.insert(hd);
        result.insert(hd);
      }
    }
  }
  return result;
}

Area hex::fill	(	const std::set< Hex * > &	beyond,
		Hex *	h
	)

Calc.

the max. area that contains h, but does not intersect beyond.

Definition at line 218 of file algorithm.cc.

Referenced by hex::Boundary::area().

{
  return fill( beyond, Area(h) );
}

void hex::go	(	int &	i,
		int &	j,
		const std::string &	steps
	)

Translates coordinates i,j along steps.

Definition at line 60 of file algorithm.cc.

References go(), and to_direction().

{
  for(std::string::const_iterator s=steps.begin(); s!=steps.end(); ++s)
    if('A'<=*s && *s<='F')
        go(i,j,to_direction(*s));
    else
        break; // Just bail out if we encounter a non-Direction character.
}

void hex::go	(	int &	i,
		int &	j,
		Direction	d,
		int	distance = 1
	)

Translates coordinates i,j in direction d.

Definition at line 33 of file algorithm.cc.

References A, B, C, D, E, and F.

Referenced by hex::Hex::go(), go(), hex::Grid::hex(), range(), and steps().

{
  for(; distance>0; --distance)
      if(j%2)
          switch(d) // odd
          {
            case A: ++i;      break;
            case B: ++i; ++j; break;
            case C:      ++j; break;
            case D: --i;      break;
            case E:      --j; break;
            case F: ++i; --j; break;
          }
      else
          switch(d) // even
          {
            case A: ++i;      break;
            case B:      ++j; break;
            case C: --i; ++j; break;
            case D: --i;      break;
            case E: --i; --j; break;
            case F:      --j; break;
          }
}

bool hex::is_connected

(

const std::set< Hex * > &

s

)

TRUE iff s is connected.

Definition at line 285 of file algorithm.cc.

References extract_connected_set().

Referenced by hex::Area::Area().

{
  std::set<Hex*> unallocated = s;
  extract_connected_set( unallocated );
  return unallocated.empty();
}

Direction hex::operator+	(	const Direction &	d,
		int	i
	)

Definition at line 54 of file direction.cc.

{
  Direction result =d;
  result+=i;
  return result;
}

Direction hex::operator++	(	const Direction &	d,
		int
	)

Postfix increment.

Definition at line 68 of file direction.cc.

{
  Direction result =d;
  ++result;
  return result;
}

Direction & hex::operator++

(

Direction &

d

)

Prefix increment.

Definition at line 62 of file direction.cc.

{
  return d+=1;
}

Direction & hex::operator+=	(	Direction &	d,
		int	i
	)

Definition at line 44 of file direction.cc.

References DIRECTIONS.

{
  int d_ =static_cast<int>( d );
  d_= (d_+i) % DIRECTIONS;
  while(d_<0)
    d_ += DIRECTIONS;
  d=static_cast<Direction>( d_ );
  return d;
}

Direction hex::operator-	(	const Direction &	d,
		int	i
	)

Definition at line 80 of file direction.cc.

{
  return d + (-i);
}

Direction hex::operator--	(	const Direction &	d,
		int
	)

Postfix decrement.

Definition at line 92 of file direction.cc.

{
  Direction result =d;
  --result;
  return result;
}

Direction & hex::operator--

(

Direction &

d

)

Prefix decrement.

Definition at line 86 of file direction.cc.

{
  return d-=1;
}

Direction & hex::operator-=	(	Direction &	d,
		int	i
	)

Definition at line 75 of file direction.cc.

{
  return d += (-i);
}

std::ostream & hex::operator<<	(	std::ostream &	os,
		const Direction &	d
	)

Definition at line 99 of file direction.cc.

References to_char().

{
  os << to_char(d);
  return os;
}

std::list<Hex*> hex::path	(	Hex *	start,
		const std::string &	steps
	)			throw (hex::out_of_range,hex::invalid_argument) [inline]

Helper: populate _hexes from steps.

Definition at line 74 of file path.cc.

References steps(), and to_direction().

Referenced by hex::Area::fillpaths().

{
  // See also: go(int&,int&,const std::string&)
  std::list<Hex*> hexes;
  hexes.push_back(start);
  std::string::size_type cur =0;
  while(cur<steps.size() && steps[cur]!='?')
  {
    // Find direction
    Direction dir =to_direction( steps[cur] );
    ++cur;
    bool repeat =(cur<steps.size() && steps[cur]=='*');
    do{
        Hex* next =hexes.back()->go( dir );
        if(next)
            hexes.push_back( next );
        else if(*steps.rbegin()=='?' || repeat)
            return hexes; // bail out instead of throwing
        else
            throw hex::out_of_range(start->str()+":"+steps);
    } while(repeat);
  }
  return hexes;
}

std::set< Hex * > hex::range	(	Hex *	h,
		int	distance
	)

Calculates the set of hexes that are range r from hex h.

The result may NOT be a valid Area, since it may be cut into several pieces by the edge of the grid.

Definition at line 114 of file algorithm.cc.

References A, C, DIRECTIONS, go(), hex::Hex::grid(), hex::Grid::hex(), hex::Hex::i, and hex::Hex::j.

Referenced by hex::Area::Area(), extract_connected_set(), and main().

{
  std::set<Hex*> result;
  if(distance<1)
  {
    result.insert(h);
  }
  else
  {
    const Grid& grid =h->grid();
    int i =h->i;
    int j =h->j;
  
    try {
      go(i,j,hex::A,distance); // in/out: i,j
      result.insert( grid.hex(i,j) );
    } catch(hex::out_of_range&) {}
  
    for(int d=0; d<DIRECTIONS; ++d)
    {
      Direction direction =C+d;
      for(int count=0; count<distance; ++count)
          try {
            go(i,j,direction); // in/out: i,j
            result.insert( grid.hex(i,j) );
          } catch(hex::out_of_range&) {}
    }
  }
  return result;
}

std::string hex::rotate	(	const std::string &	steps,
		int	i
	)

steps is a string of characters A-F, representing a set of Directions.

This function rotates each step by i.

Definition at line 106 of file direction.cc.

References to_char(), and to_direction().

{
  // Rotate all letters A-F, but leave other characters alone.
  std::string result =steps;
  for(std::string::iterator c=result.begin(); c!=result.end(); ++c)
      if('A'<=*c && *c<='F')
      {
        Direction d =to_direction(*c);
        *c = to_char(d+i);
      }
  return result;
}

std::set< Hex * > hex::set_difference	(	const std::set< Hex * > &	a,
		const std::set< Hex * > &	b
	)

The set difference between a and b.

Definition at line 147 of file algorithm.cc.

Referenced by hex::Area::enclosed_areas().

{
  std::set<Hex*> result;
  std::set_difference(
    a.begin(),a.end(),
    b.begin(),b.end(),
    std::inserter(result,result.end())
  );
  return result;
}

std::set< Hex * > hex::set_intersection	(	const std::set< Hex * > &	a,
		const std::set< Hex * > &	b
	)

The set intersection between a and b.

Definition at line 160 of file algorithm.cc.

Referenced by extract_connected_set().

{
  std::set<Hex*> result;
  std::set_intersection(
    a.begin(),a.end(),
    b.begin(),b.end(),
    std::inserter(result,result.end())
  );
  return result;
}

std::string hex::set_str

(

const std::set< Hex * > &

a

)

Generates a string representation of hex-set a.

Definition at line 186 of file algorithm.cc.

{
  std::ostringstream ss;
  for(std::set<Hex*>::const_iterator h=a.begin(); h!=a.end(); ++h)
      ss<<(**h).str()<<" ";
  return ss.str();
}

std::set< Hex * > hex::set_union	(	const std::set< Hex * > &	a,
		const std::set< Hex * > &	b
	)

The set union between a and b.

Definition at line 173 of file algorithm.cc.

{
  std::set<Hex*> result;
  std::set_union(
    a.begin(),a.end(),
    b.begin(),b.end(),
    std::inserter(result,result.end())
  );
  return result;
}

std::list< Boundary > hex::skeleton	(	const std::list< Area > &	a,
		bool	include_boundary = true
	)

The skeletons of areas a.

Definition at line 294 of file algorithm.cc.

{
  std::list<Boundary> result;
  for(std::list<Area>::const_iterator iter=a.begin(); iter!=a.end(); ++iter)
  {
    std::list<Boundary> b =iter->skeleton(include_boundary);
    std::copy(b.begin(),b.end(),inserter(result,result.end()));
  }
  return result;
}

std::string hex::steps	(	const Hex *	from,
		const Hex *	to
	)

Calculates a minimum-length path between two hexes.

The result is one of many possible solutions.

Definition at line 71 of file algorithm.cc.

References A, B, C, D, E, F, go(), hex::Hex::i, hex::Hex::j, and to_char().

Referenced by hex::Grid::area(), distance(), hex::Area::go(), path(), hex::Path::steps(), and hex::Area::str().

{
  std::string result ="";
  int i =from->i;
  int j =from->j;
  const int to_i =to->i;
  const int to_j =to->j;
  Direction direction;
  while(true)
  {
    if( j < to_j )                                   // go up
    {
        if(      i < to_i )          direction = B;
        else if( i > to_i || j%2 )   direction = C;
        else                         direction = B;
    }
    else if( j > to_j )                              // go down
    {
        if(      i < to_i )          direction = F;
        else if( i > to_i || j%2 )   direction = E;
        else                         direction = F;
    }
    else // j == to_j                                // go across
    {
        if(      i < to_i )          direction = A;
        else if( i > to_i )          direction = D;
        else                         break;          //  Done!
    }
    result += to_char(direction);
    go(i,j,direction);
  }
  return result;
}

char hex::to_char

(

Direction

d

)

Definition at line 37 of file direction.cc.

References A.

Referenced by operator<<(), rotate(), steps(), and hex::Boundary::str().

{
  static const char root =static_cast<char>( A );
  return static_cast<char>( 'A' + (static_cast<char>(d) - root) );
}

Direction hex::to_direction

(

char

c

)

throw (hex::invalid_argument)

Definition at line 29 of file direction.cc.

References A.

Referenced by hex::Grid::boundary(), go(), path(), and rotate().

{
  if(c<'A' || c>'F')
      throw hex::invalid_argument(std::string("to_direction:")+c);
  return A + static_cast<int>(c-'A');
}

---

Variable Documentation

const int hex::DIRECTIONS = 6

Definition at line 120 of file hex.h.

Referenced by hex::move::Topography::best_path(), fill(), hex::move::Topography::horizon(), hex::move::Topography::increase_hex_cost(), operator+=(), hex::move::Topography::override_hex_cost(), and range().

const Distance hex::I = 1.0

Distance between centres of adjacent hexes.

Definition at line 110 of file hex.h.

Referenced by hex::Hex::centre(), corner_offset(), and hex::Grid::width().

const Distance hex::J = M_SQRT3/2.0

Distance between adjacent hex rows.

Definition at line 111 of file hex.h.

Referenced by hex::Hex::centre(), hex::Grid::height(), and hex::Grid::hex().

const Distance hex::K = 1.0/M_SQRT3

Length of hex's edge.

Definition at line 112 of file hex.h.

Referenced by hex::Hex::centre(), corner_offset(), hex::Grid::height(), and hex::Grid::hex().

const Distance hex::M_SQRT3 = 1.73205080756887729352744634150587236

Definition at line 109 of file hex.h.

---