Changeset View
Changeset View
Standalone View
Standalone View
source/simulation2/components/CCmpRangeManager.h
- This file was added.
/* Copyright (C) 2022 Wildfire Games. | |||||
* This file is part of 0 A.D. | |||||
* | |||||
* 0 A.D. is free software: you can redistribute it and/or modify | |||||
* it under the terms of the GNU General Public License as published by | |||||
* the Free Software Foundation, either version 2 of the License, or | |||||
* (at your option) any later version. | |||||
* | |||||
* 0 A.D. is distributed in the hope that it will be useful, | |||||
* but WITHOUT ANY WARRANTY; without even the implied warranty of | |||||
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |||||
* GNU General Public License for more details. | |||||
* | |||||
* You should have received a copy of the GNU General Public License | |||||
* along with 0 A.D. If not, see <http://www.gnu.org/licenses/>. | |||||
*/ | |||||
#ifndef INCLUDED_CCMPRANGEMANAGER | |||||
#define INCLUDED_CCMPRANGEMANAGER | |||||
#include "ICmpRangeManager.h" | |||||
#include "graphics/Overlay.h" | |||||
#include "renderer/Scene.h" | |||||
#include "simulation2/helpers/Grid.h" | |||||
#include "simulation2/helpers/Los.h" | |||||
#include "simulation2/helpers/Spatial.h" | |||||
#include "simulation2/system/EntityMap.h" | |||||
#define DEBUG_RANGE_MANAGER_BOUNDS 0 | |||||
/** | |||||
* Range manager implementation. | |||||
* Maintains a list of all entities (and their positions and owners), which is used for | |||||
* queries. | |||||
* | |||||
* LOS implementation is based on the model described in GPG2. | |||||
* (TODO: would be nice to make it cleverer, so e.g. mountains and walls | |||||
* can block vision) | |||||
*/ | |||||
class CCmpRangeManager final : public ICmpRangeManager | |||||
{ | |||||
public: | |||||
/** | |||||
* Representation of a range query. | |||||
*/ | |||||
struct Query | |||||
{ | |||||
std::vector<entity_id_t> lastMatch; | |||||
CEntityHandle source; // TODO: this could crash if an entity is destroyed while a Query is still referencing it | |||||
entity_pos_t minRange; | |||||
entity_pos_t maxRange; | |||||
entity_pos_t yOrigin; // Used for parabolas only. | |||||
u32 ownersMask; | |||||
i32 interface; | |||||
u8 flagsMask; | |||||
bool enabled; | |||||
bool parabolic; | |||||
bool accountForSize; // If true, the query accounts for unit sizes, otherwise it treats all entities as points. | |||||
}; | |||||
/** | |||||
* Representation of an entity, with the data needed for queries. | |||||
*/ | |||||
enum class FlagMasks | |||||
{ | |||||
// flags used for queries | |||||
None = 0x00, | |||||
Normal = 0x01, | |||||
Injured = 0x02, | |||||
AllQuery = Normal | Injured, | |||||
// 0x04 reserved for future use | |||||
// general flags | |||||
InWorld = 0x08, | |||||
RetainInFog = 0x10, | |||||
RevealShore = 0x20, | |||||
ScriptedVisibility = 0x40, | |||||
SharedVision = 0x80 | |||||
}; | |||||
struct EntityData | |||||
{ | |||||
EntityData() : | |||||
visibilities(0), size(0), visionSharing(0), | |||||
owner(-1), flags{static_cast<u8>(FlagMasks::Normal)} | |||||
{ } | |||||
entity_pos_t x, z; | |||||
entity_pos_t visionRange; | |||||
u32 visibilities; // 2-bit visibility, per player | |||||
u32 size; | |||||
u16 visionSharing; // 1-bit per player | |||||
i8 owner; | |||||
u8 flags; // See the FlagMasks enum | |||||
template<FlagMasks mask> | |||||
bool HasFlag() const { return (flags & static_cast<int>(mask)) != 0; } | |||||
template<FlagMasks mask> | |||||
void SetFlag(bool val) { flags = val ? (flags | static_cast<int>(mask)) : | |||||
(flags & ~static_cast<int>(mask)); } | |||||
void SetFlag(u8 mask, bool val) { flags = val ? (flags | mask) : (flags & ~mask); } | |||||
}; | |||||
static constexpr int typeId{CID_RangeManager}; | |||||
static void ClassInit(CComponentManager& componentManager); | |||||
static IComponent* Allocate(const ScriptInterface&, JS::HandleValue); | |||||
static void Deallocate(IComponent* cmp); | |||||
int GetComponentTypeId() const override; | |||||
bool m_DebugOverlayEnabled; | |||||
bool m_DebugOverlayDirty; | |||||
std::vector<SOverlayLine> m_DebugOverlayLines; | |||||
// Deserialization flag. A lot of different functions are called by Deserialize() | |||||
// and we don't want to pass isDeserializing bool arguments to all of them... | |||||
bool m_Deserializing; | |||||
// World bounds (entities are expected to be within this range) | |||||
entity_pos_t m_WorldX0; | |||||
entity_pos_t m_WorldZ0; | |||||
entity_pos_t m_WorldX1; | |||||
entity_pos_t m_WorldZ1; | |||||
// Range query state: | |||||
tag_t m_QueryNext; // next allocated id | |||||
std::map<tag_t, Query> m_Queries; | |||||
EntityMap<EntityData> m_EntityData; | |||||
FastSpatialSubdivision m_Subdivision; // spatial index of m_EntityData | |||||
std::vector<entity_id_t> m_SubdivisionResults; | |||||
// LOS state: | |||||
static const player_id_t MAX_LOS_PLAYER_ID = 16; | |||||
using LosRegion = std::pair<u16, u16>; | |||||
std::array<bool, MAX_LOS_PLAYER_ID+2> m_LosRevealAll; | |||||
bool m_LosCircular; | |||||
i32 m_LosVerticesPerSide; | |||||
// Cache for visibility tracking | |||||
i32 m_LosRegionsPerSide; | |||||
bool m_GlobalVisibilityUpdate; | |||||
std::array<bool, MAX_LOS_PLAYER_ID> m_GlobalPlayerVisibilityUpdate; | |||||
Grid<u16> m_DirtyVisibility; | |||||
Grid<std::set<entity_id_t>> m_LosRegions; | |||||
// List of entities that must be updated, regardless of the status of their tile | |||||
std::vector<entity_id_t> m_ModifiedEntities; | |||||
// Counts of units seeing vertex, per vertex, per player (starting with player 0). | |||||
// Use u16 to avoid overflows when we have very large (but not infeasibly large) numbers | |||||
// of units in a very small area. | |||||
// (Note we use vertexes, not tiles, to better match the renderer.) | |||||
// Lazily constructed when it's needed, to save memory in smaller games. | |||||
std::array<Grid<u16>, MAX_LOS_PLAYER_ID> m_LosPlayerCounts; | |||||
// 2-bit LosState per player, starting with player 1 (not 0!) up to player MAX_LOS_PLAYER_ID (inclusive) | |||||
Grid<u32> m_LosState; | |||||
// Special static visibility data for the "reveal whole map" mode | |||||
// (TODO: this is usually a waste of memory) | |||||
Grid<u32> m_LosStateRevealed; | |||||
// Shared LOS masks, one per player. | |||||
std::array<u32, MAX_LOS_PLAYER_ID+2> m_SharedLosMasks; | |||||
// Shared dirty visibility masks, one per player. | |||||
std::array<u16, MAX_LOS_PLAYER_ID+2> m_SharedDirtyVisibilityMasks; | |||||
// Cache explored vertices per player (not serialized) | |||||
u32 m_TotalInworldVertices; | |||||
std::vector<u32> m_ExploredVertices; | |||||
static std::string GetSchema(); | |||||
void Init(const CParamNode& UNUSED(paramNode)) override; | |||||
void Deinit() override; | |||||
template<typename S> | |||||
void SerializeCommon(S& serialize) | |||||
{ | |||||
serialize.NumberFixed_Unbounded("world x0", m_WorldX0); | |||||
serialize.NumberFixed_Unbounded("world z0", m_WorldZ0); | |||||
serialize.NumberFixed_Unbounded("world x1", m_WorldX1); | |||||
serialize.NumberFixed_Unbounded("world z1", m_WorldZ1); | |||||
serialize.NumberU32_Unbounded("query next", m_QueryNext); | |||||
Serializer(serialize, "queries", m_Queries, GetSimContext()); | |||||
Serializer(serialize, "entity data", m_EntityData); | |||||
Serializer(serialize, "los reveal all", m_LosRevealAll); | |||||
serialize.Bool("los circular", m_LosCircular); | |||||
serialize.NumberI32_Unbounded("los verts per side", m_LosVerticesPerSide); | |||||
serialize.Bool("global visibility update", m_GlobalVisibilityUpdate); | |||||
Serializer(serialize, "global player visibility update", m_GlobalPlayerVisibilityUpdate); | |||||
Serializer(serialize, "dirty visibility", m_DirtyVisibility); | |||||
Serializer(serialize, "modified entities", m_ModifiedEntities); | |||||
// We don't serialize m_Subdivision, m_LosPlayerCounts or m_LosRegions | |||||
// since they can be recomputed from the entity data when deserializing; | |||||
// m_LosState must be serialized since it depends on the history of exploration | |||||
Serializer(serialize, "los state", m_LosState); | |||||
Serializer(serialize, "shared los masks", m_SharedLosMasks); | |||||
Serializer(serialize, "shared dirty visibility masks", m_SharedDirtyVisibilityMasks); | |||||
} | |||||
void Serialize(ISerializer& serialize) override; | |||||
void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) override; | |||||
void HandleMessage(const CMessage& msg, bool UNUSED(global)) override; | |||||
void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1) override; | |||||
void Verify() override; | |||||
FastSpatialSubdivision* GetSubdivision() override; | |||||
// Reinitialise subdivisions and LOS data, based on entity data | |||||
void ResetDerivedData(); | |||||
void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1); | |||||
tag_t CreateActiveQuery(entity_id_t source, | |||||
entity_pos_t minRange, entity_pos_t maxRange, const std::vector<int>& owners, | |||||
int requiredInterface, u8 flags, bool accountForSize) override; | |||||
tag_t CreateActiveParabolicQuery(entity_id_t source, | |||||
entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t yOrigin, | |||||
const std::vector<int>& owners, int requiredInterface, u8 flags) override; | |||||
void DestroyActiveQuery(tag_t tag) override; | |||||
void EnableActiveQuery(tag_t tag) override; | |||||
void DisableActiveQuery(tag_t tag) override; | |||||
bool IsActiveQueryEnabled(tag_t tag) const override; | |||||
std::vector<entity_id_t> ExecuteQueryAroundPos(const CFixedVector2D& pos, entity_pos_t minRange, | |||||
entity_pos_t maxRange, const std::vector<int>& owners, int requiredInterface, | |||||
bool accountForSize) override; | |||||
std::vector<entity_id_t> ExecuteQuery(entity_id_t source, entity_pos_t minRange, | |||||
entity_pos_t maxRange, const std::vector<int>& owners, int requiredInterface, | |||||
bool accountForSize) override; | |||||
std::vector<entity_id_t> ResetActiveQuery(tag_t tag) override; | |||||
std::vector<entity_id_t> GetEntitiesByPlayer(player_id_t player) const override; | |||||
std::vector<entity_id_t> GetNonGaiaEntities() const override; | |||||
std::vector<entity_id_t> GetGaiaAndNonGaiaEntities() const override; | |||||
std::vector<entity_id_t> GetEntitiesByMask(u32 ownerMask) const; | |||||
void SetDebugOverlay(bool enabled) override; | |||||
/** | |||||
* Update all currently-enabled active queries. | |||||
*/ | |||||
void ExecuteActiveQueries(); | |||||
/** | |||||
* Returns whether the given entity matches the given query (ignoring maxRange) | |||||
*/ | |||||
bool TestEntityQuery(const Query& q, entity_id_t id, const EntityData& entity) const; | |||||
/** | |||||
* Returns a list of distinct entity IDs that match the given query, sorted by ID. | |||||
*/ | |||||
void PerformQuery(const Query& q, std::vector<entity_id_t>& r, CFixedVector2D pos); | |||||
entity_pos_t GetEffectiveParabolicRange(entity_id_t source, entity_id_t target, entity_pos_t range, | |||||
entity_pos_t yOrigin) const override; | |||||
entity_pos_t GetElevationAdaptedRange(const CFixedVector3D& pos1, const CFixedVector3D& rot, | |||||
entity_pos_t range, entity_pos_t yOrigin, entity_pos_t angle) const override; | |||||
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; | |||||
Query ConstructQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, | |||||
const std::vector<int>& owners, int requiredInterface, u8 flagsMask, bool accountForSize) const; | |||||
Query ConstructParabolicQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, | |||||
entity_pos_t yOrigin, const std::vector<int>& owners, int requiredInterface, u8 flagsMask, | |||||
bool accountForSize) const; | |||||
void RenderSubmit(SceneCollector& collector); | |||||
u8 GetEntityFlagMask(const std::string& identifier) const override; | |||||
void SetEntityFlag(entity_id_t ent, const std::string& identifier, bool value) override; | |||||
// **************************************************************** | |||||
// LOS implementation: | |||||
CLosQuerier GetLosQuerier(player_id_t player) const override; | |||||
void ActivateScriptedVisibility(entity_id_t ent, bool status) override; | |||||
LosVisibility ComputeLosVisibility(CEntityHandle ent, player_id_t player) const; | |||||
LosVisibility ComputeLosVisibility(entity_id_t ent, player_id_t player) const; | |||||
LosVisibility GetLosVisibility(CEntityHandle ent, player_id_t player) const override; | |||||
LosVisibility GetLosVisibility(entity_id_t ent, player_id_t player) const override; | |||||
LosVisibility GetLosVisibilityPosition(entity_pos_t x, entity_pos_t z, player_id_t player) const | |||||
override; | |||||
size_t GetVerticesPerSide() const override; | |||||
LosRegion LosVertexToLosRegionsHelper(u16 x, u16 z) const; | |||||
LosRegion PosToLosRegionsHelper(entity_pos_t x, entity_pos_t z) const; | |||||
void AddToRegion(LosRegion region, entity_id_t ent); | |||||
void RemoveFromRegion(LosRegion region, entity_id_t ent); | |||||
void UpdateVisibilityData(); | |||||
void RequestVisibilityUpdate(entity_id_t ent) override; | |||||
void UpdateVisibility(entity_id_t ent, player_id_t player); | |||||
void UpdateVisibility(entity_id_t ent); | |||||
void SetLosRevealAll(player_id_t player, bool enabled) override; | |||||
bool GetLosRevealAll(player_id_t player) const override; | |||||
void SetLosCircular(bool enabled) override; | |||||
bool GetLosCircular() const override; | |||||
void SetSharedLos(player_id_t player, const std::vector<player_id_t>& players) override; | |||||
u32 GetSharedLosMask(player_id_t player) const override; | |||||
void ExploreMap(player_id_t p) override; | |||||
void ExploreTerritories() override; | |||||
/** | |||||
* Force any entity in explored territory to appear for player p. | |||||
* This is useful for miraging entities inside the territory borders at the beginning of a game, | |||||
* or if the "Explore Map" option has been set. | |||||
*/ | |||||
void SeeExploredEntities(player_id_t p) const; | |||||
void RevealShore(player_id_t p, bool enable) override; | |||||
/** | |||||
* Returns whether the given vertex is outside the normal bounds of the world | |||||
* (i.e. outside the range of a circular map) | |||||
*/ | |||||
bool LosIsOffWorld(ssize_t i, ssize_t j) const; | |||||
/** | |||||
* Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive). | |||||
*/ | |||||
void LosAddStripHelper(u8 owner, i32 i0, i32 i1, i32 j, Grid<u16>& counts); | |||||
/** | |||||
* Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive). | |||||
*/ | |||||
void LosRemoveStripHelper(u8 owner, i32 i0, i32 i1, i32 j, Grid<u16>& counts); | |||||
void MarkVisibilityDirtyAroundTile(u8 owner, i32 i, i32 j); | |||||
/** | |||||
* Update the LOS state of tiles within a given circular range, | |||||
* either adding or removing visibility depending on the template parameter. | |||||
* Assumes owner is in the valid range. | |||||
*/ | |||||
template<bool adding> | |||||
void LosUpdateHelper(u8 owner, entity_pos_t visionRange, CFixedVector2D pos) | |||||
{ | |||||
if (m_LosVerticesPerSide == 0) // do nothing if not initialised yet | |||||
return; | |||||
PROFILE("LosUpdateHelper"); | |||||
Grid<u16>& counts = m_LosPlayerCounts.at(owner); | |||||
// Lazy initialisation of counts: | |||||
if (counts.blank()) | |||||
counts.resize(m_LosVerticesPerSide, m_LosVerticesPerSide); | |||||
// Compute the circular region as a series of strips. | |||||
// Rather than quantise pos to vertexes, we do more precise sub-tile computations | |||||
// to get smoother behaviour as a unit moves rather than jumping a whole tile | |||||
// at once. | |||||
// To avoid the cost of sqrt when computing the outline of the circle, | |||||
// we loop from the bottom to the top and estimate the width of the current | |||||
// strip based on the previous strip, then adjust each end of the strip | |||||
// inwards or outwards until it's the widest that still falls within the circle. | |||||
// Compute top/bottom coordinates, and clamp to exclude the 1-tile border around the map | |||||
// (so that we never render the sharp edge of the map) | |||||
i32 j0 = ((pos.Y - visionRange)/LOS_TILE_SIZE).ToInt_RoundToInfinity(); | |||||
i32 j1 = ((pos.Y + visionRange)/LOS_TILE_SIZE).ToInt_RoundToNegInfinity(); | |||||
i32 j0clamp = std::max(j0, 1); | |||||
i32 j1clamp = std::min(j1, m_LosVerticesPerSide-2); | |||||
// Translate world coordinates into fractional tile-space coordinates | |||||
entity_pos_t x = pos.X / LOS_TILE_SIZE; | |||||
entity_pos_t y = pos.Y / LOS_TILE_SIZE; | |||||
entity_pos_t r = visionRange / LOS_TILE_SIZE; | |||||
entity_pos_t r2 = r.Square(); | |||||
// Compute the integers on either side of x | |||||
i32 xfloor = (x - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); | |||||
i32 xceil = (x + entity_pos_t::Epsilon()).ToInt_RoundToInfinity(); | |||||
// Initialise the strip (i0, i1) to a rough guess | |||||
i32 i0 = xfloor; | |||||
i32 i1 = xceil; | |||||
for (i32 j = j0clamp; j <= j1clamp; ++j) | |||||
{ | |||||
// Adjust i0 and i1 to be the outermost values that don't exceed | |||||
// the circle's radius (i.e. require dy^2 + dx^2 <= r^2). | |||||
// When moving the points inwards, clamp them to xceil+1 or xfloor-1 | |||||
// so they don't accidentally shoot off in the wrong direction forever. | |||||
entity_pos_t dy = entity_pos_t::FromInt(j) - y; | |||||
entity_pos_t dy2 = dy.Square(); | |||||
while (dy2 + (entity_pos_t::FromInt(i0-1) - x).Square() <= r2) | |||||
--i0; | |||||
while (i0 < xceil && dy2 + (entity_pos_t::FromInt(i0) - x).Square() > r2) | |||||
++i0; | |||||
while (dy2 + (entity_pos_t::FromInt(i1+1) - x).Square() <= r2) | |||||
++i1; | |||||
while (i1 > xfloor && dy2 + (entity_pos_t::FromInt(i1) - x).Square() > r2) | |||||
--i1; | |||||
#if DEBUG_RANGE_MANAGER_BOUNDS | |||||
if (i0 <= i1) | |||||
{ | |||||
ENSURE(dy2 + (entity_pos_t::FromInt(i0) - x).Square() <= r2); | |||||
ENSURE(dy2 + (entity_pos_t::FromInt(i1) - x).Square() <= r2); | |||||
} | |||||
ENSURE(dy2 + (entity_pos_t::FromInt(i0 - 1) - x).Square() > r2); | |||||
ENSURE(dy2 + (entity_pos_t::FromInt(i1 + 1) - x).Square() > r2); | |||||
#endif | |||||
// Clamp the strip to exclude the 1-tile border, | |||||
// then add or remove the strip as requested | |||||
i32 i0clamp = std::max(i0, 1); | |||||
i32 i1clamp = std::min(i1, m_LosVerticesPerSide-2); | |||||
if (adding) | |||||
LosAddStripHelper(owner, i0clamp, i1clamp, j, counts); | |||||
else | |||||
LosRemoveStripHelper(owner, i0clamp, i1clamp, j, counts); | |||||
} | |||||
} | |||||
/** | |||||
* Update the LOS state of tiles within a given circular range, | |||||
* by removing visibility around the 'from' position | |||||
* and then adding visibility around the 'to' position. | |||||
*/ | |||||
void LosUpdateHelperIncremental(u8 owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to); | |||||
void LosAdd(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos); | |||||
void SharingLosAdd(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos); | |||||
void LosRemove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos); | |||||
void SharingLosRemove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos); | |||||
void LosMove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to); | |||||
void SharingLosMove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D from, | |||||
CFixedVector2D to); | |||||
u8 GetPercentMapExplored(player_id_t player) const override; | |||||
u8 GetUnionPercentMapExplored(const std::vector<player_id_t>& players) const override; | |||||
}; | |||||
#endif // INCLUDED_CCMPRANGEMANAGER |
Wildfire Games · Phabricator