ryzom/server/src/gpm_service/move_grid.h

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program 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
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17
  18
  19 #ifndef NL_MOVE_GRID_H
  20 #define NL_MOVE_GRID_H
  21
  22 #include "nel/misc/types_nl.h"
  23 #include "nel/misc/vector.h"
  24 #include "nel/misc/aabbox.h"
  25 #include "nel/misc/block_memory.h"
  26 #include "nel/misc/stream.h"
  27
  28 /**
  29  * A list of object that must have Next and Previous pointers
  30  * \param T the type of item
  31  * \param TPtr a pointer to T to use in list (useful for smartpointer)
  32  */
  33 template<class TT>
  34 class CMoveGridObjectList
  35 {
  36 public:
  37         TT                                                                      *Head;
  38         TT                                                                      *Tail;
  39
  40         CMoveGridObjectList() : Head(NULL), Tail(NULL) {}
  41
  42         void    insertAtHead(TT *object)
  43         {
  44                 nlassert(object->Next == NULL);
  45                 nlassert(object->Previous == NULL);
  46
  47                 object->Next = Head;
  48                 if (object->Next != NULL)
  49                         object->Next->Previous = object;
  50                 else
  51                         Tail = object;
  52                 Head = object;
  53         }
  54
  55         void    insertAtTail(TT *object)
  56         {
  57                 nlassert(object->Next == NULL);
  58                 nlassert(object->Previous == NULL);
  59
  60                 object->Previous = Tail;
  61                 if (object->Previous != NULL)
  62                         object->Previous->Next = object;
  63                 else
  64                         Head = object;
  65                 Tail = object;
  66         }
  67
  68         void    remove(TT *object)
  69         {
  70                 // if object at head
  71                 if (object->Previous == NULL)
  72                         Head = object->Next;
  73                 else
  74                         object->Previous->Next = object->Next;
  75
  76                 // if object at tail
  77                 if (object->Next == NULL)
  78                         Tail = object->Previous;
  79                 else
  80                         object->Next->Previous = object->Previous;
  81
  82                 object->Previous = NULL;
  83                 object->Next = NULL;
  84         }
  85
  86         TT                      *getHead() { return (TT*)Head; }
  87         TT                      *getTail() { return (TT*)Tail; }
  88 };
  89
  90 /**
  91  * Move grid, allows to select moving entities fast (template parameter CSIZE is in millimeter)
  92  * \author Benjamin Legros
  93  * \author Nevrax France
  94  * \date 2001
  95  */
  96 template<typename T, int CELLS, int CSIZE>
  97 class CMoveGrid
  98 {
  99 public:
 100         class CIterator;
 101         friend class CIterator;
 102
 103 protected:
 104         class CCellNode;
 105         class CNode;
 106
 107 public:
 108
 109         /// Constructor
 110         CMoveGrid();
 111
 112         /// Destructor
 113         ~CMoveGrid();
 114
 115         /// Clear
 116         void            clear();
 117
 118
 119         /// Insert an element in move grid. Return an iterator towards the inserted object
 120         CIterator       insert(const T &object, const NLMISC::CVector &position);
 121
 122
 123         /// Move an object in grid.
 124         void            move(CIterator &it, const NLMISC::CVector &position);
 125
 126
 127         /// Remove
 128         void            remove(CIterator &it);
 129         void            insertNode(CIterator &it, sint x, sint y);
 130         void            removeNode(CIterator &it);
 131
 132
 133         /// select
 134         void            select(const NLMISC::CVector &position);
 135
 136         /// select
 137         void            select(const NLMISC::CAABBox &bbox);
 138
 139         /// begin
 140         CIterator       begin();
 141
 142         /// end
 143         CIterator       end();
 144
 145         /// clearSelection
 146         void            clearSelection();
 147
 148         /// round value so it is a half of a segment
 149         double          round(double v)
 150         {
 151                 const double    INV = 1000.0 / (double)CSIZE;
 152                 return (floor(v*INV)+0.5)*(double)CSIZE*0.001;
 153         }
 154
 155         /// Serial
 156         void            serial(NLMISC::IStream &f);
 157
 158 protected:
 159         sint            convert(float v)
 160         {
 161                 const float     INV = 1000.0f / (float)CSIZE;
 162                 return (sint)(v*INV);
 163         }
 164
 165         sint            convertGrid(float v)
 166         {
 167                 const float     INV = 1000.0f / (float)CSIZE;
 168                 return (sint)(v*INV)&(CELLS-1);
 169         }
 170
 171         sint            convertGrid(sint v)
 172         {
 173                 return v&(CELLS-1);
 174         }
 175
 176         void            select(sint X, sint Y);
 177
 178
 179 protected:
 180
 181         /// A node that contains an objects.
 182         typedef CMoveGridObjectList<CNode>              TNodeList;
 183         /// A node that is a cell, containing a list of node inside this cell.
 184         typedef CMoveGridObjectList<CCellNode>  TCellNodeList;
 185
 186         class CCellNode
 187         {
 188         public:
 189                 sint32          X, Y;
 190                 sint32          GridX, GridY;
 191
 192                 TNodeList       NodeList;
 193
 194                 CCellNode       *Previous, *Next;
 195                 CCellNode       *Selection;
 196
 197                 CCellNode() : X(0), Y(0), GridX(0), GridY(0), Previous(NULL), Next(NULL), Selection(NULL) {}
 198
 199                 void            serial(NLMISC::IStream &f)
 200                 {
 201                         f.serial(X, Y, GridX, GridY);
 202                 }
 203         };
 204
 205         class CNode
 206         {
 207         public:
 208                 CNode           *Previous, *Next;
 209                 CCellNode       *Root;
 210                 T                       Object;
 211
 212                 CNode() : Previous(NULL), Next(NULL), Root(NULL) {}
 213
 214                 void            serial(NLMISC::IStream &f)
 215                 {
 216                         f.serial(Object);
 217                 }
 218         };
 219
 220         /// The map of cell nodes
 221         TCellNodeList   _Grid[CELLS][CELLS];
 222
 223         /// The first selected cell node
 224         CCellNode               *_Selection;
 225
 226         /// The allocator of nodes
 227         NLMISC::CBlockMemory<CNode>             _NodeAllocator;
 228         /// The allocator of cell nodes
 229         NLMISC::CBlockMemory<CCellNode> _CellNodeAllocator;
 230
 231 public:
 232         class CIterator
 233         {
 234                 friend class CMoveGrid<T, CELLS, CSIZE>;
 235         public:
 236                 CIterator(CNode *node = NULL) : _Node(node) {}
 237                 CIterator(const CIterator &it) : _Node(it._Node) {}
 238
 239                 T                       & operator * () { return _Node->Object; }
 240
 241                 CIterator       & operator ++ ()
 242                 {
 243                         if (_Node->Next != NULL)
 244                         {
 245                                 _Node = _Node->Next;
 246                         }
 247                         else
 248                         {
 249                                 CCellNode       *nextCell = _Node->Root->Selection;
 250                                 _Node = NULL;
 251                                 // iterate till we have a non empty selected cell
 252                                 while (nextCell != NULL && (_Node = nextCell->NodeList.getHead()) == NULL)
 253                                         nextCell = nextCell->Selection;
 254                         }
 255                         return *this;
 256                 }
 257                 CIterator       operator ++ (int)
 258                 {
 259                         CIterator ret(_Node);
 260                         ++(*this);
 261                         return ret;
 262                 }
 263
 264                 bool            operator == (const CIterator &it) const { return it._Node == _Node; }
 265                 bool            operator != (const CIterator &it) const { return !(*this == it); }
 266
 267                 CIterator       operator = (const CIterator &it) { _Node = it._Node; return *this; }
 268
 269         protected:
 270                 CNode   *_Node;
 271         };
 272 };
 273
 274 //
 275 // TEMPLATE IMPLEMENTATION
 276 //
 277
 278
 279
 280 // Serial
 281 template<typename T, int CELLS, int CSIZE>
 282 void    CMoveGrid<T, CELLS, CSIZE>::serial(NLMISC::IStream &f)
 283 {
 284         sint    version = f.serialVersion(0);
 285         f.serialCheck((sint32)CELLS);
 286         f.serialCheck((sint32)CSIZE);
 287
 288         if (f.isReading())
 289         {
 290                 clear();
 291                 sint    i, j;
 292                 uint32  nc, nn;
 293
 294                 for (i=0; i<CELLS; ++i)
 295                 {
 296                         for (j=0; j<CELLS; ++j)
 297                         {
 298                                 TCellNodeList   &list = _Grid[i][j];
 299                                 CCellNode               *cellNode;
 300                                 CNode                   *node;
 301
 302                                 f.serial(nc);
 303                                 while (nc-- > 0)
 304                                 {
 305                                         cellNode = _CellNodeAllocator.allocate();
 306                                         f.serial(*cellNode);
 307                                         list.insertAtTail(cellNode);
 308
 309                                         f.serial(nn);
 310                                         while (nn-- > 0)
 311                                         {
 312                                                 node = _NodeAllocator.allocate();
 313                                                 f.serial(*node);
 314                                                 cellNode->NodeList.insertAtTail(node);
 315                                                 node->Root = cellNode;
 316                                         }
 317                                 }
 318                         }
 319                 }
 320         }
 321         else
 322         {
 323                 sint    i, j;
 324                 uint32  nc, nn;
 325
 326                 for (i=0; i<CELLS; ++i)
 327                 {
 328                         for (j=0; j<CELLS; ++j)
 329                         {
 330                                 TCellNodeList   &list = _Grid[i][j];
 331                                 CCellNode               *cellNode;
 332                                 CNode                   *node;
 333
 334                                 cellNode = list.getHead();
 335                                 nc = 0;
 336                                 while (cellNode != NULL)
 337                                         ++nc, cellNode = cellNode->Next;
 338
 339                                 f.serial(nc);
 340                                 cellNode = list.getHead();
 341                                 while (cellNode != NULL)
 342                                 {
 343                                         f.serial(*cellNode);
 344
 345                                         node = cellNode->NodeList.getHead();
 346                                         nn = 0;
 347                                         while (node != NULL)
 348                                                 ++nn, node = node->Next;
 349
 350                                         f.serial(nn);
 351                                         node = cellNode->NodeList.getHead();
 352                                         while (node != NULL)
 353                                         {
 354                                                 f.serial(*node);
 355                                                 node = node->Next;
 356                                         }
 357
 358                                         cellNode = cellNode->Next;
 359                                 }
 360                         }
 361                 }
 362         }
 363 }
 364
 365
 366 //
 367 template<typename T, int CELLS, int CSIZE>
 368 void    CMoveGrid<T, CELLS, CSIZE>::clear()
 369 {
 370         sint    i, j;
 371
 372         for (i=0; i<CELLS; ++i)
 373         {
 374                 for (j=0; j<CELLS; ++j)
 375                 {
 376                         TCellNodeList   &list = _Grid[i][j];
 377                         CCellNode               *cellNode;
 378                         CNode                   *node;
 379                         while ((cellNode = list.getHead()) != NULL)
 380                         {
 381                                 while ((node = cellNode->NodeList.getHead()) != NULL)
 382                                 {
 383                                         cellNode->NodeList.remove(node);
 384                                         _NodeAllocator.freeBlock(node);
 385                                 }
 386                                 list.remove(cellNode);
 387                                 _CellNodeAllocator.freeBlock(cellNode);
 388                         }
 389                 }
 390         }
 391
 392         clearSelection();
 393 }
 394
 395 //
 396 template<typename T, int CELLS, int CSIZE>
 397 CMoveGrid<T, CELLS, CSIZE>::CMoveGrid()
 398 {
 399         _Selection = NULL;
 400 }
 401
 402
 403 //
 404 template<typename T, int CELLS, int CSIZE>
 405 CMoveGrid<T, CELLS, CSIZE>::~CMoveGrid()
 406 {
 407         clear();
 408 }
 409
 410 //
 411 template<typename T, int CELLS, int CSIZE>
 412 void    CMoveGrid<T, CELLS, CSIZE>::insertNode(CIterator &it, sint x, sint y)
 413 {
 414         sint    gridX, gridY;
 415         gridX = convertGrid(x);
 416         gridY = convertGrid(y);
 417
 418         CCellNode *cellNode = _Grid[gridX][gridY].getHead();
 419         while (cellNode != NULL && (cellNode->X != x || cellNode->Y != y))
 420                 cellNode = cellNode->Next;
 421
 422         if (cellNode == NULL)
 423         {
 424                 cellNode = _CellNodeAllocator.allocate();
 425                 _Grid[gridX][gridY].insertAtHead(cellNode);
 426                 cellNode->X = x;
 427                 cellNode->Y = y;
 428                 cellNode->GridX = gridX;
 429                 cellNode->GridY = gridY;
 430         }
 431
 432         it._Node->Root = cellNode;
 433         cellNode->NodeList.insertAtHead(it._Node);
 434 }
 435
 436 //
 437 template<typename T, int CELLS, int CSIZE>
 438 void    CMoveGrid<T, CELLS, CSIZE>::removeNode(CIterator &it)
 439 {
 440         it._Node->Root->NodeList.remove(it._Node);
 441 }
 442
 443 //
 444 template<typename T, int CELLS, int CSIZE>
 445 typename::CMoveGrid<T, CELLS, CSIZE>::CIterator CMoveGrid<T, CELLS, CSIZE>::insert(const T &object, const NLMISC::CVector &position)
 446 {
 447         CNode   *node = _NodeAllocator.allocate();
 448
 449         sint    X, Y;
 450
 451         X = convert(position.x);
 452         Y = convert(position.y);
 453         node->Object = object;
 454
 455         CIterator it(node);
 456         insertNode(it, X, Y);
 457
 458         return CIterator(node);
 459 }
 460
 461 template<typename T, int CELLS, int CSIZE>
 462 void    CMoveGrid<T, CELLS, CSIZE>::move(CIterator &it, const NLMISC::CVector &position)
 463 {
 464         sint    X, Y;
 465         X = convert(position.x);
 466         Y = convert(position.y);
 467
 468         CNode   *node = it._Node;
 469
 470         if (X == node->Root->X && Y == node->Root->Y)
 471                 return;
 472
 473         removeNode(it);
 474         insertNode(it, X, Y);
 475 }
 476
 477 template<typename T, int CELLS, int CSIZE>
 478 void    CMoveGrid<T, CELLS, CSIZE>::remove(CIterator &it)
 479 {
 480         CNode   *node = it._Node;
 481
 482         removeNode(it);
 483         it._Node = NULL;
 484
 485         _NodeAllocator.freeBlock(node);
 486 }
 487
 488
 489 template<typename T, int CELLS, int CSIZE>
 490 void    CMoveGrid<T, CELLS, CSIZE>::select(const NLMISC::CVector &position)
 491 {
 492         select(convert(position.x), convert(position.y));
 493 }
 494
 495 template<typename T, int CELLS, int CSIZE>
 496 void    CMoveGrid<T, CELLS, CSIZE>::select(const NLMISC::CAABBox &bbox)
 497 {
 498         sint    x0, x1;
 499         sint    y0, y1;
 500
 501         x0 = convert(bbox.getCenter().x-bbox.getHalfSize().x);
 502         x1 = convert(bbox.getCenter().x+bbox.getHalfSize().x);
 503
 504         y0 = convert(bbox.getCenter().y-bbox.getHalfSize().y);
 505         y1 = convert(bbox.getCenter().y+bbox.getHalfSize().y);
 506
 507         sint    x, y;
 508
 509         for (y=y0; y<=y1; ++y)
 510                 for (x=x0; x<=x1; ++x)
 511                         select(x, y);
 512 }
 513
 514 template<typename T, int CELLS, int CSIZE>
 515 void    CMoveGrid<T, CELLS, CSIZE>::select(sint x, sint y)
 516 {
 517         sint    gx = convertGrid(x),
 518                         gy = convertGrid(y);
 519
 520         CCellNode       *cellNode = _Grid[gx][gy].getHead();
 521         while (cellNode != NULL && (cellNode->X != x || cellNode->Y != y))
 522                 cellNode = cellNode->Next;
 523
 524         if (cellNode != NULL && cellNode->NodeList.getHead() != NULL)
 525         {
 526                 cellNode->Selection = _Selection;
 527                 _Selection = cellNode;
 528         }
 529 }
 530
 531 template<typename T, int CELLS, int CSIZE>
 532 typename::CMoveGrid<T, CELLS, CSIZE>::CIterator CMoveGrid<T, CELLS, CSIZE>::begin()
 533 {
 534         return (_Selection != NULL) ? CIterator(_Selection->NodeList.getHead()) : CIterator(NULL);
 535 }
 536
 537 template<typename T, int CELLS, int CSIZE>
 538 typename::CMoveGrid<T, CELLS, CSIZE>::CIterator CMoveGrid<T, CELLS, CSIZE>::end()
 539 {
 540         return CIterator(NULL);
 541 }
 542
 543 template<typename T, int CELLS, int CSIZE>
 544 void    CMoveGrid<T, CELLS, CSIZE>::clearSelection()
 545 {
 546         CCellNode       *cellNode = _Selection;
 547         _Selection = NULL;
 548
 549         while (cellNode != NULL)
 550         {
 551                 CCellNode       *nd = cellNode;
 552                 cellNode = cellNode->Selection;
 553                 nd->Selection = NULL;
 554         }
 555 }
 556
 557
 558 #endif // NL_MOVE_GRID_H
 559
 560 /* End of move_grid.h */