1 /* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
2
3 #include <algorithm>
4
5 #include "QuadField.h"
6 #include "Sim/Misc/CollisionVolume.h"
7 #include "Sim/Misc/GlobalSynced.h"
8 #include "Sim/Misc/GlobalConstants.h"
9 #include "Sim/Misc/TeamHandler.h"
10 #include "Sim/Features/Feature.h"
11 #include "Sim/Units/Unit.h"
12 #include "Sim/Projectiles/Projectile.h"
13 #include "System/creg/STL_List.h"
14
15 #define CELL_IDX_X(wpx) Clamp(int((wpx) / quadSizeX), 0, numQuadsX - 1)
16 #define CELL_IDX_Z(wpz) Clamp(int((wpz) / quadSizeZ), 0, numQuadsZ - 1)
17
18 CR_BIND(CQuadField, (1, 1))
19 CR_REG_METADATA(CQuadField, (
20 CR_MEMBER(baseQuads),
21 CR_MEMBER(tempQuads),
22 CR_MEMBER(numQuadsX),
23 CR_MEMBER(numQuadsZ),
24 CR_MEMBER(quadSizeX),
25 CR_MEMBER(quadSizeZ)
26 ))
27
28 CR_BIND(CQuadField::Quad, )
29 CR_REG_METADATA_SUB(CQuadField, Quad, (
30 CR_MEMBER(units),
31 CR_MEMBER(teamUnits),
32 CR_MEMBER(features),
33 CR_MEMBER(projectiles)
34 ))
35
36 CQuadField* quadField = NULL;
37
38
39
Resize(unsigned int nqx,unsigned int nqz)40 void CQuadField::Resize(unsigned int nqx, unsigned int nqz)
41 {
42 CQuadField* oldQuadField = quadField;
43 CQuadField* newQuadField = new CQuadField(nqx, nqz);
44
45 quadField = NULL;
46
47 for (int zq = 0; zq < oldQuadField->GetNumQuadsZ(); zq++) {
48 for (int xq = 0; xq < oldQuadField->GetNumQuadsX(); xq++) {
49 const CQuadField::Quad& quad = oldQuadField->GetQuadAt(xq, zq);
50
51 // COPY the object lists because the Remove* functions modify them
52 // NOTE:
53 // teamUnits is updated internally by RemoveUnit and MovedUnit
54 //
55 // if a unit exists in multiple quads in the old field, it will
56 // be removed from all of them and there is no danger of double
57 // re-insertion (important if new grid has higher resolution)
58 const std::list<CUnit* > units = quad.units;
59 const std::list<CFeature* > features = quad.features;
60 const std::list<CProjectile*> projectiles = quad.projectiles;
61
62 for (std::list<CUnit*>::const_iterator it = units.begin(); it != units.end(); ++it) {
63 oldQuadField->RemoveUnit(*it);
64 newQuadField->MovedUnit(*it); // handles addition
65 }
66
67 for (std::list<CFeature*>::const_iterator it = features.begin(); it != features.end(); ++it) {
68 oldQuadField->RemoveFeature(*it);
69 newQuadField->AddFeature(*it);
70 }
71
72 for (std::list<CProjectile*>::const_iterator it = projectiles.begin(); it != projectiles.end(); ++it) {
73 oldQuadField->RemoveProjectile(*it);
74 newQuadField->AddProjectile(*it);
75 }
76 }
77 }
78
79 quadField = newQuadField;
80
81 // do this last so pointer is never dangling
82 delete oldQuadField;
83 }
84
85
86
Quad()87 CQuadField::Quad::Quad() : teamUnits(teamHandler->ActiveAllyTeams())
88 {
89 }
90
CQuadField(unsigned int nqx,unsigned int nqz)91 CQuadField::CQuadField(unsigned int nqx, unsigned int nqz)
92 {
93 numQuadsX = nqx;
94 numQuadsZ = nqz;
95 quadSizeX = (gs->mapx * SQUARE_SIZE) / numQuadsX;
96 quadSizeZ = (gs->mapy * SQUARE_SIZE) / numQuadsZ;
97
98 assert(numQuadsX >= 1);
99 assert(numQuadsZ >= 1);
100 // square cells only
101 assert(quadSizeX == quadSizeZ);
102
103 // Without the temporary, std::max takes address of NUM_TEMP_QUADS
104 // if it isn't inlined, forcing NUM_TEMP_QUADS to be defined.
105 const int numTempQuads = NUM_TEMP_QUADS;
106
107 baseQuads.resize(numQuadsX * numQuadsZ);
108 tempQuads.resize(std::max(numTempQuads, numQuadsX * numQuadsZ));
109 }
110
~CQuadField()111 CQuadField::~CQuadField()
112 {
113 baseQuads.clear();
114 tempQuads.clear();
115 }
116
117
GetQuads(float3 pos,float radius) const118 std::vector<int> CQuadField::GetQuads(float3 pos, float radius) const
119 {
120 pos.ClampInBounds();
121 pos.AssertNaNs();
122
123 std::vector<int> ret;
124
125 // qsx and qsz are always equal
126 const float maxSqLength = (radius + quadSizeX * 0.72f) * (radius + quadSizeZ * 0.72f);
127
128 const int maxx = std::min((int(pos.x + radius)) / quadSizeX + 1, numQuadsX - 1);
129 const int maxz = std::min((int(pos.z + radius)) / quadSizeZ + 1, numQuadsZ - 1);
130
131 const int minx = std::max((int(pos.x - radius)) / quadSizeX, 0);
132 const int minz = std::max((int(pos.z - radius)) / quadSizeZ, 0);
133
134 if (maxz < minz || maxx < minx) {
135 return ret;
136 }
137
138 ret.reserve((maxz - minz) * (maxx - minx));
139
140 for (int z = minz; z <= maxz; ++z) {
141 for (int x = minx; x <= maxx; ++x) {
142 if ((pos - float3(x * quadSizeX + quadSizeX * 0.5f, 0, z * quadSizeZ + quadSizeZ * 0.5f)).SqLength2D() < maxSqLength) {
143 ret.push_back(z * numQuadsX + x);
144 }
145 }
146 }
147
148 return ret;
149 }
150
151
GetQuads(float3 pos,float radius,int * & begQuad,int * & endQuad) const152 unsigned int CQuadField::GetQuads(float3 pos, float radius, int*& begQuad, int*& endQuad) const
153 {
154 pos.ClampInBounds();
155 pos.AssertNaNs();
156
157 assert(begQuad == &tempQuads[0]);
158 assert(endQuad == &tempQuads[0]);
159
160 const int maxx = std::min((int(pos.x + radius)) / quadSizeX + 1, numQuadsX - 1);
161 const int maxz = std::min((int(pos.z + radius)) / quadSizeZ + 1, numQuadsZ - 1);
162
163 const int minx = std::max((int(pos.x - radius)) / quadSizeX, 0);
164 const int minz = std::max((int(pos.z - radius)) / quadSizeZ, 0);
165
166 if (maxz < minz || maxx < minx) {
167 return 0;
168 }
169
170 // qsx and qsz are always equal
171 const float maxSqLength = (radius + quadSizeX * 0.72f) * (radius + quadSizeZ * 0.72f);
172
173 for (int z = minz; z <= maxz; ++z) {
174 for (int x = minx; x <= maxx; ++x) {
175 const float3 quadCenterPos = float3(x * quadSizeX + quadSizeX * 0.5f, 0, z * quadSizeZ + quadSizeZ * 0.5f);
176
177 if ((pos - quadCenterPos).SqLength2D() < maxSqLength) {
178 *endQuad = z * numQuadsX + x; ++endQuad;
179 }
180 }
181 }
182
183 return (endQuad - begQuad);
184 }
185
186
187
GetUnits(const float3 & pos,float radius)188 std::vector<CUnit*> CQuadField::GetUnits(const float3& pos, float radius)
189 {
190 const int tempNum = gs->tempNum++;
191
192 int* begQuad = &tempQuads[0];
193 int* endQuad = &tempQuads[0];
194
195 GetQuads(pos, radius, begQuad, endQuad);
196
197 std::vector<CUnit*> units;
198 std::list<CUnit*>::iterator ui;
199
200 for (int* a = begQuad; a != endQuad; ++a) {
201 Quad& quad = baseQuads[*a];
202
203 for (ui = quad.units.begin(); ui != quad.units.end(); ++ui) {
204 if ((*ui)->tempNum == tempNum)
205 continue;
206
207 (*ui)->tempNum = tempNum;
208 units.push_back(*ui);
209 }
210 }
211
212 return units;
213 }
214
GetUnitsExact(const float3 & pos,float radius,bool spherical)215 std::vector<CUnit*> CQuadField::GetUnitsExact(const float3& pos, float radius, bool spherical)
216 {
217 const int tempNum = gs->tempNum++;
218
219 int* begQuad = &tempQuads[0];
220 int* endQuad = &tempQuads[0];
221
222 GetQuads(pos, radius, begQuad, endQuad);
223
224 std::vector<CUnit*> units;
225 std::list<CUnit*>::iterator ui;
226
227 for (int* a = begQuad; a != endQuad; ++a) {
228 Quad& quad = baseQuads[*a];
229
230 for (ui = quad.units.begin(); ui != quad.units.end(); ++ui) {
231 if ((*ui)->tempNum == tempNum)
232 continue;
233
234 const float totRad = radius + (*ui)->radius;
235 const float totRadSq = totRad * totRad;
236 const float posUnitDstSq = spherical?
237 pos.SqDistance((*ui)->midPos):
238 pos.SqDistance2D((*ui)->midPos);
239
240 if (posUnitDstSq >= totRadSq)
241 continue;
242
243 (*ui)->tempNum = tempNum;
244 units.push_back(*ui);
245 }
246 }
247
248 return units;
249 }
250
GetUnitsExact(const float3 & mins,const float3 & maxs)251 std::vector<CUnit*> CQuadField::GetUnitsExact(const float3& mins, const float3& maxs)
252 {
253 const std::vector<int>& quads = GetQuadsRectangle(mins, maxs);
254 const int tempNum = gs->tempNum++;
255
256 std::vector<CUnit*> units;
257 std::vector<int>::const_iterator qi;
258
259 for (qi = quads.begin(); qi != quads.end(); ++qi) {
260 std::list<CUnit*>& quadUnits = baseQuads[*qi].units;
261 std::list<CUnit*>::iterator ui;
262
263 for (ui = quadUnits.begin(); ui != quadUnits.end(); ++ui) {
264 CUnit* unit = *ui;
265 const float3& pos = unit->midPos;
266
267 if (unit->tempNum == tempNum) { continue; }
268 if (pos.x < mins.x || pos.x > maxs.x) { continue; }
269 if (pos.z < mins.z || pos.z > maxs.z) { continue; }
270
271 unit->tempNum = tempNum;
272 units.push_back(unit);
273 }
274 }
275
276 return units;
277 }
278
279
280
GetQuadsOnRay(float3 start,float3 dir,float length,int * & begQuad,int * & endQuad)281 unsigned int CQuadField::GetQuadsOnRay(float3 start, float3 dir, float length, int*& begQuad, int*& endQuad)
282 {
283 assert(!math::isnan(start.x));
284 assert(!math::isnan(start.y));
285 assert(!math::isnan(start.z));
286 assert(!math::isnan(dir.x));
287 assert(!math::isnan(dir.y));
288 assert(!math::isnan(dir.z));
289 assert(begQuad == NULL);
290 assert(endQuad == NULL);
291
292 begQuad = &tempQuads[0];
293 endQuad = &tempQuads[0];
294
295 if (start.x < 1) {
296 if (dir.x == 0) {
297 dir.x = 0.00001f;
298 }
299 start = start + dir * ((1 - start.x) / dir.x);
300 }
301 if (start.x > gs->mapx * SQUARE_SIZE - 1) {
302 if (dir.x == 0) {
303 dir.x = 0.00001f;
304 }
305 start = start + dir * ((gs->mapx * SQUARE_SIZE - 1 - start.x) / dir.x);
306 }
307 if (start.z < 1) {
308 if (dir.z == 0) {
309 dir.z = 0.00001f;
310 }
311 start = start + dir * ((1 - start.z) / dir.z);
312 }
313 if (start.z > gs->mapy * SQUARE_SIZE - 1) {
314 if (dir.z == 0) {
315 dir.z = 0.00001f;
316 }
317 start = start + dir * ((gs->mapy * SQUARE_SIZE - 1 - start.z) / dir.z);
318 }
319
320 if (start.x < 1) {
321 start.x = 1;
322 }
323 if (start.x > gs->mapx * SQUARE_SIZE - 1) {
324 start.x = gs->mapx * SQUARE_SIZE - 1;
325 }
326 if (start.z < 1) {
327 start.z = 1;
328 }
329 if (start.z > gs->mapy * SQUARE_SIZE - 1) {
330 start.z = gs->mapy * SQUARE_SIZE - 1;
331 }
332
333 float3 to = start + (dir * length);
334
335 if (to.x < 1) {
336 to = to - dir * ((to.x - 1) / dir.x);
337 }
338 if (to.x > gs->mapx * SQUARE_SIZE - 1) {
339 to = to - dir * ((to.x - gs->mapx * SQUARE_SIZE + 1) / dir.x);
340 }
341 if (to.z < 1){
342 to= to - dir * ((to.z - 1) / dir.z);
343 }
344 if (to.z > gs->mapy * SQUARE_SIZE - 1) {
345 to= to - dir * ((to.z - gs->mapy * SQUARE_SIZE + 1) / dir.z);
346 }
347 // these 4 shouldnt be needed, but sometimes we seem to get strange enough
348 // values that rounding errors throw us outside the map
349 if (to.x < 1) {
350 to.x = 1;
351 }
352 if (to.x > gs->mapx * SQUARE_SIZE - 1) {
353 to.x = gs->mapx * SQUARE_SIZE - 1;
354 }
355 if (to.z < 1) {
356 to.z = 1;
357 }
358 if (to.z > gs->mapy * SQUARE_SIZE - 1) {
359 to.z = gs->mapy * SQUARE_SIZE - 1;
360 }
361
362 const float dx = to.x - start.x;
363 const float dz = to.z - start.z;
364 float xp = start.x;
365 float zp = start.z;
366
367 const float invQuadSizeX = 1.0f / quadSizeX;
368 const float invQuadSizeZ = 1.0f / quadSizeZ;
369
370 if ((math::floor(start.x * invQuadSizeX) == math::floor(to.x * invQuadSizeX)) &&
371 (math::floor(start.z * invQuadSizeZ) == math::floor(to.z * invQuadSizeZ)))
372 {
373 *endQuad = ((int(start.x * invQuadSizeX)) + (int(start.z * invQuadSizeZ)) * numQuadsX);
374 ++endQuad;
375 } else if (math::floor(start.x * invQuadSizeX) == math::floor(to.x * invQuadSizeX)) {
376 const int first = (int)(start.x * invQuadSizeX) + ((int)(start.z * invQuadSizeZ) * numQuadsX);
377 const int last = (int)(to.x * invQuadSizeX) + ((int)(to.z * invQuadSizeZ) * numQuadsX);
378
379 if (dz > 0) {
380 for (int a = first; a <= last; a += numQuadsX) {
381 *endQuad = a; ++endQuad;
382 }
383 } else {
384 for(int a = first; a >= last; a -= numQuadsX) {
385 *endQuad = a; ++endQuad;
386 }
387 }
388 } else if (math::floor(start.z * invQuadSizeZ) == math::floor(to.z * invQuadSizeZ)) {
389 const int first = (int)(start.x * invQuadSizeX) + ((int)(start.z * invQuadSizeZ) * numQuadsX);
390 const int last = (int)(to.x * invQuadSizeX) + ((int)(to.z * invQuadSizeZ) * numQuadsX);
391
392 if (dx > 0) {
393 for (int a = first; a <= last; a++) {
394 *endQuad = a; ++endQuad;
395 }
396 } else {
397 for (int a = first; a >= last; a--) {
398 *endQuad = a; ++endQuad;
399 }
400 }
401 } else {
402 float xn, zn;
403 bool keepgoing = true;
404
405 for (unsigned int i = 0; i < tempQuads.size() && keepgoing; i++) {
406 *endQuad = ((int)(zp * invQuadSizeZ) * numQuadsX) + (int)(xp * invQuadSizeX);
407 ++endQuad;
408
409 if (dx > 0) {
410 xn = (math::floor(xp * invQuadSizeX) * quadSizeX + quadSizeX - xp) / dx;
411 } else {
412 xn = (math::floor(xp * invQuadSizeX) * quadSizeX - xp) / dx;
413 }
414 if (dz > 0) {
415 zn = (math::floor(zp * invQuadSizeZ) * quadSizeZ + quadSizeZ - zp) / dz;
416 } else {
417 zn = (math::floor(zp * invQuadSizeZ) * quadSizeZ - zp) / dz;
418 }
419
420 if (xn < zn) {
421 xp += (xn + 0.0001f) * dx;
422 zp += (xn + 0.0001f) * dz;
423 } else {
424 xp += (zn + 0.0001f) * dx;
425 zp += (zn + 0.0001f) * dz;
426 }
427
428 keepgoing =
429 (math::fabs(xp - start.x) < math::fabs(to.x - start.x)) &&
430 (math::fabs(zp - start.z) < math::fabs(to.z - start.z));
431 }
432 }
433
434 return (endQuad - begQuad);
435 }
436
437
438
MovedUnit(CUnit * unit)439 void CQuadField::MovedUnit(CUnit* unit)
440 {
441 const std::vector<int>& newQuads = GetQuads(unit->pos, unit->radius);
442
443 // compare if the quads have changed, if not stop here
444 if (newQuads.size() == unit->quads.size()) {
445 if (std::equal(newQuads.begin(), newQuads.end(), unit->quads.begin())) {
446 return;
447 }
448 }
449
450 std::vector<int>::const_iterator qi;
451 for (qi = unit->quads.begin(); qi != unit->quads.end(); ++qi) {
452 std::list<CUnit*>& quadUnits = baseQuads[*qi].units;
453 std::list<CUnit*>& quadAllyUnits = baseQuads[*qi].teamUnits[unit->allyteam];
454 std::list<CUnit*>::iterator ui;
455
456 ui = std::find(quadUnits.begin(), quadUnits.end(), unit);
457 if (ui != quadUnits.end())
458 quadUnits.erase(ui);
459
460 ui = std::find(quadAllyUnits.begin(), quadAllyUnits.end(), unit);
461 if (ui != quadAllyUnits.end())
462 quadAllyUnits.erase(ui);
463 }
464
465 for (qi = newQuads.begin(); qi != newQuads.end(); ++qi) {
466 baseQuads[*qi].units.push_front(unit);
467 baseQuads[*qi].teamUnits[unit->allyteam].push_front(unit);
468 }
469 unit->quads = newQuads;
470 }
471
RemoveUnit(CUnit * unit)472 void CQuadField::RemoveUnit(CUnit* unit)
473 {
474 std::vector<int>::const_iterator qi;
475 for (qi = unit->quads.begin(); qi != unit->quads.end(); ++qi) {
476 std::list<CUnit*>& quadUnits = baseQuads[*qi].units;
477 std::list<CUnit*>& quadAllyUnits = baseQuads[*qi].teamUnits[unit->allyteam];
478 std::list<CUnit*>::iterator ui;
479
480 ui = std::find(quadUnits.begin(), quadUnits.end(), unit);
481 if (ui != quadUnits.end())
482 quadUnits.erase(ui);
483
484 ui = std::find(quadAllyUnits.begin(), quadAllyUnits.end(), unit);
485 if (ui != quadAllyUnits.end())
486 quadAllyUnits.erase(ui);
487 }
488 unit->quads.clear();
489 }
490
491
492
AddFeature(CFeature * feature)493 void CQuadField::AddFeature(CFeature* feature)
494 {
495 const std::vector<int>& newQuads = GetQuads(feature->pos, feature->radius);
496
497 std::vector<int>::const_iterator qi;
498 for (qi = newQuads.begin(); qi != newQuads.end(); ++qi) {
499 baseQuads[*qi].features.push_front(feature);
500 }
501 }
502
RemoveFeature(CFeature * feature)503 void CQuadField::RemoveFeature(CFeature* feature)
504 {
505 const std::vector<int>& quads = GetQuads(feature->pos, feature->radius);
506
507 std::vector<int>::const_iterator qi;
508 for (qi = quads.begin(); qi != quads.end(); ++qi) {
509 baseQuads[*qi].features.remove(feature);
510 }
511
512 #ifdef DEBUG_QUADFIELD
513 for (int x = 0; x < numQuadsX; x++) {
514 for (int z = 0; z < numQuadsZ; z++) {
515 const Quad& q = baseQuads[z * numQuadsX + x];
516 const std::list<CFeature*>& f = q.features;
517
518 std::list<CFeature*>::const_iterator fIt;
519
520 for (fIt = f.begin(); fIt != f.end(); ++fIt) {
521 assert((*fIt) != feature);
522 }
523 }
524 }
525 #endif
526 }
527
528
529
MovedProjectile(CProjectile * p)530 void CQuadField::MovedProjectile(CProjectile* p)
531 {
532 if (!p->synced)
533 return;
534 // hit-scan projectiles do NOT move!
535 if (p->hitscan)
536 return;
537
538 const CProjectile::QuadFieldCellData& qfcd = p->GetQuadFieldCellData();
539
540 const int2& oldCellCoors = qfcd.GetCoor(0);
541 const int2 newCellCoors = {
542 Clamp(int(p->pos.x / quadSizeX), 0, numQuadsX - 1),
543 Clamp(int(p->pos.z / quadSizeZ), 0, numQuadsZ - 1)
544 };
545
546 if (newCellCoors != oldCellCoors) {
547 RemoveProjectile(p);
548 AddProjectile(p);
549 }
550 }
551
AddProjectile(CProjectile * p)552 void CQuadField::AddProjectile(CProjectile* p)
553 {
554 assert(p->synced);
555
556 CProjectile::QuadFieldCellData qfcd;
557
558 typedef CQuadField::Quad Cell;
559 typedef std::list<CProjectile*> List;
560
561 if (p->hitscan) {
562 // all coordinates always map to a valid quad
563 qfcd.SetCoor(0, int2(CELL_IDX_X(p->pos.x ), CELL_IDX_Z(p->pos.z )));
564 qfcd.SetCoor(1, int2(CELL_IDX_X(p->pos.x + p->speed.x * 0.5f), CELL_IDX_Z(p->pos.z + p->speed.z * 0.5f)));
565 qfcd.SetCoor(2, int2(CELL_IDX_X(p->pos.x + p->speed.x ), CELL_IDX_Z(p->pos.z + p->speed.z )));
566
567 Cell& cell = baseQuads[numQuadsX * qfcd.GetCoor(0).y + qfcd.GetCoor(0).x];
568 List& list = cell.projectiles;
569
570 // projectiles are point-objects so they exist
571 // only in a single cell EXCEPT hit-scan types
572 qfcd.SetIter(0, list.insert(list.end(), p));
573
574 for (unsigned int n = 1; n < 3; n++) {
575 Cell& ncell = baseQuads[numQuadsX * qfcd.GetCoor(n).y + qfcd.GetCoor(n).x];
576 List& nlist = ncell.projectiles;
577
578 // prevent possible double insertions (into the same quad-list)
579 // if case p->speed is not large enough to reach adjacent quads
580 if (qfcd.GetCoor(n) != qfcd.GetCoor(n - 1)) {
581 qfcd.SetIter(n, nlist.insert(nlist.end(), p));
582 } else {
583 qfcd.SetIter(n, nlist.end());
584 }
585 }
586 } else {
587 qfcd.SetCoor(0, int2(CELL_IDX_X(p->pos.x), CELL_IDX_Z(p->pos.z)));
588
589 Cell& cell = baseQuads[numQuadsX * qfcd.GetCoor(0).y + qfcd.GetCoor(0).x];
590 List& list = cell.projectiles;
591
592 qfcd.SetIter(0, list.insert(list.end(), p));
593 }
594
595 p->SetQuadFieldCellData(qfcd);
596 }
597
RemoveProjectile(CProjectile * p)598 void CQuadField::RemoveProjectile(CProjectile* p)
599 {
600 assert(p->synced);
601
602 CProjectile::QuadFieldCellData& qfcd = p->GetQuadFieldCellData();
603
604 typedef CQuadField::Quad Cell;
605 typedef std::list<CProjectile*> List;
606
607 if (p->hitscan) {
608 for (unsigned int n = 0; n < 3; n++) {
609 Cell& cell = baseQuads[numQuadsX * qfcd.GetCoor(n).y + qfcd.GetCoor(n).x];
610 List& list = cell.projectiles;
611
612 if (qfcd.GetIter(n) != list.end()) {
613 // this is O(1) instead of O(n) and crucially
614 // important for projectiles, but less clean
615 list.erase(qfcd.GetIter(n));
616 }
617
618 qfcd.SetIter(n, list.end());
619 }
620 } else {
621 Cell& cell = baseQuads[numQuadsX * qfcd.GetCoor(0).y + qfcd.GetCoor(0).x];
622 List& list = cell.projectiles;
623
624 assert(qfcd.GetIter(0) != list.end());
625
626 list.erase(qfcd.GetIter(0));
627 qfcd.SetIter(0, list.end());
628 }
629 }
630
631
632
GetFeaturesExact(const float3 & pos,float radius)633 std::vector<CFeature*> CQuadField::GetFeaturesExact(const float3& pos, float radius)
634 {
635 const std::vector<int>& quads = GetQuads(pos, radius);
636 const int tempNum = gs->tempNum++;
637
638 std::vector<CFeature*> features;
639 std::vector<int>::const_iterator qi;
640 std::list<CFeature*>::iterator fi;
641
642 for (qi = quads.begin(); qi != quads.end(); ++qi) {
643 for (fi = baseQuads[*qi].features.begin(); fi != baseQuads[*qi].features.end(); ++fi) {
644 if ((*fi)->tempNum == tempNum) { continue; }
645 if (pos.SqDistance((*fi)->midPos) >= Square(radius + (*fi)->radius)) { continue; }
646
647 (*fi)->tempNum = tempNum;
648 features.push_back(*fi);
649 }
650 }
651
652 return features;
653 }
654
GetFeaturesExact(const float3 & pos,float radius,bool spherical)655 std::vector<CFeature*> CQuadField::GetFeaturesExact(const float3& pos, float radius, bool spherical)
656 {
657 const std::vector<int>& quads = GetQuads(pos, radius);
658 const int tempNum = gs->tempNum++;
659
660 std::vector<CFeature*> features;
661 std::vector<int>::const_iterator qi;
662 std::list<CFeature*>::iterator fi;
663 const float totRadSq = radius * radius;
664
665 for (qi = quads.begin(); qi != quads.end(); ++qi) {
666 for (fi = baseQuads[*qi].features.begin(); fi != baseQuads[*qi].features.end(); ++fi) {
667
668 if ((*fi)->tempNum == tempNum) { continue; }
669 if ((spherical ?
670 (pos - (*fi)->midPos).SqLength() :
671 (pos - (*fi)->midPos).SqLength2D()) >= totRadSq) { continue; }
672
673 (*fi)->tempNum = tempNum;
674 features.push_back(*fi);
675 }
676 }
677
678 return features;
679 }
680
GetFeaturesExact(const float3 & mins,const float3 & maxs)681 std::vector<CFeature*> CQuadField::GetFeaturesExact(const float3& mins, const float3& maxs)
682 {
683 const std::vector<int>& quads = GetQuadsRectangle(mins, maxs);
684 const int tempNum = gs->tempNum++;
685
686 std::vector<CFeature*> features;
687 std::vector<int>::const_iterator qi;
688 std::list<CFeature*>::iterator fi;
689
690 for (qi = quads.begin(); qi != quads.end(); ++qi) {
691 std::list<CFeature*>& quadFeatures = baseQuads[*qi].features;
692
693 for (fi = quadFeatures.begin(); fi != quadFeatures.end(); ++fi) {
694 CFeature* feature = *fi;
695 const float3& pos = feature->midPos;
696
697 if (feature->tempNum == tempNum) { continue; }
698 if (pos.x < mins.x || pos.x > maxs.x) { continue; }
699 if (pos.z < mins.z || pos.z > maxs.z) { continue; }
700
701 feature->tempNum = tempNum;
702 features.push_back(feature);
703 }
704 }
705
706 return features;
707 }
708
709
710
GetProjectilesExact(const float3 & pos,float radius)711 std::vector<CProjectile*> CQuadField::GetProjectilesExact(const float3& pos, float radius)
712 {
713 const std::vector<int>& quads = GetQuads(pos, radius);
714
715 std::vector<CProjectile*> projectiles;
716 std::vector<int>::const_iterator qi;
717 std::list<CProjectile*>::iterator pi;
718
719 for (qi = quads.begin(); qi != quads.end(); ++qi) {
720 std::list<CProjectile*>& quadProjectiles = baseQuads[*qi].projectiles;
721
722 for (pi = quadProjectiles.begin(); pi != quadProjectiles.end(); ++pi) {
723 if ((pos - (*pi)->pos).SqLength() >= Square(radius + (*pi)->radius)) {
724 continue;
725 }
726
727 projectiles.push_back(*pi);
728 }
729 }
730
731 return projectiles;
732 }
733
GetProjectilesExact(const float3 & mins,const float3 & maxs)734 std::vector<CProjectile*> CQuadField::GetProjectilesExact(const float3& mins, const float3& maxs)
735 {
736 const std::vector<int>& quads = GetQuadsRectangle(mins, maxs);
737
738 std::vector<CProjectile*> projectiles;
739 std::vector<int>::const_iterator qi;
740 std::list<CProjectile*>::iterator pi;
741
742 for (qi = quads.begin(); qi != quads.end(); ++qi) {
743 std::list<CProjectile*>& quadProjectiles = baseQuads[*qi].projectiles;
744
745 for (pi = quadProjectiles.begin(); pi != quadProjectiles.end(); ++pi) {
746 CProjectile* projectile = *pi;
747 const float3& pos = projectile->pos;
748
749 if (pos.x < mins.x || pos.x > maxs.x) { continue; }
750 if (pos.z < mins.z || pos.z > maxs.z) { continue; }
751
752 projectiles.push_back(projectile);
753 }
754 }
755
756 return projectiles;
757 }
758
759
760
GetSolidsExact(const float3 & pos,const float radius,const unsigned int physicalStateBits,const unsigned int collisionStateBits)761 std::vector<CSolidObject*> CQuadField::GetSolidsExact(
762 const float3& pos,
763 const float radius,
764 const unsigned int physicalStateBits,
765 const unsigned int collisionStateBits
766 ) {
767 const std::vector<int>& quads = GetQuads(pos, radius);
768 const int tempNum = gs->tempNum++;
769
770 std::vector<CSolidObject*> solids;
771 std::vector<int>::const_iterator qi;
772
773 std::list<CUnit*>::iterator ui;
774 std::list<CFeature*>::iterator fi;
775
776 for (qi = quads.begin(); qi != quads.end(); ++qi) {
777 for (ui = baseQuads[*qi].units.begin(); ui != baseQuads[*qi].units.end(); ++ui) {
778 CUnit* u = *ui;
779
780 if (u->tempNum == tempNum)
781 continue;
782 if (!u->HasPhysicalStateBit(physicalStateBits))
783 continue;
784 if (!u->HasCollidableStateBit(collisionStateBits))
785 continue;
786 if ((pos - u->midPos).SqLength() >= Square(radius + u->radius))
787 continue;
788
789 u->tempNum = tempNum;
790 solids.push_back(u);
791 }
792
793 for (fi = baseQuads[*qi].features.begin(); fi != baseQuads[*qi].features.end(); ++fi) {
794 CFeature* f = *fi;
795
796 if (f->tempNum == tempNum)
797 continue;
798 if (!f->HasPhysicalStateBit(physicalStateBits))
799 continue;
800 if (!f->HasCollidableStateBit(collisionStateBits))
801 continue;
802 if ((pos - f->midPos).SqLength() >= Square(radius + f->radius))
803 continue;
804
805 f->tempNum = tempNum;
806 solids.push_back(f);
807 }
808 }
809
810 return solids;
811 }
812
813
814
GetQuadsRectangle(const float3 & pos1,const float3 & pos2) const815 std::vector<int> CQuadField::GetQuadsRectangle(const float3& pos1, const float3& pos2) const
816 {
817 assert(!math::isnan(pos1.x));
818 assert(!math::isnan(pos1.y));
819 assert(!math::isnan(pos1.z));
820 assert(!math::isnan(pos2.x));
821 assert(!math::isnan(pos2.y));
822 assert(!math::isnan(pos2.z));
823
824 std::vector<int> ret;
825
826 const int maxx = std::max(0, std::min((int(pos2.x)) / quadSizeX + 1, numQuadsX - 1));
827 const int maxz = std::max(0, std::min((int(pos2.z)) / quadSizeZ + 1, numQuadsZ - 1));
828
829 const int minx = std::max(0, std::min((int(pos1.x)) / quadSizeX, numQuadsX - 1));
830 const int minz = std::max(0, std::min((int(pos1.z)) / quadSizeZ, numQuadsZ - 1));
831
832 if (maxz < minz || maxx < minx)
833 return ret;
834
835 ret.reserve((maxz - minz) * (maxx - minx));
836
837 for (int z = minz; z <= maxz; ++z) {
838 for (int x = minx; x <= maxx; ++x) {
839 ret.push_back(z * numQuadsX + x);
840 }
841 }
842
843 return ret;
844 }
845
846
847 // optimization specifically for projectile collisions
GetUnitsAndFeaturesColVol(const float3 & pos,const float radius,std::vector<CUnit * > & units,std::vector<CFeature * > & features,unsigned int * numUnitsPtr,unsigned int * numFeaturesPtr)848 void CQuadField::GetUnitsAndFeaturesColVol(
849 const float3& pos,
850 const float radius,
851 std::vector<CUnit*>& units,
852 std::vector<CFeature*>& features,
853 unsigned int* numUnitsPtr,
854 unsigned int* numFeaturesPtr
855 ) {
856 const int tempNum = gs->tempNum++;
857
858 // start counting from the previous object-cache sizes
859 unsigned int numUnits = (numUnitsPtr == NULL)? 0: (*numUnitsPtr);
860 unsigned int numFeatures = (numFeaturesPtr == NULL)? 0: (*numFeaturesPtr);
861
862 int* begQuad = &tempQuads[0];
863 int* endQuad = &tempQuads[0];
864
865 // bail early if caches are already full
866 if (numUnits >= units.size())
867 return;
868 if (numFeatures >= features.size())
869 return;
870
871 assert(numUnits == 0 || units[numUnits] == NULL);
872 assert(numFeatures == 0 || features[numFeatures] == NULL);
873
874 GetQuads(pos, radius, begQuad, endQuad);
875
876 std::list<CUnit*>::const_iterator ui;
877 std::list<CFeature*>::const_iterator fi;
878
879 for (int* a = begQuad; a != endQuad; ++a) {
880 const Quad& quad = baseQuads[*a];
881
882 for (ui = quad.units.begin(); ui != quad.units.end(); ++ui) {
883 CUnit* u = *ui;
884
885 // prevent double adding
886 if (u->tempNum == tempNum)
887 continue;
888
889 const auto* colvol = u->collisionVolume;
890 const float totRad = radius + colvol->GetBoundingRadius();
891
892 if (pos.SqDistance(colvol->GetWorldSpacePos(u)) >= (totRad * totRad))
893 continue;
894
895 assert(numUnits < units.size());
896
897 if (numUnits < units.size()) {
898 u->tempNum = tempNum;
899 units[numUnits++] = u;
900 }
901 }
902
903 for (fi = quad.features.begin(); fi != quad.features.end(); ++fi) {
904 CFeature* f = *fi;
905
906 // prevent double adding
907 if (f->tempNum == tempNum)
908 continue;
909
910 const auto* colvol = f->collisionVolume;
911 const float totRad = radius + colvol->GetBoundingRadius();
912
913 if (pos.SqDistance(colvol->GetWorldSpacePos(f)) >= (totRad * totRad))
914 continue;
915
916 assert(numFeatures < features.size());
917
918 if (numFeatures < features.size()) {
919 f->tempNum = tempNum;
920 features[numFeatures++] = f;
921 }
922 }
923 }
924
925 assert(numUnits < units.size());
926 assert(numFeatures < features.size());
927
928 // set end-of-list sentinels
929 if (numUnits < units.size())
930 units[numUnits] = NULL;
931 if (numFeatures < features.size())
932 features[numFeatures] = NULL;
933
934 if (numUnitsPtr != NULL) { *numUnitsPtr = numUnits; }
935 if (numFeaturesPtr != NULL) { *numFeaturesPtr = numFeatures; }
936 }
937
938