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