libkdegames Library API Documentation

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., 59 Temple Place - Suite 330, 00017 Boston, MA 02111-1307, 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 Logo
This file is part of the documentation for libkdegames Library Version 3.2.3.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Tue Sep 21 12:08:03 2004 by doxygen 1.3.7 written by Dimitri van Heesch, © 1997-2003