1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 #ifndef PATH_CONSTANTS_HDR
4 #define PATH_CONSTANTS_HDR
5
6 #include <limits>
7 #include <array>
8 #include "Sim/Misc/GlobalConstants.h"
9
10 static const float PATHCOST_INFINITY = std::numeric_limits<float>::infinity();
11
12 // NOTE:
13 // PF and PE both use a PathNodeBuffer of size MAX_SEARCHED_NODES,
14 // thus MAX_SEARCHED_NODES_{PF, PE} MUST be <= MAX_SEARCHED_NODES
15 static const unsigned int MAX_SEARCHED_NODES = 65536U;
16 static const unsigned int MAX_SEARCHED_NODES_PF = MAX_SEARCHED_NODES;
17 static const unsigned int MAX_SEARCHED_NODES_PE = MAX_SEARCHED_NODES;
18
19 // PathManager distance thresholds (to use PF or PE)
20 static const float MAXRES_SEARCH_DISTANCE = 25.0f;
21 static const float MEDRES_SEARCH_DISTANCE = 55.0f;
22 static const float MIN_MEDRES_SEARCH_DISTANCE = 40.0f;
23 static const float MIN_MAXRES_SEARCH_DISTANCE = 12.0f;
24
25 // how many recursive refinement attempts NextWayPoint should make
26 static const unsigned int MAX_PATH_REFINEMENT_DEPTH = 4;
27
28 static const unsigned int PATHESTIMATOR_VERSION = 61;
29
30 static const unsigned int MEDRES_PE_BLOCKSIZE = 8;
31 static const unsigned int LOWRES_PE_BLOCKSIZE = 32;
32
33 static const unsigned int SQUARES_TO_UPDATE = 1000;
34 static const unsigned int MAX_SEARCHED_NODES_ON_REFINE = 2000;
35
36 static const unsigned int PATH_HEATMAP_XSCALE = 1; // wrt. gs->hmapx
37 static const unsigned int PATH_HEATMAP_ZSCALE = 1; // wrt. gs->hmapy
38 static const unsigned int PATH_FLOWMAP_XSCALE = 32; // wrt. gs->mapx
39 static const unsigned int PATH_FLOWMAP_ZSCALE = 32; // wrt. gs->mapy
40
41
42 // PE-only flags (indices)
43 enum {
44 PATHDIR_LEFT = 0, // +x
45 PATHDIR_LEFT_UP = 1, // +x+z
46 PATHDIR_UP = 2, // +z
47 PATHDIR_RIGHT_UP = 3, // -x+z
48 PATHDIR_RIGHT = 4, // -x
49 PATHDIR_RIGHT_DOWN = 5, // -x-z
50 PATHDIR_DOWN = 6, // -z
51 PATHDIR_LEFT_DOWN = 7, // +x-z
52 PATH_DIRECTIONS = 8,
53 };
54 static const unsigned int PATHDIR_CARDINALS[4] = {PATHDIR_LEFT, PATHDIR_RIGHT, PATHDIR_UP, PATHDIR_DOWN};
55 static const unsigned int PATH_DIRECTION_VERTICES = PATH_DIRECTIONS >> 1;
56 static const unsigned int PATH_NODE_SPACING = 2;
57
58 // note: because the spacing between nodes is 2 (not 1) we
59 // must also make sure not to skip across any intermediate
60 // impassable squares (!) but without reducing the spacing
61 // factor which would drop performance four-fold --> messy
62 static_assert(PATH_NODE_SPACING == 2, "");
63
64 // PF and PE flags (used in nodeMask[])
65 enum {
66 PATHOPT_LEFT = 1, // +x
67 PATHOPT_RIGHT = 2, // -x
68 PATHOPT_UP = 4, // +z
69 PATHOPT_DOWN = 8, // -z
70 PATHOPT_OPEN = 16,
71 PATHOPT_CLOSED = 32,
72 PATHOPT_BLOCKED = 64,
73 PATHOPT_OBSOLETE = 128,
74
75 PATHOPT_SIZE = 255, // size of PATHOPT bitmask
76 };
77 static const unsigned int PATHOPT_CARDINALS = (PATHOPT_RIGHT | PATHOPT_LEFT | PATHOPT_UP | PATHOPT_DOWN);
78
79
GetPathDir2PathOpt()80 static inline std::array<unsigned int, PATH_DIRECTIONS> GetPathDir2PathOpt()
81 {
82 std::array<unsigned int, PATH_DIRECTIONS> a;
83 a[PATHDIR_LEFT] = PATHOPT_LEFT;
84 a[PATHDIR_RIGHT] = PATHOPT_RIGHT;
85 a[PATHDIR_UP] = PATHOPT_UP;
86 a[PATHDIR_DOWN] = PATHOPT_DOWN;
87 a[PATHDIR_LEFT_UP] = (PATHOPT_LEFT | PATHOPT_UP);
88 a[PATHDIR_RIGHT_UP] = (PATHOPT_RIGHT | PATHOPT_UP);
89 a[PATHDIR_RIGHT_DOWN] = (PATHOPT_RIGHT | PATHOPT_DOWN);
90 a[PATHDIR_LEFT_DOWN] = (PATHOPT_LEFT | PATHOPT_DOWN);
91 return a;
92 }
93
GetPathOpt2PathDir()94 static inline std::array<unsigned int, 15> GetPathOpt2PathDir()
95 {
96 std::array<unsigned int, 15> a;
97 for (auto& i: a) i = 0;
98 a[PATHOPT_LEFT] = PATHDIR_LEFT;
99 a[PATHOPT_RIGHT] = PATHDIR_RIGHT;
100 a[PATHOPT_UP] = PATHDIR_UP;
101 a[PATHOPT_DOWN] = PATHDIR_DOWN;
102 a[(PATHOPT_LEFT | PATHOPT_UP)] = PATHDIR_LEFT_UP;
103 a[(PATHOPT_RIGHT | PATHOPT_UP)] = PATHDIR_RIGHT_UP;
104 a[(PATHOPT_RIGHT | PATHOPT_DOWN)] = PATHDIR_RIGHT_DOWN;
105 a[(PATHOPT_LEFT | PATHOPT_DOWN)] = PATHDIR_LEFT_DOWN;
106 return a;
107 }
108
109
110 // converts a PATHDIR* index to a PATHOPT* bitmask
PathDir2PathOpt(unsigned int pathDir)111 static inline unsigned int PathDir2PathOpt(unsigned int pathDir) {
112 static const std::array<unsigned int, PATH_DIRECTIONS> DIR2OPT = GetPathDir2PathOpt();
113 return DIR2OPT[pathDir];
114 }
115
116 // converts a PATHOPT* bitmask to a PATHDIR* index
PathOpt2PathDir(unsigned int pathOptDir)117 static inline unsigned int PathOpt2PathDir(unsigned int pathOptDir) {
118 static const std::array<unsigned int, 15> OPT2DIR = GetPathOpt2PathDir();
119 return OPT2DIR[pathOptDir];
120 }
121
122
123 // transition costs between vertices are bi-directional
124 // (cost(A-->B) == cost(A<--B)) so we only need to store
125 // (PATH_DIRECTIONS >> 1) values
GetBlockVertexOffset(unsigned int pathDir,unsigned int numBlocks)126 static inline int GetBlockVertexOffset(unsigned int pathDir, unsigned int numBlocks) {
127 int bvo = 0;
128
129 switch (pathDir) {
130 case PATHDIR_LEFT: { bvo = PATHDIR_LEFT; } break;
131 case PATHDIR_LEFT_UP: { bvo = PATHDIR_LEFT_UP; } break;
132 case PATHDIR_UP: { bvo = PATHDIR_UP; } break;
133 case PATHDIR_RIGHT_UP: { bvo = PATHDIR_RIGHT_UP; } break;
134
135 case PATHDIR_RIGHT: { bvo = int(PATHDIR_LEFT ) - PATH_DIRECTION_VERTICES; } break;
136 case PATHDIR_RIGHT_DOWN: { bvo = int(PATHDIR_LEFT_UP ) - (numBlocks * PATH_DIRECTION_VERTICES) - PATH_DIRECTION_VERTICES; } break;
137 case PATHDIR_DOWN: { bvo = int(PATHDIR_UP ) - (numBlocks * PATH_DIRECTION_VERTICES); } break;
138 case PATHDIR_LEFT_DOWN: { bvo = int(PATHDIR_RIGHT_UP) - (numBlocks * PATH_DIRECTION_VERTICES) + PATH_DIRECTION_VERTICES; } break;
139 }
140
141 return bvo;
142 }
143
144 enum {
145 NODE_COST_F = 0,
146 NODE_COST_G = 1,
147 NODE_COST_H = 2,
148 };
149
150 #endif
151