1 /* Copyright (C) 2018 Wildfire Games.
2 * This file is part of 0 A.D.
3 *
4 * 0 A.D. is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * 0 A.D. is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "precompiled.h"
19
20 #include "simulation2/system/Component.h"
21 #include "ICmpObstructionManager.h"
22
23 #include "ICmpTerrain.h"
24 #include "ICmpPosition.h"
25
26 #include "simulation2/MessageTypes.h"
27 #include "simulation2/helpers/Geometry.h"
28 #include "simulation2/helpers/Rasterize.h"
29 #include "simulation2/helpers/Render.h"
30 #include "simulation2/helpers/Spatial.h"
31 #include "simulation2/serialization/SerializeTemplates.h"
32
33 #include "graphics/Overlay.h"
34 #include "graphics/Terrain.h"
35 #include "maths/MathUtil.h"
36 #include "ps/Profile.h"
37 #include "renderer/Scene.h"
38 #include "ps/CLogger.h"
39
40 // Externally, tags are opaque non-zero positive integers.
41 // Internally, they are tagged (by shape) indexes into shape lists.
42 // idx must be non-zero.
43 #define TAG_IS_VALID(tag) ((tag).valid())
44 #define TAG_IS_UNIT(tag) (((tag).n & 1) == 0)
45 #define TAG_IS_STATIC(tag) (((tag).n & 1) == 1)
46 #define UNIT_INDEX_TO_TAG(idx) tag_t(((idx) << 1) | 0)
47 #define STATIC_INDEX_TO_TAG(idx) tag_t(((idx) << 1) | 1)
48 #define TAG_TO_INDEX(tag) ((tag).n >> 1)
49
50 /**
51 * Internal representation of axis-aligned circular shapes for moving units
52 */
53 struct UnitShape
54 {
55 entity_id_t entity;
56 entity_pos_t x, z;
57 entity_pos_t clearance;
58 ICmpObstructionManager::flags_t flags;
59 entity_id_t group; // control group (typically the owner entity, or a formation controller entity) (units ignore collisions with others in the same group)
60 };
61
62 /**
63 * Internal representation of arbitrary-rotation static square shapes for buildings
64 */
65 struct StaticShape
66 {
67 entity_id_t entity;
68 entity_pos_t x, z; // world-space coordinates
69 CFixedVector2D u, v; // orthogonal unit vectors - axes of local coordinate space
70 entity_pos_t hw, hh; // half width/height in local coordinate space
71 ICmpObstructionManager::flags_t flags;
72 entity_id_t group;
73 entity_id_t group2;
74 };
75
76 /**
77 * Serialization helper template for UnitShape
78 */
79 struct SerializeUnitShape
80 {
81 template<typename S>
operator ()SerializeUnitShape82 void operator()(S& serialize, const char* UNUSED(name), UnitShape& value) const
83 {
84 serialize.NumberU32_Unbounded("entity", value.entity);
85 serialize.NumberFixed_Unbounded("x", value.x);
86 serialize.NumberFixed_Unbounded("z", value.z);
87 serialize.NumberFixed_Unbounded("clearance", value.clearance);
88 serialize.NumberU8_Unbounded("flags", value.flags);
89 serialize.NumberU32_Unbounded("group", value.group);
90 }
91 };
92
93 /**
94 * Serialization helper template for StaticShape
95 */
96 struct SerializeStaticShape
97 {
98 template<typename S>
operator ()SerializeStaticShape99 void operator()(S& serialize, const char* UNUSED(name), StaticShape& value) const
100 {
101 serialize.NumberU32_Unbounded("entity", value.entity);
102 serialize.NumberFixed_Unbounded("x", value.x);
103 serialize.NumberFixed_Unbounded("z", value.z);
104 serialize.NumberFixed_Unbounded("u.x", value.u.X);
105 serialize.NumberFixed_Unbounded("u.y", value.u.Y);
106 serialize.NumberFixed_Unbounded("v.x", value.v.X);
107 serialize.NumberFixed_Unbounded("v.y", value.v.Y);
108 serialize.NumberFixed_Unbounded("hw", value.hw);
109 serialize.NumberFixed_Unbounded("hh", value.hh);
110 serialize.NumberU8_Unbounded("flags", value.flags);
111 serialize.NumberU32_Unbounded("group", value.group);
112 serialize.NumberU32_Unbounded("group2", value.group2);
113 }
114 };
115
116 class CCmpObstructionManager : public ICmpObstructionManager
117 {
118 public:
ClassInit(CComponentManager & componentManager)119 static void ClassInit(CComponentManager& componentManager)
120 {
121 componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
122 }
123
124 DEFAULT_COMPONENT_ALLOCATOR(ObstructionManager)
125
126 bool m_DebugOverlayEnabled;
127 bool m_DebugOverlayDirty;
128 std::vector<SOverlayLine> m_DebugOverlayLines;
129
130 SpatialSubdivision m_UnitSubdivision;
131 SpatialSubdivision m_StaticSubdivision;
132
133 // TODO: using std::map is a bit inefficient; is there a better way to store these?
134 std::map<u32, UnitShape> m_UnitShapes;
135 std::map<u32, StaticShape> m_StaticShapes;
136 u32 m_UnitShapeNext; // next allocated id
137 u32 m_StaticShapeNext;
138
139 entity_pos_t m_MaxClearance;
140
141 bool m_PassabilityCircular;
142
143 entity_pos_t m_WorldX0;
144 entity_pos_t m_WorldZ0;
145 entity_pos_t m_WorldX1;
146 entity_pos_t m_WorldZ1;
147 u16 m_TerrainTiles;
148
GetSchema()149 static std::string GetSchema()
150 {
151 return "<a:component type='system'/><empty/>";
152 }
153
Init(const CParamNode & UNUSED (paramNode))154 virtual void Init(const CParamNode& UNUSED(paramNode))
155 {
156 m_DebugOverlayEnabled = false;
157 m_DebugOverlayDirty = true;
158
159 m_UnitShapeNext = 1;
160 m_StaticShapeNext = 1;
161
162 m_UpdateInformations.dirty = true;
163 m_UpdateInformations.globallyDirty = true;
164
165 m_PassabilityCircular = false;
166
167 m_WorldX0 = m_WorldZ0 = m_WorldX1 = m_WorldZ1 = entity_pos_t::Zero();
168 m_TerrainTiles = 0;
169
170 // Initialise with bogus values (these will get replaced when
171 // SetBounds is called)
172 ResetSubdivisions(entity_pos_t::FromInt(1024), entity_pos_t::FromInt(1024));
173 }
174
Deinit()175 virtual void Deinit()
176 {
177 }
178
179 template<typename S>
SerializeCommon(S & serialize)180 void SerializeCommon(S& serialize)
181 {
182 SerializeSpatialSubdivision()(serialize, "unit subdiv", m_UnitSubdivision);
183 SerializeSpatialSubdivision()(serialize, "static subdiv", m_StaticSubdivision);
184
185 serialize.NumberFixed_Unbounded("max clearance", m_MaxClearance);
186
187 SerializeMap<SerializeU32_Unbounded, SerializeUnitShape>()(serialize, "unit shapes", m_UnitShapes);
188 SerializeMap<SerializeU32_Unbounded, SerializeStaticShape>()(serialize, "static shapes", m_StaticShapes);
189 serialize.NumberU32_Unbounded("unit shape next", m_UnitShapeNext);
190 serialize.NumberU32_Unbounded("static shape next", m_StaticShapeNext);
191
192 serialize.Bool("circular", m_PassabilityCircular);
193
194 serialize.NumberFixed_Unbounded("world x0", m_WorldX0);
195 serialize.NumberFixed_Unbounded("world z0", m_WorldZ0);
196 serialize.NumberFixed_Unbounded("world x1", m_WorldX1);
197 serialize.NumberFixed_Unbounded("world z1", m_WorldZ1);
198 serialize.NumberU16_Unbounded("terrain tiles", m_TerrainTiles);
199 }
200
Serialize(ISerializer & serialize)201 virtual void Serialize(ISerializer& serialize)
202 {
203 // TODO: this could perhaps be optimised by not storing all the obstructions,
204 // and instead regenerating them from the other entities on Deserialize
205
206 SerializeCommon(serialize);
207 }
208
Deserialize(const CParamNode & paramNode,IDeserializer & deserialize)209 virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
210 {
211 Init(paramNode);
212
213 SerializeCommon(deserialize);
214
215 m_UpdateInformations.dirtinessGrid = Grid<u8>(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE);
216 }
217
HandleMessage(const CMessage & msg,bool UNUSED (global))218 virtual void HandleMessage(const CMessage& msg, bool UNUSED(global))
219 {
220 switch (msg.GetType())
221 {
222 case MT_RenderSubmit:
223 {
224 const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
225 RenderSubmit(msgData.collector);
226 break;
227 }
228 }
229 }
230
231 // NB: on deserialization, this function is not called after the component is reset.
232 // So anything that happens here should be safely serialized.
SetBounds(entity_pos_t x0,entity_pos_t z0,entity_pos_t x1,entity_pos_t z1)233 virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1)
234 {
235 m_WorldX0 = x0;
236 m_WorldZ0 = z0;
237 m_WorldX1 = x1;
238 m_WorldZ1 = z1;
239 MakeDirtyAll();
240
241 // Subdivision system bounds:
242 ENSURE(x0.IsZero() && z0.IsZero()); // don't bother implementing non-zero offsets yet
243 ResetSubdivisions(x1, z1);
244
245 CmpPtr<ICmpTerrain> cmpTerrain(GetSystemEntity());
246 if (!cmpTerrain)
247 return;
248
249 m_TerrainTiles = cmpTerrain->GetTilesPerSide();
250 m_UpdateInformations.dirtinessGrid = Grid<u8>(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE);
251
252 CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
253 if (cmpPathfinder)
254 m_MaxClearance = cmpPathfinder->GetMaximumClearance();
255 }
256
ResetSubdivisions(entity_pos_t x1,entity_pos_t z1)257 void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1)
258 {
259 // Use 8x8 tile subdivisions
260 // (TODO: find the optimal number instead of blindly guessing)
261 m_UnitSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE));
262 m_StaticSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE));
263
264 for (std::map<u32, UnitShape>::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it)
265 {
266 CFixedVector2D center(it->second.x, it->second.z);
267 CFixedVector2D halfSize(it->second.clearance, it->second.clearance);
268 m_UnitSubdivision.Add(it->first, center - halfSize, center + halfSize);
269 }
270
271 for (std::map<u32, StaticShape>::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it)
272 {
273 CFixedVector2D center(it->second.x, it->second.z);
274 CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(it->second.u, it->second.v, CFixedVector2D(it->second.hw, it->second.hh));
275 m_StaticSubdivision.Add(it->first, center - bbHalfSize, center + bbHalfSize);
276 }
277 }
278
AddUnitShape(entity_id_t ent,entity_pos_t x,entity_pos_t z,entity_pos_t clearance,flags_t flags,entity_id_t group)279 virtual tag_t AddUnitShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, flags_t flags, entity_id_t group)
280 {
281 UnitShape shape = { ent, x, z, clearance, flags, group };
282 u32 id = m_UnitShapeNext++;
283 m_UnitShapes[id] = shape;
284
285 m_UnitSubdivision.Add(id, CFixedVector2D(x - clearance, z - clearance), CFixedVector2D(x + clearance, z + clearance));
286
287 MakeDirtyUnit(flags, id, shape);
288
289 return UNIT_INDEX_TO_TAG(id);
290 }
291
AddStaticShape(entity_id_t ent,entity_pos_t x,entity_pos_t z,entity_angle_t a,entity_pos_t w,entity_pos_t h,flags_t flags,entity_id_t group,entity_id_t group2)292 virtual tag_t AddStaticShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h, flags_t flags, entity_id_t group, entity_id_t group2 /* = INVALID_ENTITY */)
293 {
294 fixed s, c;
295 sincos_approx(a, s, c);
296 CFixedVector2D u(c, -s);
297 CFixedVector2D v(s, c);
298
299 StaticShape shape = { ent, x, z, u, v, w/2, h/2, flags, group, group2 };
300 u32 id = m_StaticShapeNext++;
301 m_StaticShapes[id] = shape;
302
303 CFixedVector2D center(x, z);
304 CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(w/2, h/2));
305 m_StaticSubdivision.Add(id, center - bbHalfSize, center + bbHalfSize);
306
307 MakeDirtyStatic(flags, id, shape);
308
309 return STATIC_INDEX_TO_TAG(id);
310 }
311
GetUnitShapeObstruction(entity_pos_t x,entity_pos_t z,entity_pos_t clearance) const312 virtual ObstructionSquare GetUnitShapeObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t clearance) const
313 {
314 CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero());
315 CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1));
316 ObstructionSquare o = { x, z, u, v, clearance, clearance };
317 return o;
318 }
319
GetStaticShapeObstruction(entity_pos_t x,entity_pos_t z,entity_angle_t a,entity_pos_t w,entity_pos_t h) const320 virtual ObstructionSquare GetStaticShapeObstruction(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) const
321 {
322 fixed s, c;
323 sincos_approx(a, s, c);
324 CFixedVector2D u(c, -s);
325 CFixedVector2D v(s, c);
326
327 ObstructionSquare o = { x, z, u, v, w/2, h/2 };
328 return o;
329 }
330
MoveShape(tag_t tag,entity_pos_t x,entity_pos_t z,entity_angle_t a)331 virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a)
332 {
333 ENSURE(TAG_IS_VALID(tag));
334
335 if (TAG_IS_UNIT(tag))
336 {
337 UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
338
339 MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region
340
341 m_UnitSubdivision.Move(TAG_TO_INDEX(tag),
342 CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance),
343 CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance),
344 CFixedVector2D(x - shape.clearance, z - shape.clearance),
345 CFixedVector2D(x + shape.clearance, z + shape.clearance));
346
347 shape.x = x;
348 shape.z = z;
349
350 MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the new shape region
351 }
352 else
353 {
354 fixed s, c;
355 sincos_approx(a, s, c);
356 CFixedVector2D u(c, -s);
357 CFixedVector2D v(s, c);
358
359 StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)];
360
361 MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region
362
363 CFixedVector2D fromBbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh));
364 CFixedVector2D toBbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(shape.hw, shape.hh));
365 m_StaticSubdivision.Move(TAG_TO_INDEX(tag),
366 CFixedVector2D(shape.x, shape.z) - fromBbHalfSize,
367 CFixedVector2D(shape.x, shape.z) + fromBbHalfSize,
368 CFixedVector2D(x, z) - toBbHalfSize,
369 CFixedVector2D(x, z) + toBbHalfSize);
370
371 shape.x = x;
372 shape.z = z;
373 shape.u = u;
374 shape.v = v;
375
376 MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the new shape region
377 }
378 }
379
SetUnitMovingFlag(tag_t tag,bool moving)380 virtual void SetUnitMovingFlag(tag_t tag, bool moving)
381 {
382 ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag));
383
384 if (TAG_IS_UNIT(tag))
385 {
386 UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
387 if (moving)
388 shape.flags |= FLAG_MOVING;
389 else
390 shape.flags &= (flags_t)~FLAG_MOVING;
391
392 MakeDirtyDebug();
393 }
394 }
395
SetUnitControlGroup(tag_t tag,entity_id_t group)396 virtual void SetUnitControlGroup(tag_t tag, entity_id_t group)
397 {
398 ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag));
399
400 if (TAG_IS_UNIT(tag))
401 {
402 UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
403 shape.group = group;
404 }
405 }
406
SetStaticControlGroup(tag_t tag,entity_id_t group,entity_id_t group2)407 virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2)
408 {
409 ENSURE(TAG_IS_VALID(tag) && TAG_IS_STATIC(tag));
410
411 if (TAG_IS_STATIC(tag))
412 {
413 StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)];
414 shape.group = group;
415 shape.group2 = group2;
416 }
417 }
418
RemoveShape(tag_t tag)419 virtual void RemoveShape(tag_t tag)
420 {
421 ENSURE(TAG_IS_VALID(tag));
422
423 if (TAG_IS_UNIT(tag))
424 {
425 UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
426 m_UnitSubdivision.Remove(TAG_TO_INDEX(tag),
427 CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance),
428 CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance));
429
430 MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape);
431
432 m_UnitShapes.erase(TAG_TO_INDEX(tag));
433 }
434 else
435 {
436 StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)];
437
438 CFixedVector2D center(shape.x, shape.z);
439 CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh));
440 m_StaticSubdivision.Remove(TAG_TO_INDEX(tag), center - bbHalfSize, center + bbHalfSize);
441
442 MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape);
443
444 m_StaticShapes.erase(TAG_TO_INDEX(tag));
445 }
446 }
447
GetObstruction(tag_t tag) const448 virtual ObstructionSquare GetObstruction(tag_t tag) const
449 {
450 ENSURE(TAG_IS_VALID(tag));
451
452 if (TAG_IS_UNIT(tag))
453 {
454 const UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag));
455 CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero());
456 CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1));
457 ObstructionSquare o = { shape.x, shape.z, u, v, shape.clearance, shape.clearance };
458 return o;
459 }
460 else
461 {
462 const StaticShape& shape = m_StaticShapes.at(TAG_TO_INDEX(tag));
463 ObstructionSquare o = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh };
464 return o;
465 }
466 }
467
468 virtual fixed DistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const;
469
470 virtual bool TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits = false) const;
471 virtual bool TestStaticShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, std::vector<entity_id_t>* out) const;
472 virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, std::vector<entity_id_t>* out) const;
473
474 virtual void Rasterize(Grid<NavcellData>& grid, const std::vector<PathfinderPassability>& passClasses, bool fullUpdate);
475 virtual void GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector<ObstructionSquare>& squares) const;
476 virtual void GetUnitObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector<ObstructionSquare>& squares) const;
477 virtual void GetStaticObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector<ObstructionSquare>& squares) const;
478 virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector<entity_id_t>& out, const IObstructionTestFilter& filter, bool strict = false) const;
479 virtual void GetStaticObstructionsOnObstruction(const ObstructionSquare& square, std::vector<entity_id_t>& out, const IObstructionTestFilter& filter) const;
480
SetPassabilityCircular(bool enabled)481 virtual void SetPassabilityCircular(bool enabled)
482 {
483 m_PassabilityCircular = enabled;
484 MakeDirtyAll();
485
486 CMessageObstructionMapShapeChanged msg;
487 GetSimContext().GetComponentManager().BroadcastMessage(msg);
488 }
489
GetPassabilityCircular() const490 virtual bool GetPassabilityCircular() const
491 {
492 return m_PassabilityCircular;
493 }
494
SetDebugOverlay(bool enabled)495 virtual void SetDebugOverlay(bool enabled)
496 {
497 m_DebugOverlayEnabled = enabled;
498 m_DebugOverlayDirty = true;
499 if (!enabled)
500 m_DebugOverlayLines.clear();
501 }
502
503 void RenderSubmit(SceneCollector& collector);
504
UpdateInformations(GridUpdateInformation & informations)505 virtual void UpdateInformations(GridUpdateInformation& informations)
506 {
507 if (!m_UpdateInformations.dirtinessGrid.blank())
508 informations.MergeAndClear(m_UpdateInformations);
509 }
510
511 private:
512 // Dynamic updates for the long-range pathfinder
513 GridUpdateInformation m_UpdateInformations;
514 // These vectors might contain shapes that were deleted
515 std::vector<u32> m_DirtyStaticShapes;
516 std::vector<u32> m_DirtyUnitShapes;
517
518 /**
519 * Mark all previous Rasterize()d grids as dirty, and the debug display.
520 * Call this when the world bounds have changed.
521 */
MakeDirtyAll()522 void MakeDirtyAll()
523 {
524 m_UpdateInformations.dirty = true;
525 m_UpdateInformations.globallyDirty = true;
526 m_UpdateInformations.dirtinessGrid.reset();
527
528 m_DebugOverlayDirty = true;
529 }
530
531 /**
532 * Mark the debug display as dirty.
533 * Call this when nothing has changed except a unit's 'moving' flag.
534 */
MakeDirtyDebug()535 void MakeDirtyDebug()
536 {
537 m_DebugOverlayDirty = true;
538 }
539
MarkDirtinessGrid(const entity_pos_t & x,const entity_pos_t & z,const entity_pos_t & r)540 inline void MarkDirtinessGrid(const entity_pos_t& x, const entity_pos_t& z, const entity_pos_t& r)
541 {
542 MarkDirtinessGrid(x, z, CFixedVector2D(r, r));
543 }
544
MarkDirtinessGrid(const entity_pos_t & x,const entity_pos_t & z,const CFixedVector2D & hbox)545 inline void MarkDirtinessGrid(const entity_pos_t& x, const entity_pos_t& z, const CFixedVector2D& hbox)
546 {
547 ENSURE(m_UpdateInformations.dirtinessGrid.m_W == m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE &&
548 m_UpdateInformations.dirtinessGrid.m_H == m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE);
549 if (m_TerrainTiles == 0)
550 return;
551
552 u16 j0, j1, i0, i1;
553 Pathfinding::NearestNavcell(x - hbox.X, z - hbox.Y, i0, j0, m_UpdateInformations.dirtinessGrid.m_W, m_UpdateInformations.dirtinessGrid.m_H);
554 Pathfinding::NearestNavcell(x + hbox.X, z + hbox.Y, i1, j1, m_UpdateInformations.dirtinessGrid.m_W, m_UpdateInformations.dirtinessGrid.m_H);
555
556 for (int j = j0; j < j1; ++j)
557 for (int i = i0; i < i1; ++i)
558 m_UpdateInformations.dirtinessGrid.set(i, j, 1);
559 }
560
561 /**
562 * Mark all previous Rasterize()d grids as dirty, if they depend on this shape.
563 * Call this when a static shape has changed.
564 */
MakeDirtyStatic(flags_t flags,u32 index,const StaticShape & shape)565 void MakeDirtyStatic(flags_t flags, u32 index, const StaticShape& shape)
566 {
567 m_DebugOverlayDirty = true;
568
569 if (flags & (FLAG_BLOCK_PATHFINDING | FLAG_BLOCK_FOUNDATION))
570 {
571 m_UpdateInformations.dirty = true;
572
573 if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), index) == m_DirtyStaticShapes.end())
574 m_DirtyStaticShapes.push_back(index);
575
576 // All shapes overlapping the updated part of the grid should be dirtied too.
577 // We are going to invalidate the region of the grid corresponding to the modified shape plus its clearance,
578 // and we need to get the shapes whose clearance can overlap this area. So we need to extend the search area
579 // by two times the maximum clearance.
580
581 CFixedVector2D center(shape.x, shape.z);
582 CFixedVector2D hbox = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh));
583 CFixedVector2D expand(m_MaxClearance, m_MaxClearance);
584
585 std::vector<u32> staticsNear;
586 m_StaticSubdivision.GetInRange(staticsNear, center - hbox - expand*2, center + hbox + expand*2);
587 for (u32& staticId : staticsNear)
588 if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end())
589 m_DirtyStaticShapes.push_back(staticId);
590
591 std::vector<u32> unitsNear;
592 m_UnitSubdivision.GetInRange(unitsNear, center - hbox - expand*2, center + hbox + expand*2);
593 for (u32& unitId : unitsNear)
594 if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end())
595 m_DirtyUnitShapes.push_back(unitId);
596
597 MarkDirtinessGrid(shape.x, shape.z, hbox + expand);
598 }
599 }
600
601 /**
602 * Mark all previous Rasterize()d grids as dirty, if they depend on this shape.
603 * Call this when a unit shape has changed.
604 */
MakeDirtyUnit(flags_t flags,u32 index,const UnitShape & shape)605 void MakeDirtyUnit(flags_t flags, u32 index, const UnitShape& shape)
606 {
607 m_DebugOverlayDirty = true;
608
609 if (flags & (FLAG_BLOCK_PATHFINDING | FLAG_BLOCK_FOUNDATION))
610 {
611 m_UpdateInformations.dirty = true;
612
613 if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), index) == m_DirtyUnitShapes.end())
614 m_DirtyUnitShapes.push_back(index);
615
616 // All shapes overlapping the updated part of the grid should be dirtied too.
617 // We are going to invalidate the region of the grid corresponding to the modified shape plus its clearance,
618 // and we need to get the shapes whose clearance can overlap this area. So we need to extend the search area
619 // by two times the maximum clearance.
620
621 CFixedVector2D center(shape.x, shape.z);
622
623 std::vector<u32> staticsNear;
624 m_StaticSubdivision.GetNear(staticsNear, center, shape.clearance + m_MaxClearance*2);
625 for (u32& staticId : staticsNear)
626 if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end())
627 m_DirtyStaticShapes.push_back(staticId);
628
629 std::vector<u32> unitsNear;
630 m_UnitSubdivision.GetNear(unitsNear, center, shape.clearance + m_MaxClearance*2);
631 for (u32& unitId : unitsNear)
632 if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end())
633 m_DirtyUnitShapes.push_back(unitId);
634
635 MarkDirtinessGrid(shape.x, shape.z, shape.clearance + m_MaxClearance);
636 }
637 }
638
639 /**
640 * Return whether the given point is within the world bounds by at least r
641 */
IsInWorld(entity_pos_t x,entity_pos_t z,entity_pos_t r) const642 inline bool IsInWorld(entity_pos_t x, entity_pos_t z, entity_pos_t r) const
643 {
644 return (m_WorldX0+r <= x && x <= m_WorldX1-r && m_WorldZ0+r <= z && z <= m_WorldZ1-r);
645 }
646
647 /**
648 * Return whether the given point is within the world bounds
649 */
IsInWorld(const CFixedVector2D & p) const650 inline bool IsInWorld(const CFixedVector2D& p) const
651 {
652 return (m_WorldX0 <= p.X && p.X <= m_WorldX1 && m_WorldZ0 <= p.Y && p.Y <= m_WorldZ1);
653 }
654
655 void RasterizeHelper(Grid<NavcellData>& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance = fixed::Zero()) const;
656 };
657
REGISTER_COMPONENT_TYPE(ObstructionManager)658 REGISTER_COMPONENT_TYPE(ObstructionManager)
659
660 fixed CCmpObstructionManager::DistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const
661 {
662 CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), ent);
663 if (!cmpPosition || !cmpPosition->IsInWorld())
664 return fixed::FromInt(-1);
665
666 ObstructionSquare s;
667 CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), ent);
668 if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(s))
669 return (CFixedVector2D(px, pz) - cmpPosition->GetPosition2D()).Length();
670
671 return Geometry::DistanceToSquare(CFixedVector2D(px - s.x, pz - s.z), s.u, s.v, CFixedVector2D(s.hw, s.hh));
672 }
673
TestLine(const IObstructionTestFilter & filter,entity_pos_t x0,entity_pos_t z0,entity_pos_t x1,entity_pos_t z1,entity_pos_t r,bool relaxClearanceForUnits) const674 bool CCmpObstructionManager::TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits) const
675 {
676 PROFILE("TestLine");
677
678 // Check that both end points are within the world (which means the whole line must be)
679 if (!IsInWorld(x0, z0, r) || !IsInWorld(x1, z1, r))
680 return true;
681
682 CFixedVector2D posMin (std::min(x0, x1) - r, std::min(z0, z1) - r);
683 CFixedVector2D posMax (std::max(x0, x1) + r, std::max(z0, z1) + r);
684
685 // actual radius used for unit-unit collisions. If relaxClearanceForUnits, will be smaller to allow more overlap.
686 entity_pos_t unitUnitRadius = r;
687 if (relaxClearanceForUnits)
688 unitUnitRadius -= entity_pos_t::FromInt(1)/2;
689
690 std::vector<entity_id_t> unitShapes;
691 m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax);
692 for (const entity_id_t& shape : unitShapes)
693 {
694 std::map<u32, UnitShape>::const_iterator it = m_UnitShapes.find(shape);
695 ENSURE(it != m_UnitShapes.end());
696
697 if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
698 continue;
699
700 CFixedVector2D center(it->second.x, it->second.z);
701 CFixedVector2D halfSize(it->second.clearance + unitUnitRadius, it->second.clearance + unitUnitRadius);
702 if (Geometry::TestRayAASquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, halfSize))
703 return true;
704 }
705
706 std::vector<entity_id_t> staticShapes;
707 m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax);
708 for (const entity_id_t& shape : staticShapes)
709 {
710 std::map<u32, StaticShape>::const_iterator it = m_StaticShapes.find(shape);
711 ENSURE(it != m_StaticShapes.end());
712
713 if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
714 continue;
715
716 CFixedVector2D center(it->second.x, it->second.z);
717 CFixedVector2D halfSize(it->second.hw + r, it->second.hh + r);
718 if (Geometry::TestRaySquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, it->second.u, it->second.v, halfSize))
719 return true;
720 }
721
722 return false;
723 }
724
TestStaticShape(const IObstructionTestFilter & filter,entity_pos_t x,entity_pos_t z,entity_pos_t a,entity_pos_t w,entity_pos_t h,std::vector<entity_id_t> * out) const725 bool CCmpObstructionManager::TestStaticShape(const IObstructionTestFilter& filter,
726 entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h,
727 std::vector<entity_id_t>* out) const
728 {
729 PROFILE("TestStaticShape");
730
731 if (out)
732 out->clear();
733
734 fixed s, c;
735 sincos_approx(a, s, c);
736 CFixedVector2D u(c, -s);
737 CFixedVector2D v(s, c);
738 CFixedVector2D center(x, z);
739 CFixedVector2D halfSize(w/2, h/2);
740 CFixedVector2D corner1 = u.Multiply(halfSize.X) + v.Multiply(halfSize.Y);
741 CFixedVector2D corner2 = u.Multiply(halfSize.X) - v.Multiply(halfSize.Y);
742
743 // Check that all corners are within the world (which means the whole shape must be)
744 if (!IsInWorld(center + corner1) || !IsInWorld(center + corner2) ||
745 !IsInWorld(center - corner1) || !IsInWorld(center - corner2))
746 {
747 if (out)
748 out->push_back(INVALID_ENTITY); // no entity ID, so just push an arbitrary marker
749 else
750 return true;
751 }
752
753 fixed bbHalfWidth = std::max(corner1.X.Absolute(), corner2.X.Absolute());
754 fixed bbHalfHeight = std::max(corner1.Y.Absolute(), corner2.Y.Absolute());
755 CFixedVector2D posMin(x - bbHalfWidth, z - bbHalfHeight);
756 CFixedVector2D posMax(x + bbHalfWidth, z + bbHalfHeight);
757
758 std::vector<entity_id_t> unitShapes;
759 m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax);
760 for (entity_id_t& shape : unitShapes)
761 {
762 std::map<u32, UnitShape>::const_iterator it = m_UnitShapes.find(shape);
763 ENSURE(it != m_UnitShapes.end());
764
765 if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
766 continue;
767
768 CFixedVector2D center1(it->second.x, it->second.z);
769
770 if (Geometry::PointIsInSquare(center1 - center, u, v, CFixedVector2D(halfSize.X + it->second.clearance, halfSize.Y + it->second.clearance)))
771 {
772 if (out)
773 out->push_back(it->second.entity);
774 else
775 return true;
776 }
777 }
778
779 std::vector<entity_id_t> staticShapes;
780 m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax);
781 for (entity_id_t& shape : staticShapes)
782 {
783 std::map<u32, StaticShape>::const_iterator it = m_StaticShapes.find(shape);
784 ENSURE(it != m_StaticShapes.end());
785
786 if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
787 continue;
788
789 CFixedVector2D center1(it->second.x, it->second.z);
790 CFixedVector2D halfSize1(it->second.hw, it->second.hh);
791 if (Geometry::TestSquareSquare(center, u, v, halfSize, center1, it->second.u, it->second.v, halfSize1))
792 {
793 if (out)
794 out->push_back(it->second.entity);
795 else
796 return true;
797 }
798 }
799
800 if (out)
801 return !out->empty(); // collided if the list isn't empty
802 else
803 return false; // didn't collide, if we got this far
804 }
805
TestUnitShape(const IObstructionTestFilter & filter,entity_pos_t x,entity_pos_t z,entity_pos_t clearance,std::vector<entity_id_t> * out) const806 bool CCmpObstructionManager::TestUnitShape(const IObstructionTestFilter& filter,
807 entity_pos_t x, entity_pos_t z, entity_pos_t clearance,
808 std::vector<entity_id_t>* out) const
809 {
810 PROFILE("TestUnitShape");
811
812 // Check that the shape is within the world
813 if (!IsInWorld(x, z, clearance))
814 {
815 if (out)
816 out->push_back(INVALID_ENTITY); // no entity ID, so just push an arbitrary marker
817 else
818 return true;
819 }
820
821 CFixedVector2D center(x, z);
822 CFixedVector2D posMin(x - clearance, z - clearance);
823 CFixedVector2D posMax(x + clearance, z + clearance);
824
825 std::vector<entity_id_t> unitShapes;
826 m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax);
827 for (const entity_id_t& shape : unitShapes)
828 {
829 std::map<u32, UnitShape>::const_iterator it = m_UnitShapes.find(shape);
830 ENSURE(it != m_UnitShapes.end());
831
832 if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
833 continue;
834
835 entity_pos_t c1 = it->second.clearance;
836
837 if (!(
838 it->second.x + c1 < x - clearance ||
839 it->second.x - c1 > x + clearance ||
840 it->second.z + c1 < z - clearance ||
841 it->second.z - c1 > z + clearance))
842 {
843 if (out)
844 out->push_back(it->second.entity);
845 else
846 return true;
847 }
848 }
849
850 std::vector<entity_id_t> staticShapes;
851 m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax);
852 for (const entity_id_t& shape : staticShapes)
853 {
854 std::map<u32, StaticShape>::const_iterator it = m_StaticShapes.find(shape);
855 ENSURE(it != m_StaticShapes.end());
856
857 if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
858 continue;
859
860 CFixedVector2D center1(it->second.x, it->second.z);
861 if (Geometry::PointIsInSquare(center1 - center, it->second.u, it->second.v, CFixedVector2D(it->second.hw + clearance, it->second.hh + clearance)))
862 {
863 if (out)
864 out->push_back(it->second.entity);
865 else
866 return true;
867 }
868 }
869
870 if (out)
871 return !out->empty(); // collided if the list isn't empty
872 else
873 return false; // didn't collide, if we got this far
874 }
875
Rasterize(Grid<NavcellData> & grid,const std::vector<PathfinderPassability> & passClasses,bool fullUpdate)876 void CCmpObstructionManager::Rasterize(Grid<NavcellData>& grid, const std::vector<PathfinderPassability>& passClasses, bool fullUpdate)
877 {
878 PROFILE3("Rasterize Obstructions");
879
880 // Cells are only marked as blocked if the whole cell is strictly inside the shape.
881 // (That ensures the shape's geometric border is always reachable.)
882
883 // Pass classes will get shapes rasterized on them depending on their Obstruction value.
884 // Classes with another value than "pathfinding" should not use Clearance.
885
886 std::map<entity_pos_t, u16> pathfindingMasks;
887 u16 foundationMask = 0;
888 for (const PathfinderPassability& passability : passClasses)
889 {
890 switch (passability.m_Obstructions)
891 {
892 case PathfinderPassability::PATHFINDING:
893 {
894 std::map<entity_pos_t, u16>::iterator it = pathfindingMasks.find(passability.m_Clearance);
895 if (it == pathfindingMasks.end())
896 pathfindingMasks[passability.m_Clearance] = passability.m_Mask;
897 else
898 it->second |= passability.m_Mask;
899 break;
900 }
901 case PathfinderPassability::FOUNDATION:
902 foundationMask |= passability.m_Mask;
903 break;
904 default:
905 continue;
906 }
907 }
908
909 // FLAG_BLOCK_PATHFINDING and FLAG_BLOCK_FOUNDATION are the only flags taken into account by MakeDirty* functions,
910 // so they should be the only ones rasterized using with the help of m_Dirty*Shapes vectors.
911
912 for (auto& maskPair : pathfindingMasks)
913 RasterizeHelper(grid, FLAG_BLOCK_PATHFINDING, fullUpdate, maskPair.second, maskPair.first);
914
915 RasterizeHelper(grid, FLAG_BLOCK_FOUNDATION, fullUpdate, foundationMask);
916
917 m_DirtyStaticShapes.clear();
918 m_DirtyUnitShapes.clear();
919 }
920
RasterizeHelper(Grid<NavcellData> & grid,ICmpObstructionManager::flags_t requireMask,bool fullUpdate,pass_class_t appliedMask,entity_pos_t clearance) const921 void CCmpObstructionManager::RasterizeHelper(Grid<NavcellData>& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance) const
922 {
923 for (auto& pair : m_StaticShapes)
924 {
925 const StaticShape& shape = pair.second;
926 if (!(shape.flags & requireMask))
927 continue;
928
929 if (!fullUpdate && std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), pair.first) == m_DirtyStaticShapes.end())
930 continue;
931
932 // TODO: it might be nice to rasterize with rounded corners for large 'expand' values.
933 ObstructionSquare square = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh };
934 SimRasterize::Spans spans;
935 SimRasterize::RasterizeRectWithClearance(spans, square, clearance, Pathfinding::NAVCELL_SIZE);
936 for (SimRasterize::Span& span : spans)
937 {
938 i16 j = Clamp(span.j, (i16)0, (i16)(grid.m_H-1));
939 i16 i0 = std::max(span.i0, (i16)0);
940 i16 i1 = std::min(span.i1, (i16)grid.m_W);
941
942 for (i16 i = i0; i < i1; ++i)
943 grid.set(i, j, grid.get(i, j) | appliedMask);
944 }
945 }
946
947 for (auto& pair : m_UnitShapes)
948 {
949 if (!(pair.second.flags & requireMask))
950 continue;
951
952 if (!fullUpdate && std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), pair.first) == m_DirtyUnitShapes.end())
953 continue;
954
955 CFixedVector2D center(pair.second.x, pair.second.z);
956 entity_pos_t r = pair.second.clearance + clearance;
957
958 u16 i0, j0, i1, j1;
959 Pathfinding::NearestNavcell(center.X - r, center.Y - r, i0, j0, grid.m_W, grid.m_H);
960 Pathfinding::NearestNavcell(center.X + r, center.Y + r, i1, j1, grid.m_W, grid.m_H);
961 for (u16 j = j0+1; j < j1; ++j)
962 for (u16 i = i0+1; i < i1; ++i)
963 grid.set(i, j, grid.get(i, j) | appliedMask);
964 }
965 }
966
GetObstructionsInRange(const IObstructionTestFilter & filter,entity_pos_t x0,entity_pos_t z0,entity_pos_t x1,entity_pos_t z1,std::vector<ObstructionSquare> & squares) const967 void CCmpObstructionManager::GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector<ObstructionSquare>& squares) const
968 {
969 GetUnitObstructionsInRange(filter, x0, z0, x1, z1, squares);
970 GetStaticObstructionsInRange(filter, x0, z0, x1, z1, squares);
971 }
972
GetUnitObstructionsInRange(const IObstructionTestFilter & filter,entity_pos_t x0,entity_pos_t z0,entity_pos_t x1,entity_pos_t z1,std::vector<ObstructionSquare> & squares) const973 void CCmpObstructionManager::GetUnitObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector<ObstructionSquare>& squares) const
974 {
975 PROFILE("GetObstructionsInRange");
976
977 ENSURE(x0 <= x1 && z0 <= z1);
978
979 std::vector<entity_id_t> unitShapes;
980 m_UnitSubdivision.GetInRange(unitShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1));
981 for (entity_id_t& unitShape : unitShapes)
982 {
983 std::map<u32, UnitShape>::const_iterator it = m_UnitShapes.find(unitShape);
984 ENSURE(it != m_UnitShapes.end());
985
986 if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
987 continue;
988
989 entity_pos_t c = it->second.clearance;
990
991 // Skip this object if it's completely outside the requested range
992 if (it->second.x + c < x0 || it->second.x - c > x1 || it->second.z + c < z0 || it->second.z - c > z1)
993 continue;
994
995 CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero());
996 CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1));
997 squares.emplace_back(ObstructionSquare{ it->second.x, it->second.z, u, v, c, c });
998 }
999 }
1000
GetStaticObstructionsInRange(const IObstructionTestFilter & filter,entity_pos_t x0,entity_pos_t z0,entity_pos_t x1,entity_pos_t z1,std::vector<ObstructionSquare> & squares) const1001 void CCmpObstructionManager::GetStaticObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector<ObstructionSquare>& squares) const
1002 {
1003 PROFILE("GetObstructionsInRange");
1004
1005 ENSURE(x0 <= x1 && z0 <= z1);
1006
1007 std::vector<entity_id_t> staticShapes;
1008 m_StaticSubdivision.GetInRange(staticShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1));
1009 for (entity_id_t& staticShape : staticShapes)
1010 {
1011 std::map<u32, StaticShape>::const_iterator it = m_StaticShapes.find(staticShape);
1012 ENSURE(it != m_StaticShapes.end());
1013
1014 if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
1015 continue;
1016
1017 entity_pos_t r = it->second.hw + it->second.hh; // overestimate the max dist of an edge from the center
1018
1019 // Skip this object if its overestimated bounding box is completely outside the requested range
1020 if (it->second.x + r < x0 || it->second.x - r > x1 || it->second.z + r < z0 || it->second.z - r > z1)
1021 continue;
1022
1023 // TODO: maybe we should use Geometry::GetHalfBoundingBox to be more precise?
1024
1025 squares.emplace_back(ObstructionSquare{ it->second.x, it->second.z, it->second.u, it->second.v, it->second.hw, it->second.hh });
1026 }
1027 }
1028
GetUnitsOnObstruction(const ObstructionSquare & square,std::vector<entity_id_t> & out,const IObstructionTestFilter & filter,bool strict) const1029 void CCmpObstructionManager::GetUnitsOnObstruction(const ObstructionSquare& square, std::vector<entity_id_t>& out, const IObstructionTestFilter& filter, bool strict) const
1030 {
1031 PROFILE("GetUnitsOnObstruction");
1032
1033 // In order to avoid getting units on impassable cells, we want to find all
1034 // units subject to the RasterizeRectWithClearance of the building's shape with the
1035 // unit's clearance covers the navcell the unit is on.
1036
1037 std::vector<entity_id_t> unitShapes;
1038 CFixedVector2D center(square.x, square.z);
1039 CFixedVector2D expandedBox =
1040 Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh)) +
1041 CFixedVector2D(m_MaxClearance, m_MaxClearance);
1042 m_UnitSubdivision.GetInRange(unitShapes, center - expandedBox, center + expandedBox);
1043
1044 std::map<entity_pos_t, SimRasterize::Spans> rasterizedRects;
1045
1046 for (const u32& unitShape : unitShapes)
1047 {
1048 std::map<u32, UnitShape>::const_iterator it = m_UnitShapes.find(unitShape);
1049 ENSURE(it != m_UnitShapes.end());
1050
1051 const UnitShape& shape = it->second;
1052
1053 if (!filter.TestShape(UNIT_INDEX_TO_TAG(unitShape), shape.flags, shape.group, INVALID_ENTITY))
1054 continue;
1055
1056 if (rasterizedRects.find(shape.clearance) == rasterizedRects.end())
1057 {
1058 // The rasterization is an approximation of the real shapes.
1059 // Depending on your use, you may want to be more or less strict on the rasterization,
1060 // ie this may either return some units that aren't actually on the shape (if strict is set)
1061 // or this may not return some units that are on the shape (if strict is not set).
1062 // Foundations need to be non-strict, as otherwise it sometimes detects the builder units
1063 // as being on the shape, so it orders them away.
1064 SimRasterize::Spans& newSpans = rasterizedRects[shape.clearance];
1065 if (strict)
1066 SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance, Pathfinding::NAVCELL_SIZE);
1067 else
1068 SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance-Pathfinding::CLEARANCE_EXTENSION_RADIUS, Pathfinding::NAVCELL_SIZE);
1069 }
1070
1071 SimRasterize::Spans& spans = rasterizedRects[shape.clearance];
1072
1073 // Check whether the unit's center is on a navcell that's in
1074 // any of the spans
1075
1076 u16 i = (shape.x / Pathfinding::NAVCELL_SIZE).ToInt_RoundToNegInfinity();
1077 u16 j = (shape.z / Pathfinding::NAVCELL_SIZE).ToInt_RoundToNegInfinity();
1078
1079 for (const SimRasterize::Span& span : spans)
1080 {
1081 if (j == span.j && span.i0 <= i && i < span.i1)
1082 {
1083 out.push_back(shape.entity);
1084 break;
1085 }
1086 }
1087 }
1088 }
1089
GetStaticObstructionsOnObstruction(const ObstructionSquare & square,std::vector<entity_id_t> & out,const IObstructionTestFilter & filter) const1090 void CCmpObstructionManager::GetStaticObstructionsOnObstruction(const ObstructionSquare& square, std::vector<entity_id_t>& out, const IObstructionTestFilter& filter) const
1091 {
1092 PROFILE("GetStaticObstructionsOnObstruction");
1093
1094 std::vector<entity_id_t> staticShapes;
1095 CFixedVector2D center(square.x, square.z);
1096 CFixedVector2D expandedBox = Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh));
1097 m_StaticSubdivision.GetInRange(staticShapes, center - expandedBox, center + expandedBox);
1098
1099 for (const u32& staticShape : staticShapes)
1100 {
1101 std::map<u32, StaticShape>::const_iterator it = m_StaticShapes.find(staticShape);
1102 ENSURE(it != m_StaticShapes.end());
1103
1104 const StaticShape& shape = it->second;
1105
1106 if (!filter.TestShape(STATIC_INDEX_TO_TAG(staticShape), shape.flags, shape.group, shape.group2))
1107 continue;
1108
1109 if (Geometry::TestSquareSquare(
1110 center,
1111 square.u,
1112 square.v,
1113 CFixedVector2D(square.hw, square.hh),
1114 CFixedVector2D(shape.x, shape.z),
1115 shape.u,
1116 shape.v,
1117 CFixedVector2D(shape.hw, shape.hh)))
1118 {
1119 out.push_back(shape.entity);
1120 }
1121 }
1122 }
1123
RenderSubmit(SceneCollector & collector)1124 void CCmpObstructionManager::RenderSubmit(SceneCollector& collector)
1125 {
1126 if (!m_DebugOverlayEnabled)
1127 return;
1128
1129 CColor defaultColor(0, 0, 1, 1);
1130 CColor movingColor(1, 0, 1, 1);
1131 CColor boundsColor(1, 1, 0, 1);
1132
1133 // If the shapes have changed, then regenerate all the overlays
1134 if (m_DebugOverlayDirty)
1135 {
1136 m_DebugOverlayLines.clear();
1137
1138 m_DebugOverlayLines.push_back(SOverlayLine());
1139 m_DebugOverlayLines.back().m_Color = boundsColor;
1140 SimRender::ConstructSquareOnGround(GetSimContext(),
1141 (m_WorldX0+m_WorldX1).ToFloat()/2.f, (m_WorldZ0+m_WorldZ1).ToFloat()/2.f,
1142 (m_WorldX1-m_WorldX0).ToFloat(), (m_WorldZ1-m_WorldZ0).ToFloat(),
1143 0, m_DebugOverlayLines.back(), true);
1144
1145 for (std::map<u32, UnitShape>::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it)
1146 {
1147 m_DebugOverlayLines.push_back(SOverlayLine());
1148 m_DebugOverlayLines.back().m_Color = ((it->second.flags & FLAG_MOVING) ? movingColor : defaultColor);
1149 SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.clearance.ToFloat()*2, it->second.clearance.ToFloat()*2, 0, m_DebugOverlayLines.back(), true);
1150 }
1151
1152 for (std::map<u32, StaticShape>::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it)
1153 {
1154 m_DebugOverlayLines.push_back(SOverlayLine());
1155 m_DebugOverlayLines.back().m_Color = defaultColor;
1156 float a = atan2f(it->second.v.X.ToFloat(), it->second.v.Y.ToFloat());
1157 SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.hw.ToFloat()*2, it->second.hh.ToFloat()*2, a, m_DebugOverlayLines.back(), true);
1158 }
1159
1160 m_DebugOverlayDirty = false;
1161 }
1162
1163 for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i)
1164 collector.Submit(&m_DebugOverlayLines[i]);
1165 }
1166