home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2009 February / PCWFEB09.iso / Software / Linux / SLAX 6.0.8 / slax-6.0.8.iso / slax / base / 006-devel.lzm / usr / include / kgrid2d.h < prev    next >
Encoding:
C/C++ Source or Header  |  2005-10-10  |  15.0 KB  |  521 lines
  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 <qpair.h>
  26. #include <qvaluelist.h>
  27. #include <qvaluevector.h>
  28.  
  29. #include <kglobal.h>
  30.  
  31.  
  32. //-----------------------------------------------------------------------------
  33. namespace KGrid2D
  34. {
  35.     /**
  36.      * This type represents coordinates on a bidimensionnal grid.
  37.      * @since 3.2
  38.      */
  39.     typedef QPair<int, int> Coord;
  40.  
  41.     /**
  42.      * This type represents a list of @ref Coord.
  43.      * @since 3.2
  44.      */
  45.     typedef QValueList<Coord> CoordList;
  46. }
  47.  
  48. inline KGrid2D::Coord
  49. operator +(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  50.     return KGrid2D::Coord(c1.first + c2.first, c1.second + c2.second);
  51. }
  52.  
  53. inline KGrid2D::Coord
  54. operator -(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  55.     return KGrid2D::Coord(c1.first - c2.first, c1.second - c2.second);
  56. }
  57.  
  58. /**
  59.  * @return the maximum of both coordinates.
  60.  * @since 3.2
  61.  */
  62. inline KGrid2D::Coord
  63. maximum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  64.     return KGrid2D::Coord(kMax(c1.first, c2.first), kMax(c1.second, c2.second));
  65. }
  66. /**
  67.  * @return the minimum of both coordinates.
  68.  * @since 3.2
  69.  */
  70. inline KGrid2D::Coord
  71. minimum(const KGrid2D::Coord &c1, const KGrid2D::Coord &c2) {
  72.     return KGrid2D::Coord(kMin(c1.first, c2.first), kMin(c1.second, c2.second));
  73. }
  74.  
  75. inline QTextStream &operator <<(QTextStream &s, const KGrid2D::Coord &c) {
  76.     return s << '(' << c.second << ", " << c.first << ')';
  77. }
  78.  
  79. inline QTextStream &operator <<(QTextStream &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. //-----------------------------------------------------------------------------
  87. namespace KGrid2D
  88. {
  89. /**
  90.  * This template class represents a generic bidimensionnal grid. Each node
  91.  * contains an element of the template type.
  92.  *
  93.  * @since 3.2
  94.  */
  95. template <class Type>
  96. class Generic
  97. {
  98.  public:
  99.     /**
  100.      * Constructor.
  101.      */
  102.     Generic(uint width = 0, uint height = 0) {
  103.         resize(width, height);
  104.     }
  105.  
  106.     virtual ~Generic() {}
  107.  
  108.     /**
  109.      * Resize the grid.
  110.      */
  111.     void resize(uint width, uint height) {
  112.         _width = width;
  113.         _height = height;
  114.         _vector.resize(width*height);
  115.     }
  116.  
  117.     /**
  118.      * Fill the nodes with the given value.
  119.      */
  120.     void fill(const Type &value) {
  121.         for (uint i=0; i<_vector.count(); i++) _vector[i] = value;
  122.     }
  123.  
  124.     /**
  125.      * @return the width.
  126.      */
  127.     uint width() const  { return _width; }
  128.     /**
  129.      * @return the height.
  130.      */
  131.     uint height() const { return _height; }
  132.     /**
  133.      * @return the number of nodes (ie width*height).
  134.      */
  135.     uint size() const   { return _width*_height; }
  136.  
  137.     /**
  138.      * @return the linear index for the given coordinate.
  139.      */
  140.     uint index(const Coord &c) const {
  141.         return c.first + c.second*_width;
  142.     }
  143.  
  144.     /**
  145.      * @return the coordinate corresponding to the linear index.
  146.      */
  147.     Coord coord(uint index) const {
  148.         return Coord(index % _width, index / _width);
  149.     }
  150.  
  151.     /**
  152.      * @return the value at the given coordinate.
  153.      */
  154.     const Type &at(const Coord &c) const { return _vector[index(c)]; }
  155.     /**
  156.      * @return the value at the given coordinate.
  157.      */
  158.     Type &at(const Coord &c)             { return _vector[index(c)]; }
  159.     /**
  160.      * @return the value at the given coordinate.
  161.      */
  162.     const Type &operator [](const Coord &c) const { return _vector[index(c)]; }
  163.     /**
  164.      * @return the value at the given coordinate.
  165.      */
  166.     Type &operator [](const Coord &c)             { return _vector[index(c)]; }
  167.  
  168.     /**
  169.      * @return the value at the given linear index.
  170.      */
  171.     const Type &at(uint index) const          { return _vector[index]; }
  172.     /**
  173.      * @return the value at the given linear index.
  174.      */
  175.     Type &at(uint index)                      { return _vector[index]; }
  176.     /**
  177.      * @return the value at the given linear index.
  178.      */
  179.     const Type &operator [](uint index) const { return _vector[index]; }
  180.     /**
  181.      * @return the value at the given linear index.
  182.      */
  183.     Type &operator [](uint index)             { return _vector[index]; }
  184.  
  185.     /**
  186.      * @return if the given coordinate is inside the grid.
  187.      */
  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.  
  193.     /**
  194.      * Bound the given coordinate with the grid dimensions.
  195.      */
  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.     QValueVector<Type> _vector;
  204. };
  205. }
  206.  
  207. template <class Type>
  208. QDataStream &operator <<(QDataStream &s, const KGrid2D::Generic<Type> &m) {
  209.     s << (Q_UINT32)m.width() << (Q_UINT32)m.height();
  210.     for (uint i=0; i<m.size(); i++) s << m[i];
  211.     return s;
  212. }
  213.  
  214. template <class Type>
  215. QDataStream &operator >>(QDataStream &s, KGrid2D::Generic<Type> &m) {
  216.     Q_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.  
  224. namespace KGrid2D
  225. {
  226.  
  227. //-----------------------------------------------------------------------------
  228. /**
  229.  * This class contains static methods to manipulate coordinates for a
  230.  * square bidimensionnal grid.
  231.  *
  232.  * @since 3.2
  233.  */
  234. class SquareBase
  235. {
  236.  public:
  237.     /**
  238.      * Identify the eight neighbours.
  239.      */
  240.     enum Neighbour { Left=0, Right, Up, Down, LeftUp, LeftDown,
  241.                      RightUp, RightDown, Nb_Neighbour };
  242.  
  243.     /**
  244.      * @return the trigonometric angle in radians for the given neighbour.
  245.      */
  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.  
  261.     /**
  262.      * @return the opposed neighbour.
  263.      */
  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.  
  279.     /**
  280.      * @return true if the neighbour is a direct one (ie is one of the four
  281.      * nearest).
  282.      */
  283.     static bool isDirect(Neighbour n) { return n<LeftUp; }
  284.  
  285.     /**
  286.      * @return the neighbour for the given coordinate.
  287.      */
  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.  
  304. /**
  305.  * This template is a @ref Generic implementation for a square bidimensionnal
  306.  * grid (@ref SquareBase).
  307.  *
  308.  * @since 3.2
  309.  */
  310. template <class T>
  311. class Square : public Generic<T>, public SquareBase
  312. {
  313.  public:
  314.     /**
  315.      * Constructor.
  316.      */
  317.     Square(uint width = 0, uint height = 0)
  318.         : Generic<T>(width, height) {}
  319.  
  320.     /**
  321.      * @return the neighbours of coordinate @param c
  322.      * to the given set of coordinates
  323.      * @param c the coordinate to use as the reference point
  324.      * @param insideOnly only add coordinates that are inside the grid.
  325.      * @param directOnly only add the four nearest neighbours.
  326.      */
  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.  
  338.     /**
  339.      * @return the "projection" of the given coordinate on the grid edges.
  340.      *
  341.      * @param c the coordinate to use as the reference point
  342.      * @param n the direction of projection.
  343.      */
  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. //-----------------------------------------------------------------------------
  361. /**
  362.  * This class contains static methods to manipulate coordinates on an
  363.  * hexagonal grid where hexagons form horizontal lines:
  364.  * <pre>
  365.  * (0,0)   (0,1)   (0,2)
  366.  *     (1,0)   (1,1)   (1,2)
  367.  * (2,0)   (2,1)   (2,2)
  368.  * </pre>
  369.  *
  370.  * @since 3.2
  371.  */
  372. class HexagonalBase
  373. {
  374.  public:
  375.     /**
  376.      * Identify the six neighbours.
  377.      */
  378.     enum Neighbour { Left = 0, Right, LeftUp, LeftDown,
  379.                      RightUp, RightDown, Nb_Neighbour };
  380.  
  381.      /**
  382.      * @return the trigonometric angle in radians for the given neighbour.
  383.      */
  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.  
  397.     /**
  398.      * @return the opposed neighbour.
  399.      */
  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.  
  413.     /**
  414.      * @return the neighbour of the given coordinate.
  415.      */
  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.  
  430.     /**
  431.     * @return the distance between the two coordinates in term of hexagons.
  432.     */
  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.  
  439. /**
  440.  * This template implements a hexagonal grid
  441.  * where hexagons form horizontal lines:
  442.  * <pre>
  443.  * (0,0)   (0,1)   (0,2)
  444.  *     (1,0)   (1,1)   (1,2)
  445.  * (2,0)   (2,1)   (2,2)
  446.  * </pre>
  447.  *
  448.  * @ since 3.2
  449.  */
  450. template <class Type>
  451. class Hexagonal : public Generic<Type>, public HexagonalBase
  452. {
  453.  public:
  454.     /**
  455.      * Constructor.
  456.      */
  457.     Hexagonal(uint width = 0, uint height = 0)
  458.         : Generic<Type>(width, height) {}
  459.  
  460.     /**
  461.      * @return the neighbours of coordinate @param c
  462.      * to the given set of coordinates
  463.      * @param c the coordiante to use as the reference point
  464.      * @param insideOnly only add coordinates that are inside the grid.
  465.      */
  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.  
  477.     /**
  478.      * @return the neighbours at distance @param distance of coordinate
  479.      * @param c the coordinate to use as the reference point
  480.      * @param distance distance to the neighbour (1 means at contact).
  481.      * @param insideOnly only add coordinates that are inside the grid.
  482.      * @param all returns all neighbours at distance equal and less than
  483.      *        @param distance (the original coordinate is not included).
  484.      */
  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
  521.