1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 #include <cassert>
4
5 #include "PathCache.hpp"
6 #include "PathDefines.hpp"
7
8 #include "Sim/Misc/GlobalConstants.h"
9 #include "Sim/Misc/CollisionHandler.h"
10 #include "Sim/Misc/CollisionVolume.h"
11 #include "System/Rectangle.h"
12
GetRectangleCollisionVolume(const SRectangle & r,CollisionVolume & v,float3 & rm)13 static void GetRectangleCollisionVolume(const SRectangle& r, CollisionVolume& v, float3& rm) {
14 float3 vScales;
15
16 // rectangle dimensions (WS)
17 vScales.x = ((r.x2 - r.x1) * SQUARE_SIZE);
18 vScales.z = ((r.z2 - r.z1) * SQUARE_SIZE);
19 vScales.y = 1.0f;
20
21 // rectangle mid-point (WS)
22 rm.x = ((r.x1 + r.x2) * SQUARE_SIZE) >> 1;
23 rm.z = ((r.z1 + r.z2) * SQUARE_SIZE) >> 1;
24 rm.y = 0.0f;
25
26 #define CV CollisionVolume
27 v.InitShape(vScales, ZeroVector, CV::COLVOL_TYPE_BOX, CV::COLVOL_HITTEST_CONT, CV::COLVOL_AXIS_Y);
28 #undef CV
29 }
30
31
32
GetConstPath(unsigned int pathID,unsigned int pathType) const33 const QTPFS::IPath* QTPFS::PathCache::GetConstPath(unsigned int pathID, unsigned int pathType) const {
34 static IPath path; // dummy
35 const PathMap* map;
36
37 switch (pathType) {
38 case PATH_TYPE_TEMP: { map = &tempPaths; } break;
39 case PATH_TYPE_LIVE: { map = &livePaths; } break;
40 case PATH_TYPE_DEAD: { map = &deadPaths; } break;
41 default: { map = NULL; } break;
42 }
43
44 if (map == NULL)
45 return &path;
46
47 const PathMap::const_iterator it = map->find(pathID);
48
49 if (it != map->end()) {
50 return it->second;
51 }
52
53 return &path;
54 }
55
GetPath(unsigned int pathID,unsigned int pathType)56 QTPFS::IPath* QTPFS::PathCache::GetPath(unsigned int pathID, unsigned int pathType) {
57 IPath* path = const_cast<IPath*>(GetConstPath(pathID, pathType));
58
59 if (path->GetID() != 0) {
60 numCacheHits[pathType] += 1;
61 } else {
62 numCacheMisses[pathType] += 1;
63 }
64
65 return path;
66 }
67
68
69
AddTempPath(IPath * path)70 void QTPFS::PathCache::AddTempPath(IPath* path) {
71 assert(path->GetID() != 0);
72 assert(path->NumPoints() == 2);
73 assert(tempPaths.find(path->GetID()) == tempPaths.end());
74 assert(livePaths.find(path->GetID()) == livePaths.end());
75
76 tempPaths.insert(std::pair<unsigned int, IPath*>(path->GetID(), path));
77 }
78
AddLivePath(IPath * path)79 void QTPFS::PathCache::AddLivePath(IPath* path) {
80 assert(path->GetID() != 0);
81 assert(path->NumPoints() >= 2);
82
83 assert(tempPaths.find(path->GetID()) != tempPaths.end());
84 assert(livePaths.find(path->GetID()) == livePaths.end());
85 assert(deadPaths.find(path->GetID()) == deadPaths.end());
86
87 // promote a path from temporary- to live-status (no deletion)
88 tempPaths.erase(path->GetID());
89 livePaths.insert(std::pair<unsigned int, IPath*>(path->GetID(), path));
90 }
91
DelPath(unsigned int pathID)92 void QTPFS::PathCache::DelPath(unsigned int pathID) {
93 // if pathID is in xPaths, then yPaths and zPaths are guaranteed not
94 // to contain it (*only* exception is that deadPaths briefly overlaps
95 // tempPaths between QueueDeadPathSearches and KillDeadPaths)
96 PathMapIt it;
97
98 if ((it = tempPaths.find(pathID)) != tempPaths.end()) {
99 assert(livePaths.find(pathID) == livePaths.end());
100 assert(deadPaths.find(pathID) == deadPaths.end());
101 delete (it->second);
102 tempPaths.erase(it);
103 return;
104 }
105 if ((it = livePaths.find(pathID)) != livePaths.end()) {
106 assert(deadPaths.find(pathID) == deadPaths.end());
107 delete (it->second);
108 livePaths.erase(it);
109 return;
110 }
111 if ((it = deadPaths.find(pathID)) != deadPaths.end()) {
112 delete (it->second);
113 deadPaths.erase(it);
114 }
115 }
116
117
118
119
MarkDeadPaths(const SRectangle & r)120 bool QTPFS::PathCache::MarkDeadPaths(const SRectangle& r) {
121 #ifdef QTPFS_IGNORE_DEAD_PATHS
122 return false;
123 #endif
124
125 if (livePaths.empty())
126 return false;
127
128 // NOTE: not static, we run in multiple threads
129 CollisionVolume rv;
130 float3 rm;
131
132 GetRectangleCollisionVolume(r, rv, rm);
133
134 // "mark" any live path crossing the area of a terrain
135 // deformation, for which some or all of its waypoints
136 // might now be invalid and need to be recomputed
137 //
138 std::list<PathMapIt> livePathIts;
139
140 for (PathMapIt it = livePaths.begin(); it != livePaths.end(); ++it) {
141 IPath* path = it->second;
142
143 const float3& pathMins = path->GetBoundingBoxMins();
144 const float3& pathMaxs = path->GetBoundingBoxMaxs();
145
146 // if rectangle does not overlap bounding-box, skip this path
147 if ((r.x2 * SQUARE_SIZE) < pathMins.x) { continue; }
148 if ((r.z2 * SQUARE_SIZE) < pathMins.z) { continue; }
149 if ((r.x1 * SQUARE_SIZE) > pathMaxs.x) { continue; }
150 if ((r.z1 * SQUARE_SIZE) > pathMaxs.z) { continue; }
151
152 // figure out if <path> has at least one edge crossing <r>
153 // we only care about the segments we have not yet visited
154 const unsigned int minIdx = std::max(path->GetNextPointIndex(), 2U) - 2;
155 const unsigned int maxIdx = std::max(path->NumPoints(), 1u) - 1;
156
157 for (unsigned int i = minIdx; i < maxIdx; i++) {
158 const float3& p0 = path->GetPoint(i );
159 const float3& p1 = path->GetPoint(i + 1);
160
161 const bool p0InRect =
162 ((p0.x >= (r.x1 * SQUARE_SIZE) && p0.x < (r.x2 * SQUARE_SIZE)) &&
163 (p0.z >= (r.z1 * SQUARE_SIZE) && p0.z < (r.z2 * SQUARE_SIZE)));
164 const bool p1InRect =
165 ((p1.x >= (r.x1 * SQUARE_SIZE) && p1.x < (r.x2 * SQUARE_SIZE)) &&
166 (p1.z >= (r.z1 * SQUARE_SIZE) && p1.z < (r.z2 * SQUARE_SIZE)));
167 const bool havePointInRect = (p0InRect || p1InRect);
168
169 // NOTE:
170 // box-volume tests in its own space, but points are
171 // in world-space so we must inv-transform them first
172 // (p0 --> p0 - rm, p1 --> p1 - rm)
173 const bool
174 xRangeInRect = (p0.x >= (r.x1 * SQUARE_SIZE) && p1.x < (r.x2 * SQUARE_SIZE)),
175 xRangeExRect = (p0.x < (r.x1 * SQUARE_SIZE) && p1.x >= (r.x2 * SQUARE_SIZE)),
176 zRangeInRect = (p0.z >= (r.z1 * SQUARE_SIZE) && p1.z < (r.z2 * SQUARE_SIZE)),
177 zRangeExRect = (p0.z < (r.z1 * SQUARE_SIZE) && p1.z >= (r.z2 * SQUARE_SIZE));
178 const bool edgeCrossesRect =
179 (xRangeExRect && zRangeInRect) ||
180 (xRangeInRect && zRangeExRect) ||
181 CCollisionHandler::IntersectBox(&rv, p0 - rm, p1 - rm, NULL);
182
183 // remember the ID of each path affected by the deformation
184 if (havePointInRect || edgeCrossesRect) {
185 assert(tempPaths.find(path->GetID()) == tempPaths.end());
186 deadPaths.insert(std::pair<unsigned int, IPath*>(path->GetID(), path));
187 livePathIts.push_back(it);
188 break;
189 }
190 }
191 }
192
193 for (std::list<PathMapIt>::const_iterator it = livePathIts.begin(); it != livePathIts.end(); ++it) {
194 livePaths.erase(*it);
195 }
196
197 return true;
198 }
199
KillDeadPaths()200 void QTPFS::PathCache::KillDeadPaths() {
201 for (PathMap::const_iterator deadPathsIt = deadPaths.begin(); deadPathsIt != deadPaths.end(); ++deadPathsIt) {
202 // NOTE: "!=" because re-requested dead paths go onto the temp-pile
203 assert(tempPaths.find(deadPathsIt->first) != tempPaths.end());
204 assert(livePaths.find(deadPathsIt->first) == livePaths.end());
205 delete (deadPathsIt->second);
206 }
207
208 deadPaths.clear();
209 }
210
211