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 : #ifndef INCLUDED_CCMPPATHFINDER_COMMON
19 : #define INCLUDED_CCMPPATHFINDER_COMMON
20 :
21 : /**
22 : * @file
23 : * Declares CCmpPathfinder. Its implementation is mainly done in CCmpPathfinder.cpp,
24 : * but the short-range (vertex) pathfinding is done in CCmpPathfinder_Vertex.cpp.
25 : * This file provides common code needed for both files.
26 : *
27 : * The long-range pathfinding is done by a LongPathfinder object.
28 : */
29 :
30 : #include "simulation2/system/Component.h"
31 :
32 : #include "ICmpPathfinder.h"
33 :
34 : #include "graphics/Overlay.h"
35 : #include "graphics/Terrain.h"
36 : #include "maths/MathUtil.h"
37 : #include "ps/CLogger.h"
38 : #include "ps/TaskManager.h"
39 : #include "renderer/TerrainOverlay.h"
40 : #include "simulation2/components/ICmpObstructionManager.h"
41 : #include "simulation2/helpers/Grid.h"
42 :
43 : #include <vector>
44 :
45 : class HierarchicalPathfinder;
46 : class LongPathfinder;
47 : class VertexPathfinder;
48 :
49 : class SceneCollector;
50 : class AtlasOverlay;
51 :
52 : #ifdef NDEBUG
53 : #define PATHFIND_DEBUG 0
54 : #else
55 : #define PATHFIND_DEBUG 1
56 : #endif
57 :
58 : /**
59 : * Implementation of ICmpPathfinder
60 : */
61 3 : class CCmpPathfinder final : public ICmpPathfinder
62 : {
63 : public:
64 116 : static void ClassInit(CComponentManager& componentManager)
65 : {
66 116 : componentManager.SubscribeToMessageType(MT_Deserialized);
67 116 : componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
68 116 : componentManager.SubscribeToMessageType(MT_TerrainChanged);
69 116 : componentManager.SubscribeToMessageType(MT_WaterChanged);
70 116 : componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);
71 116 : }
72 :
73 : ~CCmpPathfinder();
74 :
75 6 : DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)
76 :
77 : // Template state:
78 :
79 : std::map<std::string, pass_class_t> m_PassClassMasks;
80 : std::vector<PathfinderPassability> m_PassClasses;
81 : u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves.
82 :
83 : // Dynamic state:
84 :
85 : // Lazily-constructed dynamic state (not serialized):
86 :
87 : u16 m_GridSize; // Navcells per side of the map.
88 : Grid<NavcellData>* m_Grid; // terrain/passability information
89 : Grid<NavcellData>* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations
90 :
91 : // Keep clever updates in memory to avoid memory fragmentation from the grid.
92 : // This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else.
93 : GridUpdateInformation m_DirtinessInformation;
94 : // The data from clever updates is stored for the AI manager
95 : GridUpdateInformation m_AIPathfinderDirtinessInformation;
96 : bool m_TerrainDirty;
97 :
98 : std::vector<VertexPathfinder> m_VertexPathfinders;
99 : std::unique_ptr<HierarchicalPathfinder> m_PathfinderHier;
100 : std::unique_ptr<LongPathfinder> m_LongPathfinder;
101 :
102 : // One per live asynchronous path computing task.
103 : std::vector<Future<void>> m_Futures;
104 :
105 : template<typename T>
106 12 : class PathRequests {
107 : public:
108 : std::vector<T> m_Requests;
109 : std::vector<PathResult> m_Results;
110 : // This is the array index of the next path to compute.
111 : std::atomic<size_t> m_NextPathToCompute = 0;
112 : // This is false until all scheduled paths have been computed.
113 : std::atomic<bool> m_ComputeDone = true;
114 :
115 0 : void ClearComputed()
116 : {
117 0 : if (m_Results.size() == m_Requests.size())
118 0 : m_Requests.clear();
119 : else
120 0 : m_Requests.erase(m_Requests.end() - m_Results.size(), m_Requests.end());
121 0 : m_Results.clear();
122 0 : }
123 :
124 : /**
125 : * @param max - if non-zero, how many paths to process.
126 : */
127 0 : void PrepareForComputation(u16 max)
128 : {
129 0 : size_t n = m_Requests.size();
130 0 : if (max && n > max)
131 0 : n = max;
132 0 : m_NextPathToCompute = 0;
133 0 : m_Results.resize(n);
134 0 : m_ComputeDone = n == 0;
135 0 : }
136 :
137 : template<typename U>
138 : void Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder);
139 : };
140 : PathRequests<LongPathRequest> m_LongPathRequests;
141 : PathRequests<ShortPathRequest> m_ShortPathRequests;
142 :
143 : u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests.
144 :
145 : AtlasOverlay* m_AtlasOverlay;
146 :
147 116 : static std::string GetSchema()
148 : {
149 116 : return "<a:component type='system'/><empty/>";
150 : }
151 :
152 : void Init(const CParamNode& paramNode) override;
153 :
154 : void Deinit() override;
155 :
156 : template<typename S>
157 : void SerializeCommon(S& serialize);
158 :
159 : void Serialize(ISerializer& serialize) override;
160 :
161 : void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) override;
162 :
163 : void HandleMessage(const CMessage& msg, bool global) override;
164 :
165 : pass_class_t GetPassabilityClass(const std::string& name) const override;
166 :
167 : void GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const override;
168 : void GetPassabilityClasses(
169 : std::map<std::string, pass_class_t>& nonPathfindingPassClasses,
170 : std::map<std::string, pass_class_t>& pathfindingPassClasses) const override;
171 :
172 : const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const;
173 :
174 0 : entity_pos_t GetClearance(pass_class_t passClass) const override
175 : {
176 0 : const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
177 0 : if (!passability)
178 0 : return fixed::Zero();
179 :
180 0 : return passability->m_Clearance;
181 : }
182 :
183 0 : entity_pos_t GetMaximumClearance() const override
184 : {
185 0 : entity_pos_t max = fixed::Zero();
186 :
187 0 : for (const PathfinderPassability& passability : m_PassClasses)
188 0 : if (passability.m_Clearance > max)
189 0 : max = passability.m_Clearance;
190 :
191 0 : return max + Pathfinding::CLEARANCE_EXTENSION_RADIUS;
192 : }
193 :
194 : const Grid<NavcellData>& GetPassabilityGrid() override;
195 :
196 0 : const GridUpdateInformation& GetAIPathfinderDirtinessInformation() const override
197 : {
198 0 : return m_AIPathfinderDirtinessInformation;
199 : }
200 :
201 3 : void FlushAIPathfinderDirtinessInformation() override
202 : {
203 3 : m_AIPathfinderDirtinessInformation.Clean();
204 3 : }
205 :
206 : Grid<u16> ComputeShoreGrid(bool expandOnWater = false) override;
207 :
208 : void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const override;
209 :
210 : u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify) override;
211 :
212 : WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const override;
213 :
214 : u32 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 controller, entity_id_t notify) override;
215 :
216 : bool IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) override;
217 :
218 : void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) override;
219 :
220 : void SetDebugOverlay(bool enabled) override;
221 :
222 : void SetHierDebugOverlay(bool enabled) override;
223 :
224 : void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const override;
225 :
226 : void SetAtlasOverlay(bool enable, pass_class_t passClass = 0) override;
227 :
228 : bool 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) const override;
229 :
230 : ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint) const override;
231 :
232 : ICmpObstruction::EFoundationCheck 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) const override;
233 :
234 : ICmpObstruction::EFoundationCheck 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 onlyCenterPoint) const override;
235 :
236 : void SendRequestedPaths() override;
237 :
238 : void StartProcessingMoves(bool useMax) override;
239 :
240 : template <typename T>
241 : std::vector<T> GetMovesToProcess(std::vector<T>& requests, bool useMax = false, size_t maxMoves = 0);
242 :
243 : template <typename T>
244 : void PushRequestsToWorkers(std::vector<T>& from);
245 :
246 : /**
247 : * Regenerates the grid based on the current obstruction list, if necessary
248 : */
249 : void UpdateGrid() override;
250 :
251 : /**
252 : * Updates the terrain-only grid without updating the dirtiness informations.
253 : * Useful for fast passability updates in Atlas.
254 : */
255 : void MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1);
256 :
257 : /**
258 : * Regenerates the terrain-only grid.
259 : * Atlas doesn't need to have passability cells expanded.
260 : */
261 : void TerrainUpdateHelper(bool expandPassability = true, int itile0 = -1, int jtile0 = -1, int itile1 = -1, int jtile1 = -1);
262 :
263 : void RenderSubmit(SceneCollector& collector);
264 : };
265 :
266 0 : class AtlasOverlay : public TerrainTextureOverlay
267 : {
268 : public:
269 : const CCmpPathfinder* m_Pathfinder;
270 : pass_class_t m_PassClass;
271 :
272 0 : AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) :
273 0 : TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TERRAIN_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
274 : {
275 0 : }
276 :
277 0 : void BuildTextureRGBA(u8* data, size_t w, size_t h) override
278 : {
279 : // Render navcell passability, based on the terrain-only grid
280 0 : u8* p = data;
281 0 : for (size_t j = 0; j < h; ++j)
282 : {
283 0 : for (size_t i = 0; i < w; ++i)
284 : {
285 0 : SColor4ub color(0, 0, 0, 0);
286 0 : if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
287 0 : color = SColor4ub(255, 0, 0, 127);
288 :
289 0 : *p++ = color.R;
290 0 : *p++ = color.G;
291 0 : *p++ = color.B;
292 0 : *p++ = color.A;
293 : }
294 : }
295 0 : }
296 : };
297 :
298 : #endif // INCLUDED_CCMPPATHFINDER_COMMON
|
