libkdegames/kgrid2d.h

   1 /*
   2     This file is part of the KDE 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 <QtCore/QPair>
  26 #include <QtCore/QVector>
  27 //Added by qt3to4:
  28 #include <QtCore/QTextStream>
  29
  30 #include <kglobal.h>
  31
  32
  33 //-----------------------------------------------------------------------------
  34 namespace KGrid2D
  35 {
  36     /**
  37      * This type represents coordinates on a bidimensionnal grid.
  38      */
  39     typedef QPair<int, int> Coord;
  40
  41     /**
  42      * This type represents a list of @ref Coord.
  43      */
  44     typedef QList<Coord> CoordList;
  45 }
  46
  47 inline KGrid2D::Coord
  48 operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  49     return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
  50 }
  51
  52 inline KGrid2D::Coord
  53 operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  54     return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
  55 }
  56
  57 /**
  58  * @return the maximum of both coordinates.
  59  */
  60 inline KGrid2D::Coord
  61 maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  62     return KGrid2D::Coord(qMax(c1.first, c2.first), qMax(c1.second, c2.second));
  63 }
  64 /**
  65  * @return the minimum of both coordinates.
  66  */
  67 inline KGrid2D::Coord
  68 minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  69     return KGrid2D::Coord(qMin(c1.first, c2.first), qMin(c1.second, c2.second));
  70 }
  71
  72 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::Coord &c) {
  73     return s << '(' << c.second << "," << c.first << ')';
  74 }
  75
  76 inline QTextStream &operator <<(QTextStream &s, const KGrid2D::CoordList &list)
  77 {
  78     for(KGrid2D::CoordList::const_iterator i=list.begin(); i!=list.end(); ++i)
  79         s << *i;
  80         return s;
  81 }
  82
  83 //-----------------------------------------------------------------------------
  84 namespace KGrid2D
  85 {
  86 /**
  87  * \class Generic kgrid2d.h <KGrid2D>
  88  *
  89  * This template class represents a generic bidimensionnal grid. Each node
  90  * contains an element of the template type.
  91  */
  92 template <class Type>
  93 class Generic
  94 {
  95  public:
  96     /**
  97      * Constructor.
  98      */
  99     Generic(uint width = 0, uint height = 0) {
 100         resize(width, height);
 101     }
 102
 103     virtual ~Generic() {}
 104
 105     /**
 106      * Resize the grid.
 107      */
 108     void resize(uint width, uint height) {
 109         _width = width;
 110         _height = height;
 111         _vector.resize(width*height);
 112     }
 113
 114     /**
 115      * Fill the nodes with the given value.
 116      */
 117     void fill(const Type &value) {
 118         for (int i=0; i<_vector.count(); i++) _vector[i] = value;
 119     }
 120
 121     /**
 122      * @return the width.
 123      */
 124     uint width() const  { return _width; }
 125     /**
 126      * @return the height.
 127      */
 128     uint height() const { return _height; }
 129     /**
 130      * @return the number of nodes (ie width*height).
 131      */
 132     uint size() const   { return _width*_height; }
 133
 134     /**
 135      * @return the linear index for the given coordinate.
 136      */
 137     uint index(const Coord &c) const {
 138         return c.first + c.second*_width;
 139     }
 140
 141     /**
 142      * @return the coordinate corresponding to the linear index.
 143      */
 144     Coord coord(uint index) const {
 145         return Coord(index % _width, index / _width);
 146     }
 147
 148     /**
 149      * @return the value at the given coordinate.
 150      */
 151     const Type &at(const Coord &c) const { return _vector[index(c)]; }
 152     /**
 153      * @return the value at the given coordinate.
 154      */
 155     Type &at(const Coord &c)             { return _vector[index(c)]; }
 156     /**
 157      * @return the value at the given coordinate.
 158      */
 159     const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
 160     /**
 161      * @return the value at the given coordinate.
 162      */
 163     Type &operator [](const Coord &c)             { return _vector[index(c)]; }
 164
 165     /**
 166      * @return the value at the given linear index.
 167      */
 168     const Type &at(uint index) const          { return _vector[index]; }
 169     /**
 170      * @return the value at the given linear index.
 171      */
 172     Type &at(uint index)                      { return _vector[index]; }
 173     /**
 174      * @return the value at the given linear index.
 175      */
 176     const Type &operator [](uint index) const { return _vector[index]; }
 177     /**
 178      * @return the value at the given linear index.
 179      */
 180     Type &operator [](uint index)             { return _vector[index]; }
 181
 182     /**
 183      * @return if the given coordinate is inside the grid.
 184      */
 185     bool inside(const Coord &c) const {
 186         return ( c.first>=0 && c.first<(int)_width
 187                  && c.second>=0 && c.second<(int)_height );
 188     }
 189
 190     /**
 191      * Bound the given coordinate with the grid dimensions.
 192      */
 193     void bound(Coord &c) const {
 194         c.first = qMax(qMin(c.first, (int)_width-1), 0);
 195         c.second = qMax(qMin(c.second, (int)_height-1), 0);
 196     }
 197
 198  protected:
 199     uint               _width, _height;
 200     QVector<Type> _vector;
 201 };
 202 }
 203
 204 template <class Type>
 205 QDataStream &operator <<(QDataStream &s, const KGrid2D::Generic<Type> &m) {
 206     s << (quint32)m.width() << (quint32)m.height();
 207     for (uint i=0; i<m.size(); i++) s << m[i];
 208     return s;
 209 }
 210
 211 template <class Type>
 212 QDataStream &operator >>(QDataStream &s, KGrid2D::Generic<Type> &m) {
 213     quint32 w, h;
 214     s >> w >> h;
 215     m.resize(w, h);
 216     for (uint i=0; i<m.size(); i++) s >> m[i];
 217     return s;
 218 }
 219
 220
 221 namespace KGrid2D
 222 {
 223
 224 //-----------------------------------------------------------------------------
 225 /**
 226  * \class SquareBase kgrid2d.h <KGrid2D>
 227  *
 228  * kgamecanvas.hThis class contains static methods to manipulate coordinates for a
 229  * square bidimensionnal grid.
 230  */
 231 class SquareBase
 232 {
 233  public:
 234     /**
 235      * Identify the eight neighbours.
 236      */
 237     enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
 238                      RightUp, RightDown, Nb_Neighbour };
 239
 240     /**
 241      * @return the trigonometric angle in radians for the given neighbour.
 242      */
 243     static double angle(Neighbour n) {
 244         switch (n) {
 245         case Left:      return M_PI;
 246         case Right:     return 0;
 247         case Up:        return M_PI_2;
 248         case Down:      return -M_PI_2;
 249         case LeftUp:    return 3.0*M_PI_4;
 250         case LeftDown:  return -3.0*M_PI_4;
 251         case RightUp:   return M_PI_4;
 252         case RightDown: return -M_PI_4;
 253         case Nb_Neighbour: Q_ASSERT(false);
 254         }
 255         return 0;
 256     }
 257
 258     /**
 259      * @return the opposed neighbour.
 260      */
 261     static Neighbour opposed(Neighbour n) {
 262         switch (n) {
 263         case Left:      return Right;
 264         case Right:     return Left;
 265         case Up:        return Down;
 266         case Down:      return Up;
 267         case LeftUp:    return RightDown;
 268         case LeftDown:  return RightUp;
 269         case RightUp:   return LeftDown;
 270         case RightDown: return LeftUp;
 271         case Nb_Neighbour: Q_ASSERT(false);
 272         }
 273         return Nb_Neighbour;
 274     }
 275
 276     /**
 277      * @return true if the neighbour is a direct one (ie is one of the four
 278      * nearest).
 279      */
 280     static bool isDirect(Neighbour n) { return n<LeftUp; }
 281
 282     /**
 283      * @return the neighbour for the given coordinate.
 284      */
 285     static Coord neighbour(const Coord &c, Neighbour n) {
 286         switch (n) {
 287         case Left:      return c + Coord(-1,  0);
 288         case Right:     return c + Coord( 1,  0);
 289         case Up:        return c + Coord( 0, -1);
 290         case Down:      return c + Coord( 0,  1);
 291         case LeftUp:    return c + Coord(-1, -1);
 292         case LeftDown:  return c + Coord(-1,  1);
 293         case RightUp:   return c + Coord( 1, -1);
 294         case RightDown: return c + Coord( 1,  1);
 295         case Nb_Neighbour: Q_ASSERT(false);
 296         }
 297         return c;
 298     }
 299 };
 300
 301 /**
 302  * \class Square kgrid2d.h <KGrid2D>
 303  *
 304  * This template is a @ref Generic implementation for a square bidimensionnal
 305  * grid (@ref SquareBase).
 306  */
 307 template <class T>
 308 class Square : public Generic<T>, public SquareBase
 309 {
 310  public:
 311     /**
 312      * Constructor.
 313      */
 314     Square(uint width = 0, uint height = 0)
 315         : Generic<T>(width, height) {}
 316
 317     /**
 318      * @return the neighbours of coordinate @param c
 319      * to the given set of coordinates
 320      * @param c the coordinate to use as the reference point
 321      * @param insideOnly only add coordinates that are inside the grid.
 322      * @param directOnly only add the four nearest neighbours.
 323      */
 324     CoordList neighbours(const Coord &c, bool insideOnly = true,
 325                          bool directOnly = false) const {
 326         CoordList neighbours;
 327         for (int i=0; i<(directOnly ? LeftUp : Nb_Neighbour); i++) {
 328             Coord n = neighbour(c, (Neighbour)i);
 329             if ( insideOnly && !Generic<T>::inside(n) ) continue;
 330             neighbours.append(n);
 331         }
 332         return neighbours;
 333     }
 334
 335     /**
 336      * @return the "projection" of the given coordinate on the grid edges.
 337      *
 338      * @param c the coordinate to use as the reference point
 339      * @param n the direction of projection.
 340      */
 341     Coord toEdge(const Coord &c, Neighbour n) const {
 342         switch (n) {
 343         case Left:      return Coord(0, c.second);
 344         case Right:     return Coord(Generic<T>::width()-1, c.second);
 345         case Up:        return Coord(c.first, 0);
 346         case Down:      return Coord(c.first, Generic<T>::height()-1);
 347         case LeftUp:    return Coord(0, 0);
 348         case LeftDown:  return Coord(0, Generic<T>::height()-1);
 349         case RightUp:   return Coord(Generic<T>::width()-1, 0);
 350         case RightDown: return Coord(Generic<T>::width()-1, Generic<T>::height()-1);
 351         case Nb_Neighbour: Q_ASSERT(false);
 352         }
 353         return c;
 354     }
 355 };
 356
 357 //-----------------------------------------------------------------------------
 358 /**
 359  * \class HexagonalBase kgrid2d.h <KGrid2D>
 360  *
 361  * This class contains static methods to manipulate coordinates on an
 362  * hexagonal grid where hexagons form horizontal lines:
 363  * <pre>
 364  * (0,0)   (0,1)   (0,2)
 365  *     (1,0)   (1,1)   (1,2)
 366  * (2,0)   (2,1)   (2,2)
 367  * </pre>
 368  */
 369 class HexagonalBase
 370 {
 371  public:
 372     /**
 373      * Identify the six neighbours.
 374      */
 375     enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
 376                      RightUp, RightDown, Nb_Neighbour };
 377
 378      /**
 379      * @return the trigonometric angle in radians for the given neighbour.
 380      */
 381     static double angle(Neighbour n) {
 382         switch (n) {
 383         case Left:      return M_PI;
 384         case Right:     return 0;
 385         case LeftUp:    return 2.0*M_PI/3;
 386         case LeftDown:  return -2.0*M_PI/3;
 387         case RightUp:   return M_PI/3;
 388         case RightDown: return -M_PI/3;
 389         case Nb_Neighbour: Q_ASSERT(false);
 390         }
 391         return 0;
 392     }
 393
 394     /**
 395      * @return the opposed neighbour.
 396      */
 397     static Neighbour opposed(Neighbour n) {
 398         switch (n) {
 399         case Left:      return Right;
 400         case Right:     return Left;
 401         case LeftUp:    return RightDown;
 402         case LeftDown:  return RightUp;
 403         case RightUp:   return LeftDown;
 404         case RightDown: return LeftUp;
 405         case Nb_Neighbour: Q_ASSERT(false);
 406         }
 407         return Nb_Neighbour;
 408     }
 409
 410     /**
 411      * @return the neighbour of the given coordinate.
 412      */
 413     static Coord neighbour(const Coord &c, Neighbour n) {
 414         bool oddRow = c.second%2;
 415         switch (n) {
 416         case Left:      return c + Coord(-1,  0);
 417         case Right:     return c + Coord( 1,  0);
 418         case LeftUp:    return c + (oddRow ? Coord( 0, -1) : Coord(-1, -1));
 419         case LeftDown:  return c + (oddRow ? Coord( 0,  1) : Coord(-1,  1));
 420         case RightUp:   return c + (oddRow ? Coord( 1, -1) : Coord( 0, -1));
 421         case RightDown: return c + (oddRow ? Coord( 1,  1) : Coord( 0,  1));
 422         case Nb_Neighbour: Q_ASSERT(false);
 423         }
 424         return c;
 425     }
 426
 427     /**
 428     * @return the distance between the two coordinates in term of hexagons.
 429     */
 430     static uint distance(const Coord &c1, const Coord &c2) {
 431         return qAbs(c1.first - c2.first) + qAbs(c1.second - c2.second)
 432             + (c1.first==c2.first || c1.second==c2.second ? 0 : -1);
 433     }
 434 };
 435
 436 /**
 437  * \class Hexagonal kgrid2d.h <KGrid2D>
 438  *
 439  * This template implements a hexagonal grid
 440  * where hexagons form horizontal lines:
 441  * <pre>
 442  * (0,0)   (0,1)   (0,2)
 443  *     (1,0)   (1,1)   (1,2)
 444  * (2,0)   (2,1)   (2,2)
 445  * </pre>
 446  */
 447 template <class Type>
 448 class Hexagonal : public Generic<Type>, public HexagonalBase
 449 {
 450  public:
 451     /**
 452      * Constructor.
 453      */
 454     Hexagonal(uint width = 0, uint height = 0)
 455         : Generic<Type>(width, height) {}
 456
 457     /**
 458      * @return the neighbours of coordinate @param c
 459      * to the given set of coordinates
 460      * @param c the coordiante to use as the reference point
 461      * @param insideOnly only add coordinates that are inside the grid.
 462      */
 463     CoordList neighbours(const Coord &c, bool insideOnly = true) const {
 464         CoordList neighbours;
 465         for (uint i=0; i<Nb_Neighbour; i++) {
 466             Coord n = neighbour(c, (Neighbour)i);
 467             if ( insideOnly && !Generic<Type>::inside(n) ) continue;
 468             neighbours.append(n);
 469         }
 470         return neighbours;
 471     }
 472
 473
 474     /**
 475      * @return the neighbours at distance @param distance of coordinate
 476      * @param c the coordinate to use as the reference point
 477      * @param distance distance to the neighbour (1 means at contact).
 478      * @param insideOnly only add coordinates that are inside the grid.
 479      * @param all returns all neighbours at distance equal and less than
 480      *        @param distance (the original coordinate is not included).
 481      */
 482     CoordList neighbours(const Coord &c, uint distance, bool all,
 483                         bool insideOnly = true) const {
 484         // brute force algorithm -- you're welcome to make it more efficient :)
 485         CoordList ring;
 486         if ( distance==0 ) return ring;
 487         ring = neighbours(c, insideOnly);
 488         if ( distance==1 ) return ring;
 489         CoordList center;
 490         center.append(c);
 491         for (uint i=1; i<distance; i++) {
 492             CoordList newRing;
 493             CoordList::const_iterator it;
 494             for (it=ring.begin(); it!=ring.end(); ++it) {
 495                 CoordList n = neighbours(*it, insideOnly);
 496                 CoordList::const_iterator it2;
 497                 for (it2=n.begin(); it2!=n.end(); ++it2)
 498                     if ( center.indexOf(*it2)==-1
 499                          && ring.indexOf(*it2)==-1
 500                          && newRing.indexOf(*it2)==-1 )
 501                         newRing.append(*it2);
 502                 center.append(*it);
 503             }
 504             ring = newRing;
 505         }
 506         if ( !all ) return ring;
 507         CoordList::const_iterator it;
 508         for (it=ring.begin(); it!=ring.end(); ++it)
 509             center.append(*it);
 510         center.removeAll(c);
 511         return center;
 512     }
 513 };
 514
 515 } // namespace
 516
 517 #endif