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_PATHFINDING
19 : #define INCLUDED_PATHFINDING
20 :
21 : #include "graphics/Terrain.h"
22 : #include "maths/MathUtil.h"
23 :
24 : #include "simulation2/system/Entity.h"
25 : #include "PathGoal.h"
26 :
27 : class CParamNode;
28 :
29 : typedef u16 pass_class_t;
30 : template<typename T>
31 : class Grid;
32 :
33 0 : struct LongPathRequest
34 : {
35 : u32 ticket;
36 : entity_pos_t x0;
37 : entity_pos_t z0;
38 : PathGoal goal;
39 : pass_class_t passClass;
40 : entity_id_t notify;
41 : };
42 :
43 0 : struct ShortPathRequest
44 : {
45 : u32 ticket;
46 : entity_pos_t x0;
47 : entity_pos_t z0;
48 : entity_pos_t clearance;
49 : entity_pos_t range;
50 : PathGoal goal;
51 : pass_class_t passClass;
52 : bool avoidMovingUnits;
53 : entity_id_t group;
54 : entity_id_t notify;
55 : };
56 :
57 0 : struct Waypoint
58 : {
59 : entity_pos_t x, z;
60 : };
61 :
62 : /**
63 : * Returned path.
64 : * Waypoints are in *reverse* order (the earliest is at the back of the list)
65 : */
66 0 : struct WaypointPath
67 : {
68 : std::vector<Waypoint> m_Waypoints;
69 : };
70 :
71 : /**
72 : * Represents the cost of a path consisting of horizontal/vertical and
73 : * diagonal movements over a uniform-cost grid.
74 : * Maximum path length before overflow is about 45K steps.
75 : */
76 : struct PathCost
77 : {
78 0 : PathCost() : data(0) { }
79 :
80 : /// Construct from a number of horizontal/vertical and diagonal steps
81 0 : PathCost(u16 hv, u16 d)
82 0 : : data(hv * 65536 + d * 92682) // 2^16 * sqrt(2) == 92681.9
83 : {
84 0 : }
85 :
86 : /// Construct for horizontal/vertical movement of given number of steps
87 0 : static PathCost horizvert(u16 n)
88 : {
89 0 : return PathCost(n, 0);
90 : }
91 :
92 : /// Construct for diagonal movement of given number of steps
93 0 : static PathCost diag(u16 n)
94 : {
95 0 : return PathCost(0, n);
96 : }
97 :
98 0 : PathCost operator+(const PathCost& a) const
99 : {
100 0 : PathCost c;
101 0 : c.data = data + a.data;
102 0 : return c;
103 : }
104 :
105 0 : PathCost& operator+=(const PathCost& a)
106 : {
107 0 : data += a.data;
108 0 : return *this;
109 : }
110 :
111 : bool operator<=(const PathCost& b) const { return data <= b.data; }
112 0 : bool operator< (const PathCost& b) const { return data < b.data; }
113 0 : bool operator>=(const PathCost& b) const { return data >= b.data; }
114 0 : bool operator>(const PathCost& b) const { return data > b.data; }
115 :
116 : u32 ToInt()
117 : {
118 : return data;
119 : }
120 :
121 : private:
122 : u32 data;
123 : };
124 :
125 : inline constexpr int PASS_CLASS_BITS = 16;
126 : typedef u16 NavcellData; // 1 bit per passability class (up to PASS_CLASS_BITS)
127 : #define IS_PASSABLE(item, classmask) (((item) & (classmask)) == 0)
128 : #define PASS_CLASS_MASK_FROM_INDEX(id) ((pass_class_t)(1u << id))
129 : #define SPECIAL_PASS_CLASS PASS_CLASS_MASK_FROM_INDEX((PASS_CLASS_BITS-1)) // 16th bit, used for special in-place computations
130 :
131 : namespace Pathfinding
132 : {
133 : /**
134 : * The long-range pathfinder operates primarily over a navigation grid (a uniform-cost
135 : * 2D passability grid, with horizontal/vertical (not diagonal) connectivity).
136 : * This is based on the terrain tile passability, plus the rasterized shapes of
137 : * obstructions, all expanded outwards by the radius of the units.
138 : * Since units are much smaller than terrain tiles, the nav grid should be
139 : * higher resolution than the tiles.
140 : * We therefore split each the world into NxN "nav cells" (for some integer N,
141 : * preferably a power of two).
142 : */
143 956018 : inline constexpr fixed NAVCELL_SIZE = fixed::FromInt(1);
144 : inline constexpr int NAVCELL_SIZE_INT = 1;
145 : inline constexpr int NAVCELL_SIZE_LOG2 = 0;
146 :
147 : /**
148 : * The terrain grid is coarser, and it is often convenient to convert from one to the other.
149 : */
150 : inline constexpr int NAVCELLS_PER_TERRAIN_TILE = TERRAIN_TILE_SIZE / NAVCELL_SIZE_INT;
151 : static_assert(TERRAIN_TILE_SIZE % NAVCELL_SIZE_INT == 0, "Terrain tile size is not a multiple of navcell size");
152 :
153 : /**
154 : * To make sure the long-range pathfinder is more strict than the short-range one,
155 : * we need to slightly over-rasterize. So we extend the clearance radius by 1.
156 : */
157 : inline constexpr entity_pos_t CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1);
158 :
159 : /**
160 : * Compute the navcell indexes on the grid nearest to a given point
161 : * w, h are the grid dimensions, i.e. the number of navcells per side
162 : */
163 49 : inline void NearestNavcell(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h)
164 : {
165 : // Use NAVCELL_SIZE_INT to save the cost of dividing by a fixed
166 49 : i = static_cast<u16>(Clamp((x / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, w - 1));
167 49 : j = static_cast<u16>(Clamp((z / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, h - 1));
168 49 : }
169 :
170 : /**
171 : * Returns the position of the center of the given terrain tile
172 : */
173 0 : inline void TerrainTileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
174 : {
175 : static_assert(TERRAIN_TILE_SIZE % 2 == 0);
176 0 : x = entity_pos_t::FromInt(i*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2);
177 0 : z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2);
178 0 : }
179 :
180 6 : inline void NavcellCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
181 : {
182 6 : x = entity_pos_t::FromInt(i * 2 + 1).Multiply(NAVCELL_SIZE / 2);
183 6 : z = entity_pos_t::FromInt(j * 2 + 1).Multiply(NAVCELL_SIZE / 2);
184 6 : }
185 :
186 : /*
187 : * Checks that the line (x0,z0)-(x1,z1) does not intersect any impassable navcells.
188 : */
189 : bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1,
190 : pass_class_t passClass, const Grid<NavcellData>& grid);
191 : }
192 :
193 : /*
194 : * For efficient pathfinding we want to try hard to minimise the per-tile search cost,
195 : * so we precompute the tile passability flags for the various different types of unit.
196 : * We also want to minimise memory usage (there can easily be 100K tiles so we don't want
197 : * to store many bytes for each).
198 : *
199 : * To handle passability efficiently, we have a small number of passability classes
200 : * (e.g. "infantry", "ship"). Each unit belongs to a single passability class, and
201 : * uses that for all its pathfinding.
202 : * Passability is determined by water depth, terrain slope, forestness, buildingness.
203 : * We need at least one bit per class per tile to represent passability.
204 : *
205 : * Not all pass classes are used for actual pathfinding. The pathfinder calls
206 : * CCmpObstructionManager's Rasterize() to add shapes onto the passability grid.
207 : * Which shapes are rasterized depend on the value of the m_Obstructions of each passability
208 : * class.
209 : *
210 : * Passabilities not used for unit pathfinding should not use the Clearance attribute, and
211 : * will get a zero clearance value.
212 : */
213 : class PathfinderPassability
214 : {
215 : public:
216 : PathfinderPassability(pass_class_t mask, const CParamNode& node);
217 :
218 0 : bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) const
219 : {
220 0 : return ((m_MinDepth <= waterdepth && waterdepth <= m_MaxDepth) && (steepness < m_MaxSlope) && (m_MinShore <= shoredist && shoredist <= m_MaxShore));
221 : }
222 :
223 : pass_class_t m_Mask;
224 :
225 : fixed m_Clearance; // min distance from static obstructions
226 :
227 : enum ObstructionHandling
228 : {
229 : NONE,
230 : PATHFINDING,
231 : FOUNDATION
232 : };
233 : ObstructionHandling m_Obstructions;
234 :
235 : private:
236 : fixed m_MinDepth;
237 : fixed m_MaxDepth;
238 : fixed m_MaxSlope;
239 : fixed m_MinShore;
240 : fixed m_MaxShore;
241 : };
242 :
243 : #endif // INCLUDED_PATHFINDING
|
