Line data Source code
1 : /* Copyright (C) 2022 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 "simulation2/MessageTypes.h"
28 : #include "simulation2/components/ICmpObstruction.h"
29 : #include "simulation2/components/ICmpObstructionManager.h"
30 : #include "simulation2/components/ICmpTerrain.h"
31 : #include "simulation2/components/ICmpWaterManager.h"
32 : #include "simulation2/helpers/HierarchicalPathfinder.h"
33 : #include "simulation2/helpers/LongPathfinder.h"
34 : #include "simulation2/helpers/MapEdgeTiles.h"
35 : #include "simulation2/helpers/Rasterize.h"
36 : #include "simulation2/helpers/VertexPathfinder.h"
37 : #include "simulation2/serialization/SerializedPathfinder.h"
38 : #include "simulation2/serialization/SerializedTypes.h"
39 :
40 : #include "ps/CLogger.h"
41 : #include "ps/CStr.h"
42 : #include "ps/Profile.h"
43 : #include "ps/XML/Xeromyces.h"
44 : #include "renderer/Scene.h"
45 :
46 : #include <type_traits>
47 :
48 116 : REGISTER_COMPONENT_TYPE(Pathfinder)
49 :
50 3 : void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
51 : {
52 3 : m_GridSize = 0;
53 3 : m_Grid = NULL;
54 3 : m_TerrainOnlyGrid = NULL;
55 :
56 3 : FlushAIPathfinderDirtinessInformation();
57 :
58 3 : m_NextAsyncTicket = 1;
59 :
60 3 : m_AtlasOverlay = NULL;
61 :
62 3 : size_t workerThreads = Threading::TaskManager::Instance().GetNumberOfWorkers();
63 : // Store one vertex pathfinder for each thread (including the main thread).
64 27 : while (m_VertexPathfinders.size() < workerThreads + 1)
65 12 : m_VertexPathfinders.emplace_back(m_GridSize, m_TerrainOnlyGrid);
66 3 : m_LongPathfinder = std::make_unique<LongPathfinder>();
67 3 : m_PathfinderHier = std::make_unique<HierarchicalPathfinder>();
68 :
69 : // Set up one future for each worker thread.
70 3 : m_Futures.resize(workerThreads);
71 :
72 : // Register Relax NG validator
73 3 : CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
74 :
75 : // Since this is used as a system component (not loaded from an entity template),
76 : // we can't use the real paramNode (it won't get handled properly when deserializing),
77 : // so load the data from a special XML file.
78 6 : CParamNode externalParamNode;
79 3 : CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
80 :
81 : // Paths are computed:
82 : // - Before MT_Update
83 : // - Before MT_MotionUnitFormation
84 : // - asynchronously between turn end and turn start.
85 : // The latter of these must compute all outstanding requests, but the former two are capped
86 : // to avoid spending too much time there (since the latter are threaded and thus much 'cheaper').
87 : // This loads that maximum number (note that it's per computation call, not per turn for now).
88 6 : const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
89 3 : m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
90 :
91 3 : const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
92 18 : for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
93 : {
94 30 : std::string name = it->first;
95 15 : ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);
96 15 : pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());
97 15 : m_PassClasses.push_back(PathfinderPassability(mask, it->second));
98 15 : m_PassClassMasks[name] = mask;
99 : }
100 3 : }
101 :
102 6 : CCmpPathfinder::~CCmpPathfinder() {};
103 :
104 3 : void CCmpPathfinder::Deinit()
105 : {
106 3 : SetDebugOverlay(false); // cleans up memory
107 :
108 : // Wait on all pathfinding tasks.
109 12 : for (Future<void>& future : m_Futures)
110 9 : future.CancelOrWait();
111 3 : m_Futures.clear();
112 :
113 3 : SAFE_DELETE(m_AtlasOverlay);
114 :
115 3 : SAFE_DELETE(m_Grid);
116 3 : SAFE_DELETE(m_TerrainOnlyGrid);
117 3 : }
118 :
119 : template<>
120 : struct SerializeHelper<LongPathRequest>
121 : {
122 : template<typename S>
123 0 : void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify<S, LongPathRequest> value)
124 : {
125 0 : serialize.NumberU32_Unbounded("ticket", value.ticket);
126 0 : serialize.NumberFixed_Unbounded("x0", value.x0);
127 0 : serialize.NumberFixed_Unbounded("z0", value.z0);
128 0 : Serializer(serialize, "goal", value.goal);
129 0 : serialize.NumberU16_Unbounded("pass class", value.passClass);
130 0 : serialize.NumberU32_Unbounded("notify", value.notify);
131 0 : }
132 : };
133 :
134 : template<>
135 : struct SerializeHelper<ShortPathRequest>
136 : {
137 : template<typename S>
138 0 : void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify<S, ShortPathRequest> value)
139 : {
140 0 : serialize.NumberU32_Unbounded("ticket", value.ticket);
141 0 : serialize.NumberFixed_Unbounded("x0", value.x0);
142 0 : serialize.NumberFixed_Unbounded("z0", value.z0);
143 0 : serialize.NumberFixed_Unbounded("clearance", value.clearance);
144 0 : serialize.NumberFixed_Unbounded("range", value.range);
145 0 : Serializer(serialize, "goal", value.goal);
146 0 : serialize.NumberU16_Unbounded("pass class", value.passClass);
147 0 : serialize.Bool("avoid moving units", value.avoidMovingUnits);
148 0 : serialize.NumberU32_Unbounded("group", value.group);
149 0 : serialize.NumberU32_Unbounded("notify", value.notify);
150 0 : }
151 : };
152 :
153 : template<typename S>
154 0 : void CCmpPathfinder::SerializeCommon(S& serialize)
155 : {
156 0 : Serializer(serialize, "long requests", m_LongPathRequests.m_Requests);
157 0 : Serializer(serialize, "short requests", m_ShortPathRequests.m_Requests);
158 0 : serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
159 0 : serialize.NumberU16_Unbounded("grid size", m_GridSize);
160 0 : }
161 :
162 0 : void CCmpPathfinder::Serialize(ISerializer& serialize)
163 : {
164 0 : SerializeCommon(serialize);
165 0 : }
166 :
167 0 : void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
168 : {
169 0 : Init(paramNode);
170 :
171 0 : SerializeCommon(deserialize);
172 0 : }
173 :
174 0 : void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
175 : {
176 0 : switch (msg.GetType())
177 : {
178 0 : case MT_RenderSubmit:
179 : {
180 0 : const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
181 0 : RenderSubmit(msgData.collector);
182 0 : break;
183 : }
184 0 : case MT_TerrainChanged:
185 : {
186 0 : const CMessageTerrainChanged& msgData = static_cast<const CMessageTerrainChanged&>(msg);
187 0 : m_TerrainDirty = true;
188 0 : MinimalTerrainUpdate(msgData.i0, msgData.j0, msgData.i1, msgData.j1);
189 0 : break;
190 : }
191 0 : case MT_WaterChanged:
192 : case MT_ObstructionMapShapeChanged:
193 0 : m_TerrainDirty = true;
194 0 : UpdateGrid();
195 0 : break;
196 0 : case MT_Deserialized:
197 0 : UpdateGrid();
198 : // In case we were serialised with requests pending, we need to process them.
199 0 : if (!m_ShortPathRequests.m_Requests.empty() || !m_LongPathRequests.m_Requests.empty())
200 : {
201 0 : ENSURE(CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
202 0 : StartProcessingMoves(false);
203 : }
204 0 : break;
205 : }
206 0 : }
207 :
208 0 : void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
209 : {
210 0 : g_VertexPathfinderDebugOverlay.RenderSubmit(collector);
211 0 : m_PathfinderHier->RenderSubmit(collector);
212 0 : }
213 :
214 0 : void CCmpPathfinder::SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
215 : {
216 0 : m_LongPathfinder->SetDebugPath(*m_PathfinderHier, x0, z0, goal, passClass);
217 0 : }
218 :
219 3 : void CCmpPathfinder::SetDebugOverlay(bool enabled)
220 : {
221 3 : g_VertexPathfinderDebugOverlay.SetDebugOverlay(enabled);
222 3 : m_LongPathfinder->SetDebugOverlay(enabled);
223 3 : }
224 :
225 0 : void CCmpPathfinder::SetHierDebugOverlay(bool enabled)
226 : {
227 0 : m_PathfinderHier->SetDebugOverlay(enabled, &GetSimContext());
228 0 : }
229 :
230 0 : void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid<u8>& grid) const
231 : {
232 0 : m_LongPathfinder->GetDebugData(steps, time, grid);
233 0 : }
234 :
235 0 : void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
236 : {
237 0 : if (enable)
238 : {
239 0 : if (!m_AtlasOverlay)
240 0 : m_AtlasOverlay = new AtlasOverlay(this, passClass);
241 0 : m_AtlasOverlay->m_PassClass = passClass;
242 : }
243 : else
244 0 : SAFE_DELETE(m_AtlasOverlay);
245 0 : }
246 :
247 0 : pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
248 : {
249 0 : std::map<std::string, pass_class_t>::const_iterator it = m_PassClassMasks.find(name);
250 0 : if (it == m_PassClassMasks.end())
251 : {
252 0 : LOGERROR("Invalid passability class name '%s'", name.c_str());
253 0 : return 0;
254 : }
255 :
256 0 : return it->second;
257 : }
258 :
259 0 : void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const
260 : {
261 0 : passClasses = m_PassClassMasks;
262 0 : }
263 :
264 0 : void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& nonPathfindingPassClasses, std::map<std::string, pass_class_t>& pathfindingPassClasses) const
265 : {
266 0 : for (const std::pair<const std::string, pass_class_t>& pair : m_PassClassMasks)
267 : {
268 0 : if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
269 0 : pathfindingPassClasses[pair.first] = pair.second;
270 : else
271 0 : nonPathfindingPassClasses[pair.first] = pair.second;
272 : }
273 0 : }
274 :
275 0 : const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
276 : {
277 0 : for (const PathfinderPassability& passability : m_PassClasses)
278 : {
279 0 : if (passability.m_Mask == passClass)
280 0 : return &passability;
281 : }
282 :
283 0 : return NULL;
284 : }
285 :
286 0 : const Grid<NavcellData>& CCmpPathfinder::GetPassabilityGrid()
287 : {
288 0 : if (!m_Grid)
289 0 : UpdateGrid();
290 :
291 0 : return *m_Grid;
292 : }
293 :
294 : /**
295 : * Given a grid of passable/impassable navcells (based on some passability mask),
296 : * computes a new grid where a navcell is impassable (per that mask) if
297 : * it is <=clearance navcells away from an impassable navcell in the original grid.
298 : * The results are ORed onto the original grid.
299 : *
300 : * This is used for adding clearance onto terrain-based navcell passability.
301 : *
302 : * TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
303 : * Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
304 : * This would only really be a problem for big clearances.
305 : */
306 0 : static void ExpandImpassableCells(Grid<NavcellData>& grid, u16 clearance, pass_class_t mask)
307 : {
308 0 : PROFILE3("ExpandImpassableCells");
309 :
310 0 : u16 w = grid.m_W;
311 0 : u16 h = grid.m_H;
312 :
313 : // First expand impassable cells horizontally into a temporary 1-bit grid
314 0 : Grid<u8> tempGrid(w, h);
315 0 : for (u16 j = 0; j < h; ++j)
316 : {
317 : // New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance
318 :
319 : // Count the number of blocked cells around i=0
320 0 : u16 numBlocked = 0;
321 0 : for (u16 i = 0; i <= clearance && i < w; ++i)
322 0 : if (!IS_PASSABLE(grid.get(i, j), mask))
323 0 : ++numBlocked;
324 :
325 0 : for (u16 i = 0; i < w; ++i)
326 : {
327 : // Store a flag if blocked by at least one nearby cell
328 0 : if (numBlocked)
329 0 : tempGrid.set(i, j, 1);
330 :
331 : // Slide the numBlocked window along:
332 : // remove the old i-clearance value, add the new (i+1)+clearance
333 : // (avoiding overflowing the grid)
334 0 : if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))
335 0 : --numBlocked;
336 0 : if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))
337 0 : ++numBlocked;
338 : }
339 : }
340 :
341 0 : for (u16 i = 0; i < w; ++i)
342 : {
343 : // New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance
344 : // Count the number of blocked cells around j=0
345 0 : u16 numBlocked = 0;
346 0 : for (u16 j = 0; j <= clearance && j < h; ++j)
347 0 : if (tempGrid.get(i, j))
348 0 : ++numBlocked;
349 :
350 0 : for (u16 j = 0; j < h; ++j)
351 : {
352 : // Add the mask if blocked by at least one nearby cell
353 0 : if (numBlocked)
354 0 : grid.set(i, j, grid.get(i, j) | mask);
355 :
356 : // Slide the numBlocked window along:
357 : // remove the old j-clearance value, add the new (j+1)+clearance
358 : // (avoiding overflowing the grid)
359 0 : if (j >= clearance && tempGrid.get(i, j-clearance))
360 0 : --numBlocked;
361 0 : if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))
362 0 : ++numBlocked;
363 : }
364 : }
365 0 : }
366 :
367 0 : Grid<u16> CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
368 : {
369 0 : PROFILE3("ComputeShoreGrid");
370 :
371 0 : CmpPtr<ICmpWaterManager> cmpWaterManager(GetSystemEntity());
372 :
373 : // TODO: these bits should come from ICmpTerrain
374 0 : CTerrain& terrain = GetSimContext().GetTerrain();
375 :
376 : // avoid integer overflow in intermediate calculation
377 0 : const u16 shoreMax = 32767;
378 :
379 0 : u16 shoreGridSize = terrain.GetTilesPerSide();
380 :
381 : // First pass - find underwater tiles
382 0 : Grid<u8> waterGrid(shoreGridSize, shoreGridSize);
383 0 : for (u16 j = 0; j < shoreGridSize; ++j)
384 : {
385 0 : for (u16 i = 0; i < shoreGridSize; ++i)
386 : {
387 0 : fixed x, z;
388 0 : Pathfinding::TerrainTileCenter(i, j, x, z);
389 :
390 0 : bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
391 0 : waterGrid.set(i, j, underWater ? 1 : 0);
392 : }
393 : }
394 :
395 : // Second pass - find shore tiles
396 0 : Grid<u16> shoreGrid(shoreGridSize, shoreGridSize);
397 0 : for (u16 j = 0; j < shoreGridSize; ++j)
398 : {
399 0 : for (u16 i = 0; i < shoreGridSize; ++i)
400 : {
401 : // Find a land tile
402 0 : if (!waterGrid.get(i, j))
403 : {
404 : // If it's bordered by water, it's a shore tile
405 0 : if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < shoreGridSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1))
406 0 : || (i < shoreGridSize-1 && waterGrid.get(i+1, j)) || (i < shoreGridSize-1 && j < shoreGridSize-1 && waterGrid.get(i+1, j+1)) || (i < shoreGridSize-1 && j > 0 && waterGrid.get(i+1, j-1))
407 0 : || (j > 0 && waterGrid.get(i, j-1)) || (j < shoreGridSize-1 && waterGrid.get(i, j+1))
408 : )
409 0 : shoreGrid.set(i, j, 0);
410 : else
411 0 : shoreGrid.set(i, j, shoreMax);
412 : }
413 : // If we want to expand on water, we want water tiles not to be shore tiles
414 0 : else if (expandOnWater)
415 0 : shoreGrid.set(i, j, shoreMax);
416 : }
417 : }
418 :
419 : // Expand influences on land to find shore distance
420 0 : for (u16 y = 0; y < shoreGridSize; ++y)
421 : {
422 0 : u16 min = shoreMax;
423 0 : for (u16 x = 0; x < shoreGridSize; ++x)
424 : {
425 0 : if (!waterGrid.get(x, y) || expandOnWater)
426 : {
427 0 : u16 g = shoreGrid.get(x, y);
428 0 : if (g > min)
429 0 : shoreGrid.set(x, y, min);
430 0 : else if (g < min)
431 0 : min = g;
432 :
433 0 : ++min;
434 : }
435 : }
436 0 : for (u16 x = shoreGridSize; x > 0; --x)
437 : {
438 0 : if (!waterGrid.get(x-1, y) || expandOnWater)
439 : {
440 0 : u16 g = shoreGrid.get(x-1, y);
441 0 : if (g > min)
442 0 : shoreGrid.set(x-1, y, min);
443 0 : else if (g < min)
444 0 : min = g;
445 :
446 0 : ++min;
447 : }
448 : }
449 : }
450 0 : for (u16 x = 0; x < shoreGridSize; ++x)
451 : {
452 0 : u16 min = shoreMax;
453 0 : for (u16 y = 0; y < shoreGridSize; ++y)
454 : {
455 0 : if (!waterGrid.get(x, y) || expandOnWater)
456 : {
457 0 : u16 g = shoreGrid.get(x, y);
458 0 : if (g > min)
459 0 : shoreGrid.set(x, y, min);
460 0 : else if (g < min)
461 0 : min = g;
462 :
463 0 : ++min;
464 : }
465 : }
466 0 : for (u16 y = shoreGridSize; y > 0; --y)
467 : {
468 0 : if (!waterGrid.get(x, y-1) || expandOnWater)
469 : {
470 0 : u16 g = shoreGrid.get(x, y-1);
471 0 : if (g > min)
472 0 : shoreGrid.set(x, y-1, min);
473 0 : else if (g < min)
474 0 : min = g;
475 :
476 0 : ++min;
477 : }
478 : }
479 : }
480 :
481 0 : return shoreGrid;
482 : }
483 :
484 0 : void CCmpPathfinder::UpdateGrid()
485 : {
486 0 : PROFILE3("UpdateGrid");
487 :
488 0 : CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
489 0 : if (!cmpTerrain)
490 0 : return; // error
491 :
492 0 : u16 gridSize = cmpTerrain->GetMapSize() / Pathfinding::NAVCELL_SIZE_INT;
493 0 : if (gridSize == 0)
494 0 : return;
495 :
496 : // If the terrain was resized then delete the old grid data
497 0 : if (m_Grid && m_GridSize != gridSize)
498 : {
499 0 : SAFE_DELETE(m_Grid);
500 0 : SAFE_DELETE(m_TerrainOnlyGrid);
501 : }
502 :
503 : // Initialise the terrain data when first needed
504 0 : if (!m_Grid)
505 : {
506 0 : m_GridSize = gridSize;
507 0 : m_Grid = new Grid<NavcellData>(m_GridSize, m_GridSize);
508 0 : SAFE_DELETE(m_TerrainOnlyGrid);
509 0 : m_TerrainOnlyGrid = new Grid<NavcellData>(m_GridSize, m_GridSize);
510 :
511 0 : m_DirtinessInformation = { true, true, Grid<u8>(m_GridSize, m_GridSize) };
512 0 : m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
513 :
514 0 : m_TerrainDirty = true;
515 : }
516 :
517 : // The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
518 : #ifdef NDEBUG
519 : ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
520 : #else
521 0 : ENSURE(m_DirtinessInformation.dirtinessGrid == Grid<u8>(m_GridSize, m_GridSize));
522 : #endif
523 :
524 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
525 0 : cmpObstructionManager->UpdateInformations(m_DirtinessInformation);
526 :
527 0 : if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
528 0 : return;
529 :
530 : // If the terrain has changed, recompute m_Grid
531 : // Else, use data from m_TerrainOnlyGrid and add obstructions
532 0 : if (m_TerrainDirty)
533 : {
534 0 : TerrainUpdateHelper();
535 :
536 0 : *m_Grid = *m_TerrainOnlyGrid;
537 :
538 0 : m_TerrainDirty = false;
539 0 : m_DirtinessInformation.globallyDirty = true;
540 : }
541 0 : else if (m_DirtinessInformation.globallyDirty)
542 : {
543 0 : ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
544 0 : memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)*(m_Grid->m_H)*sizeof(NavcellData));
545 : }
546 : else
547 : {
548 0 : ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
549 :
550 0 : for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
551 0 : for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
552 0 : if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
553 0 : m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
554 : }
555 :
556 : // Add obstructions onto the grid
557 0 : cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);
558 :
559 : // Update the long-range and hierarchical pathfinders.
560 0 : if (m_DirtinessInformation.globallyDirty)
561 : {
562 0 : std::map<std::string, pass_class_t> nonPathfindingPassClasses, pathfindingPassClasses;
563 0 : GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
564 0 : m_LongPathfinder->Reload(m_Grid);
565 0 : m_PathfinderHier->Recompute(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
566 : }
567 : else
568 : {
569 0 : m_LongPathfinder->Update(m_Grid);
570 0 : m_PathfinderHier->Update(m_Grid, m_DirtinessInformation.dirtinessGrid);
571 : }
572 :
573 : // Remember the necessary updates that the AI pathfinder will have to perform as well
574 0 : m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);
575 : }
576 :
577 0 : void CCmpPathfinder::MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1)
578 : {
579 0 : TerrainUpdateHelper(false, itile0, jtile0, itile1, jtile1);
580 0 : }
581 :
582 0 : void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability, int itile0, int jtile0, int itile1, int jtile1)
583 : {
584 0 : PROFILE3("TerrainUpdateHelper");
585 :
586 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
587 0 : CmpPtr<ICmpWaterManager> cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
588 0 : CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
589 0 : CTerrain& terrain = GetSimContext().GetTerrain();
590 :
591 0 : if (!cmpTerrain || !cmpObstructionManager)
592 0 : return;
593 :
594 0 : u16 gridSize = cmpTerrain->GetMapSize() / Pathfinding::NAVCELL_SIZE_INT;
595 0 : if (gridSize == 0)
596 0 : return;
597 :
598 0 : const bool needsNewTerrainGrid = !m_TerrainOnlyGrid || m_GridSize != gridSize;
599 0 : if (needsNewTerrainGrid)
600 : {
601 0 : m_GridSize = gridSize;
602 :
603 0 : SAFE_DELETE(m_TerrainOnlyGrid);
604 0 : m_TerrainOnlyGrid = new Grid<NavcellData>(m_GridSize, m_GridSize);
605 :
606 : // If this update comes from a map resizing, we must reinitialize the other grids as well
607 0 : if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
608 : {
609 0 : SAFE_DELETE(m_Grid);
610 0 : m_Grid = new Grid<NavcellData>(m_GridSize, m_GridSize);
611 :
612 0 : m_DirtinessInformation = { true, true, Grid<u8>(m_GridSize, m_GridSize) };
613 0 : m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
614 : }
615 : }
616 :
617 0 : Grid<u16> shoreGrid = ComputeShoreGrid();
618 :
619 0 : const bool partialTerrainGridUpdate =
620 0 : !expandPassability && !needsNewTerrainGrid &&
621 0 : itile0 != -1 && jtile0 != -1 && itile1 != -1 && jtile1 != -1;
622 0 : int istart = 0, iend = m_GridSize;
623 0 : int jstart = 0, jend = m_GridSize;
624 0 : if (partialTerrainGridUpdate)
625 : {
626 : // We need to extend the boundaries by 1 tile, because slope and ground
627 : // level are calculated by multiple neighboring tiles.
628 : // TODO: add CTerrain constant instead of 1.
629 0 : istart = Clamp<int>((itile0 - 1) * Pathfinding::NAVCELLS_PER_TERRAIN_TILE, 0, m_GridSize);
630 0 : iend = Clamp<int>((itile1 + 1) * Pathfinding::NAVCELLS_PER_TERRAIN_TILE, 0, m_GridSize);
631 0 : jstart = Clamp<int>((jtile0 - 1) * Pathfinding::NAVCELLS_PER_TERRAIN_TILE, 0, m_GridSize);
632 0 : jend = Clamp<int>((jtile1 + 1) * Pathfinding::NAVCELLS_PER_TERRAIN_TILE, 0, m_GridSize);
633 : }
634 :
635 : // Compute initial terrain-dependent passability
636 0 : for (int j = jstart; j < jend; ++j)
637 : {
638 0 : for (int i = istart; i < iend; ++i)
639 : {
640 : // World-space coordinates for this navcell
641 0 : fixed x, z;
642 0 : Pathfinding::NavcellCenter(i, j, x, z);
643 :
644 : // Terrain-tile coordinates for this navcell
645 0 : int itile = i / Pathfinding::NAVCELLS_PER_TERRAIN_TILE;
646 0 : int jtile = j / Pathfinding::NAVCELLS_PER_TERRAIN_TILE;
647 :
648 : // Gather all the data potentially needed to determine passability:
649 :
650 0 : fixed height = terrain.GetExactGroundLevelFixed(x, z);
651 :
652 0 : fixed water;
653 0 : if (cmpWaterManager)
654 0 : water = cmpWaterManager->GetWaterLevel(x, z);
655 :
656 0 : fixed depth = water - height;
657 :
658 : // Exact slopes give kind of weird output, so just use rough tile-based slopes
659 0 : fixed slope = terrain.GetSlopeFixed(itile, jtile);
660 :
661 : // Get world-space coordinates from shoreGrid (which uses terrain tiles)
662 0 : fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);
663 :
664 : // Compute the passability for every class for this cell
665 0 : NavcellData t = 0;
666 0 : for (const PathfinderPassability& passability : m_PassClasses)
667 0 : if (!passability.IsPassable(depth, slope, shoredist))
668 0 : t |= passability.m_Mask;
669 :
670 0 : m_TerrainOnlyGrid->set(i, j, t);
671 : }
672 : }
673 :
674 : // Compute off-world passability
675 0 : const int edgeSize = MAP_EDGE_TILES * Pathfinding::NAVCELLS_PER_TERRAIN_TILE;
676 :
677 0 : NavcellData edgeMask = 0;
678 0 : for (const PathfinderPassability& passability : m_PassClasses)
679 0 : edgeMask |= passability.m_Mask;
680 :
681 0 : int w = m_TerrainOnlyGrid->m_W;
682 0 : int h = m_TerrainOnlyGrid->m_H;
683 :
684 0 : if (cmpObstructionManager->GetPassabilityCircular())
685 : {
686 0 : for (int j = jstart; j < jend; ++j)
687 : {
688 0 : for (int i = istart; i < iend; ++i)
689 : {
690 : // Based on CCmpRangeManager::LosIsOffWorld
691 : // but tweaked since it's tile-based instead.
692 : // (We double all the values so we can handle half-tile coordinates.)
693 : // This needs to be slightly tighter than the LOS circle,
694 : // else units might get themselves lost in the SoD around the edge.
695 :
696 0 : int dist2 = (i*2 + 1 - w)*(i*2 + 1 - w)
697 0 : + (j*2 + 1 - h)*(j*2 + 1 - h);
698 :
699 0 : if (dist2 >= (w - 2*edgeSize) * (h - 2*edgeSize))
700 0 : m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
701 : }
702 : }
703 : }
704 : else
705 : {
706 0 : for (u16 j = 0; j < h; ++j)
707 0 : for (u16 i = 0; i < edgeSize; ++i)
708 0 : m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
709 0 : for (u16 j = 0; j < h; ++j)
710 0 : for (u16 i = w-edgeSize+1; i < w; ++i)
711 0 : m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
712 0 : for (u16 j = 0; j < edgeSize; ++j)
713 0 : for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
714 0 : m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
715 0 : for (u16 j = h-edgeSize+1; j < h; ++j)
716 0 : for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
717 0 : m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
718 : }
719 :
720 0 : if (!expandPassability)
721 0 : return;
722 :
723 : // Expand the impassability grid, for any class with non-zero clearance,
724 : // so that we can stop units getting too close to impassable navcells.
725 : // Note: It's not possible to perform this expansion once for all passabilities
726 : // with the same clearance, because the impassable cells are not necessarily the
727 : // same for all these passabilities.
728 0 : for (PathfinderPassability& passability : m_PassClasses)
729 : {
730 0 : if (passability.m_Clearance == fixed::Zero())
731 0 : continue;
732 :
733 0 : int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();
734 0 : ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);
735 : }
736 : }
737 :
738 : //////////////////////////////////////////////////////////
739 :
740 0 : u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
741 : {
742 0 : LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
743 0 : m_LongPathRequests.m_Requests.push_back(req);
744 0 : return req.ticket;
745 : }
746 :
747 0 : u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range,
748 : const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits,
749 : entity_id_t group, entity_id_t notify)
750 : {
751 0 : ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
752 0 : m_ShortPathRequests.m_Requests.push_back(req);
753 0 : return req.ticket;
754 : }
755 :
756 0 : void CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const
757 : {
758 0 : m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret);
759 0 : }
760 :
761 0 : WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const
762 : {
763 0 : return m_VertexPathfinders.front().ComputeShortPath(request, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
764 : }
765 :
766 : template<typename T>
767 : template<typename U>
768 0 : void CCmpPathfinder::PathRequests<T>::Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder)
769 : {
770 : static_assert((std::is_same_v<T, LongPathRequest> && std::is_same_v<U, LongPathfinder>) ||
771 : (std::is_same_v<T, ShortPathRequest> && std::is_same_v<U, VertexPathfinder>));
772 0 : size_t maxN = m_Results.size();
773 0 : size_t startIndex = m_Requests.size() - m_Results.size();
774 : do
775 : {
776 0 : size_t workIndex = m_NextPathToCompute++;
777 0 : if (workIndex >= maxN)
778 0 : break;
779 0 : const T& req = m_Requests[startIndex + workIndex];
780 0 : PathResult& result = m_Results[workIndex];
781 0 : result.ticket = req.ticket;
782 0 : result.notify = req.notify;
783 : if constexpr (std::is_same_v<T, LongPathRequest>)
784 0 : pathfinder.ComputePath(*cmpPathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, result.path);
785 : else
786 0 : result.path = pathfinder.ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(cmpPathfinder.GetSystemEntity()));
787 0 : if (workIndex == maxN - 1)
788 0 : m_ComputeDone = true;
789 : }
790 : while (true);
791 0 : }
792 :
793 0 : void CCmpPathfinder::SendRequestedPaths()
794 : {
795 0 : PROFILE2("SendRequestedPaths");
796 :
797 0 : if (!m_LongPathRequests.m_ComputeDone || !m_ShortPathRequests.m_ComputeDone)
798 : {
799 : // Also start computing on the main thread to finish faster.
800 0 : m_ShortPathRequests.Compute(*this, m_VertexPathfinders.front());
801 0 : m_LongPathRequests.Compute(*this, *m_LongPathfinder);
802 : }
803 : // We're done, clear futures.
804 : // Use CancelOrWait instead of just Cancel to ensure determinism.
805 0 : for (Future<void>& future : m_Futures)
806 0 : future.CancelOrWait();
807 :
808 : {
809 0 : PROFILE2("PostMessages");
810 0 : for (PathResult& path : m_ShortPathRequests.m_Results)
811 : {
812 0 : CMessagePathResult msg(path.ticket, path.path);
813 0 : GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
814 : }
815 :
816 0 : for (PathResult& path : m_LongPathRequests.m_Results)
817 : {
818 0 : CMessagePathResult msg(path.ticket, path.path);
819 0 : GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
820 : }
821 : }
822 0 : m_ShortPathRequests.ClearComputed();
823 0 : m_LongPathRequests.ClearComputed();
824 0 : }
825 :
826 0 : void CCmpPathfinder::StartProcessingMoves(bool useMax)
827 : {
828 0 : m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
829 0 : m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
830 :
831 0 : Threading::TaskManager& taskManager = Threading::TaskManager::Instance();
832 0 : for (size_t i = 0; i < m_Futures.size(); ++i)
833 : {
834 0 : ENSURE(!m_Futures[i].Valid());
835 : // Pass the i+1th vertex pathfinder to keep the first for the main thread,
836 : // each thread get its own instance to avoid conflicts in cached data.
837 0 : m_Futures[i] = taskManager.PushTask([&pathfinder=*this, &vertexPfr=m_VertexPathfinders[i + 1]]() {
838 0 : PROFILE2("Async pathfinding");
839 0 : pathfinder.m_ShortPathRequests.Compute(pathfinder, vertexPfr);
840 0 : pathfinder.m_LongPathRequests.Compute(pathfinder, *pathfinder.m_LongPathfinder);
841 0 : });
842 : }
843 0 : }
844 :
845 :
846 : //////////////////////////////////////////////////////////
847 :
848 0 : bool CCmpPathfinder::IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
849 : {
850 0 : PROFILE2("IsGoalReachable");
851 :
852 : u16 i, j;
853 0 : Pathfinding::NearestNavcell(x0, z0, i, j, m_GridSize, m_GridSize);
854 0 : if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
855 0 : m_PathfinderHier->FindNearestPassableNavcell(i, j, passClass);
856 :
857 0 : return m_PathfinderHier->IsGoalReachable(i, j, goal, passClass);
858 : }
859 :
860 0 : bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,
861 : entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r,
862 : pass_class_t passClass) const
863 : {
864 0 : PROFILE2_IFSPIKE("Check Movement", 0.001);
865 :
866 : // Test against obstructions first. filter may discard pathfinding-blocking obstructions.
867 : // Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
868 : // This makes movement smoother and more natural for units, overall.
869 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
870 0 : if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
871 0 : return false;
872 :
873 : // Then test against the terrain grid. This should not be necessary
874 : // But in case we allow terrain to change it will become so.
875 0 : return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
876 : }
877 :
878 0 : ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,
879 : entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
880 : {
881 : // Check unit obstruction
882 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
883 0 : if (!cmpObstructionManager)
884 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
885 :
886 0 : if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
887 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
888 :
889 : // Test against terrain and static obstructions:
890 :
891 : u16 i, j;
892 0 : Pathfinding::NearestNavcell(x, z, i, j, m_GridSize, m_GridSize);
893 0 : if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
894 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
895 :
896 : // (Static obstructions will be redundantly tested against in both the
897 : // obstruction-shape test and navcell-passability test, which is slightly
898 : // inefficient but shouldn't affect behaviour)
899 :
900 0 : return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
901 : }
902 :
903 0 : ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
904 : entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
905 : entity_pos_t h, entity_id_t id, pass_class_t passClass) const
906 : {
907 0 : return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
908 : }
909 :
910 :
911 0 : ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
912 : entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
913 : entity_pos_t h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
914 : {
915 : // Check unit obstruction
916 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
917 0 : if (!cmpObstructionManager)
918 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
919 :
920 0 : if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
921 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
922 :
923 : // Test against terrain:
924 :
925 0 : ICmpObstructionManager::ObstructionSquare square;
926 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), id);
927 0 : if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square))
928 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;
929 :
930 0 : entity_pos_t expand;
931 0 : const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
932 0 : if (passability)
933 0 : expand = passability->m_Clearance;
934 :
935 0 : SimRasterize::Spans spans;
936 0 : SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
937 0 : for (const SimRasterize::Span& span : spans)
938 : {
939 0 : i16 i0 = span.i0;
940 0 : i16 i1 = span.i1;
941 0 : i16 j = span.j;
942 :
943 : // Fail if any span extends outside the grid
944 0 : if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H)
945 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
946 :
947 : // Fail if any span includes an impassable tile
948 0 : for (i16 i = i0; i < i1; ++i)
949 0 : if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
950 0 : return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
951 : }
952 :
953 0 : return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
954 3 : }
|
