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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
/* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
#include <cassert>
#include "PathCache.hpp"
#include "PathDefines.hpp"
#include "Sim/Misc/GlobalConstants.h"
#include "Sim/Misc/CollisionHandler.h"
#include "Sim/Misc/CollisionVolume.h"
#include "System/Rectangle.h"
static void GetRectangleCollisionVolume(const SRectangle& r, CollisionVolume& v, float3& rm) {
float3 vScales;
// rectangle dimensions (WS)
vScales.x = ((r.x2 - r.x1) * SQUARE_SIZE);
vScales.z = ((r.z2 - r.z1) * SQUARE_SIZE);
vScales.y = 1.0f;
// rectangle mid-point (WS)
rm.x = ((r.x1 + r.x2) * SQUARE_SIZE) >> 1;
rm.z = ((r.z1 + r.z2) * SQUARE_SIZE) >> 1;
rm.y = 0.0f;
#define CV CollisionVolume
v.InitShape(vScales, ZeroVector, CV::COLVOL_TYPE_BOX, CV::COLVOL_HITTEST_CONT, CV::COLVOL_AXIS_Y);
#undef CV
}
const QTPFS::IPath* QTPFS::PathCache::GetConstPath(unsigned int pathID, unsigned int pathType) const {
static IPath path; // dummy
const PathMap* map;
switch (pathType) {
case PATH_TYPE_TEMP: { map = &tempPaths; } break;
case PATH_TYPE_LIVE: { map = &livePaths; } break;
case PATH_TYPE_DEAD: { map = &deadPaths; } break;
default: { map = NULL; } break;
}
if (map == NULL)
return &path;
const PathMap::const_iterator it = map->find(pathID);
if (it != map->end()) {
return it->second;
}
return &path;
}
QTPFS::IPath* QTPFS::PathCache::GetPath(unsigned int pathID, unsigned int pathType) {
IPath* path = const_cast<IPath*>(GetConstPath(pathID, pathType));
if (path->GetID() != 0) {
numCacheHits[pathType] += 1;
} else {
numCacheMisses[pathType] += 1;
}
return path;
}
void QTPFS::PathCache::AddTempPath(IPath* path) {
assert(path->GetID() != 0);
assert(path->NumPoints() == 2);
assert(tempPaths.find(path->GetID()) == tempPaths.end());
assert(livePaths.find(path->GetID()) == livePaths.end());
tempPaths.insert(std::pair<unsigned int, IPath*>(path->GetID(), path));
}
void QTPFS::PathCache::AddLivePath(IPath* path) {
assert(path->GetID() != 0);
assert(path->NumPoints() >= 2);
assert(tempPaths.find(path->GetID()) != tempPaths.end());
assert(livePaths.find(path->GetID()) == livePaths.end());
assert(deadPaths.find(path->GetID()) == deadPaths.end());
// promote a path from temporary- to live-status (no deletion)
tempPaths.erase(path->GetID());
livePaths.insert(std::pair<unsigned int, IPath*>(path->GetID(), path));
}
void QTPFS::PathCache::DelPath(unsigned int pathID) {
// if pathID is in xPaths, then yPaths and zPaths are guaranteed not
// to contain it (*only* exception is that deadPaths briefly overlaps
// tempPaths between QueueDeadPathSearches and KillDeadPaths)
PathMapIt it;
if ((it = tempPaths.find(pathID)) != tempPaths.end()) {
assert(livePaths.find(pathID) == livePaths.end());
assert(deadPaths.find(pathID) == deadPaths.end());
delete (it->second);
tempPaths.erase(it);
return;
}
if ((it = livePaths.find(pathID)) != livePaths.end()) {
assert(deadPaths.find(pathID) == deadPaths.end());
delete (it->second);
livePaths.erase(it);
return;
}
if ((it = deadPaths.find(pathID)) != deadPaths.end()) {
delete (it->second);
deadPaths.erase(it);
}
}
bool QTPFS::PathCache::MarkDeadPaths(const SRectangle& r) {
#ifdef QTPFS_IGNORE_DEAD_PATHS
return false;
#endif
if (livePaths.empty())
return false;
// NOTE: not static, we run in multiple threads
CollisionVolume rv;
float3 rm;
GetRectangleCollisionVolume(r, rv, rm);
// "mark" any live path crossing the area of a terrain
// deformation, for which some or all of its waypoints
// might now be invalid and need to be recomputed
std::vector<PathMapIt> livePathIts;
livePathIts.reserve(livePaths.size());
for (PathMapIt it = livePaths.begin(); it != livePaths.end(); ++it) {
IPath* path = it->second;
const float3& pathMins = path->GetBoundingBoxMins();
const float3& pathMaxs = path->GetBoundingBoxMaxs();
// if rectangle does not overlap bounding-box, skip this path
if ((r.x2 * SQUARE_SIZE) < pathMins.x) { continue; }
if ((r.z2 * SQUARE_SIZE) < pathMins.z) { continue; }
if ((r.x1 * SQUARE_SIZE) > pathMaxs.x) { continue; }
if ((r.z1 * SQUARE_SIZE) > pathMaxs.z) { continue; }
// figure out if <path> has at least one edge crossing <r>
// we only care about the segments we have not yet visited
const unsigned int minIdx = std::max(path->GetNextPointIndex(), 2U) - 2;
const unsigned int maxIdx = std::max(path->NumPoints(), 1u) - 1;
for (unsigned int i = minIdx; i < maxIdx; i++) {
const float3& p0 = path->GetPoint(i );
const float3& p1 = path->GetPoint(i + 1);
const bool p0InRect =
((p0.x >= (r.x1 * SQUARE_SIZE) && p0.x < (r.x2 * SQUARE_SIZE)) &&
(p0.z >= (r.z1 * SQUARE_SIZE) && p0.z < (r.z2 * SQUARE_SIZE)));
const bool p1InRect =
((p1.x >= (r.x1 * SQUARE_SIZE) && p1.x < (r.x2 * SQUARE_SIZE)) &&
(p1.z >= (r.z1 * SQUARE_SIZE) && p1.z < (r.z2 * SQUARE_SIZE)));
const bool havePointInRect = (p0InRect || p1InRect);
// NOTE:
// box-volume tests in its own space, but points are
// in world-space so we must inv-transform them first
// (p0 --> p0 - rm, p1 --> p1 - rm)
const bool
xRangeInRect = (p0.x >= (r.x1 * SQUARE_SIZE) && p1.x < (r.x2 * SQUARE_SIZE)),
xRangeExRect = (p0.x < (r.x1 * SQUARE_SIZE) && p1.x >= (r.x2 * SQUARE_SIZE)),
zRangeInRect = (p0.z >= (r.z1 * SQUARE_SIZE) && p1.z < (r.z2 * SQUARE_SIZE)),
zRangeExRect = (p0.z < (r.z1 * SQUARE_SIZE) && p1.z >= (r.z2 * SQUARE_SIZE));
const bool edgeCrossesRect =
(xRangeExRect && zRangeInRect) ||
(xRangeInRect && zRangeExRect) ||
CCollisionHandler::IntersectBox(&rv, p0 - rm, p1 - rm, NULL);
// remember the ID of each path affected by the deformation
if (havePointInRect || edgeCrossesRect) {
assert(tempPaths.find(path->GetID()) == tempPaths.end());
deadPaths.insert(std::pair<unsigned int, IPath*>(path->GetID(), path));
livePathIts.push_back(it);
break;
}
}
}
for (auto it = livePathIts.begin(); it != livePathIts.end(); ++it) {
livePaths.erase(*it);
}
return true;
}
void QTPFS::PathCache::KillDeadPaths() {
for (PathMap::const_iterator deadPathsIt = deadPaths.begin(); deadPathsIt != deadPaths.end(); ++deadPathsIt) {
// NOTE: "!=" because re-requested dead paths go onto the temp-pile
assert(tempPaths.find(deadPathsIt->first) != tempPaths.end());
assert(livePaths.find(deadPathsIt->first) == livePaths.end());
delete (deadPathsIt->second);
}
deadPaths.clear();
}
|
