1 #include "Strategic_Movement_Costs.h"
2 #include "Types.h"
3 #include "WorldDef.h"
4 #include "MapScreen.h"
5 #include "Overhead.h"
6 #include "StrategicMap.h"
7 #include "Strategic_Pathing.h"
8 #include "Map_Screen_Interface_Border.h"
9 #include "Game_Clock.h"
10 #include "Strategic_Movement.h"
11 #include "Campaign_Types.h"
12 #include "Assignments.h"
13 #include "Squads.h"
14 #include "Vehicles.h"
15 #include "Map_Screen_Helicopter.h"
16 #include "Input.h"
17 #include "English.h"
18 #include "Game_Event_Hook.h"
19 #include "Strategic_AI.h"
20 #include "Debug.h"
21 #include "MemMan.h"
22
23 #include <algorithm>
24 #include <iterator>
25
26 static UINT16 gusMapPathingData[256];
27 static BOOLEAN gfPlotToAvoidPlayerInfuencedSectors = FALSE;
28
29
30 // Globals
31 struct path_t
32 {
33 INT16 nextLink; //2
34 INT16 prevLink; //2
35 INT16 location; //2
36 INT16 pathNdx; //2
37 INT32 costSoFar; //4
38 INT32 costToGo; //4
39 };
40
41 struct trail_t
42 {
43 short nextLink;
44 short diStratDelta;
45 };
46
47 #define MAXTRAILTREE (4096)
48 #define MAXpathQ (512)
49 #define MAP_WIDTH 18
50 #define MAP_LENGTH MAP_WIDTH*MAP_WIDTH
51
52 //#define EASYWATERCOST TRAVELCOST_FLAT / 2
53 //#define ISWATER(t) (((t)==TRAVELCOST_KNEEDEEP) || ((t)==TRAVELCOST_DEEPWATER))
54 //#define NOPASS (TRAVELCOST_OBSTACLE)
55 //#define VEINCOST TRAVELCOST_FLAT //actual cost for bridges and doors and such
56 #define TRAILCELLTYPE UINT32
57 #define TRAILCELLMAX 0xFFFFFFFF
58
59 static path_t pathQB[MAXpathQ];
60 static TRAILCELLTYPE trailCostB[MAP_LENGTH];
61 static trail_t trailStratTreeB[MAXTRAILTREE];
62 static short trailStratTreedxB = 0;
63
64 #define QHEADNDX (0)
65 #define QPOOLNDX (MAXpathQ-1)
66
67 #define pathQNotEmpty (pathQB[QHEADNDX].nextLink!=QHEADNDX)
68 #define pathFound (pathQB[ pathQB[QHEADNDX].nextLink ].location == sDestination)
69 #define pathNotYetFound (!pathFound)
70
71 #define REMQUENODE(ndx) \
72 do \
73 { \
74 pathQB[pathQB[ndx].prevLink].nextLink = pathQB[ndx].nextLink; \
75 pathQB[pathQB[ndx].nextLink].prevLink = pathQB[ndx].prevLink; \
76 } \
77 while (0)
78
79 #define INSQUENODEPREV(newNode, curNode) \
80 do \
81 { \
82 pathQB[newNode].nextLink = curNode; \
83 pathQB[newNode].prevLink = pathQB[curNode].prevLink; \
84 pathQB[pathQB[curNode].prevLink].nextLink = newNode; \
85 pathQB[curNode].prevLink = newNode; \
86 } \
87 while (0)
88
89 #define INSQUENODE(newNode,curNode) \
90 { pathQB[ newNode ].prevLink = curNode; \
91 pathQB[ newNode ].NextLink = pathQB[ curNode ].nextLink; \
92 pathQB[ pathQB[curNode].nextLink ].prevLink = newNode; \
93 pathQB[ curNode ].nextLink = newNode; \
94 }
95
96 #define DELQUENODE(ndx) \
97 do \
98 { \
99 REMQUENODE(ndx); \
100 INSQUENODEPREV(ndx, QPOOLNDX); \
101 pathQB[ndx].location = -1; \
102 } \
103 while (0)
104
105 #define NEWQUENODE \
106 do \
107 { \
108 if (queRequests < QPOOLNDX) \
109 { \
110 qNewNdx = queRequests++; \
111 } \
112 else \
113 { \
114 qNewNdx = pathQB[QPOOLNDX].nextLink; \
115 REMQUENODE(qNewNdx); \
116 } \
117 } \
118 while (0)
119
120 #define ESTIMATE0 ((dx>dy) ? (dx) : (dy))
121 #define ESTIMATE1 ((dx<dy) ? ((dx*14)/10+dy) : ((dy*14)/10+dx) )
122 #define ESTIMATE2 FLATCOST*( (dx<dy) ? ((dx*14)/10+dy) : ((dy*14)/10+dx) )
123 #define ESTIMATEn ((int)(FLATCOST*sqrt(dx*dx+dy*dy)))
124 #define ESTIMATE ESTIMATE1
125
126
127 #define REMAININGCOST(ndx) \
128 ( \
129 (locY = pathQB[ndx].location/MAP_WIDTH), \
130 (locX = pathQB[ndx].location%MAP_WIDTH), \
131 (dy = ABS(iDestY-locY)), \
132 (dx = ABS(iDestX-locX)), \
133 ESTIMATE \
134 )
135
136
137 #define MAXCOST (99900)
138 #define TOTALCOST(ndx) (pathQB[ndx].costSoFar + pathQB[ndx].costToGo)
139 #define XLOC(a) (a%MAP_WIDTH)
140 #define YLOC(a) (a/MAP_WIDTH)
141 #define LEGDISTANCE(a,b) ( ABS( XLOC(b)-XLOC(a) ) + ABS( YLOC(b)-YLOC(a) ) )
142 #define FARTHER(ndx,NDX) ( LEGDISTANCE(pathQB[ndx].location,sDestination) > LEGDISTANCE(pathQB[NDX].location,sDestination) )
143
144 #define FLAT_STRATEGIC_TRAVEL_TIME 60
145
146 #define QUESEARCH(ndx,NDX) \
147 do \
148 { \
149 INT32 k = TOTALCOST(ndx); \
150 NDX = pathQB[QHEADNDX].nextLink; \
151 while(NDX && (k > TOTALCOST(NDX))) \
152 { \
153 NDX = pathQB[NDX].nextLink; \
154 } \
155 while (NDX && (k == TOTALCOST(NDX)) && FARTHER(ndx, NDX)) \
156 { \
157 NDX = pathQB[NDX].nextLink; \
158 } \
159 } \
160 while (0)
161
162
163 static INT32 queRequests;
164
165
166 static INT16 const diStratDelta[]=
167 {
168 -MAP_WIDTH, //N
169 1-MAP_WIDTH, //NE
170 1, //E
171 1+MAP_WIDTH, //SE
172 MAP_WIDTH, //S
173 MAP_WIDTH-1, //SW
174 -1, //W
175 -MAP_WIDTH-1 //NW
176 };
177
178
179 // this will find if a shortest strategic path
180
FindStratPath(INT16 const sStart,INT16 const sDestination,GROUP const & g,BOOLEAN const fTacticalTraversal)181 INT32 FindStratPath(INT16 const sStart, INT16 const sDestination, GROUP const& g, BOOLEAN const fTacticalTraversal)
182 {
183 INT32 iCnt,ndx,insertNdx,qNewNdx;
184 INT32 iDestX,iDestY,locX,locY,dx,dy;
185 INT16 sSectorX, sSectorY;
186 UINT16 newLoc,curLoc;
187 TRAILCELLTYPE curCost,newTotCost,nextCost;
188 INT16 sOrigination;
189 BOOLEAN fPlotDirectPath = FALSE;
190 static BOOLEAN fPreviousPlotDirectPath = FALSE; // don't save
191
192 // ******** Fudge by Bret (for now), curAPcost is never initialized in this function, but should be!
193 // so this is just to keep things happy!
194
195 // for player groups only!
196 if (g.fPlayer)
197 {
198 // if player is holding down SHIFT key, find the shortest route instead of the quickest route!
199 if ( _KeyDown( SHIFT ) )
200 {
201 fPlotDirectPath = TRUE;
202 }
203
204
205 if ( fPlotDirectPath != fPreviousPlotDirectPath )
206 {
207 // must redraw map to erase the previous path...
208 fMapPanelDirty = TRUE;
209 fPreviousPlotDirectPath = fPlotDirectPath;
210 }
211 }
212
213
214 queRequests = 2;
215
216 //initialize the ai data structures
217 std::fill(std::begin(trailStratTreeB), std::end(trailStratTreeB), trail_t{});
218 std::fill(std::begin(trailCostB), std::end(trailCostB), TRAILCELLMAX);
219
220 std::fill(std::begin(pathQB), std::end(pathQB), path_t{});
221
222 // FOLLOWING LINE COMMENTED OUT ON MARCH 7/97 BY IC
223 std::fill(std::begin(gusMapPathingData), std::end(gusMapPathingData), ((UINT16)sStart));
224 trailStratTreedxB=0;
225
226 //set up common info
227 sOrigination = sStart;
228
229
230 iDestY = (sDestination / MAP_WIDTH);
231 iDestX = (sDestination % MAP_WIDTH);
232
233
234 // if origin and dest is water, then user wants to stay in water!
235 // so, check and set waterToWater flag accordingly
236
237
238
239 //setup Q
240 pathQB[QHEADNDX].location = sOrigination;
241 pathQB[QHEADNDX].nextLink = 1;
242 pathQB[QHEADNDX].prevLink = 1;
243 pathQB[QHEADNDX].costSoFar = MAXCOST;
244
245 pathQB[QPOOLNDX].nextLink = QPOOLNDX;
246 pathQB[QPOOLNDX].prevLink = QPOOLNDX;
247
248 //setup first path record
249 pathQB[1].nextLink = QHEADNDX;
250 pathQB[1].prevLink = QHEADNDX;
251 pathQB[1].location = sOrigination;
252 pathQB[1].pathNdx = 0;
253 pathQB[1].costSoFar= 0;
254 pathQB[1].costToGo = REMAININGCOST(1);
255
256
257 trailStratTreedxB =0;
258 trailCostB[sOrigination]=0;
259 ndx = pathQB[QHEADNDX].nextLink;
260 pathQB[ndx].pathNdx = trailStratTreedxB;
261 trailStratTreedxB++;
262
263 const GROUP* const heli_group = iHelicopterVehicleId != -1 ?
264 GetGroup(GetHelicopter().ubMovementGroup) : 0;
265
266 do
267 {
268 //remove the first and best path so far from the que
269 ndx = pathQB[QHEADNDX].nextLink;
270 curLoc = pathQB[ndx].location;
271 curCost = pathQB[ndx].costSoFar;
272 DELQUENODE( (INT16)ndx );
273
274 if (trailCostB[curLoc] < curCost)
275 continue;
276
277
278 //contemplate a new path in each direction
279 for (iCnt=0; iCnt < 8; iCnt+=2)
280 {
281 newLoc = curLoc + diStratDelta[iCnt];
282
283
284 // are we going off the map?
285 if( ( newLoc % MAP_WORLD_X == 0 )||( newLoc%MAP_WORLD_X == MAP_WORLD_X -1 ) || ( newLoc / MAP_WORLD_X == 0 ) || ( newLoc / MAP_WORLD_X == MAP_WORLD_X - 1 ) )
286 {
287 // yeppers
288 continue;
289 }
290
291 if( gfPlotToAvoidPlayerInfuencedSectors && newLoc != sDestination )
292 {
293 sSectorX = (INT16)( newLoc % MAP_WORLD_X );
294 sSectorY = (INT16)( newLoc / MAP_WORLD_X );
295
296 if( IsThereASoldierInThisSector( sSectorX, sSectorY, 0 ) )
297 {
298 continue;
299 }
300 if( GetNumberOfMilitiaInSector( sSectorX, sSectorY, 0 ) )
301 {
302 continue;
303 }
304 if( !OkayForEnemyToMoveThroughSector( (UINT8)SECTOR( sSectorX, sSectorY ) ) )
305 {
306 continue;
307 }
308 }
309
310 // are we plotting path or checking for existance of one?
311 nextCost = GetSectorMvtTimeForGroup(SECTOR(curLoc % MAP_WORLD_X, curLoc / MAP_WORLD_X), iCnt / 2, &g);
312 if (nextCost == TRAVERSE_TIME_IMPOSSIBLE) continue;
313
314 if (&g == heli_group)
315 {
316 // is a heli, its pathing is determined not by time (it's always the same) but by total cost
317 // Skyrider will avoid uncontrolled airspace as much as possible...
318 if (StrategicMap[curLoc].fEnemyAirControlled)
319 {
320 nextCost = COST_AIRSPACE_UNSAFE;
321 }
322 else
323 {
324 nextCost = COST_AIRSPACE_SAFE;
325 }
326 }
327
328 // if we're building this path due to a tactical traversal exit, we have to force the path to the next sector be
329 // in the same direction as the traversal, even if it's not the shortest route, otherwise pathing can crash! This
330 // can happen in places where the long way around to next sector is actually shorter: e.g. D5 to D6. ARM
331 if ( fTacticalTraversal )
332 {
333 // if it's the first sector only (no cost yet)
334 if( curCost == 0 && ( newLoc == sDestination ) )
335 {
336 if( GetTraversability( ( INT16 )( SECTOR( curLoc % 18, curLoc / 18 ) ), ( INT16 ) ( SECTOR( newLoc %18, newLoc / 18 ) ) ) != GROUNDBARRIER )
337 {
338 nextCost = 0;
339 }
340 }
341 }
342 else
343 {
344 if ( fPlotDirectPath )
345 {
346 // use shortest route instead of faster route
347 nextCost = FLAT_STRATEGIC_TRAVEL_TIME;
348 }
349 }
350
351 /*
352 // Commented out by CJC Feb 4 1999... causing errors!
353
354 //make the destination look very attractive
355 if( ( newLoc == sDestination ) )
356 {
357 if( GetTraversability( ( INT16 )( SECTOR( curLoc % 18, curLoc / 18 ) ), ( INT16 ) ( SECTOR( newLoc %18, newLoc / 18 ) ) ) != GROUNDBARRIER )
358 {
359 nextCost = 0;
360 }
361 }
362 */
363 newTotCost = curCost + nextCost;
364 if (newTotCost < trailCostB[newLoc])
365 {
366 NEWQUENODE;
367
368 if (qNewNdx == QHEADNDX)
369 {
370 return(0);
371 }
372
373
374 if (qNewNdx == QPOOLNDX)
375 {
376 return(0);
377 }
378
379 //make new path to current location
380 trailStratTreeB[trailStratTreedxB].nextLink = pathQB[ndx].pathNdx;
381 trailStratTreeB[trailStratTreedxB].diStratDelta = (INT16) iCnt;
382 pathQB[qNewNdx].pathNdx = trailStratTreedxB;
383 trailStratTreedxB++;
384
385
386 if (trailStratTreedxB >= MAXTRAILTREE)
387 {
388 return(0);
389 }
390
391 pathQB[qNewNdx].location = (INT16) newLoc;
392 pathQB[qNewNdx].costSoFar = newTotCost;
393 pathQB[qNewNdx].costToGo = REMAININGCOST(qNewNdx);
394 trailCostB[newLoc]=newTotCost;
395 //do a sorted que insert of the new path
396 QUESEARCH(qNewNdx,insertNdx);
397 INSQUENODEPREV( (INT16)qNewNdx, (INT16)insertNdx);
398 }
399 }
400 }
401 while (pathQNotEmpty && pathNotYetFound);
402 // work finished. Did we find a path?
403 if (pathFound)
404 {
405 INT16 z,_z,_nextLink; //,tempgrid;
406
407 _z=0;
408 z=pathQB[ pathQB[QHEADNDX].nextLink ].pathNdx;
409
410 while (z)
411 {
412 _nextLink = trailStratTreeB[z].nextLink;
413 trailStratTreeB[z].nextLink = _z;
414 _z = z;
415 z = _nextLink;
416 }
417
418 // if this function was called because a solider is about to embark on an actual route
419 // (as opposed to "test" path finding (used by cursor, etc), then grab all pertinent
420 // data and copy into soldier's database
421
422
423 z=_z;
424
425 for (iCnt=0; z && (iCnt < MAX_PATH_LIST_SIZE); iCnt++)
426 {
427 gusMapPathingData[ iCnt ] = trailStratTreeB[z].diStratDelta;
428
429 z = trailStratTreeB[z].nextLink;
430 }
431
432 // return path length : serves as a "successful" flag and a path length counter
433 return(iCnt);
434 }
435 // failed miserably, report...
436 return(0);
437 }
438
439
BuildAStrategicPath(INT16 const start_sector,INT16 const end_sector,GROUP const & g,BOOLEAN const fTacticalTraversal)440 PathSt* BuildAStrategicPath(INT16 const start_sector, INT16 const end_sector, GROUP const& g, BOOLEAN const fTacticalTraversal)
441 {
442 if (end_sector < MAP_WORLD_X - 1) return NULL;
443
444 const INT32 path_len = FindStratPath(start_sector, end_sector, g, fTacticalTraversal);
445 if (path_len == 0) return NULL;
446
447 // start new path list
448 PathSt* const head = new PathSt{};
449 head->uiSectorId = start_sector;
450 head->pNext = NULL;
451 head->pPrev = NULL;
452
453 INT32 cur_sector = start_sector;
454 INT32 delta = 0;
455 PathSt* path = head;
456 for (INT32 i = 0; i < path_len; ++i)
457 {
458 switch (gusMapPathingData[i])
459 {
460 case NORTH: delta = NORTH_MOVE; break;
461 case SOUTH: delta = SOUTH_MOVE; break;
462 case EAST: delta = EAST_MOVE; break;
463 case WEST: delta = WEST_MOVE; break;
464 }
465 // create new node
466 cur_sector += delta;
467
468 if (cur_sector < MAP_WORLD_X - 1)
469 {
470 ClearStrategicPathList(head, 0);
471 return NULL;
472 }
473
474 PathSt* const n = new PathSt{};
475 n->uiSectorId = cur_sector;
476 n->pPrev = path;
477 n->pNext = NULL;
478 path->pNext = n;
479 path = n;
480 }
481
482 return head;
483 }
484
485
AppendStrategicPath(PathSt * pNewSection,PathSt * pHeadOfPathList)486 PathSt* AppendStrategicPath(PathSt* pNewSection, PathSt* pHeadOfPathList)
487 {
488 // will append a new section onto the end of the head of list, then return the head of the new list
489
490 PathSt* pNode = pHeadOfPathList;
491 // move to end of original section
492
493 if( pNewSection == NULL )
494 {
495 return pHeadOfPathList;
496 }
497
498
499 // is there in fact a list to append to
500 if( pNode )
501 {
502 // move to tail of old list
503 while( pNode -> pNext )
504 {
505 // next node in list
506 pNode = pNode ->pNext;
507 }
508
509 // make sure the 2 are not the same
510
511 if( pNode -> uiSectorId == pNewSection -> uiSectorId )
512 {
513 // are the same, remove head of new list
514 pNewSection = RemoveHeadFromStrategicPath( pNewSection );
515 }
516
517 // append onto old list
518 pNode -> pNext = pNewSection;
519 pNewSection -> pPrev = pNode;
520
521 }
522 else
523 {
524 // head of list becomes head of new section
525 pHeadOfPathList = pNewSection;
526 }
527
528 // return head of new list
529 return( pHeadOfPathList );
530 }
531
532
ClearStrategicPathList(PathSt * const pHeadOfPath,const INT16 sMvtGroup)533 PathSt* ClearStrategicPathList(PathSt* const pHeadOfPath, const INT16 sMvtGroup)
534 {
535 // will clear out a strategic path and return head of list as NULL
536
537 // is there in fact a path?
538 if (pHeadOfPath == NULL) return NULL;
539 Assert(pHeadOfPath->pPrev == NULL);
540
541 for (PathSt* n = pHeadOfPath; n != NULL;)
542 {
543 PathSt* const del = n;
544 n = n->pNext;
545 delete del;
546 }
547
548 if (sMvtGroup != -1 && sMvtGroup != 0)
549 {
550 RemoveGroupWaypoints(*GetGroup(sMvtGroup));
551 }
552 return NULL;
553 }
554
555
556 static PathSt* MoveToEndOfPathList(PathSt* pList);
557
558
ClearStrategicPathListAfterThisSector(PathSt * pHeadOfPath,INT16 sX,INT16 sY,INT16 sMvtGroup)559 PathSt* ClearStrategicPathListAfterThisSector(PathSt* pHeadOfPath, INT16 sX, INT16 sY, INT16 sMvtGroup)
560 {
561 // will clear out a strategic path and return head of list as NULL
562 PathSt* pNode = pHeadOfPath;
563 PathSt* pDeleteNode = pHeadOfPath;
564 INT16 sSector = 0;
565 INT16 sCurrentSector = -1;
566
567
568
569 // is there in fact a path?
570 if( pNode == NULL )
571 {
572 // no path, leave
573 return ( pNode );
574 }
575
576
577 // get sector value
578 sSector = sX + ( sY * MAP_WORLD_X );
579
580 // go to end of list
581 pNode = MoveToEndOfPathList( pNode );
582
583 // get current sector value
584 sCurrentSector = ( INT16 )pNode -> uiSectorId;
585
586 // move through list
587 while( ( pNode )&&( sSector != sCurrentSector ) )
588 {
589
590 // next value
591 pNode = pNode -> pPrev;
592
593 // get current sector value
594 if( pNode != NULL )
595 {
596 sCurrentSector = ( INT16 )pNode -> uiSectorId;
597 }
598 }
599
600 // did we find the target sector?
601 if( pNode == NULL )
602 {
603 // nope, leave
604 return ( pHeadOfPath );
605 }
606
607
608 // we want to KEEP the target sector, not delete it, so advance to the next sector
609 pNode = pNode -> pNext;
610
611 // is nothing left?
612 if( pNode == NULL )
613 {
614 // that's it, leave
615 return ( pHeadOfPath );
616 }
617
618
619 // if we're NOT about to clear the head (there's a previous entry)
620 if( pNode -> pPrev )
621 {
622 // set next for tail to NULL
623 pNode -> pPrev -> pNext = NULL;
624 }
625 else
626 {
627 // clear head, return NULL
628 pHeadOfPath = ClearStrategicPathList( pHeadOfPath, sMvtGroup );
629
630 return ( NULL );
631 }
632
633 // clear list
634 while( pNode -> pNext )
635 {
636 // set up delete node
637 pDeleteNode = pNode;
638
639 // move to next node
640 pNode = pNode -> pNext;
641
642 // check if we are clearing the head of the list
643 if( pDeleteNode == pHeadOfPath )
644 {
645 // null out head
646 pHeadOfPath = NULL;
647 }
648
649 // delete delete node
650 delete pDeleteNode;
651 }
652
653
654 // clear out last node
655 delete pNode;
656 pNode = NULL;
657 pDeleteNode = NULL;
658
659 return( pHeadOfPath );
660 }
661
662
MoveToEndOfPathList(PathSt * pList)663 static PathSt* MoveToEndOfPathList(PathSt* pList)
664 {
665 // move to end of list
666
667 // no list, return
668 if( pList == NULL )
669 {
670 return ( NULL );
671 }
672
673 // move to beginning of list
674 while( pList -> pNext )
675 {
676 pList = pList -> pNext;
677 }
678
679 return ( pList );
680
681 }
682
683
RemoveTailFromStrategicPath(PathSt * pHeadOfList)684 static PathSt* RemoveTailFromStrategicPath(PathSt* pHeadOfList)
685 {
686 // remove the tail section from the strategic path
687 PathSt* pNode = pHeadOfList;
688 PathSt* pLastNode = pHeadOfList;
689
690 if( pNode == NULL )
691 {
692 // no list, leave
693 return( NULL );
694 }
695
696 while( pNode -> pNext )
697 {
698 pLastNode = pNode;
699 pNode = pNode -> pNext;
700 }
701
702 // end of list
703
704 // set next to null
705 pLastNode -> pNext = NULL;
706
707 // now remove old last node
708 delete pNode;
709
710 // return head of new list
711 return( pHeadOfList );
712
713 }
714
715
RemoveHeadFromStrategicPath(PathSt * pList)716 PathSt* RemoveHeadFromStrategicPath(PathSt* pList)
717 {
718 // move to head of list
719 PathSt* pNode = pList;
720 PathSt* pNewHead = pList;
721
722 // check if there is a list
723 if( pNode == NULL )
724 {
725 // no list, leave
726 return( NULL );
727 }
728
729 // move to head of list
730 while( pNode ->pPrev )
731 {
732 // back one node
733 pNode = pNode -> pPrev;
734 }
735
736 // set up new head
737 pNewHead = pNode -> pNext;
738 if( pNewHead )
739 {
740 pNewHead -> pPrev = NULL;
741 }
742
743 // free old head
744 delete pNode;
745
746 pNode = NULL;
747
748 // return new head
749 return( pNewHead );
750 }
751
752
GetLastSectorIdInCharactersPath(const SOLDIERTYPE * pCharacter)753 INT16 GetLastSectorIdInCharactersPath(const SOLDIERTYPE* pCharacter)
754 {
755 // will return the last sector of the current path, or the current sector if there's no path
756 INT16 sLastSector = ( pCharacter -> sSectorX ) + ( pCharacter ->sSectorY ) * ( MAP_WORLD_X );
757 PathSt* pNode = NULL;
758
759 pNode = GetSoldierMercPathPtr( pCharacter );
760
761 while( pNode )
762 {
763 sLastSector = ( INT16 ) ( pNode -> uiSectorId );
764 pNode = pNode -> pNext;
765 }
766
767 return sLastSector;
768 }
769
770
CopyPaths(PathSt * src)771 PathSt* CopyPaths(PathSt* src)
772 {
773 if (src == NULL) return NULL;
774
775 PathSt* const head = new PathSt{};
776 head->uiSectorId = src->uiSectorId;
777 head->pPrev = NULL;
778
779 for (PathSt* dst = head;;)
780 {
781 src = src->pNext;
782 if (src == NULL)
783 {
784 dst->pNext = NULL;
785 break;
786 }
787
788 PathSt* const p = new PathSt{};
789 p->uiSectorId = src->uiSectorId;
790 p->pPrev = dst;
791
792 dst->pNext = p;
793 dst = p;
794 }
795
796 return head;
797 }
798
799
800 #ifdef BETA_VERSION
VerifyAllMercsInGroupAreOnSameSquad(GROUP const & g)801 static void VerifyAllMercsInGroupAreOnSameSquad(GROUP const& g)
802 {
803 SOLDIERTYPE *pSoldier;
804 INT8 bSquad = -1;
805
806 // Let's choose somebody in group.....
807 CFOR_EACH_PLAYER_IN_GROUP(pPlayer, &g)
808 {
809 pSoldier = pPlayer->pSoldier;
810 Assert( pSoldier );
811
812 if ( pSoldier->bAssignment < ON_DUTY )
813 {
814 if ( bSquad == -1 )
815 {
816 bSquad = pSoldier->bAssignment;
817 }
818 else
819 {
820 // better be the same squad!
821 Assert( pSoldier->bAssignment == bSquad );
822 }
823 }
824 }
825 }
826 #endif
827
828
RebuildWayPointsForGroupPath(PathSt * const pHeadOfPath,GROUP & g)829 void RebuildWayPointsForGroupPath(PathSt* const pHeadOfPath, GROUP& g)
830 {
831 INT32 iDelta = 0;
832 INT32 iOldDelta = 0;
833 BOOLEAN fFirstNode = TRUE;
834 PathSt* pNode = pHeadOfPath;
835 WAYPOINT *wp = NULL;
836
837 //KRIS! Added this because it was possible to plot a new course to the same destination, and the
838 // group would add new arrival events without removing the existing one(s).
839 DeleteStrategicEvent(EVENT_GROUP_ARRIVAL, g.ubGroupID);
840
841 RemoveGroupWaypoints(g);
842
843 if (g.fPlayer)
844 {
845 #ifdef BETA_VERSION
846 VerifyAllMercsInGroupAreOnSameSquad(g);
847 #endif
848
849 // update the destination(s) in the team list
850 fTeamPanelDirty = TRUE;
851
852 // update the ETA in character info
853 fCharacterInfoPanelDirty = TRUE;
854
855 // allows assignments to flash right away if their subject moves away/returns (robot/vehicle being repaired), or
856 // patient/doctor/student/trainer being automatically put on a squad via the movement menu.
857 gfReEvaluateEveryonesNothingToDo = TRUE;
858 }
859
860
861 // if group has no path planned at all
862 if( ( pNode == NULL ) || ( pNode->pNext == NULL ) )
863 {
864 // and it's a player group, and it's between sectors
865 // NOTE: AI groups never reverse direction between sectors, Kris cheats & teleports them back to their current sector!
866 if (g.fPlayer && g.fBetweenSectors)
867 {
868 // send the group right back to its current sector by reversing directions
869 GroupReversingDirectionsBetweenSectors(&g, g.ubSectorX, g.ubSectorY, FALSE);
870 }
871
872 return;
873 }
874
875
876 // if we're currently between sectors
877 if (g.fBetweenSectors)
878 {
879 // figure out which direction we're already going in (Otherwise iOldDelta starts at 0)
880 iOldDelta = CALCULATE_STRATEGIC_INDEX(g.ubNextX, g.ubNextY) - CALCULATE_STRATEGIC_INDEX(g.ubSectorX, g.ubSectorY);
881 }
882
883 // build a brand new list of waypoints, one for initial direction, and another for every "direction change" thereafter
884 while( pNode->pNext )
885 {
886 iDelta = pNode->pNext->uiSectorId - pNode->uiSectorId;
887 Assert( iDelta != 0 ); // same sector should never repeat in the path list
888
889 // Waypoints are only added at "pivot points" - whenever there is a change in orthogonal direction.
890 // If we're NOT currently between sectors, iOldDelta will start off at 0, which means that the first node can't be
891 // added as a waypoint. This is what we want - for stationary mercs, the first node in a path is the CURRENT sector.
892 if( ( iOldDelta != 0 ) && ( iDelta != iOldDelta ) )
893 {
894 // add this strategic sector as a waypoint
895 AddWaypointStrategicIDToPGroup(&g, pNode->uiSectorId);
896 }
897
898 // remember this delta
899 iOldDelta = iDelta;
900
901 pNode = pNode->pNext;
902 fFirstNode = FALSE;
903 }
904
905
906 // there must have been at least one next node, or we would have bailed out on "no path" earlier
907 Assert( !fFirstNode );
908
909 // the final destination sector - always add a waypoint for it
910 AddWaypointStrategicIDToPGroup(&g, pNode->uiSectorId);
911
912 // at this point, the final sector in the path must be identical to this group's last waypoint
913 wp = GetFinalWaypoint(&g);
914 AssertMsg( wp, "Path exists, but no waypoints were added! AM-0" );
915 AssertMsg( pNode->uiSectorId == ( UINT32 ) CALCULATE_STRATEGIC_INDEX( wp->x, wp->y ), "Last waypoint differs from final path sector! AM-0" );
916
917
918 // see if we've already reached the first sector in the path (we never actually left the sector and reversed back to it)
919 if (g.uiArrivalTime == GetWorldTotalMin())
920 {
921 // never really left. Must set check for battle TRUE in order for HandleNonCombatGroupArrival() to run!
922 GroupArrivedAtSector(g, TRUE, TRUE);
923 }
924 }
925
926
927 // clear strategic movement (mercpaths and waypoints) for this soldier, and his group (including its vehicles)
ClearMvtForThisSoldierAndGang(SOLDIERTYPE * pSoldier)928 void ClearMvtForThisSoldierAndGang( SOLDIERTYPE *pSoldier )
929 {
930 GROUP *pGroup = NULL;
931
932
933 // check if valid grunt
934 Assert( pSoldier );
935
936 pGroup = GetGroup( pSoldier->ubGroupID );
937 Assert( pGroup );
938
939 // clear their strategic movement (mercpaths and waypoints)
940 ClearMercPathsAndWaypointsForAllInGroup(*pGroup);
941 }
942
943
MoveGroupFromSectorToSector(GROUP & g,INT16 const sStartX,INT16 const sStartY,INT16 const sDestX,INT16 const sDestY)944 BOOLEAN MoveGroupFromSectorToSector(GROUP& g, INT16 const sStartX, INT16 const sStartY, INT16 const sDestX, INT16 const sDestY)
945 {
946 PathSt* pNode = BuildAStrategicPath((INT16)CALCULATE_STRATEGIC_INDEX(sStartX, sStartY), (INT16)CALCULATE_STRATEGIC_INDEX(sDestX, sDestY), g, FALSE);
947
948 if( pNode == NULL )
949 {
950 return( FALSE );
951 }
952
953 // start movement to next sector
954 RebuildWayPointsForGroupPath(pNode, g);
955
956 // now clear out the mess
957 pNode = ClearStrategicPathList( pNode, -1 );
958
959 return( TRUE );
960 }
961
962
MoveGroupFromSectorToSectorButAvoidLastSector(GROUP & g,INT16 const sStartX,INT16 const sStartY,INT16 const sDestX,INT16 const sDestY)963 static BOOLEAN MoveGroupFromSectorToSectorButAvoidLastSector(GROUP& g, INT16 const sStartX, INT16 const sStartY, INT16 const sDestX, INT16 const sDestY)
964 {
965 PathSt* pNode = BuildAStrategicPath((INT16)CALCULATE_STRATEGIC_INDEX(sStartX, sStartY), (INT16)CALCULATE_STRATEGIC_INDEX(sDestX, sDestY), g, FALSE);
966
967 if( pNode == NULL )
968 {
969 return( FALSE );
970 }
971
972 // remove tail from path
973 pNode = RemoveTailFromStrategicPath( pNode );
974
975 // start movement to next sector
976 RebuildWayPointsForGroupPath(pNode, g);
977
978 // now clear out the mess
979 pNode = ClearStrategicPathList( pNode, -1 );
980
981 return( TRUE );
982 }
983
984
MoveGroupFromSectorToSectorButAvoidPlayerInfluencedSectors(GROUP & g,INT16 const sStartX,INT16 const sStartY,INT16 const sDestX,INT16 const sDestY)985 BOOLEAN MoveGroupFromSectorToSectorButAvoidPlayerInfluencedSectors(GROUP& g, INT16 const sStartX, INT16 const sStartY, INT16 const sDestX, INT16 const sDestY)
986 {
987 // init sectors with soldiers in them
988 InitSectorsWithSoldiersList( );
989
990 // build the list of sectors with soldier in them
991 BuildSectorsWithSoldiersList( );
992
993 // turn on the avoid flag
994 gfPlotToAvoidPlayerInfuencedSectors = TRUE;
995
996 PathSt* pNode = BuildAStrategicPath((INT16)CALCULATE_STRATEGIC_INDEX(sStartX, sStartY), (INT16)CALCULATE_STRATEGIC_INDEX(sDestX, sDestY), g, FALSE);
997
998 // turn off the avoid flag
999 gfPlotToAvoidPlayerInfuencedSectors = FALSE;
1000
1001 if( pNode == NULL )
1002 {
1003 return MoveGroupFromSectorToSector(g, sStartX, sStartY, sDestX, sDestY);
1004 }
1005
1006 // start movement to next sector
1007 RebuildWayPointsForGroupPath(pNode, g);
1008
1009 // now clear out the mess
1010 pNode = ClearStrategicPathList( pNode, -1 );
1011
1012 return( TRUE );
1013 }
1014
1015
MoveGroupFromSectorToSectorButAvoidPlayerInfluencedSectorsAndStopOneSectorBeforeEnd(GROUP & g,INT16 const sStartX,INT16 const sStartY,INT16 const sDestX,INT16 const sDestY)1016 BOOLEAN MoveGroupFromSectorToSectorButAvoidPlayerInfluencedSectorsAndStopOneSectorBeforeEnd(GROUP& g, INT16 const sStartX, INT16 const sStartY, INT16 const sDestX, INT16 const sDestY)
1017 {
1018 // init sectors with soldiers in them
1019 InitSectorsWithSoldiersList( );
1020
1021 // build the list of sectors with soldier in them
1022 BuildSectorsWithSoldiersList( );
1023
1024 // turn on the avoid flag
1025 gfPlotToAvoidPlayerInfuencedSectors = TRUE;
1026
1027 PathSt* pNode = BuildAStrategicPath((INT16)CALCULATE_STRATEGIC_INDEX(sStartX, sStartY), (INT16)CALCULATE_STRATEGIC_INDEX(sDestX, sDestY), g, FALSE);
1028
1029 // turn off the avoid flag
1030 gfPlotToAvoidPlayerInfuencedSectors = FALSE;
1031
1032 if( pNode == NULL )
1033 {
1034 return MoveGroupFromSectorToSectorButAvoidLastSector(g, sStartX, sStartY, sDestX, sDestY);
1035 }
1036
1037 // remove tail from path
1038 pNode = RemoveTailFromStrategicPath( pNode );
1039
1040 // start movement to next sector
1041 RebuildWayPointsForGroupPath(pNode, g);
1042
1043 // now clear out the mess
1044 pNode = ClearStrategicPathList( pNode, -1 );
1045
1046 return( TRUE );
1047 }
1048
1049
GetLengthOfPath(PathSt * pHeadPath)1050 INT32 GetLengthOfPath(PathSt* pHeadPath)
1051 {
1052 INT32 iLength = 0;
1053 PathSt* pNode = pHeadPath;
1054
1055 while( pNode )
1056 {
1057 pNode = pNode->pNext;
1058 iLength++;
1059 }
1060
1061 return( iLength );
1062 }
1063
1064
GetLengthOfMercPath(const SOLDIERTYPE * pSoldier)1065 INT32 GetLengthOfMercPath(const SOLDIERTYPE* pSoldier)
1066 {
1067 PathSt* pNode = NULL;
1068 INT32 iLength = 0;
1069
1070 pNode = GetSoldierMercPathPtr( pSoldier );
1071 iLength = GetLengthOfPath( pNode );
1072 return( iLength );
1073 }
1074
1075
GetSoldierMercPathPtr(SOLDIERTYPE const * const s)1076 PathSt* GetSoldierMercPathPtr(SOLDIERTYPE const* const s)
1077 {
1078 Assert(s);
1079 return
1080 /* In a vehicle? */
1081 s->bAssignment == VEHICLE ? pVehicleList[s->iVehicleId].pMercPath :
1082 /* Is a vehicle? */
1083 s->uiStatusFlags & SOLDIER_VEHICLE ? pVehicleList[s->bVehicleID].pMercPath :
1084 /* A person */
1085 s->pMercPath;
1086 }
1087
1088
GetGroupMercPathPtr(GROUP const & g)1089 PathSt* GetGroupMercPathPtr(GROUP const& g)
1090 {
1091 Assert(g.fPlayer);
1092
1093 if (g.fVehicle)
1094 {
1095 return GetVehicleFromMvtGroup(g).pMercPath;
1096 }
1097
1098 if (g.pPlayerList && g.pPlayerList->pSoldier) // XXX pSoldier test necessary?
1099 {
1100 return g.pPlayerList->pSoldier->pMercPath;
1101 }
1102
1103 return 0;
1104 }
1105
1106
GetSoldierGroup(SOLDIERTYPE const & s)1107 GROUP* GetSoldierGroup(SOLDIERTYPE const& s)
1108 {
1109 UINT8 const group_id =
1110 /* In a vehicle? */
1111 s.bAssignment == VEHICLE ? pVehicleList[s.iVehicleId].ubMovementGroup :
1112 /* Is a vehicle? */
1113 s.uiStatusFlags & SOLDIER_VEHICLE ? pVehicleList[s.bVehicleID].ubMovementGroup :
1114 /* A person */
1115 s.ubGroupID;
1116 return GetGroup(group_id);
1117 }
1118
1119
1120 static void ClearPathForSoldier(SOLDIERTYPE* pSoldier);
1121
1122
1123 // clears this groups strategic movement (mercpaths and waypoints), include those in the vehicle structs(!)
ClearMercPathsAndWaypointsForAllInGroup(GROUP & g)1124 void ClearMercPathsAndWaypointsForAllInGroup(GROUP& g)
1125 {
1126 SOLDIERTYPE *pSoldier = NULL;
1127
1128 CFOR_EACH_PLAYER_IN_GROUP(pPlayer, &g)
1129 {
1130 pSoldier = pPlayer->pSoldier;
1131
1132 if ( pSoldier != NULL )
1133 {
1134 ClearPathForSoldier( pSoldier );
1135 }
1136 }
1137
1138 // if it's a vehicle
1139 if (g.fVehicle)
1140 {
1141 VEHICLETYPE& v = GetVehicleFromMvtGroup(g);
1142 // clear the path for that vehicle
1143 v.pMercPath = ClearStrategicPathList(v.pMercPath, v.ubMovementGroup);
1144 }
1145
1146 // clear the waypoints for this group too - no mercpath = no waypoints!
1147 RemoveGroupWaypoints(g);
1148 }
1149
1150
1151 // clears the contents of the soldier's mercpPath, as well as his vehicle path if he is a / or is in a vehicle
ClearPathForSoldier(SOLDIERTYPE * pSoldier)1152 static void ClearPathForSoldier(SOLDIERTYPE* pSoldier)
1153 {
1154 VEHICLETYPE *pVehicle = NULL;
1155
1156
1157 // clear the soldier's mercpath
1158 pSoldier->pMercPath = ClearStrategicPathList( pSoldier->pMercPath, pSoldier->ubGroupID );
1159
1160 // if a vehicle
1161 if( pSoldier->uiStatusFlags & SOLDIER_VEHICLE )
1162 {
1163 pVehicle = &( pVehicleList[ pSoldier->bVehicleID ] );
1164 }
1165 // or in a vehicle
1166 else if( pSoldier->bAssignment == VEHICLE )
1167 {
1168 pVehicle = &( pVehicleList[ pSoldier->iVehicleId ] );
1169 }
1170
1171 // if there's an associate vehicle structure
1172 if ( pVehicle != NULL )
1173 {
1174 // clear its mercpath, too
1175 pVehicle->pMercPath = ClearStrategicPathList( pVehicle->pMercPath, pVehicle->ubMovementGroup );
1176 }
1177 }
1178
1179
1180 static void AddSectorToFrontOfMercPath(PathSt** ppMercPath, UINT8 ubSectorX, UINT8 ubSectorY);
1181
1182
AddSectorToFrontOfMercPathForAllSoldiersInGroup(GROUP * pGroup,UINT8 ubSectorX,UINT8 ubSectorY)1183 void AddSectorToFrontOfMercPathForAllSoldiersInGroup( GROUP *pGroup, UINT8 ubSectorX, UINT8 ubSectorY )
1184 {
1185 SOLDIERTYPE *pSoldier = NULL;
1186
1187 CFOR_EACH_PLAYER_IN_GROUP(pPlayer, pGroup)
1188 {
1189 pSoldier = pPlayer->pSoldier;
1190
1191 if ( pSoldier != NULL )
1192 {
1193 AddSectorToFrontOfMercPath( &(pSoldier->pMercPath), ubSectorX, ubSectorY );
1194 }
1195 }
1196
1197 // if it's a vehicle
1198 if ( pGroup->fVehicle )
1199 {
1200 VEHICLETYPE& v = GetVehicleFromMvtGroup(*pGroup);
1201 // add it to that vehicle's path
1202 AddSectorToFrontOfMercPath(&v.pMercPath, ubSectorX, ubSectorY);
1203 }
1204 }
1205
1206
AddSectorToFrontOfMercPath(PathSt ** ppMercPath,UINT8 ubSectorX,UINT8 ubSectorY)1207 static void AddSectorToFrontOfMercPath(PathSt** ppMercPath, UINT8 ubSectorX, UINT8 ubSectorY)
1208 {
1209 // allocate and hang a new node at the front of the path list
1210 PathSt* const pNode = new PathSt{};
1211 pNode->uiSectorId = CALCULATE_STRATEGIC_INDEX( ubSectorX, ubSectorY );
1212 pNode->pNext = *ppMercPath;
1213 pNode->pPrev = NULL;
1214
1215 // if path wasn't null
1216 if ( *ppMercPath != NULL )
1217 {
1218 // hang the previous pointer of the old head to the new head
1219 (*ppMercPath)->pPrev = pNode;
1220 }
1221
1222 *ppMercPath = pNode;
1223 }
1224