kgrid2d.h

Go to the documentation of this file.
00001 
00009 /*
00010     This file is part of the KDE games library
00011     Copyright (C) 2001-02 Nicolas Hadacek (hadacek@kde.org)
00012 
00013     This library is free software; you can redistribute it and/or
00014     modify it under the terms of the GNU Library General Public
00015     License version 2 as published by the Free Software Foundation.
00016 
00017     This library is distributed in the hope that it will be useful,
00018     but WITHOUT ANY WARRANTY; without even the implied warranty of
00019     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00020     Library General Public License for more details.
00021 
00022     You should have received a copy of the GNU Library General Public License
00023     along with this library; see the file COPYING.LIB.  If not, write to
00024     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00025     Boston, MA 02110-1301, USA.
00026 */
00027 
00028 #ifndef __KGRID2D_H_
00029 #define __KGRID2D_H_
00030 
00031 #include <math.h>
00032 
00033 #include <qpair.h>
00034 #include <qvaluelist.h>
00035 #include <qvaluevector.h>
00036 
00037 #include <kglobal.h>
00038 
00039 
00040 //-----------------------------------------------------------------------------
00041 namespace KGrid2D
00042 {
00047     typedef QPair<int, int> Coord;
00048 
00053     typedef QValueList<Coord> CoordList;
00054 }
00055 
00056 inline KGrid2D::Coord
00057 operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00058     return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
00059 }
00060 
00061 inline KGrid2D::Coord
00062 operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00063     return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
00064 }
00065 
00070 inline KGrid2D::Coord
00071 maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00072     return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
00073 }
00078 inline KGrid2D::Coord
00079 minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00080     return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
00081 }
00082 
00083 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::Coord &c) {
00084     return s << '(' << c.second << ", " << c.first << ')';
00085 }
00086 
00087 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::CoordList &list)
00088 {
00089     for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
00090         s << *i;
00091         return s;
00092 }
00093 
00094 //-----------------------------------------------------------------------------
00095 namespace KGrid2D
00096 {
00103 template <class Type>
00104 class Generic
00105 {
00106  public:
00110     Generic(uint width = 0, uint height = 0) {
00111         resize(width, height);
00112     }
00113 
00114     virtual ~Generic() {}
00115 
00119     void resize(uint width, uint height) {
00120         _width = width;
00121         _height = height;
00122         _vector.resize(width*height);
00123     }
00124 
00128     void fill(const Type &value) {
00129         for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
00130     }
00131 
00135     uint width() const  { return _width; }
00139     uint height() const { return _height; }
00143     uint size() const   { return _width*_height; }
00144 
00148     uint index(const Coord &c) const {
00149         return c.first + c.second*_width;
00150     }
00151 
00155     Coord coord(uint index) const {
00156         return Coord(index % _width, index / _width);
00157     }
00158 
00162     const Type &at(const Coord &c) const { return _vector[index(c)]; }
00166     Type &at(const Coord &c)             { return _vector[index(c)]; }
00170     const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
00174     Type &operator [](const Coord &c)             { return _vector[index(c)]; }
00175 
00179     const Type &at(uint index) const          { return _vector[index]; }
00183     Type &at(uint index)                      { return _vector[index]; }
00187     const Type &operator [](uint index) const { return _vector[index]; }
00191     Type &operator [](uint index)             { return _vector[index]; }
00192 
00196     bool inside(const Coord &c) const {
00197         return ( c.first>=0 && c.first<(int)_width
00198                  && c.second>=0 && c.second<(int)_height );
00199     }
00200 
00204     void bound(Coord &c) const {
00205         c.first = kMax(kMin(c.first, (int)_width-1), 0);
00206         c.second = kMax(kMin(c.second, (int)_height-1), 0);
00207     }
00208 
00209  protected:
00210     uint               _width, _height;
00211     QValueVector<Type> _vector;
00212 };
00213 }
00214 
00215 template <class Type>
00216 QDataStream &operator <<(QDataStream &s, const KGrid2D::Generic<Type> &m) {
00217     s << (Q_UINT32)m.width() << (Q_UINT32)m.height();
00218     for (uint i=0; i<m.size(); i++) s << m[i];
00219     return s;
00220 }
00221 
00222 template <class Type>
00223 QDataStream &operator >>(QDataStream &s, KGrid2D::Generic<Type> &m) {
00224     Q_UINT32 w, h;
00225     s >> w >> h;
00226     m.resize(w, h);
00227     for (uint i=0; i<m.size(); i++) s >> m[i];
00228     return s;
00229 }
00230 
00231 
00232 namespace KGrid2D
00233 {
00234 
00235 //-----------------------------------------------------------------------------
00242 class SquareBase
00243 {
00244  public:
00248     enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
00249                      RightUp, RightDown, Nb_Neighbour };
00250 
00254     static double angle(Neighbour n) {
00255         switch (n) {
00256         case Left:      return M_PI;
00257         case Right:     return 0;
00258         case Up:        return M_PI_2;
00259         case Down:      return -M_PI_2;
00260         case LeftUp:    return 3.0*M_PI_4;
00261         case LeftDown:  return -3.0*M_PI_4;
00262         case RightUp:   return M_PI_4;
00263         case RightDown: return -M_PI_4;
00264         case Nb_Neighbour: Q_ASSERT(false);
00265         }
00266         return 0;
00267     }
00268 
00272     static Neighbour opposed(Neighbour n) {
00273         switch (n) {
00274         case Left:      return Right;
00275         case Right:     return Left;
00276         case Up:        return Down;
00277         case Down:      return Up;
00278         case LeftUp:    return RightDown;
00279         case LeftDown:  return RightUp;
00280         case RightUp:   return LeftDown;
00281         case RightDown: return LeftUp;
00282         case Nb_Neighbour: Q_ASSERT(false);
00283         }
00284         return Nb_Neighbour;
00285     }
00286 
00291     static bool isDirect(Neighbour n) { return n<LeftUp; }
00292 
00296     static Coord neighbour(const Coord &c, Neighbour n) {
00297         switch (n) {
00298         case Left:      return c + Coord(-1,  0);
00299         case Right:     return c + Coord( 1,  0);
00300         case Up:        return c + Coord( 0, -1);
00301         case Down:      return c + Coord( 0,  1);
00302         case LeftUp:    return c + Coord(-1, -1);
00303         case LeftDown:  return c + Coord(-1,  1);
00304         case RightUp:   return c + Coord( 1, -1);
00305         case RightDown: return c + Coord( 1,  1);
00306         case Nb_Neighbour: Q_ASSERT(false);
00307         }
00308         return c;
00309     }
00310 };
00311 
00318 template <class T>
00319 class Square : public Generic<T>, public SquareBase
00320 {
00321  public:
00325     Square(uint width = 0, uint height = 0)
00326         : Generic<T>(width, height) {}
00327 
00335     CoordList neighbours(const Coord &c, bool insideOnly = true,
00336                          bool directOnly = false) const {
00337         CoordList neighbours;
00338         for (uint i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
00339             Coord n = neighbour(c, (Neighbour)i);
00340             if ( insideOnly && !Generic<T>::inside(n) ) continue;
00341             neighbours.append(n);
00342         }
00343         return neighbours;
00344     }
00345 
00352     Coord toEdge(const Coord &c, Neighbour n) const {
00353         switch (n) {
00354         case Left:      return Coord(0, c.second);
00355         case Right:     return Coord(Generic<T>::width()-1, c.second);
00356         case Up:        return Coord(c.first, 0);
00357         case Down:      return Coord(c.first, Generic<T>::height()-1);
00358         case LeftUp:    return Coord(0, 0);
00359         case LeftDown:  return Coord(0, Generic<T>::height()-1);
00360         case RightUp:   return Coord(Generic<T>::width()-1, 0);
00361         case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
00362         case Nb_Neighbour: Q_ASSERT(false);
00363         }
00364         return c;
00365     }
00366 };
00367 
00368 //-----------------------------------------------------------------------------
00380 class HexagonalBase
00381 {
00382  public:
00386     enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
00387                      RightUp, RightDown, Nb_Neighbour };
00388 
00392     static double angle(Neighbour n) {
00393         switch (n) {
00394         case Left:      return M_PI;
00395         case Right:     return 0;
00396         case LeftUp:    return 2.0*M_PI/3;
00397         case LeftDown:  return -2.0*M_PI/3;
00398         case RightUp:   return M_PI/3;
00399         case RightDown: return -M_PI/3;
00400         case Nb_Neighbour: Q_ASSERT(false);
00401         }
00402         return 0;
00403     }
00404 
00408     static Neighbour opposed(Neighbour n) {
00409         switch (n) {
00410         case Left:      return Right;
00411         case Right:     return Left;
00412         case LeftUp:    return RightDown;
00413         case LeftDown:  return RightUp;
00414         case RightUp:   return LeftDown;
00415         case RightDown: return LeftUp;
00416         case Nb_Neighbour: Q_ASSERT(false);
00417         }
00418         return Nb_Neighbour;
00419     }
00420 
00424     static Coord neighbour(const Coord &c, Neighbour n) {
00425         bool oddRow = c.second%2;
00426         switch (n) {
00427         case Left:      return c + Coord(-1,  0);
00428         case Right:     return c + Coord( 1,  0);
00429         case LeftUp:    return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
00430         case LeftDown:  return c + (oddRow ? Coord( 0,  1) : Coord(-1,  1));
00431         case RightUp:   return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
00432         case RightDown: return c + (oddRow ? Coord( 1,  1) : Coord( 0,  1));
00433         case Nb_Neighbour: Q_ASSERT(false);
00434         }
00435         return c;
00436     }
00437 
00441     static uint distance(const Coord &c1, const Coord &c2) {
00442         return kAbs(c1.first - c2.first) + kAbs(c1.second - c2.second)
00443             + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
00444     }
00445 };
00446 
00458 template <class Type>
00459 class Hexagonal : public Generic<Type>, public HexagonalBase
00460 {
00461  public:
00465     Hexagonal(uint width = 0, uint height = 0)
00466         : Generic<Type>(width, height) {}
00467 
00474     CoordList neighbours(const Coord &c, bool insideOnly = true) const {
00475         CoordList neighbours;
00476         for (uint i=0; i<Nb_Neighbour; i++) {
00477             Coord n = neighbour(c, (Neighbour)i);
00478             if ( insideOnly && !Generic<Type>::inside(n) ) continue;
00479             neighbours.append(n);
00480         }
00481         return neighbours;
00482     }
00483 
00484 
00493     CoordList neighbours(const Coord &c, uint distance, bool all,
00494                         bool insideOnly = true) const {
00495         // brute force algorithm -- you're welcome to make it more efficient :)
00496         CoordList ring;
00497         if ( distance==0 ) return ring;
00498         ring = neighbours(c, insideOnly);
00499         if ( distance==1 ) return ring;
00500         CoordList center;
00501         center.append(c);
00502         for (uint i=1; i<distance; i++) {
00503             CoordList newRing;
00504             CoordList::const_iterator it;
00505             for (it=ring.begin(); it!=ring.end(); ++it) {
00506                 CoordList n = neighbours(*it, insideOnly);
00507                 CoordList::const_iterator it2;
00508                 for (it2=n.begin(); it2!=n.end(); ++it2)
00509                     if ( center.find(*it2)==center.end()
00510                          && ring.find(*it2)==ring.end()
00511                          && newRing.find(*it2)==newRing.end() )
00512                         newRing.append(*it2);
00513                 center.append(*it);
00514             }
00515             ring = newRing;
00516         }
00517         if ( !all ) return ring;
00518         CoordList::const_iterator it;
00519         for (it=ring.begin(); it!=ring.end(); ++it)
00520             center.append(*it);
00521         center.remove(c);
00522         return center;
00523     }
00524 };
00525 
00526 } // namespace
00527 
00528 #endif

Generated on Wed Aug 23 18:04:18 2006 for libkdegames by  doxygen 1.4.6