Line data Source code
1 : /* Copyright (C) 2021 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_HIERPATHFINDER
19 : #define INCLUDED_HIERPATHFINDER
20 :
21 : #include "Pathfinding.h"
22 :
23 : #include "ps/CLogger.h"
24 : #include "renderer/TerrainOverlay.h"
25 : #include "Render.h"
26 : #include "graphics/SColor.h"
27 :
28 : #include <map>
29 : #include <set>
30 :
31 : /**
32 : * Hierarchical pathfinder.
33 : *
34 : * Deals with connectivity (can point A reach point B?).
35 : *
36 : * The navcell-grid representation of the map is split into fixed-size chunks.
37 : * Within a chunk, each maximal set of adjacently-connected passable navcells
38 : * is defined as a region.
39 : * Each region is a vertex in the hierarchical pathfinder's graph.
40 : * When two regions in adjacent chunks are connected by passable navcells,
41 : * the graph contains an edge between the corresponding two vertexes.
42 : * By design, there can never be an edge between two regions in the same chunk.
43 : *
44 : * Those fixed-size chunks are used to efficiently compute "global regions" by effectively flood-filling.
45 : * Those can then be used to immediately determine if two reachables points are connected.
46 : *
47 : * The main use of this class is to convert an arbitrary PathGoal to a reachable navcell.
48 : * This happens in MakeGoalReachable.
49 : *
50 : */
51 :
52 : #ifdef TEST
53 : class TestCmpPathfinder;
54 : class TestHierarchicalPathfinder;
55 : #endif
56 :
57 : class HierarchicalOverlay;
58 : class SceneCollector;
59 :
60 : class HierarchicalPathfinder
61 : {
62 : #ifdef TEST
63 : friend class TestCmpPathfinder;
64 : friend class TestHierarchicalPathfinder;
65 : #endif
66 : public:
67 : typedef u32 GlobalRegionID;
68 :
69 : struct RegionID
70 : {
71 : u8 ci, cj; // chunk ID
72 : u16 r; // unique-per-chunk local region ID
73 :
74 452592 : RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { }
75 :
76 1020729 : bool operator<(const RegionID& b) const
77 : {
78 : // Sort by chunk ID, then by per-chunk region ID
79 1020729 : if (ci < b.ci)
80 113463 : return true;
81 907266 : if (b.ci < ci)
82 161443 : return false;
83 745823 : if (cj < b.cj)
84 127674 : return true;
85 618149 : if (b.cj < cj)
86 112298 : return false;
87 505851 : return r < b.r;
88 : }
89 :
90 19644 : bool operator==(const RegionID& b) const
91 : {
92 19644 : return ((ci == b.ci) && (cj == b.cj) && (r == b.r));
93 : }
94 :
95 : // Returns the distance from the center to the point (i, j)
96 5019 : inline u32 DistanceTo(u16 i, u16 j) const
97 : {
98 10038 : return (ci * CHUNK_SIZE + CHUNK_SIZE/2 - i) * (ci * CHUNK_SIZE + CHUNK_SIZE/2 - i) +
99 10038 : (cj * CHUNK_SIZE + CHUNK_SIZE/2 - j) * (cj * CHUNK_SIZE + CHUNK_SIZE/2 - j);
100 : }
101 :
102 : };
103 :
104 : HierarchicalPathfinder();
105 : ~HierarchicalPathfinder();
106 :
107 : void SetDebugOverlay(bool enabled, const CSimContext* simContext);
108 :
109 : // Non-pathfinding grids will never be recomputed on calling HierarchicalPathfinder::Update
110 : void Recompute(Grid<NavcellData>* passabilityGrid,
111 : const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks,
112 : const std::map<std::string, pass_class_t>& pathfindingPassClassMasks);
113 :
114 : void Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid);
115 :
116 : RegionID Get(u16 i, u16 j, pass_class_t passClass) const;
117 :
118 : GlobalRegionID GetGlobalRegion(u16 i, u16 j, pass_class_t passClass) const;
119 : GlobalRegionID GetGlobalRegion(RegionID region, pass_class_t passClass) const;
120 :
121 : /**
122 : * Updates @p goal so that it's guaranteed to be reachable from the navcell
123 : * @p i0, @p j0 (which is assumed to be on a passable navcell).
124 : *
125 : * If the goal is not reachable, it is replaced with a point goal nearest to
126 : * the goal center.
127 : *
128 : * In the case of a non-point reachable goal, it is replaced with a point goal
129 : * at the reachable navcell of the goal which is nearest to the starting navcell.
130 : *
131 : * @returns true if the goal was reachable, false otherwise.
132 : */
133 : bool MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass) const;
134 :
135 : /**
136 : * @return true if the goal is reachable from navcell i0, j0.
137 : * (similar to MakeGoalReachable but only checking for reachability).
138 : */
139 : bool IsGoalReachable(u16 i0, u16 j0, const PathGoal& goal, pass_class_t passClass) const;
140 :
141 : /**
142 : * Updates @p i, @p j (which is assumed to be an impassable navcell)
143 : * to the nearest passable navcell.
144 : */
145 : void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass) const;
146 :
147 : /**
148 : * Generates the connectivity grid associated with the given pass_class
149 : */
150 : Grid<u16> GetConnectivityGrid(pass_class_t passClass) const;
151 :
152 0 : pass_class_t GetPassabilityClass(const std::string& name) const
153 : {
154 0 : auto it = m_PassClassMasks.find(name);
155 0 : if (it != m_PassClassMasks.end())
156 0 : return it->second;
157 :
158 0 : LOGERROR("Invalid passability class name '%s'", name.c_str());
159 0 : return 0;
160 : }
161 :
162 : void RenderSubmit(SceneCollector& collector);
163 :
164 : private:
165 : static const u8 CHUNK_SIZE = 96; // number of navcells per side
166 : // TODO: figure out best number. Probably 64 < n < 128
167 :
168 114 : struct Chunk
169 : {
170 : u8 m_ChunkI, m_ChunkJ; // chunk ID
171 : std::vector<u16> m_RegionsID; // IDs of local regions, 0 (impassable) excluded
172 : u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell
173 :
174 : cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_RegionsID with a checkerboard pattern
175 :
176 : void InitRegions(int ci, int cj, Grid<NavcellData>* grid, pass_class_t passClass);
177 :
178 : RegionID Get(int i, int j) const;
179 :
180 : void RegionCenter(u16 r, int& i, int& j) const;
181 :
182 : void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const;
183 :
184 : bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const;
185 :
186 : #ifdef TEST
187 : bool operator==(const Chunk& b) const
188 : {
189 : return (m_ChunkI == b.m_ChunkI && m_ChunkJ == b.m_ChunkJ && m_RegionsID.size() == b.m_RegionsID.size() && memcmp(&m_Regions, &b.m_Regions, sizeof(u16) * CHUNK_SIZE * CHUNK_SIZE) == 0);
190 : }
191 : #endif
192 : };
193 :
194 154 : const Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) const
195 : {
196 154 : return m_Chunks.at(passClass).at(cj * m_ChunksW + ci);
197 : }
198 :
199 : typedef std::map<RegionID, std::set<RegionID> > EdgesMap;
200 :
201 : void ComputeNeighbors(EdgesMap& edges, Chunk& a, Chunk& b, bool transpose, bool opposite) const;
202 : void RecomputeAllEdges(pass_class_t passClass, EdgesMap& edges);
203 : void UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges);
204 :
205 : void UpdateGlobalRegions(const std::map<pass_class_t, std::vector<RegionID> >& needNewGlobalRegionMap);
206 :
207 : /**
208 : * Returns all reachable regions, optionally ordered in a specific manner.
209 : */
210 : template<typename Ordering>
211 31 : void FindReachableRegions(RegionID from, std::set<RegionID, Ordering>& reachable, pass_class_t passClass) const
212 : {
213 : // Flood-fill the region graph, starting at 'from',
214 : // collecting all the regions that are reachable via edges
215 31 : reachable.insert(from);
216 :
217 31 : const EdgesMap& edgeMap = m_Edges.at(passClass);
218 31 : if (edgeMap.find(from) == edgeMap.end())
219 2 : return;
220 :
221 58 : std::vector<RegionID> open;
222 29 : open.reserve(64);
223 29 : open.push_back(from);
224 :
225 551 : while (!open.empty())
226 : {
227 261 : RegionID curr = open.back();
228 261 : open.pop_back();
229 :
230 921 : for (const RegionID& region : edgeMap.at(curr))
231 : // Add to the reachable set; if this is the first time we added
232 : // it then also add it to the open list
233 660 : if (reachable.insert(region).second)
234 232 : open.push_back(region);
235 : }
236 : }
237 :
238 : struct SortByCenterToPoint
239 : {
240 22 : SortByCenterToPoint(u16 i, u16 j): gi(i), gj(j) {};
241 1477 : bool operator()(const HierarchicalPathfinder::RegionID& a, const HierarchicalPathfinder::RegionID& b) const
242 : {
243 1477 : if (a.DistanceTo(gi, gj) < b.DistanceTo(gi, gj))
244 502 : return true;
245 975 : if (a.DistanceTo(gi, gj) > b.DistanceTo(gi, gj))
246 636 : return false;
247 339 : return a.r < b.r;
248 : }
249 : u16 gi, gj;
250 : };
251 :
252 : void FindNearestNavcellInRegions(const std::set<RegionID, SortByCenterToPoint>& regions,
253 : u16& iGoal, u16& jGoal, pass_class_t passClass) const;
254 :
255 : struct InterestingRegion {
256 : RegionID region;
257 : u16 bestI;
258 : u16 bestJ;
259 : };
260 :
261 : struct SortByBestToPoint
262 : {
263 11 : SortByBestToPoint(u16 i, u16 j): gi(i), gj(j) {};
264 0 : bool operator()(const InterestingRegion& a, const InterestingRegion& b) const
265 : {
266 0 : if ((a.bestI - gi) * (a.bestI - gi) + (a.bestJ - gj) * (a.bestJ - gj) < (b.bestI - gi) * (b.bestI - gi) + (b.bestJ - gj) * (b.bestJ - gj))
267 0 : return true;
268 0 : if ((a.bestI - gi) * (a.bestI - gi) + (a.bestJ - gj) * (a.bestJ - gj) > (b.bestI - gi) * (b.bestI - gi) + (b.bestJ - gj) * (b.bestJ - gj))
269 0 : return false;
270 0 : return a.region.r < b.region.r;
271 : }
272 : u16 gi, gj;
273 : };
274 :
275 : // Returns the region along with the best cell for optimisation.
276 : void FindGoalRegionsAndBestNavcells(u16 i0, u16 j0, u16 gi, u16 gj, const PathGoal& goal, std::set<InterestingRegion, SortByBestToPoint>& regions, pass_class_t passClass) const;
277 :
278 : void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid) const;
279 :
280 : u16 m_W, m_H;
281 : u8 m_ChunksW, m_ChunksH;
282 : std::map<pass_class_t, std::vector<Chunk> > m_Chunks;
283 :
284 : std::map<pass_class_t, EdgesMap> m_Edges;
285 :
286 : std::map<pass_class_t, std::map<RegionID, GlobalRegionID> > m_GlobalRegions;
287 : GlobalRegionID m_NextGlobalRegionID;
288 :
289 : // Passability classes for which grids will be updated when calling Update
290 : std::map<std::string, pass_class_t> m_PassClassMasks;
291 :
292 : void AddDebugEdges(pass_class_t passClass);
293 : HierarchicalOverlay* m_DebugOverlay;
294 : const CSimContext* m_SimContext; // Used for drawing the debug lines
295 :
296 : public:
297 : std::vector<SOverlayLine> m_DebugOverlayLines;
298 : };
299 :
300 0 : class HierarchicalOverlay : public TerrainTextureOverlay
301 : {
302 : public:
303 : HierarchicalPathfinder& m_PathfinderHier;
304 :
305 0 : HierarchicalOverlay(HierarchicalPathfinder& pathfinderHier) :
306 0 : TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TERRAIN_TILE), m_PathfinderHier(pathfinderHier)
307 : {
308 0 : }
309 :
310 0 : virtual void BuildTextureRGBA(u8* data, size_t w, size_t h)
311 : {
312 0 : ENSURE(h <= std::numeric_limits<u16>::max() && w <= std::numeric_limits<u16>::max());
313 0 : u16 height = static_cast<u16>(h);
314 0 : u16 width = static_cast<u16>(w);
315 0 : pass_class_t passClass = m_PathfinderHier.GetPassabilityClass("default");
316 :
317 0 : for (u16 j = 0; j < height; ++j)
318 : {
319 0 : for (u16 i = 0; i < width; ++i)
320 : {
321 0 : SColor4ub color;
322 :
323 0 : HierarchicalPathfinder::RegionID rid = m_PathfinderHier.Get(i, j, passClass);
324 0 : if (rid.r == 0)
325 0 : color = SColor4ub(0, 0, 0, 0);
326 0 : else if (rid.r == 0xFFFF)
327 0 : color = SColor4ub(255, 0, 255, 255);
328 : else
329 0 : color = GetColor(rid.r + rid.ci*5 + rid.cj*7, 127);
330 :
331 0 : *data++ = color.R;
332 0 : *data++ = color.G;
333 0 : *data++ = color.B;
334 0 : *data++ = color.A;
335 : }
336 : }
337 0 : }
338 : };
339 :
340 :
341 : #endif // INCLUDED_HIERPATHFINDER
|
