1 | /* Copyright (C) 2020 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 "renderer/TerrainOverlay.h"
|
---|
39 | #include "simulation2/components/ICmpObstructionManager.h"
|
---|
40 | #include "simulation2/helpers/Grid.h"
|
---|
41 |
|
---|
42 |
|
---|
43 | class HierarchicalPathfinder;
|
---|
44 | class LongPathfinder;
|
---|
45 | class VertexPathfinder;
|
---|
46 |
|
---|
47 | class SceneCollector;
|
---|
48 | class AtlasOverlay;
|
---|
49 |
|
---|
50 | #ifdef NDEBUG
|
---|
51 | #define PATHFIND_DEBUG 0
|
---|
52 | #else
|
---|
53 | #define PATHFIND_DEBUG 1
|
---|
54 | #endif
|
---|
55 |
|
---|
56 | /**
|
---|
57 | * Implementation of ICmpPathfinder
|
---|
58 | */
|
---|
59 | class CCmpPathfinder final : public ICmpPathfinder
|
---|
60 | {
|
---|
61 | protected:
|
---|
62 |
|
---|
63 | class PathfinderWorker
|
---|
64 | {
|
---|
65 | friend CCmpPathfinder;
|
---|
66 | public:
|
---|
67 | PathfinderWorker();
|
---|
68 |
|
---|
69 | // Process path requests, checking if we should stop before each new one.
|
---|
70 | void Work(const CCmpPathfinder& pathfinder);
|
---|
71 |
|
---|
72 | private:
|
---|
73 | // Insert requests in m_[Long/Short]Requests depending on from.
|
---|
74 | // This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers
|
---|
75 | template<typename T>
|
---|
76 | void PushRequests(std::vector<T>& from, ssize_t amount);
|
---|
77 |
|
---|
78 | // Stores our results, the main thread will fetch this.
|
---|
79 | std::vector<PathResult> m_Results;
|
---|
80 |
|
---|
81 | std::vector<LongPathRequest> m_LongRequests;
|
---|
82 | std::vector<ShortPathRequest> m_ShortRequests;
|
---|
83 | };
|
---|
84 |
|
---|
85 | // Allow the workers to access our private variables
|
---|
86 | friend class PathfinderWorker;
|
---|
87 |
|
---|
88 | public:
|
---|
89 | static void ClassInit(CComponentManager& componentManager)
|
---|
90 | {
|
---|
91 | componentManager.SubscribeToMessageType(MT_Deserialized);
|
---|
92 | componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
|
---|
93 | componentManager.SubscribeToMessageType(MT_TerrainChanged);
|
---|
94 | componentManager.SubscribeToMessageType(MT_WaterChanged);
|
---|
95 | componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);
|
---|
96 | }
|
---|
97 |
|
---|
98 | ~CCmpPathfinder();
|
---|
99 |
|
---|
100 | DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)
|
---|
101 |
|
---|
102 | // Template state:
|
---|
103 |
|
---|
104 | std::map<std::string, pass_class_t> m_PassClassMasks;
|
---|
105 | std::vector<PathfinderPassability> m_PassClasses;
|
---|
106 |
|
---|
107 | // Dynamic state:
|
---|
108 |
|
---|
109 | std::vector<LongPathRequest> m_LongPathRequests;
|
---|
110 | std::vector<ShortPathRequest> m_ShortPathRequests;
|
---|
111 | u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests.
|
---|
112 | u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves.
|
---|
113 |
|
---|
114 | // Lazily-constructed dynamic state (not serialized):
|
---|
115 |
|
---|
116 | u16 m_MapSize; // tiles per side
|
---|
117 | Grid<NavcellData>* m_Grid; // terrain/passability information
|
---|
118 | Grid<NavcellData>* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations
|
---|
119 |
|
---|
120 | // Keep clever updates in memory to avoid memory fragmentation from the grid.
|
---|
121 | // This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else.
|
---|
122 | GridUpdateInformation m_DirtinessInformation;
|
---|
123 | // The data from clever updates is stored for the AI manager
|
---|
124 | GridUpdateInformation m_AIPathfinderDirtinessInformation;
|
---|
125 | bool m_TerrainDirty;
|
---|
126 |
|
---|
127 | std::unique_ptr<VertexPathfinder> m_VertexPathfinder;
|
---|
128 | std::unique_ptr<HierarchicalPathfinder> m_PathfinderHier;
|
---|
129 | std::unique_ptr<LongPathfinder> m_LongPathfinder;
|
---|
130 |
|
---|
131 | // Workers process pathing requests.
|
---|
132 | std::vector<PathfinderWorker> m_Workers;
|
---|
133 |
|
---|
134 | AtlasOverlay* m_AtlasOverlay;
|
---|
135 |
|
---|
136 | static std::string GetSchema()
|
---|
137 | {
|
---|
138 | return "<a:component type='system'/><empty/>";
|
---|
139 | }
|
---|
140 |
|
---|
141 | virtual void Init(const CParamNode& paramNode);
|
---|
142 |
|
---|
143 | virtual void Deinit();
|
---|
144 |
|
---|
145 | template<typename S>
|
---|
146 | void SerializeCommon(S& serialize);
|
---|
147 |
|
---|
148 | virtual void Serialize(ISerializer& serialize);
|
---|
149 |
|
---|
150 | virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize);
|
---|
151 |
|
---|
152 | virtual void HandleMessage(const CMessage& msg, bool global);
|
---|
153 |
|
---|
154 | virtual pass_class_t GetPassabilityClass(const std::string& name) const;
|
---|
155 |
|
---|
156 | virtual void GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const;
|
---|
157 | virtual void GetPassabilityClasses(
|
---|
158 | std::map<std::string, pass_class_t>& nonPathfindingPassClasses,
|
---|
159 | std::map<std::string, pass_class_t>& pathfindingPassClasses) const;
|
---|
160 |
|
---|
161 | const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const;
|
---|
162 |
|
---|
163 | virtual entity_pos_t GetClearance(pass_class_t passClass) const
|
---|
164 | {
|
---|
165 | const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
|
---|
166 | if (!passability)
|
---|
167 | return fixed::Zero();
|
---|
168 |
|
---|
169 | return passability->m_Clearance;
|
---|
170 | }
|
---|
171 |
|
---|
172 | virtual entity_pos_t GetMaximumClearance() const
|
---|
173 | {
|
---|
174 | entity_pos_t max = fixed::Zero();
|
---|
175 |
|
---|
176 | for (const PathfinderPassability& passability : m_PassClasses)
|
---|
177 | if (passability.m_Clearance > max)
|
---|
178 | max = passability.m_Clearance;
|
---|
179 |
|
---|
180 | return max + Pathfinding::CLEARANCE_EXTENSION_RADIUS;
|
---|
181 | }
|
---|
182 |
|
---|
183 | virtual const Grid<NavcellData>& GetPassabilityGrid();
|
---|
184 |
|
---|
185 | virtual const GridUpdateInformation& GetAIPathfinderDirtinessInformation() const
|
---|
186 | {
|
---|
187 | return m_AIPathfinderDirtinessInformation;
|
---|
188 | }
|
---|
189 |
|
---|
190 | virtual void FlushAIPathfinderDirtinessInformation()
|
---|
191 | {
|
---|
192 | m_AIPathfinderDirtinessInformation.Clean();
|
---|
193 | }
|
---|
194 |
|
---|
195 | virtual Grid<u16> ComputeShoreGrid(bool expandOnWater = false);
|
---|
196 |
|
---|
197 | virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const;
|
---|
198 |
|
---|
199 | virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify);
|
---|
200 |
|
---|
201 | virtual WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const;
|
---|
202 |
|
---|
203 | virtual 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);
|
---|
204 |
|
---|
205 | virtual bool IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass);
|
---|
206 |
|
---|
207 | virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass);
|
---|
208 |
|
---|
209 | virtual void SetDebugOverlay(bool enabled);
|
---|
210 |
|
---|
211 | virtual void SetHierDebugOverlay(bool enabled);
|
---|
212 |
|
---|
213 | virtual void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const;
|
---|
214 |
|
---|
215 | virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0);
|
---|
216 |
|
---|
217 | virtual 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;
|
---|
218 |
|
---|
219 | virtual 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;
|
---|
220 |
|
---|
221 | virtual 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;
|
---|
222 |
|
---|
223 | virtual 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;
|
---|
224 |
|
---|
225 | virtual void FetchAsyncResultsAndSendMessages();
|
---|
226 |
|
---|
227 | virtual void StartProcessingMoves(bool useMax);
|
---|
228 |
|
---|
229 | template <typename T>
|
---|
230 | std::vector<T> GetMovesToProcess(std::vector<T>& requests, bool useMax = false, size_t maxMoves = 0);
|
---|
231 |
|
---|
232 | template <typename T>
|
---|
233 | void PushRequestsToWorkers(std::vector<T>& from);
|
---|
234 |
|
---|
235 | /**
|
---|
236 | * Regenerates the grid based on the current obstruction list, if necessary
|
---|
237 | */
|
---|
238 | virtual void UpdateGrid();
|
---|
239 |
|
---|
240 | /**
|
---|
241 | * Updates the terrain-only grid without updating the dirtiness informations.
|
---|
242 | * Useful for fast passability updates in Atlas.
|
---|
243 | */
|
---|
244 | void MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1);
|
---|
245 |
|
---|
246 | /**
|
---|
247 | * Regenerates the terrain-only grid.
|
---|
248 | * Atlas doesn't need to have passability cells expanded.
|
---|
249 | */
|
---|
250 | void TerrainUpdateHelper(bool expandPassability = true, int itile0 = -1, int jtile0 = -1, int itile1 = -1, int jtile1 = -1);
|
---|
251 |
|
---|
252 | void RenderSubmit(SceneCollector& collector);
|
---|
253 | };
|
---|
254 |
|
---|
255 | class AtlasOverlay : public TerrainTextureOverlay
|
---|
256 | {
|
---|
257 | public:
|
---|
258 | const CCmpPathfinder* m_Pathfinder;
|
---|
259 | pass_class_t m_PassClass;
|
---|
260 |
|
---|
261 | AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) :
|
---|
262 | TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
|
---|
263 | {
|
---|
264 | }
|
---|
265 |
|
---|
266 | virtual void BuildTextureRGBA(u8* data, size_t w, size_t h)
|
---|
267 | {
|
---|
268 | // Render navcell passability, based on the terrain-only grid
|
---|
269 | u8* p = data;
|
---|
270 | for (size_t j = 0; j < h; ++j)
|
---|
271 | {
|
---|
272 | for (size_t i = 0; i < w; ++i)
|
---|
273 | {
|
---|
274 | SColor4ub color(0, 0, 0, 0);
|
---|
275 | if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
|
---|
276 | color = SColor4ub(255, 0, 0, 127);
|
---|
277 |
|
---|
278 | *p++ = color.R;
|
---|
279 | *p++ = color.G;
|
---|
280 | *p++ = color.B;
|
---|
281 | *p++ = color.A;
|
---|
282 | }
|
---|
283 | }
|
---|
284 | }
|
---|
285 | };
|
---|
286 |
|
---|
287 | #endif // INCLUDED_CCMPPATHFINDER_COMMON
|
---|