Pyrogenesis trunk
Pathfinding.h
Go to the documentation of this file.
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
25#include "PathGoal.h"
26
27class CParamNode;
28
30template<typename T>
31class Grid;
32
34{
41};
42
44{
55};
56
58{
60};
61
62/**
63 * Returned path.
64 * Waypoints are in *reverse* order (the earliest is at the back of the list)
65 */
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 */
77{
78 PathCost() : data(0) { }
79
80 /// Construct from a number of horizontal/vertical and diagonal steps
82 : data(hv * 65536 + d * 92682) // 2^16 * sqrt(2) == 92681.9
83 {
84 }
85
86 /// Construct for horizontal/vertical movement of given number of steps
88 {
89 return PathCost(n, 0);
90 }
91
92 /// Construct for diagonal movement of given number of steps
93 static PathCost diag(u16 n)
94 {
95 return PathCost(0, n);
96 }
97
98 PathCost operator+(const PathCost& a) const
99 {
100 PathCost c;
101 c.data = data + a.data;
102 return c;
103 }
104
106 {
107 data += a.data;
108 return *this;
109 }
110
111 bool operator<=(const PathCost& b) const { return data <= b.data; }
112 bool operator< (const PathCost& b) const { return data < b.data; }
113 bool operator>=(const PathCost& b) const { return data >= b.data; }
114 bool operator>(const PathCost& b) const { return data > b.data; }
115
117 {
118 return data;
119 }
120
121private:
123};
124
125inline constexpr int PASS_CLASS_BITS = 16;
126typedef 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
131namespace 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 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 */
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 */
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 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 i = static_cast<u16>(Clamp((x / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, w - 1));
167 j = static_cast<u16>(Clamp((z / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, h - 1));
168 }
169
170 /**
171 * Returns the position of the center of the given terrain tile
172 */
174 {
175 static_assert(TERRAIN_TILE_SIZE % 2 == 0);
178 }
179
181 {
182 x = entity_pos_t::FromInt(i * 2 + 1).Multiply(NAVCELL_SIZE / 2);
183 z = entity_pos_t::FromInt(j * 2 + 1).Multiply(NAVCELL_SIZE / 2);
184 }
185
186 /*
187 * Checks that the line (x0,z0)-(x1,z1) does not intersect any impassable navcells.
188 */
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 */
214{
215public:
217
218 bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) const
219 {
220 return ((m_MinDepth <= waterdepth && waterdepth <= m_MaxDepth) && (steepness < m_MaxSlope) && (m_MinShore <= shoredist && shoredist <= m_MaxShore));
221 }
222
224
225 fixed m_Clearance; // min distance from static obstructions
226
228 {
232 };
234
235private:
241};
242
243#endif // INCLUDED_PATHFINDING
T Clamp(T value, T min, T max)
Definition: MathUtil.h:32
u16 pass_class_t
Definition: Pathfinding.h:29
u16 NavcellData
Definition: Pathfinding.h:126
constexpr int PASS_CLASS_BITS
Definition: Pathfinding.h:125
const ssize_t TERRAIN_TILE_SIZE
metres [world space units] per tile in x and z
Definition: Terrain.h:40
A simple fixed-point number class.
Definition: Fixed.h:120
CFixed Multiply(CFixed n) const
Multiply by a CFixed.
Definition: Fixed.h:321
static constexpr CFixed FromInt(int n)
Definition: Fixed.h:140
An entity initialisation parameter node.
Definition: ParamNode.h:151
Basic 2D array, intended for storing tile data, plus support for lazy updates by ICmpObstructionManag...
Definition: Grid.h:38
Pathfinder goal.
Definition: PathGoal.h:33
Definition: Pathfinding.h:214
pass_class_t m_Mask
Definition: Pathfinding.h:223
fixed m_MinShore
Definition: Pathfinding.h:239
PathfinderPassability(pass_class_t mask, const CParamNode &node)
Definition: Pathfinding.cpp:124
fixed m_Clearance
Definition: Pathfinding.h:225
fixed m_MaxSlope
Definition: Pathfinding.h:238
ObstructionHandling
Definition: Pathfinding.h:228
@ NONE
Definition: Pathfinding.h:229
@ FOUNDATION
Definition: Pathfinding.h:231
@ PATHFINDING
Definition: Pathfinding.h:230
fixed m_MinDepth
Definition: Pathfinding.h:236
fixed m_MaxShore
Definition: Pathfinding.h:240
fixed m_MaxDepth
Definition: Pathfinding.h:237
ObstructionHandling m_Obstructions
Definition: Pathfinding.h:233
bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) const
Definition: Pathfinding.h:218
Definition: Pathfinding.cpp:28
void TerrainTileCenter(u16 i, u16 j, entity_pos_t &x, entity_pos_t &z)
Returns the position of the center of the given terrain tile.
Definition: Pathfinding.h:173
constexpr fixed NAVCELL_SIZE
The long-range pathfinder operates primarily over a navigation grid (a uniform-cost 2D passability gr...
Definition: Pathfinding.h:143
bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, pass_class_t passClass, const Grid< NavcellData > &grid)
Definition: Pathfinding.cpp:29
constexpr entity_pos_t CLEARANCE_EXTENSION_RADIUS
To make sure the long-range pathfinder is more strict than the short-range one, we need to slightly o...
Definition: Pathfinding.h:157
constexpr int NAVCELL_SIZE_INT
Definition: Pathfinding.h:144
constexpr int NAVCELLS_PER_TERRAIN_TILE
The terrain grid is coarser, and it is often convenient to convert from one to the other.
Definition: Pathfinding.h:150
void NearestNavcell(entity_pos_t x, entity_pos_t z, u16 &i, u16 &j, u16 w, u16 h)
Compute the navcell indexes on the grid nearest to a given point w, h are the grid dimensions,...
Definition: Pathfinding.h:163
void NavcellCenter(u16 i, u16 j, entity_pos_t &x, entity_pos_t &z)
Definition: Pathfinding.h:180
constexpr int NAVCELL_SIZE_LOG2
Definition: Pathfinding.h:145
u32 entity_id_t
Entity ID type.
Definition: Entity.h:29
Definition: Pathfinding.h:34
entity_id_t notify
Definition: Pathfinding.h:40
entity_pos_t x0
Definition: Pathfinding.h:36
u32 ticket
Definition: Pathfinding.h:35
pass_class_t passClass
Definition: Pathfinding.h:39
PathGoal goal
Definition: Pathfinding.h:38
entity_pos_t z0
Definition: Pathfinding.h:37
Represents the cost of a path consisting of horizontal/vertical and diagonal movements over a uniform...
Definition: Pathfinding.h:77
bool operator>(const PathCost &b) const
Definition: Pathfinding.h:114
PathCost(u16 hv, u16 d)
Construct from a number of horizontal/vertical and diagonal steps.
Definition: Pathfinding.h:81
PathCost operator+(const PathCost &a) const
Definition: Pathfinding.h:98
PathCost & operator+=(const PathCost &a)
Definition: Pathfinding.h:105
u32 ToInt()
Definition: Pathfinding.h:116
bool operator>=(const PathCost &b) const
Definition: Pathfinding.h:113
static PathCost horizvert(u16 n)
Construct for horizontal/vertical movement of given number of steps.
Definition: Pathfinding.h:87
static PathCost diag(u16 n)
Construct for diagonal movement of given number of steps.
Definition: Pathfinding.h:93
bool operator<=(const PathCost &b) const
Definition: Pathfinding.h:111
PathCost()
Definition: Pathfinding.h:78
bool operator<(const PathCost &b) const
Definition: Pathfinding.h:112
u32 data
Definition: Pathfinding.h:122
Definition: Pathfinding.h:44
entity_pos_t clearance
Definition: Pathfinding.h:48
pass_class_t passClass
Definition: Pathfinding.h:51
u32 ticket
Definition: Pathfinding.h:45
entity_id_t group
Definition: Pathfinding.h:53
PathGoal goal
Definition: Pathfinding.h:50
entity_id_t notify
Definition: Pathfinding.h:54
bool avoidMovingUnits
Definition: Pathfinding.h:52
entity_pos_t range
Definition: Pathfinding.h:49
entity_pos_t x0
Definition: Pathfinding.h:46
entity_pos_t z0
Definition: Pathfinding.h:47
Returned path.
Definition: Pathfinding.h:67
std::vector< Waypoint > m_Waypoints
Definition: Pathfinding.h:68
Definition: Pathfinding.h:58
entity_pos_t x
Definition: Pathfinding.h:59
entity_pos_t z
Definition: Pathfinding.h:59
uint16_t u16
Definition: types.h:38
uint32_t u32
Definition: types.h:39