?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add infos into target window
[ryzomcore.git] / ryzom / server / src / ai_share / world_map.cpp
blob8133c481b2352b7b72a4e39d44699834a12ed4ec
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) 2015-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 #include "stdpch.h"
22 #include "game_share/utils.h"
23 #include "world_map.h"
24
25 //extern bool simulateBug(int bugId);
26
27 using namespace std;
28 using namespace NLMISC;
29
30 namespace RYAI_MAP_CRUNCH
31 {
32
33 NL_BEGIN_STRING_CONVERSION_TABLE (TAStarFlag)
34 NL_STRING_CONVERSION_TABLE_ENTRY(Nothing)
35 NL_STRING_CONVERSION_TABLE_ENTRY(Interior)
36 NL_STRING_CONVERSION_TABLE_ENTRY(Water)
37 NL_STRING_CONVERSION_TABLE_ENTRY(NoGo)
38 NL_STRING_CONVERSION_TABLE_ENTRY(WaterAndNogo)
39 NL_STRING_CONVERSION_TABLE_ENTRY(GroundFlags)
40 NL_END_STRING_CONVERSION_TABLE(TAStarFlag, AStarFlagConversion, Nothing)
41
42 const std::string& toString(TAStarFlag flag)
43 {
44 return AStarFlagConversion.toString(flag);
45 }
46
47 TAStarFlag toAStarFlag(const std::string& str)
48 {
49 return AStarFlagConversion.fromString(str);
50 }
51
52
53 //////////////////////////////////////////////////////////////////////////////
54 // Helper classes and data //
55 //////////////////////////////////////////////////////////////////////////////
56
57 const struct CDirection::CDirectionData CDirection::directionDatas[] =
58 {
59 { +1, 0, ORTHO_COST},
60 { +1, +1, DIAG_COST},
61 { 0, +1, ORTHO_COST},
62 { -1, +1, DIAG_COST},
63 { -1, 0, ORTHO_COST},
64 { -1, -1, DIAG_COST},
65 { 0, -1, ORTHO_COST},
66 { +1, -1, DIAG_COST},
67 { 0, 0, NO_COST}
68 };
69
70 // Enum vals ..
71 // 5 6 7
72 // 4 8 0
73 // 3 2 1
74 const CDirection::TDirection CDirection::table[] =
75 {
76 CDirection::SW, CDirection::S, CDirection::SE,
77 CDirection::W, CDirection::UNDEFINED, CDirection::E,
78 CDirection::NW, CDirection::N, CDirection::NE
79 };
80
81 //////////////////////////////////////////////////////////////////////////////
82 // //
83 //////////////////////////////////////////////////////////////////////////////
84
85 class CABaseStarNode
86 {
87 public:
88 CABaseStarNode(uint father, float distance, bool open);
89
90 void setOpen(bool open) { _Open = open; }
91 bool isOpened() const { return _Open; }
92 float getDistance() const { return _Distance; }
93 uint getFather() const { return _Father; }
94
95 private:
96 uint _Father; ///< Parent node in the path from the start position
97 float _Distance;
98 bool _Open; ///< Is the node in the OPEN or CLOSED set?
99 };
100
101 inline
102 CABaseStarNode::CABaseStarNode(uint father, float distance, bool open)
103 : _Father(father)
104 , _Distance(distance)
105 , _Open(open)
106 {
107 }
108
109 //////////////////////////////////////////////////////////////////////////////
110 // CAStarHeapNode //
111 //////////////////////////////////////////////////////////////////////////////
112
113 class CAStarHeapNode : public CABaseStarNode
114 {
115 public:
116 explicit CAStarHeapNode(CTopology::TTopologyRef Ref, uint Father, float Distance, bool Open);
117
118 CTopology::TTopologyRef const& getRef() const { return _Ref; }
119
120 private:
121 CTopology::TTopologyRef _Ref;
122 };
123
124 inline
125 CAStarHeapNode::CAStarHeapNode(CTopology::TTopologyRef Ref, uint Father, float Distance, bool Open)
126 : CABaseStarNode(Father, Distance, Open)
127 , _Ref(Ref)
128 {
129 }
130
131 //////////////////////////////////////////////////////////////////////////////
132 // CAStarNode //
133 //////////////////////////////////////////////////////////////////////////////
134
135 class CAStarNode
136 {
137 public:
138 CAStarNode() { }
139 explicit CAStarNode(CWorldPosition const& pos) :
140 _x(pos.xCoord().getUnitId()) , _y(pos.yCoord().getUnitId()), _slot(pos.slot())
141 { }
142
143 CAStarNode(const CAStarNode & other) :
144 _x(other._x), _y(other._y), _slot(other._slot)
145 { }
146
147 void updateMapPosition(CMapPosition& _mapPos) const;
148
149 bool operator==(CAStarNode const& other) const;
150 bool operator!=(CAStarNode const& other) const;
151 bool operator<(CAStarNode const& other) const;
152
153 CSlot const& slot() const { return _slot; }
154
155 private:
156 uint8 _x;
157 uint8 _y;
158 CSlot _slot;
159 };
160
161 inline
162 void CAStarNode::updateMapPosition(CMapPosition& _mapPos) const
163 {
164 _mapPos.setUnitId(_x, _y);
165 }
166
167 inline
168 bool CAStarNode::operator==(CAStarNode const& other) const
169 {
170 return _x==other._x && _y==other._y && _slot==other._slot;
171 }
172
173 inline
174 bool CAStarNode::operator!=(CAStarNode const& other) const
175 {
176 return _x!=other._x || _y!=other._y || _slot!=other._slot;
177 }
178
179 inline
180 bool CAStarNode::operator<(CAStarNode const& other) const
181 {
182 if (_x!=other._x)
183 return _x<other._x;
184 if (_y!=other._y)
185 return _y<other._y;
186 return _slot<other._slot;
187 }
188
189 //////////////////////////////////////////////////////////////////////////////
190 // //
191 //////////////////////////////////////////////////////////////////////////////
192
193 class CInsideAStarHeapNode : public CABaseStarNode
194 {
195 public:
196 friend class CAStarNode;
197
198 explicit CInsideAStarHeapNode(const CAStarNode &node, uint Father, CDirection Direction, float Distance, bool Open) : CABaseStarNode(Father,Distance,Open), _Direction(Direction), _Node(node)
199 {
200 }
201
202 inline const CDirection &getDirection() const
203 {
204 return _Direction;
205 }
206
207 inline const CAStarNode &getNode() const
208 {
209 return _Node;
210 }
211
212 private:
213 CDirection _Direction;
214 CAStarNode _Node;
215 };
216
217
218 //////////////////////////////////////////////////////////////////////////////
219 // CDirectionLayer //
220 //////////////////////////////////////////////////////////////////////////////
221
222 void CDirectionLayer::serial(NLMISC::IStream& f)
223 {
224 uint i, j;
225 for (i=0; i<3; ++i)
226 {
227 for (j=0; j<3; ++j)
228 {
229 if (f.isReading())
230 {
231 delete Grid[i][j];
232 Grid[i][j] = NULL;
233 }
234
235 bool present = (Grid[i][j] != NULL);
236 f.serial(present);
237
238 if (present)
239 {
240 if (f.isReading())
241 Grid[i][j] = I16x16Layer::load(f);
242 else
243 I16x16Layer::save(f, Grid[i][j]);
244 }
245 }
246 }
247 }
248
249 //////////////////////////////////////////////////////////////////////////////
250 // CDirectionMap //
251 //////////////////////////////////////////////////////////////////////////////
252
253 void CDirectionMap::serial(NLMISC::IStream& f)
254 {
255 uint i;
256 for (i=0; i<3; ++i)
257 {
258 if (f.isReading())
259 {
260 delete Layers[i];
261 Layers[i] = NULL;
262 }
263
264 bool present = (Layers[i] != NULL);
265 f.serial(present);
266
267 if (present)
268 {
269 if (f.isReading())
270 Layers[i] = new CDirectionLayer();
271 nlassert(Layers[i]);
272 f.serial(*Layers[i]);
273 }
274 }
275 }
276
277 //////////////////////////////////////////////////////////////////////////////
278 // CRootCell //
279 //////////////////////////////////////////////////////////////////////////////
280
281 CRootCell* CRootCell::load(NLMISC::IStream& f, CWorldMap const& worldMap)
282 {
283 TCellType type = Compute;
284 CRootCell *result = NULL;
285
286 f.serialEnum(type);
287
288 switch (type)
289 {
290 case Compute:
291 result = new CComputeCell(worldMap);
292 static_cast<CComputeCell*>(result)->serial(f);
293 break;
294 case White:
295 result = new CWhiteCell(worldMap);
296 static_cast<CWhiteCell*>(result)->serial(f);
297 break;
298 case SingleLayer:
299 result = new CSingleLayerCell(worldMap);
300 static_cast<CSingleLayerCell*>(result)->serial(f);
301 break;
302 case MultiLayer:
303 result = new CMultiLayerCell(worldMap);
304 static_cast<CMultiLayerCell*>(result)->serial(f);
305 break;
306 default:
307 nlassert(false);
308 nlwarning("Unknown type of cell %d to load, abort", type);
309 return result;
310 break;
311 }
312
313 // allow us to optimize access.
314 f.serialCont(result->_TopologiesNodes);
315
316 return result;
317 }
318
319 void CRootCell::save(NLMISC::IStream& f, CRootCell* cell)
320 {
321 if (dynamic_cast<CComputeCell*>(cell) != NULL)
322 {
323 TCellType type = Compute;
324 f.serialEnum(type);
325 static_cast<CComputeCell*>(cell)->serial(f);
326 }
327 else if (dynamic_cast<CWhiteCell*>(cell) != NULL)
328 {
329 TCellType type = White;
330 f.serialEnum(type);
331 static_cast<CWhiteCell*>(cell)->serial(f);
332 }
333 else if (dynamic_cast<CSingleLayerCell*>(cell) != NULL)
334 {
335 TCellType type = SingleLayer;
336 f.serialEnum(type);
337 static_cast<CSingleLayerCell*>(cell)->serial(f);
338 }
339 else if (dynamic_cast<CMultiLayerCell*>(cell) != NULL)
340 {
341 TCellType type = MultiLayer;
342 f.serialEnum(type);
343 static_cast<CMultiLayerCell*>(cell)->serial(f);
344 }
345 else
346 {
347 nlassert(false);
348 nlwarning("Unknown type of cell to save, abort");
349 return;
350 }
351
352 f.serialCont(cell->_TopologiesNodes);
353 }
354
355 //////////////////////////////////////////////////////////////////////////////
356 // CComputeCell //
357 //////////////////////////////////////////////////////////////////////////////
358
359 void CComputeCell::serial(NLMISC::IStream& f)
360 {
361 // Version
362 // 0: initial version
363 uint version = f.serialVersion(0);
364
365 for (uint32 i=0; i<16*16; ++i)
366 for (uint32 k=0; k<3; ++k)
367 f.serial(_Grid[i][k]);
368 }
369
370 //////////////////////////////////////////////////////////////////////////////
371 // CSingleLayerCell //
372 //////////////////////////////////////////////////////////////////////////////
373
374 bool CSingleLayerCell::_Initialized = false;
375 uint16 CSingleLayerCell::_MaskMap[16];
376
377 void CSingleLayerCell::serial(NLMISC::IStream& f)
378 {
379 f.serialCheck(NELID16("SL"));
380
381 uint i;
382 for (i=0; i<16; ++i)
383 f.serial(_Map[i]);
384
385 f.serial(_SLinks);
386 f.serial(_NLinks);
387 f.serial(_ELinks);
388 f.serial(_WLinks);
389
390 if (f.isReading())
391 {
392 delete _Topologies;
393 delete _HeightMap;
394 _Topologies = I16x16Layer::load(f);
395 _HeightMap = I16x16Layer::load(f);
396 }
397 else
398 {
399 I16x16Layer::save(f, _Topologies);
400 I16x16Layer::save(f, _HeightMap);
401 }
402 }
403
404 //////////////////////////////////////////////////////////////////////////////
405 // CMultiLayerCell //
406 //////////////////////////////////////////////////////////////////////////////
407
408 void CMultiLayerCell::serial(NLMISC::IStream& f)
409 {
410 f.serialCheck(NELID16("ML"));
411
412 uint slot;
413
414 for (slot=0; slot<3; ++slot)
415 {
416 // delete layer if any previously
417 if (f.isReading())
418 {
419 if (_Layers[slot] != NULL)
420 delete _Layers[slot]->_HeightMap;
421 delete _Layers[slot];
422 _Layers[slot] = NULL;
423 }
424
425 bool present = (_Layers[slot] != NULL);
426 f.serial(present);
427
428 if (present)
429 {
430 if (f.isReading())
431 {
432 _Layers[slot] = new CCellLayer();
433 _Layers[slot]->_HeightMap = I16x16Layer::load(f);
434 }
435 else
436 {
437 nlassert(_Layers[slot]);
438 I16x16Layer::save(f, _Layers[slot]->_HeightMap);
439 }
440
441 nlassert(_Layers[slot] != NULL);
442
443 for (uint32 i=0; i<16*16; ++i)
444 {
445 f.serial(_Layers[slot]->_Layer[i]);
446 f.serial(_Layers[slot]->_Topology[i]);
447 }
448 }
449 }
450 }
451
452 //////////////////////////////////////////////////////////////////////////////
453 // CSuperCell //
454 //////////////////////////////////////////////////////////////////////////////
455
456 void CSuperCell::serial(NLMISC::IStream& f)
457 {
458 // Version
459 // 0: initial version
460 uint version = f.serialVersion(0);
461
462 if (f.isReading())
463 {
464 for (uint32 i=0; i<16*16; ++i)
465 {
466 bool present;
467 f.serial(present);
468
469 if (_Grid[i] != NULL)
470 delete _Grid[i];
471
472 if (present)
473 _Grid[i] = CRootCell::load(f,_WorldMap);
474 }
475 }
476 else
477 {
478 for (uint32 i=0; i<16*16; ++i)
479 {
480 bool present = (_Grid[i] != NULL);
481 f.serial(present);
482
483 if (present)
484 CRootCell::save(f, _Grid[i]);
485 }
486 }
487 }
488
489 void CSuperCell::updateTopologyRef(CWorldMap* worldMap)
490 {
491 for (uint32 i=0; i<16*16; ++i)
492 {
493 if (_Grid[i])
494 _Grid[i]->updateTopologyRef (worldMap);
495 }
496 }
497
498 void CSuperCell::countCells(uint& compute, uint& white, uint& simple, uint& multi, uint& other) const
499 {
500 for (uint32 i=0; i<16*16; ++i)
501 {
502 if (!_Grid[i])
503 continue;
504 if (dynamic_cast<const CWhiteCell*>(_Grid[i]) != NULL)
505 ++white;
506 else if (dynamic_cast<const CSingleLayerCell*>(_Grid[i]) != NULL)
507 ++simple;
508 else if (dynamic_cast<const CComputeCell*>(_Grid[i]) != NULL)
509 ++compute;
510 else if (dynamic_cast<const CMultiLayerCell*>(_Grid[i]) != NULL)
511 ++multi;
512 else
513 ++other;
514 }
515 }
516
517 //////////////////////////////////////////////////////////////////////////////
518 // CWorldMap //
519 //////////////////////////////////////////////////////////////////////////////
520
521 void CWorldMap::getBounds(CMapPosition& min, CMapPosition& max)
522 {
523 uint i, j;
524 uint mini = 256, maxi = 0, minj = 256, maxj = 0;
525
526 for (i=0; i<256; ++i)
527 {
528 for (j=0; j<256; ++j)
529 {
530 if (_GridFastAccess[i*256+j])
531 {
532 if (i < mini) mini = i;
533 if (i > maxi) maxi = i;
534 if (j < minj) minj = j;
535 if (j > maxj) maxj = j;
536 }
537 }
538 }
539
540 min = CMapPosition(CMapCoord(minj, 0, 0), CMapCoord(mini, 0, 0) );
541 max = CMapPosition(CMapCoord(maxj+1, 0, 0), CMapCoord(maxi+1, 0, 0) );
542 }
543
544 void CWorldMap::clear()
545 {
546 for (uint i=0;i<65536;i++)
547 {
548 if (_GridFastAccess[i])
549 {
550 delete _GridFastAccess[i];
551 _GridFastAccess[i]=NULL;
552 }
553
554 }
555
556 }
557
558
559 void CWorldMap::serial(NLMISC::IStream &f)
560 {
561 f.serialCheck(NELID("WMAP"));
562
563 // Version
564 // 0: initial version
565 uint version = f.serialVersion(0);
566
567 if (f.isReading())
568 {
569 uint32 i;
570 for (i=0;i<65536;i++)
571 {
572 bool present;
573 f.serial(present);
574
575 if (present)
576 {
577 CSuperCell *scell = _GridFastAccess[i];
578 if (!scell)
579 _GridFastAccess[i] = scell =new CSuperCell(*this);
580 f.serial(*scell);
581 }
582
583 }
584
585 // made to update RootCell pointers in TTopologyRef ..
586 for (i=0;i<65536;i++)
587 {
588 CSuperCell *scell = _GridFastAccess[i];
589 if (scell)
590 scell->updateTopologyRef (this);
591 }
592
593 // made to calculate some random pos ..
594 {
595 CMapPosition min, max;
596 getBounds(min, max);
597 CMapPosition scan, scanline;
598 NLMISC::CRandom random;
599
600 for (scan = min; scan.y() != max.y(); scan = scan.stepCell(0, 1))
601 {
602 for (scanline = scan; scanline.x() != max.x(); scanline = scanline.stepCell(1, 0))
603 {
604 CRootCell *rootCell=getRootCell(scanline);
605
606 if (!rootCell)
607 continue;
608
609 CMapPosition pos(scanline.x(),0xffff0000|scanline.y());
610
611 uint ind=0;
612 uint maxTries=256;
613
614 for (;ind<4 && maxTries>0;maxTries--)
615 {
616 CWorldPosition wpos;
617
618 uint i= uint32(random.rand()) & 0xf;
619 uint j= uint32(random.rand()) & 0xf;
620 #ifdef NL_DEBUG
621 nlassert(i<16 && j<16);
622 #endif
623 pos.setUnitId(i,j);
624 CAIVector vecPos=CAIVector(pos);
625 if (setWorldPosition (AITYPES::vp_auto, wpos, vecPos))
626 {
627 #ifdef NL_DEBUG
628 nlassert(wpos.getRootCell()==rootCell);
629 nlassert(wpos.y()<=0 && wpos.x()>=0);
630 #endif
631 rootCell->setWorldPosition(wpos, ind);
632 ind++;
633 }
634
635 }
636
637 // if we have found some valid positions but not all, fill the array with the last pos found.
638 if (ind<4 && ind>0)
639 {
640 while (ind<4)
641 {
642 rootCell->setWorldPosition(rootCell->getWorldPosition(ind-1), ind);
643 ind++;
644 }
645
646 }
647
648 }
649
650 }
651
652 }
653
654 }
655 else
656 {
657 for (uint32 i=0;i<65536;i++)
658 {
659 bool present = (_GridFastAccess[i]!=NULL);
660 f.serial(present);
661
662 if (present)
663 {
664 //nldebug("Save SuperCell %d/%d", i, j);
665 nlassert(_GridFastAccess[i]);
666 f.serial(*(_GridFastAccess[i]));
667 }
668
669 }
670
671 }
672
673 }
674
675 void CWorldMap::setFlagOnPosAndRadius(const CMapPosition &pos,float radius, uint32 flag)
676 {
677 float minx=pos.x()-radius;
678 float maxx=pos.x()+radius;
679
680 float miny=pos.y()-radius;
681 float maxy=pos.y()+radius;
682
683 const float radius2=radius*radius;
684
685 for (float ty=miny;ty<=maxy;ty++)
686 {
687 const float dy=ty-pos.y();
688 for (float tx=minx;tx<=maxx;tx++)
689 {
690 const float dx=tx-pos.x();
691
692 if ((dy*dy+dx*dx)>radius2)
693 continue;
694
695 CRootCell *rootCell=getRootCell(CMapPosition((int)tx,(int)ty));
696 if (!rootCell)
697 continue;
698 rootCell->setFlag(flag);
699 }
700
701 }
702
703 }
704
705 void CWorldMap::countCells(uint &compute, uint &white, uint &simple, uint &multi, uint &other) const
706 {
707 for (uint32 i=0; i<65536; ++i)
708 {
709 if (_GridFastAccess[i])
710 _GridFastAccess[i]->countCells(compute, white, simple, multi, other);
711 }
712
713 // uint i, j;
714 // for (i=0; i<256; ++i)
715 // for (j=0; j<256; ++j)
716 // if (_Grid[i][j] != NULL)
717 // _Grid[i][j]->countCells(compute, white, simple, multi, other);
718 }
719
720 //
721 CNeighbourhood CWorldMap::neighbours(const CWorldPosition &wpos) const
722 {
723 CNeighbourhood neighbs;
724 const CCellLinkage lnks=wpos.getCellLinkage();
725
726 if (lnks.isSSlotValid())
727 {
728 neighbs.set(CDirection::S);
729
730 const CCellLinkage &nlnk = wpos.getPosS().getCellLinkage(); //CWorldPosition(wpos.getPosS(),lnks.NSlot()));
731 if (nlnk.isESlotValid())
732 neighbs.set(CDirection::SE);
733 if (nlnk.isWSlotValid())
734 neighbs.set(CDirection::SW);
735 }
736
737 if (lnks.isNSlotValid())
738 {
739 neighbs.set(CDirection::N);
740
741 const CCellLinkage &slnk = wpos.getPosN().getCellLinkage();
742 if (slnk.isESlotValid())
743 neighbs.set(CDirection::NE);
744 if (slnk.isWSlotValid())
745 neighbs.set(CDirection::NW);
746 }
747
748 if (lnks.isESlotValid())
749 {
750 neighbs.set(CDirection::E);
751
752 const CCellLinkage &elnk = wpos.getPosE().getCellLinkage();
753 if (elnk.isSSlotValid())
754 neighbs.set(CDirection::SE);
755 if (elnk.isNSlotValid())
756 neighbs.set(CDirection::NE);
757 }
758
759 if (lnks.isWSlotValid())
760 {
761 neighbs.set(CDirection::W);
762
763 const CCellLinkage &wlnk = wpos.getPosW().getCellLinkage();
764 if (wlnk.isSSlotValid())
765 neighbs.set(CDirection::SW);
766 if (wlnk.isNSlotValid())
767 neighbs.set(CDirection::NW);
768 }
769 return neighbs;
770 }
771
772
773 //
774 bool CWorldMap::customCheckDiagMove(const CWorldPosition &pos, const CDirection &direction, TAStarFlag denyFlags) const
775 {
776 H_AUTO(AI_WorldMap_move);
777 // get straight links
778 const CCellLinkage &lnk = pos.getCellLinkage();
779
780 switch (direction.getVal())
781 {
782 case CDirection::SE:
783 {
784 {
785 CWorldPosition tmpPos(pos);
786 if (!tmpPos.getCellLinkage().isSSlotValid())
787 return false;
788
789 tmpPos=tmpPos.getPosS();
790 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
791 return false;
792
793 if (!tmpPos.getCellLinkage().isESlotValid())
794 return false;
795
796 tmpPos=tmpPos.getPosE();
797 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
798 return false;
799 }
800
801 {
802 CWorldPosition tmpPos(pos);
803 if (!tmpPos.getCellLinkage().isESlotValid())
804 return false;
805
806 tmpPos=tmpPos.getPosE();
807 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
808 return false;
809
810 if (!tmpPos.getCellLinkage().isSSlotValid())
811 return false;
812
813 // tmpPos=tmpPos.getPosS();
814 // if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
815 // return false;
816 }
817 return true;
818 }
819
820 case CDirection::NE:
821 {
822 {
823 CWorldPosition tmpPos(pos);
824 if (!tmpPos.getCellLinkage().isNSlotValid())
825 return false;
826
827 tmpPos=tmpPos.getPosN();
828 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
829 return false;
830
831 if (!tmpPos.getCellLinkage().isESlotValid())
832 return false;
833
834 tmpPos=tmpPos.getPosE();
835 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
836 return false;
837 }
838
839 {
840 CWorldPosition tmpPos(pos);
841 if (!tmpPos.getCellLinkage().isESlotValid())
842 return false;
843
844 tmpPos=tmpPos.getPosE();
845 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
846 return false;
847
848 if (!tmpPos.getCellLinkage().isNSlotValid())
849 return false;
850
851 // tmpPos=tmpPos.getPosN();
852 // if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
853 // return false;
854 }
855 return true;
856 }
857 case CDirection::NW:
858 {
859 {
860 CWorldPosition tmpPos(pos);
861 if (!tmpPos.getCellLinkage().isNSlotValid())
862 return false;
863
864 tmpPos=tmpPos.getPosN();
865 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
866 return false;
867
868 if (!tmpPos.getCellLinkage().isWSlotValid())
869 return false;
870
871 tmpPos=tmpPos.getPosW();
872 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
873 return false;
874 }
875
876 {
877 CWorldPosition tmpPos(pos);
878 if (!tmpPos.getCellLinkage().isWSlotValid())
879 return false;
880
881 tmpPos=tmpPos.getPosW();
882 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
883 return false;
884
885 if (!tmpPos.getCellLinkage().isNSlotValid())
886 return false;
887
888 // tmpPos=tmpPos.getPosN();
889 // if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
890 // return false;
891 }
892 return true;
893 }
894 case CDirection::SW:
895 {
896 {
897 CWorldPosition tmpPos(pos);
898 if (!tmpPos.getCellLinkage().isSSlotValid())
899 return false;
900
901 tmpPos=tmpPos.getPosS();
902 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
903 return false;
904
905 if (!tmpPos.getCellLinkage().isWSlotValid())
906 return false;
907
908 tmpPos=tmpPos.getPosW();
909 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
910 return false;
911 }
912
913 {
914 CWorldPosition tmpPos(pos);
915 if (!tmpPos.getCellLinkage().isWSlotValid())
916 return false;
917
918 tmpPos=tmpPos.getPosW();
919 if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
920 return false;
921
922 if (!tmpPos.getCellLinkage().isSSlotValid())
923 return false;
924
925 // tmpPos=tmpPos.getPosS();
926 // if ((tmpPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0)
927 // return false;
928 }
929 return true;
930 }
931 break;
932 default:
933 break;
934
935 }
936 return false;
937 }
938
939 /*
940 bool CWorldMap::customCheckDiagMove(const CWorldPosition &pos, const CDirection &direction, TAStarFlag denyFlags) const
941 {
942 H_AUTO(AI_WorldMap_move);
943 // get straight links
944 const CCellLinkage &lnk = pos.getCellLinkage();
945
946 switch (direction.getVal())
947 {
948 case CDirection::SE:
949 {
950 if (!lnk.isSSlotValid())
951 return false;
952 if (!lnk.isESlotValid())
953 return false;
954
955 return ( pos.getPosS().getCellLinkage().isESlotValid()
956 || pos.getPosE().getCellLinkage().isSSlotValid());
957 }
958
959 case CDirection::NE:
960 {
961 if (!lnk.isNSlotValid())
962 return false;
963 if (!lnk.isESlotValid())
964 return false;
965
966 return ( pos.getPosN().getCellLinkage().isESlotValid()
967 || pos.getPosE().getCellLinkage().isNSlotValid());
968 }
969 case CDirection::NW:
970 {
971 if (!lnk.isNSlotValid())
972 return false;
973 if (!lnk.isWSlotValid())
974 return false;
975
976 return ( pos.getPosN().getCellLinkage().isWSlotValid()
977 || pos.getPosW().getCellLinkage().isNSlotValid());
978 }
979 case CDirection::SW:
980 {
981 if (!lnk.isSSlotValid())
982 return false;
983 if (!lnk.isWSlotValid())
984 return false;
985
986 return ( pos.getPosS().getCellLinkage().isWSlotValid()
987 || pos.getPosW().getCellLinkage().isSSlotValid());
988 }
989
990 }
991 return false;
992 }
993 */
994
995 //
996 bool CWorldMap::move(CWorldPosition &pos, const CDirection &direction) const
997 {
998 H_AUTO(AI_WorldMap_move);
999 // get straight links
1000 const CCellLinkage &lnk = pos.getCellLinkage();
1001
1002 switch (direction.getVal())
1003 {
1004 case CDirection::S:
1005 {
1006 if (lnk.isSSlotValid())
1007 {
1008 pos.stepS();
1009 return true;
1010 }
1011 return false;
1012 }
1013 case CDirection::SE:
1014 {
1015 if (lnk.isSSlotValid())
1016 {
1017 const CWorldPosition temp(pos.getPosS());
1018 if (temp.getCellLinkage().isESlotValid())
1019 {
1020 temp.setPosE(pos);
1021 return true;
1022 }
1023 }
1024
1025 if (lnk.isESlotValid())
1026 {
1027 const CWorldPosition temp(pos.getPosE());
1028 if (temp.getCellLinkage().isSSlotValid())
1029 {
1030 temp.setPosS(pos);
1031 return true;
1032 }
1033 }
1034 return false;
1035 }
1036 case CDirection::E:
1037 {
1038 if (lnk.isESlotValid())
1039 {
1040 pos.stepE();
1041 return true;
1042 }
1043 return false;
1044 }
1045 case CDirection::NE:
1046 {
1047 if (lnk.isESlotValid())
1048 {
1049 const CWorldPosition temp(pos.getPosE());
1050 if (temp.getCellLinkage().isNSlotValid())
1051 {
1052 temp.setPosN(pos);
1053 return true;
1054 }
1055
1056 }
1057
1058 if (lnk.isNSlotValid())
1059 {
1060 const CWorldPosition temp(pos.getPosN());
1061 if (temp.getCellLinkage().isESlotValid())
1062 {
1063 temp.setPosE(pos);
1064 return true;
1065 }
1066 }
1067
1068 return false;
1069 }
1070 case CDirection::N:
1071 {
1072 if (lnk.isNSlotValid())
1073 {
1074 pos.stepN();
1075 return true;
1076 }
1077 return false;
1078 }
1079 case CDirection::NW:
1080 {
1081 if (lnk.isWSlotValid())
1082 {
1083 const CWorldPosition temp(pos.getPosW());
1084 if (temp.getCellLinkage().isNSlotValid())
1085 {
1086 temp.setPosN(pos);
1087 return true;
1088 }
1089 }
1090
1091 if (lnk.isNSlotValid())
1092 {
1093 const CWorldPosition temp(pos.getPosN());
1094 if (temp.getCellLinkage().isWSlotValid())
1095 {
1096 temp.setPosW(pos);
1097 return true;
1098 }
1099 }
1100
1101 return false;
1102 }
1103 case CDirection::W:
1104 {
1105 if (lnk.isWSlotValid())
1106 {
1107 pos.stepW();
1108 return true;
1109 }
1110 return false;
1111 }
1112 case CDirection::SW:
1113 {
1114 if (lnk.isSSlotValid())
1115 {
1116 const CWorldPosition temp(pos.getPosS());
1117 if (temp.getCellLinkage().isWSlotValid())
1118 {
1119 temp.setPosW(pos);
1120 return true;
1121 }
1122 }
1123
1124 if (lnk.isWSlotValid())
1125 {
1126 const CWorldPosition temp(pos.getPosW());
1127 if (temp.getCellLinkage().isSSlotValid())
1128 {
1129 temp.setPosS(pos);
1130 return true;
1131 }
1132
1133 }
1134 return false;
1135 }
1136 default:
1137 break;
1138
1139 }
1140 return false;
1141 }
1142
1143 //
1144 bool CWorldMap::moveSecure(CWorldPosition &pos, const CDirection &direction, uint16 maskFlags) const
1145 {
1146 H_AUTO(AI_WorldMap_moveSecure);
1147 // get straight links
1148
1149 uint16 pflags = pos.getFlags();
1150
1151 switch (direction.getVal())
1152 {
1153 case CDirection::S:
1154 {
1155 return pos.moveS();
1156 }
1157 case CDirection::SE:
1158 {
1159 CWorldPosition p1(pos), p2(pos);
1160 if (p1.moveS() && (((p1.getFlags()^pflags)&maskFlags) == 0) && p1.moveE() && (((p1.getFlags()^pflags)&maskFlags) == 0) &&
1161 p2.moveE() && (((p2.getFlags()^pflags)&maskFlags) == 0) && p2.moveS() && (((p2.getFlags()^pflags)&maskFlags) == 0) &&
1162 p1 == p2)
1163 {
1164 pos = p1;
1165 return true;
1166 }
1167 break;
1168 }
1169 case CDirection::E:
1170 {
1171 return pos.moveE();
1172 }
1173 case CDirection::NE:
1174 {
1175 CWorldPosition p1(pos), p2(pos);
1176 if (p1.moveN() && (((p1.getFlags()^pflags)&maskFlags) == 0) && p1.moveE() && (((p1.getFlags()^pflags)&maskFlags) == 0) &&
1177 p2.moveE() && (((p2.getFlags()^pflags)&maskFlags) == 0) && p2.moveN() && (((p2.getFlags()^pflags)&maskFlags) == 0) &&
1178 p1 == p2)
1179 {
1180 pos = p1;
1181 return true;
1182 }
1183 break;
1184 }
1185 case CDirection::N:
1186 {
1187 return pos.moveN();
1188 }
1189 case CDirection::NW:
1190 {
1191 CWorldPosition p1(pos), p2(pos);
1192 if (p1.moveN() && (((p1.getFlags()^pflags)&maskFlags) == 0) && p1.moveW() && (((p1.getFlags()^pflags)&maskFlags) == 0) &&
1193 p2.moveW() && (((p2.getFlags()^pflags)&maskFlags) == 0) && p2.moveN() && (((p2.getFlags()^pflags)&maskFlags) == 0) &&
1194 p1 == p2)
1195 {
1196 pos = p1;
1197 return true;
1198 }
1199 break;
1200 }
1201 case CDirection::W:
1202 {
1203 return pos.moveW();
1204 }
1205 case CDirection::SW:
1206 {
1207 CWorldPosition p1(pos), p2(pos);
1208 if (p1.moveS() && (((p1.getFlags()^pflags)&maskFlags) == 0) && p1.moveW() && (((p1.getFlags()^pflags)&maskFlags) == 0) &&
1209 p2.moveW() && (((p2.getFlags()^pflags)&maskFlags) == 0) && p2.moveS() && (((p2.getFlags()^pflags)&maskFlags) == 0) &&
1210 p1 == p2)
1211 {
1212 pos = p1;
1213 return true;
1214 }
1215 break;
1216 }
1217 default:
1218 break;
1219 }
1220 return false;
1221 }
1222
1223 //
1224 bool CWorldMap::moveDiagTestBothSide(CWorldPosition &pos, const CDirection &direction) const
1225 {
1226 H_AUTO(AI_WorldMap_move);
1227 // get straight links
1228 const CCellLinkage &lnk = pos.getCellLinkage();
1229
1230 switch (direction.getVal())
1231 {
1232 case CDirection::S:
1233 {
1234 if (lnk.isSSlotValid())
1235 {
1236 pos.stepS();
1237 return true;
1238 }
1239 return false;
1240 }
1241 case CDirection::SE:
1242 {
1243 if (!lnk.isSSlotValid() || !lnk.isESlotValid())
1244 return false;
1245
1246 CSlot eSlot=pos.getPosS().getCellLinkage().ESlot();
1247 if (!eSlot.isValid())
1248 return false;
1249
1250 const CWorldPosition temp(pos.getPosE());
1251 if (temp.getCellLinkage().SSlot()!=eSlot)
1252 return false;
1253
1254 temp.setPosS(pos);
1255 return true;
1256 }
1257 case CDirection::E:
1258 {
1259 if (lnk.isESlotValid())
1260 {
1261 pos.stepE();
1262 return true;
1263 }
1264 return false;
1265 }
1266 case CDirection::NE:
1267 {
1268 if (!lnk.isNSlotValid() || !lnk.isESlotValid())
1269 return false;
1270
1271 CSlot eSlot=pos.getPosN().getCellLinkage().ESlot();
1272 if (!eSlot.isValid())
1273 return false;
1274
1275 const CWorldPosition temp(pos.getPosE());
1276 if (temp.getCellLinkage().NSlot()!=eSlot)
1277 return false;
1278
1279 temp.setPosN(pos);
1280 return true;
1281 }
1282 case CDirection::N:
1283 {
1284 if (lnk.isNSlotValid())
1285 {
1286 pos.stepN();
1287 return true;
1288 }
1289 return false;
1290 }
1291 case CDirection::NW:
1292 {
1293 if (!lnk.isNSlotValid() || !lnk.isWSlotValid())
1294 return false;
1295
1296 CSlot wSlot=pos.getPosN().getCellLinkage().WSlot();
1297 if (!wSlot.isValid())
1298 return false;
1299
1300 const CWorldPosition temp(pos.getPosW());
1301 if (temp.getCellLinkage().NSlot()!=wSlot)
1302 return false;
1303
1304 temp.setPosN(pos);
1305 return true;
1306 }
1307 case CDirection::W:
1308 {
1309 if (lnk.isWSlotValid())
1310 {
1311 pos.stepW();
1312 return true;
1313 }
1314 return false;
1315 }
1316 case CDirection::SW:
1317 {
1318 if (!lnk.isSSlotValid() || !lnk.isWSlotValid())
1319 return false;
1320
1321 CSlot wSlot=pos.getPosS().getCellLinkage().WSlot();
1322 if (!wSlot.isValid())
1323 return false;
1324
1325 const CWorldPosition temp(pos.getPosW());
1326 if (temp.getCellLinkage().SSlot()!=wSlot)
1327 return false;
1328
1329 temp.setPosS(pos);
1330 return true;
1331 }
1332 default:
1333 break;
1334 }
1335 return false;
1336 }
1337
1338
1339 void areCompatiblesWithoutStartRestriction(const CWorldPosition &startPos, const CWorldPosition& endPos, const TAStarFlag &denyflags, CCompatibleResult &res, bool allowStartRestriction)
1340 {
1341 res.setValid(false);
1342
1343 if (&startPos == NULL)
1344 {
1345 nlwarning("Invalid startPos (NULL)");
1346 return;
1347 }
1348
1349 if (&endPos == NULL)
1350 {
1351 nlwarning("Invalid endPos (NULL)");
1352 return;
1353 }
1354
1355 const CTopology &startTopoNode=startPos.getTopologyRef().getCstTopologyNode();
1356 const CTopology &endTopoNode=endPos.getTopologyRef().getCstTopologyNode();
1357 TAStarFlag startFlag=(TAStarFlag)(startTopoNode.getFlags()&WaterAndNogo);
1358 // if (!allowStartRestriction)
1359 startFlag=Nothing;
1360
1361
1362 for (TAStarFlag possibleFlag=Nothing;possibleFlag<=WaterAndNogo;possibleFlag=(TAStarFlag)(possibleFlag+2)) // tricky !! -> to replace with a defined list of flags to checks.
1363 {
1364 const uint32 incompatibilityFlags=(possibleFlag&(denyflags&~startFlag))&WaterAndNogo;
1365
1366 if (incompatibilityFlags)
1367 continue;
1368
1369 const uint32 startMasterTopo=startTopoNode.getMasterTopo(possibleFlag);
1370 const uint32 endMasterTopo=endTopoNode.getMasterTopo(possibleFlag);
1371 if ( (startMasterTopo^endMasterTopo)!=0
1372 || startMasterTopo == std::numeric_limits<uint32>::max()) // if not same masterTopo or invalid masterTopo then bypass ..
1373 continue;
1374
1375 res.set(possibleFlag, startMasterTopo);
1376 res.setValid();
1377
1378 if (((possibleFlag&denyflags)&WaterAndNogo)==0) // it was the optimal case ?
1379 break;
1380 }
1381
1382 }
1383
1384 //////////////////////////////////////////////////////////////////////////////
1385 // Path finding //
1386 //////////////////////////////////////////////////////////////////////////////
1387
1388 //#define CHECK_HEAP
1389 std::map<uint, uint> MapAStarNbSteps;
1390 uint LastAStarNbSteps = 0;
1391
1392 NLMISC_CATEGORISED_COMMAND(ais, dumpAStarSteps, "Dump the distribution of A* number of steps", "")
1393 {
1394 log.displayNL( "Distribution of the %u nb steps:", MapAStarNbSteps.size() );
1395 log.displayNL( "NbSteps\tNbOccurrences", MapAStarNbSteps.size() );
1396 for( std::map<uint, uint>::const_iterator first=MapAStarNbSteps.begin(), last=MapAStarNbSteps.end(); first!=last; ++first )
1397 {
1398 log.displayNL( "%u\t%u", first->first, first->second );
1399 }
1400 return true;
1401 }
1402
1403 bool CWorldMap::findAStarPath(CWorldPosition const& start, CWorldPosition const& end, std::vector<CTopology::TTopologyRef>& path, TAStarFlag denyflags) const
1404 {
1405 H_AUTO(findAStarPath1);
1406
1407 // Clear destination path
1408 path.clear();
1409
1410 // Check start position validity
1411 if (!start.isValid())
1412 {
1413 _LastFASPReason = FASPR_INVALID_START_POS;
1414 return false;
1415 }
1416 // Check end position validity
1417 if (!end.isValid())
1418 {
1419 _LastFASPReason = FASPR_INVALID_END_POS;
1420 return false;
1421 }
1422
1423 // Get start and end topologies
1424 CTopology::TTopologyRef startTopo = start.getTopologyRef();
1425 CTopology::TTopologyRef endTopo = end.getTopologyRef();
1426
1427 // Get associated topology nodes
1428 CTopology const& startTopoNode = startTopo.getCstTopologyNode();
1429 CTopology const& endTopoNode = endTopo.getCstTopologyNode();
1430
1431 // Check start point
1432 if (!startTopo.isValid())
1433 {
1434 _LastFASPReason = FASPR_INVALID_START_TOPO;
1435 return false;
1436 }
1437 // Check end point
1438 if (!endTopo.isValid())
1439 {
1440 _LastFASPReason = FASPR_INVALID_END_TOPO;
1441 return false;
1442 }
1443
1444 // Check compatibility of start and end points depending on flags to avoid
1445 RYAI_MAP_CRUNCH::CCompatibleResult res;
1446 areCompatiblesWithoutStartRestriction(start, end, denyflags, res, true);
1447 if (!res.isValid())
1448 {
1449 _LastFASPReason = FASPR_INCOMPATIBLE_POSITIONS;
1450 return false;
1451 }
1452
1453 // Get flags to use to compute the path
1454 TAStarFlag movementFlags = res.movementFlags();
1455 // Get the master topology inside which to compute the path (reminder: no path between different master topo)
1456 uint32 choosenMasterTopo=res.choosenMasterTopo();
1457
1458 // A list of A* nodes
1459 vector<CAStarHeapNode> nodes;
1460 // List of visited topologies, with associated node in 'nodes' vector
1461 map<CTopology::TTopologyId, uint> visited;
1462
1463 // The heap used to store A* nodes
1464 // :TODO: Check if STL heap is not better suited, or if another data structure would be more useful in AIS
1465 CHeap<float, uint> heap;
1466
1467 // Get end position
1468 CVector const& endPoint = endTopo.getCstTopologyNode().Position;
1469
1470 // Create a heap node for the start point
1471 CAStarHeapNode hnode(startTopo, 0xffffffff, 0.0f, true);
1472 // Push it in the node list
1473 nodes.push_back(hnode);
1474 // Take it as first father
1475 uint father = (uint)nodes.size()-1;
1476
1477 // Add start topology to visited nodes (father holds start topo node index for the moment)
1478 visited.insert(std::pair<CTopology::TTopologyId, uint>(startTopo, father));
1479 // Push start node in the heap with a zero cost
1480 heap.push(0.0f, father);
1481
1482 // Boolean to notify that end point has been reached
1483 bool found = false;
1484
1485 #ifdef CHECK_HEAP
1486 static uint32 maxHeap = 65535;
1487 static uint32 maxHeapMeasure = 0;
1488 #endif
1489
1490 uint nbHeapSteps = 0;
1491 while (!heap.empty())
1492 {
1493 #ifdef CHECK_HEAP
1494 if (heap.size()>maxHeap) // if too much calculs, not found (to remove when debugged).
1495 break;
1496 #endif
1497
1498 ++nbHeapSteps;
1499
1500 // Get best node (popping it)
1501 father = std::numeric_limits<uint>::max(); // :TODO: Remove that useless statement (since do while first loop ALWAYS overwrite it)
1502 do
1503 {
1504 father = heap.pop();
1505 }
1506 while (!nodes[father].isOpened() && !heap.empty());
1507
1508 if (father == std::numeric_limits<uint>::max())
1509 break;
1510
1511 // Mark current node as closed
1512 hnode.setOpen(false);
1513
1514 // Make best node the current one
1515 hnode = nodes[father];
1516
1517 // Get the current node itself
1518 CTopology::TTopologyRef const& current = hnode.getRef();
1519
1520 // If we reached the end node, stop search
1521 if (current==endTopo)
1522 {
1523 found=true;
1524 break;
1525 }
1526
1527 // Get current node topology
1528 CTopology const& ctp = current.getCstTopologyNode();
1529
1530 // Get g(n) for current node
1531 float dist = hnode.getDistance();
1532
1533 // Examine each neighbour of the current node
1534 for (vector<CTopology::CNeighbourLink>::const_iterator it=ctp.Neighbours.begin(), itEnd=ctp.Neighbours.end();it!=itEnd;++it)
1535 {
1536 // Get the neighbour topology node
1537 CTopology::CNeighbourLink const& neighbourLink = (*it);
1538 CTopology::TTopologyRef const& next = neighbourLink.getTopologyRef();
1539
1540 // If it's not in the same master topo skip it
1541 if (next.getCstTopologyNode().getMasterTopo(movementFlags)!=choosenMasterTopo)
1542 continue;
1543
1544 // Compute neighbour node g(n)
1545 float distance = dist + neighbourLink.getDistance();
1546
1547 uint child;
1548 // Check if node has already been visited
1549 map<CTopology::TTopologyId, uint>::iterator itv = visited.find(next);
1550 if (itv!=visited.end())
1551 {
1552 // Assume child is that node
1553 child = (*itv).second;
1554 // If that node's previous distance is better than the new one skip it
1555 if (nodes[child].getDistance() <= distance)
1556 continue;
1557
1558 // Close the old node
1559 nodes[child].setOpen(false);
1560 // Remove it from visited
1561 visited.erase(itv);
1562 }
1563 // Create a new node for that cell
1564 child = (uint)nodes.size();
1565 nodes.push_back(CAStarHeapNode(next, father, distance, true));
1566 // Compute h(n) as an euclidian distance heuristic
1567 float heuristic = (endPoint-next.getCstTopologyNode().Position).norm();
1568 // Add node to heap with a computed f(n)=g(n)+h(n)
1569 heap.push(distance + heuristic, child);
1570 // Add node to visited
1571 visited.insert(std::pair<CTopology::TTopologyId, uint>(next, child));
1572 }
1573 }
1574
1575 #ifdef CHECK_HEAP
1576 if (heap.size()>maxHeapMeasure)
1577 {
1578 maxHeapMeasure=heap.size();
1579 }
1580 #endif
1581
1582 ++MapAStarNbSteps[nbHeapSteps];
1583 LastAStarNbSteps = nbHeapSteps;
1584
1585 #ifdef NL_DEBUG
1586 nlassert(found);
1587 #else
1588 if (!found)
1589 {
1590 nlwarning("(!!Appeler StepH!!)Path not found from %s : %d to %s : %d", start.toString().c_str(), start.slot(), end.toString().c_str(), end.slot());
1591 }
1592 #endif
1593
1594 // If not found, return error
1595 if (!found)
1596 {
1597 _LastFASPReason = FASPR_NOT_FOUND;
1598 return false;
1599 }
1600
1601 // Backtrack path
1602 while (father != 0xffffffff)
1603 {
1604 CAStarHeapNode const& node = nodes[father];
1605 path.push_back(node.getRef());
1606 father = node.getFather();
1607 }
1608
1609 // Reverse path container
1610 std::reverse(path.begin(), path.end());
1611
1612 _LastFASPReason = FASPR_NO_ERROR;
1613 return true;
1614 }
1615
1616 // Finds an A* path
1617 bool CWorldMap::findAStarPath(const CTopology::TTopologyId &start, const CTopology::TTopologyId &end, CAStarPath &path, TAStarFlag denyflags) const
1618 {
1619 H_AUTO(findAStarPath2)
1620 path._TopologiesPath.clear();
1621
1622 CTopology::TTopologyRef startTopo = getTopologyRef(start);
1623 CTopology::TTopologyRef endTopo = getTopologyRef(end);
1624
1625 // if not found start point or end point, abort
1626 if (!startTopo.isValid() || !endTopo.isValid())
1627 return false;
1628
1629 vector<CAStarHeapNode> nodes;
1630 map<CTopology::TTopologyId, uint> visited; // topology + node index in vector
1631 CHeap<float, uint> heap;
1632
1633 const CVector &endPoint = endTopo.getCstTopologyNode().Position;
1634
1635 // add current to heap
1636 CAStarHeapNode hnode(startTopo,0xffffffff,0.0f,true);
1637
1638 nodes.push_back(hnode);
1639 uint father = (uint)nodes.size()-1;
1640
1641 // add current to visited nodes
1642 visited.insert(std::pair<CTopology::TTopologyId, uint>(startTopo, father));
1643 heap.push(0.0f, father);
1644
1645 bool found=false;
1646
1647 while (!heap.empty())
1648 {
1649 // pop best node
1650 father = heap.pop();
1651 hnode = nodes[father];
1652
1653 const CTopology::TTopologyRef &current = hnode.getRef();
1654
1655 // if reached end node, leave
1656 if (current==endTopo)
1657 {
1658 found=true;
1659 break;
1660 }
1661
1662 const CTopology &ctp = current.getCstTopologyNode();
1663 float dist = hnode.getDistance();
1664
1665 for (uint i=0; i<ctp.Neighbours.size(); ++i)
1666 {
1667 const CTopology::CNeighbourLink &neightBourgLink=ctp.Neighbours[i];
1668
1669 const CTopology::TTopologyRef &next=neightBourgLink.getTopologyRef();
1670
1671 const CTopology &ntp = next.getCstTopologyNode();
1672
1673 // don't examine not accessible nodes
1674 if ((ntp.Flags & denyflags) != 0)
1675 continue;
1676
1677 // compute actual node distance
1678 float distance = dist + neightBourgLink.getDistance();
1679
1680 // if node is open or closed and previous visit has shorter path, skip node
1681 map<CTopology::TTopologyId, uint>::iterator itv = visited.find(next);
1682 if (itv != visited.end() && nodes[(*itv).second].getDistance() <= distance)
1683 continue;
1684
1685 // compute heuristic
1686 float heuristic = distance + (endPoint-ntp.Position).norm();
1687
1688 // setup node
1689 CAStarHeapNode cnode(next,father,distance,true);
1690 uint child;
1691
1692 // setup node
1693 if (itv == visited.end())
1694 {
1695 // if node is not open nor closed, create an entry
1696 child = (uint)nodes.size();
1697 nodes.push_back(cnode);
1698 }
1699 else
1700 {
1701 // else recover previous entry -- reopen node
1702 child = (*itv).second;
1703 nodes[child]=cnode;
1704 }
1705
1706 // add node to visited and to heap
1707 heap.push(heuristic, child);
1708 visited.insert(std::pair<CTopology::TTopologyId, uint>(next, child));
1709 }
1710 }
1711
1712 // if not found, return error
1713 if (!found)
1714 return false;
1715
1716 // backtrack path
1717 while (father != 0xffffffff)
1718 {
1719 const CAStarHeapNode& node=nodes[father];
1720
1721 path._TopologiesPath.push_back(node.getRef());
1722 father = node.getFather();
1723 }
1724
1725 // reverse path
1726 reverse(path._TopologiesPath.begin(), path._TopologiesPath.end());
1727
1728 return true;
1729 }
1730
1731
1732 // This whole routine MUST be optimized !! Its slow .. (to much).
1733 bool CWorldMap::findInsideAStarPath(CWorldPosition const& start, CWorldPosition const& end, std::vector<CDirection>& stepPath, TAStarFlag denyflags) const
1734 {
1735 H_AUTO(findInsideAStarPath);
1736
1737 // Check start and end position validity
1738 if (!start.isValid())
1739 {
1740 _LastFIASPReason = FIASPR_INVALID_START_POS;
1741 return false;
1742 }
1743 if (!end.isValid())
1744 {
1745 _LastFIASPReason = FIASPR_INVALID_END_POS;
1746 return false;
1747 }
1748 // Verify that they are in the same topology
1749 if (start.getTopologyRef()!=end.getTopologyRef())
1750 {
1751 _LastFIASPReason = FIASPR_DIFFERENT_TOPO;
1752 return false;
1753 }
1754
1755 // A list of A* nodes
1756 vector<CInsideAStarHeapNode> nodes;
1757 // List of visited nodes, with associated node index in 'nodes' vector
1758 map<CAStarNode, uint> visited;
1759 // The heap used to store A* nodes
1760 // :TODO: Check if STL heap is not better suited, or if another data structure would be more useful in AIS
1761 CHeap<float, uint> heap;
1762
1763 // Get end point
1764 CVector endPoint = end.toVectorD();
1765 // Build a node for the end point
1766 CAStarNode endId(end);
1767 // Build a node for the start point
1768 CAStarNode startNode(start);
1769
1770 // Create a heap node for the start point and push it in the node list
1771 nodes.push_back(CInsideAStarHeapNode(startNode, 0xffffffff, CDirection(), 0.f, true));
1772 // Take it as first father
1773 uint father = (uint)nodes.size()-1;
1774
1775 // Add start node to visited nodes (father holds start node index for the moment)
1776 visited.insert(std::pair<CAStarNode, uint>(startNode, father));
1777 // Push start node in the heap with a zero cost
1778 heap.push(0.0f, father);
1779
1780 // Boolean to notify that end point has been reached
1781 bool found = false;
1782
1783 while (!heap.empty())
1784 {
1785 // Get best node (popping it)
1786 father = heap.pop();
1787 // Get associated heap node
1788 CInsideAStarHeapNode& hnode = nodes[father];
1789 // Get associated A* node
1790 CAStarNode const& current = hnode.getNode();
1791
1792 // If we reached the end node, stop search
1793 if (current==endId)
1794 {
1795 found=true;
1796 break;
1797 }
1798
1799 // Get g(n) for current node
1800 float dist = hnode.getDistance();
1801
1802 // Get current node slot
1803 CSlot slot = current.slot();
1804 // Compute a map position
1805 CMapPosition pos = start; // The map has the same cell than the start pos (coz in same topo)
1806 current.updateMapPosition(pos); // Just update the unit id
1807
1808 // For each neighbour (8 directions)
1809 CNeighbourhood neighbourhood = neighbours(getWorldPosition(pos,slot));
1810 for (uint i=0; i<8; ++i)
1811 {
1812 // Compute a CDirection
1813 CDirection dir((CDirection::TDirection)i);
1814
1815 // If neighbour in that direction is not valid skip it
1816 if (!neighbourhood.isValid(dir))
1817 continue;
1818
1819 // :TODO: Continue documentation
1820 // If we cannot move in that direction skip it
1821 CWorldPosition mv(getWorldPosition(pos, slot));
1822 if (!moveDiagTestBothSide(mv, dir))
1823 continue;
1824
1825 // If that new point is not in the same cell skip it
1826 if (!mv.hasSameFullCellId(start))
1827 continue;
1828
1829 // If that point's flags are not compatible skip it
1830 if ((denyflags & mv.getTopologyRef().getCstTopologyNode().getFlags()) != 0)
1831 continue;
1832
1833 // Build an A* node
1834 CAStarNode next(mv);
1835
1836 // Compute g(n) (diagonal)
1837 float distance = dist + (((i & 1) != 0) ? 1.4142f : 1.0f);
1838
1839 // If node has already been visited and previous distance was better skip it
1840 map<CAStarNode, uint>::iterator itv = visited.find(next);
1841 if ( itv != visited.end()
1842 && nodes[(*itv).second].getDistance() <= distance )
1843 continue;
1844
1845 uint child;
1846 // If node has already been visited update it
1847 if (itv!=visited.end())
1848 {
1849 child = (*itv).second;
1850 nodes[child] = CInsideAStarHeapNode(next, father, dir, distance, true);
1851 }
1852 // Else create a new node
1853 else
1854 {
1855 child = (uint)nodes.size();
1856 nodes.push_back(CInsideAStarHeapNode(next, father, dir, distance, true));
1857 }
1858 // Compute h(n) as an euclidian distance heuristic
1859 float heuristic = (endPoint-mv.toVectorD()).norm();
1860 // Add node to heap with a computed f(n)=g(n)+h(n)
1861 heap.push(distance + heuristic, child);
1862 // Add node to visited
1863 visited.insert(std::pair<CAStarNode, uint>(next, child));
1864 }
1865 }
1866
1867 #ifdef NL_DEBUG
1868 nlassert(found);
1869 #endif
1870 // If not found, return error
1871 if (!found)
1872 {
1873 _LastFIASPReason = FIASPR_NOT_FOUND;
1874 return false;
1875 }
1876
1877 stepPath.clear();
1878
1879 // Backtrack path
1880 while (father != 0xffffffff)
1881 {
1882 if (nodes[father].getFather() != 0xffffffff)
1883 stepPath.push_back(nodes[father].getDirection());
1884 father = nodes[father].getFather();
1885 }
1886
1887 // Reverse path container
1888 std::reverse(stepPath.begin(), stepPath.end());
1889
1890 _LastFIASPReason = FIASPR_NO_ERROR;
1891 return true;
1892 }
1893
1894 //////////////////////////////////////////////////////////////////////////////
1895 // //
1896 //////////////////////////////////////////////////////////////////////////////
1897
1898 bool CWorldMap::moveTowards(CWorldPosition& pos, CTopology::TTopologyRef const& topology) const
1899 {
1900 CGridDirectionLayer const* layer = getGridDirectionLayer(pos, topology);
1901 if (!layer)
1902 return false;
1903
1904 CDirection motion=layer->getDirection(pos);
1905 if (!motion.isValid())
1906 return false;
1907
1908 return move(pos,motion);
1909 }
1910
1911 // Moves according a to a given path, returns false if failed
1912 bool CWorldMap::move(CWorldPosition &pos, CAStarPath &path, uint &currentstep) const
1913 {
1914 if (currentstep >= path._TopologiesPath.size())
1915 return false;
1916
1917 CTopology::TTopologyRef cid(pos);
1918
1919 if (!cid.isValid())
1920 return false;
1921
1922 if (cid==path._TopologiesPath[currentstep])
1923 {
1924 ++currentstep;
1925 if (currentstep==path._TopologiesPath.size())
1926 return false;
1927 }
1928 return moveTowards(pos, path._TopologiesPath[currentstep]);
1929 }
1930
1931
1932 // Moves from a position to another
1933 bool CWorldMap::move(CWorldPosition& pos, CMapPosition const& end, TAStarFlag const denyFlags) const
1934 {
1935 CWorldPosition tempPos(pos);
1936 BOMB_IF((tempPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0, "Error in CWorldMap::mode, invalid flag "<<RYAI_MAP_CRUNCH::toString(tempPos.getTopologyRef().getCstTopologyNode().getFlags())
1937 <<"on world pos "<<pos.toString()<<" while going to map pos "<<end.toString()<<" with denyflags "<<RYAI_MAP_CRUNCH::toString(denyFlags), return false);
1938 // not optimum but it will be rewrite for each specialized rootcell type.
1939 const sint32 x0 = pos.x();
1940 const sint32 y0 = pos.y();
1941
1942 const sint32 deltax = end.x() - x0;
1943 const sint32 deltay = end.y() - y0;
1944
1945 const sint32 d = std::max(abs(deltax), abs(deltay));
1946
1947 for (sint32 i=1; i<=d; ++i)
1948 {
1949 const sint dx = x0 + (deltax*i)/d - pos.x();
1950 const sint dy = y0 + (deltay*i)/d - pos.y();
1951
1952
1953 if ( !move(tempPos, CDirection(dx,dy))
1954 || (tempPos.getTopologyRef().getCstTopologyNode().getFlags()&denyFlags)!=0) // Arghh !!
1955 return false;
1956 pos=tempPos;
1957 }
1958 return true;
1959 }
1960
1961 // Clears height map
1962 void CWorldMap::clearHeightMap()
1963 {
1964 CMapPosition min, max;
1965 getBounds(min, max);
1966
1967 CMapPosition scan, scanline;
1968
1969 for (scan = min; scan.yCoord() != max.yCoord(); scan = scan.stepCell(0, 1))
1970 {
1971 for (scanline = scan; scanline.x() != max.x(); scanline = scanline.stepCell(1, 0))
1972 {
1973 CRootCell* rootCell=getRootCell(scanline);
1974 if (!rootCell)
1975 continue;
1976 rootCell->clearHeightMap();
1977 }
1978 }
1979 }
1980
1981 // checks motion layers
1982 void CWorldMap::checkMotionLayer()
1983 {
1984 CMapPosition min, max;
1985 getBounds(min, max);
1986
1987 uint compute = 0, white = 0, simple = 0, multi = 0, other = 0;
1988 countCells(compute, white, simple, multi, other);
1989 uint total = compute+white+simple+multi+other;
1990 uint compCells = 0;
1991
1992 CMapPosition scan, scanline;
1993 CTimeEstimator timeest(total);
1994
1995 for (scan = min; scan.yCoord() != max.yCoord(); scan = scan.stepCell(0, 1))
1996 {
1997 for (scanline = scan; scanline.x() != max.x(); scanline = scanline.stepCell(1, 0))
1998 {
1999
2000 CRootCell* rootCell=getRootCell(scanline);
2001 if (!rootCell)
2002 continue;
2003
2004 timeest.step("checkMotionLayer");
2005
2006 vector<CTopology> &topologies = rootCell->getTopologiesNodes();
2007
2008 // move from any point to the current topology
2009 uint i;
2010 for (i=0; i<topologies.size(); ++i)
2011 {
2012 CTopology &topology = topologies[i];
2013 CTopology::TTopologyRef tref = getTopologyRef(topology.Id);
2014 set<CTopology::TTopologyId> neighbours;
2015
2016 //
2017 uint16 toflags = topology.Flags;
2018
2019 uint j;
2020 for (j=0; j<topology.Neighbours.size(); ++j)
2021 neighbours.insert(topology.Neighbours[j].getTopologyRef());
2022
2023 sint x, y, slot;
2024
2025 bool failed = false;
2026
2027 for (y=-16; y<32; ++y)
2028 {
2029 for (x=-16; x<32; ++x)
2030 {
2031 CMapPosition cpos(scanline.x()+x, scanline.y()+y);
2032
2033 for (slot=0; slot<3; ++slot)
2034 {
2035 // build world pos and test it is valid
2036 CWorldPosition cwpos = getSafeWorldPosition(cpos, CSlot(slot));
2037 if (!cwpos.isValid())
2038 continue;
2039
2040 // if current topo is not a neighbour of checked topo, go to the next pos
2041 CTopology::TTopologyId ctopoId = getTopologyId(cwpos);
2042 if (neighbours.find(ctopoId) == neighbours.end())
2043 continue;
2044
2045 //
2046 CTopology &starttopo = getTopologyNode(ctopoId);
2047 uint16 fromflags = starttopo.Flags;
2048
2049 cwpos = getWorldPosition(cpos, CSlot(slot));
2050
2051 bool found = false;
2052 uint32 numSteps = 0;
2053
2054 do
2055 {
2056 if (getTopologyId(cwpos) == tref)
2057 {
2058 found = true;
2059 break;
2060 }
2061
2062 CTopology &ctopo = getTopologyNode(getTopologyId(cwpos));
2063 uint16 cflags = ctopo.Flags;
2064
2065 uint16 allow = ((~fromflags) & (~toflags) & cflags);
2066
2067 if (allow != 0)
2068 {
2069 nlwarning("Unallowed move from (%04X,%04X,%d-topo=%08X) to topo %08X, fromflags=%04X, toflags=%04X, cflags=%04X", cpos.x(), cpos.y(), slot, ctopoId.getVal(), tref.getVal(), fromflags, toflags, cflags);
2070 failed = true;
2071 }
2072 }
2073 while (moveTowards(cwpos, tref) && cwpos.isValid() && numSteps++ < 128);
2074
2075 if (!found)
2076 {
2077 nlwarning("Failed to go from (%d,%d,%d-topo=%08X) to topo %08X", cpos.x(), cpos.y(), slot, ctopoId.getVal(), tref.getVal());
2078 }
2079
2080 }
2081
2082 }
2083
2084 }
2085
2086 if (failed)
2087 {
2088 nlinfo("---- scanline = %04X %04X topo = %d ----", scanline.x(), scanline.y(), i);
2089 topology.DirectionMap->dump();
2090 }
2091
2092 }
2093
2094 }
2095
2096 }
2097
2098 }
2099
2100 //
2101 void CWorldMap::buildMasterTopo(bool allowWater, bool allowNogo)
2102 {
2103 nlinfo("buildMasterTopo");
2104
2105 CMapPosition min, max;
2106 getBounds(min, max);
2107
2108 CMapPosition scan, scanline;
2109
2110 uint masterTopo = 0;
2111 uint totalTopos = 0;
2112
2113 for (scan = min; scan.y() != max.y(); scan = scan.stepCell(0, 1))
2114 {
2115 for (scanline = scan; scanline.x() != max.x(); scanline = scanline.stepCell(1, 0))
2116 {
2117 CRootCell *cell = getRootCell(scanline);
2118 if (cell == NULL)
2119 continue;
2120
2121 vector<CTopology> &topos = cell->getTopologiesNodes();
2122
2123 uint i;
2124 for (i=0; i<topos.size(); ++i)
2125 {
2126 CTopology& tp = topos[i];
2127
2128 ++totalTopos;
2129
2130 if (!tp.isCompatible(allowWater, allowNogo) ||
2131 tp.getMasterTopo(allowWater, allowNogo) != CTopology::TTopologyId::UNDEFINED_TOPOLOGY)
2132 continue;
2133
2134 set<CTopology::TTopologyId> tovisit;
2135
2136 // set mastertopo id
2137 tp.getMasterTopoRef(allowWater, allowNogo) = masterTopo;
2138 tovisit.insert(tp.Id);
2139
2140 while (!tovisit.empty())
2141 {
2142 CTopology& t = getTopologyNode(*(tovisit.begin()));
2143 tovisit.erase(tovisit.begin());
2144
2145 uint j;
2146 for (j=0; j<t.Neighbours.size(); ++j)
2147 {
2148 CTopology& neighb = getTopologyNode(t.Neighbours[j].getTopologyRef());
2149
2150 // can go to the neighbour and neighb not visited yet ?
2151 if (!neighb.isCompatible(allowWater, allowNogo) ||
2152 neighb.getMasterTopo(allowWater, allowNogo) != CTopology::TTopologyId::UNDEFINED_TOPOLOGY)
2153 continue;
2154
2155 // set mastertopo id
2156 neighb.getMasterTopoRef(allowWater, allowNogo) = masterTopo;
2157 tovisit.insert(neighb.Id);
2158 }
2159 }
2160 ++masterTopo;
2161 }
2162 }
2163 }
2164 nlinfo("Built %d master topologies (%d topos tested)", masterTopo, totalTopos);
2165 }
2166
2167 //
2168 void CWorldMap::countSuperTopo()
2169 {
2170 nlinfo("Count super topologies");
2171
2172 CMapPosition min, max;
2173 getBounds(min, max);
2174
2175 CMapPosition scan, scanline;
2176
2177 uint superTopo = 0;
2178 set<CTopology::TTopologyId> visited;
2179
2180 uint totalTopos = 0;
2181
2182 for (scan = min; scan.y() != max.y(); scan = scan.stepCell(0, 1))
2183 {
2184 for (scanline = scan; scanline.x() != max.x(); scanline = scanline.stepCell(1, 0))
2185 {
2186 const CRootCell *cell = getRootCellCst(scanline);
2187 if (cell == NULL)
2188 continue;
2189
2190 const vector<CTopology> &topos = cell->getTopologiesNodes();
2191
2192 uint i;
2193 for (i=0; i<topos.size(); ++i)
2194 {
2195 CTopology::TTopologyId topoid = topos[i].Id;
2196
2197 ++totalTopos;
2198
2199 if (visited.find(topoid) == visited.end())
2200 {
2201 set<CTopology::TTopologyId> tovisit;
2202
2203 tovisit.insert(topoid);
2204 visited.insert(topoid);
2205
2206 while (!tovisit.empty())
2207 {
2208 CTopology::TTopologyId id = *(tovisit.begin());
2209 tovisit.erase(tovisit.begin());
2210
2211 const CTopology &t = getTopologyNode(id);
2212
2213 uint j;
2214 for (j=0; j<t.Neighbours.size(); ++j)
2215 {
2216 CTopology::TTopologyId neighb = t.Neighbours[j].getTopologyRef();
2217 if (visited.find(neighb) == visited.end())
2218 {
2219 visited.insert(neighb);
2220 tovisit.insert(neighb);
2221 }
2222
2223 }
2224
2225 }
2226 ++superTopo;
2227 }
2228
2229 }
2230
2231 }
2232
2233 }
2234 nlinfo("Found %d super topologies (%d topos tested, %d topos visited)", superTopo, totalTopos, visited.size());
2235 }
2236
2237 bool CWorldMap::setWorldPosition(sint32 z, CWorldPosition &wpos, const CAIVector &pos, const CRootCell *originCell) const
2238 {
2239 CSlot slot;
2240 const CMapPosition mapPos(pos);
2241
2242 const CRootCell *cell = originCell ? originCell : getRootCellCst(mapPos);
2243 if (!cell)
2244 {
2245 return false;
2246 }
2247
2248 sint32 minDistZ = INT_MAX;
2249 CSlot bestSlot;
2250 sint32 bestZ = 0;
2251 // Find best slot
2252 for (uint32 s=0; s<3; ++s)
2253 {
2254 if (!cell->isSlotUsed(mapPos, CSlot(s)))
2255 continue;
2256
2257 CSlot sslot=CSlot(s);
2258 sint32 sh = cell->getMetricHeight(CWorldPosition(cell, mapPos, sslot));
2259 sint32 dist = z-sh;
2260 dist = dist<0?-dist:dist;
2261 if (dist < minDistZ)
2262 {
2263 nlassert(dist>=0);
2264 minDistZ = dist;
2265 bestZ = sh;
2266 bestSlot = sslot;
2267 }
2268 }
2269 if (!bestSlot.isValid())
2270 {
2271 wpos = CWorldPosition(cell,mapPos,bestSlot,true);
2272 return false;
2273 }
2274 wpos = CWorldPosition(cell,mapPos,bestSlot);
2275 // if (simulateBug(5))
2276 // {
2277 // if (minDistZ > 2000)
2278 // {
2279 // return false;
2280 // }
2281 // }
2282 // else
2283 {
2284 // :KLUDGE: Water hack
2285 // If error is too big and player is either not in water or under slot (ie not floating above slot at surface)
2286 if (minDistZ > 2000 && ((wpos.getFlags()&RYAI_MAP_CRUNCH::Water)==0 || z<bestZ))
2287 {
2288 return false;
2289 }
2290 }
2291 return true;
2292 }
2293
2294 bool CWorldMap::setWorldPosition( double z, CWorldPosition &wpos, const CAIVector &pos, const CRootCell *originCell) const
2295 {
2296 nlassert(false && "Double version of setWorldPosition isn't tested !!! Verify it's the same than above sint32 version !");
2297 CSlot slot;
2298 const CMapPosition mapPos(pos);
2299
2300 const CRootCell *cell = originCell ? originCell : getRootCellCst(mapPos);
2301 if (!cell)
2302 {
2303 return false;
2304 }
2305
2306 double minDistZ = DBL_MAX;
2307 CSlot bestSlot;
2308 double bestZ;
2309 // find best slot
2310 for (uint32 s=0; s<3; ++s)
2311 {
2312 if (!cell->isSlotUsed(mapPos, CSlot(s)))
2313 continue;
2314
2315 CSlot sslot=CSlot(s);
2316 double sh = ((double)cell->getMetricHeight(CWorldPosition(cell, mapPos, sslot)))/1000.0;
2317 double dist = fabs(z-sh);
2318 if (dist < minDistZ)
2319 {
2320 nlassert(dist>=0);
2321 minDistZ = dist;
2322 bestZ = sh;
2323 bestSlot = sslot;
2324 }
2325 }
2326
2327 if (!bestSlot.isValid())
2328 {
2329 wpos=CWorldPosition(cell,mapPos,bestSlot,true);
2330 return false;
2331 }
2332 if (minDistZ > 2.000)
2333 {
2334 // nldebug("Setting a WorldPosition too far from specified z: x=%d y=%d z=%f slotz=%f", pos.x(), pos.y(), z, bestZ);
2335 wpos = CWorldPosition(cell,mapPos,bestSlot,true);
2336 return false;
2337 }
2338 wpos=CWorldPosition(cell,mapPos,bestSlot);
2339 return true;
2340 }
2341
2342 }
2343