kgrid2d.h

00001 /*
00002     This file is part of the KDE games library
00003     Copyright (C) 2001-02 Nicolas Hadacek (hadacek@kde.org)
00004 
00005     This library is free software; you can redistribute it and/or
00006     modify it under the terms of the GNU Library General Public
00007     License version 2 as published by the Free Software Foundation.
00008 
00009     This library is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012     Library General Public License for more details.
00013 
00014     You should have received a copy of the GNU Library General Public License
00015     along with this library; see the file COPYING.LIB.  If not, write to
00016     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00017     Boston, MA 02110-1301, USA.
00018 */
00019 
00020 #ifndef __KGRID2D_H_
00021 #define __KGRID2D_H_
00022 
00023 #include <math.h>
00024 
00025 #include <qpair.h>
00026 #include <qvaluelist.h>
00027 #include <qvaluevector.h>
00028 
00029 #include <kglobal.h>
00030 
00031 
00032 //-----------------------------------------------------------------------------
00033 namespace KGrid2D
00034 {
00039     typedef QPair<int, int> Coord;
00040 
00045     typedef QValueList<Coord> CoordList;
00046 }
00047 
00048 inline KGrid2D::Coord
00049 operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00050     return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
00051 }
00052 
00053 inline KGrid2D::Coord
00054 operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00055     return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
00056 }
00057 
00062 inline KGrid2D::Coord
00063 maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00064     return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
00065 }
00070 inline KGrid2D::Coord
00071 minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
00072     return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
00073 }
00074 
00075 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::Coord &c) {
00076     return s << '(' << c.second << ", " << c.first << ')';
00077 }
00078 
00079 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::CoordList &list)
00080 {
00081     for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
00082         s << *i;
00083     return s;
00084 }
00085 
00086 //-----------------------------------------------------------------------------
00087 namespace KGrid2D
00088 {
00095 template <class Type>
00096 class Generic
00097 {
00098  public:
00102     Generic(uint width = 0, uint height = 0) {
00103         resize(width, height);
00104     }
00105 
00106     virtual ~Generic() {}
00107 
00111     void resize(uint width, uint height) {
00112         _width = width;
00113         _height = height;
00114         _vector.resize(width*height);
00115     }
00116 
00120     void fill(const Type &value) {
00121         for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
00122     }
00123 
00127     uint width() const  { return _width; }
00131     uint height() const { return _height; }
00135     uint size() const   { return _width*_height; }
00136 
00140     uint index(const Coord &c) const {
00141         return c.first + c.second*_width;
00142     }
00143 
00147     Coord coord(uint index) const {
00148         return Coord(index % _width, index / _width);
00149     }
00150 
00154     const Type &at(const Coord &c) const { return _vector[index(c)]; }
00158     Type &at(const Coord &c)             { return _vector[index(c)]; }
00162     const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
00166     Type &operator [](const Coord &c)             { return _vector[index(c)]; }
00167 
00171     const Type &at(uint index) const          { return _vector[index]; }
00175     Type &at(uint index)                      { return _vector[index]; }
00179     const Type &operator [](uint index) const { return _vector[index]; }
00183     Type &operator [](uint index)             { return _vector[index]; }
00184 
00188     bool inside(const Coord &c) const {
00189         return ( c.first>=0 && c.first<(int)_width
00190                  && c.second>=0 && c.second<(int)_height );
00191     }
00192 
00196     void bound(Coord &c) const {
00197         c.first = kMax(kMin(c.first, (int)_width-1), 0);
00198         c.second = kMax(kMin(c.second, (int)_height-1), 0);
00199     }
00200 
00201  protected:
00202     uint               _width, _height;
00203     QValueVector<Type> _vector;
00204 };
00205 }
00206 
00207 template <class Type>
00208 QDataStream &operator <<(QDataStream &s, const KGrid2D::Generic<Type> &m) {
00209     s << (Q_UINT32)m.width() << (Q_UINT32)m.height();
00210     for (uint i=0; i<m.size(); i++) s << m[i];
00211     return s;
00212 }
00213 
00214 template <class Type>
00215 QDataStream &operator >>(QDataStream &s, KGrid2D::Generic<Type> &m) {
00216     Q_UINT32 w, h;
00217     s >> w >> h;
00218     m.resize(w, h);
00219     for (uint i=0; i<m.size(); i++) s >> m[i];
00220     return s;
00221 }
00222 
00223 
00224 namespace KGrid2D
00225 {
00226 
00227 //-----------------------------------------------------------------------------
00234 class SquareBase
00235 {
00236  public:
00240     enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
00241                      RightUp, RightDown, Nb_Neighbour };
00242 
00246     static double angle(Neighbour n) {
00247         switch (n) {
00248         case Left:      return M_PI;
00249         case Right:     return 0;
00250         case Up:        return M_PI_2;
00251         case Down:      return -M_PI_2;
00252         case LeftUp:    return 3.0*M_PI_4;
00253         case LeftDown:  return -3.0*M_PI_4;
00254         case RightUp:   return M_PI_4;
00255         case RightDown: return -M_PI_4;
00256         case Nb_Neighbour: Q_ASSERT(false);
00257         }
00258         return 0;
00259     }
00260 
00264     static Neighbour opposed(Neighbour n) {
00265         switch (n) {
00266         case Left:      return Right;
00267         case Right:     return Left;
00268         case Up:        return Down;
00269         case Down:      return Up;
00270         case LeftUp:    return RightDown;
00271         case LeftDown:  return RightUp;
00272         case RightUp:   return LeftDown;
00273         case RightDown: return LeftUp;
00274         case Nb_Neighbour: Q_ASSERT(false);
00275         }
00276         return Nb_Neighbour;
00277     }
00278 
00283     static bool isDirect(Neighbour n) { return n<LeftUp; }
00284 
00288     static Coord neighbour(const Coord &c, Neighbour n) {
00289         switch (n) {
00290         case Left:      return c + Coord(-1,  0);
00291         case Right:     return c + Coord( 1,  0);
00292         case Up:        return c + Coord( 0, -1);
00293         case Down:      return c + Coord( 0,  1);
00294         case LeftUp:    return c + Coord(-1, -1);
00295         case LeftDown:  return c + Coord(-1,  1);
00296         case RightUp:   return c + Coord( 1, -1);
00297         case RightDown: return c + Coord( 1,  1);
00298         case Nb_Neighbour: Q_ASSERT(false);
00299         }
00300         return c;
00301     }
00302 };
00303 
00310 template <class T>
00311 class Square : public Generic<T>, public SquareBase
00312 {
00313  public:
00317     Square(uint width = 0, uint height = 0)
00318         : Generic<T>(width, height) {}
00319 
00327     CoordList neighbours(const Coord &c, bool insideOnly = true,
00328                          bool directOnly = false) const {
00329         CoordList neighbours;
00330         for (uint i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
00331             Coord n = neighbour(c, (Neighbour)i);
00332             if ( insideOnly && !Generic<T>::inside(n) ) continue;
00333             neighbours.append(n);
00334         }
00335         return neighbours;
00336     }
00337 
00344     Coord toEdge(const Coord &c, Neighbour n) const {
00345         switch (n) {
00346         case Left:      return Coord(0, c.second);
00347         case Right:     return Coord(Generic<T>::width()-1, c.second);
00348         case Up:        return Coord(c.first, 0);
00349         case Down:      return Coord(c.first, Generic<T>::height()-1);
00350         case LeftUp:    return Coord(0, 0);
00351         case LeftDown:  return Coord(0, Generic<T>::height()-1);
00352         case RightUp:   return Coord(Generic<T>::width()-1, 0);
00353         case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
00354         case Nb_Neighbour: Q_ASSERT(false);
00355         }
00356         return c;
00357     }
00358 };
00359 
00360 //-----------------------------------------------------------------------------
00372 class HexagonalBase
00373 {
00374  public:
00378     enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
00379                      RightUp, RightDown, Nb_Neighbour };
00380 
00384     static double angle(Neighbour n) {
00385         switch (n) {
00386         case Left:      return M_PI;
00387         case Right:     return 0;
00388         case LeftUp:    return 2.0*M_PI/3;
00389         case LeftDown:  return -2.0*M_PI/3;
00390         case RightUp:   return M_PI/3;
00391         case RightDown: return -M_PI/3;
00392         case Nb_Neighbour: Q_ASSERT(false);
00393         }
00394         return 0;
00395     }
00396 
00400     static Neighbour opposed(Neighbour n) {
00401         switch (n) {
00402         case Left:      return Right;
00403         case Right:     return Left;
00404         case LeftUp:    return RightDown;
00405         case LeftDown:  return RightUp;
00406         case RightUp:   return LeftDown;
00407         case RightDown: return LeftUp;
00408         case Nb_Neighbour: Q_ASSERT(false);
00409         }
00410         return Nb_Neighbour;
00411     }
00412 
00416     static Coord neighbour(const Coord &c, Neighbour n) {
00417         bool oddRow = c.second%2;
00418         switch (n) {
00419         case Left:      return c + Coord(-1,  0);
00420         case Right:     return c + Coord( 1,  0);
00421         case LeftUp:    return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
00422         case LeftDown:  return c + (oddRow ? Coord( 0,  1) : Coord(-1,  1));
00423         case RightUp:   return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
00424         case RightDown: return c + (oddRow ? Coord( 1,  1) : Coord( 0,  1));
00425         case Nb_Neighbour: Q_ASSERT(false);
00426         }
00427         return c;
00428     }
00429 
00433     static uint distance(const Coord &c1, const Coord &c2) {
00434         return kAbs(c1.first - c2.first) + kAbs(c1.second - c2.second)
00435             + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
00436     }
00437 };
00438 
00450 template <class Type>
00451 class Hexagonal : public Generic<Type>, public HexagonalBase
00452 {
00453  public:
00457     Hexagonal(uint width = 0, uint height = 0)
00458         : Generic<Type>(width, height) {}
00459 
00466     CoordList neighbours(const Coord &c, bool insideOnly = true) const {
00467         CoordList neighbours;
00468         for (uint i=0; i<Nb_Neighbour; i++) {
00469             Coord n = neighbour(c, (Neighbour)i);
00470             if ( insideOnly && !Generic<Type>::inside(n) ) continue;
00471             neighbours.append(n);
00472         }
00473         return neighbours;
00474     }
00475 
00476 
00485     CoordList neighbours(const Coord &c, uint distance, bool all,
00486                         bool insideOnly = true) const {
00487         // brute force algorithm -- you're welcome to make it more efficient :)
00488         CoordList ring;
00489         if ( distance==0 ) return ring;
00490         ring = neighbours(c, insideOnly);
00491         if ( distance==1 ) return ring;
00492         CoordList center;
00493         center.append(c);
00494         for (uint i=1; i<distance; i++) {
00495             CoordList newRing;
00496             CoordList::const_iterator it;
00497             for (it=ring.begin(); it!=ring.end(); ++it) {
00498                 CoordList n = neighbours(*it, insideOnly);
00499                 CoordList::const_iterator it2;
00500                 for (it2=n.begin(); it2!=n.end(); ++it2)
00501                     if ( center.find(*it2)==center.end()
00502                          && ring.find(*it2)==ring.end()
00503                          && newRing.find(*it2)==newRing.end() )
00504                         newRing.append(*it2);
00505                 center.append(*it);
00506             }
00507             ring = newRing;
00508         }
00509         if ( !all ) return ring;
00510         CoordList::const_iterator it;
00511         for (it=ring.begin(); it!=ring.end(); ++it)
00512             center.append(*it);
00513         center.remove(c);
00514         return center;
00515     }
00516 };
00517 
00518 } // namespace
00519 
00520 #endif
KDE Home | KDE Accessibility Home | Description of Access Keys