1 // Filename : pathai.c
2 // Author : Ray E. Bornert II
3 // Date : 1992-MAR-15
4
5 // Skip list additions
6 // Author : Chris Camfield
7 // Date : 1997-NOV
8
9 #include "Font_Control.h"
10 #include "Isometric_Utils.h"
11 #include "Overhead.h"
12 #include "MemMan.h"
13 #include "Overhead_Types.h"
14 #include "Soldier_Control.h"
15 #include "Animation_Cache.h"
16 #include "Animation_Data.h"
17 #include "Animation_Control.h"
18 #include "Interface.h"
19 #include "Input.h"
20 #include "English.h"
21 #include "Structure.h"
22 #include "TileDef.h"
23 #include "WorldDef.h"
24 #include "WorldMan.h"
25 #include "PathAI.h"
26 #include "PathAIDebug.h"
27 #include "Points.h"
28 #include "AI.h"
29 #include "Random.h"
30 #include "Message.h"
31 #include "Structure_Wrap.h"
32 #include "Keys.h"
33 #include "GameSettings.h"
34 #include "Buildings.h"
35 #include "Logger.h"
36
37 // skiplist has extra level of pointers every 4 elements, so a level 5is optimized for
38 // 4 to the power of 5 elements, or 2 to the power of 10, 1024
39
40 //#define PATHAI_VISIBLE_DEBUG
41
42 //#define PATHAI_SKIPLIST_DEBUG
43
44 #ifdef PATHAI_VISIBLE_DEBUG
45 #include "JAScreens.h"
46 #include "RenderWorld.h"
47 #include "Video.h"
48
49 extern INT16 gsCoverValue[WORLD_MAX];
50 BOOLEAN gfDisplayCoverValues = TRUE;
51 static BOOLEAN gfDrawPathPoints = FALSE;
52 #endif
53
54 #include "Logger.h"
55
56 #include <algorithm>
57
58 BOOLEAN gfPlotPathToExitGrid = FALSE;
59 BOOLEAN gfRecalculatingExistingPathCost = FALSE;
60 UINT8 gubGlobalPathFlags = 0;
61
62 UINT8 gubBuildingInfoToSet;
63
64 // ABSOLUTE maximums
65 #define ABSMAX_SKIPLIST_LEVEL 6
66 #define ABSMAX_TRAIL_TREE (65536)
67 #define ABSMAX_PATHQ (1024)
68
69 // STANDARD maximums... configurable!
70 #define MAX_SKIPLIST_LEVEL 6
71 #define MAX_TRAIL_TREE (16384)
72 #define MAX_PATHQ (1024)
73
74 INT32 iMaxSkipListLevel = MAX_SKIPLIST_LEVEL;
75 INT32 iMaxTrailTree = MAX_TRAIL_TREE;
76 INT32 iMaxPathQ = MAX_PATHQ;
77
78 extern BOOLEAN gfGeneratingMapEdgepoints;
79
80 #define VEHICLE
81
82 #define TRAILCELLTYPE UINT16
83
84 // OLD PATHAI STUFF
85 /////////////////////////////////////////////////
86 struct path_t
87 {
88 INT32 iLocation; //4
89 path_t* pNext[ABSMAX_SKIPLIST_LEVEL]; //4 * MAX_SKIPLIST_LEVEL (5) = 20
90 INT16 sPathNdx; //2
91 TRAILCELLTYPE usCostSoFar; //2
92 TRAILCELLTYPE usCostToGo; //2
93 TRAILCELLTYPE usTotalCost; //2
94 INT8 bLevel; //1
95 UINT8 ubTotalAPCost; //1
96 UINT8 ubLegDistance; //1
97 };
98
99 struct trail_t
100 {
101 INT16 nextLink;
102 UINT8 stepDir;
103 INT8 fFlags;
104 INT16 sGridNo;
105 };
106
107 enum TrailFlags
108 {
109 STEP_BACKWARDS = 0x01
110 };
111
112 #define EASYWATERCOST TRAVELCOST_FLAT / 2
113 #define ISWATER(t) (((t)==TRAVELCOST_KNEEDEEP) || ((t)==TRAVELCOST_DEEPWATER))
114 #define NOPASS (TRAVELCOST_BLOCKED)
115
116 static path_t *pathQ;
117 static UINT16 gusPathShown,gusAPtsToMove;
118 static INT32 queRequests;
119 static INT32 iSkipListSize;
120 static INT32 iClosedListSize;
121 static INT8 bSkipListLevel;
122 static INT32 iSkipListLevelLimit[9] = {0, 4, 16, 64, 256, 1024, 4096, 16384, 65536};
123
124 // The estimated cost must never exceed the real cost, otherwise you lose the
125 // guarantee that you're getting the least-cost path from start to goal. (issue #375)
126 #define LOWESTCOST (EASYWATERCOST)
127
128 #define ESTIMATE0 ( (dx>dy) ? (dx) : (dy) )
129 #define ESTIMATE1 ( (dx<dy) ? (dx+(dy*10)/14) : (dy+(dx*10)/14) )
130 #define ESTIMATE2 LOWESTCOST*( (dx<dy) ? (dx+(dy*10)/14) : (dy+(dx*10)/14) )
131 #define ESTIMATEn ((int)(LOWESTCOST*sqrt(dx*dx+dy*dy)))
132 #define ESTIMATEC ( (dx<dy) ? (LOWESTCOST * (dx * 14 + dy * 10) / 14) : (LOWESTCOST * (dy * 14 + dx * 10) / 14) )
133 #define ESTIMATE ESTIMATEC
134
135 #define MAXCOST (9990)
136 //#define MAXCOST (255)
137 //#define TOTALCOST(pCurrPtr) (pCurrPtr->usCostSoFar + pCurrPtr->usCostToGo)
138 #define TOTALCOST( ptr ) (ptr->usTotalCost)
139 #define XLOC(a) (a%MAPWIDTH)
140 #define YLOC(a) (a/MAPWIDTH)
141 //#define LEGDISTANCE(a,b) ( abs( XLOC(b)-XLOC(a) ) + abs( YLOC(b)-YLOC(a) ) )
142 #define LEGDISTANCE( x1, y1, x2, y2 ) ( ABS( x2 - x1 ) + ABS( y2 - y1 ) )
143 //#define FARTHER(ndx,NDX) ( LEGDISTANCE( ndx->sLocation,sDestination) > LEGDISTANCE(NDX->sLocation,sDestination) )
144 #define FARTHER(ndx,NDX) ( ndx->ubLegDistance > NDX->ubLegDistance )
145
146 #define SETLOC( str, loc )\
147 {\
148 (str).iLocation = loc;\
149 }
150
151 static TRAILCELLTYPE *trailCost;
152 static UINT8 *trailCostUsed;
153 static UINT8 gubGlobalPathCount = 0;
154 static trail_t *trailTree;
155
156 static short trailTreeNdx=0;
157
158 #define QHEADNDX (0)
159 #define QPOOLNDX (iMaxPathQ-1)
160
161 static path_t *pQueueHead;
162 static path_t *pClosedHead;
163
164
165 #define pathQNotEmpty (pQueueHead->pNext[0] != NULL)
166 #define pathFound (pQueueHead->pNext[0]->iLocation == iDestination)
167 #define pathNotYetFound (!pathFound)
168
169 // Note, the closed list is maintained as a doubly-linked list;
170 // it's a regular queue, essentially, as we always add to the end
171 // and remove from the front
172
173 // pNext[0] is used for the next pointers
174 // and pNext[1] is used for prev pointers
175
176 /*
177 #define ClosedListAdd( pNew ) \
178 {\
179 pNew->pNext[0] = pClosedHead;\
180 pNew->pNext[1] = pClosedHead->pNext[1];\
181 pClosedHead->pNext[1]->pNext[0] = pNew;\
182 pClosedHead->pNext[1] = pNew;\
183 pNew->iLocation = -1;\
184 iClosedListSize++;\
185 }
186
187 #define ClosedListGet( pNew )\
188 {\
189 if (queRequests<QPOOLNDX)\
190 {\
191 pNew = pathQ + (queRequests);\
192 queRequests++;\
193 std::fill_n(pNew->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);\
194 pNew->bLevel = RandomSkipListLevel();\
195 }\
196 else if (iClosedListSize > 0)\
197 {\
198 pNew = pClosedHead->pNext[0];\
199 pNew->pNext[1]->pNext[0] = pNew->pNext[0];\
200 pNew->pNext[0]->pNext[1] = pNew->pNext[1];\
201 iClosedListSize--;\
202 queRequests++;\
203 std::fill_n(pNew->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);\
204 pNew->bLevel = RandomSkipListLevel();\
205 }\
206 else\
207 {\
208 pNew = NULL;\
209 }\
210 }*/
211
212 // experiment 1, seemed to fail
213 #define ClosedListAdd( pNew ) \
214 {\
215 pNew->pNext[0] = pClosedHead->pNext[0];\
216 pClosedHead->pNext[0] = pNew;\
217 pNew->iLocation = -1;\
218 iClosedListSize++;\
219 }
220
221 #define ClosedListGet( pNew )\
222 {\
223 if (queRequests<QPOOLNDX)\
224 {\
225 pNew = pathQ + (queRequests);\
226 queRequests++;\
227 pNew->bLevel = RandomSkipListLevel();\
228 }\
229 else if (iClosedListSize > 0)\
230 {\
231 pNew = pClosedHead->pNext[0];\
232 pClosedHead->pNext[0] = pNew->pNext[0];\
233 iClosedListSize--;\
234 queRequests++;\
235 std::fill_n(pNew->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);\
236 pNew->bLevel = RandomSkipListLevel();\
237 }\
238 else\
239 {\
240 pNew = NULL;\
241 }\
242 }
243
244 /*
245 #define ClosedListAdd( pNew ) \
246 {\
247 pNew->pNext[0] = pClosedHead;\
248 pNew->pNext[1] = pClosedHead->pNext[1];\
249 pClosedHead->pNext[1]->pNext[0] = pNew;\
250 pClosedHead->pNext[1] = pNew;\
251 pNew->iLocation = -1;\
252 iClosedListSize++;\
253 }
254
255 #define ClosedListGet( pNew )\
256 {\
257 if (queRequests<QPOOLNDX)\
258 {\
259 pNew = pathQ + (queRequests);\
260 queRequests++;\
261 std::fill_n(pNew->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);\
262 pNew->bLevel = RandomSkipListLevel();\
263 }\
264 else if (iClosedListSize > 0)\
265 {\
266 pNew = pClosedHead->pNext[0];\
267 pNew->pNext[1]->pNext[0] = pNew->pNext[0];\
268 pNew->pNext[0]->pNext[1] = pNew->pNext[1];\
269 iClosedListSize--;\
270 queRequests++;\
271 std::fill_n(pNew->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);\
272 pNew->bLevel = RandomSkipListLevel();\
273 }\
274 else\
275 {\
276 pNew = NULL;\
277 }\
278 }*/
279
280 #define SkipListRemoveHead()\
281 {\
282 pDel = pQueueHead->pNext[0];\
283 for (iLoop = 0; iLoop < __min( bSkipListLevel, pDel->bLevel ); iLoop++)\
284 {\
285 pQueueHead->pNext[iLoop] = pDel->pNext[iLoop];\
286 }\
287 iSkipListSize--;\
288 ClosedListAdd( pDel );\
289 }
290
291 #define SkipListInsert( pNew )\
292 {\
293 pCurr = pQueueHead;\
294 uiCost = TOTALCOST( pNew );\
295 std::fill_n(pUpdate, MAX_SKIPLIST_LEVEL, nullptr);\
296 for (iCurrLevel = bSkipListLevel - 1; iCurrLevel >= 0; iCurrLevel--)\
297 {\
298 pNext = pCurr->pNext[iCurrLevel];\
299 while (pNext)\
300 {\
301 if ( uiCost > TOTALCOST( pNext ) || (uiCost == TOTALCOST( pNext ) && FARTHER( pNew, pNext ) ) )\
302 {\
303 pCurr = pNext;\
304 pNext = pCurr->pNext[iCurrLevel];\
305 }\
306 else\
307 {\
308 break;\
309 }\
310 }\
311 pUpdate[iCurrLevel] = pCurr;\
312 }\
313 pCurr = pCurr->pNext[0];\
314 for (iCurrLevel = 0; iCurrLevel < pNew->bLevel; iCurrLevel++)\
315 {\
316 if (!(pUpdate[iCurrLevel]))\
317 {\
318 break;\
319 }\
320 pNew->pNext[iCurrLevel] = pUpdate[iCurrLevel]->pNext[iCurrLevel];\
321 pUpdate[iCurrLevel]->pNext[iCurrLevel] = pNew;\
322 }\
323 iSkipListSize++;\
324 if (iSkipListSize > iSkipListLevelLimit[bSkipListLevel])\
325 {\
326 pCurr = pQueueHead;\
327 pNext = pQueueHead->pNext[bSkipListLevel - 1];\
328 while( pNext )\
329 {\
330 if (pNext->bLevel > bSkipListLevel)\
331 {\
332 pCurr->pNext[bSkipListLevel] = pNext;\
333 pCurr = pNext;\
334 }\
335 pNext = pNext->pNext[bSkipListLevel - 1];\
336 }\
337 pCurr->pNext[bSkipListLevel] = pNext;\
338 bSkipListLevel++;\
339 }\
340 }
341
342 #define REMQUEHEADNODE() SkipListRemoveHead();
343
344 #define DELQUENODE(ndx) SkipListRemoveHead()
345
346 #define REMAININGCOST(ptr)\
347 (\
348 (dy = ABS(iDestY-iLocY)),\
349 (dx = ABS(iDestX-iLocX)),\
350 ESTIMATE\
351 )
352 /*
353 #define REMAININGCOST(ptr)\
354 (\
355 (locY = (ptr)->iLocation/MAPWIDTH),\
356 (locX = (ptr)->iLocation%MAPWIDTH),\
357 (dy = ABS(iDestY-locY)),\
358 (dx = ABS(iDestX-locX)),\
359 ESTIMATE\
360 )*/
361
362 #define NEWQUENODE ClosedListGet( pNewPtr )
363
364 #define QUEINSERT(ndx) SkipListInsert( ndx )
365
366 #define GREENSTEPSTART 0
367 #define REDSTEPSTART 16
368 #define PURPLESTEPSTART 32
369 #define BLUESTEPSTART 48
370 #define ORANGESTEPSTART 64
371
372 UINT8 gubNPCAPBudget = 0;
373 UINT8 gubNPCDistLimit = 0;
374 BOOLEAN gfNPCCircularDistLimit = FALSE;
375 UINT8 gubNPCPathCount;
376
377 BOOLEAN gfPlotDirectPath = FALSE;
378 BOOLEAN gfEstimatePath = FALSE;
379 BOOLEAN gfPathAroundObstacles = TRUE;
380
381 static UINT32 guiPlottedPath[256];
382 UINT8 guiPathingData[256];
383 static INT32 giPathDataSize;
384 static INT32 giPlotCnt;
385
386 #define LOOPING_CLOCKWISE 0
387 #define LOOPING_COUNTERCLOCKWISE 1
388 #define LOOPING_REVERSE 2
389
390 #ifdef COUNT_PATHS
391 UINT32 guiSuccessfulPathChecks = 0;
392 UINT32 guiTotalPathChecks = 0;
393 UINT32 guiFailedPathChecks = 0;
394 UINT32 guiUnsuccessfulPathChecks = 0;
395 #endif
396
397
RandomSkipListLevel(void)398 static INT8 RandomSkipListLevel(void)
399 {
400 INT8 bLevel = 1;
401
402 while( Random( 4 ) == 0 && bLevel < iMaxSkipListLevel - 1)
403 {
404 bLevel++;
405 }
406 return( bLevel );
407 }
408
409
InitPathAI(void)410 void InitPathAI(void)
411 {
412 pathQ = new path_t[ABSMAX_PATHQ]{};
413 trailCost = new TRAILCELLTYPE[MAPLENGTH]{};
414 trailCostUsed = new UINT8[MAPLENGTH]{};
415 trailTree = new trail_t[ABSMAX_TRAIL_TREE]{};
416 pQueueHead = &(pathQ[QHEADNDX]);
417 pClosedHead = &(pathQ[QPOOLNDX]);
418 }
419
420
ShutDownPathAI(void)421 void ShutDownPathAI( void )
422 {
423 delete[] pathQ;
424 delete[] trailCostUsed;
425 delete[] trailCost;
426 delete[] trailTree;
427 }
428
429
ReconfigurePathAI(INT32 iNewMaxSkipListLevel,INT32 iNewMaxTrailTree,INT32 iNewMaxPathQ)430 static void ReconfigurePathAI(INT32 iNewMaxSkipListLevel, INT32 iNewMaxTrailTree, INT32 iNewMaxPathQ)
431 {
432 // make sure the specified parameters are reasonable
433 iNewMaxSkipListLevel = __max( 0, __min( iNewMaxSkipListLevel, ABSMAX_SKIPLIST_LEVEL ) );
434 iNewMaxTrailTree = __max( 0, __min( iNewMaxTrailTree, ABSMAX_TRAIL_TREE ) );
435 iNewMaxPathQ = __max( 0, __min( iNewMaxPathQ, ABSMAX_PATHQ ) );
436 // assign them
437 iMaxSkipListLevel = iNewMaxSkipListLevel;
438 iMaxTrailTree = iNewMaxTrailTree;
439 iMaxPathQ = iNewMaxPathQ;
440 // relocate the head of the closed list to the end of the array portion being used
441 pClosedHead = &(pathQ[QPOOLNDX]);
442 *pClosedHead = path_t{};
443 }
444
445
RestorePathAIToDefaults(void)446 static void RestorePathAIToDefaults(void)
447 {
448 iMaxSkipListLevel = MAX_SKIPLIST_LEVEL;
449 iMaxTrailTree = MAX_TRAIL_TREE;
450 iMaxPathQ = MAX_PATHQ;
451 // relocate the head of the closed list to the end of the array portion being used
452 pClosedHead = &(pathQ[QPOOLNDX]);
453 *pClosedHead = path_t{};
454 }
455
456 ///////////////////////////////////////////////////////////////////////
457 // FINDBESTPATH /
458 ////////////////////////////////////////////////////////////////////////
FindBestPath(SOLDIERTYPE * s,INT16 sDestination,INT8 ubLevel,INT16 usMovementMode,INT8 bCopy,UINT8 fFlags)459 INT32 FindBestPath(SOLDIERTYPE* s, INT16 sDestination, INT8 ubLevel, INT16 usMovementMode, INT8 bCopy, UINT8 fFlags)
460 {
461 INT32 iDestination = sDestination, iOrigination;
462 UINT8 ubCnt = 0 , ubLoopStart = 0, ubLoopEnd = 0, ubLastDir = 0, ubStructIndex;
463 INT8 bLoopState = LOOPING_CLOCKWISE;
464 //BOOLEAN fLoopForwards = FALSE;
465 BOOLEAN fCheckedBehind = FALSE;
466 INT32 iDestX,iDestY, iLocX, iLocY, dx, dy;
467 INT32 newLoc,curLoc;
468 //INT32 curY;
469 INT32 curCost,newTotCost,nextCost;
470 INT16 sCurPathNdx;
471 INT32 prevCost;
472 INT32 iWaterToWater;
473 UINT8 ubCurAPCost,ubAPCost;
474 UINT8 ubNewAPCost=0;
475 #ifdef VEHICLE
476 //BOOLEAN fTurnSlow = FALSE;
477 //BOOLEAN fReverse = FALSE; // stuff for vehicles turning
478 BOOLEAN fMultiTile;
479 //BOOLEAN fVehicle;
480 //INT32 ubLastDir, iPrevToLastDir;
481 //INT8 bVehicleCheckDir;
482 //UINT16 adjLoc;
483 STRUCTURE_FILE_REF *pStructureFileRef=NULL;
484 UINT16 usAnimSurface;
485 //INT32 iCnt2, iCnt3;
486 #endif
487
488 path_t *pNewPtr;
489 path_t *pCurrPtr;
490
491 path_t *pUpdate[ABSMAX_SKIPLIST_LEVEL];
492 path_t *pCurr;
493 path_t *pNext;
494 path_t *pDel;
495 UINT32 uiCost;
496 INT32 iCurrLevel, iLoop;
497
498 UINT16 usOKToAddStructID=0;
499
500 BOOLEAN fCopyReachable;
501 BOOLEAN fCopyPathCosts;
502 BOOLEAN fVisitSpotsOnlyOnce;
503 INT32 iOriginationX, iOriginationY, iX, iY;
504
505 //BOOLEAN fTurnBased;
506 BOOLEAN fPathingForPlayer;
507 INT32 iDoorGridNo=-1;
508 BOOLEAN fDoorIsObstacleIfClosed= 0; // if false, door is obstacle if it is open
509 DOOR_STATUS *pDoorStatus;
510 DOOR *pDoor;
511 STRUCTURE *pDoorStructure;
512 BOOLEAN fDoorIsOpen = FALSE;
513 BOOLEAN fNonFenceJumper;
514 BOOLEAN fNonSwimmer;
515 BOOLEAN fPathAroundPeople;
516 BOOLEAN fGoingThroughDoor = FALSE; // for one tile
517 BOOLEAN fContinuousTurnNeeded;
518 BOOLEAN fCloseGoodEnough;
519 UINT16 usMovementModeToUseForAPs;
520 INT16 sClosePathLimit = -1; // XXX HACK000E
521
522 #ifdef PATHAI_SKIPLIST_DEBUG
523 CHAR8 zTempString[1000], zTS[50];
524 #endif
525
526 #ifdef PATHAI_VISIBLE_DEBUG
527 UINT16 usCounter = 0;
528 #endif
529
530 //fVehicle = FALSE;
531 iOriginationX = iOriginationY = 0;
532 iOrigination = (INT32) s->sGridNo;
533
534 if (iOrigination < 0 || iOrigination > WORLD_MAX)
535 {
536 SLOGE("Trying to calculate path from off-world gridno %d to %d",
537 iOrigination, sDestination );
538 return( 0 );
539 }
540 else if (!GridNoOnVisibleWorldTile( (INT16) iOrigination ) )
541 {
542 SLOGE("Trying to calculate path from non-visible gridno %d to %d",
543 iOrigination, sDestination );
544 return( 0 );
545 }
546 else if (s->bLevel != ubLevel)
547 {
548 // pathing to a different level... bzzzt!
549 return( 0 );
550 }
551
552 if ( gubGlobalPathFlags )
553 {
554 fFlags |= gubGlobalPathFlags;
555 }
556
557 //fTurnBased = (gTacticalStatus.uiFlags & INCOMBAT);
558
559 fPathingForPlayer = ( (s->bTeam == OUR_TEAM) && (!gTacticalStatus.fAutoBandageMode) && !(s->uiStatusFlags & SOLDIER_PCUNDERAICONTROL) );
560 fNonFenceJumper = !( IS_MERC_BODY_TYPE( s ) );
561 fNonSwimmer = !( IS_MERC_BODY_TYPE( s ) );
562 if ( fNonSwimmer )
563 {
564 if ( Water( sDestination ) )
565 {
566 return( 0 );
567 }
568 }
569 fPathAroundPeople = ( (fFlags & PATH_THROUGH_PEOPLE) == 0 );
570 fCloseGoodEnough = ( (fFlags & PATH_CLOSE_GOOD_ENOUGH) != 0);
571 if ( fCloseGoodEnough )
572 {
573 sClosePathLimit = __min( PythSpacesAway( (INT16)s->sGridNo, sDestination ) - 1, PATH_CLOSE_RADIUS );
574 if ( sClosePathLimit <= 0 )
575 {
576 return( 0 );
577 }
578 }
579
580 BOOLEAN const fConsiderPersonAtDestAsObstacle = fPathingForPlayer && fPathAroundPeople && !(fFlags & PATH_IGNORE_PERSON_AT_DEST);
581
582 if (bCopy >= COPYREACHABLE)
583 {
584 fCopyReachable = TRUE;
585 fCopyPathCosts = (bCopy == COPYREACHABLE_AND_APS);
586 fVisitSpotsOnlyOnce = (bCopy == COPYREACHABLE);
587 // make sure we aren't trying to copy path costs for an area greater than the AI array...
588 if (fCopyPathCosts && gubNPCDistLimit > AI_PATHCOST_RADIUS)
589 {
590 // oy!!!! dis no supposed to happen!
591 gubNPCDistLimit = AI_PATHCOST_RADIUS;
592 }
593 }
594 else
595 {
596 fCopyReachable = FALSE;
597 fCopyPathCosts = FALSE;
598 fVisitSpotsOnlyOnce = FALSE;
599 }
600
601 gubNPCPathCount++;
602
603 if (gubGlobalPathCount == 255)
604 {
605 // reset arrays!
606 std::fill_n(trailCostUsed, MAPLENGTH, 0);
607 gubGlobalPathCount = 1;
608 }
609 else
610 {
611 gubGlobalPathCount++;
612 }
613
614 // only allow nowhere destination if distance limit set
615 if (sDestination == NOWHERE)
616 {
617 /*
618 if (gubNPCDistLimit == 0)
619 {
620 return( FALSE );
621 }*/
622 }
623 else
624 {
625 // the very first thing to do is make sure the destination tile is reachable
626 if (!NewOKDestination( s, sDestination, fConsiderPersonAtDestAsObstacle, ubLevel ))
627 {
628 gubNPCAPBudget = 0;
629 gubNPCDistLimit = 0;
630 return( FALSE );
631 }
632
633 if (sDestination == s->sGridNo)
634 {
635 return( FALSE );
636 }
637 }
638
639 if (gubNPCAPBudget)
640 {
641 ubAPCost = MinAPsToStartMovement( s, usMovementMode );
642 if (ubAPCost > gubNPCAPBudget)
643 {
644 gubNPCAPBudget = 0;
645 gubNPCDistLimit = 0;
646 return( 0 );
647 }
648 else
649 {
650 gubNPCAPBudget -= ubAPCost;
651 }
652 }
653
654 #ifdef COUNT_PATHS
655 guiTotalPathChecks++;
656 #endif
657
658 #ifdef VEHICLE
659
660 fMultiTile = ((s->uiStatusFlags & SOLDIER_MULTITILE) != 0);
661 if (fMultiTile)
662 {
663 // Get animation surface...
664 // Chris_C... change this to use parameter.....
665 usAnimSurface = DetermineSoldierAnimationSurface( s, usMovementMode );
666 // Get structure ref...
667 pStructureFileRef = GetAnimationStructureRef(s, usAnimSurface, usMovementMode);
668
669 if ( pStructureFileRef )
670 {
671 //fVehicle = ( (s->uiStatusFlags & SOLDIER_VEHICLE) != 0 );
672
673 fContinuousTurnNeeded = ( ( s->uiStatusFlags & (SOLDIER_MONSTER | SOLDIER_ANIMAL | SOLDIER_VEHICLE) ) != 0 );
674
675 /*
676 if (fVehicle && s->bReverse)
677 {
678 fReverse = TRUE;
679 }*/
680 /*
681 if (fVehicle || s->ubBodyType == COW || s->ubBodyType == BLOODCAT) // or a vehicle
682 {
683 fTurnSlow = TRUE;
684 }*/
685 if ( gfEstimatePath )
686 {
687 usOKToAddStructID = IGNORE_PEOPLE_STRUCTURE_ID;
688 }
689 else if ( s->pLevelNode != NULL && s->pLevelNode->pStructureData != NULL )
690 {
691 usOKToAddStructID = s->pLevelNode->pStructureData->usStructureID;
692 }
693 else
694 {
695 usOKToAddStructID = INVALID_STRUCTURE_ID;
696 }
697
698 }
699 else
700 {
701 // turn off multitile pathing
702 fMultiTile = FALSE;
703 fContinuousTurnNeeded = FALSE;
704 }
705
706 }
707 else
708 {
709 fContinuousTurnNeeded = FALSE;
710 }
711
712 #endif
713
714 if (!fContinuousTurnNeeded)
715 {
716 ubLoopStart = 0;
717 ubLoopEnd = 0;
718 bLoopState = LOOPING_CLOCKWISE;
719 }
720
721 ubCurAPCost = 0;
722 queRequests = 2;
723
724 //initialize the path data structures
725 std::fill_n(pathQ, iMaxPathQ, path_t{});
726 std::fill_n(trailTree, iMaxTrailTree, trail_t{});
727
728 #if defined( PATHAI_VISIBLE_DEBUG )
729 if (gfDisplayCoverValues && gfDrawPathPoints)
730 {
731 std::fill_n(gsCoverValue, WORLD_MAX, 0x7F7F);
732 }
733 #endif
734
735 bSkipListLevel = 1;
736 iSkipListSize = 0;
737 iClosedListSize = 0;
738
739 trailTreeNdx=0;
740
741 //set up common info
742 if (fCopyPathCosts)
743 {
744 iOriginationY = (iOrigination / MAPWIDTH);
745 iOriginationX = (iOrigination % MAPWIDTH);
746 }
747
748 iDestY = (iDestination / MAPWIDTH);
749 iDestX = (iDestination % MAPWIDTH);
750
751 // if origin and dest is water, then user wants to stay in water!
752 // so, check and set waterToWater flag accordingly
753 if (iDestination == NOWHERE)
754 {
755 iWaterToWater = 0;
756 }
757 else
758 {
759 if (ISWATER(gubWorldMovementCosts[iOrigination][0][ubLevel]) &&
760 ISWATER(gubWorldMovementCosts[iDestination][0][ubLevel]))
761 {
762 iWaterToWater = 1;
763 }
764 else
765 {
766 iWaterToWater = 0;
767 }
768 }
769
770 //setup Q and first path record
771
772 SETLOC( *pQueueHead, iOrigination );
773 pQueueHead->usCostSoFar = MAXCOST;
774 pQueueHead->bLevel = iMaxSkipListLevel - 1;
775
776 pClosedHead->pNext[0] = pClosedHead;
777 pClosedHead->pNext[1] = pClosedHead;
778
779 //setup first path record
780 iLocY = iOrigination / MAPWIDTH;
781 iLocX = iOrigination % MAPWIDTH;
782
783 SETLOC( pathQ[1], iOrigination );
784 pathQ[1].sPathNdx = 0;
785 pathQ[1].usCostSoFar = 0;
786 if ( fCopyReachable )
787 {
788 pathQ[1].usCostToGo = 100;
789 }
790 else
791 {
792 pathQ[1].usCostToGo = REMAININGCOST( &(pathQ[1]) );
793 }
794 pathQ[1].usTotalCost = pathQ[1].usCostSoFar + pathQ[1].usCostToGo;
795 pathQ[1].ubLegDistance = LEGDISTANCE( iLocX, iLocY, iDestX, iDestY );
796 pathQ[1].bLevel = 1;
797 pQueueHead->pNext[0] = &( pathQ[1] );
798 iSkipListSize++;
799
800 trailTreeNdx = 0;
801 trailCost[iOrigination] = 0;
802 pCurrPtr = pQueueHead->pNext[0];
803 pCurrPtr->sPathNdx = trailTreeNdx;
804 trailTreeNdx++;
805
806
807 do
808 {
809 //remove the first and best path so far from the que
810 pCurrPtr = pQueueHead->pNext[0];
811 curLoc = pCurrPtr->iLocation;
812 curCost = pCurrPtr->usCostSoFar;
813 sCurPathNdx = pCurrPtr->sPathNdx;
814
815 // remember the cost used to get here...
816 prevCost = gubWorldMovementCosts[trailTree[sCurPathNdx].sGridNo][trailTree[sCurPathNdx].stepDir][ubLevel];
817
818 #if defined( PATHAI_VISIBLE_DEBUG )
819 if (gfDisplayCoverValues && gfDrawPathPoints)
820 {
821 if (gsCoverValue[ curLoc ] > 0)
822 {
823 gsCoverValue[ curLoc ] *= -1;
824 }
825 }
826 #endif
827
828 #ifdef VEHICLE
829 /*
830 if (fTurnSlow)
831 {
832 if (pCurrPtr->pNext[0] == 0)
833 {
834 if (fReverse)
835 {
836 ubLastDir = OppositeDirection(s->bDirection);
837 }
838 else
839 {
840 ubLastDir = s->bDirection;
841 }
842 // start prev-to-last dir at same as current (could cause a problem)
843 iPrevToLastDir = ubLastDir;
844 }
845 else
846 {
847 iPrevToLastDir = trailTree[trailTree[pCurrPtr->sPathNdx].nextLink].dirDelta;
848 ubLastDir = trailTree[pCurrPtr->sPathNdx].dirDelta;
849 }
850 }*/
851 #endif
852
853 if (gubNPCAPBudget)
854 {
855 ubCurAPCost = pCurrPtr->ubTotalAPCost;
856 }
857 if (fCopyReachable && prevCost != TRAVELCOST_FENCE)
858 {
859 gpWorldLevelData[curLoc].uiFlags |= MAPELEMENT_REACHABLE;
860 if (gubBuildingInfoToSet > 0)
861 {
862 gubBuildingInfo[ curLoc ] = gubBuildingInfoToSet;
863 }
864 }
865
866 DELQUENODE( pCurrPtr );
867
868 if ( trailCostUsed[curLoc] == gubGlobalPathCount && trailCost[curLoc] < curCost)
869 goto NEXTDIR;
870
871 if (fContinuousTurnNeeded)
872 {
873 if (trailTreeNdx < 2)
874 {
875 ubLastDir = s->bDirection;
876 }
877 else if ( trailTree[pCurrPtr->sPathNdx].fFlags & STEP_BACKWARDS )
878 {
879 ubLastDir = OppositeDirection(trailTree[pCurrPtr->sPathNdx].stepDir);
880 }
881 else
882 {
883 ubLastDir = trailTree[pCurrPtr->sPathNdx].stepDir;
884 }
885 ubLoopStart = ubLastDir;
886 ubLoopEnd = ubLastDir;
887 bLoopState = LOOPING_CLOCKWISE;
888 fCheckedBehind = FALSE;
889 }
890
891 //contemplate a new path in each direction
892 //for ( ubCnt = ubLoopStart; ubCnt != ubLoopEnd; ubCnt = (ubCnt + iLoopIncrement) % MAXDIR )
893 for ( ubCnt = ubLoopStart; ; )
894 {
895
896 #ifdef VEHICLE
897 /*
898 if (fTurnSlow)
899 {
900 if (ubLastDir == iPrevToLastDir)
901 {
902 if (ubCnt != ubLastDir &&
903 ubCnt != OneCDirection(ubLastDir) &&
904 ubCnt != OneCCDirection(ubLastDir))
905 {
906 goto NEXTDIR;
907 }
908 }
909 else
910 {
911 if ( ubCnt != ubLastDir )
912 {
913 goto NEXTDIR;
914 }
915 }
916 }*/
917
918 if ( bLoopState == LOOPING_REVERSE )
919 {
920 ubStructIndex = OppositeDirection(OneCDirection(ubCnt));
921 }
922 else
923 {
924 ubStructIndex = OneCDirection(ubCnt);
925 }
926
927 if (fMultiTile)
928 {
929 if ( fContinuousTurnNeeded )
930 {
931 if ( ubCnt != ubLastDir )
932 {
933 if ( !OkayToAddStructureToWorld( (INT16) curLoc, ubLevel, &(pStructureFileRef->pDBStructureRef[ ubStructIndex ]), usOKToAddStructID ) )
934 {
935 // we have to abort this loop and possibly reset the loop conditions to
936 // search in the other direction (if we haven't already done the other dir)
937 if (bLoopState == LOOPING_CLOCKWISE)
938 {
939 ubLoopStart = ubLastDir;
940 ubLoopEnd = ubCnt;
941 bLoopState = LOOPING_COUNTERCLOCKWISE; // backwards
942 // when we go to the bottom of the loop, iLoopIncrement will be added to ubCnt
943 // which is good since it avoids duplication of effort
944 ubCnt = ubLoopStart;
945 goto NEXTDIR;
946 }
947 else if ( bLoopState == LOOPING_COUNTERCLOCKWISE && !fCheckedBehind )
948 {
949 // check rear dir
950 bLoopState = LOOPING_REVERSE;
951
952 // NB we're stuck with adding 1 to the loop counter down below so configure to accomodate...
953 //ubLoopStart = (ubLastDir + (MAXDIR / 2) - 1) % MAXDIR;
954 ubLoopStart = OppositeDirection(OneCCDirection(ubLastDir));
955 ubLoopEnd = (ubLoopStart + 2) % MAXDIR;
956 ubCnt = ubLoopStart;
957 fCheckedBehind = TRUE;
958 goto NEXTDIR;
959 }
960 else
961 {
962 // done
963 goto ENDOFLOOP;
964 }
965
966 }
967 }
968 }
969 else if ( pStructureFileRef )
970 {
971 // check to make sure it's okay for us to turn to the new direction in our current tile
972 if (!OkayToAddStructureToWorld( (INT16) curLoc, ubLevel, &(pStructureFileRef->pDBStructureRef[ ubStructIndex ]), usOKToAddStructID ) )
973 {
974 goto NEXTDIR;
975 }
976 }
977 }
978
979 #endif
980
981 newLoc = curLoc + DirIncrementer[ubCnt];
982
983 if ( newLoc < 0 || newLoc >= GRIDSIZE )
984 {
985 STLOGW("Path Finding algorithm tried to go out of bounds at {}, in an attempt to find path from {} to {}", newLoc, iOrigination, iDestination);
986 goto NEXTDIR;
987 }
988
989 if ( fVisitSpotsOnlyOnce && trailCostUsed[newLoc] == gubGlobalPathCount )
990 {
991 // on a "reachable" test, never revisit locations!
992 goto NEXTDIR;
993 }
994
995
996 //if (gpWorldLevelData[newLoc].sHeight != ubLevel)
997 //ATE: Movement onto cliffs? Check vs the soldier's gridno height
998 // CJC: PREVIOUS LOCATION's height
999 if ( gpWorldLevelData[ newLoc ].sHeight != gpWorldLevelData[ curLoc ].sHeight )
1000 {
1001 goto NEXTDIR;
1002 }
1003
1004 if (gubNPCDistLimit)
1005 {
1006 if ( gfNPCCircularDistLimit )
1007 {
1008 if (PythSpacesAway( (INT16) iOrigination, (INT16) newLoc) > gubNPCDistLimit)
1009 {
1010 goto NEXTDIR;
1011 }
1012 }
1013 else
1014 {
1015 if (SpacesAway( (INT16) iOrigination, (INT16) newLoc) > gubNPCDistLimit)
1016 {
1017 goto NEXTDIR;
1018 }
1019 }
1020 }
1021
1022 // AI check for mines
1023 if ( gpWorldLevelData[newLoc].uiFlags & MAPELEMENT_ENEMY_MINE_PRESENT && s->bSide != 0)
1024 {
1025 goto NEXTDIR;
1026 }
1027
1028 /*
1029 if ( gpWorldLevelData[newLoc].uiFlags & (MAPELEMENT_ENEMY_MINE_PRESENT | MAPELEMENT_PLAYER_MINE_PRESENT) )
1030 {
1031 if (s->bSide == 0)
1032 {
1033 // For our team, skip a location with a known mines unless it is the end of our
1034 // path; for others on our side, skip such locations completely;
1035 if (s->bTeam != OUR_TEAM || newLoc != iDestination)
1036 {
1037 if (gpWorldLevelData[newLoc].uiFlags & MAPELEMENT_PLAYER_MINE_PRESENT)
1038 {
1039 goto NEXTDIR;
1040 }
1041 }
1042 }
1043 else
1044 {
1045 // For the enemy, always skip known mines
1046 if (gpWorldLevelData[newLoc].uiFlags & MAPELEMENT_ENEMY_MINE_PRESENT)
1047 {
1048 goto NEXTDIR;
1049 }
1050 }
1051 }*/
1052
1053 //how much is admission to the next tile
1054 if ( gfPathAroundObstacles )
1055 {
1056 nextCost = gubWorldMovementCosts[ newLoc ][ ubCnt ][ ubLevel ];
1057
1058 //ATE: Check for differences from reality
1059 if (nextCost == TRAVELCOST_NOT_STANDING)
1060 {
1061 // for path plotting purposes, use the terrain value
1062 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1063 }
1064 else if ( nextCost == TRAVELCOST_EXITGRID )
1065 {
1066 if (gfPlotPathToExitGrid)
1067 {
1068 // replace with terrain cost so that we can plot path, otherwise is obstacle
1069 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1070 }
1071 }
1072 else if ( nextCost == TRAVELCOST_FENCE && fNonFenceJumper )
1073 {
1074 goto NEXTDIR;
1075 }
1076 else if ( IS_TRAVELCOST_DOOR( nextCost ) )
1077 {
1078
1079 // don't let anyone path diagonally through doors!
1080 if (ubCnt & 1)
1081 {
1082 goto NEXTDIR;
1083 }
1084
1085 switch( nextCost )
1086 {
1087 case TRAVELCOST_DOOR_CLOSED_HERE:
1088 fDoorIsObstacleIfClosed = TRUE;
1089 iDoorGridNo = newLoc;
1090 break;
1091 case TRAVELCOST_DOOR_CLOSED_N:
1092 fDoorIsObstacleIfClosed = TRUE;
1093 iDoorGridNo = newLoc + DirIncrementer[ NORTH ];
1094 break;
1095 case TRAVELCOST_DOOR_CLOSED_W:
1096 fDoorIsObstacleIfClosed = TRUE;
1097 iDoorGridNo = newLoc + DirIncrementer[ WEST ];
1098 break;
1099 case TRAVELCOST_DOOR_OPEN_HERE:
1100 fDoorIsObstacleIfClosed = FALSE;
1101 iDoorGridNo = newLoc;
1102 break;
1103 case TRAVELCOST_DOOR_OPEN_N:
1104 fDoorIsObstacleIfClosed = FALSE;
1105 iDoorGridNo = newLoc + DirIncrementer[ NORTH ];
1106 break;
1107 case TRAVELCOST_DOOR_OPEN_NE:
1108 fDoorIsObstacleIfClosed = FALSE;
1109 iDoorGridNo = newLoc + DirIncrementer[ NORTHEAST ];
1110 break;
1111 case TRAVELCOST_DOOR_OPEN_E:
1112 fDoorIsObstacleIfClosed = FALSE;
1113 iDoorGridNo = newLoc + DirIncrementer[ EAST ];
1114 break;
1115 case TRAVELCOST_DOOR_OPEN_SE:
1116 fDoorIsObstacleIfClosed = FALSE;
1117 iDoorGridNo = newLoc + DirIncrementer[ SOUTHEAST ];
1118 break;
1119 case TRAVELCOST_DOOR_OPEN_S:
1120 fDoorIsObstacleIfClosed = FALSE;
1121 iDoorGridNo = newLoc + DirIncrementer[ SOUTH ];
1122 break;
1123 case TRAVELCOST_DOOR_OPEN_SW:
1124 fDoorIsObstacleIfClosed = FALSE;
1125 iDoorGridNo = newLoc + DirIncrementer[ SOUTHWEST ];
1126 break;
1127 case TRAVELCOST_DOOR_OPEN_W:
1128 fDoorIsObstacleIfClosed = FALSE;
1129 iDoorGridNo = newLoc + DirIncrementer[ WEST ];
1130 break;
1131 case TRAVELCOST_DOOR_OPEN_NW:
1132 fDoorIsObstacleIfClosed = FALSE;
1133 iDoorGridNo = newLoc + DirIncrementer[ NORTHWEST ];
1134 break;
1135 case TRAVELCOST_DOOR_OPEN_N_N:
1136 fDoorIsObstacleIfClosed = FALSE;
1137 iDoorGridNo = newLoc + DirIncrementer[ NORTH ] + DirIncrementer[ NORTH ];
1138 break;
1139 case TRAVELCOST_DOOR_OPEN_NW_N:
1140 fDoorIsObstacleIfClosed = FALSE;
1141 iDoorGridNo = newLoc + DirIncrementer[ NORTHWEST ] + DirIncrementer[ NORTH ];
1142 break;
1143 case TRAVELCOST_DOOR_OPEN_NE_N:
1144 fDoorIsObstacleIfClosed = FALSE;
1145 iDoorGridNo = newLoc + DirIncrementer[ NORTHEAST ] + DirIncrementer[ NORTH ];
1146 break;
1147 case TRAVELCOST_DOOR_OPEN_W_W:
1148 fDoorIsObstacleIfClosed = FALSE;
1149 iDoorGridNo = newLoc + DirIncrementer[ WEST ] + DirIncrementer[ WEST ];
1150 break;
1151 case TRAVELCOST_DOOR_OPEN_SW_W:
1152 fDoorIsObstacleIfClosed = FALSE;
1153 iDoorGridNo = newLoc + DirIncrementer[ SOUTHWEST ] + DirIncrementer[ WEST ];
1154 break;
1155 case TRAVELCOST_DOOR_OPEN_NW_W:
1156 fDoorIsObstacleIfClosed = FALSE;
1157 iDoorGridNo = newLoc + DirIncrementer[ NORTHWEST ] + DirIncrementer[ WEST ];
1158 break;
1159 default:
1160 break;
1161 }
1162
1163 if ( fPathingForPlayer && gpWorldLevelData[ iDoorGridNo ].ubExtFlags[0] & MAPELEMENT_EXT_DOOR_STATUS_PRESENT )
1164 {
1165 // check door status
1166 pDoorStatus = GetDoorStatus( (INT16) iDoorGridNo );
1167 if (pDoorStatus)
1168 {
1169 fDoorIsOpen = (pDoorStatus->ubFlags & DOOR_PERCEIVED_OPEN) != 0;
1170 }
1171 else
1172 {
1173 // door destroyed?
1174 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1175 }
1176 }
1177 else
1178 {
1179 // check door structure
1180 pDoorStructure = FindStructure( (INT16) iDoorGridNo, STRUCTURE_ANYDOOR );
1181 if (pDoorStructure)
1182 {
1183 fDoorIsOpen = (pDoorStructure->fFlags & STRUCTURE_OPEN) != 0;
1184 }
1185 else
1186 {
1187 // door destroyed?
1188 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1189 }
1190 }
1191
1192 // now determine movement cost... if it hasn't been changed already
1193 if ( IS_TRAVELCOST_DOOR( nextCost ) )
1194 {
1195
1196 if (fDoorIsOpen)
1197 {
1198 if (fDoorIsObstacleIfClosed)
1199 {
1200 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1201 }
1202 else
1203 {
1204 nextCost = TRAVELCOST_OBSTACLE;
1205 }
1206 }
1207 else
1208 {
1209 if (fDoorIsObstacleIfClosed)
1210 {
1211 // door is closed and this should be an obstacle, EXCEPT if we are calculating
1212 // a path for an enemy or NPC with keys
1213 if ( fPathingForPlayer || ( s && (s->uiStatusFlags & SOLDIER_MONSTER || s->uiStatusFlags & SOLDIER_ANIMAL) ) )
1214 {
1215 nextCost = TRAVELCOST_OBSTACLE;
1216 }
1217 else
1218 {
1219 // have to check if door is locked and NPC does not have keys!
1220 pDoor = FindDoorInfoAtGridNo( iDoorGridNo );
1221 if (pDoor)
1222 {
1223 if (!pDoor->fLocked || s->bHasKeys)
1224 {
1225 // add to AP cost
1226 if (gubNPCAPBudget)
1227 {
1228 fGoingThroughDoor = TRUE;
1229 }
1230 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1231 }
1232 else
1233 {
1234 nextCost = TRAVELCOST_OBSTACLE;
1235 }
1236 }
1237 else
1238 {
1239 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1240 }
1241 }
1242 }
1243 else
1244 {
1245 nextCost = gTileTypeMovementCost[ gpWorldLevelData[ newLoc ].ubTerrainID ];
1246 }
1247 }
1248 }
1249 }
1250 else if ( (nextCost == TRAVELCOST_SHORE || nextCost == TRAVELCOST_KNEEDEEP || nextCost == TRAVELCOST_DEEPWATER ) && fNonSwimmer )
1251 {
1252 // creatures and animals can't go in water
1253 nextCost = TRAVELCOST_OBSTACLE;
1254 }
1255
1256
1257 // Apr. '96 - moved up be ahead of AP_Budget stuff
1258 if ( ( nextCost >= NOPASS) ) // || ( nextCost == TRAVELCOST_DOOR ) )
1259 goto NEXTDIR;
1260
1261 }
1262 else
1263 {
1264 nextCost = TRAVELCOST_FLAT;
1265 }
1266
1267 // if contemplated tile is NOT final dest and someone there, disqualify route
1268 // when doing a reachable test, ignore all locations with people in them
1269 if (fPathAroundPeople && ( (newLoc != iDestination) || fCopyReachable) )
1270 {
1271 // ATE: ONLY cancel if they are moving.....
1272 const SOLDIERTYPE* const tgt = WhoIsThere2(newLoc, s->bLevel);
1273 if (tgt != NULL && tgt != s)
1274 {
1275 // Check for movement....
1276 //if (fTurnBased || tgt->sFinalDestination == tgt->sGridNo || tgt->fDelayedMovement)
1277 //{
1278 goto NEXTDIR;
1279 //}
1280 //else
1281 //{
1282 // nextCost += 50;
1283 //}
1284 }
1285 }
1286
1287 #ifdef VEHICLE
1288 if (fMultiTile)
1289 {
1290 // vehicle test for obstacles: prevent movement to next tile if
1291 // a tile covered by the vehicle in that position & direction
1292 // has an obstacle in it
1293
1294 // because of the order in which animations are stored (dir 7 first,
1295 // then 0 1 2 3 4 5 6), we must subtract 1 from the direction
1296 // ATE: Send in our existing structure ID so it's ignored!
1297
1298 if (!OkayToAddStructureToWorld( (INT16) newLoc, ubLevel, &(pStructureFileRef->pDBStructureRef[ ubStructIndex ]), usOKToAddStructID ) )
1299 {
1300 goto NEXTDIR;
1301 }
1302
1303 /*
1304 // vehicles aren't moving any more....
1305 if (fVehicle)
1306 {
1307 // transmogrify pathing costs for vehicles!
1308 switch(nextCost)
1309 {
1310 case TRAVELCOST_THICK:
1311 nextCost = TRAVELCOST_GRASS;
1312 break;
1313 case TRAVELCOST_SHORE:
1314 case TRAVELCOST_KNEEDEEP:
1315 case TRAVELCOST_DEEPWATER:
1316 //case TRAVELCOST_DOOR:
1317 case TRAVELCOST_FENCE:
1318 nextCost = TRAVELCOST_OBSTACLE;
1319 break;
1320
1321 default:
1322 break;
1323 }
1324 }
1325 */
1326 }
1327 #endif
1328
1329 // NEW Apr 21 by Ian: abort if cost exceeds budget
1330 if (gubNPCAPBudget)
1331 {
1332 switch(nextCost)
1333 {
1334 case TRAVELCOST_NONE:
1335 ubAPCost = 0;
1336 break;
1337
1338 case TRAVELCOST_DIRTROAD:
1339 case TRAVELCOST_FLAT:
1340 ubAPCost = AP_MOVEMENT_FLAT;
1341 break;
1342 //case TRAVELCOST_BUMPY:
1343 case TRAVELCOST_GRASS:
1344 ubAPCost = AP_MOVEMENT_GRASS;
1345 break;
1346 case TRAVELCOST_THICK:
1347 ubAPCost = AP_MOVEMENT_BUSH;
1348 break;
1349 case TRAVELCOST_DEBRIS:
1350 ubAPCost = AP_MOVEMENT_RUBBLE;
1351 break;
1352 case TRAVELCOST_SHORE:
1353 ubAPCost = AP_MOVEMENT_SHORE; // wading shallow water
1354 break;
1355 case TRAVELCOST_KNEEDEEP:
1356 ubAPCost = AP_MOVEMENT_LAKE; // wading waist/chest deep - very slow
1357 break;
1358
1359 case TRAVELCOST_DEEPWATER:
1360 ubAPCost = AP_MOVEMENT_OCEAN; // can swim, so it's faster than wading
1361 break;
1362
1363 //case TRAVELCOST_DOOR:
1364 // ubAPCost = AP_MOVEMENT_FLAT;
1365 // break;
1366
1367 case TRAVELCOST_FENCE:
1368 ubAPCost = AP_JUMPFENCE;
1369
1370 /*
1371 if ( sSwitchValue == TRAVELCOST_FENCE )
1372 {
1373 sPoints += sTileCost;
1374
1375 // If we are changeing stance ( either before or after getting there....
1376 // We need to reflect that...
1377 switch(usMovementMode)
1378 {
1379 case RUNNING:
1380 case WALKING :
1381
1382 // Add here cost to go from crouch to stand AFTER fence hop....
1383 // Since it's AFTER.. make sure we will be moving after jump...
1384 if ( ( ubCnt + 2 ) < iLastGrid )
1385 {
1386 sPoints += AP_CROUCH;
1387 }
1388 break;
1389
1390 case SWATTING:
1391
1392 // Add cost to stand once there BEFORE....
1393 sPoints += AP_CROUCH;
1394 break;
1395
1396 case CRAWLING:
1397
1398 // Can't do it here.....
1399 break;
1400
1401 }
1402 }*/
1403
1404 break;
1405
1406 case TRAVELCOST_OBSTACLE:
1407 default:
1408 goto NEXTDIR; // Cost too much to be considered!
1409 }
1410
1411
1412 // don't make the mistake of adding directly to
1413 // ubCurAPCost, that must be preserved for remaining dirs!
1414 if (ubCnt & 1)
1415 {
1416 ubAPCost = (ubAPCost * 14) / 10;
1417 }
1418
1419 usMovementModeToUseForAPs = usMovementMode;
1420
1421 // ATE: if water, force to be walking always!
1422 if ( nextCost == TRAVELCOST_SHORE || nextCost == TRAVELCOST_KNEEDEEP ||
1423 nextCost == TRAVELCOST_DEEPWATER )
1424 {
1425 usMovementModeToUseForAPs = WALKING;
1426 }
1427
1428 // adjust AP cost for movement mode
1429 switch( usMovementModeToUseForAPs )
1430 {
1431 case RUNNING:
1432 case ADULTMONSTER_WALKING:
1433 // save on casting
1434 ubAPCost = ubAPCost * 10 / ( (UINT8) (RUNDIVISOR * 10));
1435 //ubAPCost = (INT16)(((DOUBLE)sTileCost) / RUNDIVISOR );break;
1436 break;
1437 case WALKING:
1438 case ROBOT_WALK:
1439 ubAPCost = (ubAPCost + WALKCOST);
1440 break;
1441 case SWATTING:
1442 ubAPCost = (ubAPCost + SWATCOST);
1443 break;
1444 case CRAWLING:
1445 ubAPCost = (ubAPCost + CRAWLCOST);
1446 break;
1447 }
1448
1449 if (nextCost == TRAVELCOST_FENCE)
1450 {
1451 switch( usMovementModeToUseForAPs )
1452 {
1453 case RUNNING:
1454 case WALKING :
1455 // Here pessimistically assume the path will continue after hopping the fence
1456 ubAPCost += AP_CROUCH;
1457 break;
1458
1459 case SWATTING:
1460
1461 // Add cost to stand once there BEFORE jumping....
1462 ubAPCost += AP_CROUCH;
1463 break;
1464
1465 case CRAWLING:
1466
1467 // Can't do it here.....
1468 goto NEXTDIR;
1469 }
1470 }
1471 else if (nextCost == TRAVELCOST_NOT_STANDING)
1472 {
1473 switch(usMovementModeToUseForAPs)
1474 {
1475 case RUNNING:
1476 case WALKING :
1477 // charge crouch APs for ducking head!
1478 ubAPCost += AP_CROUCH;
1479 break;
1480
1481 default:
1482 break;
1483 }
1484 }
1485 else if (fGoingThroughDoor)
1486 {
1487 ubAPCost += AP_OPEN_DOOR;
1488 fGoingThroughDoor = FALSE;
1489 }
1490
1491
1492 ubNewAPCost = ubCurAPCost + ubAPCost;
1493
1494
1495 if (ubNewAPCost > gubNPCAPBudget)
1496 goto NEXTDIR;
1497
1498 }
1499
1500 if ( fCloseGoodEnough )
1501 {
1502 if ( PythSpacesAway( (INT16)newLoc, sDestination ) <= sClosePathLimit )
1503 {
1504 // stop the path here!
1505 iDestination = newLoc;
1506 sDestination = (INT16) newLoc;
1507 fCloseGoodEnough = FALSE;
1508 }
1509 }
1510 //make the destination look very attractive
1511 if (newLoc == iDestination)
1512 nextCost = 0;
1513 else
1514 if (gfPlotDirectPath && nextCost < NOPASS)
1515 nextCost = TRAVELCOST_FLAT;
1516
1517 // make water cost attractive for water to water paths
1518 if (iWaterToWater)
1519 {
1520 if (ISWATER(prevCost))
1521 prevCost = EASYWATERCOST;
1522 if (ISWATER(nextCost))
1523 nextCost = EASYWATERCOST;
1524 }
1525
1526 // NOTE: on September 24, 1997, Chris went back to a diagonal bias system
1527 if (ubCnt & 1)
1528 {
1529 // moving on a diagonal
1530 nextCost = nextCost * 14 / 10;
1531 }
1532
1533 if ( bLoopState == LOOPING_REVERSE)
1534 {
1535 // penalize moving backwards to encourage turning sooner
1536 nextCost += 50;
1537 }
1538
1539 newTotCost = curCost + nextCost;
1540
1541 // have we found a path to the current location that
1542 // costs less than the best so far to the same location?
1543 if (trailCostUsed[newLoc] != gubGlobalPathCount || newTotCost < trailCost[newLoc])
1544 {
1545
1546 #if defined( PATHAI_VISIBLE_DEBUG )
1547 if (gfDisplayCoverValues && gfDrawPathPoints)
1548 {
1549 if (gsCoverValue[newLoc] == 0x7F7F)
1550 {
1551 gsCoverValue[newLoc] = usCounter++;
1552 }
1553 /*
1554 else if (gsCoverValue[newLoc] >= 0)
1555 {
1556 gsCoverValue[newLoc]++;
1557 }
1558 else
1559 {
1560 gsCoverValue[newLoc]--;
1561 }*/
1562 }
1563 #endif
1564
1565 //NEWQUENODE;
1566 //{
1567 if (queRequests<QPOOLNDX)
1568 {
1569 pNewPtr = pathQ + (queRequests);
1570 queRequests++;
1571 std::fill_n(pNewPtr->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);
1572 pNewPtr->bLevel = RandomSkipListLevel();
1573 }
1574 else if (iClosedListSize > 0)
1575 {
1576 pNewPtr = pClosedHead->pNext[0];
1577 pClosedHead->pNext[0] = pNewPtr->pNext[0];
1578 iClosedListSize--;
1579 queRequests++;
1580 std::fill_n(pNewPtr->pNext, ABSMAX_SKIPLIST_LEVEL, nullptr);
1581 pNewPtr->bLevel = RandomSkipListLevel();
1582 }
1583 else
1584 {
1585 pNewPtr = NULL;
1586 }
1587 //}
1588
1589 if (pNewPtr == NULL)
1590 {
1591 #ifdef COUNT_PATHS
1592 guiFailedPathChecks++;
1593 #endif
1594 gubNPCAPBudget = 0;
1595 gubNPCDistLimit = 0;
1596 return(0);
1597 }
1598
1599 //make new path to current location
1600 trailTree[trailTreeNdx].nextLink = sCurPathNdx;
1601 trailTree[trailTreeNdx].stepDir = ubCnt;
1602 if ( bLoopState == LOOPING_REVERSE )
1603 {
1604 trailTree[trailTreeNdx].fFlags = STEP_BACKWARDS;
1605 }
1606 else
1607 {
1608 trailTree[trailTreeNdx].fFlags = 0;
1609 }
1610 trailTree[trailTreeNdx].sGridNo = (INT16) newLoc;
1611 pNewPtr->sPathNdx = trailTreeNdx;
1612 trailTreeNdx++;
1613
1614 if (trailTreeNdx >= iMaxTrailTree)
1615 {
1616 #ifdef COUNT_PATHS
1617 guiFailedPathChecks++;
1618 #endif
1619 gubNPCAPBudget = 0;
1620 gubNPCDistLimit = 0;
1621 return(0);
1622 }
1623
1624 iLocY = newLoc / MAPWIDTH;
1625 iLocX = newLoc % MAPWIDTH;
1626 SETLOC( *pNewPtr, newLoc );
1627 pNewPtr->usCostSoFar = (UINT16) newTotCost;
1628 pNewPtr->usCostToGo = (UINT16) REMAININGCOST(pNewPtr);
1629 if ( fCopyReachable )
1630 {
1631 pNewPtr->usCostToGo = 100;
1632 }
1633 else
1634 {
1635 pNewPtr->usCostToGo = (UINT16) REMAININGCOST(pNewPtr);
1636 }
1637
1638 pNewPtr->usTotalCost = newTotCost + pNewPtr->usCostToGo;
1639 pNewPtr->ubLegDistance = LEGDISTANCE( iLocX, iLocY, iDestX, iDestY );
1640
1641 if (gubNPCAPBudget)
1642 {
1643 //save the AP cost so far along this path
1644 pNewPtr->ubTotalAPCost = ubNewAPCost;
1645 // update the AP costs in the AI array of path costs if necessary...
1646 if (fCopyPathCosts)
1647 {
1648 iX = AI_PATHCOST_RADIUS + iLocX - iOriginationX;
1649 iY = AI_PATHCOST_RADIUS + iLocY - iOriginationY;
1650 gubAIPathCosts[iX][iY] = ubNewAPCost;
1651 }
1652 }
1653
1654 //update the trail map to reflect the newer shorter path
1655 trailCost[newLoc] = (UINT16) newTotCost;
1656 trailCostUsed[newLoc] = gubGlobalPathCount;
1657
1658 //do a sorted que insert of the new path
1659 // COMMENTED OUT TO DO BOUNDS CHECKER CC JAN 18 99
1660 //QUEINSERT(pNewPtr);
1661 //#define SkipListInsert( pNewPtr )
1662 {
1663 pCurr = pQueueHead;
1664 uiCost = TOTALCOST( pNewPtr );
1665 std::fill_n(pUpdate, MAX_SKIPLIST_LEVEL, nullptr);
1666 for (iCurrLevel = bSkipListLevel - 1; iCurrLevel >= 0; iCurrLevel--)
1667 {
1668 pNext = pCurr->pNext[iCurrLevel];
1669 while (pNext)
1670 {
1671 if ( uiCost > TOTALCOST( pNext ) || (uiCost == TOTALCOST( pNext ) && FARTHER( pNewPtr, pNext ) ) )
1672 {
1673 pCurr = pNext;
1674 pNext = pCurr->pNext[iCurrLevel];
1675 }
1676 else
1677 {
1678 break;
1679 }
1680 }
1681 pUpdate[iCurrLevel] = pCurr;
1682 }
1683 pCurr = pCurr->pNext[0];
1684 for (iCurrLevel = 0; iCurrLevel < pNewPtr->bLevel; iCurrLevel++)
1685 {
1686 if (!(pUpdate[iCurrLevel]))
1687 {
1688 break;
1689 }
1690 pNewPtr->pNext[iCurrLevel] = pUpdate[iCurrLevel]->pNext[iCurrLevel];
1691 pUpdate[iCurrLevel]->pNext[iCurrLevel] = pNewPtr;
1692 }
1693 iSkipListSize++;
1694 if (iSkipListSize > iSkipListLevelLimit[bSkipListLevel])
1695 {
1696 pCurr = pQueueHead;
1697 pNext = pQueueHead->pNext[bSkipListLevel - 1];
1698 while( pNext )
1699 {
1700 if (pNext->bLevel > bSkipListLevel)
1701 {
1702 pCurr->pNext[bSkipListLevel] = pNext;
1703 pCurr = pNext;
1704 }
1705 pNext = pNext->pNext[bSkipListLevel - 1];
1706 }
1707 pCurr->pNext[bSkipListLevel] = pNext;
1708 bSkipListLevel++;
1709 }
1710 }
1711
1712 #ifdef PATHAI_SKIPLIST_DEBUG
1713 // print out contents of queue
1714 {
1715 INT32 iLoop;
1716 INT8 bTemp;
1717
1718 zTempString[0] = '\0';
1719 pCurr = pQueueHead;
1720 iLoop = 0;
1721 while( pCurr )
1722 {
1723 sprintf( zTS, "\t%ld", pCurr->sPathNdx );
1724 if (pCurr == pNewPtr)
1725 {
1726 strcat( zTS, "*" );
1727 }
1728 strcat( zTempString, zTS );
1729 pCurr = pCurr->pNext[0];
1730 iLoop++;
1731 if (iLoop > 50)
1732 {
1733 break;
1734 }
1735 }
1736 SLOGD(zTempString );
1737
1738
1739 zTempString[0] = '\0';
1740 pCurr = pQueueHead;
1741 iLoop = 0;
1742 while( pCurr )
1743 {
1744 sprintf( zTS, "\t%d", pCurr->bLevel );
1745 strcat( zTempString, zTS );
1746 pCurr = pCurr->pNext[0];
1747 iLoop++;
1748 if (iLoop > 50)
1749 {
1750 break;
1751 }
1752 }
1753 SLOGD(zTempString );
1754
1755 zTempString[0] = '\0';
1756 bTemp = pQueueHead->bLevel;
1757 pCurr = pQueueHead;
1758 iLoop = 0;
1759 while( pCurr )
1760 {
1761 bTemp = pQueueHead->bLevel;
1762 while ( pCurr->pNext[ bTemp - 1 ] == NULL )
1763 {
1764 bTemp--;
1765 }
1766 sprintf( zTS, "\t%d", bTemp );
1767 strcat( zTempString, zTS );
1768 pCurr = pCurr->pNext[0];
1769 iLoop++;
1770 if (iLoop > 50)
1771 {
1772 break;
1773 }
1774 }
1775 SLOGD(zTempString );
1776 SLOGD("------" );
1777 }
1778 #endif
1779
1780 }
1781
1782 NEXTDIR:
1783 if (bLoopState == LOOPING_CLOCKWISE) // backwards
1784 {
1785 ubCnt = OneCCDirection(ubCnt);
1786 }
1787 else
1788 {
1789 ubCnt = OneCDirection(ubCnt);
1790 }
1791 if ( ubCnt == ubLoopEnd )
1792 {
1793 ENDOFLOOP:
1794 break;
1795 }
1796 else if (fContinuousTurnNeeded && ubCnt == OppositeDirection(ubLoopStart))
1797 {
1798 fCheckedBehind = TRUE;
1799 }
1800 }
1801 }
1802 while (pathQNotEmpty && pathNotYetFound);
1803
1804
1805 #if defined( PATHAI_VISIBLE_DEBUG )
1806 if (gfDisplayCoverValues && gfDrawPathPoints)
1807 {
1808 SetRenderFlags( RENDER_FLAG_FULL );
1809 if ( guiCurrentScreen == GAME_SCREEN )
1810 {
1811 RenderWorld();
1812 RenderCoverDebug( );
1813 InvalidateScreen( );
1814 RefreshScreen();
1815 }
1816 }
1817 #endif
1818
1819
1820 // work finished. Did we find a path?
1821 if (pathQNotEmpty && pathFound)
1822 {
1823 INT16 z,_z,_nextLink; //,tempgrid;
1824
1825 _z=0;
1826 z = (INT16) pQueueHead->pNext[0]->sPathNdx;
1827
1828 while (z)
1829 {
1830 _nextLink = trailTree[z].nextLink;
1831 trailTree[z].nextLink = _z;
1832 _z = z;
1833 z = _nextLink;
1834 }
1835
1836 // if this function was called because a solider is about to embark on an actual route
1837 // (as opposed to "test" path finding (used by cursor, etc), then grab all pertinent
1838 // data and copy into soldier's database
1839 if (bCopy == COPYROUTE)
1840 {
1841 z=_z;
1842
1843 for (ubCnt=0; z && (ubCnt < MAX_PATH_LIST_SIZE); ubCnt++)
1844 {
1845 s->ubPathingData[ubCnt] = trailTree[z].stepDir;
1846
1847 z = trailTree[z].nextLink;
1848 }
1849
1850 s->ubPathIndex = 0;
1851 s->ubPathDataSize = ubCnt;
1852
1853 }
1854 else if (bCopy == NO_COPYROUTE)
1855 {
1856
1857 z=_z;
1858 UINT16 iCnt;
1859 for (iCnt = 0; z != 0 && iCnt < lengthof(guiPathingData); iCnt++)
1860 {
1861 guiPathingData[ iCnt ] = trailTree[z].stepDir;
1862
1863 z = trailTree[z].nextLink;
1864 }
1865 ubCnt = iCnt;
1866 giPathDataSize = ubCnt;
1867
1868 }
1869
1870 #if defined( PATHAI_VISIBLE_DEBUG )
1871 if (gfDisplayCoverValues && gfDrawPathPoints)
1872 {
1873 SetRenderFlags( RENDER_FLAG_FULL );
1874 RenderWorld();
1875 RenderCoverDebug( );
1876 InvalidateScreen( );
1877 RefreshScreen();
1878 }
1879 #endif
1880
1881
1882 // return path length : serves as a "successful" flag and a path length counter
1883 #ifdef COUNT_PATHS
1884 guiSuccessfulPathChecks++;
1885 #endif
1886 gubNPCAPBudget = 0;
1887 gubNPCDistLimit = 0;
1888
1889 //TEMP: This is returning zero when I am generating edgepoints, so I am force returning 1 until
1890 // this is fixed?
1891 if( gfGeneratingMapEdgepoints )
1892 {
1893 return TRUE;
1894 }
1895
1896
1897 return(ubCnt);
1898 }
1899
1900 #ifdef COUNT_PATHS
1901 if (fCopyReachable)
1902 {
1903 // actually this is a success
1904 guiSuccessfulPathChecks++;
1905 }
1906 else
1907 {
1908 guiUnsuccessfulPathChecks++;
1909 }
1910 #endif
1911
1912 // failed miserably, report...
1913 gubNPCAPBudget = 0;
1914 gubNPCDistLimit = 0;
1915 return(0);
1916 }
1917
GlobalReachableTest(INT16 sStartGridNo)1918 void GlobalReachableTest( INT16 sStartGridNo )
1919 {
1920 SOLDIERTYPE s;
1921
1922 s = SOLDIERTYPE{};
1923 s.sGridNo = sStartGridNo;
1924 s.bLevel = 0;
1925 s.bTeam = 1;
1926
1927 //reset the flag for gridno's
1928 FOR_EACH_WORLD_TILE(i)
1929 {
1930 i->uiFlags &= ~MAPELEMENT_REACHABLE;
1931 }
1932
1933 ReconfigurePathAI( ABSMAX_SKIPLIST_LEVEL, ABSMAX_TRAIL_TREE, ABSMAX_PATHQ );
1934 FindBestPath( &s, NOWHERE, 0, WALKING, COPYREACHABLE, PATH_THROUGH_PEOPLE );
1935 RestorePathAIToDefaults();
1936 }
1937
LocalReachableTest(INT16 sStartGridNo,INT8 bRadius)1938 void LocalReachableTest( INT16 sStartGridNo, INT8 bRadius )
1939 {
1940 SOLDIERTYPE s;
1941 INT32 iCurrentGridNo = 0;
1942 INT32 iX, iY;
1943
1944 s = SOLDIERTYPE{};
1945 s.sGridNo = sStartGridNo;
1946
1947 //if we are moving on the gorund level
1948 if( gsInterfaceLevel == I_ROOF_LEVEL )
1949 {
1950 s.bLevel = 1;
1951 }
1952 else
1953 {
1954 s.bLevel = 0;
1955 }
1956
1957 s.bTeam = OUR_TEAM;
1958
1959 //reset the flag for gridno's
1960 for ( iY = -bRadius; iY <= bRadius; iY++ )
1961 {
1962 for ( iX = -bRadius; iX <= bRadius; iX++ )
1963 {
1964 iCurrentGridNo = sStartGridNo + iX + iY * MAXCOL;
1965 if ( iCurrentGridNo >= 0 && iCurrentGridNo <= WORLD_MAX )
1966 {
1967 gpWorldLevelData[ iCurrentGridNo ].uiFlags &= ~( MAPELEMENT_REACHABLE );
1968 }
1969 }
1970 }
1971
1972 // set the dist limit
1973 gubNPCDistLimit = bRadius;
1974 // make the function call
1975 FindBestPath( &s, NOWHERE, s.bLevel, WALKING, COPYREACHABLE, PATH_THROUGH_PEOPLE );
1976 // reset dist limit
1977 gubNPCDistLimit = 0;
1978 }
1979
GlobalItemsReachableTest(INT16 sStartGridNo1,INT16 sStartGridNo2)1980 void GlobalItemsReachableTest( INT16 sStartGridNo1, INT16 sStartGridNo2 )
1981 {
1982 SOLDIERTYPE s;
1983
1984 s = SOLDIERTYPE{};
1985 s.sGridNo = sStartGridNo1;
1986 s.bLevel = 0;
1987 s.bTeam = 1;
1988
1989 //reset the flag for gridno's
1990 FOR_EACH_WORLD_TILE(i)
1991 {
1992 i->uiFlags &= ~MAPELEMENT_REACHABLE;
1993 }
1994
1995 ReconfigurePathAI( ABSMAX_SKIPLIST_LEVEL, ABSMAX_TRAIL_TREE, ABSMAX_PATHQ );
1996 FindBestPath( &s, NOWHERE, 0, WALKING, COPYREACHABLE, PATH_THROUGH_PEOPLE );
1997 if ( sStartGridNo2 != NOWHERE )
1998 {
1999 s.sGridNo = sStartGridNo2;
2000 FindBestPath( &s, NOWHERE, 0, WALKING, COPYREACHABLE, PATH_THROUGH_PEOPLE );
2001 }
2002 RestorePathAIToDefaults();
2003 }
2004
RoofReachableTest(INT16 sStartGridNo,UINT8 ubBuildingID)2005 void RoofReachableTest( INT16 sStartGridNo, UINT8 ubBuildingID )
2006 {
2007 SOLDIERTYPE s;
2008
2009 s = SOLDIERTYPE{};
2010 s.sGridNo = sStartGridNo;
2011 s.bLevel = 1;
2012 s.bTeam = 1;
2013
2014 gubBuildingInfoToSet = ubBuildingID;
2015
2016 ReconfigurePathAI( ABSMAX_SKIPLIST_LEVEL, ABSMAX_TRAIL_TREE, ABSMAX_PATHQ );
2017 FindBestPath( &s, NOWHERE, 1, WALKING, COPYREACHABLE, 0 );
2018 RestorePathAIToDefaults();
2019
2020 // set start position to reachable since path code sets it unreachable
2021 gpWorldLevelData[ sStartGridNo ].uiFlags |= MAPELEMENT_REACHABLE;
2022
2023 // reset building variable
2024 gubBuildingInfoToSet = 0;
2025 }
2026
2027
ErasePath()2028 void ErasePath()
2029 {
2030 INT16 iCnt;
2031
2032 // NOTE: This routine must be called BEFORE anything happens that changes
2033 // a merc's gridno, else the....
2034
2035 //EraseAPCursor();
2036
2037 if ( gfUIHandleShowMoveGrid )
2038 {
2039 gfUIHandleShowMoveGrid = FALSE;
2040
2041 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS4);
2042 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS9);
2043 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS2);
2044 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS13);
2045 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS15);
2046 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS19);
2047 RemoveTopmost(gsUIHandleShowMoveGridLocation, FIRSTPOINTERS20);
2048 }
2049
2050 if (!gusPathShown)
2051 {
2052 //OldPath = FALSE;
2053 return;
2054 }
2055
2056
2057 //if (OldPath > 0 && !eraseOldOne)
2058 // return;
2059
2060 //OldPath = FALSE;
2061
2062
2063
2064 gusPathShown = FALSE;
2065
2066
2067 for (iCnt=0; iCnt < giPlotCnt; iCnt++)
2068 {
2069 //Grid[PlottedPath[cnt]].fstep = 0;
2070
2071 RemoveAllObjectsOfTypeRange( guiPlottedPath[iCnt], FOOTPRINTS, FOOTPRINTS );
2072
2073 RemoveAllOnRoofsOfTypeRange( guiPlottedPath[iCnt], FOOTPRINTS, FOOTPRINTS );
2074
2075 //RemoveAllObjectsOfTypeRange( guiPlottedPath[iCnt], FIRSTPOINTERS, FIRSTPOINTERS );
2076 }
2077
2078 //for (cnt=0; cnt < GRIDSIZE; cnt++)
2079 // Grid[cnt].fstep = 0;
2080
2081 giPlotCnt = 0;
2082 std::fill_n(guiPlottedPath, 256, 0);
2083 }
2084
2085
PlotPath(SOLDIERTYPE * const pSold,const INT16 sDestGridno,const INT8 bCopyRoute,const INT8 bPlot,const UINT16 usMovementMode,const INT16 sAPBudget)2086 INT16 PlotPath(SOLDIERTYPE* const pSold, const INT16 sDestGridno, const INT8 bCopyRoute, const INT8 bPlot, const UINT16 usMovementMode, const INT16 sAPBudget)
2087 {
2088 INT16 sTileCost,sPoints=0,sTempGrid,sAnimCost=0;
2089 INT16 sPointsWalk=0,sPointsCrawl=0,sPointsRun=0,sPointsSwat=0;
2090 INT16 sExtraCostStand,sExtraCostSwat,sExtraCostCrawl;
2091 INT32 iCnt;
2092 INT16 sFootOrderIndex;
2093 INT16 sSwitchValue;
2094 INT16 sFootOrder[5] = {
2095 GREENSTEPSTART,
2096 PURPLESTEPSTART,
2097 BLUESTEPSTART,
2098 ORANGESTEPSTART,
2099 REDSTEPSTART
2100 };
2101 UINT16 usTileNum;
2102 LEVELNODE *pNode;
2103 UINT16 usMovementModeToUseForAPs;
2104 BOOLEAN bIgnoreNextCost = FALSE;
2105 INT16 sTestGridno;
2106
2107 if ( bPlot && gusPathShown )
2108 {
2109 ErasePath();
2110 }
2111
2112 gusAPtsToMove = 0;
2113 sTempGrid = (INT16) pSold->sGridNo;
2114
2115 sFootOrderIndex = 0;
2116
2117
2118 //gubNPCMovementMode = (UINT8) usMovementMode;
2119 // distance limit to reduce the cost of plotting a path to a location we can't reach
2120
2121 // For now, use known hight adjustment
2122 if (gfRecalculatingExistingPathCost ||
2123 FindBestPath(pSold, sDestGridno, (INT8)pSold->bLevel, usMovementMode, bCopyRoute, 0 ))
2124 {
2125 // if soldier would be STARTING to run then he pays a penalty since it takes time to
2126 // run full speed
2127 if (pSold->usAnimState != RUNNING)
2128 {
2129 // for estimation purposes, always pay penalty
2130 sPointsRun = AP_START_RUN_COST;
2131 }
2132
2133 // Add to points, those needed to start from different stance!
2134 sPoints += MinAPsToStartMovement( pSold, usMovementMode );
2135
2136
2137 // We should reduce points for starting to run if first tile is a fence...
2138 sTestGridno = NewGridNo(pSold->sGridNo, DirectionInc( guiPathingData[0]));
2139 if ( gubWorldMovementCosts[ sTestGridno ][ guiPathingData[0] ][ pSold->bLevel] == TRAVELCOST_FENCE )
2140 {
2141 if ( usMovementMode == RUNNING && pSold->usAnimState != RUNNING )
2142 {
2143 sPoints -= AP_START_RUN_COST;
2144 }
2145 }
2146
2147 // FIRST, add up "startup" additional costs - such as intermediate animations, etc.
2148 //switch(pSold->usAnimState)
2149 //{
2150 // case START_AID:
2151 // case GIVING_AID:
2152 // sAnimCost = AP_STOP_FIRST_AID;
2153 // break;
2154 // case TWISTOMACH:
2155 // case COLLAPSED:
2156 // sAnimCost = AP_GET_UP;
2157 // break;
2158 // case TWISTBACK:
2159 // case UNCONSCIOUS:
2160 // sAnimCost = (AP_ROLL_OVER+AP_GET_UP);
2161 // break;
2162 // case CROUCHING:
2163 // if (usMovementMode == WALKING || usMovementMode == RUNNING)
2164 // sAnimCost = AP_CROUCH;
2165 // break;
2166 //}
2167
2168
2169 sPoints += sAnimCost;
2170 gusAPtsToMove += sAnimCost;
2171
2172 const INT32 iLastGrid = giPathDataSize;
2173 for ( iCnt=0; iCnt < iLastGrid; iCnt++ )
2174 {
2175 sExtraCostStand = 0;
2176 sExtraCostSwat = 0;
2177 sExtraCostCrawl = 0;
2178
2179 sTempGrid = NewGridNo(sTempGrid, DirectionInc( guiPathingData[iCnt]));
2180
2181 // Get switch value...
2182 sSwitchValue = gubWorldMovementCosts[ sTempGrid ][ guiPathingData[iCnt] ][ pSold->bLevel];
2183
2184 // get the tile cost for that tile based on WALKING
2185 sTileCost = TerrainActionPoints( pSold, sTempGrid, guiPathingData[iCnt], pSold->bLevel );
2186
2187 usMovementModeToUseForAPs = usMovementMode;
2188
2189 // ATE - MAKE MOVEMENT ALWAYS WALK IF IN WATER
2190 if (gpWorldLevelData[sTempGrid].ubTerrainID == DEEP_WATER ||
2191 gpWorldLevelData[sTempGrid].ubTerrainID == MED_WATER ||
2192 gpWorldLevelData[sTempGrid].ubTerrainID == LOW_WATER)
2193 {
2194 usMovementModeToUseForAPs = WALKING;
2195 }
2196
2197 if ( bIgnoreNextCost )
2198 {
2199 bIgnoreNextCost = FALSE;
2200 }
2201 else
2202 {
2203 // ATE: If we have a 'special cost, like jump fence...
2204 if ( sSwitchValue == TRAVELCOST_FENCE )
2205 {
2206 sPoints += sTileCost;
2207
2208 bIgnoreNextCost = TRUE;
2209
2210 // If we are changeing stance ( either before or after getting there....
2211 // We need to reflect that...
2212 switch( usMovementModeToUseForAPs )
2213 {
2214 case RUNNING:
2215 case WALKING:
2216 // Add here cost to go from crouch to stand AFTER fence hop....
2217 // Since it's AFTER.. make sure we will be moving after jump...
2218 if ( ( iCnt + 2 ) < iLastGrid )
2219 {
2220 sExtraCostStand += AP_CROUCH;
2221
2222 // ATE: if running, charge extra point to srart again
2223 if ( usMovementModeToUseForAPs== RUNNING )
2224 {
2225 sExtraCostStand++;
2226 }
2227
2228 sPoints += sExtraCostStand;
2229 }
2230 break;
2231
2232 case SWATTING:
2233 // Add cost to stand once there BEFORE....
2234 sExtraCostSwat += AP_CROUCH;
2235 sPoints += sExtraCostSwat;
2236 break;
2237
2238 case CRAWLING:
2239 // Can't do it here.....
2240 break;
2241
2242 }
2243 }
2244 else if (sTileCost > 0)
2245 {
2246 // else, movement is adjusted based on mode...
2247
2248 if (sSwitchValue == TRAVELCOST_NOT_STANDING)
2249 {
2250 switch( usMovementModeToUseForAPs )
2251 {
2252 case RUNNING:
2253 case WALKING :
2254 // charge crouch APs for ducking head!
2255 sExtraCostStand += AP_CROUCH;
2256 break;
2257
2258 default:
2259 break;
2260 }
2261 }
2262
2263 // so, then we must modify it for other movement styles and accumulate
2264 switch( usMovementModeToUseForAPs )
2265 {
2266 case RUNNING:
2267 sPoints += (INT16)((DOUBLE)(sTileCost) / RUNDIVISOR) + sExtraCostStand; break;
2268 case WALKING :
2269 sPoints += (sTileCost + WALKCOST) + sExtraCostStand;
2270 break;
2271 case SWATTING:
2272 sPoints += (sTileCost + SWATCOST) + sExtraCostSwat;
2273 break;
2274 case CRAWLING:
2275 sPoints += (sTileCost + CRAWLCOST) + sExtraCostCrawl;
2276 break;
2277 default:
2278 sPoints += sTileCost;
2279 break;
2280 }
2281 }
2282 }
2283
2284 // THIS NEXT SECTION ONLY NEEDS TO HAPPEN FOR CURSOR UI FEEDBACK, NOT ACTUAL COSTING
2285
2286 if (bPlot && (gTacticalStatus.uiFlags & INCOMBAT)) // OR USER OPTION ON... ***)
2287 {
2288 // ATE; TODO: Put stuff in here to allow for fact of costs other than movement ( jump fence, open door )
2289
2290 // store WALK cost
2291 sPointsWalk += (sTileCost + WALKCOST) + sExtraCostStand;
2292
2293 // now get cost as if CRAWLING
2294 sPointsCrawl += (sTileCost + CRAWLCOST) + sExtraCostCrawl;
2295
2296 // now get cost as if SWATTING
2297 sPointsSwat += (sTileCost + SWATCOST) + sExtraCostSwat;
2298
2299 // now get cost as if RUNNING
2300 sPointsRun += (INT16)((DOUBLE)(sTileCost) / RUNDIVISOR) + sExtraCostStand;
2301 }
2302
2303 if ( iCnt == 0 && bPlot )
2304 {
2305 gusAPtsToMove = sPoints;
2306
2307 giPlotCnt = 0;
2308
2309 }
2310
2311
2312 //if (gTacticalStatus.uiFlags & INCOMBAT) // OR USER OPTION "show paths" ON... ***
2313 {
2314 if (bPlot && iCnt < iLastGrid - 1 && giPlotCnt < static_cast<INT32>(lengthof(guiPlottedPath)))
2315 {
2316 guiPlottedPath[giPlotCnt++] = sTempGrid;
2317
2318 // we need a footstep graphic ENTERING the next tile
2319
2320 // get the direction
2321 usTileNum = (UINT16) guiPathingData[iCnt] + 2;
2322 if (usTileNum > 8)
2323 {
2324 usTileNum = 1;
2325 }
2326
2327 // Are we a vehicle?
2328 if ( pSold->uiStatusFlags & SOLDIER_VEHICLE )
2329 {
2330 // did we exceed WALK cost?
2331 if ( sPointsSwat > sAPBudget)
2332 {
2333 sFootOrderIndex = 4;
2334 }
2335 else
2336 {
2337 sFootOrderIndex = 3;
2338 }
2339 }
2340 else
2341 {
2342 // did we exceed CRAWL cost?
2343 if (sFootOrderIndex == 0 && sPointsCrawl > sAPBudget)
2344 {
2345 sFootOrderIndex++;
2346 }
2347
2348 // did we exceed WALK cost?
2349 if (sFootOrderIndex == 1 && sPointsSwat > sAPBudget)
2350 {
2351 sFootOrderIndex++;
2352 }
2353
2354 // did we exceed SWAT cost?
2355 if (sFootOrderIndex == 2 && sPointsWalk > sAPBudget)
2356 {
2357 sFootOrderIndex++;
2358 }
2359
2360 // did we exceed RUN cost?
2361 if (sFootOrderIndex == 3 && sPointsRun > sAPBudget)
2362 {
2363 sFootOrderIndex++;
2364 }
2365 }
2366
2367 UINT16 usTileIndex;
2368 usTileIndex = GetTileIndexFromTypeSubIndex(FOOTPRINTS, usTileNum);
2369
2370 // Adjust based on what mode we are in...
2371 if (!(gTacticalStatus.uiFlags & INCOMBAT))
2372 {
2373 // find out which color we're using
2374 usTileIndex += sFootOrder[ 4 ];
2375 }
2376 else // turn based
2377 {
2378 // find out which color we're using
2379 usTileIndex += sFootOrder[sFootOrderIndex];
2380 }
2381
2382
2383 /*
2384 if ( sPoints <= sAPBudget)
2385 {
2386 // find out which color we're using
2387 usTileIndex += sFootOrder[sFootOrderIndex];
2388 }
2389 else
2390 {
2391 // use red footprints ( offset by 16 )
2392 usTileIndex += REDSTEPSTART;
2393 }*/
2394
2395 if ( pSold->bLevel == 0 )
2396 {
2397 pNode = AddObjectToTail(sTempGrid, usTileIndex );
2398 pNode->ubShadeLevel=DEFAULT_SHADE_LEVEL;
2399 pNode->ubNaturalShadeLevel=DEFAULT_SHADE_LEVEL;
2400 }
2401 else
2402 {
2403 pNode = AddOnRoofToTail(sTempGrid, usTileIndex );
2404 pNode->ubShadeLevel=DEFAULT_SHADE_LEVEL;
2405 pNode->ubNaturalShadeLevel=DEFAULT_SHADE_LEVEL;
2406 }
2407
2408
2409
2410 // we need a footstep graphic LEAVING this tile
2411
2412 // get the direction using the NEXT tile (thus iCnt+1 as index)
2413 usTileNum = (UINT16) guiPathingData[iCnt + 1] + 2;
2414 if (usTileNum > 8)
2415 {
2416 usTileNum = 1;
2417 }
2418
2419
2420 // this is a LEAVING footstep which is always the second set of 8
2421 usTileNum += 8;
2422
2423 usTileIndex = GetTileIndexFromTypeSubIndex(FOOTPRINTS, usTileNum);
2424
2425 // Adjust based on what mode we are in...
2426 if (!(gTacticalStatus.uiFlags & INCOMBAT))
2427 {
2428 // find out which color we're using
2429 usTileIndex += sFootOrder[ 4 ];
2430 }
2431 else // turnbased
2432 {
2433 // find out which color we're using
2434 usTileIndex += sFootOrder[sFootOrderIndex];
2435 }
2436
2437
2438
2439 if ( pSold->bLevel == 0 )
2440 {
2441 pNode = AddObjectToTail(sTempGrid, usTileIndex );
2442 pNode->ubShadeLevel=DEFAULT_SHADE_LEVEL;
2443 pNode->ubNaturalShadeLevel=DEFAULT_SHADE_LEVEL;
2444 }
2445 else
2446 {
2447 pNode = AddOnRoofToTail(sTempGrid, usTileIndex );
2448 pNode->ubShadeLevel=DEFAULT_SHADE_LEVEL;
2449 pNode->ubNaturalShadeLevel=DEFAULT_SHADE_LEVEL;
2450 }
2451 }
2452
2453 } // end of if turn based or real-time user option "show paths" on...
2454 }
2455
2456 if ( bPlot )
2457 {
2458 gusPathShown = TRUE;
2459 }
2460
2461 } // end of found a path
2462
2463 // reset distance limit
2464 gubNPCDistLimit = 0;
2465
2466 return(sPoints);
2467 }
2468
2469
UIPlotPath(SOLDIERTYPE * const pSold,const INT16 sDestGridno,const INT8 bCopyRoute,INT8 bPlot,const UINT16 usMovementMode,const INT16 sAPBudget)2470 INT16 UIPlotPath(SOLDIERTYPE* const pSold, const INT16 sDestGridno, const INT8 bCopyRoute, INT8 bPlot, const UINT16 usMovementMode, const INT16 sAPBudget)
2471 {
2472 // This function is specifically for UI calls to the pathing routine, to
2473 // check whether the shift key is pressed, etc.
2474
2475 if ( _KeyDown( SHIFT ) )
2476 {
2477 gfPlotDirectPath = TRUE;
2478 }
2479
2480 // If we are on the same level as the interface level, continue, else return
2481 if ( pSold->bLevel != gsInterfaceLevel )
2482 {
2483 return( 0 );
2484 }
2485
2486 if ( gGameSettings.fOptions[ TOPTION_ALWAYS_SHOW_MOVEMENT_PATH ] )
2487 {
2488 bPlot = TRUE;
2489 }
2490
2491 const INT16 sRet = PlotPath(pSold, sDestGridno, bCopyRoute, bPlot, usMovementMode, sAPBudget);
2492 gfPlotDirectPath = FALSE;
2493 return( sRet );
2494 }
2495
RecalculatePathCost(SOLDIERTYPE * pSoldier,UINT16 usMovementMode)2496 INT16 RecalculatePathCost( SOLDIERTYPE *pSoldier, UINT16 usMovementMode )
2497 {
2498 // AI function for a soldier already with a path; this will return the cost of that
2499 // path using the given movement mode
2500
2501 if ( !pSoldier->bPathStored || pSoldier->ubPathDataSize == 0 )
2502 {
2503 return( 0 );
2504 }
2505
2506 gfRecalculatingExistingPathCost = TRUE;
2507 const INT16 sRet = PlotPath(pSoldier, pSoldier->sFinalDestination, NO_COPYROUTE, FALSE, usMovementMode, 0);
2508 gfRecalculatingExistingPathCost = FALSE;
2509 return( sRet );
2510 }
2511
2512
EstimatePlotPath(SOLDIERTYPE * const pSold,const INT16 sDestGridno,const INT8 bCopyRoute,const INT8 bPlot,const UINT16 usMovementMode,const INT16 sAPBudget)2513 INT16 EstimatePlotPath(SOLDIERTYPE* const pSold, const INT16 sDestGridno, const INT8 bCopyRoute, const INT8 bPlot, const UINT16 usMovementMode, const INT16 sAPBudget)
2514 {
2515 // This function is specifically for AI calls to estimate path cost to a location
2516 // It sets stuff up to ignore all people
2517
2518 gfEstimatePath = TRUE;
2519
2520 const INT16 sRet = PlotPath(pSold, sDestGridno, bCopyRoute, bPlot, usMovementMode, sAPBudget);
2521
2522 gfEstimatePath = FALSE;
2523
2524 return( sRet );
2525 }
2526
2527
InternalDoorTravelCost(const SOLDIERTYPE * pSoldier,INT32 iGridNo,UINT8 ubMovementCost,BOOLEAN fReturnPerceivedValue,INT32 * piDoorGridNo,BOOLEAN fReturnDoorCost)2528 UINT8 InternalDoorTravelCost(const SOLDIERTYPE* pSoldier, INT32 iGridNo, UINT8 ubMovementCost, BOOLEAN fReturnPerceivedValue, INT32* piDoorGridNo, BOOLEAN fReturnDoorCost)
2529 {
2530 // This function will return either TRAVELCOST_DOOR (in place of closed door cost),
2531 // TRAVELCOST_OBSTACLE, or the base ground terrain
2532 // travel cost, depending on whether or not the door is open or closed etc.
2533 BOOLEAN fDoorIsObstacleIfClosed=FALSE;
2534 INT32 iDoorGridNo=-1;
2535 DOOR_STATUS *pDoorStatus;
2536 DOOR *pDoor;
2537 STRUCTURE *pDoorStructure;
2538 BOOLEAN fDoorIsOpen;
2539 UINT8 ubReplacementCost;
2540
2541 if ( IS_TRAVELCOST_DOOR( ubMovementCost ) )
2542 {
2543 ubReplacementCost = ubMovementCost;
2544
2545 switch( ubMovementCost )
2546 {
2547 case TRAVELCOST_DOOR_CLOSED_HERE:
2548 fDoorIsObstacleIfClosed = TRUE;
2549 iDoorGridNo = iGridNo;
2550 ubReplacementCost = TRAVELCOST_DOOR;
2551 break;
2552 case TRAVELCOST_DOOR_CLOSED_N:
2553 fDoorIsObstacleIfClosed = TRUE;
2554 iDoorGridNo = iGridNo + DirIncrementer[ NORTH ];
2555 ubReplacementCost = TRAVELCOST_DOOR;
2556 break;
2557 case TRAVELCOST_DOOR_CLOSED_W:
2558 fDoorIsObstacleIfClosed = TRUE;
2559 iDoorGridNo = iGridNo + DirIncrementer[ WEST ];
2560 ubReplacementCost = TRAVELCOST_DOOR;
2561 break;
2562 case TRAVELCOST_DOOR_OPEN_HERE:
2563 fDoorIsObstacleIfClosed = FALSE;
2564 iDoorGridNo = iGridNo;
2565 break;
2566 case TRAVELCOST_DOOR_OPEN_N:
2567 fDoorIsObstacleIfClosed = FALSE;
2568 iDoorGridNo = iGridNo + DirIncrementer[ NORTH ];
2569 break;
2570 case TRAVELCOST_DOOR_OPEN_NE:
2571 fDoorIsObstacleIfClosed = FALSE;
2572 iDoorGridNo = iGridNo + DirIncrementer[ NORTHEAST ];
2573 break;
2574 case TRAVELCOST_DOOR_OPEN_E:
2575 fDoorIsObstacleIfClosed = FALSE;
2576 iDoorGridNo = iGridNo + DirIncrementer[ EAST ];
2577 break;
2578 case TRAVELCOST_DOOR_OPEN_SE:
2579 fDoorIsObstacleIfClosed = FALSE;
2580 iDoorGridNo = iGridNo + DirIncrementer[ SOUTHEAST ];
2581 break;
2582 case TRAVELCOST_DOOR_OPEN_S:
2583 fDoorIsObstacleIfClosed = FALSE;
2584 iDoorGridNo = iGridNo + DirIncrementer[ SOUTH ];
2585 break;
2586 case TRAVELCOST_DOOR_OPEN_SW:
2587 fDoorIsObstacleIfClosed = FALSE;
2588 iDoorGridNo = iGridNo + DirIncrementer[ SOUTHWEST ];
2589 break;
2590 case TRAVELCOST_DOOR_OPEN_W:
2591 fDoorIsObstacleIfClosed = FALSE;
2592 iDoorGridNo = iGridNo + DirIncrementer[ WEST ];
2593 break;
2594 case TRAVELCOST_DOOR_OPEN_NW:
2595 fDoorIsObstacleIfClosed = FALSE;
2596 iDoorGridNo = iGridNo + DirIncrementer[ NORTHWEST ];
2597 break;
2598 case TRAVELCOST_DOOR_OPEN_N_N:
2599 fDoorIsObstacleIfClosed = FALSE;
2600 iDoorGridNo = iGridNo + DirIncrementer[ NORTH ] + DirIncrementer[ NORTH ];
2601 break;
2602 case TRAVELCOST_DOOR_OPEN_NW_N:
2603 fDoorIsObstacleIfClosed = FALSE;
2604 iDoorGridNo = iGridNo + DirIncrementer[ NORTHWEST ] + DirIncrementer[ NORTH ];
2605 break;
2606 case TRAVELCOST_DOOR_OPEN_NE_N:
2607 fDoorIsObstacleIfClosed = FALSE;
2608 iDoorGridNo = iGridNo + DirIncrementer[ NORTHEAST ] + DirIncrementer[ NORTH ];
2609 break;
2610 case TRAVELCOST_DOOR_OPEN_W_W:
2611 fDoorIsObstacleIfClosed = FALSE;
2612 iDoorGridNo = iGridNo + DirIncrementer[ WEST ] + DirIncrementer[ WEST ];
2613 break;
2614 case TRAVELCOST_DOOR_OPEN_SW_W:
2615 fDoorIsObstacleIfClosed = FALSE;
2616 iDoorGridNo = iGridNo + DirIncrementer[ SOUTHWEST ] + DirIncrementer[ WEST ];
2617 break;
2618 case TRAVELCOST_DOOR_OPEN_NW_W:
2619 fDoorIsObstacleIfClosed = FALSE;
2620 iDoorGridNo = iGridNo + DirIncrementer[ NORTHWEST ] + DirIncrementer[ WEST ];
2621 break;
2622 default:
2623 ubReplacementCost = TRAVELCOST_OBSTACLE;
2624 break;
2625 }
2626
2627 if ( pSoldier && (pSoldier->uiStatusFlags & SOLDIER_MONSTER || pSoldier->uiStatusFlags & SOLDIER_ANIMAL) )
2628 {
2629 // can't open doors!
2630 ubReplacementCost = TRAVELCOST_OBSTACLE;
2631 }
2632
2633 if (piDoorGridNo)
2634 {
2635 // return gridno of door through pointer
2636 *piDoorGridNo = iDoorGridNo;
2637 }
2638
2639 if (fReturnPerceivedValue &&
2640 gpWorldLevelData[ iDoorGridNo ].ubExtFlags[0] & MAPELEMENT_EXT_DOOR_STATUS_PRESENT)
2641 {
2642 // check door status
2643 pDoorStatus = GetDoorStatus( (INT16) iDoorGridNo );
2644 if (pDoorStatus)
2645 {
2646 fDoorIsOpen = (pDoorStatus->ubFlags & DOOR_PERCEIVED_OPEN) != 0;
2647 }
2648 else
2649 {
2650 // abort!
2651 return( ubMovementCost );
2652 }
2653 }
2654 else
2655 {
2656 // check door structure
2657 pDoorStructure = FindStructure( (INT16) iDoorGridNo, STRUCTURE_ANYDOOR );
2658 if (pDoorStructure)
2659 {
2660 fDoorIsOpen = (pDoorStructure->fFlags & STRUCTURE_OPEN) != 0;
2661 }
2662 else
2663 {
2664 // abort!
2665 return( ubMovementCost );
2666 }
2667 }
2668 // now determine movement cost
2669 if (fDoorIsOpen)
2670 {
2671 if (fDoorIsObstacleIfClosed)
2672 {
2673 ubMovementCost = gTileTypeMovementCost[ gpWorldLevelData[ iGridNo ].ubTerrainID ];
2674 }
2675 else
2676 {
2677 ubMovementCost = ubReplacementCost;
2678 }
2679 }
2680 else
2681 {
2682 if (fDoorIsObstacleIfClosed)
2683 {
2684 // door is closed and this should be an obstacle, EXCEPT if we are calculating
2685 // a path for an enemy or NPC with keys
2686
2687 // creatures and animals can't open doors!
2688 if (fReturnPerceivedValue ||
2689 (pSoldier && (pSoldier->uiStatusFlags & SOLDIER_MONSTER ||
2690 pSoldier->uiStatusFlags & SOLDIER_ANIMAL)))
2691 {
2692 ubMovementCost = ubReplacementCost;
2693 }
2694 else
2695 {
2696 // have to check if door is locked and NPC does not have keys!
2697 pDoor = FindDoorInfoAtGridNo( iDoorGridNo );
2698 if ( pDoor )
2699 {
2700 if ( ( !pDoor->fLocked || (pSoldier && pSoldier->bHasKeys) ) && !fReturnDoorCost )
2701 {
2702 ubMovementCost = gTileTypeMovementCost[ gpWorldLevelData[ iGridNo ].ubTerrainID ];
2703 }
2704 else
2705 {
2706 ubMovementCost = ubReplacementCost;
2707 }
2708 }
2709 else
2710 {
2711 ubMovementCost = ubReplacementCost;
2712 }
2713 }
2714 }
2715 else
2716 {
2717 ubMovementCost = gTileTypeMovementCost[ gpWorldLevelData[ iGridNo ].ubTerrainID ];
2718 }
2719 }
2720
2721 }
2722 return( ubMovementCost );
2723 }
2724
2725
DoorTravelCost(const SOLDIERTYPE * pSoldier,INT32 iGridNo,UINT8 ubMovementCost,BOOLEAN fReturnPerceivedValue,INT32 * piDoorGridNo)2726 UINT8 DoorTravelCost(const SOLDIERTYPE* pSoldier, INT32 iGridNo, UINT8 ubMovementCost, BOOLEAN fReturnPerceivedValue, INT32* piDoorGridNo)
2727 {
2728 return( InternalDoorTravelCost( pSoldier, iGridNo, ubMovementCost, fReturnPerceivedValue, piDoorGridNo, FALSE ) );
2729 }
2730