1 /* Copyright (C) 2018 Wildfire Games.
2 * This file is part of 0 A.D.
3 *
4 * 0 A.D. is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * 0 A.D. is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 /**
19 * @file
20 * Common code and setup code for CCmpPathfinder.
21 */
22
23 #include "precompiled.h"
24
25 #include "CCmpPathfinder_Common.h"
26
27 #include "ps/CLogger.h"
28 #include "ps/CStr.h"
29 #include "ps/Profile.h"
30 #include "ps/XML/Xeromyces.h"
31 #include "renderer/Scene.h"
32 #include "simulation2/MessageTypes.h"
33 #include "simulation2/components/ICmpObstruction.h"
34 #include "simulation2/components/ICmpObstructionManager.h"
35 #include "simulation2/components/ICmpTerrain.h"
36 #include "simulation2/components/ICmpWaterManager.h"
37 #include "simulation2/helpers/Rasterize.h"
38 #include "simulation2/serialization/SerializeTemplates.h"
39
REGISTER_COMPONENT_TYPE(Pathfinder)40 REGISTER_COMPONENT_TYPE(Pathfinder)
41
42 void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
43 {
44 m_MapSize = 0;
45 m_Grid = NULL;
46 m_TerrainOnlyGrid = NULL;
47
48 FlushAIPathfinderDirtinessInformation();
49
50 m_NextAsyncTicket = 1;
51
52 m_DebugOverlay = false;
53 m_AtlasOverlay = NULL;
54
55 m_SameTurnMovesCount = 0;
56
57 // Register Relax NG validator
58 CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
59
60 // Since this is used as a system component (not loaded from an entity template),
61 // we can't use the real paramNode (it won't get handled properly when deserializing),
62 // so load the data from a special XML file.
63 CParamNode externalParamNode;
64 CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
65
66 // Previously all move commands during a turn were
67 // queued up and processed asynchronously at the start
68 // of the next turn. Now we are processing queued up
69 // events several times duing the turn. This improves
70 // responsiveness and units move more smoothly especially.
71 // when in formation. There is still a call at the
72 // beginning of a turn to process all outstanding moves -
73 // this will handle any moves above the MaxSameTurnMoves
74 // threshold.
75 //
76 // TODO - The moves processed at the beginning of the
77 // turn do not count against the maximum moves per turn
78 // currently. The thinking is that this will eventually
79 // happen in another thread. Either way this probably
80 // will require some adjustment and rethinking.
81 const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
82 m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
83
84
85 const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
86 for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
87 {
88 std::string name = it->first;
89 ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);
90 pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());
91 m_PassClasses.push_back(PathfinderPassability(mask, it->second));
92 m_PassClassMasks[name] = mask;
93 }
94 }
95
Deinit()96 void CCmpPathfinder::Deinit()
97 {
98 SetDebugOverlay(false); // cleans up memory
99 SAFE_DELETE(m_AtlasOverlay);
100
101 SAFE_DELETE(m_Grid);
102 SAFE_DELETE(m_TerrainOnlyGrid);
103 }
104
105 struct SerializeLongRequest
106 {
107 template<typename S>
operator ()SerializeLongRequest108 void operator()(S& serialize, const char* UNUSED(name), AsyncLongPathRequest& value)
109 {
110 serialize.NumberU32_Unbounded("ticket", value.ticket);
111 serialize.NumberFixed_Unbounded("x0", value.x0);
112 serialize.NumberFixed_Unbounded("z0", value.z0);
113 SerializeGoal()(serialize, "goal", value.goal);
114 serialize.NumberU16_Unbounded("pass class", value.passClass);
115 serialize.NumberU32_Unbounded("notify", value.notify);
116 }
117 };
118
119 struct SerializeShortRequest
120 {
121 template<typename S>
operator ()SerializeShortRequest122 void operator()(S& serialize, const char* UNUSED(name), AsyncShortPathRequest& value)
123 {
124 serialize.NumberU32_Unbounded("ticket", value.ticket);
125 serialize.NumberFixed_Unbounded("x0", value.x0);
126 serialize.NumberFixed_Unbounded("z0", value.z0);
127 serialize.NumberFixed_Unbounded("clearance", value.clearance);
128 serialize.NumberFixed_Unbounded("range", value.range);
129 SerializeGoal()(serialize, "goal", value.goal);
130 serialize.NumberU16_Unbounded("pass class", value.passClass);
131 serialize.Bool("avoid moving units", value.avoidMovingUnits);
132 serialize.NumberU32_Unbounded("group", value.group);
133 serialize.NumberU32_Unbounded("notify", value.notify);
134 }
135 };
136
137 template<typename S>
SerializeCommon(S & serialize)138 void CCmpPathfinder::SerializeCommon(S& serialize)
139 {
140 SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_AsyncLongPathRequests);
141 SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_AsyncShortPathRequests);
142 serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
143 serialize.NumberU16_Unbounded("same turn moves count", m_SameTurnMovesCount);
144 serialize.NumberU16_Unbounded("map size", m_MapSize);
145 }
146
Serialize(ISerializer & serialize)147 void CCmpPathfinder::Serialize(ISerializer& serialize)
148 {
149 SerializeCommon(serialize);
150 }
151
Deserialize(const CParamNode & paramNode,IDeserializer & deserialize)152 void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
153 {
154 Init(paramNode);
155
156 SerializeCommon(deserialize);
157 }
158
HandleMessage(const CMessage & msg,bool UNUSED (global))159 void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
160 {
161 switch (msg.GetType())
162 {
163 case MT_RenderSubmit:
164 {
165 const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
166 RenderSubmit(msgData.collector);
167 break;
168 }
169 case MT_TerrainChanged:
170 m_TerrainDirty = true;
171 MinimalTerrainUpdate();
172 break;
173 case MT_WaterChanged:
174 case MT_ObstructionMapShapeChanged:
175 m_TerrainDirty = true;
176 UpdateGrid();
177 break;
178 case MT_TurnStart:
179 m_SameTurnMovesCount = 0;
180 break;
181 }
182 }
183
RenderSubmit(SceneCollector & collector)184 void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
185 {
186 for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)
187 collector.Submit(&m_DebugOverlayShortPathLines[i]);
188
189 m_LongPathfinder.HierarchicalRenderSubmit(collector);
190 }
191
SetAtlasOverlay(bool enable,pass_class_t passClass)192 void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
193 {
194 if (enable)
195 {
196 if (!m_AtlasOverlay)
197 m_AtlasOverlay = new AtlasOverlay(this, passClass);
198 m_AtlasOverlay->m_PassClass = passClass;
199 }
200 else
201 SAFE_DELETE(m_AtlasOverlay);
202 }
203
GetPassabilityClass(const std::string & name) const204 pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
205 {
206 std::map<std::string, pass_class_t>::const_iterator it = m_PassClassMasks.find(name);
207 if (it == m_PassClassMasks.end())
208 {
209 LOGERROR("Invalid passability class name '%s'", name.c_str());
210 return 0;
211 }
212
213 return it->second;
214 }
215
GetPassabilityClasses(std::map<std::string,pass_class_t> & passClasses) const216 void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const
217 {
218 passClasses = m_PassClassMasks;
219 }
220
GetPassabilityClasses(std::map<std::string,pass_class_t> & nonPathfindingPassClasses,std::map<std::string,pass_class_t> & pathfindingPassClasses) const221 void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& nonPathfindingPassClasses, std::map<std::string, pass_class_t>& pathfindingPassClasses) const
222 {
223 for (const std::pair<std::string, pass_class_t>& pair : m_PassClassMasks)
224 {
225 if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
226 pathfindingPassClasses[pair.first] = pair.second;
227 else
228 nonPathfindingPassClasses[pair.first] = pair.second;
229 }
230 }
231
GetPassabilityFromMask(pass_class_t passClass) const232 const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
233 {
234 for (const PathfinderPassability& passability : m_PassClasses)
235 {
236 if (passability.m_Mask == passClass)
237 return &passability;
238 }
239
240 return NULL;
241 }
242
GetPassabilityGrid()243 const Grid<NavcellData>& CCmpPathfinder::GetPassabilityGrid()
244 {
245 if (!m_Grid)
246 UpdateGrid();
247
248 return *m_Grid;
249 }
250
251 /**
252 * Given a grid of passable/impassable navcells (based on some passability mask),
253 * computes a new grid where a navcell is impassable (per that mask) if
254 * it is <=clearance navcells away from an impassable navcell in the original grid.
255 * The results are ORed onto the original grid.
256 *
257 * This is used for adding clearance onto terrain-based navcell passability.
258 *
259 * TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
260 * Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
261 * This would only really be a problem for big clearances.
262 */
ExpandImpassableCells(Grid<NavcellData> & grid,u16 clearance,pass_class_t mask)263 static void ExpandImpassableCells(Grid<NavcellData>& grid, u16 clearance, pass_class_t mask)
264 {
265 PROFILE3("ExpandImpassableCells");
266
267 u16 w = grid.m_W;
268 u16 h = grid.m_H;
269
270 // First expand impassable cells horizontally into a temporary 1-bit grid
271 Grid<u8> tempGrid(w, h);
272 for (u16 j = 0; j < h; ++j)
273 {
274 // New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance
275
276 // Count the number of blocked cells around i=0
277 u16 numBlocked = 0;
278 for (u16 i = 0; i <= clearance && i < w; ++i)
279 if (!IS_PASSABLE(grid.get(i, j), mask))
280 ++numBlocked;
281
282 for (u16 i = 0; i < w; ++i)
283 {
284 // Store a flag if blocked by at least one nearby cell
285 if (numBlocked)
286 tempGrid.set(i, j, 1);
287
288 // Slide the numBlocked window along:
289 // remove the old i-clearance value, add the new (i+1)+clearance
290 // (avoiding overflowing the grid)
291 if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))
292 --numBlocked;
293 if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))
294 ++numBlocked;
295 }
296 }
297
298 for (u16 i = 0; i < w; ++i)
299 {
300 // New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance
301 // Count the number of blocked cells around j=0
302 u16 numBlocked = 0;
303 for (u16 j = 0; j <= clearance && j < h; ++j)
304 if (tempGrid.get(i, j))
305 ++numBlocked;
306
307 for (u16 j = 0; j < h; ++j)
308 {
309 // Add the mask if blocked by at least one nearby cell
310 if (numBlocked)
311 grid.set(i, j, grid.get(i, j) | mask);
312
313 // Slide the numBlocked window along:
314 // remove the old j-clearance value, add the new (j+1)+clearance
315 // (avoiding overflowing the grid)
316 if (j >= clearance && tempGrid.get(i, j-clearance))
317 --numBlocked;
318 if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))
319 ++numBlocked;
320 }
321 }
322 }
323
ComputeShoreGrid(bool expandOnWater)324 Grid<u16> CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
325 {
326 PROFILE3("ComputeShoreGrid");
327
328 CmpPtr<ICmpWaterManager> cmpWaterManager(GetSystemEntity());
329
330 // TODO: these bits should come from ICmpTerrain
331 CTerrain& terrain = GetSimContext().GetTerrain();
332
333 // avoid integer overflow in intermediate calculation
334 const u16 shoreMax = 32767;
335
336 // First pass - find underwater tiles
337 Grid<u8> waterGrid(m_MapSize, m_MapSize);
338 for (u16 j = 0; j < m_MapSize; ++j)
339 {
340 for (u16 i = 0; i < m_MapSize; ++i)
341 {
342 fixed x, z;
343 Pathfinding::TileCenter(i, j, x, z);
344
345 bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
346 waterGrid.set(i, j, underWater ? 1 : 0);
347 }
348 }
349
350 // Second pass - find shore tiles
351 Grid<u16> shoreGrid(m_MapSize, m_MapSize);
352 for (u16 j = 0; j < m_MapSize; ++j)
353 {
354 for (u16 i = 0; i < m_MapSize; ++i)
355 {
356 // Find a land tile
357 if (!waterGrid.get(i, j))
358 {
359 // If it's bordered by water, it's a shore tile
360 if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < m_MapSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1))
361 || (i < m_MapSize-1 && waterGrid.get(i+1, j)) || (i < m_MapSize-1 && j < m_MapSize-1 && waterGrid.get(i+1, j+1)) || (i < m_MapSize-1 && j > 0 && waterGrid.get(i+1, j-1))
362 || (j > 0 && waterGrid.get(i, j-1)) || (j < m_MapSize-1 && waterGrid.get(i, j+1))
363 )
364 shoreGrid.set(i, j, 0);
365 else
366 shoreGrid.set(i, j, shoreMax);
367 }
368 // If we want to expand on water, we want water tiles not to be shore tiles
369 else if (expandOnWater)
370 shoreGrid.set(i, j, shoreMax);
371 }
372 }
373
374 // Expand influences on land to find shore distance
375 for (u16 y = 0; y < m_MapSize; ++y)
376 {
377 u16 min = shoreMax;
378 for (u16 x = 0; x < m_MapSize; ++x)
379 {
380 if (!waterGrid.get(x, y) || expandOnWater)
381 {
382 u16 g = shoreGrid.get(x, y);
383 if (g > min)
384 shoreGrid.set(x, y, min);
385 else if (g < min)
386 min = g;
387
388 ++min;
389 }
390 }
391 for (u16 x = m_MapSize; x > 0; --x)
392 {
393 if (!waterGrid.get(x-1, y) || expandOnWater)
394 {
395 u16 g = shoreGrid.get(x-1, y);
396 if (g > min)
397 shoreGrid.set(x-1, y, min);
398 else if (g < min)
399 min = g;
400
401 ++min;
402 }
403 }
404 }
405 for (u16 x = 0; x < m_MapSize; ++x)
406 {
407 u16 min = shoreMax;
408 for (u16 y = 0; y < m_MapSize; ++y)
409 {
410 if (!waterGrid.get(x, y) || expandOnWater)
411 {
412 u16 g = shoreGrid.get(x, y);
413 if (g > min)
414 shoreGrid.set(x, y, min);
415 else if (g < min)
416 min = g;
417
418 ++min;
419 }
420 }
421 for (u16 y = m_MapSize; y > 0; --y)
422 {
423 if (!waterGrid.get(x, y-1) || expandOnWater)
424 {
425 u16 g = shoreGrid.get(x, y-1);
426 if (g > min)
427 shoreGrid.set(x, y-1, min);
428 else if (g < min)
429 min = g;
430
431 ++min;
432 }
433 }
434 }
435
436 return shoreGrid;
437 }
438
UpdateGrid()439 void CCmpPathfinder::UpdateGrid()
440 {
441 PROFILE3("UpdateGrid");
442
443 CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
444 if (!cmpTerrain)
445 return; // error
446
447 u16 terrainSize = cmpTerrain->GetTilesPerSide();
448 if (terrainSize == 0)
449 return;
450
451 // If the terrain was resized then delete the old grid data
452 if (m_Grid && m_MapSize != terrainSize)
453 {
454 SAFE_DELETE(m_Grid);
455 SAFE_DELETE(m_TerrainOnlyGrid);
456 }
457
458 // Initialise the terrain data when first needed
459 if (!m_Grid)
460 {
461 m_MapSize = terrainSize;
462 m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
463 SAFE_DELETE(m_TerrainOnlyGrid);
464 m_TerrainOnlyGrid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
465
466 m_DirtinessInformation = { true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
467 m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
468
469 m_TerrainDirty = true;
470 }
471
472 // The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
473 #ifdef NDEBUG
474 ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
475 #else
476 ENSURE(m_DirtinessInformation.dirtinessGrid == Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));
477 #endif
478
479 CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
480 cmpObstructionManager->UpdateInformations(m_DirtinessInformation);
481
482 if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
483 return;
484
485 // If the terrain has changed, recompute m_Grid
486 // Else, use data from m_TerrainOnlyGrid and add obstructions
487 if (m_TerrainDirty)
488 {
489 TerrainUpdateHelper();
490
491 *m_Grid = *m_TerrainOnlyGrid;
492
493 m_TerrainDirty = false;
494 m_DirtinessInformation.globallyDirty = true;
495 }
496 else if (m_DirtinessInformation.globallyDirty)
497 {
498 ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
499 memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)*(m_Grid->m_H)*sizeof(NavcellData));
500 }
501 else
502 {
503 ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
504
505 for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
506 for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
507 if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
508 m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
509 }
510
511 // Add obstructions onto the grid
512 cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);
513
514 // Update the long-range pathfinder
515 if (m_DirtinessInformation.globallyDirty)
516 {
517 std::map<std::string, pass_class_t> nonPathfindingPassClasses, pathfindingPassClasses;
518 GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
519 m_LongPathfinder.Reload(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
520 }
521 else
522 m_LongPathfinder.Update(m_Grid, m_DirtinessInformation.dirtinessGrid);
523
524 // Remember the necessary updates that the AI pathfinder will have to perform as well
525 m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);
526 }
527
MinimalTerrainUpdate()528 void CCmpPathfinder::MinimalTerrainUpdate()
529 {
530 TerrainUpdateHelper(false);
531 }
532
TerrainUpdateHelper(bool expandPassability)533 void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability/* = true */)
534 {
535 PROFILE3("TerrainUpdateHelper");
536
537 CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
538 CmpPtr<ICmpWaterManager> cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
539 CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
540 CTerrain& terrain = GetSimContext().GetTerrain();
541
542 if (!cmpTerrain || !cmpObstructionManager)
543 return;
544
545 u16 terrainSize = cmpTerrain->GetTilesPerSide();
546 if (terrainSize == 0)
547 return;
548
549 if (!m_TerrainOnlyGrid || m_MapSize != terrainSize)
550 {
551 m_MapSize = terrainSize;
552
553 SAFE_DELETE(m_TerrainOnlyGrid);
554 m_TerrainOnlyGrid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
555
556 // If this update comes from a map resizing, we must reinitialize the other grids as well
557 if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
558 {
559 SAFE_DELETE(m_Grid);
560 m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
561
562 m_DirtinessInformation = { true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
563 m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
564 }
565 }
566
567 Grid<u16> shoreGrid = ComputeShoreGrid();
568
569 // Compute initial terrain-dependent passability
570 for (int j = 0; j < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++j)
571 {
572 for (int i = 0; i < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++i)
573 {
574 // World-space coordinates for this navcell
575 fixed x, z;
576 Pathfinding::NavcellCenter(i, j, x, z);
577
578 // Terrain-tile coordinates for this navcell
579 int itile = i / Pathfinding::NAVCELLS_PER_TILE;
580 int jtile = j / Pathfinding::NAVCELLS_PER_TILE;
581
582 // Gather all the data potentially needed to determine passability:
583
584 fixed height = terrain.GetExactGroundLevelFixed(x, z);
585
586 fixed water;
587 if (cmpWaterManager)
588 water = cmpWaterManager->GetWaterLevel(x, z);
589
590 fixed depth = water - height;
591
592 // Exact slopes give kind of weird output, so just use rough tile-based slopes
593 fixed slope = terrain.GetSlopeFixed(itile, jtile);
594
595 // Get world-space coordinates from shoreGrid (which uses terrain tiles)
596 fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);
597
598 // Compute the passability for every class for this cell
599 NavcellData t = 0;
600 for (PathfinderPassability& passability : m_PassClasses)
601 if (!passability.IsPassable(depth, slope, shoredist))
602 t |= passability.m_Mask;
603
604 m_TerrainOnlyGrid->set(i, j, t);
605 }
606 }
607
608 // Compute off-world passability
609 // WARNING: CCmpRangeManager::LosIsOffWorld needs to be kept in sync with this
610 const int edgeSize = 3 * Pathfinding::NAVCELLS_PER_TILE; // number of tiles around the edge that will be off-world
611
612 NavcellData edgeMask = 0;
613 for (PathfinderPassability& passability : m_PassClasses)
614 edgeMask |= passability.m_Mask;
615
616 int w = m_TerrainOnlyGrid->m_W;
617 int h = m_TerrainOnlyGrid->m_H;
618
619 if (cmpObstructionManager->GetPassabilityCircular())
620 {
621 for (int j = 0; j < h; ++j)
622 {
623 for (int i = 0; i < w; ++i)
624 {
625 // Based on CCmpRangeManager::LosIsOffWorld
626 // but tweaked since it's tile-based instead.
627 // (We double all the values so we can handle half-tile coordinates.)
628 // This needs to be slightly tighter than the LOS circle,
629 // else units might get themselves lost in the SoD around the edge.
630
631 int dist2 = (i*2 + 1 - w)*(i*2 + 1 - w)
632 + (j*2 + 1 - h)*(j*2 + 1 - h);
633
634 if (dist2 >= (w - 2*edgeSize) * (h - 2*edgeSize))
635 m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
636 }
637 }
638 }
639 else
640 {
641 for (u16 j = 0; j < h; ++j)
642 for (u16 i = 0; i < edgeSize; ++i)
643 m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
644 for (u16 j = 0; j < h; ++j)
645 for (u16 i = w-edgeSize+1; i < w; ++i)
646 m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
647 for (u16 j = 0; j < edgeSize; ++j)
648 for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
649 m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
650 for (u16 j = h-edgeSize+1; j < h; ++j)
651 for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
652 m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
653 }
654
655 if (!expandPassability)
656 return;
657
658 // Expand the impassability grid, for any class with non-zero clearance,
659 // so that we can stop units getting too close to impassable navcells.
660 // Note: It's not possible to perform this expansion once for all passabilities
661 // with the same clearance, because the impassable cells are not necessarily the
662 // same for all these passabilities.
663 for (PathfinderPassability& passability : m_PassClasses)
664 {
665 if (passability.m_Clearance == fixed::Zero())
666 continue;
667
668 int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();
669 ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);
670 }
671 }
672
673 //////////////////////////////////////////////////////////
674
675 // Async path requests:
676
ComputePathAsync(entity_pos_t x0,entity_pos_t z0,const PathGoal & goal,pass_class_t passClass,entity_id_t notify)677 u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
678 {
679 AsyncLongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
680 m_AsyncLongPathRequests.push_back(req);
681 return req.ticket;
682 }
683
ComputeShortPathAsync(entity_pos_t x0,entity_pos_t z0,entity_pos_t clearance,entity_pos_t range,const PathGoal & goal,pass_class_t passClass,bool avoidMovingUnits,entity_id_t group,entity_id_t notify)684 u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify)
685 {
686 AsyncShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
687 m_AsyncShortPathRequests.push_back(req);
688 return req.ticket;
689 }
690
FinishAsyncRequests()691 void CCmpPathfinder::FinishAsyncRequests()
692 {
693 PROFILE2("Finish Async Requests");
694 // Save the request queue in case it gets modified while iterating
695 std::vector<AsyncLongPathRequest> longRequests;
696 m_AsyncLongPathRequests.swap(longRequests);
697
698 std::vector<AsyncShortPathRequest> shortRequests;
699 m_AsyncShortPathRequests.swap(shortRequests);
700
701 // TODO: we should only compute one path per entity per turn
702
703 // TODO: this computation should be done incrementally, spread
704 // across multiple frames (or even multiple turns)
705
706 ProcessLongRequests(longRequests);
707 ProcessShortRequests(shortRequests);
708 }
709
ProcessLongRequests(const std::vector<AsyncLongPathRequest> & longRequests)710 void CCmpPathfinder::ProcessLongRequests(const std::vector<AsyncLongPathRequest>& longRequests)
711 {
712 PROFILE2("Process Long Requests");
713 for (size_t i = 0; i < longRequests.size(); ++i)
714 {
715 const AsyncLongPathRequest& req = longRequests[i];
716 WaypointPath path;
717 ComputePath(req.x0, req.z0, req.goal, req.passClass, path);
718 CMessagePathResult msg(req.ticket, path);
719 GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
720 }
721 }
722
ProcessShortRequests(const std::vector<AsyncShortPathRequest> & shortRequests)723 void CCmpPathfinder::ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests)
724 {
725 PROFILE2("Process Short Requests");
726 for (size_t i = 0; i < shortRequests.size(); ++i)
727 {
728 const AsyncShortPathRequest& req = shortRequests[i];
729 WaypointPath path;
730 ControlGroupMovementObstructionFilter filter(req.avoidMovingUnits, req.group);
731 ComputeShortPath(filter, req.x0, req.z0, req.clearance, req.range, req.goal, req.passClass, path);
732 CMessagePathResult msg(req.ticket, path);
733 GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
734 }
735 }
736
ProcessSameTurnMoves()737 void CCmpPathfinder::ProcessSameTurnMoves()
738 {
739 if (!m_AsyncLongPathRequests.empty())
740 {
741 // Figure out how many moves we can do this time
742 i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
743
744 if (moveCount <= 0)
745 return;
746
747 // Copy the long request elements we are going to process into a new array
748 std::vector<AsyncLongPathRequest> longRequests;
749 if ((i32)m_AsyncLongPathRequests.size() <= moveCount)
750 {
751 m_AsyncLongPathRequests.swap(longRequests);
752 moveCount = (i32)longRequests.size();
753 }
754 else
755 {
756 longRequests.resize(moveCount);
757 copy(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount, longRequests.begin());
758 m_AsyncLongPathRequests.erase(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount);
759 }
760
761 ProcessLongRequests(longRequests);
762
763 m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
764 }
765
766 if (!m_AsyncShortPathRequests.empty())
767 {
768 // Figure out how many moves we can do now
769 i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
770
771 if (moveCount <= 0)
772 return;
773
774 // Copy the short request elements we are going to process into a new array
775 std::vector<AsyncShortPathRequest> shortRequests;
776 if ((i32)m_AsyncShortPathRequests.size() <= moveCount)
777 {
778 m_AsyncShortPathRequests.swap(shortRequests);
779 moveCount = (i32)shortRequests.size();
780 }
781 else
782 {
783 shortRequests.resize(moveCount);
784 copy(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount, shortRequests.begin());
785 m_AsyncShortPathRequests.erase(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount);
786 }
787
788 ProcessShortRequests(shortRequests);
789
790 m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
791 }
792 }
793
794 //////////////////////////////////////////////////////////
795
CheckMovement(const IObstructionTestFilter & filter,entity_pos_t x0,entity_pos_t z0,entity_pos_t x1,entity_pos_t z1,entity_pos_t r,pass_class_t passClass) const796 bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,
797 entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r,
798 pass_class_t passClass) const
799 {
800 PROFILE2_IFSPIKE("Check Movement", 0.001);
801
802 // Test against obstructions first. filter may discard pathfinding-blocking obstructions.
803 // Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
804 // This makes movement smoother and more natural for units, overall.
805 CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
806 if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
807 return false;
808
809 // Then test against the terrain grid. This should not be necessary
810 // But in case we allow terrain to change it will become so.
811 return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
812 }
813
CheckUnitPlacement(const IObstructionTestFilter & filter,entity_pos_t x,entity_pos_t z,entity_pos_t r,pass_class_t passClass,bool UNUSED (onlyCenterPoint)) const814 ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,
815 entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
816 {
817 // Check unit obstruction
818 CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
819 if (!cmpObstructionManager)
820 return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
821
822 if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
823 return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
824
825 // Test against terrain and static obstructions:
826
827 u16 i, j;
828 Pathfinding::NearestNavcell(x, z, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
829 if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
830 return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
831
832 // (Static obstructions will be redundantly tested against in both the
833 // obstruction-shape test and navcell-passability test, which is slightly
834 // inefficient but shouldn't affect behaviour)
835
836 return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
837 }
838
CheckBuildingPlacement(const IObstructionTestFilter & filter,entity_pos_t x,entity_pos_t z,entity_pos_t a,entity_pos_t w,entity_pos_t h,entity_id_t id,pass_class_t passClass) const839 ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
840 entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
841 entity_pos_t h, entity_id_t id, pass_class_t passClass) const
842 {
843 return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
844 }
845
846
CheckBuildingPlacement(const IObstructionTestFilter & filter,entity_pos_t x,entity_pos_t z,entity_pos_t a,entity_pos_t w,entity_pos_t h,entity_id_t id,pass_class_t passClass,bool UNUSED (onlyCenterPoint)) const847 ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
848 entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
849 entity_pos_t h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
850 {
851 // Check unit obstruction
852 CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
853 if (!cmpObstructionManager)
854 return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
855
856 if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
857 return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
858
859 // Test against terrain:
860
861 ICmpObstructionManager::ObstructionSquare square;
862 CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), id);
863 if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square))
864 return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;
865
866 entity_pos_t expand;
867 const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
868 if (passability)
869 expand = passability->m_Clearance;
870
871 SimRasterize::Spans spans;
872 SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
873 for (const SimRasterize::Span& span : spans)
874 {
875 i16 i0 = span.i0;
876 i16 i1 = span.i1;
877 i16 j = span.j;
878
879 // Fail if any span extends outside the grid
880 if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H)
881 return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
882
883 // Fail if any span includes an impassable tile
884 for (i16 i = i0; i < i1; ++i)
885 if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
886 return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
887 }
888
889 return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
890 }
891