Merge 'remotes/trunk'
[0ad.git] / docs / pathfinder.tex
blob6a575a139fe0be5f1b8f94dd12d2c0f19793f459
1 \documentclass[a4paper,10pt]{article}
3 \usepackage{hyperref}
4 \usepackage{mathpazo}
5 \usepackage{amsmath}
7 \usepackage{tikz}
8 \usetikzlibrary{calc}
10 \setlength{\oddsidemargin}{-0.4mm} % 25 mm left margin - 1 in
11 \setlength{\evensidemargin}{\oddsidemargin}
12 \setlength{\topmargin}{-5.4mm} % 20 mm top margin - 1 in
13 \setlength{\textwidth}{160mm} % 20/25 mm right margin
14 \setlength{\textheight}{247mm} % 20 mm bottom margin
15 \setlength{\headheight}{5.1mm}
16 \setlength{\headsep}{5mm}
17 \setlength{\parindent}{0mm}
18 \setlength{\parskip}{\medskipamount}
20 \title{0 A.D.\@ Pathfinder Design}
21 \author{Wildfire Games -- \url{http://wildfiregames.com/}}
23 \begin{document}
25 \maketitle
27 Disclaimer: This document mixes elements of the current implementation and TBI features. You're invited to take a look yourself at the code, or ask questions in \#0ad-dev on QuakeNet.
29 \tableofcontents
31 \section{Basic concepts}
33 Our world consists of:
34 \begin{itemize}
35 \item \textbf{Units} --
36 Small, mobile objects.
37 Units move along the ground (or water, if they're ships).
38 They have instant acceleration and deceleration, and zero turning circles.
39 \item \textbf{Structures} --
40 Possibly-large, stationary objects.
41 This includes buildings, walls, trees, rocks, etc.
42 \item \textbf{Terrain} --
43 2D grid with a heightmap and other per-terrain-tile data (e.g.\ texture),
44 plus a water plane.
45 \end{itemize}
47 Units and structures are not restricted to terrain tiles in any way --
48 they can have high-precision positions and can face in any direction.
49 Both are represented as \emph{obstruction squares} -- we simplify their shapes to
50 a single square\footnote{For ``square'', read ``rectangle''. Or ``affine transformation of a square'' if you prefer.}.
51 Units are typically humanoids and should move in at least roughly human-like ways
52 (not e.g.\ like hover-tanks).
53 Units should never move through structures,
54 and in general should never move through other units (except in special cases like formations).
56 The world might have something like 1000 units (all moving at once),
57 $256\times256$ terrain tiles, 100 buildings, 1000 trees.
58 The target platform is PCs (in particular x86 or x86\_64 with 512+ MB RAM;
59 we can use a lot of memory for pathfinding if necessary).
61 \emph{Pathfinding} is the operation of picking a route for a unit to move along
62 from its current location to any other location in the world,
63 so that it does not collide with other units
64 or with structures or with impassable terrain.
65 The picked route should be the shortest (or an equal shortest) of all possible routes.
67 Pathfinding is split into two levels.
68 The \emph{long-range pathfinder} is responsible for finding approximate routes
69 that can span from one corner of the map to the other.
70 It only needs to care about structures and terrain;
71 any units in the way will probably have moved by the time the pathing unit reaches them,
72 so there's no need for the long-range pathfinder to plan around them.
73 It can approximate the world as a 2D grid.
74 The \emph{short-range pathfinder} is responsible for computing precise paths
75 that follow a segment of the long-range path --
76 these should not be quantised to a grid (since that would look ugly),
77 and should avoid other units,
78 but only need to work over a short distance (to the next waypoint on the long-range path).
80 \subsection{Coordinates}
82 Units have an $(x, z)$ position, measured in `meters' (the generic world-space unit of distance).
83 The coordinates are implemented as fixed-point numbers
84 (with a 16-bit fraction, i.e.\ a resolution of $2^{-16}\mathrm{m} \approx 15\mu\mathrm{m}$),
85 but we can treat them as real numbers.
86 The positive $x$ direction is interpreted as right or east; the positive $z$ direction is up or north.
88 \emph{Navcells} (the tile-like concept used for navigation)
89 are squares identified as $(i, j)$,
90 corresponding to world-space coordinates
91 \begin{align*}
92 i \times \mathrm{NavcellSize} & \leq x < (i+1) \times \mathrm{NavcellSize} \\
93 j \times \mathrm{NavcellSize} & \leq z < (j+1) \times \mathrm{NavcellSize}
94 \end{align*}
95 where $\mathrm{NavcellSize}$ is typically $1.0$ in the current implementation.
97 A unit is always located on a single navcell:
99 \mathrm{PointToNavcell}(x, z) = (\lfloor x / \mathrm{NavcellSize} \rfloor, \lfloor z / \mathrm{NavcellSize} \rfloor)
102 \subsection{Units}
104 Units have a \emph{unit obstruction} shape,
105 with a defined radius.
106 The shape is usually interpreted as an axis-aligned square
107 (with width and height equal to $2\times\mathrm{UnitRadius}$),
108 but sometimes interpreted more like a circle.
109 Infantry units might have a radius of around 0.5,
110 while siege units might have a radius of around 4.
112 Units also have a passability class,
113 which defines various details about what kinds of terrain they can cross.
114 Most of the data structures used by the pathfinder are
115 duplicated once per passability class.
116 For this document, we'll mostly just describe algorithms in terms of a single passability class,
117 and the implementation implicitly picks the appropriate data for the current unit's class.
119 There might be something like 8--16 distinct passability classes in the game.
121 Passability classes also define a \emph{clearance} value,
122 which is typically similar to their obstruction radius,
123 defining how close they can get to structures or impassable terrain.
124 Clearance should be a multiple of $\mathrm{NavcellSize}$.
126 TODO - Constraints on clearance vs radius: Currently, the radius of units is ignored, only their clearance is taken into account when computing a path, and when the move actually happens, their real obstruction size is not tested.
128 \subsection{Structures}
130 Structures are represented by \emph{static obstruction squares},
131 which are non-axis-aligned parallelograms
132 defined by $(x, z, \frac{w}{2}, \frac{h}{2}, \mathbf{u}, \mathbf{v})$:
134 \begin{tikzpicture}[>=stealth,scale=0.5]
136 \node (o) at (0,0) [label=below:{$(x,z)$}] {};
137 \draw (0,0) circle (0.1cm);
138 \node (a) at (3,4) [label=above:{$(x,z) + \frac{w}{2}\mathbf{u} + \frac{h}{2}\mathbf{v}$}] {};
139 \node (b) at (5,0) [label=right:{$(x,z) + \frac{w}{2}\mathbf{u} - \frac{h}{2}\mathbf{v}$}] {};
140 \node (c) at (-3,-4) [label=below:{$(x,z) - \frac{w}{2}\mathbf{u} - \frac{h}{2}\mathbf{v}$}] {};
141 \node (d) at (-5,0) [label=left:{$(x,z) - \frac{w}{2}\mathbf{u} + \frac{h}{2}\mathbf{v}$}] {};
143 \draw[<->,dashed] (o) -- (4,2) node[below,midway] {$\frac{w}{2}$};
144 \draw[<->,dashed] (o) -- (-1,2) node[left,midway] {$\frac{h}{2}$};
146 \draw
147 (3,4) circle (0.1cm) --
148 (5,0) circle (0.1cm) --
149 (-3,-4) circle (0.1cm) --
150 (-5,0) circle (0.1cm) --
151 (3,4);
153 \begin{scope}[xshift=-6cm,yshift=-3cm]
154 \draw[->] (0,0) -- (1,0.5) node[right] {$\mathbf{u}$};
155 \draw[->] (0,0) -- (-0.5,1) node[above] {$\mathbf{v}$};
156 \end{scope}
158 \end{tikzpicture}
160 The $\mathbf{u}$ and $\mathbf{v}$ are unit vectors.
161 They should be perpendicular; that's not theoretically required,
162 but some of the implementation assumes that.
164 We actually store the half-width $\frac{w}{2}$ (as ``\texttt{hw}'' in the code)
165 instead of $w$, because that seems more convenient for the implementation.
166 (Same for $h$.)
168 We store $\mathbf{u}$ and $\frac{w}{2}$ as two values,
169 instead of pre-multiplying them and using a single (non-unit) vector everywhere,
170 because occasionally we really need the unit vectors (e.g.\ to compute
171 world-space distance from a point to a square).
173 Some of the game code uses a representation $(x, z, w, h, \theta)$ instead
174 (where $\theta$ is anticlockwise from the $x$ axis),
175 which is more convenient for editing.
176 That is transformed into the vector form
177 (which is more convenient for geometric computation)
178 for the purposes of the algorithms described in this document.
180 \section{Implementation and code organization}
182 Pathfinding happens in two typical situations:
183 \begin{itemize}
184 \item When a unit is requested to move;
185 \item When the AI wants to plan a move (which will be eventually processed by the unit pathfinder) or a building construction.
186 \end{itemize}
188 The first case is handled by two components: \texttt{CCmpPathfinder}, which is a system component implementing pathfinding algorithms, and \texttt{CCmpUnitMotion}, which is a component each unit entity has. \texttt{CCmpUnitMotion} calls \texttt{CCmpPathfinder} methods to compute unit moves.
190 The second case must be handled inside each \emph{AI worker}, which is an object defined in \texttt{CCmpAIManager} that should eventually allow AI threading. As a consequence, it is not possible for AI workers to ask \texttt{CCmpPathfinder} for paths in a synchronous way.
192 Instead of implementing an asynchronous path request system for AI pathfinding, both AI workers and \texttt{CCmpPathfinder} have a \texttt{LongPathfinder} object capable of computing long paths based on a passability grid computed from terrain and static obstructions. This grid is computed in \texttt{CCmpPathfinder::UpdateGrid} and passed to the AI manager when an update is needed.
194 As of the short-range pathfinder, short-range algorithms remain plain \texttt{CCmpPathfinder} methods, only used for unit motion.
196 \section{Navcell grid}
198 The long-range pathfinder can be simpler and more efficient if it has a
199 grid representation of the map.
200 (Since our maps are large and open (i.e.\ a high degree of connectivity
201 between areas), and must support dynamic generation (random map scripts)
202 and dynamic modification (new buildings, walls, etc),
203 a grid is likely better than a nav mesh.)
205 Terrain is already based on a grid representation of the map,
206 but it is pretty low resolution (tiles have size $4.0 \times 4.0$;
207 you could fit 16 units onto a single terrain tile without much trouble)
208 so it will be poor at approximating narrow gaps which a single unit could fit through.
209 Increasing the terrain resolution would mean more heightmap and texture-pointer data
210 (10 bytes per tile),
211 more graphics data
212 (at least 16 bytes per tile, more when blending between textures),
213 and more triangles to render per frame.
214 It's better if we can use a higher-resolution grid for pathfinding than for terrain.
216 Pathfinding therefore uses a navcell grid, independent of the terrain grid.
217 Navcell passability is encoded as a 2D array covering the map,
218 with one bit per passability class.
219 Passability is computed from terrain and from static obstructions.
221 \subsection{Terrain}
223 (Implemented by \texttt{CCmpPathfinder::UpdateGrid}.)
225 A passability class defines maximum terrain slope, min/max water depth, etc.
226 For each navcell, we compute slopes and depths from the terrain heightmap.
227 When navcells are higher resolution than the heightmap, we do some interpolation
228 to get smoother output.
230 That will give a binary \emph{terrain passability grid} for this passability class:
232 \begin{tikzpicture}[
233 scale=0.5,
234 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=0.5cm}
237 \draw[step=1cm,black!60,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (20,10);
239 \foreach \x in {0,1,2} \node[blocked] at (\x,0) {};
240 \foreach \x in {0,1} \node[blocked] at (\x,1) {};
241 \foreach \x in {0} \node[blocked] at (\x,2) {};
242 \foreach \x in {12,...,19}
243 \foreach \y in {6,7,8,9}
244 \node[blocked] at (\x,\y) {};
246 \end{tikzpicture}
248 We also force the navcells around the outside of the map to be impassable.
249 (This means we usually don't have to worry about units walking off the edge of the map.
250 It also means we can use the shroud-of-darkness effect to make the map smoothly fade out
251 around its edges, and units won't walk so far out that they disappear into that SoD.\@)
252 This is either a circular or square pattern,
253 and we currently have at least 3 impassable terrain tiles (i.e.\ currently 12 navcells)
254 around each edge.
256 The grid is then expanded by the passability class's clearance value $c$
257 (effectively convolution with a square filter of size $(2c+1)\times(2c+1)$)
258 to get the \emph{expanded terrain passability grid}:
260 \begin{tikzpicture}[
261 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=0.5cm},
262 blocked2/.style={rectangle,draw=black!60,fill=black!30,minimum size=0.5cm},
263 scale=0.5
266 \def\unit#1;{
267 \draw[draw=green,fill=green!50,opacity=0.5] #1 circle (2cm);
268 \draw[draw=black] #1 ++(-0.2cm,-0.2cm) -- ++(0.4cm,0.4cm);
269 \draw[draw=black] #1 ++(-0.2cm,0.2cm) -- ++(0.4cm,-0.4cm);
272 \draw[step=1cm,black!60,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (20,10);
274 \node[blocked] at (0,0) {};
275 \node[blocked] at (1,0) {};
276 \node[blocked] at (2,0) {};
277 \node[blocked] at (0,1) {};
278 \node[blocked] at (1,1) {};
279 \node[blocked] at (0,2) {};
281 \foreach \x in {0,1,2} \node[blocked] at (\x,0) {};
282 \foreach \x in {0,1} \node[blocked] at (\x,1) {};
283 \foreach \x in {0} \node[blocked] at (\x,2) {};
284 \foreach \x in {12,...,19}
285 \foreach \y in {6,7,8,9}
286 \node[blocked] at (\x,\y) {};
288 \foreach \x in {3,4} \node[blocked2] at (\x,0) {};
289 \foreach \x in {2,3,4} \node[blocked2] at (\x,1) {};
290 \foreach \x in {1,2,3,4} \node[blocked2] at (\x,2) {};
291 \foreach \x in {0,1,2,3} \node[blocked2] at (\x,3) {};
292 \foreach \x in {0,1,2} \node[blocked2] at (\x,4) {};
294 \foreach \x in {10,11}
295 \foreach \y in {6,7,8,9}
296 \node[blocked2] at (\x,\y) {};
298 \foreach \x in {10,...,19}
299 \foreach \y in {4,5}
300 \node[blocked2] at (\x,\y) {};
302 \unit (14,3.45);
304 \end{tikzpicture}
306 (It'd be nicer to do a more circular convolution, so that the sharp corner
307 in the top-right gets smoothed to a more rounded corner,
308 especially with large clearance values.
309 That would be a self-contained enhancement and won't have any further consequences.)
311 A unit may be located anywhere on any passable navcell in this new grid.
312 If a unit is visualised as a circle with radius $r$,
313 then the circle won't overlap any impassable navcell in the
314 original terrain passability grid as long as $c \geq r$.
315 The green circle in the previous figure indicates a unit with $r=2$
316 in a valid location.
318 \subsection{Static obstructions}
320 (Implemented by \texttt{CCmpObstructionManager::Rasterize}.)
322 Rasterization is the process of converting a vector shape
323 (in this case an obstruction square)
324 into a pixel grid (in this case actually a navcell grid).
325 We do this so that the grid-based pathfinders can handle static obstructions (like walls)
326 in the same way as they handle terrain-based obstructions (like rivers).
328 For a given clearance value $c$,
329 a navcell is blocked by an obstruction shape
330 if every corner of the navcell
331 is either inside the shape or is a distance $d \leq c$ away from the shape.
333 In the following figure, blue is obstruction squares, red is the points at distance $c=1$
334 outside of the obstruction square,
335 green circles are some units with radius 1,
336 and grey squares are blocked by the obstructions.
338 \begin{tikzpicture}[
339 scale=0.5,
340 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=0.5cm}
343 \def\unit#1;{
344 \draw[draw=green,fill=green!50,opacity=0.5] #1 circle (1cm);
345 \draw[draw=black] #1 ++(-0.2cm,-0.2cm) -- ++(0.4cm,0.4cm);
346 \draw[draw=black] #1 ++(-0.2cm,0.2cm) -- ++(0.4cm,-0.4cm);
349 \draw[step=1cm,black!60,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (20,10);
351 \begin{scope}[xshift=4cm,yshift=3cm]
352 \foreach \x in {-1,...,1} \node[blocked] at (\x,-2) {};
353 \foreach \x in {-2,...,2} \node[blocked] at (\x,-1) {};
354 \foreach \x in {-2,...,2} \node[blocked] at (\x,0) {};
355 \foreach \x in {-1,...,1} \node[blocked] at (\x,1) {};
356 \draw [color=red,rounded corners=0.5cm] (-2.5,-2.5) rectangle (2.5,2);
357 \draw [color=blue] (-1.5,-1.5) rectangle (1.5,1);
358 \end{scope}
360 \begin{scope}[xshift=13cm,yshift=5cm]
361 \foreach \x in {2} \node[blocked] at (\x,3) {};
362 \foreach \x in {0,...,3} \node[blocked] at (\x,2) {};
363 \foreach \x in {-1,...,3} \node[blocked] at (\x,1) {};
364 \foreach \x in {-3,...,3} \node[blocked] at (\x,0) {};
365 \foreach \x in {-3,...,1} \node[blocked] at (\x,-1) {};
366 \foreach \x in {-3,...,-0} \node[blocked] at (\x,-2) {};
367 \foreach \x in {-2} \node[blocked] at (\x,-3) {};
368 \draw [color=red,rotate=30,rounded corners=0.5cm] (-4.5,-2.5) rectangle (4.5,2.5);
369 \draw [color=blue,rotate=30] (-3.5,-1.5) rectangle (3.5,1.5);
371 \unit (4.05,2);
372 \unit (4.65,1);
373 \unit (4.7,0);
374 \unit (3.3,-1);
376 \end{scope}
378 \end{tikzpicture}
380 It is important that partially-obstructed navcells are still considered passable:
381 when a unit is trying to move to a building (e.g.\ to attack it),
382 it can always succesfully get within any distance $d > c$ of the obstruction shape,
383 without having to move illegally onto an impassable navcell.
385 TODO: In the implementation, we need to be sure units never try to move
386 within a distance $d \leq c$, else they might be blocked by navcells.
387 Maybe add $c$ to all (positive) attack/gather/etc ranges?
389 \subsection{Narrow obstructions}
391 If an obstruction is especially narrow (e.g.\ a fence),
392 it might not block any navcells and units could walk straight through it,
393 which would surprise map designers.
395 The worst case is when rotated 45 degrees,
396 in which a long obstruction
397 must be at least $\frac{3}{\sqrt{2}}$ (about 2.12) navcells wide
398 (including the clearance expansion),
399 and a square obstruction must be at least $2\sqrt{2}$ (about 2.83) wide:
401 \begin{tikzpicture}[
402 >=stealth,
403 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=0.5cm}
406 \draw[step=1cm,black!40,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (10,5);
408 \begin{scope}[xshift=2.5cm,yshift=2cm]
409 \draw [color=red,rotate=45,rounded corners=0.5cm] (-1.05,-2.5) rectangle (1.05,2.5);
410 \draw[<->,rotate=45] (-1.05,1) node[right] {$\frac{\sqrt{2}}{2}+\sqrt{2}$} -- (1.05,1) ;
411 \end{scope}
413 \begin{scope}[xshift=6.5cm,yshift=2.5cm]
414 \draw [color=red,rotate=45,rounded corners=0.5cm] (-1.41,-1.41) rectangle (1.41,1.41);
415 \draw[<->,rotate=45] (-1.41,0) -- (1.41,0) node[midway,right] {$2\sqrt{2}$} ;
416 \end{scope}
418 \end{tikzpicture}
420 But there are still problems when a long obstruction is $\sqrt{5}$ (about 2.24) wide,
421 since it may contain gaps that units can walk through:
423 \begin{tikzpicture}[
424 >=stealth,
425 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=1cm}
428 \draw[step=1cm,black!40,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (7,5);
430 \begin{scope}[xshift=3cm,yshift=2cm]
431 \draw [color=red,rotate=63.43,rounded corners=0.5cm] (-1.11,-3) rectangle (1.11,3);
432 \draw[<->,rotate=63.43] (-1.11,1) node[right] {$\sqrt{5}$} -- (1.11,1) ;
433 \node[blocked] at (-2,1) {};
434 \node[blocked] at (0,0) {};
435 \node[blocked] at (2,-1) {};
436 \end{scope}
438 \end{tikzpicture}
440 To avoid these problems,
441 when rasterizing a rectangle of size $(w,h)$ with clearance $c$,
442 we will instead rasterize a rectangle of size $(w,h)$ with clearance $\max(c,\ (3-\min(w,h))/2)$
443 (where 3 is a nice round number that's definitely bigger than the limits demonstrated here).
444 When the smallest unit has $c=1$,
445 that limit will only take effect for obstructions with $w < 1$ or $h < 1$.
447 \subsection{Grid updates}
449 Each turn, the simulation calls CCmpPathfinder's UpdateGrid. This function calls the obstruction manager to know which part of the grid should be updated. This data is then stored for a clever update of the long-range pathfinder internal state. It is also sent to the AI long pathfinder.
451 If the terrain is modified, everything is recomputed. Else, the zone of the map where modified obstructions are is reset to its terrain-only passability value, and all obstructions overlapping modified obstructions are rasterized again on the map.
453 \section{Path goals}
455 When a path is requested, there is a source unit and a goal.
456 The goal might be:
457 \begin{itemize}
458 \item Point $(x, z)$ --
459 e.g.\ when telling a unit to walk to some specific location.
460 \item Square $(x, z, \frac{w}{2}, \frac{h}{2}, \mathbf{u}, \mathbf{v})$ --
461 e.g.\ when telling
462 a melee unit to attack a square building, they will move to positions close to the building
463 (depending on their maximum attack range) in a square pattern.
464 \item Circle $(x, z, r)$ --
465 e.g.\ when telling
466 a ranged unit to attack a square building, they will move to positions within
467 maximum attack range of the building in a circular pattern.
468 \item TODO: Inverted squares/circles for minimum attack range?
469 \end{itemize}
471 TODO: Need some constraints on squares/circles that are based on structures,
472 so they're always far enough out.
474 A navcell can be considered to be \emph{inside a goal}.
475 If the goal is a point $(x, z)$, then only the navcell $\mathrm{PointToNavcell}(x, z)$
476 is inside the goal.
477 Otherwise, a navcell is inside the goal if any point inside (or on the edge of) that navcell
478 is inside (or on the edge of) the goal shape.
480 TODO: Think about edges cases in relation to vertex pathfinder.
482 \section{Long-range pathfinder}
484 \subsection{Navcell-based A* pathfinder with JPS optimization}
486 The basic pathfinder is a pretty standard A* over a uniform-cost grid of navcells.
487 Connectivity between navcells is as illustrated:
489 \begin{tikzpicture}[
490 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=1cm}
493 \def\unit#1;{
494 \draw[draw=green,fill=green!50,opacity=0.5] #1 circle (1cm);
495 \draw[draw=black] #1 ++(-0.2cm,-0.2cm) -- ++(0.4cm,0.4cm);
496 \draw[draw=black] #1 ++(-0.2cm,0.2cm) -- ++(0.4cm,-0.4cm);
499 \draw[step=1cm,black!60,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (7,4);
501 \node[blocked] at (2,2) {};
502 \node[blocked] at (3,1) {};
503 \node[blocked] at (5,2) {};
505 \foreach \x in {0,...,6}
506 \foreach \y in {0,...,3}
507 \draw (\x,\y) circle (0.1cm) node [circle,inner sep=0.07cm] (c\x\y) {};
509 \begin{scope}[color=blue]
510 \draw (c03)--(c13)--(c23)--(c33)--(c43)--(c53)--(c63);
511 \draw (c02)--(c12); \draw (c32)--(c42);
512 \draw (c01)--(c11)--(c21); \draw (c41)--(c51)--(c61);
513 \draw (c00)--(c10)--(c20)--(c30)--(c40)--(c50)--(c60);
514 \draw (c03)--(c02)--(c01)--(c00);
515 \draw (c13)--(c12)--(c11)--(c10);
516 \draw (c21)--(c20);
517 \draw (c33)--(c32);
518 \draw (c43)--(c42)--(c41)--(c40);
519 \draw (c51)--(c50);
520 \draw (c63)--(c62)--(c61)--(c60);
522 \draw (c03)--(c12)--(c01)--(c10);
523 \draw (c13)--(c02)--(c11)--(c00);
524 \draw (c11)--(c20);
525 \draw (c21)--(c10);
526 \draw (c33)--(c42);
527 \draw (c43)--(c32);
528 \draw (c40)--(c51)--(c60);
529 \draw (c41)--(c50)--(c61);
530 \end{scope}
532 \end{tikzpicture}
534 From any passable navcell, you can move to any horizontally/vertically adjacent
535 passable navcell with cost $1$.
536 Also, you can move diagonally from any navcell $(i,j)$ to $(i\pm1,j\pm1)$
537 if those navcells,
538 plus the adjacent navcells $(i\pm1,j\mp1)$ and $(i\mp1,j\pm1)$,
539 are all passable.
540 Diagonal moves have cost $\sqrt{2}$.
542 Note that this definition of diagonal movement
543 means that connectivity between any two navcells
544 can be determined solely from the horizontal/vertical adjacencies;
545 the only effect of the diagonal moves is to allow smoother shorter paths.
547 This algorithm is opimized using a JPS algorithm (jump-point search), which is especially efficient on sparse grids, i.e. when a lot of similar possible paths exist.
549 \subsection{Hierarchical pathfinder}
551 The long pathfinder has a hierarchical pathfinder that provide efficient connectivity algorithms. It is used directly by the AI and it is called to improve long paths computed with the A* algorithms.
553 It can do the following:
554 \begin{itemize}
555 \item Determine if there is at least one path through the navcell grid between
556 passable navcells $a$ and $b$ (i.e.\ determine if $b$ is \emph{reachable} from $a$).
557 \item Given a goal shape and a passable source navcell $a$,
558 determine if there is any navcell that is in the goal and is reachable from $a$.
559 If not, find one of the reachable navcells that is nearest to the center of the goal.
560 \item Given an impassable navcell $a$, find one of the passable navcells that is
561 nearest to $a$.
562 \end{itemize}
564 Note that it doesn't actually find paths.
565 We might want to extend it to do that in the future,
566 if JPS is too slow.
568 TODO: Details.
570 \section{Vector pathfinder}
572 In addition to the navcell-based pathfinders (which are fine for approximate paths
573 over a fairly static grid with large obstructions,
574 but not good at fine detail or at very frequent changing or small obstructions),
575 we have a pathfinder based on a vector representation of the world.
577 The current implementation is a points-of-visibility pathfinder.
578 The world is represented as a set of edges (impassable straight lines for the outlines of obstructions)
579 and a set of vertexes (for the corners of obstructions).
580 Edges are single-sided (they block movement from outside an obstruction to the inside,
581 but not vice versa).
582 A path can go from any vertex to any other vertex, if the straight line between those vertexes
583 does not intersect any obstruction edges.
584 Given those vertexes and connectivity data,
585 a basic implementation of A* can find optimal paths.
587 The vector pathfinder has to understand terrain-based impassability
588 (which is fundamentally defined on a navcell grid),
589 static obstructions, and dynamic obstructions.
590 (Dynamic obstructions are other units -- they are smallish,
591 and can be treated as circles or axis-aligned squares or similar.)
593 Inconsistencies between the navcell pathfinder and vector pathfinder are problematic.
594 If the navcell pathfinder thinks a route is blocked,
595 but the vector pathfinder thinks there is enough space,
596 then units will sometimes use that route and sometimes refuse to.
597 In the opposite case, the navcell pathfinder will send a unit along a route
598 that it thinks is valid,
599 but the vector pathfinder will think there's not actually enough space
600 and the unit will be stuck and won't know where to go.
601 This is inevitable when a route is blocked by dynamic obstructions,
602 but we should aim to avoid such problems in at least the cases where there are
603 no dynamic obstructions.
605 To minimise those inconsistencies,
606 the vector pathfinder uses the navcell-grid rasterized versions of static obstructions,
607 instead of using the original rotated-rectangle vector versions.
609 The pathfinder algorithm does not explicitly take account of the unit's size --
610 it assumes the unit is a point and can move arbitrarily close to an obstruction edge.
611 Because the navcell grid has already encoded the unit's clearance value,
612 we can convert the navcell outlines directly into the vector representation
613 for this pathfinder, and units will not get too close to static obstructions.
615 Note that since navcells intersecting the edge of a static obstruction
616 are not made impassable,
617 the vector pathfinder will let units move slightly inside the
618 geometric shape of the obstruction
619 (by up to $\sqrt{2}\times\mathrm{NavcellSize}$).
620 (TODO: Be more specific/correct.)
622 Dynamic obstructions (units etc) are converted directly into vectors,
623 without quantising to the navcell grid.
624 Their obstruction shapes are axis-aligned squares with a known radius.
625 To stop units intersecting each other,
626 each square is expanded by the pathing unit's own obstruction radius.
628 Note that all edges (from dynamic obstructions and from the navcell grid)
629 are axis-aligned. This allows some simplifications and optimisations,
630 and avoids precision issues when deciding whether a point is precisely on a line.
632 TODO: Inconsistency between clearance and obstruction radius?
634 The pathfinder can then find paths between corners that don't intersect edges.
636 TODO: How does it handle edge cases like units starting precisely on an edge?
638 \begin{tikzpicture}[
639 >=stealth,
640 scale=0.5,
641 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=0.5cm}
644 \def\unit#1;{
645 \draw[draw=green,fill=green!50,opacity=0.5] #1 circle (1cm);
646 \draw[draw=black] #1 ++(-0.2cm,-0.2cm) -- ++(0.4cm,0.4cm);
647 \draw[draw=black] #1 ++(-0.2cm,0.2cm) -- ++(0.4cm,-0.4cm);
650 \def\unitb#1;{
651 \draw[draw=red,thick] ($#1-(2cm,2cm)$) rectangle ($#1+(2cm,2cm)$);
652 \draw[draw=green,fill=green!50,opacity=0.5] ($#1-(1cm,1cm)$) rectangle ($#1+(1cm,1cm)$);
653 \draw[draw=black] #1 ++(-0.2cm,-0.2cm) -- ++(0.4cm,0.4cm);
654 \draw[draw=black] #1 ++(-0.2cm,0.2cm) -- ++(0.4cm,-0.4cm);
657 \draw[step=1cm,black!60,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (20,10);
659 \begin{scope}[xshift=5cm,yshift=4cm]
661 \foreach \x in {0} \node[blocked] at (\x,1) {};
662 \foreach \x in {-1,0,1} \node[blocked] at (\x,0) {};
663 \foreach \x in {0} \node[blocked] at (\x,-1) {};
664 \draw [color=blue,rounded corners=0.5cm,rotate=45] (-2,-2) rectangle (2,2);
665 \draw [color=blue,rotate=45] (-1,-1) rectangle (1,1);
667 \draw [color=red,thick] (-0.5,1.5) -- ++(1,0) -- ++(0,-1) -- ++(1,0) -- ++(0,-1) -- ++(-1,0) -- ++(0,-1) -- ++(-1,0)
668 -- ++(0,1) -- ++(-1,0) -- ++(0,1) -- ++(1,0) -- ++(0,1);
670 \unitb (5.2,2.1);
671 \unitb (7.3,1.5);
673 \unit (-4,2);
674 \draw [color=black,thick]
675 (-4,2) circle (0.1cm) --
676 (0.6,1.6) circle (0.1cm) --
677 (3.1,0.0) circle (0.1cm) --
678 (5.2,-0.6) circle (0.1cm) --
679 (9.4,-0.6) circle (0.1cm) --
680 (12,2) circle (0.1cm);
682 \end{scope}
684 \end{tikzpicture}
686 \section{Specific situations}
688 \subsection{Stuck units}
690 (Implemented by \texttt{LongPathfinder::ComputePathOffImpassable}.)
692 A unit might find itself on an impassable navcell.
693 (We should prevent that whenever possible,
694 but we should be robust to error cases where the prevention fails,
695 and it can easily happen in Atlas.)
696 The JPS pathfinder and hierarchical goal reachability system
697 inherently require that units start on passable navcells.
698 We therefore need a way to safely get units off impassable navcells as quickly as possible.
700 The hierarchical pathfinder can find the nearest passable navcell to the unit.
701 We can then construct a straight-line path to that navcell,
702 and let the unit recompute a proper path once it's got out.
704 Normally the short-range pathfinder will let the unit get quite widely diverted from the long-range path.
705 That's bad when the unit is starting inside a building or a region of impassable terrain --
706 it might decide to go a very long way through the impassable region,
707 instead of getting out as quickly as possible.
709 TODO: How can we handle that? (Add a flag to disable the short-range pathfinder?
710 What if another unit is in the way?)
712 \subsection{Minimum ranges}
714 Some units have a minimum attack range (e.g.\ a ballista can't be aimed
715 at someone standing right in front of it).
716 If they are too close to their target,
717 they need to move away from it before being able to attack.
719 Minimum ranges will usually be quite small -- maybe 16 navcells at most.
720 That's short enough that the short-range pathfinder will always suffice;
721 we don't need to use the long-range pathfinder to work out how to move
722 away from the target.
723 This means the long-range pathfinder only has to care about how to move
724 towards a target (which avoids some minor complexities in the implementation).
726 The short-range pathfinder already moves to the edge of a goal shape,
727 and doesn't care whether the unit is starting inside or outside that shape.
728 That means it'll work for minimum-range movement with no further modifications.
730 \subsection{Unit movement}
732 The long-range pathfinder will give the unit a waypoint to walk towards.
733 The unit will move a short distance in that direction each turn.
734 To cope with dynamic changes to the world,
735 the unit needs to verify that its movement won't collide with anything.
736 This requires testing the movement line against the navcell grid,
737 and against unit obstructions (expanded by the moving unit's radius).
738 If there is a collision then the unit will compute a short path towards the next waypoint, to move around obstacles.
740 To check collisions with other units,
741 we expand every unit obstruction shape by the moving unit's radius,
742 and test the movement line against those squares.
743 TODO: How is the testing done, precisely?
744 If the start point is inside (or on the edge of) the square,
745 then it will never collide;
746 otherwise, if the end point is inside (or on the edge)
747 then it collides;
748 otherwise, it tests whether the line passes through the square
749 (TODO: edge cases).
751 This means a unit must never be placed precisely on the edge
752 of another unit obstruction -- it will be able to move inside the second unit.
753 If a unit is not inside (or on the edge),
754 it will never be able to move so that is inside (or on the edge),
755 so we just need to be careful when spawning new units to avoid starting too close.
757 TODO: Describe the navcell passability testing.
759 \subsection{Unit spawning}
761 (Implemented by \texttt{CCmpFootprint::PickSpawnPoint}
762 and \texttt{CCmpPathfinder::CheckUnitPlacement}.)
764 When a building trains a unit, it needs to pick positions nicely located
765 around the perimeter for the units to appear.
766 (We don't have units walking out of a door, they just appear instantly.)
767 A position is valid if it is on a passable navcell,
768 and if the unit doesn't overlap with any existing units.
770 TODO: The implementation tests against static obstructions unnecessarily.
772 \subsection{Foundation unit dispersal}
774 (Implemented by \texttt{CCmpObstruction::GetConstructionCollisions}
775 and \texttt{CCmpObstructionManager::GetUnitsOnObstruction}).
777 When a builder unit starts building a foundation,
778 there might be other units standing in the way.
779 (No other buildings etc can be in the way -- the foundation couldn't be placed in that case.)
780 Those units need to move out of the way,
781 else they will be colliding with the newly-constructed building.
782 But the builder itself shouldn't have to move
783 (it would get stuck in an infinite loop of trying to build and then moving away and then returning and trying again).
785 The important thing here is the rasterized building obstruction --
786 for each nearby unit, the unit should not be on a navcell that is blocked
787 by the rasterized obstruction after expanding by the unit's clearance.
789 Since the rasterization only includes navcells that are entirely inside the
790 obstruction expanded into a rounded-rectangle,
791 we could use an expanded (non-rounded) rectangle as a conservative approximation
792 to find units that might collide with the rasterization.
793 To be certain, we should add a small tolerance value (perhaps 0.5 navcells) onto the sizes.
795 So: Given the building's obstruction square, loop over every unit in the world.
796 Expand the square by unit's clearance plus tolerance. If the unit is inside that
797 square, tell it to move outwards to a square based on the obstruction square plus
798 clearance plus a larger tolerance.
800 The builder will have moved to a goal shape of the building's obstruction square
801 plus the max build range.
802 If the build range is strictly greater than the clearance plus tolerance,
803 then the builder won't block the building it's building.
805 TODO: Implement that range restriction somewhere.
807 \section{Building placement}
809 (Implemented by \texttt{CCmpObstruction::CheckFoundation}
810 and \texttt{CCmpPathfinder::CheckBuildingPlacement}.)
812 Buildings have various terrain restrictions (maximum slope,
813 min/max water depth, distance from shore, etc)
814 defined as a passability class.
815 Players should only be permitted to place a building if every navcell
816 under the building is valid,
817 so that they can't make them hang over the edges of cliffs etc.
818 Unlike the previously-described rasterization,
819 this should be an over-estimate of the building's shape
820 rather than an underestimate.
822 Overlapping structures are not a problem for the pathfinding system,
823 except that it's weird and ugly to let players build overlapping buildings,
824 and it's bad if players pack buildings so tightly that units get trapped
825 or if newly trained units don't have any space to spawn into.
827 We can therefore do pretty much anything to determine placeability,
828 but should expand the building's obstruction square somewhat to ensure
829 it's not too near any other buildings or obstructed navcells.
831 TODO: What specifically should we choose to do?
833 \section{Summary of constraints}
835 \begin{itemize}
837 \item Units have $(x,z)$ position, plus static $\mathrm{UnitClearance}$ and $\mathrm{UnitRadius}$.
839 \item $\mathrm{UnitClearance}$ should be an integer number of navcells,
840 to ensure consistent behaviour when the terrain grid is expanded by clearance.
842 \item $\mathrm{UnitRadius}$ can be any non-negative number.
844 \item For any unit, $\mathrm{PointToNavcell}(x,z)$ should be a passable navcell.
846 If not, the pathfinders will always try to move the unit onto the nearest passable navcell.
848 \item For any two units, we should have
849 \begin{align*}
850 |x_1-x_2| &> \mathrm{UnitRadius}_1 + \mathrm{UnitRadius}_2 \\
851 |z_1-z_2| &> \mathrm{UnitRadius}_1 + \mathrm{UnitRadius}_2
852 \end{align*}
853 If not, one unit might walk straight through the other.
855 \item When a unit is targeting a building, we need
857 \mathrm{MaxRange} \geq \mathrm{UnitClearance} + \varepsilon
859 to ensure the goal shape is fully on passable navcells, and
860 is fully reachable by the vector pathfinder.
862 \item When a unit is targeting another unit, we need
864 \mathrm{MaxRange} \geq \mathrm{UnitRadius}_1 + \mathrm{UnitRadius}_2 + \varepsilon
866 to ensure the goal shape
867 is fully reachable by the vector pathfinder.
869 \item To guarantee those two range constraints,
870 we will compute $\mathrm{MaxRange}$ separately in each case,
871 as $\mathrm{UnitMaxRange}+\mathrm{UnitClearance}+\varepsilon$ or as
872 $\mathrm{UnitMaxRange}+\mathrm{UnitRadius}_1+\mathrm{UnitRadius}_2+\varepsilon$,
873 with $\varepsilon=\frac{1}{8}$ (arbitrarily),
874 where $\mathrm{UnitMaxRange}$ is the non-negative value specified in the unit definition.
876 \item When units are spawned,
877 they must be on a passable navcell.
878 They must not collide with any unit obstruction shapes,
879 expanded by $\mathrm{UnitRadius} + \varepsilon$,
880 with $\varepsilon=\frac{1}{8}$ (arbitrarily).
882 \item Static obstructions must be at least $\frac{3}{2}\sqrt{2}$ ($\sim2.12$)
883 in each dimension, else they might not block any navcells and units could
884 walk through them:
886 \begin{tikzpicture}[
887 blocked/.style={rectangle,draw=black!60,fill=black!50,minimum size=0.5cm}
890 \draw[step=1cm,black!60,very thin,xshift=-0.5cm,yshift=-0.5cm] (0,0) grid (6,5);
892 \begin{scope}[xshift=2.5cm,yshift=2cm]
893 \draw [color=blue,rotate=45] (-1.06,-2) rectangle (1.06,2);
894 \end{scope}
896 \end{tikzpicture}
898 \end{itemize}
900 \section{TODO}
902 Things to fix in the implementation:
903 \begin{itemize}
904 \item Enforce range constraints.
905 \item Remove (or specify) support for \texttt{Unit} shapes.
906 \item Fix vector pathfinder to not do quadrant stuff.
907 \item Set up passability classes for the current units.
908 \item Testing.
909 \item Fix the navcell grid vectorisation.
910 \item Make impassable-navcell-escaping work properly.
911 \item A* heuristic overestimate with large goals.
912 \item ...
913 \end{itemize}
915 \end{document}