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 "ICmpRangeManager.h"
22 :
23 : #include "ICmpTerrain.h"
24 : #include "simulation2/system/EntityMap.h"
25 : #include "simulation2/MessageTypes.h"
26 : #include "simulation2/components/ICmpFogging.h"
27 : #include "simulation2/components/ICmpMirage.h"
28 : #include "simulation2/components/ICmpOwnership.h"
29 : #include "simulation2/components/ICmpPosition.h"
30 : #include "simulation2/components/ICmpObstructionManager.h"
31 : #include "simulation2/components/ICmpTerritoryManager.h"
32 : #include "simulation2/components/ICmpVisibility.h"
33 : #include "simulation2/components/ICmpVision.h"
34 : #include "simulation2/components/ICmpWaterManager.h"
35 : #include "simulation2/helpers/Los.h"
36 : #include "simulation2/helpers/MapEdgeTiles.h"
37 : #include "simulation2/helpers/Render.h"
38 : #include "simulation2/helpers/Spatial.h"
39 : #include "simulation2/serialization/SerializedTypes.h"
40 :
41 : #include "graphics/Overlay.h"
42 : #include "lib/timer.h"
43 : #include "ps/CLogger.h"
44 : #include "ps/Profile.h"
45 : #include "renderer/Scene.h"
46 :
47 : #define DEBUG_RANGE_MANAGER_BOUNDS 0
48 :
49 : namespace
50 : {
51 : /**
52 : * How many LOS vertices to have per region.
53 : * LOS regions are used to keep track of units.
54 : */
55 : constexpr int LOS_REGION_RATIO = 8;
56 :
57 : /**
58 : * Tolerance for parabolic range calculations.
59 : * TODO C++20: change this to constexpr by fixing CFixed with std::is_constant_evaluated
60 : */
61 1 : const fixed PARABOLIC_RANGE_TOLERANCE = fixed::FromInt(1)/2;
62 :
63 : /**
64 : * Convert an owner ID (-1 = unowned, 0 = gaia, 1..30 = players)
65 : * into a 32-bit mask for quick set-membership tests.
66 : */
67 175 : u32 CalcOwnerMask(player_id_t owner)
68 : {
69 175 : if (owner >= -1 && owner < 31)
70 175 : return 1 << (1+owner);
71 : else
72 0 : return 0; // owner was invalid
73 : }
74 :
75 : /**
76 : * Returns LOS mask for given player.
77 : */
78 0 : u32 CalcPlayerLosMask(player_id_t player)
79 : {
80 0 : if (player > 0 && player <= 16)
81 0 : return (u32)LosState::MASK << (2*(player-1));
82 0 : return 0;
83 : }
84 :
85 : /**
86 : * Returns shared LOS mask for given list of players.
87 : */
88 0 : u32 CalcSharedLosMask(std::vector<player_id_t> players)
89 : {
90 0 : u32 playerMask = 0;
91 0 : for (size_t i = 0; i < players.size(); i++)
92 0 : playerMask |= CalcPlayerLosMask(players[i]);
93 :
94 0 : return playerMask;
95 : }
96 :
97 : /**
98 : * Add/remove a player to/from mask, which is a 1-bit mask representing a list of players.
99 : * Returns true if the mask is modified.
100 : */
101 0 : bool SetPlayerSharedDirtyVisibilityBit(u16& mask, player_id_t player, bool enable)
102 : {
103 0 : if (player <= 0 || player > 16)
104 0 : return false;
105 :
106 0 : u16 oldMask = mask;
107 :
108 0 : if (enable)
109 0 : mask |= (0x1 << (player - 1));
110 : else
111 0 : mask &= ~(0x1 << (player - 1));
112 :
113 0 : return oldMask != mask;
114 : }
115 :
116 : /**
117 : * Computes the 2-bit visibility for one player, given the total 32-bit visibilities
118 : */
119 0 : LosVisibility GetPlayerVisibility(u32 visibilities, player_id_t player)
120 : {
121 0 : if (player > 0 && player <= 16)
122 0 : return static_cast<LosVisibility>( (visibilities >> (2 *(player-1))) & 0x3 );
123 0 : return LosVisibility::HIDDEN;
124 : }
125 :
126 : /**
127 : * Test whether the visibility is dirty for a given LoS region and a given player
128 : */
129 0 : bool IsVisibilityDirty(u16 dirty, player_id_t player)
130 : {
131 0 : if (player > 0 && player <= 16)
132 0 : return (dirty >> (player - 1)) & 0x1;
133 0 : return false;
134 : }
135 :
136 : /**
137 : * Test whether a player share this vision
138 : */
139 0 : bool HasVisionSharing(u16 visionSharing, player_id_t player)
140 : {
141 0 : return (visionSharing & (1 << (player - 1))) != 0;
142 : }
143 :
144 : /**
145 : * Computes the shared vision mask for the player
146 : */
147 0 : u16 CalcVisionSharingMask(player_id_t player)
148 : {
149 0 : return 1 << (player-1);
150 : }
151 :
152 : /**
153 : * Representation of a range query.
154 : */
155 26 : struct Query
156 : {
157 : std::vector<entity_id_t> lastMatch;
158 : CEntityHandle source; // TODO: this could crash if an entity is destroyed while a Query is still referencing it
159 : entity_pos_t minRange;
160 : entity_pos_t maxRange;
161 : entity_pos_t yOrigin; // Used for parabolas only.
162 : u32 ownersMask;
163 : i32 interface;
164 : u8 flagsMask;
165 : bool enabled;
166 : bool parabolic;
167 : bool accountForSize; // If true, the query accounts for unit sizes, otherwise it treats all entities as points.
168 : };
169 :
170 : /**
171 : * Checks whether v is in a parabolic range of (0,0,0)
172 : * The highest point of the paraboloid is (0,range/2,0)
173 : * and the circle of distance 'range' around (0,0,0) on height y=0 is part of the paraboloid
174 : * This equates to computing f(x, z) = y = -(xx + zz)/(2*range) + range/2 > 0,
175 : * or alternatively sqrt(xx+zz) <= sqrt(range^2 - 2range*y).
176 : *
177 : * Avoids sqrting and overflowing.
178 : */
179 0 : static bool InParabolicRange(CFixedVector3D v, fixed range)
180 : {
181 0 : u64 xx = SQUARE_U64_FIXED(v.X); // xx <= 2^62
182 0 : u64 zz = SQUARE_U64_FIXED(v.Z);
183 0 : i64 d2 = (xx + zz) >> 1; // d2 <= 2^62 (no overflow)
184 :
185 0 : i32 y = v.Y.GetInternalValue();
186 0 : i32 c = range.GetInternalValue();
187 0 : i32 c_2 = c >> 1;
188 :
189 0 : i64 c2 = MUL_I64_I32_I32(c_2 - y, c);
190 :
191 0 : return d2 <= c2;
192 : }
193 :
194 0 : struct EntityParabolicRangeOutline
195 : {
196 : entity_id_t source;
197 : CFixedVector3D position;
198 : entity_pos_t range;
199 : std::vector<entity_pos_t> outline;
200 : };
201 :
202 1 : static std::map<entity_id_t, EntityParabolicRangeOutline> ParabolicRangesOutlines;
203 :
204 : /**
205 : * Representation of an entity, with the data needed for queries.
206 : */
207 : enum FlagMasks
208 : {
209 : // flags used for queries
210 : None = 0x00,
211 : Normal = 0x01,
212 : Injured = 0x02,
213 : AllQuery = Normal | Injured,
214 :
215 : // 0x04 reserved for future use
216 :
217 : // general flags
218 : InWorld = 0x08,
219 : RetainInFog = 0x10,
220 : RevealShore = 0x20,
221 : ScriptedVisibility = 0x40,
222 : SharedVision = 0x80
223 : };
224 :
225 : struct EntityData
226 : {
227 3 : EntityData() :
228 : visibilities(0), size(0), visionSharing(0),
229 3 : owner(-1), flags(FlagMasks::Normal)
230 3 : { }
231 : entity_pos_t x, z;
232 : entity_pos_t visionRange;
233 : u32 visibilities; // 2-bit visibility, per player
234 : u32 size;
235 : u16 visionSharing; // 1-bit per player
236 : i8 owner;
237 : u8 flags; // See the FlagMasks enum
238 :
239 : template<int mask>
240 6265 : inline bool HasFlag() const { return (flags & mask) != 0; }
241 :
242 : template<int mask>
243 1041 : inline void SetFlag(bool val) { flags = val ? (flags | mask) : (flags & ~mask); }
244 :
245 0 : inline void SetFlag(u8 mask, bool val) { flags = val ? (flags | mask) : (flags & ~mask); }
246 : };
247 :
248 : static_assert(sizeof(EntityData) == 24);
249 :
250 : /**
251 : * Functor for sorting entities by distance from a source point.
252 : * It must only be passed entities that are in 'entities'
253 : * and are currently in the world.
254 : */
255 : class EntityDistanceOrdering
256 : {
257 : public:
258 13 : EntityDistanceOrdering(const EntityMap<EntityData>& entities, const CFixedVector2D& source) :
259 13 : m_EntityData(entities), m_Source(source)
260 : {
261 13 : }
262 :
263 : EntityDistanceOrdering(const EntityDistanceOrdering& entity) = default;
264 :
265 0 : bool operator()(entity_id_t a, entity_id_t b) const
266 : {
267 0 : const EntityData& da = m_EntityData.find(a)->second;
268 0 : const EntityData& db = m_EntityData.find(b)->second;
269 0 : CFixedVector2D vecA = CFixedVector2D(da.x, da.z) - m_Source;
270 0 : CFixedVector2D vecB = CFixedVector2D(db.x, db.z) - m_Source;
271 0 : return (vecA.CompareLength(vecB) < 0);
272 : }
273 :
274 : const EntityMap<EntityData>& m_EntityData;
275 : CFixedVector2D m_Source;
276 :
277 : private:
278 : EntityDistanceOrdering& operator=(const EntityDistanceOrdering&);
279 : };
280 : } // anonymous namespace
281 :
282 : /**
283 : * Serialization helper template for Query
284 : */
285 : template<>
286 : struct SerializeHelper<Query>
287 : {
288 : template<typename S>
289 0 : void Common(S& serialize, const char* UNUSED(name), Serialize::qualify<S, Query> value)
290 : {
291 0 : serialize.NumberFixed_Unbounded("min range", value.minRange);
292 0 : serialize.NumberFixed_Unbounded("max range", value.maxRange);
293 0 : serialize.NumberFixed_Unbounded("yOrigin", value.yOrigin);
294 0 : serialize.NumberU32_Unbounded("owners mask", value.ownersMask);
295 0 : serialize.NumberI32_Unbounded("interface", value.interface);
296 0 : Serializer(serialize, "last match", value.lastMatch);
297 0 : serialize.NumberU8_Unbounded("flagsMask", value.flagsMask);
298 0 : serialize.Bool("enabled", value.enabled);
299 0 : serialize.Bool("parabolic",value.parabolic);
300 0 : serialize.Bool("account for size",value.accountForSize);
301 0 : }
302 :
303 0 : void operator()(ISerializer& serialize, const char* name, Query& value, const CSimContext& UNUSED(context))
304 : {
305 0 : Common(serialize, name, value);
306 :
307 0 : uint32_t id = value.source.GetId();
308 0 : serialize.NumberU32_Unbounded("source", id);
309 0 : }
310 :
311 0 : void operator()(IDeserializer& deserialize, const char* name, Query& value, const CSimContext& context)
312 : {
313 0 : Common(deserialize, name, value);
314 :
315 : uint32_t id;
316 0 : deserialize.NumberU32_Unbounded("source", id);
317 0 : value.source = context.GetComponentManager().LookupEntityHandle(id, true);
318 : // the referenced entity might not have been deserialized yet,
319 : // so tell LookupEntityHandle to allocate the handle if necessary
320 0 : }
321 : };
322 :
323 : /**
324 : * Serialization helper template for EntityData
325 : */
326 : template<>
327 : struct SerializeHelper<EntityData>
328 : {
329 : template<typename S>
330 0 : void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify<S, EntityData> value)
331 : {
332 0 : serialize.NumberFixed_Unbounded("x", value.x);
333 0 : serialize.NumberFixed_Unbounded("z", value.z);
334 0 : serialize.NumberFixed_Unbounded("vision", value.visionRange);
335 0 : serialize.NumberU32_Unbounded("visibilities", value.visibilities);
336 0 : serialize.NumberU32_Unbounded("size", value.size);
337 0 : serialize.NumberU16_Unbounded("vision sharing", value.visionSharing);
338 0 : serialize.NumberI8_Unbounded("owner", value.owner);
339 0 : serialize.NumberU8_Unbounded("flags", value.flags);
340 0 : }
341 : };
342 :
343 : /**
344 : * Range manager implementation.
345 : * Maintains a list of all entities (and their positions and owners), which is used for
346 : * queries.
347 : *
348 : * LOS implementation is based on the model described in GPG2.
349 : * (TODO: would be nice to make it cleverer, so e.g. mountains and walls
350 : * can block vision)
351 : */
352 18 : class CCmpRangeManager final : public ICmpRangeManager
353 : {
354 : public:
355 116 : static void ClassInit(CComponentManager& componentManager)
356 : {
357 116 : componentManager.SubscribeGloballyToMessageType(MT_Create);
358 116 : componentManager.SubscribeGloballyToMessageType(MT_PositionChanged);
359 116 : componentManager.SubscribeGloballyToMessageType(MT_OwnershipChanged);
360 116 : componentManager.SubscribeGloballyToMessageType(MT_Destroy);
361 116 : componentManager.SubscribeGloballyToMessageType(MT_VisionRangeChanged);
362 116 : componentManager.SubscribeGloballyToMessageType(MT_VisionSharingChanged);
363 :
364 116 : componentManager.SubscribeToMessageType(MT_Deserialized);
365 116 : componentManager.SubscribeToMessageType(MT_Update);
366 116 : componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
367 116 : }
368 :
369 12 : DEFAULT_COMPONENT_ALLOCATOR(RangeManager)
370 :
371 : bool m_DebugOverlayEnabled;
372 : bool m_DebugOverlayDirty;
373 : std::vector<SOverlayLine> m_DebugOverlayLines;
374 :
375 : // Deserialization flag. A lot of different functions are called by Deserialize()
376 : // and we don't want to pass isDeserializing bool arguments to all of them...
377 : bool m_Deserializing;
378 :
379 : // World bounds (entities are expected to be within this range)
380 : entity_pos_t m_WorldX0;
381 : entity_pos_t m_WorldZ0;
382 : entity_pos_t m_WorldX1;
383 : entity_pos_t m_WorldZ1;
384 :
385 : // Range query state:
386 : tag_t m_QueryNext; // next allocated id
387 : std::map<tag_t, Query> m_Queries;
388 : EntityMap<EntityData> m_EntityData;
389 :
390 : FastSpatialSubdivision m_Subdivision; // spatial index of m_EntityData
391 : std::vector<entity_id_t> m_SubdivisionResults;
392 :
393 : // LOS state:
394 : static const player_id_t MAX_LOS_PLAYER_ID = 16;
395 :
396 : using LosRegion = std::pair<u16, u16>;
397 :
398 : std::array<bool, MAX_LOS_PLAYER_ID+2> m_LosRevealAll;
399 : bool m_LosCircular;
400 : i32 m_LosVerticesPerSide;
401 :
402 : // Cache for visibility tracking
403 : i32 m_LosRegionsPerSide;
404 : bool m_GlobalVisibilityUpdate;
405 : std::array<bool, MAX_LOS_PLAYER_ID> m_GlobalPlayerVisibilityUpdate;
406 : Grid<u16> m_DirtyVisibility;
407 : Grid<std::set<entity_id_t>> m_LosRegions;
408 : // List of entities that must be updated, regardless of the status of their tile
409 : std::vector<entity_id_t> m_ModifiedEntities;
410 :
411 : // Counts of units seeing vertex, per vertex, per player (starting with player 0).
412 : // Use u16 to avoid overflows when we have very large (but not infeasibly large) numbers
413 : // of units in a very small area.
414 : // (Note we use vertexes, not tiles, to better match the renderer.)
415 : // Lazily constructed when it's needed, to save memory in smaller games.
416 : std::array<Grid<u16>, MAX_LOS_PLAYER_ID> m_LosPlayerCounts;
417 :
418 : // 2-bit LosState per player, starting with player 1 (not 0!) up to player MAX_LOS_PLAYER_ID (inclusive)
419 : Grid<u32> m_LosState;
420 :
421 : // Special static visibility data for the "reveal whole map" mode
422 : // (TODO: this is usually a waste of memory)
423 : Grid<u32> m_LosStateRevealed;
424 :
425 : // Shared LOS masks, one per player.
426 : std::array<u32, MAX_LOS_PLAYER_ID+2> m_SharedLosMasks;
427 : // Shared dirty visibility masks, one per player.
428 : std::array<u16, MAX_LOS_PLAYER_ID+2> m_SharedDirtyVisibilityMasks;
429 :
430 : // Cache explored vertices per player (not serialized)
431 : u32 m_TotalInworldVertices;
432 : std::vector<u32> m_ExploredVertices;
433 :
434 116 : static std::string GetSchema()
435 : {
436 116 : return "<a:component type='system'/><empty/>";
437 : }
438 :
439 6 : void Init(const CParamNode& UNUSED(paramNode)) override
440 : {
441 6 : m_QueryNext = 1;
442 :
443 6 : m_DebugOverlayEnabled = false;
444 6 : m_DebugOverlayDirty = true;
445 :
446 6 : m_Deserializing = false;
447 6 : m_WorldX0 = m_WorldZ0 = m_WorldX1 = m_WorldZ1 = entity_pos_t::Zero();
448 :
449 : // Initialise with bogus values (these will get replaced when
450 : // SetBounds is called)
451 6 : ResetSubdivisions(entity_pos_t::FromInt(1024), entity_pos_t::FromInt(1024));
452 :
453 6 : m_SubdivisionResults.reserve(4096);
454 :
455 : // The whole map should be visible to Gaia by default, else e.g. animals
456 : // will get confused when trying to run from enemies
457 6 : m_LosRevealAll[0] = true;
458 :
459 6 : m_GlobalVisibilityUpdate = true;
460 :
461 6 : m_LosCircular = false;
462 6 : m_LosVerticesPerSide = 0;
463 6 : }
464 :
465 6 : void Deinit() override
466 : {
467 6 : }
468 :
469 : template<typename S>
470 0 : void SerializeCommon(S& serialize)
471 : {
472 0 : serialize.NumberFixed_Unbounded("world x0", m_WorldX0);
473 0 : serialize.NumberFixed_Unbounded("world z0", m_WorldZ0);
474 0 : serialize.NumberFixed_Unbounded("world x1", m_WorldX1);
475 0 : serialize.NumberFixed_Unbounded("world z1", m_WorldZ1);
476 :
477 0 : serialize.NumberU32_Unbounded("query next", m_QueryNext);
478 0 : Serializer(serialize, "queries", m_Queries, GetSimContext());
479 0 : Serializer(serialize, "entity data", m_EntityData);
480 :
481 0 : Serializer(serialize, "los reveal all", m_LosRevealAll);
482 0 : serialize.Bool("los circular", m_LosCircular);
483 0 : serialize.NumberI32_Unbounded("los verts per side", m_LosVerticesPerSide);
484 :
485 0 : serialize.Bool("global visibility update", m_GlobalVisibilityUpdate);
486 0 : Serializer(serialize, "global player visibility update", m_GlobalPlayerVisibilityUpdate);
487 0 : Serializer(serialize, "dirty visibility", m_DirtyVisibility);
488 0 : Serializer(serialize, "modified entities", m_ModifiedEntities);
489 :
490 : // We don't serialize m_Subdivision, m_LosPlayerCounts or m_LosRegions
491 : // since they can be recomputed from the entity data when deserializing;
492 : // m_LosState must be serialized since it depends on the history of exploration
493 :
494 0 : Serializer(serialize, "los state", m_LosState);
495 0 : Serializer(serialize, "shared los masks", m_SharedLosMasks);
496 0 : Serializer(serialize, "shared dirty visibility masks", m_SharedDirtyVisibilityMasks);
497 0 : }
498 :
499 0 : void Serialize(ISerializer& serialize) override
500 : {
501 0 : SerializeCommon(serialize);
502 0 : }
503 :
504 0 : void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) override
505 : {
506 0 : Init(paramNode);
507 :
508 0 : SerializeCommon(deserialize);
509 0 : }
510 :
511 1060 : void HandleMessage(const CMessage& msg, bool UNUSED(global)) override
512 : {
513 1060 : switch (msg.GetType())
514 : {
515 0 : case MT_Deserialized:
516 : {
517 : // Reinitialize subdivisions and LOS data after all
518 : // other components have been deserialized.
519 0 : m_Deserializing = true;
520 0 : ResetDerivedData();
521 0 : m_Deserializing = false;
522 0 : break;
523 : }
524 9 : case MT_Create:
525 : {
526 9 : const CMessageCreate& msgData = static_cast<const CMessageCreate&> (msg);
527 9 : entity_id_t ent = msgData.entity;
528 :
529 : // Ignore local entities - we shouldn't let them influence anything
530 9 : if (ENTITY_IS_LOCAL(ent))
531 0 : break;
532 :
533 : // Ignore non-positional entities
534 9 : CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), ent);
535 9 : if (!cmpPosition)
536 6 : break;
537 :
538 : // The newly-created entity will have owner -1 and position out-of-world
539 : // (any initialisation of those values will happen later), so we can just
540 : // use the default-constructed EntityData here
541 3 : EntityData entdata;
542 :
543 : // Store the LOS data, if any
544 3 : CmpPtr<ICmpVision> cmpVision(GetSimContext(), ent);
545 3 : if (cmpVision)
546 : {
547 3 : entdata.visionRange = cmpVision->GetRange();
548 3 : entdata.SetFlag<FlagMasks::RevealShore>(cmpVision->GetRevealShore());
549 : }
550 3 : CmpPtr<ICmpVisibility> cmpVisibility(GetSimContext(), ent);
551 3 : if (cmpVisibility)
552 0 : entdata.SetFlag<FlagMasks::RetainInFog>(cmpVisibility->GetRetainInFog());
553 :
554 : // Store the size
555 3 : CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), ent);
556 3 : if (cmpObstruction)
557 2 : entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity();
558 :
559 : // Remember this entity
560 3 : m_EntityData.insert(ent, entdata);
561 3 : break;
562 : }
563 1038 : case MT_PositionChanged:
564 : {
565 1038 : const CMessagePositionChanged& msgData = static_cast<const CMessagePositionChanged&> (msg);
566 1038 : entity_id_t ent = msgData.entity;
567 :
568 1038 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
569 :
570 : // Ignore if we're not already tracking this entity
571 1038 : if (it == m_EntityData.end())
572 0 : break;
573 :
574 1038 : if (msgData.inWorld)
575 : {
576 1038 : if (it->second.HasFlag<FlagMasks::InWorld>())
577 : {
578 1035 : CFixedVector2D from(it->second.x, it->second.z);
579 1035 : CFixedVector2D to(msgData.x, msgData.z);
580 1035 : m_Subdivision.Move(ent, from, to, it->second.size);
581 1035 : if (it->second.HasFlag<FlagMasks::SharedVision>())
582 0 : SharingLosMove(it->second.visionSharing, it->second.visionRange, from, to);
583 : else
584 1035 : LosMove(it->second.owner, it->second.visionRange, from, to);
585 1035 : LosRegion oldLosRegion = PosToLosRegionsHelper(it->second.x, it->second.z);
586 1035 : LosRegion newLosRegion = PosToLosRegionsHelper(msgData.x, msgData.z);
587 1035 : if (oldLosRegion != newLosRegion)
588 : {
589 1025 : RemoveFromRegion(oldLosRegion, ent);
590 1025 : AddToRegion(newLosRegion, ent);
591 : }
592 : }
593 : else
594 : {
595 3 : CFixedVector2D to(msgData.x, msgData.z);
596 3 : m_Subdivision.Add(ent, to, it->second.size);
597 3 : if (it->second.HasFlag<FlagMasks::SharedVision>())
598 0 : SharingLosAdd(it->second.visionSharing, it->second.visionRange, to);
599 : else
600 3 : LosAdd(it->second.owner, it->second.visionRange, to);
601 3 : AddToRegion(PosToLosRegionsHelper(msgData.x, msgData.z), ent);
602 : }
603 :
604 1038 : it->second.SetFlag<FlagMasks::InWorld>(true);
605 1038 : it->second.x = msgData.x;
606 1038 : it->second.z = msgData.z;
607 : }
608 : else
609 : {
610 0 : if (it->second.HasFlag<FlagMasks::InWorld>())
611 : {
612 0 : CFixedVector2D from(it->second.x, it->second.z);
613 0 : m_Subdivision.Remove(ent, from, it->second.size);
614 0 : if (it->second.HasFlag<FlagMasks::SharedVision>())
615 0 : SharingLosRemove(it->second.visionSharing, it->second.visionRange, from);
616 : else
617 0 : LosRemove(it->second.owner, it->second.visionRange, from);
618 0 : RemoveFromRegion(PosToLosRegionsHelper(it->second.x, it->second.z), ent);
619 : }
620 :
621 0 : it->second.SetFlag<FlagMasks::InWorld>(false);
622 0 : it->second.x = entity_pos_t::Zero();
623 0 : it->second.z = entity_pos_t::Zero();
624 : }
625 :
626 1038 : RequestVisibilityUpdate(ent);
627 :
628 1038 : break;
629 : }
630 11 : case MT_OwnershipChanged:
631 : {
632 11 : const CMessageOwnershipChanged& msgData = static_cast<const CMessageOwnershipChanged&> (msg);
633 11 : entity_id_t ent = msgData.entity;
634 :
635 11 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
636 :
637 : // Ignore if we're not already tracking this entity
638 11 : if (it == m_EntityData.end())
639 0 : break;
640 :
641 11 : if (it->second.HasFlag<FlagMasks::InWorld>())
642 : {
643 : // Entity vision is taken into account in VisionSharingChanged
644 : // when sharing component activated
645 8 : if (!it->second.HasFlag<FlagMasks::SharedVision>())
646 : {
647 8 : CFixedVector2D pos(it->second.x, it->second.z);
648 8 : LosRemove(it->second.owner, it->second.visionRange, pos);
649 8 : LosAdd(msgData.to, it->second.visionRange, pos);
650 : }
651 :
652 8 : if (it->second.HasFlag<FlagMasks::RevealShore>())
653 : {
654 0 : RevealShore(it->second.owner, false);
655 0 : RevealShore(msgData.to, true);
656 : }
657 : }
658 :
659 11 : ENSURE(-128 <= msgData.to && msgData.to <= 127);
660 11 : it->second.owner = (i8)msgData.to;
661 :
662 11 : break;
663 : }
664 2 : case MT_Destroy:
665 : {
666 2 : const CMessageDestroy& msgData = static_cast<const CMessageDestroy&> (msg);
667 2 : entity_id_t ent = msgData.entity;
668 :
669 2 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
670 :
671 : // Ignore if we're not already tracking this entity
672 2 : if (it == m_EntityData.end())
673 2 : break;
674 :
675 0 : if (it->second.HasFlag<FlagMasks::InWorld>())
676 : {
677 0 : m_Subdivision.Remove(ent, CFixedVector2D(it->second.x, it->second.z), it->second.size);
678 0 : RemoveFromRegion(PosToLosRegionsHelper(it->second.x, it->second.z), ent);
679 : }
680 :
681 : // This will be called after Ownership's OnDestroy, so ownership will be set
682 : // to -1 already and we don't have to do a LosRemove here
683 0 : ENSURE(it->second.owner == -1);
684 :
685 0 : m_EntityData.erase(it);
686 :
687 0 : break;
688 : }
689 0 : case MT_VisionRangeChanged:
690 : {
691 0 : const CMessageVisionRangeChanged& msgData = static_cast<const CMessageVisionRangeChanged&> (msg);
692 0 : entity_id_t ent = msgData.entity;
693 :
694 0 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
695 :
696 : // Ignore if we're not already tracking this entity
697 0 : if (it == m_EntityData.end())
698 0 : break;
699 :
700 0 : CmpPtr<ICmpVision> cmpVision(GetSimContext(), ent);
701 0 : if (!cmpVision)
702 0 : break;
703 :
704 0 : entity_pos_t oldRange = it->second.visionRange;
705 0 : entity_pos_t newRange = msgData.newRange;
706 :
707 : // If the range changed and the entity's in-world, we need to manually adjust it
708 : // but if it's not in-world, we only need to set the new vision range
709 :
710 0 : it->second.visionRange = newRange;
711 :
712 0 : if (it->second.HasFlag<FlagMasks::InWorld>())
713 : {
714 0 : CFixedVector2D pos(it->second.x, it->second.z);
715 0 : if (it->second.HasFlag<FlagMasks::SharedVision>())
716 : {
717 0 : SharingLosRemove(it->second.visionSharing, oldRange, pos);
718 0 : SharingLosAdd(it->second.visionSharing, newRange, pos);
719 : }
720 : else
721 : {
722 0 : LosRemove(it->second.owner, oldRange, pos);
723 0 : LosAdd(it->second.owner, newRange, pos);
724 : }
725 : }
726 :
727 0 : break;
728 : }
729 0 : case MT_VisionSharingChanged:
730 : {
731 0 : const CMessageVisionSharingChanged& msgData = static_cast<const CMessageVisionSharingChanged&> (msg);
732 0 : entity_id_t ent = msgData.entity;
733 :
734 0 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
735 :
736 : // Ignore if we're not already tracking this entity
737 0 : if (it == m_EntityData.end())
738 0 : break;
739 :
740 0 : ENSURE(msgData.player > 0 && msgData.player < MAX_LOS_PLAYER_ID+1);
741 0 : u16 visionChanged = CalcVisionSharingMask(msgData.player);
742 :
743 0 : if (!it->second.HasFlag<FlagMasks::SharedVision>())
744 : {
745 : // Activation of the Vision Sharing
746 0 : ENSURE(it->second.owner == (i8)msgData.player);
747 0 : it->second.visionSharing = visionChanged;
748 0 : it->second.SetFlag<FlagMasks::SharedVision>(true);
749 0 : break;
750 : }
751 :
752 0 : if (it->second.HasFlag<FlagMasks::InWorld>())
753 : {
754 0 : entity_pos_t range = it->second.visionRange;
755 0 : CFixedVector2D pos(it->second.x, it->second.z);
756 0 : if (msgData.add)
757 0 : LosAdd(msgData.player, range, pos);
758 : else
759 0 : LosRemove(msgData.player, range, pos);
760 : }
761 :
762 0 : if (msgData.add)
763 0 : it->second.visionSharing |= visionChanged;
764 : else
765 0 : it->second.visionSharing &= ~visionChanged;
766 0 : break;
767 : }
768 0 : case MT_Update:
769 : {
770 0 : m_DebugOverlayDirty = true;
771 0 : ExecuteActiveQueries();
772 0 : UpdateVisibilityData();
773 0 : break;
774 : }
775 0 : case MT_RenderSubmit:
776 : {
777 0 : const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
778 0 : RenderSubmit(msgData.collector);
779 0 : break;
780 : }
781 : }
782 1060 : }
783 :
784 2 : void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1) override
785 : {
786 : // Don't support rectangular looking maps.
787 2 : ENSURE(x1-x0 == z1-z0);
788 2 : m_WorldX0 = x0;
789 2 : m_WorldZ0 = z0;
790 2 : m_WorldX1 = x1;
791 2 : m_WorldZ1 = z1;
792 2 : m_LosVerticesPerSide = ((x1 - x0) / LOS_TILE_SIZE).ToInt_RoundToZero() + 1;
793 :
794 2 : ResetDerivedData();
795 2 : }
796 :
797 1037 : void Verify() override
798 : {
799 : // Ignore if map not initialised yet
800 1037 : if (m_WorldX1.IsZero())
801 0 : return;
802 :
803 : // Check that calling ResetDerivedData (i.e. recomputing all the state from scratch)
804 : // does not affect the incrementally-computed state
805 :
806 2074 : std::array<Grid<u16>, MAX_LOS_PLAYER_ID> oldPlayerCounts = m_LosPlayerCounts;
807 2074 : Grid<u32> oldStateRevealed = m_LosStateRevealed;
808 2074 : FastSpatialSubdivision oldSubdivision = m_Subdivision;
809 2074 : Grid<std::set<entity_id_t> > oldLosRegions = m_LosRegions;
810 :
811 1037 : m_Deserializing = true;
812 1037 : ResetDerivedData();
813 1037 : m_Deserializing = false;
814 :
815 1037 : if (oldPlayerCounts != m_LosPlayerCounts)
816 : {
817 0 : for (size_t id = 0; id < m_LosPlayerCounts.size(); ++id)
818 : {
819 0 : debug_printf("player %zu\n", id);
820 0 : for (size_t i = 0; i < oldPlayerCounts[id].width(); ++i)
821 : {
822 0 : for (size_t j = 0; j < oldPlayerCounts[id].height(); ++j)
823 0 : debug_printf("%i ", oldPlayerCounts[id].get(i,j));
824 0 : debug_printf("\n");
825 : }
826 : }
827 0 : for (size_t id = 0; id < m_LosPlayerCounts.size(); ++id)
828 : {
829 0 : debug_printf("player %zu\n", id);
830 0 : for (size_t i = 0; i < m_LosPlayerCounts[id].width(); ++i)
831 : {
832 0 : for (size_t j = 0; j < m_LosPlayerCounts[id].height(); ++j)
833 0 : debug_printf("%i ", m_LosPlayerCounts[id].get(i,j));
834 0 : debug_printf("\n");
835 : }
836 : }
837 0 : debug_warn(L"inconsistent player counts");
838 : }
839 1037 : if (oldStateRevealed != m_LosStateRevealed)
840 0 : debug_warn(L"inconsistent revealed");
841 1037 : if (oldSubdivision != m_Subdivision)
842 0 : debug_warn(L"inconsistent subdivs");
843 1037 : if (oldLosRegions != m_LosRegions)
844 0 : debug_warn(L"inconsistent los regions");
845 : }
846 :
847 0 : FastSpatialSubdivision* GetSubdivision() override
848 : {
849 0 : return &m_Subdivision;
850 : }
851 :
852 : // Reinitialise subdivisions and LOS data, based on entity data
853 1039 : void ResetDerivedData()
854 : {
855 1039 : ENSURE(m_WorldX0.IsZero() && m_WorldZ0.IsZero()); // don't bother implementing non-zero offsets yet
856 1039 : ResetSubdivisions(m_WorldX1, m_WorldZ1);
857 :
858 1039 : m_LosRegionsPerSide = m_LosVerticesPerSide / LOS_REGION_RATIO;
859 :
860 17663 : for (size_t player_id = 0; player_id < m_LosPlayerCounts.size(); ++player_id)
861 16624 : m_LosPlayerCounts[player_id].clear();
862 :
863 1039 : m_ExploredVertices.clear();
864 1039 : m_ExploredVertices.resize(MAX_LOS_PLAYER_ID+1, 0);
865 :
866 1039 : if (m_Deserializing)
867 : {
868 : // recalc current exploration stats.
869 134810 : for (i32 j = 0; j < m_LosVerticesPerSide; j++)
870 17390490 : for (i32 i = 0; i < m_LosVerticesPerSide; i++)
871 17256717 : if (!LosIsOffWorld(i, j))
872 266709141 : for (u8 k = 1; k < MAX_LOS_PLAYER_ID+1; ++k)
873 251020368 : m_ExploredVertices.at(k) += ((m_LosState.get(i, j) & ((u32)LosState::EXPLORED << (2*(k-1)))) > 0);
874 : } else
875 2 : m_LosState.resize(m_LosVerticesPerSide, m_LosVerticesPerSide);
876 :
877 1039 : m_LosStateRevealed.resize(m_LosVerticesPerSide, m_LosVerticesPerSide);
878 :
879 1039 : if (!m_Deserializing)
880 : {
881 2 : m_DirtyVisibility.resize(m_LosRegionsPerSide, m_LosRegionsPerSide);
882 : }
883 1039 : ENSURE(m_DirtyVisibility.width() == m_LosRegionsPerSide);
884 1039 : ENSURE(m_DirtyVisibility.height() == m_LosRegionsPerSide);
885 :
886 1039 : m_LosRegions.resize(m_LosRegionsPerSide, m_LosRegionsPerSide);
887 :
888 2074 : for (EntityMap<EntityData>::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it)
889 1035 : if (it->second.HasFlag<FlagMasks::InWorld>())
890 : {
891 1033 : if (it->second.HasFlag<FlagMasks::SharedVision>())
892 0 : SharingLosAdd(it->second.visionSharing, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z));
893 : else
894 1033 : LosAdd(it->second.owner, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z));
895 1033 : AddToRegion(PosToLosRegionsHelper(it->second.x, it->second.z), it->first);
896 :
897 1033 : if (it->second.HasFlag<FlagMasks::RevealShore>())
898 0 : RevealShore(it->second.owner, true);
899 : }
900 :
901 1039 : m_TotalInworldVertices = 0;
902 135070 : for (i32 j = 0; j < m_LosVerticesPerSide; ++j)
903 17424030 : for (i32 i = 0; i < m_LosVerticesPerSide; ++i)
904 : {
905 17289999 : if (LosIsOffWorld(i,j))
906 1570968 : m_LosStateRevealed.get(i, j) = 0;
907 : else
908 : {
909 15719031 : m_LosStateRevealed.get(i, j) = 0xFFFFFFFFu;
910 15719031 : m_TotalInworldVertices++;
911 : }
912 : }
913 1039 : }
914 :
915 1045 : void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1)
916 : {
917 1045 : m_Subdivision.Reset(x1, z1);
918 :
919 2080 : for (EntityMap<EntityData>::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it)
920 1035 : if (it->second.HasFlag<FlagMasks::InWorld>())
921 1033 : m_Subdivision.Add(it->first, CFixedVector2D(it->second.x, it->second.z), it->second.size);
922 1045 : }
923 :
924 0 : tag_t CreateActiveQuery(entity_id_t source,
925 : entity_pos_t minRange, entity_pos_t maxRange,
926 : const std::vector<int>& owners, int requiredInterface, u8 flags, bool accountForSize) override
927 : {
928 0 : tag_t id = m_QueryNext++;
929 0 : m_Queries[id] = ConstructQuery(source, minRange, maxRange, owners, requiredInterface, flags, accountForSize);
930 :
931 0 : return id;
932 : }
933 :
934 0 : tag_t CreateActiveParabolicQuery(entity_id_t source,
935 : entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t yOrigin,
936 : const std::vector<int>& owners, int requiredInterface, u8 flags) override
937 : {
938 0 : tag_t id = m_QueryNext++;
939 0 : m_Queries[id] = ConstructParabolicQuery(source, minRange, maxRange, yOrigin, owners, requiredInterface, flags, true);
940 :
941 0 : return id;
942 : }
943 :
944 0 : void DestroyActiveQuery(tag_t tag) override
945 : {
946 0 : if (m_Queries.find(tag) == m_Queries.end())
947 : {
948 0 : LOGERROR("CCmpRangeManager: DestroyActiveQuery called with invalid tag %u", tag);
949 0 : return;
950 : }
951 :
952 0 : m_Queries.erase(tag);
953 : }
954 :
955 0 : void EnableActiveQuery(tag_t tag) override
956 : {
957 0 : std::map<tag_t, Query>::iterator it = m_Queries.find(tag);
958 0 : if (it == m_Queries.end())
959 : {
960 0 : LOGERROR("CCmpRangeManager: EnableActiveQuery called with invalid tag %u", tag);
961 0 : return;
962 : }
963 :
964 0 : Query& q = it->second;
965 0 : q.enabled = true;
966 : }
967 :
968 0 : void DisableActiveQuery(tag_t tag) override
969 : {
970 0 : std::map<tag_t, Query>::iterator it = m_Queries.find(tag);
971 0 : if (it == m_Queries.end())
972 : {
973 0 : LOGERROR("CCmpRangeManager: DisableActiveQuery called with invalid tag %u", tag);
974 0 : return;
975 : }
976 :
977 0 : Query& q = it->second;
978 0 : q.enabled = false;
979 : }
980 :
981 0 : bool IsActiveQueryEnabled(tag_t tag) const override
982 : {
983 0 : std::map<tag_t, Query>::const_iterator it = m_Queries.find(tag);
984 0 : if (it == m_Queries.end())
985 : {
986 0 : LOGERROR("CCmpRangeManager: IsActiveQueryEnabled called with invalid tag %u", tag);
987 0 : return false;
988 : }
989 :
990 0 : const Query& q = it->second;
991 0 : return q.enabled;
992 : }
993 :
994 0 : std::vector<entity_id_t> ExecuteQueryAroundPos(const CFixedVector2D& pos,
995 : entity_pos_t minRange, entity_pos_t maxRange,
996 : const std::vector<int>& owners, int requiredInterface, bool accountForSize) override
997 : {
998 0 : Query q = ConstructQuery(INVALID_ENTITY, minRange, maxRange, owners, requiredInterface, GetEntityFlagMask("normal"), accountForSize);
999 0 : std::vector<entity_id_t> r;
1000 0 : PerformQuery(q, r, pos);
1001 :
1002 : // Return the list sorted by distance from the entity
1003 0 : std::stable_sort(r.begin(), r.end(), EntityDistanceOrdering(m_EntityData, pos));
1004 :
1005 0 : return r;
1006 : }
1007 :
1008 13 : std::vector<entity_id_t> ExecuteQuery(entity_id_t source,
1009 : entity_pos_t minRange, entity_pos_t maxRange,
1010 : const std::vector<int>& owners, int requiredInterface, bool accountForSize) override
1011 : {
1012 26 : PROFILE("ExecuteQuery");
1013 :
1014 26 : Query q = ConstructQuery(source, minRange, maxRange, owners, requiredInterface, GetEntityFlagMask("normal"), accountForSize);
1015 :
1016 13 : std::vector<entity_id_t> r;
1017 :
1018 13 : CmpPtr<ICmpPosition> cmpSourcePosition(q.source);
1019 13 : if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld())
1020 : {
1021 : // If the source doesn't have a position, then the result is just the empty list
1022 0 : return r;
1023 : }
1024 :
1025 13 : CFixedVector2D pos = cmpSourcePosition->GetPosition2D();
1026 13 : PerformQuery(q, r, pos);
1027 :
1028 : // Return the list sorted by distance from the entity
1029 13 : std::stable_sort(r.begin(), r.end(), EntityDistanceOrdering(m_EntityData, pos));
1030 :
1031 13 : return r;
1032 : }
1033 :
1034 0 : std::vector<entity_id_t> ResetActiveQuery(tag_t tag) override
1035 : {
1036 0 : PROFILE("ResetActiveQuery");
1037 :
1038 0 : std::vector<entity_id_t> r;
1039 :
1040 0 : std::map<tag_t, Query>::iterator it = m_Queries.find(tag);
1041 0 : if (it == m_Queries.end())
1042 : {
1043 0 : LOGERROR("CCmpRangeManager: ResetActiveQuery called with invalid tag %u", tag);
1044 0 : return r;
1045 : }
1046 :
1047 0 : Query& q = it->second;
1048 0 : q.enabled = true;
1049 :
1050 0 : CmpPtr<ICmpPosition> cmpSourcePosition(q.source);
1051 0 : if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld())
1052 : {
1053 : // If the source doesn't have a position, then the result is just the empty list
1054 0 : q.lastMatch = r;
1055 0 : return r;
1056 : }
1057 :
1058 0 : CFixedVector2D pos = cmpSourcePosition->GetPosition2D();
1059 0 : PerformQuery(q, r, pos);
1060 :
1061 0 : q.lastMatch = r;
1062 :
1063 : // Return the list sorted by distance from the entity
1064 0 : std::stable_sort(r.begin(), r.end(), EntityDistanceOrdering(m_EntityData, pos));
1065 :
1066 0 : return r;
1067 : }
1068 :
1069 64 : std::vector<entity_id_t> GetEntitiesByPlayer(player_id_t player) const override
1070 : {
1071 64 : return GetEntitiesByMask(CalcOwnerMask(player));
1072 : }
1073 :
1074 8 : std::vector<entity_id_t> GetNonGaiaEntities() const override
1075 : {
1076 8 : return GetEntitiesByMask(~3u); // bit 0 for owner=-1 and bit 1 for gaia
1077 : }
1078 :
1079 0 : std::vector<entity_id_t> GetGaiaAndNonGaiaEntities() const override
1080 : {
1081 0 : return GetEntitiesByMask(~1u); // bit 0 for owner=-1
1082 : }
1083 :
1084 72 : std::vector<entity_id_t> GetEntitiesByMask(u32 ownerMask) const
1085 : {
1086 72 : std::vector<entity_id_t> entities;
1087 :
1088 144 : for (EntityMap<EntityData>::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it)
1089 : {
1090 : // Check owner and add to list if it matches
1091 72 : if (CalcOwnerMask(it->second.owner) & ownerMask)
1092 15 : entities.push_back(it->first);
1093 : }
1094 :
1095 72 : return entities;
1096 : }
1097 :
1098 0 : void SetDebugOverlay(bool enabled) override
1099 : {
1100 0 : m_DebugOverlayEnabled = enabled;
1101 0 : m_DebugOverlayDirty = true;
1102 0 : if (!enabled)
1103 0 : m_DebugOverlayLines.clear();
1104 0 : }
1105 :
1106 : /**
1107 : * Update all currently-enabled active queries.
1108 : */
1109 0 : void ExecuteActiveQueries()
1110 : {
1111 0 : PROFILE3("ExecuteActiveQueries");
1112 :
1113 : // Store a queue of all messages before sending any, so we can assume
1114 : // no entities will move until we've finished checking all the ranges
1115 0 : std::vector<std::pair<entity_id_t, CMessageRangeUpdate> > messages;
1116 0 : std::vector<entity_id_t> results;
1117 0 : std::vector<entity_id_t> added;
1118 0 : std::vector<entity_id_t> removed;
1119 :
1120 0 : for (std::map<tag_t, Query>::iterator it = m_Queries.begin(); it != m_Queries.end(); ++it)
1121 : {
1122 0 : Query& query = it->second;
1123 :
1124 0 : if (!query.enabled)
1125 0 : continue;
1126 :
1127 0 : results.clear();
1128 0 : CmpPtr<ICmpPosition> cmpSourcePosition(query.source);
1129 0 : if (cmpSourcePosition && cmpSourcePosition->IsInWorld())
1130 : {
1131 0 : results.reserve(query.lastMatch.size());
1132 0 : PerformQuery(query, results, cmpSourcePosition->GetPosition2D());
1133 : }
1134 :
1135 : // Compute the changes vs the last match
1136 0 : added.clear();
1137 0 : removed.clear();
1138 : // Return the 'added' list sorted by distance from the entity
1139 : // (Don't bother sorting 'removed' because they might not even have positions or exist any more)
1140 0 : std::set_difference(results.begin(), results.end(), query.lastMatch.begin(), query.lastMatch.end(),
1141 0 : std::back_inserter(added));
1142 0 : std::set_difference(query.lastMatch.begin(), query.lastMatch.end(), results.begin(), results.end(),
1143 0 : std::back_inserter(removed));
1144 0 : if (added.empty() && removed.empty())
1145 0 : continue;
1146 :
1147 0 : if (cmpSourcePosition && cmpSourcePosition->IsInWorld())
1148 0 : std::stable_sort(added.begin(), added.end(), EntityDistanceOrdering(m_EntityData, cmpSourcePosition->GetPosition2D()));
1149 :
1150 0 : messages.resize(messages.size() + 1);
1151 0 : std::pair<entity_id_t, CMessageRangeUpdate>& back = messages.back();
1152 0 : back.first = query.source.GetId();
1153 0 : back.second.tag = it->first;
1154 0 : back.second.added.swap(added);
1155 0 : back.second.removed.swap(removed);
1156 0 : query.lastMatch.swap(results);
1157 : }
1158 :
1159 0 : CComponentManager& cmpMgr = GetSimContext().GetComponentManager();
1160 0 : for (size_t i = 0; i < messages.size(); ++i)
1161 0 : cmpMgr.PostMessage(messages[i].first, messages[i].second);
1162 0 : }
1163 :
1164 : /**
1165 : * Returns whether the given entity matches the given query (ignoring maxRange)
1166 : */
1167 26 : bool TestEntityQuery(const Query& q, entity_id_t id, const EntityData& entity) const
1168 : {
1169 : // Quick filter to ignore entities with the wrong owner
1170 26 : if (!(CalcOwnerMask(entity.owner) & q.ownersMask))
1171 0 : return false;
1172 :
1173 : // Ignore entities not present in the world
1174 26 : if (!entity.HasFlag<FlagMasks::InWorld>())
1175 0 : return false;
1176 :
1177 : // Ignore entities that don't match the current flags
1178 26 : if (!((entity.flags & FlagMasks::AllQuery) & q.flagsMask))
1179 0 : return false;
1180 :
1181 : // Ignore self
1182 26 : if (id == q.source.GetId())
1183 13 : return false;
1184 :
1185 : // Ignore if it's missing the required interface
1186 13 : if (q.interface && !GetSimContext().GetComponentManager().QueryInterface(id, q.interface))
1187 0 : return false;
1188 :
1189 13 : return true;
1190 : }
1191 :
1192 : /**
1193 : * Returns a list of distinct entity IDs that match the given query, sorted by ID.
1194 : */
1195 13 : void PerformQuery(const Query& q, std::vector<entity_id_t>& r, CFixedVector2D pos)
1196 : {
1197 :
1198 : // Special case: range is ALWAYS_IN_RANGE means check all entities ignoring distance.
1199 13 : if (q.maxRange == ALWAYS_IN_RANGE)
1200 : {
1201 0 : for (EntityMap<EntityData>::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it)
1202 : {
1203 0 : if (!TestEntityQuery(q, it->first, it->second))
1204 0 : continue;
1205 :
1206 0 : r.push_back(it->first);
1207 : }
1208 : }
1209 : // Not the entire world, so check a parabolic range, or a regular range.
1210 13 : else if (q.parabolic)
1211 : {
1212 : // The yOrigin is part of the 3D position, as the source is really that much heigher.
1213 0 : CmpPtr<ICmpPosition> cmpSourcePosition(q.source);
1214 0 : CFixedVector3D pos3d = cmpSourcePosition->GetPosition()+
1215 0 : CFixedVector3D(entity_pos_t::Zero(), q.yOrigin, entity_pos_t::Zero()) ;
1216 : // Get a quick list of entities that are potentially in range, with a cutoff of 2*maxRange.
1217 0 : m_SubdivisionResults.clear();
1218 0 : m_Subdivision.GetNear(m_SubdivisionResults, pos, q.maxRange * 2);
1219 :
1220 0 : for (size_t i = 0; i < m_SubdivisionResults.size(); ++i)
1221 : {
1222 0 : EntityMap<EntityData>::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]);
1223 0 : ENSURE(it != m_EntityData.end());
1224 :
1225 0 : if (!TestEntityQuery(q, it->first, it->second))
1226 0 : continue;
1227 :
1228 0 : CmpPtr<ICmpPosition> cmpSecondPosition(GetSimContext(), m_SubdivisionResults[i]);
1229 0 : if (!cmpSecondPosition || !cmpSecondPosition->IsInWorld())
1230 0 : continue;
1231 0 : CFixedVector3D secondPosition = cmpSecondPosition->GetPosition();
1232 :
1233 : // Doing an exact check for parabolas with obstruction sizes is not really possible.
1234 : // However, we can prove that InParabolicRange(d, range + size) > InParabolicRange(d, range)
1235 : // in the sense that it always returns true when the latter would, which is enough.
1236 : // To do so, compute the derivative with respect to distance, and notice that
1237 : // they have an intersection after which the former grows slower, and then use that to prove the above.
1238 : // Note that this is only true because we do not account for vertical size here,
1239 : // if we did, we would also need to artificially 'raise' the source over the target.
1240 0 : entity_pos_t range = q.maxRange + (q.accountForSize ? fixed::FromInt(it->second.size) : fixed::Zero());
1241 0 : if (!InParabolicRange(CFixedVector3D(it->second.x, secondPosition.Y, it->second.z) - pos3d, range))
1242 0 : continue;
1243 :
1244 0 : if (!q.minRange.IsZero())
1245 0 : if ((CFixedVector2D(it->second.x, it->second.z) - pos).CompareLength(q.minRange) < 0)
1246 0 : continue;
1247 :
1248 0 : r.push_back(it->first);
1249 : }
1250 0 : std::sort(r.begin(), r.end());
1251 : }
1252 : // check a regular range (i.e. not the entire world, and not parabolic)
1253 : else
1254 : {
1255 : // Get a quick list of entities that are potentially in range
1256 13 : m_SubdivisionResults.clear();
1257 13 : m_Subdivision.GetNear(m_SubdivisionResults, pos, q.maxRange);
1258 :
1259 39 : for (size_t i = 0; i < m_SubdivisionResults.size(); ++i)
1260 : {
1261 26 : EntityMap<EntityData>::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]);
1262 26 : ENSURE(it != m_EntityData.end());
1263 :
1264 26 : if (!TestEntityQuery(q, it->first, it->second))
1265 31 : continue;
1266 :
1267 : // Restrict based on approximate circle-circle distance.
1268 13 : entity_pos_t range = q.maxRange + (q.accountForSize ? fixed::FromInt(it->second.size) : fixed::Zero());
1269 13 : if ((CFixedVector2D(it->second.x, it->second.z) - pos).CompareLength(range) > 0)
1270 1 : continue;
1271 :
1272 12 : if (!q.minRange.IsZero())
1273 8 : if ((CFixedVector2D(it->second.x, it->second.z) - pos).CompareLength(q.minRange) < 0)
1274 4 : continue;
1275 :
1276 8 : r.push_back(it->first);
1277 : }
1278 13 : std::sort(r.begin(), r.end());
1279 : }
1280 13 : }
1281 :
1282 8 : entity_pos_t GetEffectiveParabolicRange(entity_id_t source, entity_id_t target, entity_pos_t range, entity_pos_t yOrigin) const override
1283 : {
1284 : // For non-positive ranges, just return the range.
1285 8 : if (range < entity_pos_t::Zero())
1286 1 : return range;
1287 :
1288 7 : CmpPtr<ICmpPosition> cmpSourcePosition(GetSimContext(), source);
1289 7 : if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld())
1290 1 : return NEVER_IN_RANGE;
1291 :
1292 6 : CmpPtr<ICmpPosition> cmpTargetPosition(GetSimContext(), target);
1293 6 : if (!cmpTargetPosition || !cmpTargetPosition->IsInWorld())
1294 1 : return NEVER_IN_RANGE;
1295 :
1296 5 : entity_pos_t heightDifference = cmpSourcePosition->GetHeightOffset() - cmpTargetPosition->GetHeightOffset() + yOrigin;
1297 5 : if (heightDifference < -range / 2)
1298 1 : return NEVER_IN_RANGE;
1299 :
1300 4 : entity_pos_t effectiveRange;
1301 4 : effectiveRange.SetInternalValue(static_cast<i32>(isqrt64(SQUARE_U64_FIXED(range) + static_cast<i64>(heightDifference.GetInternalValue()) * static_cast<i64>(range.GetInternalValue()) * 2)));
1302 4 : return effectiveRange;
1303 : }
1304 :
1305 0 : entity_pos_t GetElevationAdaptedRange(const CFixedVector3D& pos1, const CFixedVector3D& rot, entity_pos_t range, entity_pos_t yOrigin, entity_pos_t angle) const override
1306 : {
1307 0 : entity_pos_t r = entity_pos_t::Zero();
1308 0 : CFixedVector3D pos(pos1);
1309 :
1310 0 : pos.Y += yOrigin;
1311 0 : entity_pos_t orientation = rot.Y;
1312 :
1313 0 : entity_pos_t maxAngle = orientation + angle/2;
1314 0 : entity_pos_t minAngle = orientation - angle/2;
1315 :
1316 0 : int numberOfSteps = 16;
1317 :
1318 0 : if (angle == entity_pos_t::Zero())
1319 0 : numberOfSteps = 1;
1320 :
1321 0 : std::vector<entity_pos_t> coords = getParabolicRangeForm(pos, range, range*2, minAngle, maxAngle, numberOfSteps);
1322 :
1323 0 : entity_pos_t part = entity_pos_t::FromInt(numberOfSteps);
1324 :
1325 0 : for (int i = 0; i < numberOfSteps; ++i)
1326 0 : r = r + CFixedVector2D(coords[2*i],coords[2*i+1]).Length() / part;
1327 :
1328 0 : return r;
1329 :
1330 : }
1331 :
1332 0 : virtual std::vector<entity_pos_t> getParabolicRangeForm(CFixedVector3D pos, entity_pos_t maxRange, entity_pos_t cutoff, entity_pos_t minAngle, entity_pos_t maxAngle, int numberOfSteps) const
1333 : {
1334 0 : std::vector<entity_pos_t> r;
1335 :
1336 0 : CmpPtr<ICmpTerrain> cmpTerrain(GetSystemEntity());
1337 0 : if (!cmpTerrain)
1338 0 : return r;
1339 :
1340 : // angle = 0 goes in the positive Z direction
1341 0 : u64 precisionSquared = SQUARE_U64_FIXED(PARABOLIC_RANGE_TOLERANCE);
1342 :
1343 0 : CmpPtr<ICmpWaterManager> cmpWaterManager(GetSystemEntity());
1344 0 : entity_pos_t waterLevel = cmpWaterManager ? cmpWaterManager->GetWaterLevel(pos.X, pos.Z) : entity_pos_t::Zero();
1345 0 : entity_pos_t thisHeight = pos.Y > waterLevel ? pos.Y : waterLevel;
1346 :
1347 0 : for (int i = 0; i < numberOfSteps; ++i)
1348 : {
1349 0 : entity_pos_t angle = minAngle + (maxAngle - minAngle) / numberOfSteps * i;
1350 0 : entity_pos_t sin;
1351 0 : entity_pos_t cos;
1352 0 : entity_pos_t minDistance = entity_pos_t::Zero();
1353 0 : entity_pos_t maxDistance = cutoff;
1354 0 : sincos_approx(angle, sin, cos);
1355 :
1356 0 : CFixedVector2D minVector = CFixedVector2D(entity_pos_t::Zero(), entity_pos_t::Zero());
1357 0 : CFixedVector2D maxVector = CFixedVector2D(sin, cos).Multiply(cutoff);
1358 0 : entity_pos_t targetHeight = cmpTerrain->GetGroundLevel(pos.X+maxVector.X, pos.Z+maxVector.Y);
1359 : // use water level to display range on water
1360 0 : targetHeight = targetHeight > waterLevel ? targetHeight : waterLevel;
1361 :
1362 0 : if (InParabolicRange(CFixedVector3D(maxVector.X, targetHeight-thisHeight, maxVector.Y), maxRange))
1363 : {
1364 0 : r.push_back(maxVector.X);
1365 0 : r.push_back(maxVector.Y);
1366 0 : continue;
1367 : }
1368 :
1369 : // Loop until vectors come close enough
1370 0 : while ((maxVector - minVector).CompareLengthSquared(precisionSquared) > 0)
1371 : {
1372 : // difference still bigger than precision, bisect to get smaller difference
1373 0 : entity_pos_t newDistance = (minDistance+maxDistance)/entity_pos_t::FromInt(2);
1374 :
1375 0 : CFixedVector2D newVector = CFixedVector2D(sin, cos).Multiply(newDistance);
1376 :
1377 : // get the height of the ground
1378 0 : targetHeight = cmpTerrain->GetGroundLevel(pos.X+newVector.X, pos.Z+newVector.Y);
1379 0 : targetHeight = targetHeight > waterLevel ? targetHeight : waterLevel;
1380 :
1381 0 : if (InParabolicRange(CFixedVector3D(newVector.X, targetHeight-thisHeight, newVector.Y), maxRange))
1382 : {
1383 : // new vector is in parabolic range, so this is a new minVector
1384 0 : minVector = newVector;
1385 0 : minDistance = newDistance;
1386 : }
1387 : else
1388 : {
1389 : // new vector is out parabolic range, so this is a new maxVector
1390 0 : maxVector = newVector;
1391 0 : maxDistance = newDistance;
1392 : }
1393 :
1394 : }
1395 0 : r.push_back(maxVector.X);
1396 0 : r.push_back(maxVector.Y);
1397 :
1398 : }
1399 0 : r.push_back(r[0]);
1400 0 : r.push_back(r[1]);
1401 :
1402 0 : return r;
1403 : }
1404 :
1405 13 : Query ConstructQuery(entity_id_t source,
1406 : entity_pos_t minRange, entity_pos_t maxRange,
1407 : const std::vector<int>& owners, int requiredInterface, u8 flagsMask, bool accountForSize) const
1408 : {
1409 : // Min range must be non-negative.
1410 13 : if (minRange < entity_pos_t::Zero())
1411 0 : LOGWARNING("CCmpRangeManager: Invalid min range %f in query for entity %u", minRange.ToDouble(), source);
1412 :
1413 : // Max range must be non-negative, or else ALWAYS_IN_RANGE.
1414 : // TODO add NEVER_IN_RANGE.
1415 13 : if (maxRange < entity_pos_t::Zero() && maxRange != ALWAYS_IN_RANGE)
1416 0 : LOGWARNING("CCmpRangeManager: Invalid max range %f in query for entity %u", maxRange.ToDouble(), source);
1417 :
1418 13 : Query q;
1419 13 : q.enabled = false;
1420 13 : q.parabolic = false;
1421 13 : q.source = GetSimContext().GetComponentManager().LookupEntityHandle(source);
1422 13 : q.minRange = minRange;
1423 13 : q.maxRange = maxRange;
1424 13 : q.yOrigin = entity_pos_t::Zero();
1425 13 : q.accountForSize = accountForSize;
1426 :
1427 13 : if (q.accountForSize && q.source.GetId() != INVALID_ENTITY && q.maxRange != ALWAYS_IN_RANGE)
1428 : {
1429 13 : u32 size = 0;
1430 13 : if (ENTITY_IS_LOCAL(q.source.GetId()))
1431 : {
1432 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), q.source.GetId());
1433 0 : if (cmpObstruction)
1434 0 : size = cmpObstruction->GetSize().ToInt_RoundToInfinity();
1435 : }
1436 : else
1437 : {
1438 13 : EntityMap<EntityData>::const_iterator it = m_EntityData.find(q.source.GetId());
1439 13 : if (it != m_EntityData.end())
1440 13 : size = it->second.size;
1441 : }
1442 : // Adjust the range query based on the querier's obstruction radius.
1443 : // The smallest side of the obstruction isn't known here, so we can't safely adjust the min-range, only the max.
1444 : // 'size' is the diagonal size rounded up so this will cover all possible rotations of the querier.
1445 13 : q.maxRange += fixed::FromInt(size);
1446 : }
1447 :
1448 13 : q.ownersMask = 0;
1449 26 : for (size_t i = 0; i < owners.size(); ++i)
1450 13 : q.ownersMask |= CalcOwnerMask(owners[i]);
1451 :
1452 13 : if (q.ownersMask == 0)
1453 0 : LOGWARNING("CCmpRangeManager: No owners in query for entity %u", source);
1454 :
1455 13 : q.interface = requiredInterface;
1456 13 : q.flagsMask = flagsMask;
1457 :
1458 13 : return q;
1459 : }
1460 :
1461 0 : Query ConstructParabolicQuery(entity_id_t source,
1462 : entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t yOrigin,
1463 : const std::vector<int>& owners, int requiredInterface, u8 flagsMask, bool accountForSize) const
1464 : {
1465 0 : Query q = ConstructQuery(source, minRange, maxRange, owners, requiredInterface, flagsMask, accountForSize);
1466 0 : q.parabolic = true;
1467 0 : q.yOrigin = yOrigin;
1468 0 : return q;
1469 : }
1470 :
1471 0 : void RenderSubmit(SceneCollector& collector)
1472 : {
1473 0 : if (!m_DebugOverlayEnabled)
1474 0 : return;
1475 0 : static CColor disabledRingColor(1, 0, 0, 1); // red
1476 0 : static CColor enabledRingColor(0, 1, 0, 1); // green
1477 0 : static CColor subdivColor(0, 0, 1, 1); // blue
1478 0 : static CColor rayColor(1, 1, 0, 0.2f);
1479 :
1480 0 : if (m_DebugOverlayDirty)
1481 : {
1482 0 : m_DebugOverlayLines.clear();
1483 :
1484 0 : for (std::map<tag_t, Query>::iterator it = m_Queries.begin(); it != m_Queries.end(); ++it)
1485 : {
1486 0 : Query& q = it->second;
1487 :
1488 0 : CmpPtr<ICmpPosition> cmpSourcePosition(q.source);
1489 0 : if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld())
1490 0 : continue;
1491 0 : CFixedVector2D pos = cmpSourcePosition->GetPosition2D();
1492 :
1493 : // Draw the max range circle
1494 0 : if (!q.parabolic)
1495 : {
1496 0 : m_DebugOverlayLines.push_back(SOverlayLine());
1497 0 : m_DebugOverlayLines.back().m_Color = (q.enabled ? enabledRingColor : disabledRingColor);
1498 0 : SimRender::ConstructCircleOnGround(GetSimContext(), pos.X.ToFloat(), pos.Y.ToFloat(), q.maxRange.ToFloat(), m_DebugOverlayLines.back(), true);
1499 : }
1500 : else
1501 : {
1502 : // yOrigin is part of the 3D position. As if the unit is really that much higher.
1503 0 : CFixedVector3D pos3D = cmpSourcePosition->GetPosition();
1504 0 : pos3D.Y += q.yOrigin;
1505 :
1506 0 : std::vector<entity_pos_t> coords;
1507 :
1508 : // Get the outline from cache if possible
1509 0 : if (ParabolicRangesOutlines.find(q.source.GetId()) != ParabolicRangesOutlines.end())
1510 : {
1511 0 : EntityParabolicRangeOutline e = ParabolicRangesOutlines[q.source.GetId()];
1512 0 : if (e.position == pos3D && e.range == q.maxRange)
1513 : {
1514 : // outline is cached correctly, use it
1515 0 : coords = e.outline;
1516 : }
1517 : else
1518 : {
1519 : // outline was cached, but important parameters changed
1520 : // (position, elevation, range)
1521 : // update it
1522 0 : coords = getParabolicRangeForm(pos3D,q.maxRange,q.maxRange*2, entity_pos_t::Zero(), entity_pos_t::FromFloat(2.0f*3.14f),70);
1523 0 : e.outline = coords;
1524 0 : e.range = q.maxRange;
1525 0 : e.position = pos3D;
1526 0 : ParabolicRangesOutlines[q.source.GetId()] = e;
1527 : }
1528 : }
1529 : else
1530 : {
1531 : // outline wasn't cached (first time you enable the range overlay
1532 : // or you created a new entiy)
1533 : // cache a new outline
1534 0 : coords = getParabolicRangeForm(pos3D,q.maxRange,q.maxRange*2, entity_pos_t::Zero(), entity_pos_t::FromFloat(2.0f*3.14f),70);
1535 0 : EntityParabolicRangeOutline e;
1536 0 : e.source = q.source.GetId();
1537 0 : e.range = q.maxRange;
1538 0 : e.position = pos3D;
1539 0 : e.outline = coords;
1540 0 : ParabolicRangesOutlines[q.source.GetId()] = e;
1541 : }
1542 :
1543 0 : CColor thiscolor = q.enabled ? enabledRingColor : disabledRingColor;
1544 :
1545 : // draw the outline (piece by piece)
1546 0 : for (size_t i = 3; i < coords.size(); i += 2)
1547 : {
1548 0 : std::vector<float> c;
1549 0 : c.push_back((coords[i - 3] + pos3D.X).ToFloat());
1550 0 : c.push_back((coords[i - 2] + pos3D.Z).ToFloat());
1551 0 : c.push_back((coords[i - 1] + pos3D.X).ToFloat());
1552 0 : c.push_back((coords[i] + pos3D.Z).ToFloat());
1553 0 : m_DebugOverlayLines.push_back(SOverlayLine());
1554 0 : m_DebugOverlayLines.back().m_Color = thiscolor;
1555 0 : SimRender::ConstructLineOnGround(GetSimContext(), c, m_DebugOverlayLines.back(), true);
1556 : }
1557 : }
1558 :
1559 : // Draw the min range circle
1560 0 : if (!q.minRange.IsZero())
1561 0 : SimRender::ConstructCircleOnGround(GetSimContext(), pos.X.ToFloat(), pos.Y.ToFloat(), q.minRange.ToFloat(), m_DebugOverlayLines.back(), true);
1562 :
1563 : // Draw a ray from the source to each matched entity
1564 0 : for (size_t i = 0; i < q.lastMatch.size(); ++i)
1565 : {
1566 0 : CmpPtr<ICmpPosition> cmpTargetPosition(GetSimContext(), q.lastMatch[i]);
1567 0 : if (!cmpTargetPosition || !cmpTargetPosition->IsInWorld())
1568 0 : continue;
1569 0 : CFixedVector2D targetPos = cmpTargetPosition->GetPosition2D();
1570 :
1571 0 : std::vector<float> coords;
1572 0 : coords.push_back(pos.X.ToFloat());
1573 0 : coords.push_back(pos.Y.ToFloat());
1574 0 : coords.push_back(targetPos.X.ToFloat());
1575 0 : coords.push_back(targetPos.Y.ToFloat());
1576 :
1577 0 : m_DebugOverlayLines.push_back(SOverlayLine());
1578 0 : m_DebugOverlayLines.back().m_Color = rayColor;
1579 0 : SimRender::ConstructLineOnGround(GetSimContext(), coords, m_DebugOverlayLines.back(), true);
1580 : }
1581 : }
1582 :
1583 : // render subdivision grid
1584 0 : float divSize = m_Subdivision.GetDivisionSize();
1585 0 : int size = m_Subdivision.GetWidth();
1586 0 : for (int x = 0; x < size; ++x)
1587 : {
1588 0 : for (int y = 0; y < size; ++y)
1589 : {
1590 0 : m_DebugOverlayLines.push_back(SOverlayLine());
1591 0 : m_DebugOverlayLines.back().m_Color = subdivColor;
1592 :
1593 0 : float xpos = x*divSize + divSize/2;
1594 0 : float zpos = y*divSize + divSize/2;
1595 0 : SimRender::ConstructSquareOnGround(GetSimContext(), xpos, zpos, divSize, divSize, 0.0f,
1596 0 : m_DebugOverlayLines.back(), false, 1.0f);
1597 : }
1598 : }
1599 :
1600 0 : m_DebugOverlayDirty = false;
1601 : }
1602 :
1603 0 : for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i)
1604 0 : collector.Submit(&m_DebugOverlayLines[i]);
1605 : }
1606 :
1607 13 : u8 GetEntityFlagMask(const std::string& identifier) const override
1608 : {
1609 13 : if (identifier == "normal")
1610 13 : return FlagMasks::Normal;
1611 0 : if (identifier == "injured")
1612 0 : return FlagMasks::Injured;
1613 :
1614 0 : LOGWARNING("CCmpRangeManager: Invalid flag identifier %s", identifier.c_str());
1615 0 : return FlagMasks::None;
1616 : }
1617 :
1618 0 : void SetEntityFlag(entity_id_t ent, const std::string& identifier, bool value) override
1619 : {
1620 0 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
1621 :
1622 : // We don't have this entity
1623 0 : if (it == m_EntityData.end())
1624 0 : return;
1625 :
1626 0 : u8 flag = GetEntityFlagMask(identifier);
1627 :
1628 0 : if (flag == FlagMasks::None)
1629 0 : LOGWARNING("CCmpRangeManager: Invalid flag identifier %s for entity %u", identifier.c_str(), ent);
1630 : else
1631 0 : it->second.SetFlag(flag, value);
1632 : }
1633 :
1634 : // ****************************************************************
1635 :
1636 : // LOS implementation:
1637 :
1638 0 : CLosQuerier GetLosQuerier(player_id_t player) const override
1639 : {
1640 0 : if (GetLosRevealAll(player))
1641 0 : return CLosQuerier(0xFFFFFFFFu, m_LosStateRevealed, m_LosVerticesPerSide);
1642 : else
1643 0 : return CLosQuerier(GetSharedLosMask(player), m_LosState, m_LosVerticesPerSide);
1644 : }
1645 :
1646 0 : void ActivateScriptedVisibility(entity_id_t ent, bool status) override
1647 : {
1648 0 : EntityMap<EntityData>::iterator it = m_EntityData.find(ent);
1649 0 : if (it != m_EntityData.end())
1650 0 : it->second.SetFlag<FlagMasks::ScriptedVisibility>(status);
1651 0 : }
1652 :
1653 0 : LosVisibility ComputeLosVisibility(CEntityHandle ent, player_id_t player) const
1654 : {
1655 : // Entities not with positions in the world are never visible
1656 0 : if (ent.GetId() == INVALID_ENTITY)
1657 0 : return LosVisibility::HIDDEN;
1658 0 : CmpPtr<ICmpPosition> cmpPosition(ent);
1659 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1660 0 : return LosVisibility::HIDDEN;
1661 :
1662 : // Mirage entities, whatever the situation, are visible for one specific player
1663 0 : CmpPtr<ICmpMirage> cmpMirage(ent);
1664 0 : if (cmpMirage && cmpMirage->GetPlayer() != player)
1665 0 : return LosVisibility::HIDDEN;
1666 :
1667 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
1668 0 : int i = (pos.X / LOS_TILE_SIZE).ToInt_RoundToNearest();
1669 0 : int j = (pos.Y / LOS_TILE_SIZE).ToInt_RoundToNearest();
1670 :
1671 : // Reveal flag makes all positioned entities visible and all mirages useless
1672 0 : if (GetLosRevealAll(player))
1673 : {
1674 0 : if (LosIsOffWorld(i, j) || cmpMirage)
1675 0 : return LosVisibility::HIDDEN;
1676 0 : return LosVisibility::VISIBLE;
1677 : }
1678 :
1679 : // Get visible regions
1680 0 : CLosQuerier los(GetSharedLosMask(player), m_LosState, m_LosVerticesPerSide);
1681 :
1682 0 : CmpPtr<ICmpVisibility> cmpVisibility(ent);
1683 :
1684 : // Possibly ask the scripted Visibility component
1685 0 : EntityMap<EntityData>::const_iterator it = m_EntityData.find(ent.GetId());
1686 0 : if (it != m_EntityData.end())
1687 : {
1688 0 : if (it->second.HasFlag<FlagMasks::ScriptedVisibility>() && cmpVisibility)
1689 0 : return cmpVisibility->GetVisibility(player, los.IsVisible(i, j), los.IsExplored(i, j));
1690 : }
1691 : else
1692 : {
1693 0 : if (cmpVisibility && cmpVisibility->IsActivated())
1694 0 : return cmpVisibility->GetVisibility(player, los.IsVisible(i, j), los.IsExplored(i, j));
1695 : }
1696 :
1697 : // Else, default behavior
1698 :
1699 0 : if (los.IsVisible(i, j))
1700 : {
1701 0 : if (cmpMirage)
1702 0 : return LosVisibility::HIDDEN;
1703 :
1704 0 : return LosVisibility::VISIBLE;
1705 : }
1706 :
1707 0 : if (!los.IsExplored(i, j))
1708 0 : return LosVisibility::HIDDEN;
1709 :
1710 : // Invisible if the 'retain in fog' flag is not set, and in a non-visible explored region
1711 : // Try using the 'retainInFog' flag in m_EntityData to save a script call
1712 0 : if (it != m_EntityData.end())
1713 : {
1714 0 : if (!it->second.HasFlag<FlagMasks::RetainInFog>())
1715 0 : return LosVisibility::HIDDEN;
1716 : }
1717 : else
1718 : {
1719 0 : if (!(cmpVisibility && cmpVisibility->GetRetainInFog()))
1720 0 : return LosVisibility::HIDDEN;
1721 : }
1722 :
1723 0 : if (cmpMirage)
1724 0 : return LosVisibility::FOGGED;
1725 :
1726 0 : CmpPtr<ICmpOwnership> cmpOwnership(ent);
1727 0 : if (!cmpOwnership)
1728 0 : return LosVisibility::FOGGED;
1729 :
1730 0 : if (cmpOwnership->GetOwner() == player)
1731 : {
1732 0 : CmpPtr<ICmpFogging> cmpFogging(ent);
1733 0 : if (!(cmpFogging && cmpFogging->IsMiraged(player)))
1734 0 : return LosVisibility::FOGGED;
1735 :
1736 0 : return LosVisibility::HIDDEN;
1737 : }
1738 :
1739 : // Fogged entities are hidden in two cases:
1740 : // - They were not scouted
1741 : // - A mirage replaces them
1742 0 : CmpPtr<ICmpFogging> cmpFogging(ent);
1743 0 : if (cmpFogging && cmpFogging->IsActivated() &&
1744 0 : (!cmpFogging->WasSeen(player) || cmpFogging->IsMiraged(player)))
1745 0 : return LosVisibility::HIDDEN;
1746 :
1747 0 : return LosVisibility::FOGGED;
1748 : }
1749 :
1750 0 : LosVisibility ComputeLosVisibility(entity_id_t ent, player_id_t player) const
1751 : {
1752 0 : CEntityHandle handle = GetSimContext().GetComponentManager().LookupEntityHandle(ent);
1753 0 : return ComputeLosVisibility(handle, player);
1754 : }
1755 :
1756 0 : LosVisibility GetLosVisibility(CEntityHandle ent, player_id_t player) const override
1757 : {
1758 0 : entity_id_t entId = ent.GetId();
1759 :
1760 : // Entities not with positions in the world are never visible
1761 0 : if (entId == INVALID_ENTITY)
1762 0 : return LosVisibility::HIDDEN;
1763 :
1764 0 : CmpPtr<ICmpPosition> cmpPosition(ent);
1765 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1766 0 : return LosVisibility::HIDDEN;
1767 :
1768 : // Gaia and observers do not have a visibility cache
1769 0 : if (player <= 0)
1770 0 : return ComputeLosVisibility(ent, player);
1771 :
1772 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
1773 :
1774 0 : if (IsVisibilityDirty(m_DirtyVisibility[PosToLosRegionsHelper(pos.X, pos.Y)], player))
1775 0 : return ComputeLosVisibility(ent, player);
1776 :
1777 0 : if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), entId) != m_ModifiedEntities.end())
1778 0 : return ComputeLosVisibility(ent, player);
1779 :
1780 0 : EntityMap<EntityData>::const_iterator it = m_EntityData.find(entId);
1781 0 : if (it == m_EntityData.end())
1782 0 : return ComputeLosVisibility(ent, player);
1783 :
1784 0 : return static_cast<LosVisibility>(GetPlayerVisibility(it->second.visibilities, player));
1785 : }
1786 :
1787 0 : LosVisibility GetLosVisibility(entity_id_t ent, player_id_t player) const override
1788 : {
1789 0 : CEntityHandle handle = GetSimContext().GetComponentManager().LookupEntityHandle(ent);
1790 0 : return GetLosVisibility(handle, player);
1791 : }
1792 :
1793 0 : LosVisibility GetLosVisibilityPosition(entity_pos_t x, entity_pos_t z, player_id_t player) const override
1794 : {
1795 0 : int i = (x / LOS_TILE_SIZE).ToInt_RoundToNearest();
1796 0 : int j = (z / LOS_TILE_SIZE).ToInt_RoundToNearest();
1797 :
1798 : // Reveal flag makes all positioned entities visible and all mirages useless
1799 0 : if (GetLosRevealAll(player))
1800 : {
1801 0 : if (LosIsOffWorld(i, j))
1802 0 : return LosVisibility::HIDDEN;
1803 : else
1804 0 : return LosVisibility::VISIBLE;
1805 : }
1806 :
1807 : // Get visible regions
1808 0 : CLosQuerier los(GetSharedLosMask(player), m_LosState, m_LosVerticesPerSide);
1809 :
1810 0 : if (los.IsVisible(i,j))
1811 0 : return LosVisibility::VISIBLE;
1812 0 : if (los.IsExplored(i,j))
1813 0 : return LosVisibility::FOGGED;
1814 0 : return LosVisibility::HIDDEN;
1815 : }
1816 :
1817 0 : size_t GetVerticesPerSide() const override
1818 : {
1819 0 : return m_LosVerticesPerSide;
1820 : }
1821 :
1822 6085928 : LosRegion LosVertexToLosRegionsHelper(u16 x, u16 z) const
1823 : {
1824 12171856 : return LosRegion {
1825 12171856 : Clamp(x/LOS_REGION_RATIO, 0, m_LosRegionsPerSide - 1),
1826 12171856 : Clamp(z/LOS_REGION_RATIO, 0, m_LosRegionsPerSide - 1)
1827 12171856 : };
1828 : }
1829 :
1830 3106 : LosRegion PosToLosRegionsHelper(entity_pos_t x, entity_pos_t z) const
1831 : {
1832 6212 : u16 i = Clamp(
1833 6212 : (x/(LOS_TILE_SIZE*LOS_REGION_RATIO)).ToInt_RoundToZero(),
1834 : 0,
1835 6212 : m_LosRegionsPerSide - 1);
1836 6212 : u16 j = Clamp(
1837 6212 : (z/(LOS_TILE_SIZE*LOS_REGION_RATIO)).ToInt_RoundToZero(),
1838 : 0,
1839 6212 : m_LosRegionsPerSide - 1);
1840 3106 : return std::make_pair(i, j);
1841 : }
1842 :
1843 2061 : void AddToRegion(LosRegion region, entity_id_t ent)
1844 : {
1845 2061 : m_LosRegions[region].insert(ent);
1846 2061 : }
1847 :
1848 1025 : void RemoveFromRegion(LosRegion region, entity_id_t ent)
1849 : {
1850 1025 : std::set<entity_id_t>::const_iterator regionIt = m_LosRegions[region].find(ent);
1851 1025 : if (regionIt != m_LosRegions[region].end())
1852 1025 : m_LosRegions[region].erase(regionIt);
1853 1025 : }
1854 :
1855 0 : void UpdateVisibilityData()
1856 : {
1857 0 : PROFILE("UpdateVisibilityData");
1858 :
1859 0 : for (u16 i = 0; i < m_LosRegionsPerSide; ++i)
1860 0 : for (u16 j = 0; j < m_LosRegionsPerSide; ++j)
1861 : {
1862 0 : LosRegion pos{i, j};
1863 0 : for (player_id_t player = 1; player < MAX_LOS_PLAYER_ID + 1; ++player)
1864 0 : if (IsVisibilityDirty(m_DirtyVisibility[pos], player) || m_GlobalPlayerVisibilityUpdate[player-1] == 1 || m_GlobalVisibilityUpdate)
1865 0 : for (const entity_id_t& ent : m_LosRegions[pos])
1866 0 : UpdateVisibility(ent, player);
1867 :
1868 0 : m_DirtyVisibility[pos] = 0;
1869 : }
1870 :
1871 0 : std::fill(m_GlobalPlayerVisibilityUpdate.begin(), m_GlobalPlayerVisibilityUpdate.end(), false);
1872 0 : m_GlobalVisibilityUpdate = false;
1873 :
1874 : // Calling UpdateVisibility can modify m_ModifiedEntities, so be careful:
1875 : // infinite loops could be triggered by feedback between entities and their mirages.
1876 0 : std::map<entity_id_t, u8> attempts;
1877 0 : while (!m_ModifiedEntities.empty())
1878 : {
1879 0 : entity_id_t ent = m_ModifiedEntities.back();
1880 0 : m_ModifiedEntities.pop_back();
1881 :
1882 0 : ++attempts[ent];
1883 0 : ENSURE(attempts[ent] < 100 && "Infinite loop in UpdateVisibilityData");
1884 :
1885 0 : UpdateVisibility(ent);
1886 : }
1887 0 : }
1888 :
1889 1038 : void RequestVisibilityUpdate(entity_id_t ent) override
1890 : {
1891 1038 : if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), ent) == m_ModifiedEntities.end())
1892 3 : m_ModifiedEntities.push_back(ent);
1893 1038 : }
1894 :
1895 0 : void UpdateVisibility(entity_id_t ent, player_id_t player)
1896 : {
1897 0 : EntityMap<EntityData>::iterator itEnts = m_EntityData.find(ent);
1898 0 : if (itEnts == m_EntityData.end())
1899 0 : return;
1900 :
1901 0 : LosVisibility oldVis = GetPlayerVisibility(itEnts->second.visibilities, player);
1902 0 : LosVisibility newVis = ComputeLosVisibility(itEnts->first, player);
1903 :
1904 0 : if (oldVis == newVis)
1905 0 : return;
1906 :
1907 0 : itEnts->second.visibilities = (itEnts->second.visibilities & ~(0x3 << 2 * (player - 1))) | ((u8)newVis << 2 * (player - 1));
1908 :
1909 0 : CMessageVisibilityChanged msg(player, ent, static_cast<int>(oldVis), static_cast<int>(newVis));
1910 0 : GetSimContext().GetComponentManager().PostMessage(ent, msg);
1911 : }
1912 :
1913 0 : void UpdateVisibility(entity_id_t ent)
1914 : {
1915 0 : for (player_id_t player = 1; player < MAX_LOS_PLAYER_ID + 1; ++player)
1916 0 : UpdateVisibility(ent, player);
1917 0 : }
1918 :
1919 0 : void SetLosRevealAll(player_id_t player, bool enabled) override
1920 : {
1921 0 : if (player == -1)
1922 0 : m_LosRevealAll[MAX_LOS_PLAYER_ID+1] = enabled;
1923 : else
1924 : {
1925 0 : ENSURE(player >= 0 && player <= MAX_LOS_PLAYER_ID);
1926 0 : m_LosRevealAll[player] = enabled;
1927 : }
1928 :
1929 : // On next update, update the visibility of every entity in the world
1930 0 : m_GlobalVisibilityUpdate = true;
1931 0 : }
1932 :
1933 0 : bool GetLosRevealAll(player_id_t player) const override
1934 : {
1935 : // Special player value can force reveal-all for every player
1936 0 : if (m_LosRevealAll[MAX_LOS_PLAYER_ID+1] || player == -1)
1937 0 : return true;
1938 0 : ENSURE(player >= 0 && player <= MAX_LOS_PLAYER_ID+1);
1939 : // Otherwise check the player-specific flag
1940 0 : if (m_LosRevealAll[player])
1941 0 : return true;
1942 :
1943 0 : return false;
1944 : }
1945 :
1946 0 : void SetLosCircular(bool enabled) override
1947 : {
1948 0 : m_LosCircular = enabled;
1949 :
1950 0 : ResetDerivedData();
1951 0 : }
1952 :
1953 0 : bool GetLosCircular() const override
1954 : {
1955 0 : return m_LosCircular;
1956 : }
1957 :
1958 0 : void SetSharedLos(player_id_t player, const std::vector<player_id_t>& players) override
1959 : {
1960 0 : m_SharedLosMasks[player] = CalcSharedLosMask(players);
1961 :
1962 : // Units belonging to any of 'players' can now trigger visibility updates for 'player'.
1963 : // If shared LOS partners have been removed, we disable visibility updates from them
1964 : // in order to improve performance. That also allows us to properly determine whether
1965 : // 'player' needs a global visibility update for this turn.
1966 0 : bool modified = false;
1967 :
1968 0 : for (player_id_t p = 1; p < MAX_LOS_PLAYER_ID+1; ++p)
1969 : {
1970 0 : bool inList = std::find(players.begin(), players.end(), p) != players.end();
1971 :
1972 0 : if (SetPlayerSharedDirtyVisibilityBit(m_SharedDirtyVisibilityMasks[p], player, inList))
1973 0 : modified = true;
1974 : }
1975 :
1976 0 : if (modified && (size_t)player <= m_GlobalPlayerVisibilityUpdate.size())
1977 0 : m_GlobalPlayerVisibilityUpdate[player-1] = 1;
1978 0 : }
1979 :
1980 0 : u32 GetSharedLosMask(player_id_t player) const override
1981 : {
1982 0 : return m_SharedLosMasks[player];
1983 : }
1984 :
1985 0 : void ExploreMap(player_id_t p) override
1986 : {
1987 0 : for (i32 j = 0; j < m_LosVerticesPerSide; ++j)
1988 0 : for (i32 i = 0; i < m_LosVerticesPerSide; ++i)
1989 : {
1990 0 : if (LosIsOffWorld(i,j))
1991 0 : continue;
1992 0 : u32 &explored = m_ExploredVertices.at(p);
1993 0 : explored += !(m_LosState.get(i, j) & ((u32)LosState::EXPLORED << (2*(p-1))));
1994 0 : m_LosState.get(i, j) |= ((u32)LosState::EXPLORED << (2*(p-1)));
1995 : }
1996 :
1997 0 : SeeExploredEntities(p);
1998 0 : }
1999 :
2000 0 : void ExploreTerritories() override
2001 : {
2002 0 : PROFILE3("ExploreTerritories");
2003 :
2004 0 : CmpPtr<ICmpTerritoryManager> cmpTerritoryManager(GetSystemEntity());
2005 0 : const Grid<u8>& grid = cmpTerritoryManager->GetTerritoryGrid();
2006 :
2007 : // Territory data is stored per territory-tile (typically a multiple of terrain-tiles).
2008 : // LOS data is stored per los vertex (in reality tiles too, but it's the center that matters).
2009 : // This scales from LOS coordinates to Territory coordinates.
2010 0 : auto scale = [](i32 coord, i32 max) -> i32 {
2011 0 : return std::min(max, (coord * LOS_TILE_SIZE + LOS_TILE_SIZE / 2) / (ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE * Pathfinding::NAVCELL_SIZE_INT));
2012 0 : };
2013 :
2014 : // For each territory-tile, if it is owned by a valid player then update the LOS
2015 : // for every vertex inside/around that tile, to mark them as explored.
2016 0 : for (i32 j = 0; j < m_LosVerticesPerSide; ++j)
2017 0 : for (i32 i = 0; i < m_LosVerticesPerSide; ++i)
2018 : {
2019 : // TODO: This fetches data redundantly if the los grid is smaller than the territory grid
2020 : // (but it's unlikely to matter much).
2021 0 : u8 p = grid.get(scale(i, grid.width() - 1), scale(j, grid.height() - 1)) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK;
2022 0 : if (p > 0 && p <= MAX_LOS_PLAYER_ID)
2023 : {
2024 0 : u32& explored = m_ExploredVertices.at(p);
2025 :
2026 0 : if (LosIsOffWorld(i, j))
2027 0 : continue;
2028 :
2029 0 : u32& losState = m_LosState.get(i, j);
2030 0 : if (!(losState & ((u32)LosState::EXPLORED << (2*(p-1)))))
2031 : {
2032 0 : ++explored;
2033 0 : losState |= ((u32)LosState::EXPLORED << (2*(p-1)));
2034 : }
2035 : }
2036 : }
2037 :
2038 0 : for (player_id_t p = 1; p < MAX_LOS_PLAYER_ID+1; ++p)
2039 0 : SeeExploredEntities(p);
2040 0 : }
2041 :
2042 : /**
2043 : * Force any entity in explored territory to appear for player p.
2044 : * This is useful for miraging entities inside the territory borders at the beginning of a game,
2045 : * or if the "Explore Map" option has been set.
2046 : */
2047 0 : void SeeExploredEntities(player_id_t p) const
2048 : {
2049 : // Warning: Code related to fogging (like ForceMiraging) shouldn't be
2050 : // invoked while iterating through m_EntityData.
2051 : // Otherwise, by deleting mirage entities and so on, that code will
2052 : // change the indexes in the map, leading to segfaults.
2053 : // So we just remember what entities to mirage and do that later.
2054 0 : std::vector<entity_id_t> miragableEntities;
2055 :
2056 0 : for (EntityMap<EntityData>::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it)
2057 : {
2058 0 : CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), it->first);
2059 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
2060 0 : continue;
2061 :
2062 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
2063 0 : int i = (pos.X / LOS_TILE_SIZE).ToInt_RoundToNearest();
2064 0 : int j = (pos.Y / LOS_TILE_SIZE).ToInt_RoundToNearest();
2065 :
2066 0 : CLosQuerier los(GetSharedLosMask(p), m_LosState, m_LosVerticesPerSide);
2067 0 : if (!los.IsExplored(i,j) || los.IsVisible(i,j))
2068 0 : continue;
2069 :
2070 0 : CmpPtr<ICmpFogging> cmpFogging(GetSimContext(), it->first);
2071 0 : if (cmpFogging)
2072 0 : miragableEntities.push_back(it->first);
2073 : }
2074 :
2075 0 : for (std::vector<entity_id_t>::iterator it = miragableEntities.begin(); it != miragableEntities.end(); ++it)
2076 : {
2077 0 : CmpPtr<ICmpFogging> cmpFogging(GetSimContext(), *it);
2078 0 : ENSURE(cmpFogging && "Impossible to retrieve Fogging component, previously achieved");
2079 0 : cmpFogging->ForceMiraging(p);
2080 : }
2081 0 : }
2082 :
2083 0 : void RevealShore(player_id_t p, bool enable) override
2084 : {
2085 0 : if (p <= 0 || p > MAX_LOS_PLAYER_ID)
2086 0 : return;
2087 :
2088 : // Maximum distance to the shore
2089 0 : const u16 maxdist = 10;
2090 :
2091 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
2092 0 : const Grid<u16>& shoreGrid = cmpPathfinder->ComputeShoreGrid(true);
2093 0 : ENSURE(shoreGrid.m_W == m_LosVerticesPerSide-1 && shoreGrid.m_H == m_LosVerticesPerSide-1);
2094 :
2095 0 : Grid<u16>& counts = m_LosPlayerCounts.at(p);
2096 0 : ENSURE(!counts.blank());
2097 :
2098 0 : for (u16 j = 0; j < shoreGrid.m_H; ++j)
2099 0 : for (u16 i = 0; i < shoreGrid.m_W; ++i)
2100 : {
2101 0 : u16 shoredist = shoreGrid.get(i, j);
2102 0 : if (shoredist > maxdist)
2103 0 : continue;
2104 :
2105 : // Maybe we could be more clever and don't add dummy strips of one tile
2106 0 : if (enable)
2107 0 : LosAddStripHelper(p, i, i, j, counts);
2108 : else
2109 0 : LosRemoveStripHelper(p, i, i, j, counts);
2110 : }
2111 : }
2112 :
2113 : /**
2114 : * Returns whether the given vertex is outside the normal bounds of the world
2115 : * (i.e. outside the range of a circular map)
2116 : */
2117 36092680 : inline bool LosIsOffWorld(ssize_t i, ssize_t j) const
2118 : {
2119 36092680 : if (m_LosCircular)
2120 : {
2121 : // With a circular map, vertex is off-world if hypot(i - size/2, j - size/2) >= size/2:
2122 :
2123 0 : ssize_t dist2 = (i - m_LosVerticesPerSide/2)*(i - m_LosVerticesPerSide/2)
2124 0 : + (j - m_LosVerticesPerSide/2)*(j - m_LosVerticesPerSide/2);
2125 :
2126 0 : ssize_t r = m_LosVerticesPerSide / 2 - MAP_EDGE_TILES + 1;
2127 : // subtract a bit from the radius to ensure nice
2128 : // SoD blurring around the edges of the map
2129 :
2130 0 : return (dist2 >= r*r);
2131 : }
2132 : else
2133 : {
2134 : // With a square map, the outermost edge of the map should be off-world,
2135 : // so the SoD texture blends out nicely
2136 69751280 : return i < MAP_EDGE_TILES || j < MAP_EDGE_TILES ||
2137 104248018 : i >= m_LosVerticesPerSide - MAP_EDGE_TILES ||
2138 69771987 : j >= m_LosVerticesPerSide - MAP_EDGE_TILES;
2139 : }
2140 : }
2141 :
2142 : /**
2143 : * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive).
2144 : */
2145 64500 : inline void LosAddStripHelper(u8 owner, i32 i0, i32 i1, i32 j, Grid<u16>& counts)
2146 : {
2147 64500 : if (i1 < i0)
2148 1408 : return;
2149 :
2150 63092 : u32 &explored = m_ExploredVertices.at(owner);
2151 1609336 : for (i32 i = i0; i <= i1; ++i)
2152 : {
2153 : // Increasing from zero to non-zero - move from unexplored/explored to visible+explored
2154 1546244 : if (counts.get(i, j) == 0)
2155 : {
2156 1545964 : if (!LosIsOffWorld(i, j))
2157 : {
2158 1490077 : explored += !(m_LosState.get(i, j) & ((u32)LosState::EXPLORED << (2*(owner-1))));
2159 1490077 : m_LosState.get(i, j) |= (((int)LosState::VISIBLE | (u32)LosState::EXPLORED) << (2*(owner-1)));
2160 : }
2161 :
2162 1545964 : MarkVisibilityDirtyAroundTile(owner, i, j);
2163 : }
2164 :
2165 1546244 : ENSURE(counts.get(i, j) < std::numeric_limits<u16>::max());
2166 1546244 : counts.get(i, j) = (u16)(counts.get(i, j) + 1); // ignore overflow; the player should never have 64K units
2167 : }
2168 : }
2169 :
2170 : /**
2171 : * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive).
2172 : */
2173 32906 : inline void LosRemoveStripHelper(u8 owner, i32 i0, i32 i1, i32 j, Grid<u16>& counts)
2174 : {
2175 32906 : if (i1 < i0)
2176 1451 : return;
2177 :
2178 791616 : for (i32 i = i0; i <= i1; ++i)
2179 : {
2180 760161 : ASSERT(counts.get(i, j) > 0);
2181 760161 : counts.get(i, j) = (u16)(counts.get(i, j) - 1);
2182 :
2183 : // Decreasing from non-zero to zero - move from visible+explored to explored
2184 760161 : if (counts.get(i, j) == 0)
2185 : {
2186 : // (If LosIsOffWorld then this is a no-op, so don't bother doing the check)
2187 760161 : m_LosState.get(i, j) &= ~((int)LosState::VISIBLE << (2*(owner-1)));
2188 :
2189 760161 : MarkVisibilityDirtyAroundTile(owner, i, j);
2190 : }
2191 : }
2192 : }
2193 :
2194 2306125 : inline void MarkVisibilityDirtyAroundTile(u8 owner, i32 i, i32 j)
2195 : {
2196 : // If we're still in the deserializing process, we must not modify m_DirtyVisibility
2197 2306125 : if (m_Deserializing)
2198 784643 : return;
2199 :
2200 : // Mark the LoS regions around the updated vertex
2201 : // 1: left-up, 2: right-up, 3: left-down, 4: right-down
2202 1521482 : LosRegion n1 = LosVertexToLosRegionsHelper(i-1, j-1);
2203 1521482 : LosRegion n2 = LosVertexToLosRegionsHelper(i-1, j);
2204 1521482 : LosRegion n3 = LosVertexToLosRegionsHelper(i, j-1);
2205 1521482 : LosRegion n4 = LosVertexToLosRegionsHelper(i, j);
2206 :
2207 1521482 : u16 sharedDirtyVisibilityMask = m_SharedDirtyVisibilityMasks[owner];
2208 :
2209 1521482 : if (j > 0 && i > 0)
2210 1521482 : m_DirtyVisibility[n1] |= sharedDirtyVisibilityMask;
2211 1521482 : if (n2 != n1 && j > 0 && i < m_LosVerticesPerSide)
2212 184151 : m_DirtyVisibility[n2] |= sharedDirtyVisibilityMask;
2213 1521482 : if (n3 != n1 && j < m_LosVerticesPerSide && i > 0)
2214 184542 : m_DirtyVisibility[n3] |= sharedDirtyVisibilityMask;
2215 1521482 : if (n4 != n1 && j < m_LosVerticesPerSide && i < m_LosVerticesPerSide)
2216 346321 : m_DirtyVisibility[n4] |= sharedDirtyVisibilityMask;
2217 : }
2218 :
2219 : /**
2220 : * Update the LOS state of tiles within a given circular range,
2221 : * either adding or removing visibility depending on the template parameter.
2222 : * Assumes owner is in the valid range.
2223 : */
2224 : template<bool adding>
2225 3002 : void LosUpdateHelper(u8 owner, entity_pos_t visionRange, CFixedVector2D pos)
2226 : {
2227 3002 : if (m_LosVerticesPerSide == 0) // do nothing if not initialised yet
2228 0 : return;
2229 :
2230 6004 : PROFILE("LosUpdateHelper");
2231 :
2232 3002 : Grid<u16>& counts = m_LosPlayerCounts.at(owner);
2233 :
2234 : // Lazy initialisation of counts:
2235 3002 : if (counts.blank())
2236 1041 : counts.resize(m_LosVerticesPerSide, m_LosVerticesPerSide);
2237 :
2238 : // Compute the circular region as a series of strips.
2239 : // Rather than quantise pos to vertexes, we do more precise sub-tile computations
2240 : // to get smoother behaviour as a unit moves rather than jumping a whole tile
2241 : // at once.
2242 : // To avoid the cost of sqrt when computing the outline of the circle,
2243 : // we loop from the bottom to the top and estimate the width of the current
2244 : // strip based on the previous strip, then adjust each end of the strip
2245 : // inwards or outwards until it's the widest that still falls within the circle.
2246 :
2247 : // Compute top/bottom coordinates, and clamp to exclude the 1-tile border around the map
2248 : // (so that we never render the sharp edge of the map)
2249 3002 : i32 j0 = ((pos.Y - visionRange)/LOS_TILE_SIZE).ToInt_RoundToInfinity();
2250 3002 : i32 j1 = ((pos.Y + visionRange)/LOS_TILE_SIZE).ToInt_RoundToNegInfinity();
2251 3002 : i32 j0clamp = std::max(j0, 1);
2252 3002 : i32 j1clamp = std::min(j1, m_LosVerticesPerSide-2);
2253 :
2254 : // Translate world coordinates into fractional tile-space coordinates
2255 3002 : entity_pos_t x = pos.X / LOS_TILE_SIZE;
2256 3002 : entity_pos_t y = pos.Y / LOS_TILE_SIZE;
2257 3002 : entity_pos_t r = visionRange / LOS_TILE_SIZE;
2258 3002 : entity_pos_t r2 = r.Square();
2259 :
2260 : // Compute the integers on either side of x
2261 3002 : i32 xfloor = (x - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity();
2262 3002 : i32 xceil = (x + entity_pos_t::Epsilon()).ToInt_RoundToInfinity();
2263 :
2264 : // Initialise the strip (i0, i1) to a rough guess
2265 3002 : i32 i0 = xfloor;
2266 3002 : i32 i1 = xceil;
2267 :
2268 94638 : for (i32 j = j0clamp; j <= j1clamp; ++j)
2269 : {
2270 : // Adjust i0 and i1 to be the outermost values that don't exceed
2271 : // the circle's radius (i.e. require dy^2 + dx^2 <= r^2).
2272 : // When moving the points inwards, clamp them to xceil+1 or xfloor-1
2273 : // so they don't accidentally shoot off in the wrong direction forever.
2274 :
2275 91636 : entity_pos_t dy = entity_pos_t::FromInt(j) - y;
2276 91636 : entity_pos_t dy2 = dy.Square();
2277 184556 : while (dy2 + (entity_pos_t::FromInt(i0-1) - x).Square() <= r2)
2278 46460 : --i0;
2279 159206 : while (i0 < xceil && dy2 + (entity_pos_t::FromInt(i0) - x).Square() > r2)
2280 33785 : ++i0;
2281 184860 : while (dy2 + (entity_pos_t::FromInt(i1+1) - x).Square() <= r2)
2282 46612 : ++i1;
2283 159334 : while (i1 > xfloor && dy2 + (entity_pos_t::FromInt(i1) - x).Square() > r2)
2284 33849 : --i1;
2285 :
2286 : #if DEBUG_RANGE_MANAGER_BOUNDS
2287 : if (i0 <= i1)
2288 : {
2289 : ENSURE(dy2 + (entity_pos_t::FromInt(i0) - x).Square() <= r2);
2290 : ENSURE(dy2 + (entity_pos_t::FromInt(i1) - x).Square() <= r2);
2291 : }
2292 : ENSURE(dy2 + (entity_pos_t::FromInt(i0 - 1) - x).Square() > r2);
2293 : ENSURE(dy2 + (entity_pos_t::FromInt(i1 + 1) - x).Square() > r2);
2294 : #endif
2295 :
2296 : // Clamp the strip to exclude the 1-tile border,
2297 : // then add or remove the strip as requested
2298 91636 : i32 i0clamp = std::max(i0, 1);
2299 91636 : i32 i1clamp = std::min(i1, m_LosVerticesPerSide-2);
2300 : if (adding)
2301 61628 : LosAddStripHelper(owner, i0clamp, i1clamp, j, counts);
2302 : else
2303 30008 : LosRemoveStripHelper(owner, i0clamp, i1clamp, j, counts);
2304 : }
2305 : }
2306 :
2307 : /**
2308 : * Update the LOS state of tiles within a given circular range,
2309 : * by removing visibility around the 'from' position
2310 : * and then adding visibility around the 'to' position.
2311 : */
2312 59 : void LosUpdateHelperIncremental(u8 owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to)
2313 : {
2314 59 : if (m_LosVerticesPerSide == 0) // do nothing if not initialised yet
2315 0 : return;
2316 :
2317 118 : PROFILE("LosUpdateHelperIncremental");
2318 :
2319 59 : Grid<u16>& counts = m_LosPlayerCounts.at(owner);
2320 :
2321 : // Lazy initialisation of counts:
2322 59 : if (counts.blank())
2323 0 : counts.resize(m_LosVerticesPerSide, m_LosVerticesPerSide);
2324 :
2325 : // See comments in LosUpdateHelper.
2326 : // This does exactly the same, except computing the strips for
2327 : // both circles simultaneously.
2328 : // (The idea is that the circles will be heavily overlapping,
2329 : // so we can compute the difference between the removed/added strips
2330 : // and only have to touch tiles that have a net change.)
2331 :
2332 59 : i32 j0_from = ((from.Y - visionRange)/LOS_TILE_SIZE).ToInt_RoundToInfinity();
2333 59 : i32 j1_from = ((from.Y + visionRange)/LOS_TILE_SIZE).ToInt_RoundToNegInfinity();
2334 59 : i32 j0_to = ((to.Y - visionRange)/LOS_TILE_SIZE).ToInt_RoundToInfinity();
2335 59 : i32 j1_to = ((to.Y + visionRange)/LOS_TILE_SIZE).ToInt_RoundToNegInfinity();
2336 59 : i32 j0clamp = std::max(std::min(j0_from, j0_to), 1);
2337 59 : i32 j1clamp = std::min(std::max(j1_from, j1_to), m_LosVerticesPerSide-2);
2338 :
2339 59 : entity_pos_t x_from = from.X / LOS_TILE_SIZE;
2340 59 : entity_pos_t y_from = from.Y / LOS_TILE_SIZE;
2341 59 : entity_pos_t x_to = to.X / LOS_TILE_SIZE;
2342 59 : entity_pos_t y_to = to.Y / LOS_TILE_SIZE;
2343 59 : entity_pos_t r = visionRange / LOS_TILE_SIZE;
2344 59 : entity_pos_t r2 = r.Square();
2345 :
2346 59 : i32 xfloor_from = (x_from - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity();
2347 59 : i32 xceil_from = (x_from + entity_pos_t::Epsilon()).ToInt_RoundToInfinity();
2348 59 : i32 xfloor_to = (x_to - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity();
2349 59 : i32 xceil_to = (x_to + entity_pos_t::Epsilon()).ToInt_RoundToInfinity();
2350 :
2351 59 : i32 i0_from = xfloor_from;
2352 59 : i32 i1_from = xceil_from;
2353 59 : i32 i0_to = xfloor_to;
2354 59 : i32 i1_to = xceil_to;
2355 :
2356 2085 : for (i32 j = j0clamp; j <= j1clamp; ++j)
2357 : {
2358 2026 : entity_pos_t dy_from = entity_pos_t::FromInt(j) - y_from;
2359 2026 : entity_pos_t dy2_from = dy_from.Square();
2360 3874 : while (dy2_from + (entity_pos_t::FromInt(i0_from-1) - x_from).Square() <= r2)
2361 924 : --i0_from;
2362 3564 : while (i0_from < xceil_from && dy2_from + (entity_pos_t::FromInt(i0_from) - x_from).Square() > r2)
2363 769 : ++i0_from;
2364 3908 : while (dy2_from + (entity_pos_t::FromInt(i1_from+1) - x_from).Square() <= r2)
2365 941 : ++i1_from;
2366 3576 : while (i1_from > xfloor_from && dy2_from + (entity_pos_t::FromInt(i1_from) - x_from).Square() > r2)
2367 775 : --i1_from;
2368 :
2369 2026 : entity_pos_t dy_to = entity_pos_t::FromInt(j) - y_to;
2370 2026 : entity_pos_t dy2_to = dy_to.Square();
2371 3886 : while (dy2_to + (entity_pos_t::FromInt(i0_to-1) - x_to).Square() <= r2)
2372 930 : --i0_to;
2373 3528 : while (i0_to < xceil_to && dy2_to + (entity_pos_t::FromInt(i0_to) - x_to).Square() > r2)
2374 751 : ++i0_to;
2375 3896 : while (dy2_to + (entity_pos_t::FromInt(i1_to+1) - x_to).Square() <= r2)
2376 935 : ++i1_to;
2377 3530 : while (i1_to > xfloor_to && dy2_to + (entity_pos_t::FromInt(i1_to) - x_to).Square() > r2)
2378 752 : --i1_to;
2379 :
2380 : #if DEBUG_RANGE_MANAGER_BOUNDS
2381 : if (i0_from <= i1_from)
2382 : {
2383 : ENSURE(dy2_from + (entity_pos_t::FromInt(i0_from) - x_from).Square() <= r2);
2384 : ENSURE(dy2_from + (entity_pos_t::FromInt(i1_from) - x_from).Square() <= r2);
2385 : }
2386 : ENSURE(dy2_from + (entity_pos_t::FromInt(i0_from - 1) - x_from).Square() > r2);
2387 : ENSURE(dy2_from + (entity_pos_t::FromInt(i1_from + 1) - x_from).Square() > r2);
2388 : if (i0_to <= i1_to)
2389 : {
2390 : ENSURE(dy2_to + (entity_pos_t::FromInt(i0_to) - x_to).Square() <= r2);
2391 : ENSURE(dy2_to + (entity_pos_t::FromInt(i1_to) - x_to).Square() <= r2);
2392 : }
2393 : ENSURE(dy2_to + (entity_pos_t::FromInt(i0_to - 1) - x_to).Square() > r2);
2394 : ENSURE(dy2_to + (entity_pos_t::FromInt(i1_to + 1) - x_to).Square() > r2);
2395 : #endif
2396 :
2397 : // Check whether this strip moved at all
2398 2026 : if (!(i0_to == i0_from && i1_to == i1_from))
2399 : {
2400 1846 : i32 i0clamp_from = std::max(i0_from, 1);
2401 1846 : i32 i1clamp_from = std::min(i1_from, m_LosVerticesPerSide-2);
2402 1846 : i32 i0clamp_to = std::max(i0_to, 1);
2403 1846 : i32 i1clamp_to = std::min(i1_to, m_LosVerticesPerSide-2);
2404 :
2405 : // Check whether one strip is negative width,
2406 : // and we can just add/remove the entire other strip
2407 1846 : if (i1clamp_from < i0clamp_from)
2408 : {
2409 256 : LosAddStripHelper(owner, i0clamp_to, i1clamp_to, j, counts);
2410 : }
2411 1590 : else if (i1clamp_to < i0clamp_to)
2412 : {
2413 282 : LosRemoveStripHelper(owner, i0clamp_from, i1clamp_from, j, counts);
2414 : }
2415 : else
2416 : {
2417 : // There are four possible regions of overlap between the two strips
2418 : // (remove before add, remove after add, add before remove, add after remove).
2419 : // Process each of the regions as its own strip.
2420 : // (If this produces negative-width strips then they'll just get ignored
2421 : // which is fine.)
2422 : // (If the strips don't actually overlap (which is very rare with normal unit
2423 : // movement speeds), the region between them will be both added and removed,
2424 : // so we have to do the add first to avoid overflowing to -1 and triggering
2425 : // assertion failures.)
2426 1308 : LosAddStripHelper(owner, i0clamp_to, i0clamp_from-1, j, counts);
2427 1308 : LosAddStripHelper(owner, i1clamp_from+1, i1clamp_to, j, counts);
2428 1308 : LosRemoveStripHelper(owner, i0clamp_from, i0clamp_to-1, j, counts);
2429 1308 : LosRemoveStripHelper(owner, i1clamp_to+1, i1clamp_from, j, counts);
2430 : }
2431 : }
2432 : }
2433 : }
2434 :
2435 1044 : void LosAdd(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos)
2436 : {
2437 1044 : if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID)
2438 1 : return;
2439 :
2440 1043 : LosUpdateHelper<true>((u8)owner, visionRange, pos);
2441 : }
2442 :
2443 0 : void SharingLosAdd(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos)
2444 : {
2445 0 : if (visionRange.IsZero())
2446 0 : return;
2447 :
2448 0 : for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i)
2449 0 : if (HasVisionSharing(visionSharing, i))
2450 0 : LosAdd(i, visionRange, pos);
2451 : }
2452 :
2453 8 : void LosRemove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos)
2454 : {
2455 8 : if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID)
2456 1 : return;
2457 :
2458 7 : LosUpdateHelper<false>((u8)owner, visionRange, pos);
2459 : }
2460 :
2461 0 : void SharingLosRemove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos)
2462 : {
2463 0 : if (visionRange.IsZero())
2464 0 : return;
2465 :
2466 0 : for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i)
2467 0 : if (HasVisionSharing(visionSharing, i))
2468 0 : LosRemove(i, visionRange, pos);
2469 : }
2470 :
2471 1035 : void LosMove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to)
2472 : {
2473 1035 : if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID)
2474 0 : return;
2475 :
2476 1035 : if ((from - to).CompareLength(visionRange) > 0)
2477 : {
2478 : // If it's a very large move, then simply remove and add to the new position
2479 976 : LosUpdateHelper<false>((u8)owner, visionRange, from);
2480 976 : LosUpdateHelper<true>((u8)owner, visionRange, to);
2481 : }
2482 : else
2483 : // Otherwise use the version optimised for mostly-overlapping circles
2484 59 : LosUpdateHelperIncremental((u8)owner, visionRange, from, to);
2485 : }
2486 :
2487 0 : void SharingLosMove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to)
2488 : {
2489 0 : if (visionRange.IsZero())
2490 0 : return;
2491 :
2492 0 : for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i)
2493 0 : if (HasVisionSharing(visionSharing, i))
2494 0 : LosMove(i, visionRange, from, to);
2495 : }
2496 :
2497 0 : u8 GetPercentMapExplored(player_id_t player) const override
2498 : {
2499 0 : return m_ExploredVertices.at((u8)player) * 100 / m_TotalInworldVertices;
2500 : }
2501 :
2502 0 : u8 GetUnionPercentMapExplored(const std::vector<player_id_t>& players) const override
2503 : {
2504 0 : u32 exploredVertices = 0;
2505 0 : std::vector<player_id_t>::const_iterator playerIt;
2506 :
2507 0 : for (i32 j = 0; j < m_LosVerticesPerSide; j++)
2508 0 : for (i32 i = 0; i < m_LosVerticesPerSide; i++)
2509 : {
2510 0 : if (LosIsOffWorld(i, j))
2511 0 : continue;
2512 :
2513 0 : for (playerIt = players.begin(); playerIt != players.end(); ++playerIt)
2514 0 : if (m_LosState.get(i, j) & ((u32)LosState::EXPLORED << (2*((*playerIt)-1))))
2515 : {
2516 0 : exploredVertices += 1;
2517 0 : break;
2518 : }
2519 : }
2520 :
2521 0 : return exploredVertices * 100 / m_TotalInworldVertices;
2522 : }
2523 : };
2524 :
2525 119 : REGISTER_COMPONENT_TYPE(RangeManager)
|
