1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 #include <cassert>
4 #include <limits>
5
6 #include "lib/streflop/streflop_cond.h"
7
8 #include "Node.hpp"
9 #include "NodeLayer.hpp"
10 #include "PathDefines.hpp"
11 #include "PathManager.hpp"
12
13 #include "Map/MapInfo.h"
14 #include "Sim/Misc/GlobalConstants.h"
15 #include "Sim/Misc/GlobalSynced.h"
16
17 #define QTNODE_CHILD_COUNT 4
18
19 unsigned int QTPFS::QTNode::MIN_SIZE_X;
20 unsigned int QTPFS::QTNode::MIN_SIZE_Z;
21 unsigned int QTPFS::QTNode::MAX_DEPTH;
22
23
24
SetPathCost(unsigned int type,float cost)25 void QTPFS::INode::SetPathCost(unsigned int type, float cost) {
26 #ifndef QTPFS_ENABLE_MICRO_OPTIMIZATION_HACKS
27 switch (type) {
28 case NODE_PATH_COST_F: { fCost = cost; return; } break;
29 case NODE_PATH_COST_G: { gCost = cost; return; } break;
30 case NODE_PATH_COST_H: { hCost = cost; return; } break;
31 }
32
33 assert(false);
34 #else
35 assert(&gCost == &fCost + 1);
36 assert(&hCost == &gCost + 1);
37 assert(type <= NODE_PATH_COST_H);
38
39 *(&fCost + type) = cost;
40 #endif
41 }
42
GetPathCost(unsigned int type) const43 float QTPFS::INode::GetPathCost(unsigned int type) const {
44 #ifndef QTPFS_ENABLE_MICRO_OPTIMIZATION_HACKS
45 switch (type) {
46 case NODE_PATH_COST_F: { return fCost; } break;
47 case NODE_PATH_COST_G: { return gCost; } break;
48 case NODE_PATH_COST_H: { return hCost; } break;
49 }
50
51 assert(false);
52 return 0.0f;
53 #else
54 assert(&gCost == &fCost + 1);
55 assert(&hCost == &gCost + 1);
56 assert(type <= NODE_PATH_COST_H);
57
58 return *(&fCost + type);
59 #endif
60 }
61
GetDistance(const INode * n,unsigned int type) const62 float QTPFS::INode::GetDistance(const INode* n, unsigned int type) const {
63 const float dx = float(xmid() * SQUARE_SIZE) - float(n->xmid() * SQUARE_SIZE);
64 const float dz = float(zmid() * SQUARE_SIZE) - float(n->zmid() * SQUARE_SIZE);
65
66 switch (type) {
67 case NODE_DIST_EUCLIDEAN: { return (math::sqrt((dx * dx) + (dz * dz))); } break;
68 case NODE_DIST_MANHATTAN: { return (math::fabs(dx) + math::fabs(dz)); } break;
69 }
70
71 return -1.0f;
72 }
73
GetNeighborRelation(const INode * ngb) const74 unsigned int QTPFS::INode::GetNeighborRelation(const INode* ngb) const {
75 unsigned int rel = 0;
76
77 rel |= ((xmin() == ngb->xmax()) * REL_NGB_EDGE_L);
78 rel |= ((xmax() == ngb->xmin()) * REL_NGB_EDGE_R);
79 rel |= ((zmin() == ngb->zmax()) * REL_NGB_EDGE_T);
80 rel |= ((zmax() == ngb->zmin()) * REL_NGB_EDGE_B);
81
82 return rel;
83 }
84
GetRectangleRelation(const SRectangle & r) const85 unsigned int QTPFS::INode::GetRectangleRelation(const SRectangle& r) const {
86 // NOTE: we consider "interior" to be the set of all
87 // legal indices, and conversely "exterior" the set
88 // of all illegal indices (min-edges are inclusive,
89 // max-edges are exclusive)
90 //
91 if ((r.x1 >= xmin() && r.x2 < xmax()) && (r.z1 >= zmin() && r.z2 < zmax())) { return REL_RECT_INTERIOR_NODE; }
92 if ((r.x1 >= xmax() || r.x2 < xmin()) || (r.z1 >= zmax() || r.z2 < zmin())) { return REL_RECT_EXTERIOR_NODE; }
93 if ((r.x1 < xmin() && r.x2 >= xmax()) && (r.z1 < zmin() && r.z2 >= zmax())) { return REL_NODE_INTERIOR_RECT; }
94
95 return REL_NODE_OVERLAPS_RECT;
96 }
97
GetNeighborEdgeTransitionPoint(const INode * ngb,const float3 & pos,float alpha) const98 float3 QTPFS::INode::GetNeighborEdgeTransitionPoint(const INode* ngb, const float3& pos, float alpha) const {
99 float3 p;
100
101 const unsigned int
102 minx = std::max(xmin(), ngb->xmin()),
103 maxx = std::min(xmax(), ngb->xmax());
104 const unsigned int
105 minz = std::max(zmin(), ngb->zmin()),
106 maxz = std::min(zmax(), ngb->zmax());
107
108 // NOTE:
109 // do not use integer arithmetic for the mid-points,
110 // the path-backtrace expects all waypoints to have
111 // unique world-space coordinates (ortho-projection
112 // mode is broken in that regard) and this would not
113 // hold for a path through multiple neighboring nodes
114 // with xsize and/or zsize equal to 1 heightmap square
115 #ifndef QTPFS_ORTHOPROJECTED_EDGE_TRANSITIONS
116 const float
117 midx = minx * (1.0f - alpha) + maxx * (0.0f + alpha),
118 midz = minz * (1.0f - alpha) + maxz * (0.0f + alpha);
119 #endif
120
121 switch (GetNeighborRelation(ngb)) {
122 // corners
123 case REL_NGB_EDGE_T | REL_NGB_EDGE_L: { p.x = xmin() * SQUARE_SIZE; p.z = zmin() * SQUARE_SIZE; } break;
124 case REL_NGB_EDGE_T | REL_NGB_EDGE_R: { p.x = xmax() * SQUARE_SIZE; p.z = zmin() * SQUARE_SIZE; } break;
125 case REL_NGB_EDGE_B | REL_NGB_EDGE_R: { p.x = xmax() * SQUARE_SIZE; p.z = zmax() * SQUARE_SIZE; } break;
126 case REL_NGB_EDGE_B | REL_NGB_EDGE_L: { p.x = xmin() * SQUARE_SIZE; p.z = zmax() * SQUARE_SIZE; } break;
127
128 #ifdef QTPFS_ORTHOPROJECTED_EDGE_TRANSITIONS
129 #define CAST static_cast<unsigned int>
130
131 // edges
132 // clamp <pos> (assumed to be inside <this>) to
133 // the shared-edge bounds and ortho-project it
134 case REL_NGB_EDGE_T: { p.x = Clamp(CAST(pos.x / SQUARE_SIZE), minx, maxx) * SQUARE_SIZE; p.z = minz * SQUARE_SIZE; } break;
135 case REL_NGB_EDGE_B: { p.x = Clamp(CAST(pos.x / SQUARE_SIZE), minx, maxx) * SQUARE_SIZE; p.z = maxz * SQUARE_SIZE; } break;
136 case REL_NGB_EDGE_R: { p.z = Clamp(CAST(pos.z / SQUARE_SIZE), minz, maxz) * SQUARE_SIZE; p.x = maxx * SQUARE_SIZE; } break;
137 case REL_NGB_EDGE_L: { p.z = Clamp(CAST(pos.z / SQUARE_SIZE), minz, maxz) * SQUARE_SIZE; p.x = minx * SQUARE_SIZE; } break;
138
139 // <ngb> had better be an actual neighbor
140 case 0: { assert(false); } break;
141
142 #undef CAST
143 #else
144
145 // edges
146 case REL_NGB_EDGE_T: { p.x = midx * SQUARE_SIZE; p.z = zmin() * SQUARE_SIZE; } break;
147 case REL_NGB_EDGE_R: { p.x = xmax() * SQUARE_SIZE; p.z = midz * SQUARE_SIZE; } break;
148 case REL_NGB_EDGE_B: { p.x = midx * SQUARE_SIZE; p.z = zmax() * SQUARE_SIZE; } break;
149 case REL_NGB_EDGE_L: { p.x = xmin() * SQUARE_SIZE; p.z = midz * SQUARE_SIZE; } break;
150
151 // <ngb> had better be an actual neighbor
152 case 0: { assert(false); } break;
153
154 #endif
155 }
156
157 return p;
158 }
159
160 // clip an OVERLAPPING rectangle against our boundaries
161 //
162 // NOTE:
163 // the rectangle is only ASSUMED to not lie completely
164 // inside <this> (in which case this function acts as
165 // no-op), we do not explicitly test
166 //
167 // both REL_RECT_EXTERIOR_NODE and REL_NODE_OVERLAPS_RECT
168 // relations can produce zero- or negative-area rectangles
169 // when clipping --> need to ensure to not leave move-cost
170 // at its default value (0.0, which no node can logically
171 // have)
172 //
ClipRectangle(const SRectangle & r) const173 SRectangle QTPFS::INode::ClipRectangle(const SRectangle& r) const {
174 SRectangle cr = r;
175 cr.x1 = std::max(int(xmin()), r.x1);
176 cr.z1 = std::max(int(zmin()), r.z1);
177 cr.x2 = std::min(int(xmax()), r.x2);
178 cr.z2 = std::min(int(zmax()), r.z2);
179 return cr;
180 }
181
182
183
184
185
186
InitStatic()187 void QTPFS::QTNode::InitStatic() {
188 MIN_SIZE_X = std::max(1u, mapInfo->pfs.qtpfs_constants.minNodeSizeX);
189 MIN_SIZE_Z = std::max(1u, mapInfo->pfs.qtpfs_constants.minNodeSizeZ);
190 MAX_DEPTH = std::max(1u, mapInfo->pfs.qtpfs_constants.maxNodeDepth);
191 }
192
QTNode(const QTNode * parent,unsigned int nn,unsigned int x1,unsigned int z1,unsigned int x2,unsigned int z2)193 QTPFS::QTNode::QTNode(
194 const QTNode* parent,
195 unsigned int nn,
196 unsigned int x1, unsigned int z1,
197 unsigned int x2, unsigned int z2
198 ) {
199 assert(MIN_SIZE_X > 0);
200 assert(MIN_SIZE_Z > 0);
201
202 nodeNumber = nn;
203 heapIndex = -1u;
204
205 searchState = 0;
206 currMagicNum = 0;
207 prevMagicNum = -1u;
208
209 _depth = (parent != NULL)? parent->depth() + 1: 0;
210 _xminxmax = (x2 << 16) | (x1 << 0);
211 _zminzmax = (z2 << 16) | (z1 << 0);
212
213 assert(x2 < (1 << 16));
214 assert(z2 < (1 << 16));
215 assert(xsize() != 0);
216 assert(zsize() != 0);
217
218 fCost = 0.0f;
219 gCost = 0.0f;
220 hCost = 0.0f;
221
222 speedModSum = 0.0f;
223 speedModAvg = 0.0f;
224 moveCostAvg = -1.0f;
225
226 prevNode = NULL;
227
228 // for leafs, all children remain NULL
229 children.resize(QTNODE_CHILD_COUNT, NULL);
230 }
231
~QTNode()232 QTPFS::QTNode::~QTNode() {
233 children.clear();
234 neighbors.clear();
235 }
236
Delete()237 void QTPFS::QTNode::Delete() {
238 if (!IsLeaf()) {
239 for (unsigned int i = 0; i < children.size(); i++) {
240 children[i]->Delete(); children[i] = NULL;
241 }
242 }
243
244 neighbors.clear();
245 delete this;
246 }
247
248
249
GetMemFootPrint() const250 boost::uint64_t QTPFS::QTNode::GetMemFootPrint() const {
251 boost::uint64_t memFootPrint = sizeof(QTNode);
252
253 if (IsLeaf()) {
254 memFootPrint += (neighbors.size() * sizeof(INode*));
255 memFootPrint += (children.size() * sizeof(QTNode*));
256 memFootPrint += (netpoints.size() * sizeof(float3));
257 } else {
258 for (unsigned int i = 0; i < children.size(); i++) {
259 memFootPrint += (children[i]->GetMemFootPrint());
260 }
261 }
262
263 return memFootPrint;
264 }
265
GetCheckSum() const266 boost::uint64_t QTPFS::QTNode::GetCheckSum() const {
267 boost::uint64_t sum = 0;
268
269 {
270 const unsigned char* minByte = reinterpret_cast<const unsigned char*>(&nodeNumber);
271 const unsigned char* maxByte = reinterpret_cast<const unsigned char*>(&hCost) + sizeof(hCost);
272
273 assert(minByte < maxByte);
274
275 // INode bytes (unpadded)
276 for (const unsigned char* byte = minByte; byte != maxByte; byte++) {
277 sum ^= ((((byte + 1) - minByte) << 8) * (*byte));
278 }
279 }
280 {
281 const unsigned char* minByte = reinterpret_cast<const unsigned char*>(&_depth);
282 const unsigned char* maxByte = reinterpret_cast<const unsigned char*>(&prevMagicNum) + sizeof(prevMagicNum);
283
284 assert(minByte < maxByte);
285
286 // QTNode bytes (unpadded)
287 for (const unsigned char* byte = minByte; byte != maxByte; byte++) {
288 sum ^= ((((byte + 1) - minByte) << 8) * (*byte));
289 }
290 }
291
292 if (!IsLeaf()) {
293 for (unsigned int n = 0; n < children.size(); n++) {
294 sum ^= (((nodeNumber << 8) + 1) * children[n]->GetCheckSum());
295 }
296 }
297
298 return sum;
299 }
300
301
302
IsLeaf() const303 bool QTPFS::QTNode::IsLeaf() const {
304 assert(children.size() == QTNODE_CHILD_COUNT);
305 assert(
306 (children[0] == NULL && children[1] == NULL && children[2] == NULL && children[3] == NULL) ||
307 (children[0] != NULL && children[1] != NULL && children[2] != NULL && children[3] != NULL)
308 );
309 return (children[0] == NULL);
310 }
311
CanSplit(bool forced) const312 bool QTPFS::QTNode::CanSplit(bool forced) const {
313 // NOTE: caller must additionally check IsLeaf() before calling Split()
314 if (forced) {
315 return ((xsize() >> 1) > 0 && (zsize() >> 1) > 0);
316 }
317
318 if (depth() >= MAX_DEPTH) { return false; }
319
320 #ifdef QTPFS_CONSERVATIVE_NODE_SPLITS
321 if (xsize() <= MIN_SIZE_X) { return false; }
322 if (zsize() <= MIN_SIZE_Z) { return false; }
323 #else
324 // aggressive splitting, important with respect to yardmaps
325 // (one yardmap square represents four heightmap squares; a
326 // node represents MIN_SIZE_X by MIN_SIZE_Z of such squares)
327 if (((xsize() >> 1) == 0) || ((zsize() >> 1) == 0)) { return false; }
328 if (( xsize() <= MIN_SIZE_X) && ( zsize() <= MIN_SIZE_Z)) { return false; }
329 #endif
330
331 return true;
332 }
333
334
335
Split(NodeLayer & nl,bool forced)336 bool QTPFS::QTNode::Split(NodeLayer& nl, bool forced) {
337 if (!CanSplit(forced))
338 return false;
339
340 neighbors.clear();
341 netpoints.clear();
342
343 // can only split leaf-nodes (ie. nodes with NULL-children)
344 assert(children[NODE_IDX_TL] == NULL);
345 assert(children[NODE_IDX_TR] == NULL);
346 assert(children[NODE_IDX_BR] == NULL);
347 assert(children[NODE_IDX_BL] == NULL);
348
349 children[NODE_IDX_TL] = new QTNode(this, GetChildID(NODE_IDX_TL), xmin(), zmin(), xmid(), zmid());
350 children[NODE_IDX_TR] = new QTNode(this, GetChildID(NODE_IDX_TR), xmid(), zmin(), xmax(), zmid());
351 children[NODE_IDX_BR] = new QTNode(this, GetChildID(NODE_IDX_BR), xmid(), zmid(), xmax(), zmax());
352 children[NODE_IDX_BL] = new QTNode(this, GetChildID(NODE_IDX_BL), xmin(), zmid(), xmid(), zmax());
353
354 nl.SetNumLeafNodes(nl.GetNumLeafNodes() + (4 - 1));
355 assert(!IsLeaf());
356 return true;
357 }
358
Merge(NodeLayer & nl)359 bool QTPFS::QTNode::Merge(NodeLayer& nl) {
360 if (IsLeaf()) {
361 return false;
362 }
363
364 neighbors.clear();
365
366 // get rid of our children completely, but not of <this>!
367 for (unsigned int i = 0; i < children.size(); i++) {
368 children[i]->Delete(); children[i] = NULL;
369 }
370
371 nl.SetNumLeafNodes(nl.GetNumLeafNodes() - (4 - 1));
372 assert(IsLeaf());
373 return true;
374 }
375
376
377
378
379
380
381 #ifdef QTPFS_SLOW_ACCURATE_TESSELATION
382 // re-tesselate a tree from the deepest node <n> that contains
383 // rectangle <r> (<n> will be found from any higher node passed
384 // in)
385 //
386 // this code can be VERY slow in the worst-case (eg. when <r>
387 // overlaps all four children of the ROOT node), but minimizes
388 // the overall number of nodes in the tree at any given time
PreTesselate(NodeLayer & nl,const SRectangle & r,SRectangle & ur)389 void QTPFS::QTNode::PreTesselate(NodeLayer& nl, const SRectangle& r, SRectangle& ur) {
390 bool cont = false;
391
392 if (!IsLeaf()) {
393 for (unsigned int i = 0; i < children.size(); i++) {
394 if ((cont |= (children[i]->GetRectangleRelation(r) == REL_RECT_INTERIOR_NODE))) {
395 // only need to descend down one branch
396 children[i]->PreTesselate(nl, r, ur);
397 break;
398 }
399 }
400 }
401
402 if (!cont) {
403 ur.x1 = std::min(ur.x1, int(xmin()));
404 ur.z1 = std::min(ur.z1, int(zmin()));
405 ur.x2 = std::max(ur.x2, int(xmax()));
406 ur.z2 = std::max(ur.z2, int(zmax()));
407
408 Merge(nl);
409 Tesselate(nl, r);
410 }
411 }
412
413 #else
414
PreTesselate(NodeLayer & nl,const SRectangle & r,SRectangle & ur)415 void QTPFS::QTNode::PreTesselate(NodeLayer& nl, const SRectangle& r, SRectangle& ur) {
416 const unsigned int rel = GetRectangleRelation(r);
417
418 // use <r> if it is fully inside <this>, otherwise clip against our edges
419 const SRectangle& cr = (rel != REL_RECT_INTERIOR_NODE)? ClipRectangle(r): r;
420
421 if ((cr.x2 - cr.x1) <= 0 || (cr.z2 - cr.z1) <= 0) {
422 return;
423 }
424
425 // continue recursion while our CHILDREN are still larger than the clipped rectangle
426 //
427 // NOTE: this is a trade-off between minimizing the number of leaf-nodes (achieved by
428 // re-tesselating in its entirety the deepest node that fully contains <r>) and cost
429 // of re-tesselating (which grows as the node-count decreases, kept under control by
430 // breaking <r> up into pieces while descending further)
431 //
432 const bool leaf = IsLeaf();
433 const bool cont = (rel == REL_RECT_INTERIOR_NODE) ||
434 (((xsize() >> 1) > (cr.x2 - cr.x1)) &&
435 ((zsize() >> 1) > (cr.z2 - cr.z1)));
436
437 if (leaf || !cont) {
438 // extend a bounding box around every
439 // node modified during re-tesselation
440 ur.x1 = std::min(ur.x1, int(xmin()));
441 ur.z1 = std::min(ur.z1, int(zmin()));
442 ur.x2 = std::max(ur.x2, int(xmax()));
443 ur.z2 = std::max(ur.z2, int(zmax()));
444
445 Merge(nl);
446 Tesselate(nl, cr);
447 return;
448 }
449
450 for (unsigned int i = 0; i < children.size(); i++) {
451 children[i]->PreTesselate(nl, cr, ur);
452 }
453 }
454
455 #endif
456
457
458
Tesselate(NodeLayer & nl,const SRectangle & r)459 void QTPFS::QTNode::Tesselate(NodeLayer& nl, const SRectangle& r) {
460 unsigned int numNewBinSquares = 0; // nr. of squares in <r> that changed bin after deformation
461 unsigned int numDifBinSquares = 0; // nr. of different bin-types across all squares within <r>
462 unsigned int numClosedSquares = 0;
463
464 // if true, we are at the bottom of the recursion
465 bool registerNode = true;
466 bool wantSplit = false;
467 bool needSplit = false;
468
469 // if we just entered Tesselate from PreTesselate, <this> was
470 // merged and we need to update squares across the entire node
471 //
472 // if we entered from a higher-level Tesselate, <this> is newly
473 // allocated and we STILL need to update across the entire node
474 //
475 // this means the rectangle is actually irrelevant: only use it
476 // has is that numNewBinSquares can be calculated for area under
477 // rectangle rather than full node
478 //
479 // we want to *keep* splitting so long as not ALL squares
480 // within <r> share the SAME bin, OR we keep finding one
481 // that SWITCHED bins after the terrain change (we already
482 // know this is true for the entire rectangle or we would
483 // not have reached PreTesselate)
484 //
485 // NOTE: during tree construction, numNewBinSquares is ALWAYS
486 // non-0 for the entire map-rectangle (see NodeLayer::Update)
487 //
488 // NOTE: if <r> fully overlaps <this>, then splitting is *not*
489 // technically required whenever numRefBinSquares is zero, ie.
490 // when ALL squares in <r> changed bins in unison
491 //
492 UpdateMoveCost(nl, r, numNewBinSquares, numDifBinSquares, numClosedSquares, wantSplit, needSplit);
493
494 if ((wantSplit && Split(nl, false)) || (needSplit && Split(nl, true))) {
495 registerNode = false;
496
497 for (unsigned int i = 0; i < children.size(); i++) {
498 QTNode* cn = children[i];
499 SRectangle cr = cn->ClipRectangle(r);
500
501 cn->Tesselate(nl, cr);
502 assert(cn->GetMoveCost() != -1.0f);
503 }
504 }
505
506 if (registerNode) {
507 nl.RegisterNode(this);
508 }
509 }
510
UpdateMoveCost(const NodeLayer & nl,const SRectangle & r,unsigned int & numNewBinSquares,unsigned int & numDifBinSquares,unsigned int & numClosedSquares,bool & wantSplit,bool & needSplit)511 bool QTPFS::QTNode::UpdateMoveCost(
512 const NodeLayer& nl,
513 const SRectangle& r,
514 unsigned int& numNewBinSquares,
515 unsigned int& numDifBinSquares,
516 unsigned int& numClosedSquares,
517 bool& wantSplit,
518 bool& needSplit
519 ) {
520 const std::vector<NodeLayer::SpeedBinType>& oldSpeedBins = nl.GetOldSpeedBins();
521 const std::vector<NodeLayer::SpeedBinType>& curSpeedBins = nl.GetCurSpeedBins();
522 const std::vector<NodeLayer::SpeedModType>& oldSpeedMods = nl.GetOldSpeedMods();
523 const std::vector<NodeLayer::SpeedModType>& curSpeedMods = nl.GetCurSpeedMods();
524
525 const NodeLayer::SpeedBinType refSpeedBin = curSpeedBins[zmin() * gs->mapx + xmin()];
526
527 // <this> can either just have been merged or added as
528 // new child of split parent; in the former case we can
529 // restrict ourselves to <r> and update the sum in part
530 // (as well as checking homogeneousness just for squares
531 // in <r> with a single reference point outside it)
532 assert(moveCostAvg == -1.0f || moveCostAvg > 0.0f);
533
534 if (false && moveCostAvg > 0.0f) {
535 // just merged, so <r> is fully inside <this>
536 //
537 // the reference-square (xmin, zmin) MUST lie
538 // outside <r> when <r> does not cover <this>
539 // 100%, otherwise we would find a value of 0
540 // for numDifBinSquares in some situations
541 assert((r.x2 - r.x1) >= 0);
542 assert((r.z2 - r.z1) >= 0);
543
544 const unsigned int minx = std::max(r.x1, int(xmin()));
545 const unsigned int maxx = std::min(r.x2, int(xmax()));
546 const unsigned int minz = std::max(r.z1, int(zmin()));
547 const unsigned int maxz = std::min(r.z2, int(zmax()));
548
549 for (unsigned int hmz = minz; hmz < maxz; hmz++) {
550 for (unsigned int hmx = minx; hmx < maxx; hmx++) {
551 const unsigned int sqrIdx = hmz * gs->mapx + hmx;
552
553 const NodeLayer::SpeedBinType oldSpeedBin = oldSpeedBins[sqrIdx];
554 const NodeLayer::SpeedBinType curSpeedBin = curSpeedBins[sqrIdx];
555
556 numNewBinSquares += int(curSpeedBin != oldSpeedBin);
557 numDifBinSquares += int(curSpeedBin != refSpeedBin);
558 numClosedSquares += int(curSpeedMods[sqrIdx] <= 0);
559
560 speedModSum -= (oldSpeedMods[sqrIdx] / float(NodeLayer::MaxSpeedModTypeValue()));
561 speedModSum += (curSpeedMods[sqrIdx] / float(NodeLayer::MaxSpeedModTypeValue()));
562
563 assert(speedModSum >= 0.0f);
564 }
565 }
566 } else {
567 speedModSum = 0.0f;
568
569 for (unsigned int hmz = zmin(); hmz < zmax(); hmz++) {
570 for (unsigned int hmx = xmin(); hmx < xmax(); hmx++) {
571 const unsigned int sqrIdx = hmz * gs->mapx + hmx;
572
573 const NodeLayer::SpeedBinType oldSpeedBin = oldSpeedBins[sqrIdx];
574 const NodeLayer::SpeedBinType curSpeedBin = curSpeedBins[sqrIdx];
575
576 numNewBinSquares += int(curSpeedBin != oldSpeedBin);
577 numDifBinSquares += int(curSpeedBin != refSpeedBin);
578 numClosedSquares += int(curSpeedMods[sqrIdx] <= 0);
579
580 speedModSum += (curSpeedMods[sqrIdx] / float(NodeLayer::MaxSpeedModTypeValue()));
581 }
582 }
583 }
584
585 // (re-)calculate the average cost of this node
586 assert(speedModSum >= 0.0f);
587
588 speedModAvg = speedModSum / area();
589 moveCostAvg = (speedModAvg <= 0.001f)? QTPFS_POSITIVE_INFINITY: (1.0f / speedModAvg);
590
591 // no node can have ZERO traversal cost
592 assert(moveCostAvg > 0.0f);
593
594 wantSplit |= (numDifBinSquares > 0);
595 needSplit |= (numClosedSquares > 0 && numClosedSquares < area());
596
597 // if we are not going to tesselate this node further
598 // and there is at least one impassable square inside
599 // it, make sure the pathfinder will not pick us
600 //
601 // HACK:
602 // set the cost for *!PARTIALLY!* closed nodes to a
603 // non-infinite value since these are often created
604 // along factory exit lanes (most on non-square maps
605 // or when MIN_SIZE_X > 1 or MIN_SIZE_Z > 1), but do
606 // ensure their cost is still high enough so they get
607 // expanded only when absolutely necessary
608 //
609 // units with footprint dimensions equal to the size
610 // of a lane would otherwise be unable to find a path
611 // out of their factories
612 //
613 // this is crucial for handling the squares underneath
614 // static obstacles (eg. factories) if MIN_SIZE_* != 1
615 if (numClosedSquares > 0) {
616 if (numClosedSquares < area()) {
617 moveCostAvg = QTPFS_CLOSED_NODE_COST * (numClosedSquares / float(xsize() * xsize()));
618 } else {
619 moveCostAvg = QTPFS_POSITIVE_INFINITY;
620 }
621 }
622
623 return (wantSplit || needSplit);
624 }
625
626
627
628
629
630
631 // get the maximum number of neighbors this node
632 // can have, based on its position / size and the
633 // assumption that all neighbors are 1x1
634 //
635 // NOTE: this intentionally does not count corners
GetMaxNumNeighbors() const636 unsigned int QTPFS::QTNode::GetMaxNumNeighbors() const {
637 unsigned int n = 0;
638
639 if (xmin() > ( 0)) { n += zsize(); } // count EDGE_L ngbs
640 if (xmax() < (gs->mapx - 1)) { n += zsize(); } // count EDGE_R ngbs
641 if (zmin() > ( 0)) { n += xsize(); } // count EDGE_T ngbs
642 if (zmax() < (gs->mapy - 1)) { n += xsize(); } // count EDGE_B ngbs
643
644 return n;
645 }
646
647
648
649
650
Serialize(std::fstream & fStream,NodeLayer & nodeLayer,unsigned int * streamSize,bool readMode)651 void QTPFS::QTNode::Serialize(std::fstream& fStream, NodeLayer& nodeLayer, unsigned int* streamSize, bool readMode) {
652 // overwritten when de-serializing
653 unsigned int numChildren = QTNODE_CHILD_COUNT * (1 - int(IsLeaf()));
654
655 (*streamSize) += (2 * sizeof(unsigned int));
656 (*streamSize) += (3 * sizeof(float));
657
658 if (readMode) {
659 fStream.read(reinterpret_cast<char*>(&nodeNumber), sizeof(unsigned int));
660 fStream.read(reinterpret_cast<char*>(&numChildren), sizeof(unsigned int));
661
662 fStream.read(reinterpret_cast<char*>(&speedModAvg), sizeof(float));
663 fStream.read(reinterpret_cast<char*>(&speedModSum), sizeof(float));
664 fStream.read(reinterpret_cast<char*>(&moveCostAvg), sizeof(float));
665
666 if (numChildren > 0) {
667 // re-create child nodes
668 assert(IsLeaf());
669 Split(nodeLayer, true);
670 } else {
671 // node was a leaf in an earlier life, register it
672 nodeLayer.RegisterNode(this);
673 }
674 } else {
675 fStream.write(reinterpret_cast<const char*>(&nodeNumber), sizeof(unsigned int));
676 fStream.write(reinterpret_cast<const char*>(&numChildren), sizeof(unsigned int));
677
678 fStream.write(reinterpret_cast<const char*>(&speedModAvg), sizeof(float));
679 fStream.write(reinterpret_cast<const char*>(&speedModSum), sizeof(float));
680 fStream.write(reinterpret_cast<const char*>(&moveCostAvg), sizeof(float));
681 }
682
683 for (unsigned int i = 0; i < numChildren; i++) {
684 children[i]->Serialize(fStream, nodeLayer, streamSize, readMode);
685 }
686 }
687
GetNeighbors(const std::vector<INode * > & nodes,std::vector<INode * > & ngbs)688 unsigned int QTPFS::QTNode::GetNeighbors(const std::vector<INode*>& nodes, std::vector<INode*>& ngbs) {
689 #ifdef QTPFS_CONSERVATIVE_NEIGHBOR_CACHE_UPDATES
690 UpdateNeighborCache(nodes);
691 #endif
692
693 if (!neighbors.empty()) {
694 ngbs.clear();
695 ngbs.resize(neighbors.size());
696
697 std::copy(neighbors.begin(), neighbors.end(), ngbs.begin());
698 }
699
700 return (neighbors.size());
701 }
702
GetNeighbors(const std::vector<INode * > & nodes)703 const std::vector<QTPFS::INode*>& QTPFS::QTNode::GetNeighbors(const std::vector<INode*>& nodes) {
704 #ifdef QTPFS_CONSERVATIVE_NEIGHBOR_CACHE_UPDATES
705 UpdateNeighborCache(nodes);
706 #endif
707 return neighbors;
708 }
709
710 // this is *either* called from ::GetNeighbors when the conservative
711 // update-scheme is enabled, *or* from PM::ExecQueuedNodeLayerUpdates
712 // (never both)
UpdateNeighborCache(const std::vector<INode * > & nodes)713 bool QTPFS::QTNode::UpdateNeighborCache(const std::vector<INode*>& nodes) {
714 assert(IsLeaf());
715 assert(!nodes.empty());
716
717 if (prevMagicNum != currMagicNum) {
718 prevMagicNum = currMagicNum;
719
720 unsigned int ngbRels = 0;
721 unsigned int maxNgbs = GetMaxNumNeighbors();
722
723 // regenerate our neighbor cache
724 if (maxNgbs > 0) {
725 neighbors.clear();
726 neighbors.reserve(maxNgbs + 4);
727
728 netpoints.clear();
729 netpoints.reserve(1 + maxNgbs * QTPFS_MAX_NETPOINTS_PER_NODE_EDGE + 4);
730 // NOTE: caching ETP's breaks QTPFS_ORTHOPROJECTED_EDGE_TRANSITIONS
731 // NOTE: [0] is a reserved index and must always be valid
732 netpoints.push_back(float3());
733
734 INode* ngb = NULL;
735
736 if (xmin() > 0) {
737 const unsigned int hmx = xmin() - 1;
738
739 // walk along EDGE_L (west) neighbors
740 for (unsigned int hmz = zmin(); hmz < zmax(); ) {
741 ngb = nodes[hmz * gs->mapx + hmx];
742 hmz = ngb->zmax();
743
744 neighbors.push_back(ngb);
745
746 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
747 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngb, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
748 }
749 }
750
751 ngbRels |= REL_NGB_EDGE_L;
752 }
753 if (xmax() < static_cast<unsigned int>(gs->mapx)) {
754 const unsigned int hmx = xmax() + 0;
755
756 // walk along EDGE_R (east) neighbors
757 for (unsigned int hmz = zmin(); hmz < zmax(); ) {
758 ngb = nodes[hmz * gs->mapx + hmx];
759 hmz = ngb->zmax();
760
761 neighbors.push_back(ngb);
762
763 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
764 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngb, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
765 }
766 }
767
768 ngbRels |= REL_NGB_EDGE_R;
769 }
770
771 if (zmin() > 0) {
772 const unsigned int hmz = zmin() - 1;
773
774 // walk along EDGE_T (north) neighbors
775 for (unsigned int hmx = xmin(); hmx < xmax(); ) {
776 ngb = nodes[hmz * gs->mapx + hmx];
777 hmx = ngb->xmax();
778
779 neighbors.push_back(ngb);
780
781 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
782 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngb, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
783 }
784 }
785
786 ngbRels |= REL_NGB_EDGE_T;
787 }
788 if (zmax() < static_cast<unsigned int>(gs->mapy)) {
789 const unsigned int hmz = zmax() + 0;
790
791 // walk along EDGE_B (south) neighbors
792 for (unsigned int hmx = xmin(); hmx < xmax(); ) {
793 ngb = nodes[hmz * gs->mapx + hmx];
794 hmx = ngb->xmax();
795
796 neighbors.push_back(ngb);
797
798 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
799 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngb, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
800 }
801 }
802
803 ngbRels |= REL_NGB_EDGE_B;
804 }
805
806 #ifdef QTPFS_CORNER_CONNECTED_NODES
807 // top- and bottom-left corners
808 if ((ngbRels & REL_NGB_EDGE_L) != 0) {
809 if ((ngbRels & REL_NGB_EDGE_T) != 0) {
810 const INode* ngbL = nodes[(zmin() + 0) * gs->mapx + (xmin() - 1)];
811 const INode* ngbT = nodes[(zmin() - 1) * gs->mapx + (xmin() + 0)];
812 INode* ngbC = nodes[(zmin() - 1) * gs->mapx + (xmin() - 1)];
813
814 // VERT_TL ngb must be distinct from EDGE_L and EDGE_T ngbs
815 if (ngbC != ngbL && ngbC != ngbT) {
816 if (ngbL->AllSquaresAccessible() && ngbT->AllSquaresAccessible()) {
817 neighbors.push_back(ngbC);
818
819 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
820 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngbC, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
821 }
822 }
823 }
824 }
825 if ((ngbRels & REL_NGB_EDGE_B) != 0) {
826 const INode* ngbL = nodes[(zmax() - 1) * gs->mapx + (xmin() - 1)];
827 const INode* ngbB = nodes[(zmax() + 0) * gs->mapx + (xmin() + 0)];
828 INode* ngbC = nodes[(zmax() + 0) * gs->mapx + (xmin() - 1)];
829
830 // VERT_BL ngb must be distinct from EDGE_L and EDGE_B ngbs
831 if (ngbC != ngbL && ngbC != ngbB) {
832 if (ngbL->AllSquaresAccessible() && ngbB->AllSquaresAccessible()) {
833 neighbors.push_back(ngbC);
834
835 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
836 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngbC, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
837 }
838 }
839 }
840 }
841 }
842
843 // top- and bottom-right corners
844 if ((ngbRels & REL_NGB_EDGE_R) != 0) {
845 if ((ngbRels & REL_NGB_EDGE_T) != 0) {
846 const INode* ngbR = nodes[(zmin() + 0) * gs->mapx + (xmax() + 0)];
847 const INode* ngbT = nodes[(zmin() - 1) * gs->mapx + (xmax() - 1)];
848 INode* ngbC = nodes[(zmin() - 1) * gs->mapx + (xmax() + 0)];
849
850 // VERT_TR ngb must be distinct from EDGE_R and EDGE_T ngbs
851 if (ngbC != ngbR && ngbC != ngbT) {
852 if (ngbR->AllSquaresAccessible() && ngbT->AllSquaresAccessible()) {
853 neighbors.push_back(ngbC);
854
855 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
856 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngbC, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
857 }
858 }
859 }
860 }
861 if ((ngbRels & REL_NGB_EDGE_B) != 0) {
862 const INode* ngbR = nodes[(zmax() - 1) * gs->mapx + (xmax() + 0)];
863 const INode* ngbB = nodes[(zmax() + 0) * gs->mapx + (xmax() - 1)];
864 INode* ngbC = nodes[(zmax() + 0) * gs->mapx + (xmax() + 0)];
865
866 // VERT_BR ngb must be distinct from EDGE_R and EDGE_B ngbs
867 if (ngbC != ngbR && ngbC != ngbB) {
868 if (ngbR->AllSquaresAccessible() && ngbB->AllSquaresAccessible()) {
869 neighbors.push_back(ngbC);
870
871 for (unsigned int i = 0; i < QTPFS_MAX_NETPOINTS_PER_NODE_EDGE; i++) {
872 netpoints.push_back(INode::GetNeighborEdgeTransitionPoint(ngbC, float3(), QTPFS_NETPOINT_EDGE_SPACING_SCALE * (i + 1)));
873 }
874 }
875 }
876 }
877 }
878 #endif
879
880 // NOTE: gcc 4.7 should FINALLY define __cplusplus properly (and accept -std=c++11)
881 #if (__cplusplus >= 201103L)
882 // neighbors.shrink_to_fit();
883 // netpoints.shrink_to_fit();
884 #endif
885 }
886
887 return true;
888 }
889
890 return false;
891 }
892
893