• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • libtdegames
 

libtdegames

  • libtdegames
kgrid2d.h
1 /*
2  This file is part of the TDE games library
3  Copyright (C) 2001-02 Nicolas Hadacek (hadacek@kde.org)
4 
5  This library is free software; you can redistribute it and/or
6  modify it under the terms of the GNU Library General Public
7  License version 2 as published by the Free Software Foundation.
8 
9  This library is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  Library General Public License for more details.
13 
14  You should have received a copy of the GNU Library General Public License
15  along with this library; see the file COPYING.LIB. If not, write to
16  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  Boston, MA 02110-1301, USA.
18 */
19 
20 #ifndef __KGRID2D_H_
21 #define __KGRID2D_H_
22 
23 #include <math.h>
24 
25 #include <tqpair.h>
26 #include <tqvaluelist.h>
27 #include <tqvaluevector.h>
28 
29 #include <tdeglobal.h>
30 
31 
32 //-----------------------------------------------------------------------------
33 namespace KGrid2D
34 {
39  typedef TQPair<int, int> Coord;
40 
45  typedef TQValueList<Coord> CoordList;
46 }
47 
48 inline KGrid2D::Coord
49 operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
50  return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
51 }
52 
53 inline KGrid2D::Coord
54 operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
55  return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
56 }
57 
62 inline KGrid2D::Coord
63 maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
64  return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
65 }
70 inline KGrid2D::Coord
71 minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
72  return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
73 }
74 
75 inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::Coord &c) {
76  return s << '(' << c.second << ", " << c.first << ')';
77 }
78 
79 inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::CoordList &list)
80 {
81  for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
82  s << *i;
83  return s;
84 }
85 
86 //-----------------------------------------------------------------------------
87 namespace KGrid2D
88 {
95 template <class Type>
96 class Generic
97 {
98  public:
102  Generic(uint width = 0, uint height = 0) {
103  resize(width, height);
104  }
105 
106  virtual ~Generic() {}
107 
111  void resize(uint width, uint height) {
112  _width = width;
113  _height = height;
114  _vector.resize(width*height);
115  }
116 
120  void fill(const Type &value) {
121  for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
122  }
123 
127  uint width() const { return _width; }
131  uint height() const { return _height; }
135  uint size() const { return _width*_height; }
136 
140  uint index(const Coord &c) const {
141  return c.first + c.second*_width;
142  }
143 
147  Coord coord(uint index) const {
148  return Coord(index % _width, index / _width);
149  }
150 
154  const Type &at(const Coord &c) const { return _vector[index(c)]; }
158  Type &at(const Coord &c) { return _vector[index(c)]; }
162  const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
166  Type &operator [](const Coord &c) { return _vector[index(c)]; }
167 
171  const Type &at(uint index) const { return _vector[index]; }
175  Type &at(uint index) { return _vector[index]; }
179  const Type &operator [](uint index) const { return _vector[index]; }
183  Type &operator [](uint index) { return _vector[index]; }
184 
188  bool inside(const Coord &c) const {
189  return ( c.first>=0 && c.first<(int)_width
190  && c.second>=0 && c.second<(int)_height );
191  }
192 
196  void bound(Coord &c) const {
197  c.first = kMax(kMin(c.first, (int)_width-1), 0);
198  c.second = kMax(kMin(c.second, (int)_height-1), 0);
199  }
200 
201  protected:
202  uint _width, _height;
203  TQValueVector<Type> _vector;
204 };
205 }
206 
207 template <class Type>
208 TQDataStream &operator <<(TQDataStream &s, const KGrid2D::Generic<Type> &m) {
209  s << (TQ_UINT32)m.width() << (TQ_UINT32)m.height();
210  for (uint i=0; i<m.size(); i++) s << m[i];
211  return s;
212 }
213 
214 template <class Type>
215 TQDataStream &operator >>(TQDataStream &s, KGrid2D::Generic<Type> &m) {
216  TQ_UINT32 w, h;
217  s >> w >> h;
218  m.resize(w, h);
219  for (uint i=0; i<m.size(); i++) s >> m[i];
220  return s;
221 }
222 
223 
224 namespace KGrid2D
225 {
226 
227 //-----------------------------------------------------------------------------
234 class SquareBase
235 {
236  public:
240  enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
241  RightUp, RightDown, Nb_Neighbour };
242 
246  static double angle(Neighbour n) {
247  switch (n) {
248  case Left: return M_PI;
249  case Right: return 0;
250  case Up: return M_PI_2;
251  case Down: return -M_PI_2;
252  case LeftUp: return 3.0*M_PI_4;
253  case LeftDown: return -3.0*M_PI_4;
254  case RightUp: return M_PI_4;
255  case RightDown: return -M_PI_4;
256  case Nb_Neighbour: Q_ASSERT(false);
257  }
258  return 0;
259  }
260 
264  static Neighbour opposed(Neighbour n) {
265  switch (n) {
266  case Left: return Right;
267  case Right: return Left;
268  case Up: return Down;
269  case Down: return Up;
270  case LeftUp: return RightDown;
271  case LeftDown: return RightUp;
272  case RightUp: return LeftDown;
273  case RightDown: return LeftUp;
274  case Nb_Neighbour: Q_ASSERT(false);
275  }
276  return Nb_Neighbour;
277  }
278 
283  static bool isDirect(Neighbour n) { return n<LeftUp; }
284 
288  static Coord neighbour(const Coord &c, Neighbour n) {
289  switch (n) {
290  case Left: return c + Coord(-1, 0);
291  case Right: return c + Coord( 1, 0);
292  case Up: return c + Coord( 0, -1);
293  case Down: return c + Coord( 0, 1);
294  case LeftUp: return c + Coord(-1, -1);
295  case LeftDown: return c + Coord(-1, 1);
296  case RightUp: return c + Coord( 1, -1);
297  case RightDown: return c + Coord( 1, 1);
298  case Nb_Neighbour: Q_ASSERT(false);
299  }
300  return c;
301  }
302 };
303 
310 template <class T>
311 class Square : public Generic<T>, public SquareBase
312 {
313  public:
317  Square(uint width = 0, uint height = 0)
318  : Generic<T>(width, height) {}
319 
327  CoordList neighbours(const Coord &c, bool insideOnly = true,
328  bool directOnly = false) const {
329  CoordList neighbours;
330  for (uint i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
331  Coord n = neighbour(c, (Neighbour)i);
332  if ( insideOnly && !Generic<T>::inside(n) ) continue;
333  neighbours.append(n);
334  }
335  return neighbours;
336  }
337 
344  Coord toEdge(const Coord &c, Neighbour n) const {
345  switch (n) {
346  case Left: return Coord(0, c.second);
347  case Right: return Coord(Generic<T>::width()-1, c.second);
348  case Up: return Coord(c.first, 0);
349  case Down: return Coord(c.first, Generic<T>::height()-1);
350  case LeftUp: return Coord(0, 0);
351  case LeftDown: return Coord(0, Generic<T>::height()-1);
352  case RightUp: return Coord(Generic<T>::width()-1, 0);
353  case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
354  case Nb_Neighbour: Q_ASSERT(false);
355  }
356  return c;
357  }
358 };
359 
360 //-----------------------------------------------------------------------------
372 class HexagonalBase
373 {
374  public:
378  enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
379  RightUp, RightDown, Nb_Neighbour };
380 
384  static double angle(Neighbour n) {
385  switch (n) {
386  case Left: return M_PI;
387  case Right: return 0;
388  case LeftUp: return 2.0*M_PI/3;
389  case LeftDown: return -2.0*M_PI/3;
390  case RightUp: return M_PI/3;
391  case RightDown: return -M_PI/3;
392  case Nb_Neighbour: Q_ASSERT(false);
393  }
394  return 0;
395  }
396 
400  static Neighbour opposed(Neighbour n) {
401  switch (n) {
402  case Left: return Right;
403  case Right: return Left;
404  case LeftUp: return RightDown;
405  case LeftDown: return RightUp;
406  case RightUp: return LeftDown;
407  case RightDown: return LeftUp;
408  case Nb_Neighbour: Q_ASSERT(false);
409  }
410  return Nb_Neighbour;
411  }
412 
416  static Coord neighbour(const Coord &c, Neighbour n) {
417  bool oddRow = c.second%2;
418  switch (n) {
419  case Left: return c + Coord(-1, 0);
420  case Right: return c + Coord( 1, 0);
421  case LeftUp: return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
422  case LeftDown: return c + (oddRow ? Coord( 0, 1) : Coord(-1, 1));
423  case RightUp: return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
424  case RightDown: return c + (oddRow ? Coord( 1, 1) : Coord( 0, 1));
425  case Nb_Neighbour: Q_ASSERT(false);
426  }
427  return c;
428  }
429 
433  static uint distance(const Coord &c1, const Coord &c2) {
434  return kAbs(c1.first - c2.first) + kAbs(c1.second - c2.second)
435  + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
436  }
437 };
438 
450 template <class Type>
451 class Hexagonal : public Generic<Type>, public HexagonalBase
452 {
453  public:
457  Hexagonal(uint width = 0, uint height = 0)
458  : Generic<Type>(width, height) {}
459 
466  CoordList neighbours(const Coord &c, bool insideOnly = true) const {
467  CoordList neighbours;
468  for (uint i=0; i<Nb_Neighbour; i++) {
469  Coord n = neighbour(c, (Neighbour)i);
470  if ( insideOnly && !Generic<Type>::inside(n) ) continue;
471  neighbours.append(n);
472  }
473  return neighbours;
474  }
475 
476 
485  CoordList neighbours(const Coord &c, uint distance, bool all,
486  bool insideOnly = true) const {
487  // brute force algorithm -- you're welcome to make it more efficient :)
488  CoordList ring;
489  if ( distance==0 ) return ring;
490  ring = neighbours(c, insideOnly);
491  if ( distance==1 ) return ring;
492  CoordList center;
493  center.append(c);
494  for (uint i=1; i<distance; i++) {
495  CoordList newRing;
496  CoordList::const_iterator it;
497  for (it=ring.begin(); it!=ring.end(); ++it) {
498  CoordList n = neighbours(*it, insideOnly);
499  CoordList::const_iterator it2;
500  for (it2=n.begin(); it2!=n.end(); ++it2)
501  if ( center.find(*it2)==center.end()
502  && ring.find(*it2)==ring.end()
503  && newRing.find(*it2)==newRing.end() )
504  newRing.append(*it2);
505  center.append(*it);
506  }
507  ring = newRing;
508  }
509  if ( !all ) return ring;
510  CoordList::const_iterator it;
511  for (it=ring.begin(); it!=ring.end(); ++it)
512  center.append(*it);
513  center.remove(c);
514  return center;
515  }
516 };
517 
518 } // namespace
519 
520 #endif
KGrid2D::Square
This template is a Generic implementation for a square bidimensionnal grid (SquareBase).
Definition: kgrid2d.h:311
KGrid2D::Generic
This template class represents a generic bidimensionnal grid.
Definition: kgrid2d.h:96
KGrid2D::Hexagonal::neighbours
CoordList neighbours(const Coord &c, bool insideOnly=true) const
Definition: kgrid2d.h:466
KGrid2D::Square::neighbours
CoordList neighbours(const Coord &c, bool insideOnly=true, bool directOnly=false) const
Definition: kgrid2d.h:327
KGrid2D::HexagonalBase
This class contains static methods to manipulate coordinates on an hexagonal grid where hexagons form...
Definition: kgrid2d.h:372
KGrid2D::HexagonalBase::neighbour
static Coord neighbour(const Coord &c, Neighbour n)
Definition: kgrid2d.h:416
KGrid2D::SquareBase::opposed
static Neighbour opposed(Neighbour n)
Definition: kgrid2d.h:264
KGrid2D::Generic::Generic
Generic(uint width=0, uint height=0)
Constructor.
Definition: kgrid2d.h:102
KGrid2D::Generic::at
const Type & at(uint index) const
Definition: kgrid2d.h:171
KGrid2D::Generic::at
Type & at(uint index)
Definition: kgrid2d.h:175
KGrid2D::Hexagonal::neighbours
CoordList neighbours(const Coord &c, uint distance, bool all, bool insideOnly=true) const
Definition: kgrid2d.h:485
KGrid2D::Generic::at
Type & at(const Coord &c)
Definition: kgrid2d.h:158
KGrid2D::Generic::at
const Type & at(const Coord &c) const
Definition: kgrid2d.h:154
KGrid2D::SquareBase::isDirect
static bool isDirect(Neighbour n)
Definition: kgrid2d.h:283
KGrid2D
Definition: kgrid2d.h:33
KGrid2D::Square::toEdge
Coord toEdge(const Coord &c, Neighbour n) const
Definition: kgrid2d.h:344
KGrid2D::Generic::index
uint index(const Coord &c) const
Definition: kgrid2d.h:140
KGrid2D::HexagonalBase::angle
static double angle(Neighbour n)
Definition: kgrid2d.h:384
KGrid2D::Generic::fill
void fill(const Type &value)
Fill the nodes with the given value.
Definition: kgrid2d.h:120
KGrid2D::Generic::height
uint height() const
Definition: kgrid2d.h:131
KGrid2D::Generic::coord
Coord coord(uint index) const
Definition: kgrid2d.h:147
KGrid2D::Generic::resize
void resize(uint width, uint height)
Resize the grid.
Definition: kgrid2d.h:111
KGrid2D::Hexagonal::Hexagonal
Hexagonal(uint width=0, uint height=0)
Constructor.
Definition: kgrid2d.h:457
KGrid2D::Generic::size
uint size() const
Definition: kgrid2d.h:135
KGrid2D::Generic::operator[]
const Type & operator[](const Coord &c) const
Definition: kgrid2d.h:162
KGrid2D::Hexagonal
This template implements a hexagonal grid where hexagons form horizontal lines:
Definition: kgrid2d.h:451
KGrid2D::Generic::width
uint width() const
Definition: kgrid2d.h:127
KGrid2D::SquareBase
This class contains static methods to manipulate coordinates for a square bidimensionnal grid...
Definition: kgrid2d.h:234
KGrid2D::Generic::inside
bool inside(const Coord &c) const
Definition: kgrid2d.h:188
KGrid2D::SquareBase::angle
static double angle(Neighbour n)
Definition: kgrid2d.h:246
KGrid2D::HexagonalBase::opposed
static Neighbour opposed(Neighbour n)
Definition: kgrid2d.h:400
KGrid2D::Square::Square
Square(uint width=0, uint height=0)
Constructor.
Definition: kgrid2d.h:317
KGrid2D::Generic::bound
void bound(Coord &c) const
Bound the given coordinate with the grid dimensions.
Definition: kgrid2d.h:196
KGrid2D::HexagonalBase::distance
static uint distance(const Coord &c1, const Coord &c2)
Definition: kgrid2d.h:433
KGrid2D::SquareBase::Neighbour
Neighbour
Identify the eight neighbours.
Definition: kgrid2d.h:240
KGrid2D::HexagonalBase::Neighbour
Neighbour
Identify the six neighbours.
Definition: kgrid2d.h:378
KGrid2D::SquareBase::neighbour
static Coord neighbour(const Coord &c, Neighbour n)
Definition: kgrid2d.h:288

libtdegames

Skip menu "libtdegames"
  • Main Page
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Class Members
  • Related Pages

libtdegames

Skip menu "libtdegames"
  • libtdegames
Generated for libtdegames by doxygen 1.8.13
This website is maintained by Timothy Pearson.