summaryrefslogtreecommitdiffstats
path: root/libtdegames/kgrid2d.h
diff options
context:
space:
mode:
authorTimothy Pearson <kb9vqf@pearsoncomputing.net>2011-11-06 15:56:37 -0600
committerTimothy Pearson <kb9vqf@pearsoncomputing.net>2011-11-06 15:56:37 -0600
commit14c49c4f56792a934bcdc4efceebbd429d858571 (patch)
tree2f302410d5a5d678bf3ff10edead70d348be6644 /libtdegames/kgrid2d.h
parentab0981b9689e4d3ad88e9572bfa4b4a5e36c51ae (diff)
downloadtdegames-14c49c4f56792a934bcdc4efceebbd429d858571.tar.gz
tdegames-14c49c4f56792a934bcdc4efceebbd429d858571.zip
Actually move the kde files that were renamed in the last commit
Diffstat (limited to 'libtdegames/kgrid2d.h')
-rw-r--r--libtdegames/kgrid2d.h520
1 files changed, 520 insertions, 0 deletions
diff --git a/libtdegames/kgrid2d.h b/libtdegames/kgrid2d.h
new file mode 100644
index 00000000..9443b0c7
--- /dev/null
+++ b/libtdegames/kgrid2d.h
@@ -0,0 +1,520 @@
+/*
+ This file is part of the KDE games library
+ Copyright (C) 2001-02 Nicolas Hadacek (hadacek@kde.org)
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public
+ License version 2 as published by the Free Software Foundation.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public License
+ along with this library; see the file COPYING.LIB. If not, write to
+ the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
+*/
+
+#ifndef __KGRID2D_H_
+#define __KGRID2D_H_
+
+#include <math.h>
+
+#include <tqpair.h>
+#include <tqvaluelist.h>
+#include <tqvaluevector.h>
+
+#include <kglobal.h>
+
+
+//-----------------------------------------------------------------------------
+namespace KGrid2D
+{
+ /**
+ * This type represents coordinates on a bidimensionnal grid.
+ * @since 3.2
+ */
+ typedef TQPair<int, int> Coord;
+
+ /**
+ * This type represents a list of @ref Coord.
+ * @since 3.2
+ */
+ typedef TQValueList<Coord> CoordList;
+}
+
+inline KGrid2D::Coord
+operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+ return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
+}
+
+inline KGrid2D::Coord
+operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+ return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
+}
+
+/**
+ * @return the maximum of both coordinates.
+ * @since 3.2
+ */
+inline KGrid2D::Coord
+maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+ return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
+}
+/**
+ * @return the minimum of both coordinates.
+ * @since 3.2
+ */
+inline KGrid2D::Coord
+minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
+ return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
+}
+
+inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::Coord &c) {
+ return s << '(' << c.second << ", " << c.first << ')';
+}
+
+inline TQTextStream &operator <<(TQTextStream &s, const KGrid2D::CoordList &list)
+{
+ for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
+ s << *i;
+ return s;
+}
+
+//-----------------------------------------------------------------------------
+namespace KGrid2D
+{
+/**
+ * This template class represents a generic bidimensionnal grid. Each node
+ * contains an element of the template type.
+ *
+ * @since 3.2
+ */
+template <class Type>
+class Generic
+{
+ public:
+ /**
+ * Constructor.
+ */
+ Generic(uint width = 0, uint height = 0) {
+ resize(width, height);
+ }
+
+ virtual ~Generic() {}
+
+ /**
+ * Resize the grid.
+ */
+ void resize(uint width, uint height) {
+ _width = width;
+ _height = height;
+ _vector.resize(width*height);
+ }
+
+ /**
+ * Fill the nodes with the given value.
+ */
+ void fill(const Type &value) {
+ for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
+ }
+
+ /**
+ * @return the width.
+ */
+ uint width() const { return _width; }
+ /**
+ * @return the height.
+ */
+ uint height() const { return _height; }
+ /**
+ * @return the number of nodes (ie width*height).
+ */
+ uint size() const { return _width*_height; }
+
+ /**
+ * @return the linear index for the given coordinate.
+ */
+ uint index(const Coord &c) const {
+ return c.first + c.second*_width;
+ }
+
+ /**
+ * @return the coordinate corresponding to the linear index.
+ */
+ Coord coord(uint index) const {
+ return Coord(index % _width, index / _width);
+ }
+
+ /**
+ * @return the value at the given coordinate.
+ */
+ const Type &at(const Coord &c) const { return _vector[index(c)]; }
+ /**
+ * @return the value at the given coordinate.
+ */
+ Type &at(const Coord &c) { return _vector[index(c)]; }
+ /**
+ * @return the value at the given coordinate.
+ */
+ const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
+ /**
+ * @return the value at the given coordinate.
+ */
+ Type &operator [](const Coord &c) { return _vector[index(c)]; }
+
+ /**
+ * @return the value at the given linear index.
+ */
+ const Type &at(uint index) const { return _vector[index]; }
+ /**
+ * @return the value at the given linear index.
+ */
+ Type &at(uint index) { return _vector[index]; }
+ /**
+ * @return the value at the given linear index.
+ */
+ const Type &operator [](uint index) const { return _vector[index]; }
+ /**
+ * @return the value at the given linear index.
+ */
+ Type &operator [](uint index) { return _vector[index]; }
+
+ /**
+ * @return if the given coordinate is inside the grid.
+ */
+ bool inside(const Coord &c) const {
+ return ( c.first>=0 && c.first<(int)_width
+ && c.second>=0 && c.second<(int)_height );
+ }
+
+ /**
+ * Bound the given coordinate with the grid dimensions.
+ */
+ void bound(Coord &c) const {
+ c.first = kMax(kMin(c.first, (int)_width-1), 0);
+ c.second = kMax(kMin(c.second, (int)_height-1), 0);
+ }
+
+ protected:
+ uint _width, _height;
+ TQValueVector<Type> _vector;
+};
+}
+
+template <class Type>
+TQDataStream &operator <<(TQDataStream &s, const KGrid2D::Generic<Type> &m) {
+ s << (TQ_UINT32)m.width() << (TQ_UINT32)m.height();
+ for (uint i=0; i<m.size(); i++) s << m[i];
+ return s;
+}
+
+template <class Type>
+TQDataStream &operator >>(TQDataStream &s, KGrid2D::Generic<Type> &m) {
+ TQ_UINT32 w, h;
+ s >> w >> h;
+ m.resize(w, h);
+ for (uint i=0; i<m.size(); i++) s >> m[i];
+ return s;
+}
+
+
+namespace KGrid2D
+{
+
+//-----------------------------------------------------------------------------
+/**
+ * This class contains static methods to manipulate coordinates for a
+ * square bidimensionnal grid.
+ *
+ * @since 3.2
+ */
+class SquareBase
+{
+ public:
+ /**
+ * Identify the eight neighbours.
+ */
+ enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
+ RightUp, RightDown, Nb_Neighbour };
+
+ /**
+ * @return the trigonometric angle in radians for the given neighbour.
+ */
+ static double angle(Neighbour n) {
+ switch (n) {
+ case Left: return M_PI;
+ case Right: return 0;
+ case Up: return M_PI_2;
+ case Down: return -M_PI_2;
+ case LeftUp: return 3.0*M_PI_4;
+ case LeftDown: return -3.0*M_PI_4;
+ case RightUp: return M_PI_4;
+ case RightDown: return -M_PI_4;
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return 0;
+ }
+
+ /**
+ * @return the opposed neighbour.
+ */
+ static Neighbour opposed(Neighbour n) {
+ switch (n) {
+ case Left: return Right;
+ case Right: return Left;
+ case Up: return Down;
+ case Down: return Up;
+ case LeftUp: return RightDown;
+ case LeftDown: return RightUp;
+ case RightUp: return LeftDown;
+ case RightDown: return LeftUp;
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return Nb_Neighbour;
+ }
+
+ /**
+ * @return true if the neighbour is a direct one (ie is one of the four
+ * nearest).
+ */
+ static bool isDirect(Neighbour n) { return n<LeftUp; }
+
+ /**
+ * @return the neighbour for the given coordinate.
+ */
+ static Coord neighbour(const Coord &c, Neighbour n) {
+ switch (n) {
+ case Left: return c + Coord(-1, 0);
+ case Right: return c + Coord( 1, 0);
+ case Up: return c + Coord( 0, -1);
+ case Down: return c + Coord( 0, 1);
+ case LeftUp: return c + Coord(-1, -1);
+ case LeftDown: return c + Coord(-1, 1);
+ case RightUp: return c + Coord( 1, -1);
+ case RightDown: return c + Coord( 1, 1);
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return c;
+ }
+};
+
+/**
+ * This template is a @ref Generic implementation for a square bidimensionnal
+ * grid (@ref SquareBase).
+ *
+ * @since 3.2
+ */
+template <class T>
+class Square : public Generic<T>, public SquareBase
+{
+ public:
+ /**
+ * Constructor.
+ */
+ Square(uint width = 0, uint height = 0)
+ : Generic<T>(width, height) {}
+
+ /**
+ * @return the neighbours of coordinate @param c
+ * to the given set of coordinates
+ * @param c the coordinate to use as the reference point
+ * @param insideOnly only add coordinates that are inside the grid.
+ * @param directOnly only add the four nearest neighbours.
+ */
+ CoordList neighbours(const Coord &c, bool insideOnly = true,
+ bool directOnly = false) const {
+ CoordList neighbours;
+ for (uint i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
+ Coord n = neighbour(c, (Neighbour)i);
+ if ( insideOnly && !Generic<T>::inside(n) ) continue;
+ neighbours.append(n);
+ }
+ return neighbours;
+ }
+
+ /**
+ * @return the "projection" of the given coordinate on the grid edges.
+ *
+ * @param c the coordinate to use as the reference point
+ * @param n the direction of projection.
+ */
+ Coord toEdge(const Coord &c, Neighbour n) const {
+ switch (n) {
+ case Left: return Coord(0, c.second);
+ case Right: return Coord(Generic<T>::width()-1, c.second);
+ case Up: return Coord(c.first, 0);
+ case Down: return Coord(c.first, Generic<T>::height()-1);
+ case LeftUp: return Coord(0, 0);
+ case LeftDown: return Coord(0, Generic<T>::height()-1);
+ case RightUp: return Coord(Generic<T>::width()-1, 0);
+ case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return c;
+ }
+};
+
+//-----------------------------------------------------------------------------
+/**
+ * This class contains static methods to manipulate coordinates on an
+ * hexagonal grid where hexagons form horizontal lines:
+ * <pre>
+ * (0,0) (0,1) (0,2)
+ * (1,0) (1,1) (1,2)
+ * (2,0) (2,1) (2,2)
+ * </pre>
+ *
+ * @since 3.2
+ */
+class HexagonalBase
+{
+ public:
+ /**
+ * Identify the six neighbours.
+ */
+ enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
+ RightUp, RightDown, Nb_Neighbour };
+
+ /**
+ * @return the trigonometric angle in radians for the given neighbour.
+ */
+ static double angle(Neighbour n) {
+ switch (n) {
+ case Left: return M_PI;
+ case Right: return 0;
+ case LeftUp: return 2.0*M_PI/3;
+ case LeftDown: return -2.0*M_PI/3;
+ case RightUp: return M_PI/3;
+ case RightDown: return -M_PI/3;
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return 0;
+ }
+
+ /**
+ * @return the opposed neighbour.
+ */
+ static Neighbour opposed(Neighbour n) {
+ switch (n) {
+ case Left: return Right;
+ case Right: return Left;
+ case LeftUp: return RightDown;
+ case LeftDown: return RightUp;
+ case RightUp: return LeftDown;
+ case RightDown: return LeftUp;
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return Nb_Neighbour;
+ }
+
+ /**
+ * @return the neighbour of the given coordinate.
+ */
+ static Coord neighbour(const Coord &c, Neighbour n) {
+ bool oddRow = c.second%2;
+ switch (n) {
+ case Left: return c + Coord(-1, 0);
+ case Right: return c + Coord( 1, 0);
+ case LeftUp: return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
+ case LeftDown: return c + (oddRow ? Coord( 0, 1) : Coord(-1, 1));
+ case RightUp: return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
+ case RightDown: return c + (oddRow ? Coord( 1, 1) : Coord( 0, 1));
+ case Nb_Neighbour: Q_ASSERT(false);
+ }
+ return c;
+ }
+
+ /**
+ * @return the distance between the two coordinates in term of hexagons.
+ */
+ static uint distance(const Coord &c1, const Coord &c2) {
+ return kAbs(c1.first - c2.first) + kAbs(c1.second - c2.second)
+ + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
+ }
+};
+
+/**
+ * This template implements a hexagonal grid
+ * where hexagons form horizontal lines:
+ * <pre>
+ * (0,0) (0,1) (0,2)
+ * (1,0) (1,1) (1,2)
+ * (2,0) (2,1) (2,2)
+ * </pre>
+ *
+ * @ since 3.2
+ */
+template <class Type>
+class Hexagonal : public Generic<Type>, public HexagonalBase
+{
+ public:
+ /**
+ * Constructor.
+ */
+ Hexagonal(uint width = 0, uint height = 0)
+ : Generic<Type>(width, height) {}
+
+ /**
+ * @return the neighbours of coordinate @param c
+ * to the given set of coordinates
+ * @param c the coordiante to use as the reference point
+ * @param insideOnly only add coordinates that are inside the grid.
+ */
+ CoordList neighbours(const Coord &c, bool insideOnly = true) const {
+ CoordList neighbours;
+ for (uint i=0; i<Nb_Neighbour; i++) {
+ Coord n = neighbour(c, (Neighbour)i);
+ if ( insideOnly && !Generic<Type>::inside(n) ) continue;
+ neighbours.append(n);
+ }
+ return neighbours;
+ }
+
+
+ /**
+ * @return the neighbours at distance @param distance of coordinate
+ * @param c the coordinate to use as the reference point
+ * @param distance distance to the neighbour (1 means at contact).
+ * @param insideOnly only add coordinates that are inside the grid.
+ * @param all returns all neighbours at distance equal and less than
+ * @param distance (the original coordinate is not included).
+ */
+ CoordList neighbours(const Coord &c, uint distance, bool all,
+ bool insideOnly = true) const {
+ // brute force algorithm -- you're welcome to make it more efficient :)
+ CoordList ring;
+ if ( distance==0 ) return ring;
+ ring = neighbours(c, insideOnly);
+ if ( distance==1 ) return ring;
+ CoordList center;
+ center.append(c);
+ for (uint i=1; i<distance; i++) {
+ CoordList newRing;
+ CoordList::const_iterator it;
+ for (it=ring.begin(); it!=ring.end(); ++it) {
+ CoordList n = neighbours(*it, insideOnly);
+ CoordList::const_iterator it2;
+ for (it2=n.begin(); it2!=n.end(); ++it2)
+ if ( center.find(*it2)==center.end()
+ && ring.find(*it2)==ring.end()
+ && newRing.find(*it2)==newRing.end() )
+ newRing.append(*it2);
+ center.append(*it);
+ }
+ ring = newRing;
+ }
+ if ( !all ) return ring;
+ CoordList::const_iterator it;
+ for (it=ring.begin(); it!=ring.end(); ++it)
+ center.append(*it);
+ center.remove(c);
+ return center;
+ }
+};
+
+} // namespace
+
+#endif