ryzom/server/src/ai_share/world_map.h

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This source file has been modified by the following contributors:
   5 // Copyright (C) 2013-2020  Jan BOON (Kaetemi) <jan.boon@kaetemi.be>
   6 //
   7 // This program is free software: you can redistribute it and/or modify
   8 // it under the terms of the GNU Affero General Public License as
   9 // published by the Free Software Foundation, either version 3 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU Affero General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Affero General Public License
  18 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19
  20
  21
  22 #ifndef NL_WORLD_MAP_H
  23 #define NL_WORLD_MAP_H
  24
  25 #include "nel/misc/types_nl.h"
  26 #include "nel/misc/time_nl.h"
  27 #include "nel/misc/debug.h"
  28 #include "nel/misc/stream.h"
  29
  30 #include "nel/pacs/u_global_position.h"
  31 #include "nel/misc/vectord.h"
  32
  33 #include "16x16_layer.h"
  34
  35 #include "ai_coord.h"
  36 #include "ai_vector.h"
  37 #include "ai_types.h"
  38
  39 class CFollowPath;
  40
  41 namespace RYPACSCRUNCH
  42 {
  43
  44 class CPacsCruncher;
  45
  46 }
  47
  48 namespace RYAI_MAP_CRUNCH
  49 {
  50
  51 enum TAStarFlag
  52 {
  53         Nothing                 = 0,
  54         Interior                = 1,
  55         Water                   = 2,
  56         NoGo                    = 4,
  57         WaterAndNogo    = 6,
  58         GroundFlags             = WaterAndNogo
  59 };
  60
  61 const std::string& toString(TAStarFlag flag);
  62 TAStarFlag toAStarFlag(const std::string& str);
  63
  64 uint const WorldMapGridSize = 256;
  65 double const WorldGridResolution = 1.;
  66 NLMISC::CVectorD const WorldStartOffset = NLMISC::CVectorD(0., 0., 0.);
  67
  68 typedef sint TLevel;
  69
  70
  71 //////////////////////////////////////////////////////////////////////////////
  72
  73 /**
  74  * Slot for the 3 map layer (corresponding to 3 heights of deplacement)
  75  * \author Stephane le Dorze
  76  * \author Nevrax France
  77  * \date 2003
  78  */
  79 class CSlot
  80 {
  81 public:
  82         enum
  83         {
  84                 INVALID_SLOT = 3
  85         };
  86
  87 public:
  88         explicit CSlot();
  89         explicit CSlot(uint slot);
  90
  91         bool isValid() const { return _Slot!=INVALID_SLOT; }
  92         void setSlot(CSlot const& slot) { _Slot = slot._Slot; }
  93
  94         bool operator ==(CSlot const& slot) const { return _Slot==slot._Slot; }
  95         bool operator !=(CSlot const& slot) const { return _Slot!=slot._Slot; }
  96
  97         bool operator >(CSlot const& slot) const { return _Slot>slot._Slot; }
  98         bool operator <(CSlot const& slot) const { return _Slot<slot._Slot; }
  99
 100         bool operator >=(CSlot const& slot) const { return _Slot>=slot._Slot; }
 101         bool operator <=(CSlot const& slot) const { return _Slot<=slot._Slot; }
 102
 103         CSlot const& operator ++();
 104
 105         uint8 slot() const { return _Slot; }
 106
 107 private:
 108         uint8 _Slot;
 109 };
 110
 111 inline
 112 CSlot::CSlot()
 113 : _Slot(INVALID_SLOT)
 114 {
 115 }
 116
 117 inline
 118 CSlot::CSlot(uint slot)
 119 : _Slot(slot)
 120 {
 121 #ifdef NL_DEBUG
 122         nlassert(slot>=0 && slot<=3);
 123 #endif
 124 }
 125
 126 inline
 127 CSlot const& CSlot::operator ++()
 128 {
 129         ++_Slot;
 130 #ifdef NL_DEBUG
 131         nlassert(_Slot<=INVALID_SLOT);
 132 #endif
 133         return *this;
 134 }
 135
 136 //////////////////////////////////////////////////////////////////////////////
 137
 138 /**
 139  * Compressed link set for the 4 cardinal directions
 140  * \author Benjamin Legros
 141  * \author Nevrax France
 142  * \date 2003
 143  */
 144 class CCellLinkage
 145 // pass CCellLinkage parameters by references. (anyway) and remove validation checks. (big update to come).
 146 {
 147 public:
 148         enum
 149         {
 150                 SouthSlotOffset = 0,
 151                 SouthSlotMask = 0x03,
 152                 EastSlotOffset = 2,
 153                 EastSlotMask = 0x0c,
 154                 NorthSlotOffset = 4,
 155                 NorthSlotMask = 0x30,
 156                 WestSlotOffset = 6,
 157                 WestSlotMask = 0xc0,
 158         };
 159
 160 public:
 161         CCellLinkage(uint8 links = 0xff);
 162
 163         CSlot SSlot() const { return CSlot((_Links & SouthSlotMask)  >> SouthSlotOffset); }
 164         CSlot ESlot() const { return CSlot((_Links & EastSlotMask)   >> EastSlotOffset); }
 165         CSlot NSlot() const { return CSlot((_Links & NorthSlotMask)  >> NorthSlotOffset); }
 166         CSlot WSlot() const { return CSlot((_Links & WestSlotMask)   >> WestSlotOffset); }
 167
 168         bool isSSlotValid() const { return (_Links&SouthSlotMask)!=SouthSlotMask; }
 169         bool isESlotValid() const { return (_Links&EastSlotMask)!=EastSlotMask; }
 170         bool isNSlotValid() const { return (_Links&NorthSlotMask)!=NorthSlotMask; }
 171         bool isWSlotValid() const { return (_Links&WestSlotMask)!=WestSlotMask; }
 172
 173         void setSSlot(CSlot const& slot);
 174         void setESlot(CSlot const& slot);
 175         void setNSlot(CSlot const& slot);
 176         void setWSlot(CSlot const& slot);
 177
 178         CCellLinkage& operator |=(uint8 links);
 179
 180         bool used() const { return _Links!=0xff; }
 181
 182         uint8 getLinks() const { return _Links; }
 183
 184         void serial(NLMISC::IStream &f);
 185
 186 private:
 187         uint8 _Links;
 188 };
 189
 190 inline
 191 CCellLinkage::CCellLinkage(uint8 links)
 192 : _Links(links)
 193 {
 194 }
 195
 196 inline
 197 void CCellLinkage::setSSlot(CSlot const& slot)
 198 {
 199         _Links = (_Links & (~SouthSlotMask)) + (slot.slot() << SouthSlotOffset);
 200 }
 201
 202 inline
 203 void CCellLinkage::setESlot(CSlot const& slot)
 204 {
 205         _Links = (_Links & (~EastSlotMask)) + (slot.slot() << EastSlotOffset);
 206 }
 207
 208 inline
 209 void CCellLinkage::setNSlot(CSlot const& slot)
 210 {
 211         _Links = (_Links & (~NorthSlotMask)) + (slot.slot() << NorthSlotOffset);
 212 }
 213
 214 inline
 215 void CCellLinkage::setWSlot(CSlot const& slot)
 216 {
 217         _Links = (_Links & (~WestSlotMask)) + (slot.slot() << WestSlotOffset);
 218 }
 219
 220 inline
 221 CCellLinkage& CCellLinkage::operator |=(uint8 links)
 222 {
 223         _Links |= links;
 224         return *this;
 225 }
 226
 227 inline
 228 void CCellLinkage::serial(NLMISC::IStream &f)
 229 {
 230         f.serial(_Links);
 231 }
 232
 233 //////////////////////////////////////////////////////////////////////////////
 234
 235 class CDirection
 236 {
 237         friend class CWorldMap;
 238 public:
 239         enum TDeltaDirection
 240         {
 241                 HALF_TURN_LEFT  = 1,    //      45 degres
 242                 HALF_TURN_RIGHT = -1,   //      -45 degres
 243                 TURN_LEFT               = 2,    //      90 degres
 244                 TURN_RIGHT              = -2,   //      -90 degres
 245                 HALF_TURN               = 4             //      180 degres
 246         };
 247
 248         enum TDirection
 249         {
 250                 E       = 0,
 251                 NE      = 1,
 252                 N       = 2,
 253                 NW      = 3,
 254                 W       = 4,
 255                 SW      = 5,
 256                 S       = 6,
 257                 SE      = 7,
 258                 UNDEFINED = 8
 259         };
 260
 261         enum TMotifDirection
 262         {
 263                 SHIFT_E  = 1,
 264                 SHIFT_NE = 2,
 265                 SHIFT_N  = 4,
 266                 SHIFT_NW = 8,
 267                 SHIFT_W  = 16,
 268                 SHIFT_SW = 32,
 269                 SHIFT_S  = 64,
 270                 SHIFT_SE = 128,
 271                 SHIFT_UNDEFINED = 256 // be aware, if you use a byte, it makes 0.
 272         };
 273
 274         enum TCost
 275         {
 276                 NO_COST         = 0,
 277                 ORTHO_COST  = 2,
 278                 DIAG_COST   = 3,
 279                 MAX_COST        = 3
 280         };
 281
 282 public:
 283         explicit CDirection();
 284         CDirection(CDirection const& dir);
 285         explicit CDirection(TDirection dir);
 286
 287         /// @name user interface assuming the y inversion (sorry).
 288         //@{
 289         explicit CDirection(int deltax, int deltay, bool toCalculate);
 290
 291         //      initialisation with a direction depending on deltas (-1,0 or 1)
 292         explicit CDirection(int deltax, int deltay);
 293
 294         //      initialisation with a direction depending on deltas (-1,0 or 1)
 295         explicit CDirection(CAngle const& angle);
 296
 297         CAngle getAngle();
 298
 299         sint dx() const;
 300         sint dy() const;
 301         void dxdy(int& dx, int& dy);
 302         //@}
 303
 304         bool isValid() { return _value!=UNDEFINED; }
 305
 306         // add a number of 45 turn
 307         void addStep(TDeltaDirection step);
 308
 309         NLMISC::CVector2f getDirFloat() const;
 310
 311         TDirection getVal() const;
 312
 313         TMotifDirection getShift() const;
 314
 315         bool operator !=(TDirection dir) const;
 316
 317         bool operator != (CDirection const& dir) const;
 318
 319         struct CDirectionData
 320         {
 321                 sint dx;
 322                 sint dy;
 323                 TCost weight;
 324         };
 325         static CDirectionData const directionDatas[];
 326         static TDirection const table[];
 327
 328         // used in pacs (nothing to do here but i haven't enought time to rewrite much code)
 329         uint32 getWeight();
 330
 331         static void getDirectionAround(CAngle const& Angle, CDirection& Dir0, CDirection& Dir1);
 332
 333 private:
 334         void setDxDy(int deltax, int deltay);
 335
 336         TDirection _value;
 337 };
 338
 339 inline
 340 CDirection::CDirection()
 341 : _value(UNDEFINED)
 342 {
 343 }
 344
 345 inline
 346 CDirection::CDirection(CDirection const& dir)
 347 : _value(dir._value)
 348 {
 349 }
 350
 351 inline
 352 CDirection::CDirection(TDirection dir)
 353 : _value(dir)
 354 {
 355 #ifdef NL_DEBUG
 356         nlassert(dir>=E &&      dir<=UNDEFINED);
 357 #endif
 358 }
 359
 360 inline
 361 CDirection::CDirection(int deltax, int deltay, bool toCalculate)
 362 {
 363 #ifdef NL_DEBUG
 364         nlassert(deltax!=0 || deltay!=0);
 365 #endif
 366         uint absDeltax = abs(deltax);
 367         uint absDeltay = abs(deltay);
 368
 369         if (deltax!=0 && deltay!=0)
 370         {
 371                 float ratio = (float)((float)absDeltax/(float)absDeltay);
 372                 if (ratio>=0.4141 && ratio<=2.4145)     // cos(PI/8)/sin(PI/8) ou sin(PI/8)/cos(PI/8)
 373                 {
 374                         setDxDy(deltax>0?1:-1, deltay>0?1:-1);
 375                         return;
 376                 }
 377         }
 378
 379         if (absDeltax>absDeltay)
 380                 setDxDy(deltax>0?1:-1, 0);
 381         else
 382                 setDxDy(0, deltay>0?1:-1);
 383 }
 384
 385 inline
 386 CDirection::CDirection(int deltax, int deltay)
 387 {
 388         setDxDy(deltax, deltay);
 389 }
 390
 391 inline
 392 CDirection::CDirection(CAngle const& angle)
 393 {
 394         _value = (TDirection)((((sint32)angle.asRawSint16()+65536+4096)/8192)&7);       //      add 4096 to have a correct angle magnet.
 395 }
 396
 397 inline
 398 CAngle CDirection::getAngle()
 399 {
 400 #ifdef NL_DEBUG
 401         nlassert(isValid());
 402 #endif
 403         return CAngle(_value*8192);
 404 }
 405
 406 inline
 407 sint CDirection::dx() const
 408 {
 409         return directionDatas[_value].dx;
 410 }
 411
 412 inline
 413 sint CDirection::dy() const
 414 {
 415         return directionDatas[_value].dy;
 416 }
 417
 418 inline
 419 void CDirection::dxdy(int& dx, int& dy)
 420 {
 421         CDirectionData const& direction = directionDatas[_value];
 422         dx = direction.dx;
 423         dy = direction.dy;
 424 }
 425
 426 inline
 427 void CDirection::addStep(TDeltaDirection step)
 428 {
 429 #ifdef NL_DEBUG
 430         nlassert(isValid());
 431 #endif
 432         _value = (TDirection)((_value+step)&7);
 433 }
 434
 435 inline
 436 NLMISC::CVector2f CDirection::getDirFloat() const
 437 {
 438         return NLMISC::CVector2f((float)dx(), (float)dy());
 439 }
 440
 441 inline
 442 CDirection::TDirection CDirection::getVal() const
 443 {
 444         return _value;
 445 }
 446
 447 inline
 448 CDirection::TMotifDirection CDirection::getShift() const
 449 {
 450         return (TMotifDirection)(1<<_value);
 451 }
 452
 453 inline
 454 bool CDirection::operator !=(TDirection dir) const
 455 {
 456         return _value!=dir;
 457 }
 458
 459 inline
 460 bool CDirection::operator != (CDirection const& dir) const
 461 {
 462         return _value!=dir._value;
 463 }
 464
 465 inline
 466 uint32 CDirection::getWeight()
 467 {
 468         return directionDatas[_value].weight;
 469 }
 470
 471 inline
 472 void CDirection::getDirectionAround(CAngle const& Angle, CDirection& Dir0, CDirection& Dir1)
 473 {
 474         sint value = Angle.asRawSint16()&(~16383);      //8191);
 475         Dir0 = CDirection(CAngle(value));
 476         value += 16384; //8192;
 477         Dir1 = CDirection(CAngle(value));
 478 }
 479
 480 inline
 481 void CDirection::setDxDy(int deltax, int deltay)
 482 {
 483 #ifdef NL_DEBUG
 484         nlassert( deltax>=-1 && deltax<=1 && deltay>=-1 && deltay<=1);
 485 #endif
 486         _value = table[1+deltax+(1+deltay)*3];
 487 #ifdef NL_DEBUG
 488         nlassert(dx()==deltax && dy()==deltay);
 489 #endif
 490 }
 491
 492 //////////////////////////////////////////////////////////////////////////////
 493
 494 /**
 495  * A map of accessible positions near a given position
 496  * \author Benjamin Legros
 497  * \author Nevrax France
 498  * \date 2003
 499  */
 500 class CNeighbourhood
 501 {
 502 public:
 503         /// One bit per direction
 504         bool isValid(CDirection::TDirection dir) const;
 505         bool isValid(CDirection const& dir) const;
 506         void set(CDirection::TDirection dir);
 507         CNeighbourhood();
 508
 509 private:
 510         CNeighbourhood(uint32 neighb);
 511
 512         /// 8 bits for 8 directions
 513         uint32  Neighb;
 514 };
 515
 516 inline
 517 bool CNeighbourhood::isValid(CDirection::TDirection dir) const
 518 {
 519         return (Neighb&CDirection(dir).getShift())!=0;
 520 }
 521
 522 inline
 523 bool CNeighbourhood::isValid(CDirection const& dir) const
 524 {
 525         return (Neighb&dir.getShift())!=0;
 526 }
 527
 528 inline
 529 void CNeighbourhood::set(CDirection::TDirection dir)
 530 {
 531         Neighb|=CDirection(dir).getShift();
 532 }
 533
 534 inline
 535 CNeighbourhood::CNeighbourhood()
 536 : Neighb(0)
 537 {
 538 }
 539
 540 inline
 541 CNeighbourhood::CNeighbourhood(uint32 neighb)
 542 : Neighb(neighb)
 543 {
 544 }
 545
 546 //////////////////////////////////////////////////////////////////////////////
 547
 548 /**
 549  * A slot, defining pacs position and linkage to other slots
 550  * \author Benjamin Legros
 551  * \author Nevrax France
 552  * \date 2003
 553  */
 554 class CUnitSlot
 555 {
 556 public:
 557         // 12 bits  0-11 : instance id
 558         // 12 bits 12-23 : surface id
 559         // 2 bits  24-25 : north link
 560         // 2 bits  26-27 : east link
 561         // 2 bits  28-29 : south link
 562         // 2 bits  30-31 : west link
 563         enum
 564         {
 565                 InstanceIdOffset = 0,
 566                 InstanceIdMask = 0x00000fff,
 567                 InstanceIdMax = 4096,
 568
 569                 SurfaceIdOffset = 12,
 570                 SurfaceIdMask = 0x00fff000,
 571                 SurfaceIdMax = 4096,
 572
 573                 SlotOffset = 24,
 574                 SlotMask = 0xff000000
 575         };
 576
 577         // 6 bits  0-5 topology
 578         // 2 bits  6-7 gabarit
 579         enum
 580         {
 581                 TopologyMask = 0x3f,
 582                 GabaritMask = 0xc0,
 583                 GabaritShift = 6,
 584         };
 585
 586         // 1 bit   0 interior
 587         // 1 bit   1 water
 588         // 1 bit   2 nogo
 589         // 13 bits 3-15 height
 590         enum
 591         {
 592                 InteriorMask = 0x0001,
 593                 WaterMask = 0x0002,
 594                 NoGoMask = 0x0004,
 595                 HeightMask = 0xfff8,
 596                 HeightShift = 3,
 597         };
 598
 599 public:
 600         /// @name Constructors
 601         //@{
 602         explicit CUnitSlot();
 603         explicit CUnitSlot(uint instanceId, uint surfaceId);
 604         explicit CUnitSlot(NLPACS::UGlobalPosition const& pos);
 605         //@}
 606
 607         // Selectors
 608         uint instanceId() const { return (_Id&InstanceIdMask) >> InstanceIdOffset; }
 609         uint surfaceId () const { return (_Id&SurfaceIdMask)  >> SurfaceIdOffset; }
 610         uint height    () const { return _Height >> HeightShift; }
 611
 612         CCellLinkage& cellLink() { return *((CCellLinkage*)(((char*)&_Id)+3)); }
 613         CCellLinkage getCellLink() const { return *((CCellLinkage*)(((char*)&_Id)+3)); }
 614         uint topology() const   { return (_Topology & TopologyMask); }
 615         uint gabarit() const    { return (_Topology & GabaritMask) >> GabaritShift; }
 616         bool interior() const   { return (_Height & InteriorMask) != 0; }
 617         bool water() const              { return (_Height & WaterMask) != 0; }
 618         bool nogo() const               { return (_Height & NoGoMask) != 0; }
 619
 620         /// @name Mutators
 621         //@{
 622         void setInstanceId(uint instanceId);
 623         void setSurface(uint surfaceId);
 624         void setTopology(uint topology);
 625         void setGabarit(uint gabarit);
 626         void setHeight(sint height);
 627         void setInterior(bool interior);
 628         void setWater(bool water);
 629         void setNoGo(bool nogo);
 630         void reset();
 631         //@}
 632
 633         bool used() const;
 634         bool hasSameSurface(const CUnitSlot &slot)      const;
 635
 636         void serial(NLMISC::IStream &f);
 637
 638 private:
 639         // _Id is divided this way
 640         // bits  0-11 : instance id
 641         // bits 12-23 : surface id
 642         // bits 24-25 : north link
 643         // bits 26-27 : east link
 644         // bits 28-29 : south link
 645         // bits 30-31 : west link
 646         uint32  _Id;
 647
 648         // 6 bits 0-5 topology
 649         // 2 bits 6-7 gabarit
 650         uint8   _Topology;
 651
 652         // 1 bit 0 interior
 653         // 1 bit 1 water
 654         // 1 bit 2 nogo
 655         // 13 bits 3-15 height
 656         sint16  _Height;
 657 };
 658 // a cell is composed of units of 3 slots
 659 typedef CUnitSlot TCellUnit[3];
 660
 661 inline
 662 CUnitSlot::CUnitSlot()
 663 : _Id(0xffffffff)
 664 , _Topology(0)
 665 , _Height(0)
 666 {
 667 }
 668
 669 inline
 670 CUnitSlot::CUnitSlot(uint instanceId, uint surfaceId)
 671 : _Topology(0)
 672 , _Height(0)
 673 {
 674 #ifdef NL_DEBUG
 675         nlassert(instanceId<InstanceIdMax);
 676         nlassert(surfaceId<SurfaceIdMax);
 677 #endif
 678         _Id = SlotMask + (instanceId << InstanceIdOffset) + (surfaceId << SurfaceIdOffset);
 679 }
 680
 681 inline
 682 CUnitSlot::CUnitSlot(NLPACS::UGlobalPosition const& pos)
 683 : _Topology(0)
 684 , _Height(0)
 685 {
 686 #ifdef NL_DEBUG
 687         nlassert(pos.InstanceId < InstanceIdMax);
 688         nlassert(pos.LocalPosition.Surface < SurfaceIdMax);
 689 #endif
 690         _Id=SlotMask+(pos.InstanceId<<InstanceIdOffset)+(pos.LocalPosition.Surface<<SurfaceIdOffset);
 691 }
 692
 693 inline
 694 void CUnitSlot::setInstanceId(uint instanceId)
 695 {
 696 #ifdef NL_DEBUG
 697         nlassert(instanceId < InstanceIdMax);
 698 #endif
 699         _Id = (_Id & (~InstanceIdMask)) + (instanceId << InstanceIdOffset);
 700 }
 701
 702 inline
 703 void CUnitSlot::setSurface(uint surfaceId)
 704 {
 705 #ifdef NL_DEBUG
 706         nlassert(surfaceId < SurfaceIdMax);
 707 #endif
 708         _Id = (_Id & (~SurfaceIdMask)) + (surfaceId << SurfaceIdOffset);
 709 }
 710
 711 inline
 712 void CUnitSlot::setTopology(uint topology)
 713 {
 714 #ifdef NL_DEBUG
 715         nlassert(topology < 63);
 716 #endif
 717         _Topology = (_Topology & (~TopologyMask)) + (uint8)topology;
 718 }
 719
 720 inline
 721 void CUnitSlot::setGabarit(uint gabarit)
 722 {
 723 #ifdef NL_DEBUG
 724         nlassert(gabarit < 4);
 725 #endif
 726         _Topology = (_Topology & (~GabaritMask)) | (uint8)(gabarit << GabaritShift);
 727 }
 728
 729 inline
 730 void CUnitSlot::setHeight(sint height)
 731 {
 732 #ifdef NL_DEBUG
 733         nlassert(height >= -4096 && height <= 4095);
 734 #endif
 735         _Height = (_Height & (~HeightMask)) | (sint16)(height << HeightShift);
 736 }
 737
 738 inline
 739 void CUnitSlot::setInterior(bool interior)
 740 {
 741         if (interior)
 742                 _Height |=      InteriorMask;
 743         else
 744                 _Height &=      ~InteriorMask;
 745 }
 746
 747 inline
 748 void CUnitSlot::setWater(bool water)
 749 {
 750         if (water)
 751                 _Height |= WaterMask;
 752         else
 753                 _Height &=      ~WaterMask;
 754 }
 755
 756 inline
 757 void CUnitSlot::setNoGo(bool nogo)
 758 {
 759         if (nogo)
 760                 _Height |= NoGoMask;
 761         else
 762                 _Height &= ~NoGoMask;
 763 }
 764
 765 inline
 766 void CUnitSlot::reset()
 767 {
 768         _Id = 0xffffffff;
 769         _Topology = 0;
 770         _Height = 0;
 771 }
 772
 773 inline
 774 bool CUnitSlot::used() const
 775 {
 776         return _Id != 0xffffffff;
 777 }
 778
 779 inline
 780 bool CUnitSlot::hasSameSurface(const CUnitSlot &slot)   const
 781 {
 782         return ((slot._Id ^ _Id) & (~SlotMask)) == 0;
 783 }
 784
 785 inline
 786 void CUnitSlot::serial(NLMISC::IStream &f)
 787 {
 788         f.serial(_Id);
 789         f.serial(_Topology);
 790         f.serial(_Height);
 791 }
 792
 793 //////////////////////////////////////////////////////////////////////////////
 794
 795 class CMapPosition;
 796
 797 typedef sint32 TMapCoordType;
 798
 799 /**
 800  * A simple 1 axis coordinate
 801  * \author Benjamin Legros
 802  * \author Nevrax France
 803  * \date 2003
 804  */
 805 class CMapCoord
 806 {
 807         friend class CMapPosition;
 808 public:
 809         explicit CMapCoord(uint scellId, uint cellId, uint unitId);
 810
 811 private:
 812         explicit CMapCoord() : c(0) { }
 813         explicit CMapCoord(CAICoord const& aiCoord) : c((sint)(floor(aiCoord.asDouble()+0.5))) { }
 814         explicit CMapCoord(sint cc) : c(cc) { }
 815
 816         uint cellIdMask(uint val) const;
 817         uint fullCellIdMask(uint val) const;
 818
 819         uint toUnitId(uint val) const;
 820         uint toCellId(uint val) const;
 821         uint toSuperCellId(uint val) const;
 822
 823         uint unitIdToUInt(uint val) const;
 824         uint cellIdToUInt(uint val) const;
 825         uint superCellIdToUInt(uint val) const;
 826         uint fullCellIdToUInt(uint val) const;
 827
 828         TMapCoordType& cRef();
 829
 830 public:
 831         uint getUnitId          () const { return unitIdToUInt(c); }
 832         uint getCellId          () const { return cellIdToUInt(c); }
 833         uint getSuperCellId     () const { return superCellIdToUInt(c); }
 834         uint getFullCellId      () const { return fullCellIdToUInt(c); }
 835
 836         void setUnitId(uint id) { c = fullCellIdMask(c) | toUnitId(id); }
 837         void setCellId(uint id) { c = cellIdMask(c)             | toCellId(id); }
 838
 839         bool operator ==(CMapCoord const& cc) const { return c == cc.c; }
 840         bool operator !=(CMapCoord const& cc) const { return c != cc.c; }
 841         CMapCoord operator -(CMapCoord const& cc) const { return CMapCoord(c-cc.c); }
 842
 843         TMapCoordType const& get() const { return c; }
 844
 845 private:
 846         // coordinate
 847         TMapCoordType c;
 848 };
 849
 850 inline
 851 CMapCoord::CMapCoord(uint scellId, uint cellId, uint unitId)
 852 : c(toSuperCellId(scellId) + toCellId(cellId) + toUnitId(unitId))
 853 {
 854 #ifdef NL_DEBUG
 855         nlassert(scellId < 256);
 856 #endif
 857 }
 858
 859 inline
 860 uint CMapCoord::cellIdMask(uint val) const
 861 {
 862         return val&0xff0f;
 863 }
 864
 865 inline
 866 uint CMapCoord::fullCellIdMask(uint val) const
 867 {
 868         return val&0x0fffffff0;
 869 }
 870
 871 inline
 872 uint CMapCoord::toUnitId(uint val) const
 873 {
 874         return val&0x0f;
 875 }
 876
 877 inline
 878 uint CMapCoord::toCellId(uint val) const
 879 {
 880         return (val<<4)&0x0f0;
 881 }
 882
 883 inline
 884 uint CMapCoord::toSuperCellId(uint val) const
 885 {
 886         return (val<<8)&0x0ffff;
 887 }
 888
 889 inline
 890 uint CMapCoord::unitIdToUInt(uint val) const
 891 {
 892         return val&0x0f;
 893 }
 894
 895 inline
 896 uint CMapCoord::cellIdToUInt(uint val) const
 897 {
 898         return (val>>4)&0xf;
 899 }
 900
 901 inline
 902 uint CMapCoord::superCellIdToUInt(uint val) const
 903 {
 904         return (val>>8)&0x0ff;
 905 }
 906
 907 inline
 908 uint CMapCoord::fullCellIdToUInt(uint val) const
 909 {
 910         return (val>>4)&0x0fff;
 911 }
 912
 913 inline
 914 TMapCoordType& CMapCoord::cRef()
 915 {
 916         return c;
 917 }
 918
 919 //////////////////////////////////////////////////////////////////////////////
 920
 921 /**
 922  * A map position, consisting of 2 axis coordinates
 923  * \author Benjamin Legros
 924  * \author Nevrax France
 925  * \date 2003
 926  */
 927 class CMapPosition
 928 {
 929         friend class RYPACSCRUNCH::CPacsCruncher;
 930 public:
 931         CMapPosition() { }
 932         CMapPosition(sint x, sint y);
 933         CMapPosition(CMapCoord const& x, CMapCoord const& y);
 934         CMapPosition(CMapPosition const& pos);
 935         CMapPosition(NLMISC::CVectorD const& pos);
 936         CMapPosition(CAIVector const& pos);
 937         CMapPosition(CAICoord const& x, CAICoord const& y);
 938
 939         NLMISC::CVectorD toVectorD() const;
 940         NLMISC::CVector2d toVector2d() const;
 941         CAIVector toAIVector() const;
 942
 943         std::string toString() const;
 944
 945         void setUnitId(uint const xId, uint const yId);
 946         void setNullUnitId();
 947
 948         CMapPosition stepCell(sint dx, sint dy) const;
 949
 950         bool hasSameFullCellId(CMapPosition const& other) const;
 951
 952         CMapPosition operator -(CMapPosition const& other) const;
 953         bool operator ==(CMapPosition const& cc) const;
 954         bool operator !=(CMapPosition const& cc) const;
 955
 956         CMapCoord const& xCoord() const { return _x; }
 957         CMapCoord const& yCoord() const { return _y; }
 958
 959         TMapCoordType const& x() const { return _x.get(); }
 960         TMapCoordType const& y() const { return _y.get(); }
 961
 962         uint32 superCellFastIndex() const;
 963         uint32 rootCellFastIndex() const;
 964         uint32 cellUnitFastIndex() const;
 965
 966         CMapPosition step(sint dx, sint dy) const;
 967
 968         CMapPosition getStepS() const { return step(0, -1); }
 969         CMapPosition getStepN() const { return step(0, +1); }
 970         CMapPosition getStepE() const { return step(+1, 0); }
 971         CMapPosition getStepW() const { return step(-1, 0); }
 972 protected:
 973
 974         // return if we have changed of RootCell ..
 975         bool stepS() { _y.cRef()-=1; return ((_y.cRef()&0xf)==0xf); }
 976         bool stepN() { _y.cRef()+=1; return ((_y.cRef()&0xf)==0x0); }
 977         bool stepW() { _x.cRef()-=1; return ((_x.cRef()&0xf)==0xf); }
 978         bool stepE() { _x.cRef()+=1; return ((_x.cRef()&0xf)==0x0); }
 979
 980 private:
 981         CMapCoord _x;
 982         CMapCoord _y;
 983 };
 984
 985 inline
 986 CMapPosition::CMapPosition(sint x, sint y)
 987 : _x(CMapCoord(x))
 988 , _y(CMapCoord(y))
 989 {
 990 }
 991
 992 inline
 993 CMapPosition::CMapPosition(CMapCoord const& x, CMapCoord const& y)
 994 : _x(x)
 995 , _y(y)
 996 {
 997 }
 998
 999 inline
1000 CMapPosition::CMapPosition(CMapPosition const& pos)
1001 : _x(pos._x)
1002 , _y(pos._y)
1003 {
1004 }
1005
1006 inline
1007 CMapPosition::CMapPosition(NLMISC::CVectorD const& pos)
1008 : _x((uint)floor((pos.x - WorldStartOffset.x)/WorldGridResolution + 0.5))
1009 , _y((uint)floor((pos.y - WorldStartOffset.y)/WorldGridResolution + 0.5))
1010 {
1011 }
1012
1013 inline
1014 CMapPosition::CMapPosition(CAIVector const& pos)
1015 : _x(pos.x())
1016 , _y(pos.y())
1017 {
1018 }
1019
1020 inline
1021 CMapPosition::CMapPosition(CAICoord const& x, CAICoord const& y)
1022 : _x(x)
1023 , _y(y)
1024 {
1025 }
1026
1027 inline
1028 NLMISC::CVectorD CMapPosition::toVectorD() const
1029 {
1030         return NLMISC::CVectorD(WorldStartOffset.x + _x.get()*WorldGridResolution, WorldStartOffset.y + _y.get()*WorldGridResolution, 0.0);
1031 }
1032
1033 inline
1034 NLMISC::CVector2d CMapPosition::toVector2d() const
1035 {
1036         return NLMISC::CVector2d(WorldStartOffset.x + _x.get()*WorldGridResolution, WorldStartOffset.y + _y.get()*WorldGridResolution);
1037 }
1038
1039 inline
1040 CAIVector CMapPosition::toAIVector() const
1041 {
1042         return CAIVector(WorldStartOffset.x + _x.get()*WorldGridResolution, WorldStartOffset.y + _y.get()*WorldGridResolution);
1043 }
1044
1045 inline
1046 std::string CMapPosition::toString() const
1047 {
1048         return toAIVector().toString();
1049 }
1050
1051 inline
1052 void CMapPosition::setUnitId(uint const xId, uint const yId)
1053 {
1054         _x.setUnitId(xId);
1055         _y.setUnitId(yId);
1056 }
1057
1058 inline
1059 void CMapPosition::setNullUnitId()
1060 {
1061   _x.setUnitId(0);
1062   _y.setUnitId(0);
1063 }
1064
1065 inline
1066 CMapPosition CMapPosition::stepCell(sint dx, sint dy) const
1067 {
1068         CMapPosition newMapPos(xCoord().get()+(dx<<4),yCoord().get()+(dy<<4));
1069         newMapPos.setNullUnitId();
1070         return newMapPos;
1071 }
1072
1073 inline
1074 bool CMapPosition::hasSameFullCellId(CMapPosition const& other) const
1075 {
1076         return ( _x.getFullCellId()==other._x.getFullCellId() && _y.getFullCellId()==other._y.getFullCellId() );
1077 }
1078
1079 inline
1080 CMapPosition CMapPosition::operator -(CMapPosition const& other) const
1081 {
1082         return CMapPosition(_x-other._x,_y-other._y);
1083 }
1084
1085 inline
1086 bool CMapPosition::operator ==(CMapPosition const& cc) const
1087 {
1088         return _x==cc._x && _y==cc._y;
1089 }
1090
1091 inline
1092 bool CMapPosition::operator !=(CMapPosition const& cc) const
1093 {
1094         return _x!=cc._x || _y!=cc._y;
1095 }
1096
1097 inline
1098 uint32 CMapPosition::superCellFastIndex() const
1099 {
1100         return ((((uint)y())&(0x0ff<<8)) + xCoord().getSuperCellId());
1101 }
1102
1103 inline
1104 uint32 CMapPosition::rootCellFastIndex() const
1105 {
1106         return ((((uint)y())&0x0f<<4) + xCoord().getCellId());
1107 }
1108
1109 inline
1110 uint32 CMapPosition::cellUnitFastIndex() const
1111 {
1112         return ((yCoord().getUnitId()<<4) + xCoord().getUnitId());
1113 }
1114
1115 inline
1116 CMapPosition CMapPosition::step(sint dx, sint dy) const
1117 {
1118         return CMapPosition(_x.get() + dx, _y.get() + dy);
1119 }
1120
1121 //////////////////////////////////////////////////////////////////////////////
1122
1123 /**
1124  * Motion map interface
1125  * \author Benjamin Legros
1126  * \author Nevrax France
1127  * \date 2003
1128  */
1129 class CGridDirectionLayer
1130 : public I16x16Layer
1131 {
1132 public:
1133         CDirection getDirection(int y, int x) const;
1134         CDirection getDirection(CMapPosition const& pos) const;
1135
1136         void setDirection(int y, int x, CDirection dir);
1137 };
1138
1139 inline
1140 CDirection CGridDirectionLayer::getDirection(int y, int x) const
1141 {
1142         return CDirection((CDirection::TDirection)get(y, x));
1143 }
1144
1145 inline
1146 CDirection CGridDirectionLayer::getDirection(CMapPosition const& pos) const
1147 {
1148         return CDirection((CDirection::TDirection)get(pos.yCoord().getUnitId(), pos.xCoord().getUnitId()));
1149 }
1150
1151 inline
1152 void CGridDirectionLayer::setDirection(int y, int x, CDirection dir)
1153 {
1154         this->set((uint)y, (uint)x, (sint)dir.getVal());
1155 }
1156
1157 //////////////////////////////////////////////////////////////////////////////
1158
1159 class CDirectionLayer
1160 {
1161 public:
1162         CDirectionLayer();
1163
1164         void serial(NLMISC::IStream& f);
1165
1166         CGridDirectionLayer* getGridLayer(int y, int x);
1167         void setGridLayer(int y, int x, I16x16Layer* layer);
1168
1169         void dump();
1170
1171 private:
1172         // Grid[1][1] is central cell
1173         I16x16Layer     *Grid[3][3];
1174 };
1175
1176 inline
1177 CDirectionLayer::CDirectionLayer()
1178 {
1179         uint i, j;
1180         for (i=0; i<3; ++i)
1181                 for (j=0; j<3; ++j)
1182                         Grid[i][j] = NULL;
1183 }
1184
1185 inline
1186 CGridDirectionLayer* CDirectionLayer::getGridLayer(int y, int x)
1187 {
1188         return static_cast<CGridDirectionLayer*>(Grid[y][x]);
1189 }
1190
1191 inline
1192 void CDirectionLayer::setGridLayer(int y, int x, I16x16Layer* layer)
1193 {
1194         Grid[y][x] = layer;
1195 }
1196
1197 inline
1198 void CDirectionLayer::dump()
1199 {
1200         char output[16*3][16*3];
1201         for (sint i=2; i>=0; --i)
1202                 for (sint j=0; j<3; ++j)
1203                         for (sint y=15; y>=0; --y)
1204                                 for (sint x=0; x<16; ++x)
1205         {
1206                 CGridDirectionLayer* gridDirectionLayer = getGridLayer(i,j);
1207                 CDirection motion;
1208
1209                 if (gridDirectionLayer)
1210                         motion = gridDirectionLayer->getDirection(y,x);
1211
1212                 char c = ' ';
1213
1214                 switch (motion.getVal())
1215                 {
1216                 case CDirection::N:
1217                         c = '^';
1218                         break;
1219                 case CDirection::S:
1220                         c = 'v';
1221                         break;
1222                 case CDirection::E:
1223                         c = '>';
1224                         break;
1225                 case CDirection::W:
1226                         c = '<';
1227                         break;
1228                 case CDirection::NE:
1229                         c = '7';
1230                         break;
1231                 case CDirection::SW:
1232                         c = 'L';
1233                         break;
1234                 case CDirection::NW:
1235                         c = 'r';
1236                         break;
1237                 case CDirection::SE:
1238                         c = '\\';
1239                         break;
1240 //              case 255:
1241 //                      c = ' ';
1242 //                      break;
1243                 default:
1244                         c = 'o';
1245                         break;
1246                 }
1247                 output[y+i*16][x+j*16] = c;
1248         }
1249
1250         char op[256];
1251         nlinfo("    \t0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF");
1252
1253         for (sint i=47; i>=0; --i)
1254         {
1255                 sint j;
1256                 for (j=0; j<48; ++j)
1257                         op[j] = output[i][j];
1258                 op[j] = '\0';
1259                 nlinfo("%04X\t%s", (i&15), op);
1260         }
1261 }
1262
1263 //////////////////////////////////////////////////////////////////////////////
1264
1265 class CDirectionMap
1266 {
1267 public:
1268         CDirectionLayer* Layers[3];
1269
1270         CDirectionMap();
1271
1272         void serial(NLMISC::IStream& f);
1273
1274         void dump();
1275 };
1276
1277 inline
1278 CDirectionMap::CDirectionMap()
1279 {
1280         Layers[0] = NULL;
1281         Layers[1] = NULL;
1282         Layers[2] = NULL;
1283 }
1284
1285 inline
1286 void CDirectionMap::dump()
1287 {
1288         for (uint i=0; i<3; ++i)
1289         {
1290                 nlinfo("Layer %d", i);
1291                 if (Layers[i] != NULL)
1292                         Layers[i]->dump();
1293                 else
1294                         nlinfo("Empty");
1295         }
1296 }
1297
1298 //////////////////////////////////////////////////////////////////////////////
1299
1300 class CWorldMap;
1301 class CRootCell;
1302 class CWorldPosition;
1303
1304 class CTopology
1305 {
1306 public:
1307
1308         /// A topology Id, representing cell and topology
1309         class TTopologyId
1310         {
1311         public:
1312                 enum
1313                 {
1314                         UNDEFINED_TOPOLOGY      =       0xffffffff
1315                 };
1316
1317         public:
1318                 explicit TTopologyId();
1319                 explicit TTopologyId(CMapPosition const& pos, uint topology);
1320                 // For test only
1321                 explicit TTopologyId(uint32 id);
1322
1323                 bool haveSameCellPos(TTopologyId const& other) const;
1324
1325                 CMapPosition getMapPosition() const;
1326                 uint getTopologyIndex() const;
1327
1328                 bool isValid() const;
1329
1330                 bool operator <(TTopologyId const& other) const;
1331                 bool operator ==(TTopologyId const& other) const;
1332                 bool operator !=(TTopologyId const& other) const;
1333
1334                 void serial(NLMISC::IStream& f);
1335
1336                 uint32 getVal() const;
1337
1338         private:
1339                 uint32 _value;
1340         };
1341
1342         class TTopologyRef
1343         : public TTopologyId
1344         {
1345                 friend class CWorldPosition;
1346         public:
1347                 TTopologyRef(CWorldPosition const& pos);
1348                 TTopologyRef();
1349                 explicit TTopologyRef(TTopologyId const& id, CRootCell* rootCell);
1350                 CTopology const& getCstTopologyNode() const;
1351                 void setRootCell(CRootCell* rootCell);
1352
1353                 void serial(NLMISC::IStream& f);
1354                 CRootCell const* getRootCell() const;
1355
1356         private:
1357                 TTopologyRef(CWorldPosition const& pos, CRootCell const* rootCell);
1358                 CRootCell const* _RootCell;
1359         };
1360
1361         /// A link to a neighbour, including mean distance to it
1362         class CNeighbourLink
1363         {
1364         public:
1365                 explicit CNeighbourLink();
1366                 explicit CNeighbourLink(TTopologyRef const& ref, float distance);
1367                 CNeighbourLink(CNeighbourLink const& other);
1368
1369                 void serial(NLMISC::IStream& f);
1370
1371                 TTopologyRef const& getTopologyRef() const;
1372
1373                 void updateTopologyRef(CWorldMap* worldMapPtr);
1374
1375                 float getDistance() const;
1376
1377         private:
1378                 TTopologyRef _Ref;
1379                 float _Distance;
1380         };
1381
1382         void updateTopologyRef(CWorldMap* worldMapPtr);
1383
1384         bool isInInterior() const { return (Flags & Interior) != 0; }
1385         bool isInWater() const { return (Flags & Water) != 0; }
1386         bool isInNogo() const { return (Flags & NoGo) != 0; }
1387
1388         TAStarFlag getFlags() const { return (TAStarFlag)Flags; }
1389
1390         uint32 getMasterTopo(TAStarFlag const& flags) const;
1391
1392         uint32 getMasterTopo(bool allowWater, bool allowNoGo) const;
1393
1394         uint32& getMasterTopoRef(bool allowWater, bool allowNoGo);
1395
1396         bool isCompatible(bool allowWater, bool allowNoGo) const;
1397
1398         /// The Id of this topology
1399         TTopologyId      Id;
1400         /// The direction map to access this topology
1401         CDirectionMap* DirectionMap;
1402         /// The neighbour topologies that have access to this topology
1403         std::vector<CNeighbourLink>     Neighbours;
1404         /// Flags of the topology
1405         uint16 Flags;                   // why doing this (uint16), its not align so no gain in memory and it causes access cost !
1406         /// Master topologies
1407         uint32 MasterTopL;              // only landscape
1408         uint32 MasterTopLW;     // landscape and water
1409         uint32 MasterTopLN;     // landscape and nogo
1410         uint32 MasterTopLNW;    // landscape and water and nogo
1411
1412         /// Topology center, for A* purpose
1413         NLMISC::CVector Position;
1414
1415         CTopology();
1416
1417         void serial(NLMISC::IStream& f);
1418 };
1419
1420 inline
1421 CTopology::TTopologyId::TTopologyId()
1422 : _value(UNDEFINED_TOPOLOGY)
1423 {
1424 }
1425
1426 inline
1427 CTopology::TTopologyId::TTopologyId(CMapPosition const& pos, uint topology)
1428 {
1429 #ifdef NL_DEBUG
1430         nlassert(topology < 256);
1431 #endif
1432         _value = (pos.yCoord().getFullCellId() << 20) + (pos.xCoord().getFullCellId() << 8) + topology;
1433 }
1434
1435 inline
1436 CTopology::TTopologyId::TTopologyId(uint32 id)
1437 {
1438         _value = id;
1439 }
1440
1441 inline
1442 bool CTopology::TTopologyId::haveSameCellPos(TTopologyId const& other) const
1443 {
1444         return ((other._value^_value)&0x0ffffff00)==0;
1445 }
1446
1447 inline
1448 CMapPosition CTopology::TTopologyId::getMapPosition() const
1449 {
1450         return CMapPosition((_value&0x000fff00) >> (8-4),(_value&0xfff00000) >> (20-4));
1451 }
1452
1453 inline
1454 uint CTopology::TTopologyId::getTopologyIndex() const
1455 {
1456         return _value&0x000000ff;
1457 }
1458
1459 inline
1460 bool CTopology::TTopologyId::isValid() const
1461 {
1462         return _value!=UNDEFINED_TOPOLOGY;
1463 }
1464
1465 inline
1466 bool CTopology::TTopologyId::operator <(TTopologyId const& other) const
1467 {
1468         return _value<other._value;
1469 }
1470
1471 inline
1472 bool CTopology::TTopologyId::operator ==(TTopologyId const& other) const
1473 {
1474         return _value==other._value;
1475 }
1476
1477 inline
1478 bool CTopology::TTopologyId::operator !=(TTopologyId const& other) const
1479 {
1480         return _value!=other._value;
1481 }
1482
1483 inline
1484 void CTopology::TTopologyId::serial(NLMISC::IStream& f)
1485 {
1486         f.serial(_value);
1487 }
1488
1489 inline
1490 uint32 CTopology::TTopologyId::getVal() const
1491 {
1492         return _value;
1493 }
1494
1495 inline
1496 CTopology::TTopologyRef::TTopologyRef()
1497 : TTopologyId()
1498 , _RootCell(NULL)
1499 {
1500 }
1501
1502 inline
1503 CTopology::TTopologyRef::TTopologyRef(TTopologyId const& id, CRootCell* rootCell)
1504 : TTopologyId(id)
1505 {
1506         setRootCell(rootCell);
1507 }
1508
1509 inline
1510 void CTopology::TTopologyRef::setRootCell(CRootCell* rootCell)
1511 {
1512         _RootCell = rootCell;
1513 }
1514
1515 inline
1516 void CTopology::TTopologyRef::serial(NLMISC::IStream& f)
1517 {
1518         TTopologyId::serial(f);
1519 }
1520
1521 inline
1522 CRootCell const* CTopology::TTopologyRef::getRootCell() const
1523 {
1524         return _RootCell;
1525 }
1526
1527 inline
1528 CTopology::CNeighbourLink::CNeighbourLink()
1529 : _Ref()
1530 {
1531 }
1532
1533 inline
1534 CTopology::CNeighbourLink::CNeighbourLink(TTopologyRef const& ref, float distance)
1535 : _Ref(ref)
1536 , _Distance(distance)
1537 {
1538 }
1539
1540 inline
1541 CTopology::CNeighbourLink::CNeighbourLink(CNeighbourLink const& other)
1542 : _Ref(other._Ref)
1543 ,       _Distance(other._Distance)
1544 {
1545 }
1546
1547 inline
1548 void CTopology::CNeighbourLink::serial(NLMISC::IStream& f)
1549 {
1550         f.serial(_Ref, _Distance);
1551 }
1552
1553 inline
1554 CTopology::TTopologyRef const& CTopology::CNeighbourLink::getTopologyRef() const
1555 {
1556         return _Ref;
1557 }
1558
1559 inline
1560 float CTopology::CNeighbourLink::getDistance() const
1561 {
1562         return _Distance;
1563 }
1564
1565 inline
1566 void CTopology::updateTopologyRef(CWorldMap* worldMapPtr)
1567 {
1568         std::vector<CNeighbourLink>::iterator it=Neighbours.begin(), itEnd=Neighbours.end();
1569         while (it!=itEnd)
1570         {
1571                 (*it).updateTopologyRef(worldMapPtr);
1572                 ++it;
1573         }
1574 }
1575
1576 inline
1577 uint32 CTopology::getMasterTopo(TAStarFlag const& flags) const
1578 {
1579         switch (flags&WaterAndNogo)
1580         {
1581         case Nothing:
1582         default:
1583                 return MasterTopL;
1584         case Water:
1585                 return MasterTopLW;
1586         case NoGo:
1587                 return MasterTopLN;
1588         case WaterAndNogo:
1589                 return MasterTopLNW;
1590         }
1591 }
1592
1593 inline
1594 uint32 CTopology::getMasterTopo(bool allowWater, bool allowNoGo) const
1595 {
1596         if (allowWater)
1597         {
1598                 if (allowNoGo)
1599                         return MasterTopLNW;
1600                 return MasterTopLW;
1601         }
1602         if (allowNoGo)
1603                 return MasterTopLN;
1604         return MasterTopL;
1605 }
1606
1607 inline
1608 uint32& CTopology::getMasterTopoRef(bool allowWater, bool allowNoGo)
1609 {
1610         if (allowWater)
1611         {
1612                 if (allowNoGo)
1613                         return MasterTopLNW;
1614                 return MasterTopLW;
1615         }
1616         if (allowNoGo)
1617                 return MasterTopLN;
1618         return MasterTopL;
1619 }
1620
1621 inline
1622 bool CTopology::isCompatible(bool allowWater, bool allowNoGo) const
1623 {
1624         return (allowWater || !isInWater()) && (allowNoGo || !isInNogo());
1625 }
1626
1627 inline
1628 CTopology::CTopology()
1629 : Id()
1630 , DirectionMap(NULL)
1631 , Flags(Nothing)
1632 , MasterTopL(TTopologyId::UNDEFINED_TOPOLOGY)
1633 , MasterTopLW(TTopologyId::UNDEFINED_TOPOLOGY)
1634 , MasterTopLN(TTopologyId::UNDEFINED_TOPOLOGY)
1635 , MasterTopLNW(TTopologyId::UNDEFINED_TOPOLOGY)
1636 {
1637 }
1638
1639 // convert a 2 characters string to uint16
1640 #ifdef NL_LITTLE_ENDIAN
1641 #       define NELID16(x) (uint16((x[0] << 8) | (x[1])))
1642 #else
1643 #       define NELID16(x) (uint16((x[1] << 8) | (x[0])))
1644 #endif
1645
1646
1647
1648 inline
1649 void CTopology::serial(NLMISC::IStream& f)
1650 {
1651
1652         uint version = 0;
1653
1654         uint16  check = NELID16("Tp");
1655         f.serial(check);
1656
1657         if (check != NELID16("TP"))
1658         {
1659                 nlassert(check == NELID16("Tp"));
1660                 version = f.serialVersion(3);
1661         }
1662
1663         f.serial(Id);
1664
1665         if (f.isReading())
1666         {
1667                 delete DirectionMap;
1668                 DirectionMap = NULL;
1669         }
1670
1671         bool    present = (DirectionMap != NULL);
1672         f.serial(present);
1673
1674         if (present)
1675         {
1676                 if (f.isReading())
1677                         DirectionMap = new CDirectionMap();
1678
1679                 nlassert(DirectionMap);
1680                 f.serial(*DirectionMap);
1681         }
1682
1683         f.serialCont(Neighbours);
1684
1685         f.serial(Position);
1686
1687         if (version >= 3)
1688         {
1689                 f.serial(Flags);
1690
1691                 f.serial(MasterTopL);
1692                 f.serial(MasterTopLW);
1693                 f.serial(MasterTopLN);
1694                 f.serial(MasterTopLNW);
1695         }
1696         else
1697         {
1698                 nlassert(f.isReading());
1699
1700                 Flags = Nothing;
1701
1702                 if (version >= 1)
1703                 {
1704                         bool    interior;
1705                         f.serial(interior);
1706                         if      (interior)
1707                                 Flags |= Interior;
1708                 }
1709
1710                 if (version >= 2)
1711                 {
1712                         bool    water;
1713                         f.serial(water);
1714                         if      (water)
1715                                 Flags |= Water;
1716                 }
1717
1718                 MasterTopL = 0;
1719                 MasterTopLW = 0;
1720                 MasterTopLN = 0;
1721                 MasterTopLNW = 0;
1722         }
1723 }
1724
1725 //////////////////////////////////////////////////////////////////////////////
1726
1727 /**
1728  * CWorldPosition, position referenced by a map position and a slot
1729  * \author Benjamin Legros
1730  * \author Nevrax France
1731  * \date 2003
1732  */
1733 class CWorldPosition
1734 : public CMapPosition
1735 , public CSlot
1736 {
1737         friend class CWorldMap;
1738         friend class RYPACSCRUNCH::CPacsCruncher;
1739 public:
1740         explicit CWorldPosition();
1741         explicit CWorldPosition(sint x, sint y);
1742
1743         // resumes that the RootCell is valid;
1744         CRootCell const* getRootCell() const { return _RootCell; }
1745
1746         /// In millimeters.
1747         sint32 getMetricHeight() const;
1748         sint32 h() const { return getMetricHeight(); }
1749
1750         CCellLinkage const& getCellLinkage() const { return _cellLinkage; }
1751
1752         CTopology::TTopologyRef getTopologyRef() const;
1753
1754         bool isInInterior() const;
1755
1756         CTopology const& getTopologyNode() const;
1757
1758         TAStarFlag getFlags() const;
1759
1760         /// Get a vector position from a world position
1761         NLMISC::CVectorD getPosition() const;
1762
1763         bool operator ==(CWorldPosition const& cc) const { return CSlot::operator ==(cc) && CMapPosition::operator ==(cc); }
1764         bool operator !=(CWorldPosition const& cc) const { return CSlot::operator !=(cc) || CMapPosition::operator !=(cc); }
1765
1766 private:
1767         CWorldPosition getPosS() const;
1768         CWorldPosition getPosN() const;
1769         CWorldPosition getPosE() const;
1770         CWorldPosition getPosW() const;
1771
1772         void setPosS(CWorldPosition& pos) const;
1773         void setPosN(CWorldPosition& pos) const;
1774         void setPosE(CWorldPosition& pos) const;
1775         void setPosW(CWorldPosition& pos) const;
1776
1777         bool moveS();
1778         bool moveN();
1779         bool moveE();
1780         bool moveW();
1781
1782         void stepS();
1783         void stepN();
1784         void stepE();
1785         void stepW();
1786
1787         CRootCell const* _RootCell;
1788         CCellLinkage _cellLinkage;
1789
1790         explicit CWorldPosition(CRootCell const* cell, CMapPosition const& pos, CSlot const& slot);
1791         explicit CWorldPosition(CRootCell const* cell, CMapPosition const& pos, CSlot const& slot, bool generationOnly);
1792 };
1793
1794 inline
1795 CWorldPosition::CWorldPosition()
1796 : CMapPosition()
1797 , CSlot()
1798 , _RootCell(NULL)
1799 , _cellLinkage(0)
1800 {
1801 }
1802
1803 inline
1804 CWorldPosition::CWorldPosition(sint x, sint y)
1805 : CMapPosition(x, y)
1806 , CSlot()
1807 , _RootCell(NULL)
1808 , _cellLinkage(0)
1809 {
1810 }
1811
1812 inline
1813 CTopology::TTopologyRef CWorldPosition::getTopologyRef() const
1814 {
1815         return CTopology::TTopologyRef(*this, getRootCell());
1816 }
1817
1818 inline
1819 bool CWorldPosition::isInInterior() const
1820 {
1821         return getTopologyRef().getCstTopologyNode().isInInterior();
1822 }
1823
1824 inline
1825 CTopology const& CWorldPosition::getTopologyNode() const
1826 {
1827         return getTopologyRef().getCstTopologyNode();
1828 }
1829
1830 inline
1831 TAStarFlag CWorldPosition::getFlags() const
1832 {
1833         return getTopologyRef().getCstTopologyNode().getFlags();        //Flags;
1834 }
1835
1836 //////////////////////////////////////////////////////////////////////////////
1837
1838 class CCompatibleResult
1839 {
1840 public:
1841         CCompatibleResult(TAStarFlag movementFlags = Interior, uint32 choosenMasterTopo = ~0);
1842         void set(TAStarFlag movementFlags, uint32 choosenMasterTopo);
1843         void setValid(bool valid = true);
1844         TAStarFlag const& movementFlags() const;
1845         uint32 const& choosenMasterTopo() const;
1846         bool const& isValid() const;
1847
1848 private:
1849         TAStarFlag _MovementFlags;
1850         uint32 _ChoosenMasterTopo;
1851         bool _Valid;
1852 };
1853
1854 inline
1855 CCompatibleResult::CCompatibleResult(TAStarFlag movementFlags, uint32 choosenMasterTopo)
1856 : _MovementFlags(movementFlags)
1857 , _ChoosenMasterTopo(choosenMasterTopo)
1858 , _Valid(false)
1859 {
1860 }
1861
1862 inline
1863 void CCompatibleResult::set(TAStarFlag movementFlags, uint32 choosenMasterTopo)
1864 {
1865         _MovementFlags = movementFlags;
1866         _ChoosenMasterTopo = choosenMasterTopo;
1867 }
1868
1869 inline
1870 void CCompatibleResult::setValid(bool valid)
1871 {
1872         _Valid = valid;
1873 }
1874
1875 inline
1876 TAStarFlag const& CCompatibleResult::movementFlags() const
1877 {
1878         return _MovementFlags;
1879 }
1880
1881 inline
1882 uint32 const& CCompatibleResult::choosenMasterTopo() const
1883 {
1884         return _ChoosenMasterTopo;
1885 }
1886
1887 inline
1888 bool const& CCompatibleResult::isValid() const
1889 {
1890         return _Valid;
1891 }
1892
1893 //////////////////////////////////////////////////////////////////////////////
1894
1895 /**
1896 @relates CWorldPosition
1897 */
1898 void areCompatiblesWithoutStartRestriction(CWorldPosition const& startPos, CWorldPosition const& endPos, TAStarFlag const& denyflags, CCompatibleResult& res, bool allowStartRestriction = false);
1899
1900 //////////////////////////////////////////////////////////////////////////////
1901
1902 /**
1903  * CRootCell, interface for all 16x16 cells in world map
1904  * derivated into CComputeCell (for map computation only), into CSingleLayerCell and CMultiLayerCell
1905  * \author Benjamin Legros
1906  * \author Nevrax France
1907  * \date 2003
1908  */
1909 class CRootCell
1910 {
1911 public:
1912         enum TCellType
1913         {
1914                 Root = 0,
1915                 Compute,
1916                 White,
1917                 SingleLayer,
1918                 MultiLayer
1919         };
1920
1921 public:
1922         CRootCell(CWorldMap const& worldMapPtr);
1923
1924         virtual ~CRootCell() { }
1925
1926         void setFlag(uint32 const flag) { _flag = flag; }
1927         uint32 getFlag() const { return _flag; }
1928
1929         sint32 getMetricHeight(CWorldPosition const& wpos) const;
1930
1931         CWorldMap const& getWorldMapPtr() const { return _WorldMapPtr; }
1932
1933         // mutator (only for build purpose)
1934         CTopology& getTopologyNode(uint topology);
1935         CTopology const& getCstTopologyNode(uint topology) const;
1936
1937         CTopology::TTopologyId getTopologyId(CWorldPosition const& wpos) const;
1938
1939         CTopology::TTopologyRef getTopologyRef(const CWorldPosition&pos) const;
1940
1941         CTopology const& getCstTopologyNode(CTopology::TTopologyId const& id) const;
1942
1943         std::vector<CTopology>& getTopologiesNodes() { return _TopologiesNodes; }
1944         std::vector<CTopology> const& getTopologiesNodes() const { return _TopologiesNodes; }
1945         void setTopologiesNodes(std::vector<CTopology> const& nodes) { _TopologiesNodes = nodes; }
1946
1947         CDirectionMap const* getDirectionMap(uint topology) const;
1948         void setDirectionMap(CDirectionMap* map, uint topology);
1949
1950         void updateTopologyRef(CWorldMap* worldMap);
1951
1952         CWorldPosition const& getWorldPosition(uint ind) const;
1953
1954         void setWorldPosition(CWorldPosition const& pos, uint ind);
1955
1956         virtual CCellLinkage getCellLink(CWorldPosition const& wpos) const = 0;
1957
1958         virtual uint32 nbUsedSlots(CMapPosition const& pos) const = 0;
1959         virtual sint32 maxUsedSlot(CMapPosition const& pos) const = 0;
1960         virtual bool isSlotUsed(CMapPosition const& pos, CSlot const& slot) const = 0;
1961
1962         virtual uint getTopology(CWorldPosition const& wpos) const = 0;
1963
1964         virtual sint getHeight(CWorldPosition const& wpos) const = 0;
1965
1966         // clear height map
1967         virtual void clearHeightMap() = 0;
1968
1969         // serial
1970         virtual void serial(NLMISC::IStream& f) = 0;
1971
1972         // load a cell
1973         static CRootCell* load(NLMISC::IStream& f, CWorldMap const& worldMap);
1974
1975         // save a cell
1976         static void save(NLMISC::IStream& f, CRootCell* cell);
1977
1978 private:
1979         CWorldMap const& _WorldMapPtr;  //      his owner map;
1980         std::vector<CTopology> _TopologiesNodes;
1981         CWorldPosition _WorldPosition[4]; // 4 random positions for each slots.
1982         uint32 _flag;
1983 };
1984
1985 inline
1986 CRootCell::CRootCell(CWorldMap const& worldMapPtr)
1987 : _WorldMapPtr(worldMapPtr)
1988 {
1989         _flag = 0;
1990 }
1991
1992 inline
1993 sint32 CRootCell::getMetricHeight(CWorldPosition const& wpos) const
1994 {
1995         // check if wpos valid
1996         if (!wpos.isValid())
1997                 return 0;
1998
1999         sint32 const z = (getHeight(wpos)*2000 - 1000)&(~3);
2000         uint const top = getTopology(wpos);
2001         if (top<_TopologiesNodes.size() && _TopologiesNodes[top].isInInterior())
2002                 return z+2;
2003         return z;
2004 }
2005
2006 inline
2007 CTopology& CRootCell::getTopologyNode(uint topology)
2008 {
2009         if (topology >= _TopologiesNodes.size())
2010                 _TopologiesNodes.resize(topology+1);
2011
2012         return _TopologiesNodes[topology];
2013 }
2014
2015 inline
2016 CTopology const& CRootCell::getCstTopologyNode(uint topology) const
2017 {
2018 #if !FINAL_VERSION
2019         nlassert(topology < _TopologiesNodes.size());
2020 #endif
2021         return _TopologiesNodes[topology];
2022 }
2023
2024 inline
2025 CTopology::TTopologyId CRootCell::getTopologyId(CWorldPosition const& wpos) const
2026 {
2027         return CTopology::TTopologyId(wpos, getTopology(wpos));
2028 }
2029
2030 inline
2031 CTopology::TTopologyRef CRootCell::getTopologyRef(const CWorldPosition&pos) const
2032 {
2033 #ifdef NL_DEBUG
2034         nlassert(pos.getRootCell()!=this);
2035 #endif
2036         return  CTopology::TTopologyRef(pos);
2037 }
2038
2039 inline
2040 CTopology const& CRootCell::getCstTopologyNode(CTopology::TTopologyId const& id) const
2041 {
2042         return getCstTopologyNode(id.getTopologyIndex());
2043 }
2044
2045 inline
2046 CDirectionMap const* CRootCell::getDirectionMap(uint topology) const
2047 {
2048         return (topology<_TopologiesNodes.size()) ? getCstTopologyNode(topology).DirectionMap : NULL;
2049 }
2050
2051 inline
2052 void CRootCell::setDirectionMap(CDirectionMap* map, uint topology)
2053 {
2054         getTopologyNode(topology).DirectionMap = map;
2055 }
2056
2057 inline
2058 void CRootCell::updateTopologyRef(CWorldMap* worldMap)
2059 {
2060         std::vector<CTopology>::iterator it=_TopologiesNodes.begin(), itEnd=_TopologiesNodes.end();
2061         while (it!=itEnd)
2062         {
2063                 (*it).updateTopologyRef(worldMap);
2064                 ++it;
2065         }
2066 }
2067
2068 inline
2069 CWorldPosition const& CRootCell::getWorldPosition(uint ind) const
2070 {
2071 #ifdef NL_DEBUG
2072         nlassert(ind<4);
2073 #endif
2074         return _WorldPosition[ind];
2075 }
2076
2077 inline
2078 void CRootCell::setWorldPosition(CWorldPosition const& pos, uint ind)
2079 {
2080 #ifdef NL_DEBUG
2081         nlassert(ind<4);
2082 #endif
2083         _WorldPosition[ind]     = pos;
2084 }
2085
2086 //////////////////////////////////////////////////////////////////////////////
2087
2088 /**
2089  * A computed 16x16 cell
2090  * \author Benjamin Legros
2091  * \author Nevrax France
2092  * \date 2003
2093  */
2094 class CComputeCell
2095 : public CRootCell
2096 {
2097 public:
2098         CComputeCell(CWorldMap const& worldMapPtr);
2099
2100         CCellLinkage getCellLink(CWorldPosition const& wpos) const;
2101
2102         uint32 nbUsedSlots(CMapPosition const& pos) const;
2103
2104         sint32 maxUsedSlot(CMapPosition const& pos) const;
2105
2106         bool isSlotUsed(CMapPosition const& pos, CSlot const& slot) const;
2107
2108         uint getTopology(CWorldPosition const& wpos) const;
2109
2110         sint getHeight(CWorldPosition const& wpos) const;
2111
2112         TCellUnit const& getCellUnitCst(CMapPosition const& pos) const;
2113
2114         CUnitSlot const& getUnitSlotCst(CWorldPosition const& wpos) const;
2115
2116         TCellUnit& getCellUnit(CMapPosition const& pos);
2117
2118         CUnitSlot& getUnitSlot(CWorldPosition const& wpos);
2119
2120         void serial(NLMISC::IStream& f);
2121
2122         void clearHeightMap() { }
2123
2124 private:
2125         TCellUnit const& getCellUnitCst(CWorldPosition const& wpos) const;
2126
2127         // a cell is a grid of 16x16 units
2128         TCellUnit _Grid[16*16];
2129 };
2130
2131 inline
2132 CComputeCell::CComputeCell(CWorldMap const& worldMapPtr)
2133 : CRootCell(worldMapPtr)
2134 {
2135 }
2136
2137 inline
2138 CCellLinkage CComputeCell::getCellLink(CWorldPosition const& wpos) const
2139 {
2140         return getUnitSlotCst(wpos).getCellLink();
2141 }
2142
2143 inline
2144 uint32 CComputeCell::nbUsedSlots(CMapPosition const& pos) const
2145 {
2146         TCellUnit const& cellUnit = getCellUnitCst(pos);
2147         uint32 count = 0;
2148         for (uint slot=0; slot<3; ++slot)
2149                 if (cellUnit[slot].getCellLink().used())
2150                         ++count;
2151         return count;
2152 }
2153
2154 inline
2155 sint32 CComputeCell::maxUsedSlot(CMapPosition const& pos) const
2156 {
2157         TCellUnit const& cellUnit = getCellUnitCst(pos);
2158         sint32 maxs = -1;
2159         for (uint slot=0; slot<3; ++slot)
2160                 if (cellUnit[slot].getCellLink().used())
2161                         maxs = slot;
2162         return maxs;
2163 }
2164
2165 inline
2166 bool CComputeCell::isSlotUsed(CMapPosition const& pos, CSlot const& slot) const
2167 {
2168         TCellUnit const& cellUnit = getCellUnitCst(pos);
2169         return slot.isValid() ? cellUnit[slot.slot()].getCellLink().used() : false;
2170 }
2171
2172 inline
2173 uint CComputeCell::getTopology(CWorldPosition const& wpos) const
2174 {
2175         return getUnitSlotCst(wpos).topology();
2176 }
2177
2178 inline
2179 sint CComputeCell::getHeight(CWorldPosition const& wpos) const
2180 {
2181         return getUnitSlotCst(wpos).height();
2182 }
2183
2184 inline
2185 TCellUnit const& CComputeCell::getCellUnitCst(CMapPosition const& pos) const
2186 {
2187         return _Grid[pos.cellUnitFastIndex()];
2188 }
2189
2190 inline
2191 CUnitSlot const& CComputeCell::getUnitSlotCst(CWorldPosition const& wpos) const
2192 {
2193 #ifdef NL_DEBUG
2194         nlassert(wpos.isValid());
2195 #endif
2196         return getCellUnitCst(wpos)[wpos.slot()];
2197 }
2198
2199 inline
2200 TCellUnit& CComputeCell::getCellUnit(CMapPosition const& pos)
2201 {
2202         return _Grid[pos.cellUnitFastIndex()];
2203 }
2204
2205 inline
2206 CUnitSlot& CComputeCell::getUnitSlot(CWorldPosition const& wpos)
2207 {
2208 #ifdef NL_DEBUG
2209         nlassert(wpos.isValid());
2210 #endif
2211         return getCellUnit(wpos)[wpos.slot()];
2212 }
2213
2214 inline
2215 TCellUnit const& CComputeCell::getCellUnitCst(CWorldPosition const& wpos) const
2216 {
2217         return _Grid[wpos.cellUnitFastIndex()];
2218         }
2219
2220 //////////////////////////////////////////////////////////////////////////////
2221
2222 /**
2223  * A Single layer 16x16 cell that has not walk constraint (map is completely white)
2224  * \author Benjamin Legros
2225  * \author Nevrax France
2226  * \date 2003
2227  */
2228 class CWhiteCell
2229 : public CRootCell
2230 {
2231 public:
2232         CWhiteCell(CWorldMap const& worldMapPtr);
2233
2234         CCellLinkage getCellLink(CWorldPosition const& wpos) const;
2235
2236         uint32 nbUsedSlots(CMapPosition const& pos) const;
2237
2238         sint32 maxUsedSlot(CMapPosition const& pos) const;
2239
2240         bool isSlotUsed(CMapPosition const& pos, CSlot const& slot) const;
2241
2242         uint getTopology(CWorldPosition const& wpos) const;
2243
2244         sint getHeight(CWorldPosition const& wpos) const;
2245
2246         void serial(NLMISC::IStream& f);
2247
2248         void clearHeightMap();
2249
2250         void setHeightMap(I16x16Layer* heightMap);
2251
2252 private:
2253         I16x16Layer* _HeightMap;
2254 };
2255
2256 inline
2257 CWhiteCell::CWhiteCell(CWorldMap const& worldMapPtr)
2258 : CRootCell(worldMapPtr), _HeightMap(NULL)
2259 {
2260 }
2261
2262 inline
2263 CCellLinkage CWhiteCell::getCellLink(CWorldPosition const& wpos) const
2264 {
2265         return CCellLinkage(0);
2266 }
2267
2268 inline
2269 uint32 CWhiteCell::nbUsedSlots(CMapPosition const& pos) const
2270 {
2271         return 1;
2272 }
2273
2274 inline
2275 sint32 CWhiteCell::maxUsedSlot(CMapPosition const& pos) const
2276 {
2277         return 0;
2278 }
2279
2280 inline
2281 bool CWhiteCell::isSlotUsed(CMapPosition const& pos, CSlot const& slot) const
2282 {
2283         return slot.slot() == 0;
2284 }
2285
2286 inline
2287 uint CWhiteCell::getTopology(CWorldPosition const& wpos) const
2288 {
2289         return 0;
2290 }
2291
2292 inline
2293 sint CWhiteCell::getHeight(CWorldPosition const& wpos) const
2294 {
2295         return (_HeightMap != NULL) ? _HeightMap->get(wpos.yCoord().getUnitId(), wpos.xCoord().getUnitId()) : 0;
2296 }
2297
2298 inline
2299 void CWhiteCell::serial(NLMISC::IStream& f)
2300 {
2301         f.serialCheck(NELID16("WC"));
2302         if (f.isReading())
2303                 _HeightMap = I16x16Layer::load(f);
2304         else
2305                 I16x16Layer::save(f, _HeightMap);
2306 }
2307
2308 inline
2309 void CWhiteCell::clearHeightMap()
2310 {
2311         if (_HeightMap)
2312                 delete _HeightMap;
2313         _HeightMap = NULL;
2314 }
2315
2316 inline
2317 void CWhiteCell::setHeightMap(I16x16Layer* heightMap)
2318 {
2319         _HeightMap = heightMap;
2320 }
2321
2322 //////////////////////////////////////////////////////////////////////////////
2323
2324 /**
2325  * A Single layer 16x16 cell
2326  * \author Benjamin Legros
2327  * \author Nevrax France
2328  * \date 2003
2329  */
2330 class CSingleLayerCell
2331 : public CRootCell
2332 {
2333 protected:
2334         bool testPos(uint i, uint j) const { return (_Map[i] & _MaskMap[j]) != 0; }
2335         void setPos(uint i, uint j, bool p)     { _Map[i] = (p ? (_Map[i] | _MaskMap[j]) : (_Map[i] & (~_MaskMap[j]))); }
2336
2337 public:
2338         CSingleLayerCell(CWorldMap const& worldMapPtr);
2339
2340         CCellLinkage getCellLink(CWorldPosition const& wpos) const;
2341
2342         uint32 nbUsedSlots(CMapPosition const& pos) const;
2343
2344         sint32 maxUsedSlot(CMapPosition const& pos) const;
2345
2346         bool isSlotUsed(CMapPosition const& pos, CSlot const& slot) const;
2347
2348         uint getTopology(CWorldPosition const& wpos) const;
2349
2350         sint getHeight(CWorldPosition const& wpos) const;
2351
2352         bool testPos(CMapPosition const& pos) const;
2353
2354         void setPos(CMapPosition const& pos, bool p);
2355
2356         void setSLink(uint i, bool p) { _SLinks = p ? (_SLinks | _MaskMap[i]) : (_SLinks & (~_MaskMap[i])); }
2357         void setNLink(uint i, bool p) { _NLinks = p ? (_NLinks | _MaskMap[i]) : (_NLinks & (~_MaskMap[i])); }
2358         void setELink(uint i, bool p) { _ELinks = p ? (_ELinks | _MaskMap[i]) : (_ELinks & (~_MaskMap[i])); }
2359         void setWLink(uint i, bool p) { _WLinks = p ? (_WLinks | _MaskMap[i]) : (_WLinks & (~_MaskMap[i])); }
2360
2361         void setTopologies(I16x16Layer* topology);
2362
2363         void setHeightMap(I16x16Layer* heightMap);
2364
2365         virtual void serial(NLMISC::IStream& f);
2366
2367         void clearHeightMap();
2368
2369 private:
2370         /// The map of accessible positions
2371         uint16 _Map[16];
2372         /// The north links, true if north position is accessible
2373         uint16 _SLinks;
2374         uint16 _NLinks;
2375         uint16 _ELinks;
2376         uint16 _WLinks;
2377
2378         // topology layer
2379         I16x16Layer* _Topologies;
2380
2381         // height map
2382         I16x16Layer* _HeightMap;
2383
2384         static uint16 _MaskMap[16];
2385         static bool _Initialized;
2386 };
2387
2388 inline
2389 CSingleLayerCell::CSingleLayerCell(CWorldMap const& worldMapPtr)
2390 : CRootCell(worldMapPtr)
2391 {
2392         for (uint i=0; i<16; ++i)
2393                 _Map[i] = 0;
2394
2395         _SLinks = 0;
2396         _NLinks = 0;
2397         _ELinks = 0;
2398         _WLinks = 0;
2399         _Topologies = NULL;
2400         _HeightMap = NULL;
2401
2402         if (!_Initialized)
2403         {
2404                 for (uint i=0; i<16; ++i)
2405                         _MaskMap[i] = (1 << (15-i));
2406                 _Initialized = true;
2407         }
2408 }
2409
2410 inline
2411 CCellLinkage CSingleLayerCell::getCellLink(CWorldPosition const& wpos) const
2412 {
2413         uint xi = wpos.xCoord().getUnitId();
2414         uint yi = wpos.yCoord().getUnitId();
2415
2416         CCellLinkage l(0);
2417
2418         l |= ((xi > 0  && testPos(yi, xi-1)) || (xi == 0  && (_WLinks&_MaskMap[yi]))) ? 0 : CCellLinkage::WestSlotMask;
2419         l |= ((xi < 15 && testPos(yi, xi+1)) || (xi == 15 && (_ELinks&_MaskMap[yi]))) ? 0 : CCellLinkage::EastSlotMask;
2420         l |= ((yi > 0  && testPos(yi-1, xi)) || (yi == 0  && (_SLinks&_MaskMap[xi]))) ? 0 : CCellLinkage::SouthSlotMask;
2421         l |= ((yi < 15 && testPos(yi+1, xi)) || (yi == 15 && (_NLinks&_MaskMap[xi]))) ? 0 : CCellLinkage::NorthSlotMask;
2422
2423         return l;
2424 }
2425
2426 inline
2427 uint32 CSingleLayerCell::nbUsedSlots(CMapPosition const& pos) const
2428 {
2429         return testPos(pos) ? 1 : 0;
2430 }
2431
2432 inline
2433 sint32 CSingleLayerCell::maxUsedSlot(CMapPosition const& pos) const
2434 {
2435         return testPos(pos) ? 0 : -1;
2436 }
2437
2438 inline
2439 bool CSingleLayerCell::isSlotUsed(CMapPosition const& pos, CSlot const& slot) const
2440 {
2441         return slot.slot() == 0 && testPos(pos);
2442 }
2443
2444 inline
2445 uint CSingleLayerCell::getTopology(CWorldPosition const& wpos) const
2446 {
2447         return (_Topologies != NULL) ? _Topologies->get(wpos.yCoord().getUnitId(), wpos.xCoord().getUnitId()) : 0;
2448 }
2449
2450 inline
2451 sint CSingleLayerCell::getHeight(CWorldPosition const& wpos) const
2452 {
2453         return (_HeightMap != NULL) ? _HeightMap->get(wpos.yCoord().getUnitId(), wpos.xCoord().getUnitId()) : 0;
2454 }
2455
2456 inline
2457 bool CSingleLayerCell::testPos(CMapPosition const& pos) const
2458 {
2459         return testPos(pos.yCoord().getUnitId(), pos.xCoord().getUnitId());
2460 }
2461
2462 inline
2463 void CSingleLayerCell::setPos(CMapPosition const& pos, bool p)
2464 {
2465         setPos(pos.yCoord().getUnitId(), pos.xCoord().getUnitId(), p);
2466 }
2467
2468 inline
2469 void CSingleLayerCell::setTopologies(I16x16Layer* topology)
2470 {
2471         delete _Topologies;
2472         _Topologies = topology;
2473 }
2474
2475 inline
2476 void CSingleLayerCell::setHeightMap(I16x16Layer* heightMap)
2477 {
2478         if (_HeightMap)
2479                 delete _HeightMap;
2480         _HeightMap = heightMap;
2481 }
2482
2483 inline
2484 void CSingleLayerCell::clearHeightMap()
2485 {
2486         delete _HeightMap;
2487         _HeightMap = NULL;
2488 }
2489
2490 //////////////////////////////////////////////////////////////////////////////
2491
2492 /**
2493  * A Multiple layer 16x16 cell (maximum 3 layers)
2494  * \author Benjamin Legros
2495  * \author Nevrax France
2496  * \date 2003
2497  */
2498 class CMultiLayerCell
2499 : public CRootCell
2500 {
2501 protected:
2502         class CCellLayer
2503         {
2504                 friend class CMultiLayerCell; // for build features.
2505         public:
2506                 CCellLinkage const& getCellLinkage(CMapPosition const& pos) const;
2507                 uint8 getTopology(CMapPosition const& pos) const;
2508                 I16x16Layer* getHeightMap() { return _HeightMap; }
2509
2510         private:
2511                 CCellLinkage& cellLinkage(CMapPosition const& pos);
2512
2513         private:
2514                 CCellLinkage _Layer[16*16];
2515                 uint8 _Topology[16*16];
2516                 I16x16Layer* _HeightMap;
2517         };
2518
2519 public:
2520         CMultiLayerCell(CWorldMap const& worldMapPtr);
2521         virtual ~CMultiLayerCell();
2522
2523         CCellLinkage getCellLink(CWorldPosition const& wpos) const;
2524         uint32 nbUsedSlots(CMapPosition const& pos) const;
2525         sint32 maxUsedSlot(CMapPosition const& pos) const;
2526         bool isSlotUsed(CMapPosition const& pos, CSlot const& slot) const;
2527         uint getTopology(CWorldPosition const& wpos) const;
2528         sint getHeight(CWorldPosition const& wpos) const;
2529
2530         virtual void serial(NLMISC::IStream& f);
2531
2532         void setLinks(CWorldPosition const& wpos, CCellLinkage links);
2533         void setTopology(CWorldPosition const& wpos, uint topology);
2534         void setHeightMap(CSlot const& slot, I16x16Layer* heightMap);
2535         void clearHeightMap();
2536
2537 private:
2538         // each layer is allocated in memory
2539         // the 3 layers available
2540         CCellLayer* _Layers[3];
2541 };
2542
2543 inline
2544 CCellLinkage const& CMultiLayerCell::CCellLayer::getCellLinkage(CMapPosition const& pos) const
2545 {
2546         return _Layer[pos.cellUnitFastIndex()]; //yCoord().getUnitId()][pos.xCoord().getUnitId()];
2547 }
2548
2549 inline
2550 uint8 CMultiLayerCell::CCellLayer::getTopology(CMapPosition const& pos) const
2551 {
2552         return _Topology[pos.cellUnitFastIndex()];      //yCoord().getUnitId()][pos.xCoord().getUnitId()];
2553 }
2554
2555 inline
2556 CCellLinkage& CMultiLayerCell::CCellLayer::cellLinkage(CMapPosition const& pos)
2557 {
2558         return _Layer[pos.cellUnitFastIndex()]; //yCoord().getUnitId()][pos.xCoord().getUnitId()];
2559 }
2560
2561 inline
2562 CMultiLayerCell::CMultiLayerCell(CWorldMap const& worldMapPtr)
2563 : CRootCell(worldMapPtr)
2564 {
2565         _Layers[0] = NULL;
2566         _Layers[1] = NULL;
2567         _Layers[2] = NULL;
2568 }
2569
2570 inline
2571 CMultiLayerCell::~CMultiLayerCell()
2572 {
2573         delete [] _Layers[0];
2574         delete [] _Layers[1];
2575         delete [] _Layers[2];
2576 }
2577
2578 inline
2579 CCellLinkage CMultiLayerCell::getCellLink(CWorldPosition const& wpos) const
2580 {
2581 #ifdef NL_DEBUG
2582         nlassert(wpos.isValid());
2583 #endif
2584         CCellLayer*     cellLayerPt=_Layers[wpos.slot()];
2585         return (!cellLayerPt) ? CCellLinkage() : cellLayerPt->getCellLinkage(wpos);
2586 }
2587
2588 inline
2589 uint32 CMultiLayerCell::nbUsedSlots(CMapPosition const& pos) const
2590 {
2591         uint32 ns = 0;
2592         for (uint32     slot=0; slot<3; ++slot)
2593         {
2594                 CCellLayer*     cellLayerPt=_Layers[slot];
2595                 if (cellLayerPt && cellLayerPt->cellLinkage(pos).used())
2596                         ++ns;
2597         }
2598         return  ns;
2599 }
2600
2601 inline
2602 sint32 CMultiLayerCell::maxUsedSlot(CMapPosition const& pos) const
2603 {
2604         sint32 maxs = -1;
2605         for (uint32     slot=0; slot<3; ++slot)
2606         {
2607                 CCellLayer*     cellLayerPt=_Layers[slot];
2608                 if (cellLayerPt && cellLayerPt->cellLinkage(pos).used())
2609                         maxs = slot;
2610         }
2611         return maxs;
2612 }
2613
2614 inline
2615 bool CMultiLayerCell::isSlotUsed(CMapPosition const& pos, CSlot const& slot) const
2616 {
2617         if (!slot.isValid())
2618                 return false;
2619         CCellLayer*     cellLayerPt = _Layers[slot.slot()];
2620         return (cellLayerPt && cellLayerPt->cellLinkage(pos).used());
2621 }
2622
2623 inline
2624 uint CMultiLayerCell::getTopology(CWorldPosition const& wpos) const
2625 {
2626 #ifdef NL_DEBUG
2627         nlassert(wpos.isValid());
2628 #endif
2629         CCellLayer*     cellLayerPt = _Layers[wpos.slot()];
2630         return (!cellLayerPt) ? 0 : cellLayerPt->getTopology(wpos);
2631 }
2632
2633 inline
2634 sint CMultiLayerCell::getHeight(CWorldPosition const& wpos) const
2635 {
2636 #ifdef NL_DEBUG
2637         nlassert(wpos.isValid());
2638 #endif
2639         CCellLayer*     cellLayerPt = _Layers[wpos.slot()];
2640         return (!cellLayerPt || !cellLayerPt->getHeightMap()) ? 0 : cellLayerPt->getHeightMap()->get(wpos.yCoord().getUnitId(), wpos.xCoord().getUnitId());
2641 }
2642
2643 inline
2644 void CMultiLayerCell::setLinks(CWorldPosition const& wpos, CCellLinkage links)
2645 {
2646 #ifdef NL_DEBUG
2647         nlassert(wpos.isValid());
2648 #endif
2649         CCellLayer*     cellLayerPt = _Layers[wpos.slot()];
2650         if (!cellLayerPt)
2651         {
2652                 cellLayerPt = new CCellLayer();
2653                 _Layers[wpos.slot()] = cellLayerPt;
2654
2655                 for (uint i=0; i<16*16; ++i)
2656                         cellLayerPt->_Topology[i] = 0;
2657                 cellLayerPt->_HeightMap = NULL;
2658         }
2659 #ifdef NL_DEBUG
2660         nlassert(cellLayerPt);
2661 #endif
2662         cellLayerPt->cellLinkage(wpos)=links;
2663 }
2664
2665 inline
2666 void CMultiLayerCell::setTopology(CWorldPosition const& wpos, uint topology)
2667 {
2668 #ifdef NL_DEBUG
2669         nlassert(topology < 256);
2670         nlassert(wpos.isValid());
2671 #endif
2672         CCellLayer*     cellLayerPt = _Layers[wpos.slot()];
2673
2674 #ifdef NL_DEBUG
2675         nlassert(cellLayerPt);
2676 #endif
2677         cellLayerPt->_Topology[wpos.cellUnitFastIndex()]=(uint8)topology;
2678 }
2679
2680 inline
2681 void CMultiLayerCell::setHeightMap(CSlot const& slot, I16x16Layer* heightMap)
2682 {
2683 #ifdef NL_DEBUG
2684         nlassert(slot.isValid());
2685 #endif
2686         CCellLayer*     cellLayerPt = _Layers[slot.slot()];
2687
2688 #ifdef NL_DEBUG
2689         nlassert(cellLayerPt);
2690 #endif
2691         if (cellLayerPt->_HeightMap)
2692                 delete cellLayerPt->_HeightMap;
2693         cellLayerPt->_HeightMap = heightMap;
2694 }
2695
2696 inline
2697 void CMultiLayerCell::clearHeightMap()
2698 {
2699         for (CSlot i(0); i.isValid(); ++i)
2700         {
2701                 CCellLayer*     cellLayerPt = _Layers[i.slot()];
2702                 if (cellLayerPt)
2703                 {
2704                         delete cellLayerPt->_HeightMap;
2705                         cellLayerPt->_HeightMap=NULL;
2706                 }
2707         }
2708 }
2709
2710 //////////////////////////////////////////////////////////////////////////////
2711
2712 /**
2713  * A CSuperCell of basically 16x16 CCells
2714  * \author Benjamin Legros
2715  * \author Nevrax France
2716  * \date 2003
2717  */
2718 class CSuperCell
2719 {
2720 public:
2721         CSuperCell(CWorldMap const& worldMap);
2722         virtual ~CSuperCell();
2723
2724         // get a const cell (might be NULL)
2725         CRootCell const* getRootCellCst(CMapPosition const& pos) const;
2726         // get a const cell (might be NULL)
2727         CRootCell* getRootCell(CMapPosition const& pos);
2728
2729         void updateTopologyRef(CWorldMap* worldMap);
2730         void countCells(uint& compute, uint& white, uint& simple, uint& multi, uint& other) const;
2731
2732         // set a cell
2733         void setRootCell(CMapPosition const& pos, CRootCell* cell);
2734
2735         //
2736         // compute cell selectors
2737         //
2738
2739         // get a cell
2740         CComputeCell* getComputeCell(CMapPosition const& pos);
2741         // get a const cell
2742         CComputeCell const* getComputeCell(CMapPosition const& pos) const;
2743
2744         // get a slot in a cell
2745         CUnitSlot getUnitSlot(CWorldPosition const& wpos) const;
2746         // get a slot in super cell
2747         CUnitSlot& getUnitSlot(CWorldPosition const& wpos);
2748         TCellUnit& getCellUnit(CMapPosition const& pos);
2749
2750         void serial(NLMISC::IStream& f);
2751
2752         void markRootCell(uint32 const flag) const;
2753
2754 private:
2755         // a super cell is composed of 16x16 pointers to cells, initially NULL
2756         CRootCell* _Grid[16*16];
2757         CWorldMap const& _WorldMap;
2758 };
2759
2760 inline
2761 CSuperCell::CSuperCell(CWorldMap const& worldMap)
2762 : _WorldMap(worldMap)
2763 {
2764         for (uint i=0;i<16*16;i++)
2765                 _Grid[i] = NULL;
2766 }
2767
2768 inline
2769 CSuperCell::~CSuperCell()
2770 {
2771         for (uint i=0;i<16*16;i++)
2772                 if (_Grid[i])
2773                         delete _Grid[i];
2774 }
2775
2776 inline
2777 CRootCell const* CSuperCell::getRootCellCst(CMapPosition const& pos) const
2778 {
2779         return _Grid[pos.rootCellFastIndex()];
2780 }
2781
2782 inline
2783 CRootCell* CSuperCell::getRootCell(CMapPosition const& pos)
2784 {
2785         return _Grid[pos.rootCellFastIndex()];
2786 }
2787
2788 inline
2789 void CSuperCell::setRootCell(CMapPosition const& pos, CRootCell* cell)
2790 {
2791         CRootCell*& rootCell = _Grid[pos.rootCellFastIndex()];
2792         if (rootCell==cell)
2793                 return;
2794         delete rootCell;
2795         rootCell = cell;
2796 }
2797
2798 inline
2799 CComputeCell* CSuperCell::getComputeCell(CMapPosition const& pos)
2800 {
2801         CRootCell*& rootCell = _Grid[pos.rootCellFastIndex()];
2802         if (!rootCell)
2803                 rootCell = new CComputeCell(_WorldMap);
2804
2805 #ifdef NL_DEBUG
2806         nlassert(rootCell);
2807         nlassert(dynamic_cast<CComputeCell*>(rootCell));
2808 #endif
2809         return static_cast<CComputeCell*>(rootCell);
2810 }
2811
2812 inline
2813 CComputeCell const* CSuperCell::getComputeCell(CMapPosition const& pos) const
2814 {
2815         CRootCell const* const& rootCell = _Grid[pos.rootCellFastIndex()];
2816         if (!rootCell)
2817                 return NULL;
2818 #ifdef NL_DEBUG
2819         nlassert(dynamic_cast<CComputeCell const*>(rootCell));
2820 #endif
2821         return static_cast<CComputeCell const*>(rootCell);
2822 }
2823
2824 inline
2825 CUnitSlot CSuperCell::getUnitSlot(CWorldPosition const& wpos) const
2826 {
2827         CComputeCell const* cell = getComputeCell(wpos);
2828         return !cell ? CUnitSlot() : cell->getUnitSlotCst(wpos);
2829 }
2830
2831 inline
2832 CUnitSlot& CSuperCell::getUnitSlot(CWorldPosition const& wpos)
2833 {
2834         CComputeCell* cell = getComputeCell(wpos);
2835         return cell->getUnitSlot(wpos);
2836 }
2837
2838 inline
2839 TCellUnit& CSuperCell::getCellUnit(CMapPosition const& pos)
2840 {
2841         CComputeCell* cell = getComputeCell(pos);
2842         return cell->getCellUnit(pos);
2843 }
2844
2845 inline
2846 void CSuperCell::markRootCell(uint32 const flag) const
2847 {
2848         for     (uint32 i=0; i<256; ++i)
2849         {
2850                 if (_Grid[i])
2851                         _Grid[i]->setFlag(flag);
2852         }
2853 }
2854
2855 //////////////////////////////////////////////////////////////////////////////
2856
2857 /**
2858  * The A* Path structure, computed by the WorldMap
2859  * \author Benjamin Legros
2860  * \author Nevrax France
2861  * \date 2003
2862  */
2863 class CAStarPath
2864 {
2865         friend class CWorldMap;
2866 public:
2867         std::vector<CTopology::TTopologyRef> const& topologiesPath() const { return _TopologiesPath; }
2868         std::vector<CTopology::TTopologyRef>& topologiesPathForCalc() { return _TopologiesPath; }
2869
2870         CWorldPosition const& getStartPos() const { return _Start; }
2871         void setStartPos(CWorldPosition const& pos) { _Start = pos; }
2872
2873         CWorldPosition const& getEndPos() const { return _End; }
2874         void setEndPos(CWorldPosition const& pos) { _End = pos; }
2875
2876 private:
2877         std::vector<CTopology::TTopologyRef> _TopologiesPath;
2878         CWorldPosition _Start;
2879         CWorldPosition _End;
2880 };
2881
2882 //////////////////////////////////////////////////////////////////////////////
2883
2884 /**
2885  * The Inside A* Path structure, computed by the WorldMap
2886  * \author Benjamin Legros
2887  * \author Nevrax France
2888  * \date 2003
2889  */
2890 class CInsideAStarPath
2891 {
2892         friend class CWorldMap;
2893 public:
2894         CWorldPosition const& getStartPos() const { return _Start; }
2895         void setStartPos(CWorldPosition const& pos) { _Start = pos; }
2896
2897         CWorldPosition const& getEndPos() const { return _End; }
2898         void setEndPos(CWorldPosition const& pos) { _End = pos; }
2899         std::vector<CDirection>& getStepPathForCalc() { return _StepPath; }
2900
2901 private:
2902         CWorldPosition                  _Start;
2903         CWorldPosition                  _End;
2904         std::vector<CDirection> _StepPath;
2905 };
2906
2907 //////////////////////////////////////////////////////////////////////////////
2908
2909 /**
2910  * A template Heap implementation
2911  * \author Benjamin Legros
2912  * \author Nevrax France
2913  * \date 2003
2914  */
2915 template <typename T, typename V>
2916 class CHeap
2917 {
2918 public:
2919         typedef std::pair<T, V> THeapNode;
2920
2921 public:
2922         CHeap();
2923
2924         /// clear Heap
2925         void clear() { _Heap.resize(1); }
2926
2927         /// test heap is empty or not
2928         bool empty() const { return _Heap.size() <= 1; }
2929
2930         /// push a value in heap and sort it
2931         void push(T key, V const& value);
2932
2933         /// pop the minimal value of the heap
2934         V pop();
2935
2936         void backwardLeveling(uint index);
2937
2938         void forwardLeveling(uint index);
2939
2940         /// auto check of the internal heap state
2941         void check();
2942
2943         uint32 size() { return _Heap.size(); }
2944
2945         std::vector<THeapNode>& heapAsVector() { return _Heap; }
2946
2947 private:
2948         std::vector<THeapNode> _Heap;
2949 };
2950
2951 template <typename T, typename V>
2952 CHeap<T, V>::CHeap()
2953 {
2954         // node 0 unused (daniel's trick)
2955         clear();
2956 }
2957
2958 template <typename T, typename V>
2959 void CHeap<T, V>::push(T key, V const& value)
2960 {
2961         _Heap.push_back(THeapNode(key, value));
2962
2963         backwardLeveling((uint)_Heap.size()-1);
2964 }
2965
2966 template <typename T, typename V>
2967 V CHeap<T, V>::pop()
2968 {
2969 #ifdef NL_DEBUG
2970         nlassert(_Heap.size() > 1);
2971 #endif
2972
2973         // return best value
2974         V ret = _Heap[1].second;
2975
2976         // if only 1 node in heap, pop it and leave
2977         if (_Heap.size() == 2)
2978         {
2979                 _Heap.pop_back();
2980                 return ret;
2981         }
2982
2983         // for more than 1 object, copy last at top and pop last
2984         _Heap[1] = _Heap.back();
2985         _Heap.pop_back();
2986
2987         forwardLeveling (1);
2988         return ret;
2989 }
2990
2991 template <typename T, typename V>
2992 void CHeap<T, V>::backwardLeveling(uint index)
2993 {
2994         while (index != 1 && _Heap[index].first < _Heap[index/2].first)
2995         {
2996                 swap(_Heap[index], _Heap[index/2]);
2997                 index /= 2;
2998         }
2999 }
3000
3001 template <typename T, typename V>
3002 void CHeap<T, V>::forwardLeveling(uint index)
3003 {
3004         while (true)
3005         {
3006                 uint min_index = 2*index;
3007
3008                 // if object has no child, leave
3009                 if (min_index > _Heap.size()-1)
3010                         break;
3011
3012                 // choose left or right child
3013                 if (min_index+1 <= _Heap.size()-1 && _Heap[min_index].first>_Heap[min_index+1].first)
3014                         ++min_index;
3015
3016                 // if swap needed, swap and step one more, else leave
3017                 if (_Heap[index].first > _Heap[min_index].first)
3018                 {
3019                         swap(_Heap[index], _Heap[min_index]);
3020                         index = min_index;
3021                 }
3022                 else
3023                 {
3024                         break;
3025                 }
3026         }
3027 }
3028
3029 template <typename T, typename V>
3030 void CHeap<T, V>::check()
3031 {
3032         for (uint index=1; index<=_Heap.size()-1; ++index)
3033         {
3034                 if (2*index <= _Heap.size()-1)
3035                         nlassert(_Heap[index].first <= _Heap[2*index].first);
3036                 if (2*index+1 <= _Heap.size()-1)
3037                         nlassert(_Heap[index].first <= _Heap[2*index+1].first);
3038         }
3039 }
3040
3041 //////////////////////////////////////////////////////////////////////////////
3042
3043 /**
3044  * The world mapping
3045  * \author Benjamin Legros
3046  * \author Nevrax France
3047  * \date 2003
3048  */
3049
3050 class CWorldMap
3051 {
3052         friend class RYPACSCRUNCH::CPacsCruncher;
3053         friend class CWorldPosition;
3054         friend class CTopology::CNeighbourLink;
3055 public:
3056         CWorldMap();
3057         ~CWorldMap();
3058
3059         // serial -- beware, this method merges, use clear() before to load only one world map
3060         void serial(NLMISC::IStream& f);
3061
3062         /// \name User Interface, path finding and complex moves
3063         // @{
3064         /// Finds an A* path
3065         bool findAStarPath(CWorldPosition const& start, CWorldPosition const& end, std::vector<CTopology::TTopologyRef>& path, TAStarFlag denyflags = Nothing) const;
3066
3067         /// Finds an A* path
3068         bool findAStarPath(CTopology::TTopologyId const& start, CTopology::TTopologyId const& end, CAStarPath& path, TAStarFlag denyflags = Nothing) const;
3069
3070         /// Finds an A* inside a topoly
3071         bool findInsideAStarPath(CWorldPosition const& start, CWorldPosition const& end, std::vector<CDirection>& stepPath, TAStarFlag denyflags = Nothing) const;
3072
3073         /// Moves to given topology, returns false if failed
3074         bool moveTowards(CWorldPosition& pos, CTopology::TTopologyRef const& topology) const;
3075
3076         /// Moves according a to a given path, returns false if failed
3077         bool move(CWorldPosition& pos, CAStarPath& path, uint& currentstep) const;
3078
3079         /// Moves from a position to another
3080         bool move(CWorldPosition& pos, CMapPosition const& end, TAStarFlag const denyFlags) const;
3081         // @}
3082
3083         bool customCheckDiagMove(CWorldPosition const& pos, CDirection const& direction, RYAI_MAP_CRUNCH::TAStarFlag denyFlags) const;
3084
3085         // clean
3086         void clear();
3087
3088         void setFlagOnPosAndRadius(CMapPosition const& pos, float radius, uint32 flag);
3089
3090         //      to remove.
3091         CNeighbourhood neighbours(CWorldPosition const& wpos) const;
3092
3093         /// Moves in neighbourhood
3094         bool move(CWorldPosition& pos, CDirection const& direction) const;
3095
3096         /// Moves in neighbourhood (corner moves don't avoid collision)
3097         bool moveSecure(CWorldPosition& pos, CDirection const& direction, uint16 maskFlags = 0xffff) const;
3098
3099         /// Moves in neighbourhood with diag test on both sides
3100         bool moveDiagTestBothSide(CWorldPosition& pos, CDirection const& direction) const;
3101
3102         CTopology::TTopologyId getTopologyId(CWorldPosition const& wpos) const;
3103
3104         // LastRemoved
3105         CTopology const& getTopologyNode(CTopology::TTopologyId const& id) const;
3106
3107         CTopology& getTopologyNode(CTopology::TTopologyId const& id);
3108
3109         CGridDirectionLayer const* getGridDirectionLayer(CWorldPosition const& pos, CTopology::TTopologyRef const& topologyRef) const;
3110
3111         /// Get CWorldPosition from a CMapPosition and a CSlot
3112         CWorldPosition getWorldPosition(CMapPosition const& mapPos, CSlot const& slot) const;
3113
3114         /**
3115          * Get CWorldPosition from a CMapPosition and a TLevel
3116          * Assumes that 0 is the highest level at the given CMapPosition, and greater the level is, lower the height is.
3117          */
3118         CWorldPosition getWorldPosition(CMapPosition const& mapPos, TLevel level) const;
3119
3120         // do not initialise a bot with the position & the world position (or u must assume that pos have no fraction).
3121         bool setWorldPosition(AITYPES::TVerticalPos verticalPos, CWorldPosition& wpos, CAIVector const& pos, CRootCell const* originCell = NULL) const;
3122
3123         // Alternate setWorldPosition(), with real z instead of TVerticalPos, in millimeters
3124         bool setWorldPosition(sint32 z, CWorldPosition& wpos, CAIVector const& pos, CRootCell const* originCell = NULL) const;
3125         // Double version isn't tested !!! Verify it's the same than above sint32 version !
3126         bool setWorldPosition(double z, CWorldPosition& wpos, CAIVector const& pos, CRootCell const* originCell = NULL) const;
3127
3128         CTopology::TTopologyRef getTopologyRef(CTopology::TTopologyId const& id) const;
3129
3130         void buildMasterTopo(bool allowWater, bool allowNogo);
3131
3132         // checks motion layers
3133         void checkMotionLayer();
3134
3135         void countSuperTopo();
3136
3137         CRootCell const* getRootCellCst(CMapPosition const& pos) const;
3138
3139         CSuperCell const* getSuperCellCst(CMapPosition const& pos) const;
3140
3141         void getBounds(CMapPosition& min, CMapPosition& max);
3142
3143         CWorldPosition getSafeWorldPosition(CMapPosition const& mapPos, CSlot const& slot) const;
3144
3145 protected:
3146         CWorldPosition getWorldPositionGeneration(CMapPosition const& mapPos, CSlot const& slot) const;
3147
3148
3149         /// Get a world position from a vector position
3150         template <class T>
3151         CWorldPosition getWorldPosition(T const& pos) const
3152         {
3153                 CSlot slot;
3154                 CMapPosition const mapPos(pos);
3155
3156                 CRootCell const* cell = getRootCellCst(mapPos);
3157                 if (cell)
3158                 {
3159                         double bd = 1.0e10;
3160
3161                         // find best slot
3162                         for (uint32     s=0; s<3; ++s)
3163                         {
3164                                 CSlot const sslot = CSlot(s);
3165                                 if (!cell->isSlotUsed(mapPos, sslot))
3166                                         continue;
3167                                 double const sh = cell->getHeight(CWorldPosition(cell,mapPos,sslot))*2.0 + 1.0;
3168                                 if (fabs(sh) < bd)
3169                                 {
3170                                         bd = fabs(sh);
3171                                         slot=sslot;
3172                                 }
3173                         }
3174                 }
3175                 return CWorldPosition(cell,mapPos,slot);
3176         }
3177
3178
3179         //      only for generation.
3180         CSuperCell* getSuperCell(CMapPosition const& pos);
3181
3182         CComputeCell* getComputeCell(CMapPosition const& pos);
3183
3184         CRootCell* getRootCell(CMapPosition const& pos);
3185
3186         bool exist(CMapPosition const& pos) const;
3187
3188         uint32 nbUsedSlots(CMapPosition const& pos) const;
3189
3190         sint32 maxUsedSlot(CMapPosition const& pos) const;
3191
3192         bool isSlotUsed(CMapPosition const& pos, CSlot slot) const;
3193
3194         //      used in build process.
3195         uint getTopology(CWorldPosition const& wpos) const;
3196
3197         void countCells(uint& compute, uint& white, uint& simple, uint& multi, uint& other) const;
3198
3199         // mutators
3200         void setRootCell(CMapPosition const& pos, CRootCell* cell);
3201
3202         // clear height map
3203         void clearHeightMap();
3204
3205         //
3206         // compute cell selectors
3207         //
3208
3209         TCellUnit& getCellUnit(CMapPosition const& pos);
3210
3211         CUnitSlot& getUnitSlot(CWorldPosition const& wpos);
3212
3213         CComputeCell const* getComputeCellCst(CMapPosition const& pos) const;
3214
3215         void resetUnitSlotNLink(CWorldPosition const& wpos) { getUnitSlot(wpos).cellLink().setNSlot(CSlot()); }
3216         void resetUnitSlotSLink(CWorldPosition const& wpos) { getUnitSlot(wpos).cellLink().setSSlot(CSlot()); }
3217         void resetUnitSlotWLink(CWorldPosition const& wpos) { getUnitSlot(wpos).cellLink().setWSlot(CSlot()); }
3218         void resetUnitSlotELink(CWorldPosition const& wpos) { getUnitSlot(wpos).cellLink().setESlot(CSlot()); }
3219
3220         void resetUnitSlot(CWorldPosition const& wpos);
3221
3222 private:
3223         CSuperCell* _GridFastAccess[256*256];
3224
3225 public:
3226         /// \name Path finding related error handling
3227         // @{
3228         enum TFindAStarPathReason
3229         {
3230                 FASPR_NO_REASON = -1,
3231                 FASPR_NO_ERROR,
3232                 FASPR_INVALID_START_POS,
3233                 FASPR_INVALID_END_POS,
3234                 FASPR_INVALID_START_TOPO,
3235                 FASPR_INVALID_END_TOPO,
3236                 FASPR_INCOMPATIBLE_POSITIONS,
3237                 FASPR_NOT_FOUND
3238         };
3239         mutable TFindAStarPathReason _LastFASPReason;
3240         static std::string toString(TFindAStarPathReason reason);
3241         enum TFindInsideAStarPathReason
3242         {
3243                 FIASPR_NO_REASON = -1,
3244                 FIASPR_NO_ERROR,
3245                 FIASPR_INVALID_START_POS,
3246                 FIASPR_INVALID_END_POS,
3247                 FIASPR_DIFFERENT_TOPO,
3248                 FIASPR_NOT_FOUND
3249         };
3250         mutable TFindInsideAStarPathReason _LastFIASPReason;
3251         static std::string toString(TFindInsideAStarPathReason reason);
3252         // @}
3253 };
3254
3255 inline
3256 CWorldPosition::CWorldPosition(const CRootCell *cell, const CMapPosition &pos, const CSlot &slot) : CMapPosition(pos), CSlot(slot), _RootCell(cell)
3257 {
3258         _cellLinkage=_RootCell->getCellLink(*this);
3259 }
3260
3261 inline
3262 CWorldPosition::CWorldPosition(const CRootCell *cell, const CMapPosition &pos, const CSlot &slot,bool generationOnly) : CMapPosition(pos), CSlot(slot), _RootCell(cell)
3263 {
3264 }
3265
3266 inline
3267 CWorldPosition CWorldPosition::getPosS() const
3268 {
3269         CWorldPosition wp(*this);
3270         wp.stepS();
3271         return wp;
3272 }
3273
3274 inline
3275 CWorldPosition CWorldPosition::getPosN() const
3276 {
3277         CWorldPosition wp(*this);
3278         wp.stepN();
3279         return wp;
3280 }
3281
3282 inline
3283 CWorldPosition CWorldPosition::getPosE() const
3284 {
3285         CWorldPosition wp(*this);
3286         wp.stepE();
3287         return wp;
3288 }
3289
3290 inline
3291 CWorldPosition CWorldPosition::getPosW() const
3292 {
3293         CWorldPosition wp(*this);
3294         wp.stepW();
3295         return wp;
3296 }
3297
3298 inline
3299 void CWorldPosition::setPosS(CWorldPosition& pos) const
3300 {
3301         pos = *this;
3302         pos.stepS();
3303 }
3304
3305 inline
3306 void CWorldPosition::setPosN(CWorldPosition& pos) const
3307 {
3308         pos = *this;
3309         pos.stepN();
3310 }
3311
3312 inline
3313 void CWorldPosition::setPosE(CWorldPosition& pos) const
3314 {
3315         pos = *this;
3316         pos.stepE();
3317 }
3318
3319 inline
3320 void CWorldPosition::setPosW(CWorldPosition& pos) const
3321 {
3322         pos = *this;
3323         pos.stepW();
3324 }
3325
3326 inline
3327 void CWorldPosition::stepS()
3328 {
3329 #ifdef NL_DEBUG
3330         nlassert(_RootCell);
3331 #endif
3332         setSlot(_cellLinkage.SSlot());
3333 #ifdef NL_DEBUG
3334         nlassert(CSlot::isValid());
3335 #endif
3336
3337         if (CMapPosition::stepS())      //      check if we have to recalculate the RootCell ..
3338         {
3339                 _RootCell = getRootCell()->getWorldMapPtr().getRootCellCst(*this);      // obtain the new _RootCell pointer
3340         }
3341         _cellLinkage = _RootCell->getCellLink(*this);
3342 }
3343
3344 inline
3345 void CWorldPosition::stepN()
3346 {
3347 #ifdef NL_DEBUG
3348         nlassert(_RootCell);
3349 #endif
3350         setSlot(_cellLinkage.NSlot());
3351 #ifdef NL_DEBUG
3352         nlassert(CSlot::isValid());
3353 #endif
3354
3355         if (CMapPosition::stepN())      //      check if we have to recalculate the RootCell ..
3356         {
3357                 _RootCell = getRootCell()->getWorldMapPtr().getRootCellCst(*this);      // obtain the new _RootCell pointer
3358         }
3359         _cellLinkage = _RootCell->getCellLink(*this);
3360 }
3361
3362 inline
3363 void CWorldPosition::stepE()
3364 {
3365 #ifdef NL_DEBUG
3366         nlassert(_RootCell);
3367 #endif
3368         setSlot(_cellLinkage.ESlot());
3369 #ifdef NL_DEBUG
3370         nlassert(CSlot::isValid());
3371 #endif
3372
3373         if (CMapPosition::stepE())      //      check if we have to recalculate the RootCell ..
3374         {
3375                 _RootCell = getRootCell()->getWorldMapPtr().getRootCellCst(*this);      // obtain the new _RootCell pointer
3376         }
3377         _cellLinkage = _RootCell->getCellLink(*this);
3378 }
3379
3380 inline
3381 void CWorldPosition::stepW()
3382 {
3383 #ifdef NL_DEBUG
3384         nlassert(_RootCell);
3385 #endif
3386         setSlot(_cellLinkage.WSlot());
3387 #ifdef NL_DEBUG
3388         nlassert(CSlot::isValid());
3389 #endif
3390
3391         if (CMapPosition::stepW())      //      check if we have to recalculate the RootCell ..
3392         {
3393                 _RootCell = getRootCell()->getWorldMapPtr().getRootCellCst(*this);      // obtain the new _RootCell pointer
3394         }
3395         _cellLinkage = _RootCell->getCellLink(*this);
3396 }
3397
3398 inline
3399 bool CWorldPosition::moveS()
3400 {
3401         if (getCellLinkage().isSSlotValid())
3402         {
3403                 stepS();
3404                 return true;
3405         }
3406         return false;
3407 }
3408
3409 inline
3410 bool CWorldPosition::moveN()
3411 {
3412         if (getCellLinkage().isNSlotValid())
3413         {
3414                 stepN();
3415                 return true;
3416         }
3417         return false;
3418 }
3419
3420 inline
3421 bool CWorldPosition::moveE()
3422 {
3423         if (getCellLinkage().isESlotValid())
3424         {
3425                 stepE();
3426                 return true;
3427         }
3428         return false;
3429 }
3430
3431 inline
3432 bool CWorldPosition::moveW()
3433 {
3434         if (getCellLinkage().isWSlotValid())
3435         {
3436                 stepW();
3437                 return true;
3438         }
3439         return false;
3440 }
3441
3442 inline
3443 NLMISC::CVectorD CWorldPosition::getPosition() const
3444 {
3445         NLMISC::CVectorD ret = toVectorD();
3446         CRootCell const* cell = getRootCell();
3447         if (cell)
3448                 ret.z = cell->getHeight(*this)*2.0 + 1.0;
3449         return ret;
3450 }
3451
3452 inline
3453 sint32 CWorldPosition::getMetricHeight() const
3454 {
3455         if (_RootCell)
3456                 return _RootCell->getMetricHeight(*this);
3457         return 0;
3458 }
3459
3460 inline
3461 CTopology const& CTopology::TTopologyRef::getCstTopologyNode() const
3462 {
3463 #ifdef NL_DEBUG
3464         nlassert(_RootCell);
3465 #endif
3466         return _RootCell->getCstTopologyNode(getTopologyIndex());
3467 }
3468
3469 inline
3470 CTopology::TTopologyRef::TTopologyRef(CWorldPosition const& pos, CRootCell const* rootCell)
3471 : TTopologyId(pos, rootCell->getTopology(pos))
3472 , _RootCell(rootCell)
3473 {
3474 #ifdef NL_DEBUG
3475         nlassert(rootCell);
3476 #endif
3477         // TESTTOREMOVE TODO
3478 #if !FINAL_VERSION
3479         nlassert(&_RootCell->getCstTopologyNode(getTopologyIndex())!=NULL);
3480 #endif
3481 }
3482
3483 inline
3484 CTopology::TTopologyRef::TTopologyRef(CWorldPosition const& pos)
3485 : TTopologyId(pos, pos.getRootCell()->getTopology(pos))
3486 , _RootCell(pos.getRootCell())
3487 {
3488         // TESTTOREMOVE TODO
3489 #if !FINAL_VERSION
3490         nlassert(&_RootCell->getCstTopologyNode(getTopologyIndex())!=NULL);
3491 #endif
3492 }
3493
3494 inline
3495 void CTopology::CNeighbourLink::updateTopologyRef(CWorldMap* worldMapPtr)
3496 {
3497         _Ref.setRootCell(worldMapPtr->getRootCell(_Ref.getMapPosition()));
3498         // TESTTOREMOVE TODO
3499 #if !FINAL_VERSION
3500         nlassert(&_Ref.getCstTopologyNode()!=NULL);
3501 #endif
3502 }
3503
3504 inline
3505 CWorldMap::CWorldMap()
3506 {
3507         for     (uint i=0; i<65536; ++i)
3508                 _GridFastAccess[i]=NULL;
3509 }
3510
3511 inline
3512 CWorldMap::~CWorldMap()
3513 {
3514         for     (uint i=0; i<65536; ++i)
3515                 if (_GridFastAccess[i])
3516                         delete _GridFastAccess[i];
3517 }
3518
3519 inline
3520 CTopology::TTopologyId CWorldMap::getTopologyId(CWorldPosition const& wpos) const
3521 {
3522         CRootCell const* cell = getRootCellCst(wpos);
3523         return !cell ? CTopology::TTopologyId() : CTopology::TTopologyId(wpos, cell->getTopology(wpos));
3524 }
3525
3526 inline
3527 CTopology const& CWorldMap::getTopologyNode(CTopology::TTopologyId const& id) const
3528 {
3529         CMapPosition pos = id.getMapPosition();
3530         uint topo = id.getTopologyIndex();
3531
3532         CRootCell const* cell = getRootCellCst(pos);
3533 #ifdef NL_DEBUG
3534         nlassert(cell);
3535 #endif
3536         return cell->getCstTopologyNode(topo);
3537 }
3538
3539 inline
3540 CTopology& CWorldMap::getTopologyNode(CTopology::TTopologyId const& id)
3541 {
3542         CMapPosition pos = id.getMapPosition();
3543         uint topo = id.getTopologyIndex();
3544
3545         CRootCell* cell = getRootCell(pos);
3546 #ifdef NL_DEBUG
3547         nlassert(cell);
3548 #endif
3549         return cell->getTopologyNode(topo);
3550 }
3551
3552 inline
3553 CGridDirectionLayer const* CWorldMap::getGridDirectionLayer(CWorldPosition const& pos, CTopology::TTopologyRef const& topologyRef) const
3554 {
3555         if (!pos.isValid())
3556                 return NULL;
3557
3558         CMapPosition tpos = topologyRef.getMapPosition();
3559
3560         sint dx = pos.xCoord().getFullCellId()-tpos.xCoord().getFullCellId();
3561         sint dy = pos.yCoord().getFullCellId()-tpos.yCoord().getFullCellId();
3562
3563         if (abs(dx) > 1 || abs(dy) > 1)
3564                 return NULL;
3565
3566         CTopology const& node = topologyRef.getCstTopologyNode();
3567
3568         if (!node.DirectionMap)
3569                 return  NULL;
3570
3571         CDirectionLayer* directionLayer = node.DirectionMap->Layers[pos.slot()];
3572         if (!directionLayer)
3573                 return NULL;
3574
3575         return directionLayer->getGridLayer(dy+1,dx+1);
3576 }
3577
3578 inline
3579 CWorldPosition CWorldMap::getWorldPosition(CMapPosition const& mapPos, CSlot const& slot) const
3580 {
3581         return CWorldPosition(getRootCellCst(mapPos), mapPos, slot);
3582 }
3583
3584 inline
3585 CWorldPosition CWorldMap::getWorldPosition(CMapPosition const& mapPos, TLevel level) const
3586 {
3587         CRootCell const* cell = getRootCellCst(mapPos);
3588
3589         std::vector<sint32>     slots;
3590         slots.reserve(4);
3591
3592         // go through all slots and get their height
3593         for (uint s=0; s<3; ++s)
3594         {
3595                 CSlot slot(s);
3596
3597                 if (!cell->isSlotUsed(mapPos, slot))
3598                         continue;
3599
3600                 CWorldPosition wPos = CWorldPosition(cell, mapPos, slot);
3601                 slots.push_back((cell->getHeight(wPos) << 2) + s);
3602         }
3603
3604         // sort them, from the lowest to the heightest
3605         std::sort(slots.begin(), slots.end());
3606
3607         // get heightest slot
3608         level = (RYAI_MAP_CRUNCH::TLevel)(slots.size()-1) - level;
3609
3610         // if slot exists, return it or invalid position
3611         return (level < 0 && level >= (sint)slots.size()) ? CWorldPosition() : CWorldPosition(cell, mapPos, CSlot(slots[level]&3));
3612 }
3613
3614 inline
3615 bool CWorldMap::setWorldPosition(AITYPES::TVerticalPos verticalPos, CWorldPosition& wpos, CAIVector const& pos, CRootCell const* originCell) const
3616 {
3617         CSlot slot;
3618         CMapPosition const mapPos(pos);
3619
3620         CRootCell const* cell = originCell ? originCell : getRootCellCst(mapPos);
3621         if (!cell)
3622         {
3623                 wpos = CWorldPosition(cell, mapPos, slot, true);
3624                 // addon (not agree but no choice).
3625                 return false;
3626         }
3627
3628         std::map<double, CSlot> orderedSlots;
3629         // find best slot
3630         for (uint32     s=0; s<3; ++s)
3631         {
3632                 if (!cell->isSlotUsed(mapPos, CSlot(s)))
3633                         continue;
3634
3635                 CSlot const sslot = CSlot(s);
3636                 double const sh = cell->getHeight(CWorldPosition(cell,mapPos,sslot));
3637                 orderedSlots.insert(std::make_pair(sh, sslot));
3638         }
3639
3640         if (!orderedSlots.empty())
3641         {
3642                 if (verticalPos == AITYPES::vp_auto)
3643                 {
3644                         double h = orderedSlots.rbegin()->first;
3645                         slot = orderedSlots.rbegin()->second;
3646                 }
3647                 else if (verticalPos == AITYPES::vp_upper)
3648                 {
3649                         double h = orderedSlots.rbegin()->first;
3650                         slot = orderedSlots.rbegin()->second;
3651                 }
3652                 else if (verticalPos == AITYPES::vp_lower)
3653                 {
3654                         double h = orderedSlots.begin()->first;
3655                         slot = orderedSlots.begin()->second;
3656                 }
3657                 else if (verticalPos == AITYPES::vp_middle)
3658                 {
3659                         if (orderedSlots.size() > 1)
3660                         {
3661                                 orderedSlots.erase(orderedSlots.rbegin()->first);
3662                                 double h = orderedSlots.rbegin()->first;
3663                                 slot = orderedSlots.rbegin()->second;
3664                         }
3665                         else
3666                         {
3667                                 double h = orderedSlots.begin()->first;
3668                                 slot = orderedSlots.begin()->second;
3669                         }
3670                 }
3671                 else
3672                 {
3673                         nlwarning("invalid vertical pos type !");
3674                 }
3675         }
3676
3677         if (!slot.isValid())
3678         {
3679                 wpos = CWorldPosition(cell,mapPos,slot,true);
3680                 return false;
3681         }
3682
3683         wpos = CWorldPosition(cell,mapPos,slot);
3684         return true;
3685 }
3686
3687 inline
3688 CTopology::TTopologyRef CWorldMap::getTopologyRef(CTopology::TTopologyId const& id) const
3689 {
3690         return CTopology::TTopologyRef(id, const_cast<CRootCell*>(getRootCellCst(id.getMapPosition())));
3691 }
3692
3693 inline
3694 CRootCell const* CWorldMap::getRootCellCst(CMapPosition const& pos) const
3695 {
3696         CSuperCell const* scell = getSuperCellCst(pos);
3697         return !scell ? NULL : scell->getRootCellCst(pos);
3698 }
3699
3700 inline
3701 CSuperCell const* CWorldMap::getSuperCellCst(CMapPosition const& pos) const
3702 {
3703         return _GridFastAccess[pos.superCellFastIndex()];
3704 }
3705
3706 inline
3707 CWorldPosition CWorldMap::getWorldPositionGeneration(CMapPosition const& mapPos, CSlot const& slot) const
3708 {
3709         return CWorldPosition(getRootCellCst(mapPos),mapPos,slot,true); //      without assuring cellLink is valid .. :(
3710 }
3711
3712 inline
3713 CWorldPosition CWorldMap::getSafeWorldPosition(CMapPosition const& mapPos, CSlot const& slot) const
3714 {
3715         CRootCell const* cell = getRootCellCst(mapPos);
3716         return (cell && cell->isSlotUsed(mapPos, slot)) ? CWorldPosition(getRootCellCst(mapPos),mapPos,slot) : CWorldPosition();        //      without assuring cellLink is valid .. :(
3717 }
3718
3719 inline
3720 CSuperCell* CWorldMap::getSuperCell(CMapPosition const& pos)
3721 {
3722         CSuperCell*     superCellPtr = _GridFastAccess[pos.superCellFastIndex()];
3723
3724         if (!superCellPtr)
3725                 _GridFastAccess[pos.superCellFastIndex()] = superCellPtr=new CSuperCell(*this);
3726
3727 #ifdef NL_DEBUG
3728         nlassert(superCellPtr);
3729 #endif
3730         return superCellPtr;
3731 }
3732
3733 inline
3734 CComputeCell* CWorldMap::getComputeCell(CMapPosition const& pos)
3735 {
3736         return getSuperCell(pos)->getComputeCell(pos);
3737 }
3738
3739 inline
3740 CRootCell* CWorldMap::getRootCell(CMapPosition const& pos)
3741 {
3742         CSuperCell* scell = getSuperCell(pos);
3743         return !scell ? NULL : scell->getRootCell(pos);
3744 }
3745
3746 inline
3747 bool CWorldMap::exist(CMapPosition const& pos) const
3748 {
3749         return getRootCellCst(pos)!=NULL;
3750 }
3751
3752 inline
3753 uint32 CWorldMap::nbUsedSlots(CMapPosition const& pos) const
3754 {
3755         CRootCell const* cell = getRootCellCst(pos);
3756         return !cell ? 0:cell->nbUsedSlots(pos);
3757 }
3758
3759 inline
3760 sint32 CWorldMap::maxUsedSlot(CMapPosition const& pos) const
3761 {
3762         CRootCell const* cell = getRootCellCst(pos);
3763         return !cell ? -1 : cell->maxUsedSlot(pos);
3764 }
3765
3766 inline
3767 bool CWorldMap::isSlotUsed(CMapPosition const& pos, CSlot slot) const
3768 {
3769         CRootCell const* cell = getRootCellCst(pos);
3770         return !cell ? false : cell->isSlotUsed(pos, slot);
3771 }
3772
3773 inline
3774 uint CWorldMap::getTopology(CWorldPosition const& wpos) const
3775 {
3776         CRootCell const* cell = wpos.getRootCell();     //getRootCellCst(wpos);
3777         return !cell ? 0 : cell->getTopology(wpos);
3778 }
3779
3780 inline
3781 void CWorldMap::setRootCell(CMapPosition const& pos, CRootCell* cell)
3782 {
3783         getSuperCell(pos)->setRootCell(pos, cell);
3784 }
3785
3786 inline
3787 TCellUnit& CWorldMap::getCellUnit(CMapPosition const& pos)
3788 {
3789         return getComputeCell(pos)->getCellUnit(pos);
3790 }
3791
3792 inline
3793 CUnitSlot& CWorldMap::getUnitSlot(CWorldPosition const& wpos)
3794 {
3795         return getComputeCell(wpos)->getUnitSlot(wpos);
3796 }
3797
3798 inline
3799 CComputeCell const* CWorldMap::getComputeCellCst(CMapPosition const& pos) const
3800 {
3801         CSuperCell const* scell = getSuperCellCst(pos);
3802         return !scell ? NULL : scell->getComputeCell(pos);
3803 }
3804
3805 inline
3806 void CWorldMap::resetUnitSlot(CWorldPosition const& wpos)
3807 {
3808         CUnitSlot& us = getUnitSlot(wpos);
3809
3810         if (us.getCellLink().isNSlotValid()) resetUnitSlotSLink(wpos.getPosN());
3811         if (us.getCellLink().isSSlotValid()) resetUnitSlotNLink(wpos.getPosS());
3812         if (us.getCellLink().isWSlotValid()) resetUnitSlotELink(wpos.getPosW());
3813         if (us.getCellLink().isESlotValid()) resetUnitSlotWLink(wpos.getPosE());
3814
3815         us.reset();
3816 }
3817
3818 inline
3819 std::string CWorldMap::toString(TFindAStarPathReason reason)
3820 {
3821         switch (reason)
3822         {
3823         case FASPR_NO_ERROR:
3824                 return "FASPR_NO_ERROR";
3825         case FASPR_INVALID_START_POS:
3826                 return "FASPR_INVALID_START_POS";
3827         case FASPR_INVALID_END_POS:
3828                 return "FASPR_INVALID_END_POS";
3829         case FASPR_INVALID_START_TOPO:
3830                 return "FASPR_INVALID_START_TOPO";
3831         case FASPR_INVALID_END_TOPO:
3832                 return "FASPR_INVALID_END_TOPO";
3833         case FASPR_INCOMPATIBLE_POSITIONS:
3834                 return "FASPR_INCOMPATIBLE_POSITIONS";
3835         case FASPR_NOT_FOUND:
3836                 return "FIASPR_NOT_FOUND";
3837         default:
3838                 return "UnknownReason(" + NLMISC::toString((int)reason) + ")";
3839         }
3840 }
3841
3842 inline
3843 std::string CWorldMap::toString(TFindInsideAStarPathReason reason)
3844 {
3845         switch (reason)
3846         {
3847         case FIASPR_NO_ERROR:
3848                 return "FIASPR_NO_ERROR";
3849         case FIASPR_INVALID_START_POS:
3850                 return "FIASPR_INVALID_START_POS";
3851         case FIASPR_INVALID_END_POS:
3852                 return "FIASPR_INVALID_END_POS";
3853         case FIASPR_DIFFERENT_TOPO:
3854                 return "FIASPR_DIFFERENT_TOPO";
3855         case FIASPR_NOT_FOUND:
3856                 return "FIASPR_NOT_FOUND";
3857         default:
3858                 return "UnknownReason(" + NLMISC::toString((int)reason) + ")";
3859         }
3860 }
3861
3862 }
3863
3864 //////////////////////////////////////////////////////////////////////////////
3865
3866 class CTimeEstimator
3867 {
3868 public:
3869         CTimeEstimator(uint total);
3870
3871         void step(char const* str);
3872
3873 private:
3874         NLMISC::TTime   _StartTime;
3875         NLMISC::TTime   _LastTime;
3876
3877         uint                    _TotalCounter;
3878         uint                    _CurrentCounter;
3879         uint                    _LastCounter;
3880
3881         double                  _AverageSpeed;
3882
3883         std::string     secToString(sint sec);
3884 };
3885
3886 inline
3887 CTimeEstimator::CTimeEstimator(uint total)
3888 : _TotalCounter(total)
3889 , _CurrentCounter(0)
3890 , _LastCounter(0)
3891 , _AverageSpeed(-1.0)
3892 {
3893         _StartTime = NLMISC::CTime::getLocalTime();
3894         _LastTime = _StartTime;
3895 }
3896
3897 inline
3898 void CTimeEstimator::step(char const* str)
3899 {
3900         ++_CurrentCounter;
3901
3902         NLMISC::TTime currentTime = NLMISC::CTime::getLocalTime();
3903
3904         if (currentTime-_LastTime > 2000)
3905         {
3906                 NLMISC::TTime   dt = currentTime-_LastTime;
3907                 double                  speed = 1000.0*(_CurrentCounter-_LastCounter)/dt;
3908
3909                 _AverageSpeed = (_AverageSpeed < 0.0 ? speed : _AverageSpeed*0.98 + speed*0.02);
3910
3911                 uint                    remaining = _TotalCounter-_CurrentCounter;
3912
3913                 NLMISC::TTime   ellapsedTime = currentTime-_StartTime;
3914                 NLMISC::TTime   remainingTime = (NLMISC::TTime)(remaining*1000/_AverageSpeed);
3915
3916                 double                  percent = 100.0*_CurrentCounter/_TotalCounter;
3917                 uint                    maxpercent = (percent > 100.0 ? 100 : (uint)percent);
3918                 uint                    linesize = maxpercent/5;
3919
3920                 nlinfo("%s: %.1f%% [ellapsed:%s, togo:%s, total:%s]", str, percent, secToString((uint)(ellapsedTime/1000)).c_str(), secToString((uint)(remainingTime/1000)).c_str(), secToString((uint)((remainingTime+ellapsedTime)/1000)).c_str());
3921
3922                 _LastCounter = _CurrentCounter;
3923                 _LastTime = currentTime;
3924         }
3925 }
3926
3927 inline
3928 std::string     CTimeEstimator::secToString(sint sec)
3929 {
3930         return NLMISC::toString(sec/60)+"m"+NLMISC::toString(sec%60)+"s";
3931 }
3932
3933 #endif