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_LONGPATHFINDER
19 : #define INCLUDED_LONGPATHFINDER
20 :
21 : #include "Pathfinding.h"
22 :
23 : #include "graphics/Overlay.h"
24 : #include "renderer/Scene.h"
25 : #include "renderer/TerrainOverlay.h"
26 : #include "simulation2/helpers/Grid.h"
27 : #include "simulation2/helpers/PriorityQueue.h"
28 :
29 : #include <map>
30 :
31 : /**
32 : * Represents the 2D coordinates of a tile.
33 : * The i/j components are packed into a single u32, since we usually use these
34 : * objects for equality comparisons and the VC2010 optimizer doesn't seem to automatically
35 : * compare two u16s in a single operation.
36 : * TODO: maybe VC2012 will?
37 : */
38 : struct TileID
39 : {
40 : TileID() { }
41 :
42 0 : TileID(u16 i, u16 j) : data((i << 16) | j) { }
43 :
44 0 : bool operator==(const TileID& b) const
45 : {
46 0 : return data == b.data;
47 : }
48 :
49 : /// Returns lexicographic order over (i,j)
50 0 : bool operator<(const TileID& b) const
51 : {
52 0 : return data < b.data;
53 : }
54 :
55 0 : u16 i() const { return data >> 16; }
56 0 : u16 j() const { return data & 0xFFFF; }
57 :
58 : private:
59 : u32 data;
60 : };
61 :
62 : /**
63 : * Tile data for A* computation.
64 : * (We store an array of one of these per terrain tile, so it ought to be optimised for size)
65 : */
66 0 : struct PathfindTile
67 : {
68 : public:
69 : enum {
70 : STATUS_UNEXPLORED = 0,
71 : STATUS_OPEN = 1,
72 : STATUS_CLOSED = 2
73 : };
74 :
75 0 : bool IsUnexplored() const { return GetStatus() == STATUS_UNEXPLORED; }
76 0 : bool IsOpen() const { return GetStatus() == STATUS_OPEN; }
77 0 : bool IsClosed() const { return GetStatus() == STATUS_CLOSED; }
78 0 : void SetStatusOpen() { SetStatus(STATUS_OPEN); }
79 0 : void SetStatusClosed() { SetStatus(STATUS_CLOSED); }
80 :
81 : // Get pi,pj coords of predecessor to this tile on best path, given i,j coords of this tile
82 0 : inline int GetPredI(int i) const { return i + GetPredDI(); }
83 0 : inline int GetPredJ(int j) const { return j + GetPredDJ(); }
84 :
85 0 : inline PathCost GetCost() const { return g; }
86 0 : inline void SetCost(PathCost cost) { g = cost; }
87 :
88 : private:
89 : PathCost g; // cost to reach this tile
90 : u32 data; // 2-bit status; 15-bit PredI; 15-bit PredJ; packed for storage efficiency
91 :
92 : public:
93 0 : inline u8 GetStatus() const
94 : {
95 0 : return data & 3;
96 : }
97 :
98 0 : inline void SetStatus(u8 s)
99 : {
100 0 : ASSERT(s < 4);
101 0 : data &= ~3;
102 0 : data |= (s & 3);
103 0 : }
104 :
105 0 : int GetPredDI() const
106 : {
107 0 : return (i32)data >> 17;
108 : }
109 :
110 0 : int GetPredDJ() const
111 : {
112 0 : return ((i32)data << 15) >> 17;
113 : }
114 :
115 : // Set the pi,pj coords of predecessor, given i,j coords of this tile
116 0 : inline void SetPred(int pi, int pj, int i, int j)
117 : {
118 0 : int di = pi - i;
119 0 : int dj = pj - j;
120 0 : ASSERT(-16384 <= di && di < 16384);
121 0 : ASSERT(-16384 <= dj && dj < 16384);
122 0 : data &= 3;
123 0 : data |= (((u32)di & 0x7FFF) << 17) | (((u32)dj & 0x7FFF) << 2);
124 0 : }
125 : };
126 :
127 : struct CircularRegion
128 : {
129 : CircularRegion(entity_pos_t x, entity_pos_t z, entity_pos_t r) : x(x), z(z), r(r) {}
130 : entity_pos_t x, z, r;
131 : };
132 :
133 : typedef PriorityQueueHeap<TileID, PathCost, PathCost> PriorityQueue;
134 : typedef SparseGrid<PathfindTile> PathfindTileGrid;
135 :
136 : class JumpPointCache;
137 :
138 0 : struct PathfinderState
139 : {
140 : u32 steps; // number of algorithm iterations
141 :
142 : PathGoal goal;
143 :
144 : u16 iGoal, jGoal; // goal tile
145 :
146 : pass_class_t passClass;
147 :
148 : PriorityQueue open;
149 : // (there's no explicit closed list; it's encoded in PathfindTile)
150 :
151 : PathfindTileGrid* tiles;
152 : Grid<NavcellData>* terrain;
153 :
154 : PathCost hBest; // heuristic of closest discovered tile to goal
155 : u16 iBest, jBest; // closest tile
156 :
157 : const JumpPointCache* jpc;
158 : };
159 :
160 : class LongOverlay;
161 :
162 : class HierarchicalPathfinder;
163 :
164 : class LongPathfinder
165 : {
166 : public:
167 : LongPathfinder();
168 : ~LongPathfinder();
169 :
170 : void SetDebugOverlay(bool enabled);
171 :
172 0 : void SetDebugPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
173 : {
174 0 : if (!m_Debug.Overlay)
175 0 : return;
176 :
177 0 : SAFE_DELETE(m_Debug.Grid);
178 0 : delete m_Debug.Path;
179 0 : m_Debug.Path = new WaypointPath();
180 0 : ComputePath(hierPath, x0, z0, goal, passClass, *m_Debug.Path);
181 0 : m_Debug.PassClass = passClass;
182 : }
183 :
184 0 : void Reload(Grid<NavcellData>* passabilityGrid)
185 : {
186 0 : m_Grid = passabilityGrid;
187 0 : ASSERT(passabilityGrid->m_H == passabilityGrid->m_W);
188 0 : m_GridSize = passabilityGrid->m_W;
189 :
190 0 : m_JumpPointCache.clear();
191 0 : }
192 :
193 0 : void Update(Grid<NavcellData>* passabilityGrid)
194 : {
195 0 : m_Grid = passabilityGrid;
196 0 : ASSERT(passabilityGrid->m_H == passabilityGrid->m_W);
197 0 : ASSERT(m_GridSize == passabilityGrid->m_H);
198 :
199 0 : m_JumpPointCache.clear();
200 0 : }
201 :
202 : /**
203 : * Compute a tile-based path from the given point to the goal, and return the set of waypoints.
204 : * The waypoints correspond to the centers of horizontally/vertically adjacent tiles
205 : * along the path.
206 : */
207 : void ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
208 : pass_class_t passClass, WaypointPath& path) const;
209 :
210 : /**
211 : * Compute a tile-based path from the given point to the goal, excluding the regions
212 : * specified in excludedRegions (which are treated as impassable) and return the set of waypoints.
213 : * The waypoints correspond to the centers of horizontally/vertically adjacent tiles
214 : * along the path.
215 : */
216 : void ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
217 : pass_class_t passClass, std::vector<CircularRegion> excludedRegions, WaypointPath& path);
218 :
219 0 : void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const
220 : {
221 0 : GetDebugDataJPS(steps, time, grid);
222 0 : }
223 :
224 : Grid<NavcellData>* m_Grid;
225 : u16 m_GridSize;
226 :
227 : // Debugging - output from last pathfind operation.
228 3 : struct Debug
229 : {
230 : // Atomic - used to toggle debugging.
231 : std::atomic<LongOverlay*> Overlay = nullptr;
232 : // Mutable - set by ComputeJPSPath (thus possibly from different threads).
233 : // Synchronized via mutex if necessary.
234 : mutable PathfindTileGrid* Grid = nullptr;
235 : mutable u32 Steps;
236 : mutable double Time;
237 : mutable PathGoal Goal;
238 :
239 : WaypointPath* Path = nullptr;
240 : pass_class_t PassClass;
241 : } m_Debug;
242 :
243 : private:
244 : PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const;
245 : void ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state) const;
246 :
247 : /**
248 : * JPS algorithm helper functions
249 : * @param detectGoal is not used if m_UseJPSCache is true
250 : */
251 : void AddJumpedHoriz(int i, int j, int di, PathCost g, PathfinderState& state, bool detectGoal) const;
252 : int HasJumpedHoriz(int i, int j, int di, PathfinderState& state, bool detectGoal) const;
253 : void AddJumpedVert(int i, int j, int dj, PathCost g, PathfinderState& state, bool detectGoal) const;
254 : int HasJumpedVert(int i, int j, int dj, PathfinderState& state, bool detectGoal) const;
255 : void AddJumpedDiag(int i, int j, int di, int dj, PathCost g, PathfinderState& state) const;
256 :
257 : /**
258 : * See LongPathfinder.cpp for implementation details
259 : * TODO: cleanup documentation
260 : */
261 : void ComputeJPSPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const;
262 : void GetDebugDataJPS(u32& steps, double& time, Grid<u8>& grid) const;
263 :
264 : // Helper functions for ComputePath
265 :
266 : /**
267 : * Given a path with an arbitrary collection of waypoints, updates the
268 : * waypoints to be nicer.
269 : * If @param maxDist is non-zero, path waypoints will be espaced by at most @param maxDist.
270 : * In that case the distance between (x0, z0) and the first waypoint will also be made less than maxDist.
271 : */
272 : void ImprovePathWaypoints(WaypointPath& path, pass_class_t passClass, entity_pos_t maxDist, entity_pos_t x0, entity_pos_t z0) const;
273 :
274 : /**
275 : * Generate a passability map, stored in the 16th bit of navcells, based on passClass,
276 : * but with a set of impassable circular regions.
277 : */
278 : void GenerateSpecialMap(pass_class_t passClass, std::vector<CircularRegion> excludedRegions);
279 :
280 : bool m_UseJPSCache;
281 : // Mutable may be used here as caching does not change the external const-ness of the Long Range pathfinder.
282 : // This is thread-safe as it is order independent (no change in the output of the function for a given set of params).
283 : // Obviously, this means that the cache should actually be a cache and not return different results
284 : // from what would happen if things hadn't been cached.
285 : mutable std::map<pass_class_t, std::shared_ptr<JumpPointCache>> m_JumpPointCache;
286 : };
287 :
288 : #endif // INCLUDED_LONGPATHFINDER
|
