• 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//-----------------------------------------------------------------------------
33namespace KGrid2D
34{
39 typedef TQPair<int, int> Coord;
40
45 typedef TQValueList<Coord> CoordList;
46}
47
48inline KGrid2D::Coord
49operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
50 return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
51}
52
53inline KGrid2D::Coord
54operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
55 return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
56}
57
62inline KGrid2D::Coord
63maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
64 return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
65}
70inline KGrid2D::Coord
71minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
72 return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
73}
74
75inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::Coord &c) {
76 return s << '(' << c.second << ", " << c.first << ')';
77}
78
79inline 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//-----------------------------------------------------------------------------
87namespace KGrid2D
88{
95template <class Type>
96class 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
207template <class Type>
208TQDataStream &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
214template <class Type>
215TQDataStream &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
224namespace KGrid2D
225{
226
227//-----------------------------------------------------------------------------
234class 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
310template <class T>
311class 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//-----------------------------------------------------------------------------
372class 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
450template <class Type>
451class 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::Generic
This template class represents a generic bidimensionnal grid.
Definition: kgrid2d.h:97
KGrid2D::Generic::Generic
Generic(uint width=0, uint height=0)
Constructor.
Definition: kgrid2d.h:102
KGrid2D::Generic::inside
bool inside(const Coord &c) const
Definition: kgrid2d.h:188
KGrid2D::Generic::at
Type & at(uint index)
Definition: kgrid2d.h:175
KGrid2D::Generic::fill
void fill(const Type &value)
Fill the nodes with the given value.
Definition: kgrid2d.h:120
KGrid2D::Generic::index
uint index(const Coord &c) const
Definition: kgrid2d.h:140
KGrid2D::Generic::operator[]
const Type & operator[](const Coord &c) const
Definition: kgrid2d.h:162
KGrid2D::Generic::resize
void resize(uint width, uint height)
Resize the grid.
Definition: kgrid2d.h:111
KGrid2D::Generic::coord
Coord coord(uint index) const
Definition: kgrid2d.h:147
KGrid2D::Generic::bound
void bound(Coord &c) const
Bound the given coordinate with the grid dimensions.
Definition: kgrid2d.h:196
KGrid2D::Generic::at
const Type & at(uint index) const
Definition: kgrid2d.h:171
KGrid2D::Generic::at
Type & at(const Coord &c)
Definition: kgrid2d.h:158
KGrid2D::Generic::size
uint size() const
Definition: kgrid2d.h:135
KGrid2D::Generic::at
const Type & at(const Coord &c) const
Definition: kgrid2d.h:154
KGrid2D::Generic::width
uint width() const
Definition: kgrid2d.h:127
KGrid2D::Generic::height
uint height() const
Definition: kgrid2d.h:131
KGrid2D::HexagonalBase
This class contains static methods to manipulate coordinates on an hexagonal grid where hexagons form...
Definition: kgrid2d.h:373
KGrid2D::HexagonalBase::opposed
static Neighbour opposed(Neighbour n)
Definition: kgrid2d.h:400
KGrid2D::HexagonalBase::Neighbour
Neighbour
Identify the six neighbours.
Definition: kgrid2d.h:378
KGrid2D::HexagonalBase::angle
static double angle(Neighbour n)
Definition: kgrid2d.h:384
KGrid2D::HexagonalBase::distance
static uint distance(const Coord &c1, const Coord &c2)
Definition: kgrid2d.h:433
KGrid2D::HexagonalBase::neighbour
static Coord neighbour(const Coord &c, Neighbour n)
Definition: kgrid2d.h:416
KGrid2D::Hexagonal
This template implements a hexagonal grid where hexagons form horizontal lines:
Definition: kgrid2d.h:452
KGrid2D::Hexagonal::neighbours
CoordList neighbours(const Coord &c, uint distance, bool all, bool insideOnly=true) const
Definition: kgrid2d.h:485
KGrid2D::Hexagonal::neighbours
CoordList neighbours(const Coord &c, bool insideOnly=true) const
Definition: kgrid2d.h:466
KGrid2D::Hexagonal::Hexagonal
Hexagonal(uint width=0, uint height=0)
Constructor.
Definition: kgrid2d.h:457
KGrid2D::SquareBase
This class contains static methods to manipulate coordinates for a square bidimensionnal grid.
Definition: kgrid2d.h:235
KGrid2D::SquareBase::isDirect
static bool isDirect(Neighbour n)
Definition: kgrid2d.h:283
KGrid2D::SquareBase::opposed
static Neighbour opposed(Neighbour n)
Definition: kgrid2d.h:264
KGrid2D::SquareBase::Neighbour
Neighbour
Identify the eight neighbours.
Definition: kgrid2d.h:240
KGrid2D::SquareBase::neighbour
static Coord neighbour(const Coord &c, Neighbour n)
Definition: kgrid2d.h:288
KGrid2D::SquareBase::angle
static double angle(Neighbour n)
Definition: kgrid2d.h:246
KGrid2D::Square
This template is a Generic implementation for a square bidimensionnal grid (SquareBase).
Definition: kgrid2d.h:312
KGrid2D::Square::Square
Square(uint width=0, uint height=0)
Constructor.
Definition: kgrid2d.h:317
KGrid2D::Square::neighbours
CoordList neighbours(const Coord &c, bool insideOnly=true, bool directOnly=false) const
Definition: kgrid2d.h:327
KGrid2D::Square::toEdge
Coord toEdge(const Coord &c, Neighbour n) const
Definition: kgrid2d.h:344

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.9.4
This website is maintained by Timothy Pearson.