1 /*
2 This file is part of Warzone 2100.
3 Copyright (C) 1999-2004 Eidos Interactive
4 Copyright (C) 2005-2020 Warzone 2100 Project
5
6 Warzone 2100 is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 Warzone 2100 is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with Warzone 2100; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20 /**
21 * @file fpath.c
22 *
23 * Interface to the routing functions.
24 *
25 */
26
27 #include <future>
28 #include <unordered_map>
29
30 #include "lib/framework/frame.h"
31 #include "lib/framework/crc.h"
32 #include "lib/netplay/netplay.h"
33
34 #include "lib/framework/wzapp.h"
35
36 #include "objects.h"
37 #include "map.h"
38 #include "multiplay.h"
39 #include "astar.h"
40
41 #include "fpath.h"
42
43 // If the path finding system is shutdown or not
44 static volatile bool fpathQuit = false;
45
46 /* Beware: Enabling this will cause significant slow-down. */
47 #undef DEBUG_MAP
48
49 struct PATHRESULT
50 {
51 UDWORD droidID; ///< Unique droid ID.
52 MOVE_CONTROL sMove; ///< New movement values for the droid.
53 FPATH_RETVAL retval; ///< Result value from path-finding.
54 Vector2i originalDest; ///< Used to check if the pathfinding job is to the right destination.
55 };
56
57
58 // threading stuff
59 static WZ_THREAD *fpathThread = nullptr;
60 static WZ_MUTEX *fpathMutex = nullptr;
61 static WZ_SEMAPHORE *fpathSemaphore = nullptr;
62 using packagedPathJob = wz::packaged_task<PATHRESULT()>;
63 static std::list<packagedPathJob> pathJobs;
64 static std::unordered_map<uint32_t, wz::future<PATHRESULT>> pathResults;
65
66 static bool waitingForResult = false;
67 static uint32_t waitingForResultId;
68 static WZ_SEMAPHORE *waitingForResultSemaphore = nullptr;
69
70 static PATHRESULT fpathExecute(PATHJOB psJob);
71
72
73 /** This runs in a separate thread */
fpathThreadFunc(void *)74 static int fpathThreadFunc(void *)
75 {
76 wzMutexLock(fpathMutex);
77
78 while (!fpathQuit)
79 {
80 if (pathJobs.empty())
81 {
82 ASSERT(!waitingForResult, "Waiting for a result (id %u) that doesn't exist.", waitingForResultId);
83 wzMutexUnlock(fpathMutex);
84 wzSemaphoreWait(fpathSemaphore); // Go to sleep until needed.
85 wzMutexLock(fpathMutex);
86 continue;
87 }
88
89 // Copy the first job from the queue.
90 packagedPathJob job = std::move(pathJobs.front());
91 pathJobs.pop_front();
92
93 wzMutexUnlock(fpathMutex);
94 job();
95 wzMutexLock(fpathMutex);
96
97 waitingForResult = false;
98 objTrace(waitingForResultId, "These are the droids you are looking for.");
99 wzSemaphorePost(waitingForResultSemaphore);
100 }
101 wzMutexUnlock(fpathMutex);
102 return 0;
103 }
104
105
106 // initialise the findpath module
fpathInitialise()107 bool fpathInitialise()
108 {
109 // The path system is up
110 fpathQuit = false;
111
112 if (!fpathThread)
113 {
114 fpathMutex = wzMutexCreate();
115 fpathSemaphore = wzSemaphoreCreate(0);
116 waitingForResultSemaphore = wzSemaphoreCreate(0);
117 fpathThread = wzThreadCreate(fpathThreadFunc, nullptr);
118 wzThreadStart(fpathThread);
119 }
120
121 return true;
122 }
123
124
fpathShutdown()125 void fpathShutdown()
126 {
127 if (fpathThread)
128 {
129 // Signal the path finding thread to quit
130 fpathQuit = true;
131 wzSemaphorePost(fpathSemaphore); // Wake up thread.
132
133 wzThreadJoin(fpathThread);
134 fpathThread = nullptr;
135 wzMutexDestroy(fpathMutex);
136 fpathMutex = nullptr;
137 wzSemaphoreDestroy(fpathSemaphore);
138 fpathSemaphore = nullptr;
139 wzSemaphoreDestroy(waitingForResultSemaphore);
140 waitingForResultSemaphore = nullptr;
141 }
142 fpathHardTableReset();
143 }
144
145
146 /**
147 * Updates the pathfinding system.
148 * @ingroup pathfinding
149 */
fpathUpdate()150 void fpathUpdate()
151 {
152 // Nothing now
153 }
154
155
fpathIsEquivalentBlocking(PROPULSION_TYPE propulsion1,int player1,FPATH_MOVETYPE moveType1,PROPULSION_TYPE propulsion2,int player2,FPATH_MOVETYPE moveType2)156 bool fpathIsEquivalentBlocking(PROPULSION_TYPE propulsion1, int player1, FPATH_MOVETYPE moveType1,
157 PROPULSION_TYPE propulsion2, int player2, FPATH_MOVETYPE moveType2)
158 {
159 int domain1, domain2;
160 switch (propulsion1)
161 {
162 default: domain1 = 0; break; // Land
163 case PROPULSION_TYPE_LIFT: domain1 = 1; break; // Air
164 case PROPULSION_TYPE_PROPELLOR: domain1 = 2; break; // Water
165 case PROPULSION_TYPE_HOVER: domain1 = 3; break; // Land and water
166 }
167 switch (propulsion2)
168 {
169 default: domain2 = 0; break; // Land
170 case PROPULSION_TYPE_LIFT: domain2 = 1; break; // Air
171 case PROPULSION_TYPE_PROPELLOR: domain2 = 2; break; // Water
172 case PROPULSION_TYPE_HOVER: domain2 = 3; break; // Land and water
173 }
174
175 if (domain1 != domain2)
176 {
177 return false;
178 }
179
180 if (domain1 == 1)
181 {
182 return true; // Air units ignore move type and player.
183 }
184
185 if (moveType1 != moveType2 || player1 != player2)
186 {
187 return false;
188 }
189
190 return true;
191 }
192
prop2bits(PROPULSION_TYPE propulsion)193 static uint8_t prop2bits(PROPULSION_TYPE propulsion)
194 {
195 uint8_t bits;
196
197 switch (propulsion)
198 {
199 case PROPULSION_TYPE_LIFT:
200 bits = AIR_BLOCKED;
201 break;
202 case PROPULSION_TYPE_HOVER:
203 bits = FEATURE_BLOCKED;
204 break;
205 case PROPULSION_TYPE_PROPELLOR:
206 bits = FEATURE_BLOCKED | LAND_BLOCKED;
207 break;
208 default:
209 bits = FEATURE_BLOCKED | WATER_BLOCKED;
210 break;
211 }
212 return bits;
213 }
214
215 // Check if the map tile at a location blocks a droid
fpathBaseBlockingTile(SDWORD x,SDWORD y,PROPULSION_TYPE propulsion,int mapIndex,FPATH_MOVETYPE moveType)216 bool fpathBaseBlockingTile(SDWORD x, SDWORD y, PROPULSION_TYPE propulsion, int mapIndex, FPATH_MOVETYPE moveType)
217 {
218 /* All tiles outside of the map and on map border are blocking. */
219 if (x < 1 || y < 1 || x > mapWidth - 1 || y > mapHeight - 1)
220 {
221 return true;
222 }
223
224 /* Check scroll limits (used in campaign to partition the map. */
225 if (propulsion != PROPULSION_TYPE_LIFT && (x < scrollMinX + 1 || y < scrollMinY + 1 || x >= scrollMaxX - 1 || y >= scrollMaxY - 1))
226 {
227 // coords off map - auto blocking tile
228 return true;
229 }
230 unsigned aux = auxTile(x, y, mapIndex);
231
232 int auxMask = 0;
233 switch (moveType)
234 {
235 case FMT_MOVE: auxMask = AUXBITS_NONPASSABLE; break; // do not wish to shoot our way through enemy buildings, but want to go through friendly gates (without shooting them)
236 case FMT_ATTACK: auxMask = AUXBITS_OUR_BUILDING; break; // move blocked by friendly building, assuming we do not want to shoot it up en route
237 case FMT_BLOCK: auxMask = AUXBITS_BLOCKING; break; // Do not wish to tunnel through closed gates or buildings.
238 }
239
240 unsigned unitbits = prop2bits(propulsion); // TODO - cache prop2bits to psDroid, and pass in instead of propulsion type
241 if ((unitbits & FEATURE_BLOCKED) != 0 && (aux & auxMask) != 0)
242 {
243 return true; // move blocked by building, and we cannot or do not want to shoot our way through anything
244 }
245
246 // the MAX hack below is because blockTile() range does not include player-specific versions...
247 return (blockTile(x, y, MAX(0, mapIndex - MAX_PLAYERS)) & unitbits) != 0; // finally check if move is blocked by propulsion related factors
248 }
249
fpathDroidBlockingTile(DROID * psDroid,int x,int y,FPATH_MOVETYPE moveType)250 bool fpathDroidBlockingTile(DROID *psDroid, int x, int y, FPATH_MOVETYPE moveType)
251 {
252 return fpathBaseBlockingTile(x, y, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
253 }
254
255 // Check if the map tile at a location blocks a droid
fpathBlockingTile(SDWORD x,SDWORD y,PROPULSION_TYPE propulsion)256 bool fpathBlockingTile(SDWORD x, SDWORD y, PROPULSION_TYPE propulsion)
257 {
258 return fpathBaseBlockingTile(x, y, propulsion, 0, FMT_BLOCK); // with FMT_BLOCK, it is irrelevant which player is passed in
259 }
260
261
262 // Returns the closest non-blocking tile to pos, or returns pos if no non-blocking tiles are present within a 2 tile distance.
findNonblockingPosition(Position pos,PROPULSION_TYPE propulsion,int player=0,FPATH_MOVETYPE moveType=FMT_BLOCK)263 static Position findNonblockingPosition(Position pos, PROPULSION_TYPE propulsion, int player = 0, FPATH_MOVETYPE moveType = FMT_BLOCK)
264 {
265 Vector2i centreTile = map_coord(pos.xy());
266 if (!fpathBaseBlockingTile(centreTile.x, centreTile.y, propulsion, player, moveType))
267 {
268 return pos; // Fast case, pos is not on a blocking tile.
269 }
270
271 Vector2i bestTile = centreTile;
272 int bestDistSq = INT32_MAX;
273 for (int y = -2; y <= 2; ++y)
274 for (int x = -2; x <= 2; ++x)
275 {
276 Vector2i tile = centreTile + Vector2i(x, y);
277 Vector2i diff = world_coord(tile) + Vector2i(TILE_UNITS / 2, TILE_UNITS / 2) - pos.xy();
278 int distSq = dot(diff, diff);
279 if (distSq < bestDistSq && !fpathBaseBlockingTile(tile.x, tile.y, propulsion, player, moveType))
280 {
281 bestTile = tile;
282 bestDistSq = distSq;
283 }
284 }
285
286 // Return point on tile closest to the original pos.
287 Vector2i minCoord = world_coord(bestTile);
288 Vector2i maxCoord = minCoord + Vector2i(TILE_UNITS - 1, TILE_UNITS - 1);
289
290 return Position(std::min(std::max(pos.x, minCoord.x), maxCoord.x), std::min(std::max(pos.y, minCoord.y), maxCoord.y), pos.z);
291 }
292
293
294
fpathSetMove(MOVE_CONTROL * psMoveCntl,SDWORD targetX,SDWORD targetY)295 static void fpathSetMove(MOVE_CONTROL *psMoveCntl, SDWORD targetX, SDWORD targetY)
296 {
297 psMoveCntl->asPath.resize(1);
298 psMoveCntl->destination = Vector2i(targetX, targetY);
299 psMoveCntl->asPath[0] = Vector2i(targetX, targetY);
300 }
301
302
fpathSetDirectRoute(DROID * psDroid,SDWORD targetX,SDWORD targetY)303 void fpathSetDirectRoute(DROID *psDroid, SDWORD targetX, SDWORD targetY)
304 {
305 fpathSetMove(&psDroid->sMove, targetX, targetY);
306 }
307
308
fpathRemoveDroidData(int id)309 void fpathRemoveDroidData(int id)
310 {
311 pathResults.erase(id);
312 }
313
fpathRoute(MOVE_CONTROL * psMove,unsigned id,int startX,int startY,int tX,int tY,PROPULSION_TYPE propulsionType,DROID_TYPE droidType,FPATH_MOVETYPE moveType,int owner,bool acceptNearest,StructureBounds const & dstStructure)314 static FPATH_RETVAL fpathRoute(MOVE_CONTROL *psMove, unsigned id, int startX, int startY, int tX, int tY, PROPULSION_TYPE propulsionType,
315 DROID_TYPE droidType, FPATH_MOVETYPE moveType, int owner, bool acceptNearest, StructureBounds const &dstStructure)
316 {
317 objTrace(id, "called(*,id=%d,sx=%d,sy=%d,ex=%d,ey=%d,prop=%d,type=%d,move=%d,owner=%d)", id, startX, startY, tX, tY, (int)propulsionType, (int)droidType, (int)moveType, owner);
318
319 if (!worldOnMap(startX, startY) || !worldOnMap(tX, tY))
320 {
321 debug(LOG_ERROR, "Droid trying to find path to/from invalid location (%d %d) -> (%d %d).", startX, startY, tX, tY);
322 objTrace(id, "Invalid start/end.");
323 syncDebug("fpathRoute(..., %d, %d, %d, %d, %d, %d, %d, %d, %d) = FPR_FAILED", id, startX, startY, tX, tY, propulsionType, droidType, moveType, owner);
324 return FPR_FAILED;
325 }
326
327 // don't have to do anything if already there
328 if (startX == tX && startY == tY)
329 {
330 // return failed to stop them moving anywhere
331 objTrace(id, "Tried to move nowhere");
332 syncDebug("fpathRoute(..., %d, %d, %d, %d, %d, %d, %d, %d, %d) = FPR_FAILED", id, startX, startY, tX, tY, propulsionType, droidType, moveType, owner);
333 return FPR_FAILED;
334 }
335
336 // Check if waiting for a result
337 while (psMove->Status == MOVEWAITROUTE)
338 {
339 objTrace(id, "Checking if we have a path yet");
340
341 auto const &I = pathResults.find(id);
342 ASSERT(I != pathResults.end(), "Missing path result promise");
343 PATHRESULT result = I->second.get();
344 ASSERT(result.retval != FPR_OK || result.sMove.asPath.size() > 0, "Ok result but no path in list");
345
346 // Copy over select fields - preserve others
347 psMove->destination = result.sMove.destination;
348 bool correctDestination = tX == result.originalDest.x && tY == result.originalDest.y;
349 psMove->pathIndex = 0;
350 psMove->Status = MOVENAVIGATE;
351 psMove->asPath = result.sMove.asPath;
352 FPATH_RETVAL retval = result.retval;
353 ASSERT(retval != FPR_OK || psMove->asPath.size() > 0, "Ok result but no path after copy");
354
355 // Remove it from the result list
356 pathResults.erase(id);
357
358 objTrace(id, "Got a path to (%d, %d)! Length=%d Retval=%d", psMove->destination.x, psMove->destination.y, (int)psMove->asPath.size(), (int)retval);
359 syncDebug("fpathRoute(..., %d, %d, %d, %d, %d, %d, %d, %d, %d) = %d, path[%d] = %08X->(%d, %d)", id, startX, startY, tX, tY, propulsionType, droidType, moveType, owner, retval, (int)psMove->asPath.size(), ~crcSumVector2i(0, psMove->asPath.data(), psMove->asPath.size()), psMove->destination.x, psMove->destination.y);
360
361 if (!correctDestination)
362 {
363 goto queuePathfinding; // Seems we got the result of an old pathfinding job for this droid, so need to pathfind again.
364 }
365
366 return retval;
367 }
368 queuePathfinding:
369
370 // We were not waiting for a result, and found no trivial path, so create new job and start waiting
371 PATHJOB job;
372 job.origX = startX;
373 job.origY = startY;
374 job.droidID = id;
375 job.destX = tX;
376 job.destY = tY;
377 job.dstStructure = dstStructure;
378 job.droidType = droidType;
379 job.propulsion = propulsionType;
380 job.moveType = moveType;
381 job.owner = owner;
382 job.acceptNearest = acceptNearest;
383 job.deleted = false;
384 fpathSetBlockingMap(&job);
385
386 debug(LOG_NEVER, "starting new job for droid %d 0x%x", id, id);
387 // Clear any results or jobs waiting already. It is a vital assumption that there is only one
388 // job or result for each droid in the system at any time.
389 fpathRemoveDroidData(id);
390
391 packagedPathJob task([job]() { return fpathExecute(job); });
392 pathResults[id] = task.get_future();
393
394 // Add to end of list
395 wzMutexLock(fpathMutex);
396 bool isFirstJob = pathJobs.empty();
397 pathJobs.push_back(std::move(task));
398 wzMutexUnlock(fpathMutex);
399
400 if (isFirstJob)
401 {
402 wzSemaphorePost(fpathSemaphore); // Wake up processing thread.
403 }
404
405 objTrace(id, "Queued up a path-finding request to (%d, %d), at least %d items earlier in queue", tX, tY, isFirstJob);
406 syncDebug("fpathRoute(..., %d, %d, %d, %d, %d, %d, %d, %d, %d) = FPR_WAIT", id, startX, startY, tX, tY, propulsionType, droidType, moveType, owner);
407 return FPR_WAIT; // wait while polling result queue
408 }
409
410
411 // Find a route for an DROID to a location in world coordinates
fpathDroidRoute(DROID * psDroid,SDWORD tX,SDWORD tY,FPATH_MOVETYPE moveType)412 FPATH_RETVAL fpathDroidRoute(DROID *psDroid, SDWORD tX, SDWORD tY, FPATH_MOVETYPE moveType)
413 {
414 bool acceptNearest;
415 PROPULSION_STATS *psPropStats = getPropulsionStats(psDroid);
416
417 // override for AI to blast our way through stuff
418 if (!isHumanPlayer(psDroid->player) && moveType == FMT_MOVE)
419 {
420 moveType = (psDroid->asWeaps[0].nStat == 0) ? FMT_MOVE : FMT_ATTACK;
421 }
422
423 ASSERT_OR_RETURN(FPR_FAILED, psPropStats != nullptr, "invalid propulsion stats pointer");
424 ASSERT_OR_RETURN(FPR_FAILED, psDroid->type == OBJ_DROID, "We got passed an object that isn't a DROID!");
425
426 // Check whether the start and end points of the route are blocking tiles and find an alternative if they are.
427 Position startPos = psDroid->pos;
428 Position endPos = Position(tX, tY, 0);
429 StructureBounds dstStructure = getStructureBounds(worldTile(endPos.xy())->psObject);
430 startPos = findNonblockingPosition(startPos, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
431 if (!dstStructure.valid()) // If there's a structure over the destination, ignore it, otherwise pathfind from somewhere around the obstruction.
432 {
433 endPos = findNonblockingPosition(endPos, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
434 }
435 objTrace(psDroid->id, "Want to go to (%d, %d) -> (%d, %d), going (%d, %d) -> (%d, %d)", map_coord(psDroid->pos.x), map_coord(psDroid->pos.y), map_coord(tX), map_coord(tY), map_coord(startPos.x), map_coord(startPos.y), map_coord(endPos.x), map_coord(endPos.y));
436 switch (psDroid->order.type)
437 {
438 case DORDER_BUILD:
439 case DORDER_LINEBUILD: // build a number of structures in a row (walls + bridges)
440 dstStructure = getStructureBounds(psDroid->order.psStats, psDroid->order.pos, psDroid->order.direction); // Just need to get close enough to build (can be diagonally), do not need to reach the destination tile.
441 // fallthrough
442 case DORDER_HELPBUILD: // help to build a structure
443 case DORDER_DEMOLISH: // demolish a structure
444 case DORDER_REPAIR:
445 acceptNearest = false;
446 break;
447 default:
448 acceptNearest = true;
449 break;
450 }
451 return fpathRoute(&psDroid->sMove, psDroid->id, startPos.x, startPos.y, endPos.x, endPos.y, psPropStats->propulsionType,
452 psDroid->droidType, moveType, psDroid->player, acceptNearest, dstStructure);
453 }
454
455 // Run only from path thread
fpathExecute(PATHJOB job)456 PATHRESULT fpathExecute(PATHJOB job)
457 {
458 PATHRESULT result;
459 result.droidID = job.droidID;
460 result.retval = FPR_FAILED;
461 result.originalDest = Vector2i(job.destX, job.destY);
462
463 ASR_RETVAL retval = fpathAStarRoute(&result.sMove, &job);
464
465 ASSERT(retval != ASR_OK || result.sMove.asPath.size() > 0, "Ok result but no path in result");
466 switch (retval)
467 {
468 case ASR_NEAREST:
469 if (job.acceptNearest)
470 {
471 objTrace(job.droidID, "** Nearest route -- accepted **");
472 result.retval = FPR_OK;
473 }
474 else
475 {
476 objTrace(job.droidID, "** Nearest route -- rejected **");
477 result.retval = FPR_FAILED;
478 }
479 break;
480 case ASR_FAILED:
481 objTrace(job.droidID, "** Failed route **");
482 // Is this really a good idea? Was in original code.
483 if (job.propulsion == PROPULSION_TYPE_LIFT && (job.droidType != DROID_TRANSPORTER && job.droidType != DROID_SUPERTRANSPORTER))
484 {
485 objTrace(job.droidID, "Doing fallback for non-transport VTOL");
486 fpathSetMove(&result.sMove, job.destX, job.destY);
487 result.retval = FPR_OK;
488 }
489 else
490 {
491 result.retval = FPR_FAILED;
492 }
493 break;
494 case ASR_OK:
495 objTrace(job.droidID, "Got route of length %d", (int)result.sMove.asPath.size());
496 result.retval = FPR_OK;
497 break;
498 }
499 return result;
500 }
501
502 /** Find the length of the job queue. Function is thread-safe. */
fpathJobQueueLength()503 static size_t fpathJobQueueLength()
504 {
505 size_t count = 0;
506
507 wzMutexLock(fpathMutex);
508 count = pathJobs.size(); // O(N) function call for std::list. .empty() is faster, but this function isn't used except in tests.
509 wzMutexUnlock(fpathMutex);
510 return count;
511 }
512
513
514 /** Find the length of the result queue, excepting future results. Function is thread-safe. */
fpathResultQueueLength()515 static size_t fpathResultQueueLength()
516 {
517 size_t count = 0;
518
519 wzMutexLock(fpathMutex);
520 count = pathResults.size(); // O(N) function call for std::list. .empty() is faster, but this function isn't used except in tests.
521 wzMutexUnlock(fpathMutex);
522 return count;
523 }
524
525
526 // Only used by fpathTest.
fpathSimpleRoute(MOVE_CONTROL * psMove,int id,int startX,int startY,int tX,int tY)527 static FPATH_RETVAL fpathSimpleRoute(MOVE_CONTROL *psMove, int id, int startX, int startY, int tX, int tY)
528 {
529 return fpathRoute(psMove, id, startX, startY, tX, tY, PROPULSION_TYPE_WHEELED, DROID_WEAPON, FMT_BLOCK, 0, true, getStructureBounds((BASE_OBJECT *)nullptr));
530 }
531
fpathTest(int x,int y,int x2,int y2)532 void fpathTest(int x, int y, int x2, int y2)
533 {
534 MOVE_CONTROL sMove;
535 FPATH_RETVAL r;
536 int i;
537
538 // On non-debug builds prevent warnings about defining but not using fpathJobQueueLength
539 (void)fpathJobQueueLength();
540
541 /* Check initial state */
542 assert(fpathThread != nullptr);
543 assert(fpathMutex != nullptr);
544 assert(fpathSemaphore != nullptr);
545 assert(pathJobs.empty());
546 assert(pathResults.empty());
547 fpathRemoveDroidData(0); // should not crash
548
549 /* This should not leak memory */
550 sMove.asPath.clear();
551 for (i = 0; i < 100; i++)
552 {
553 fpathSetMove(&sMove, 1, 1);
554 }
555
556 /* Test one path */
557 sMove.Status = MOVEINACTIVE;
558 r = fpathSimpleRoute(&sMove, 1, x, y, x2, y2);
559 assert(r == FPR_WAIT);
560 sMove.Status = MOVEWAITROUTE;
561 assert(fpathJobQueueLength() == 1 || fpathResultQueueLength() == 1);
562 fpathRemoveDroidData(2); // should not crash, nor remove our path
563 assert(fpathJobQueueLength() == 1 || fpathResultQueueLength() == 1);
564 while (fpathResultQueueLength() == 0)
565 {
566 wzYieldCurrentThread();
567 }
568 assert(fpathJobQueueLength() == 0);
569 assert(fpathResultQueueLength() == 1);
570 r = fpathSimpleRoute(&sMove, 1, x, y, x2, y2);
571 assert(r == FPR_OK);
572 assert(sMove.asPath.size() > 0);
573 assert(sMove.asPath[sMove.asPath.size() - 1].x == x2);
574 assert(sMove.asPath[sMove.asPath.size() - 1].y == y2);
575 assert(fpathResultQueueLength() == 0);
576
577 /* Let one hundred paths flower! */
578 sMove.Status = MOVEINACTIVE;
579 for (i = 1; i <= 100; i++)
580 {
581 r = fpathSimpleRoute(&sMove, i, x, y, x2, y2);
582 assert(r == FPR_WAIT);
583 }
584 while (fpathResultQueueLength() != 100)
585 {
586 wzYieldCurrentThread();
587 }
588 assert(fpathJobQueueLength() == 0);
589 for (i = 1; i <= 100; i++)
590 {
591 sMove.Status = MOVEWAITROUTE;
592 r = fpathSimpleRoute(&sMove, i, x, y, x2, y2);
593 assert(r == FPR_OK);
594 assert(sMove.asPath.size() > 0 && sMove.asPath.size() > 0);
595 assert(sMove.asPath[sMove.asPath.size() - 1].x == x2);
596 assert(sMove.asPath[sMove.asPath.size() - 1].y == y2);
597 }
598 assert(fpathResultQueueLength() == 0);
599
600 /* Kill a hundred flowers */
601 sMove.Status = MOVEINACTIVE;
602 for (i = 1; i <= 100; i++)
603 {
604 r = fpathSimpleRoute(&sMove, i, x, y, x2, y2);
605 assert(r == FPR_WAIT);
606 }
607 for (i = 1; i <= 100; i++)
608 {
609 fpathRemoveDroidData(i);
610 }
611 //assert(pathJobs.empty()); // can now be marked .deleted as well
612 assert(pathResults.empty());
613 (void)r; // Squelch unused-but-set warning.
614 }
615
fpathCheck(Position orig,Position dest,PROPULSION_TYPE propulsion)616 bool fpathCheck(Position orig, Position dest, PROPULSION_TYPE propulsion)
617 {
618 // We have to be careful with this check because it is called on
619 // load when playing campaign on droids that are on the other
620 // map during missions, and those maps are usually larger.
621 if (!worldOnMap(orig.xy()) || !worldOnMap(dest.xy()))
622 {
623 return false;
624 }
625
626 MAPTILE *origTile = worldTile(findNonblockingPosition(orig, propulsion).xy());
627 MAPTILE *destTile = worldTile(findNonblockingPosition(dest, propulsion).xy());
628
629 ASSERT_OR_RETURN(false, propulsion != PROPULSION_TYPE_NUM, "Bad propulsion type");
630 ASSERT_OR_RETURN(false, origTile != nullptr && destTile != nullptr, "Bad tile parameter");
631
632 switch (propulsion)
633 {
634 case PROPULSION_TYPE_PROPELLOR:
635 case PROPULSION_TYPE_WHEELED:
636 case PROPULSION_TYPE_TRACKED:
637 case PROPULSION_TYPE_LEGGED:
638 case PROPULSION_TYPE_HALF_TRACKED:
639 return origTile->limitedContinent == destTile->limitedContinent;
640 case PROPULSION_TYPE_HOVER:
641 return origTile->hoverContinent == destTile->hoverContinent;
642 case PROPULSION_TYPE_LIFT:
643 return true; // assume no map uses skyscrapers to isolate areas
644 default:
645 break;
646 }
647
648 ASSERT(false, "Should never get here, unknown propulsion !");
649 return false; // should never get here
650 }
651