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