Index: binaries/data/mods/public/maps/scenarios/los_perf_test.xml =================================================================== --- /dev/null +++ binaries/data/mods/public/maps/scenarios/los_perf_test.xml @@ -0,0 +1,94 @@ + + + + + + default + + + + + + 0 + 0.5 + + + + + ocean + + + 5 + 4 + 0.45 + 0 + + + + 0 + 1 + 0.99 + 0.1999 + default + + + + + + + + + + + + Index: binaries/data/mods/public/maps/scenarios/los_perf_test_triggers.js =================================================================== --- /dev/null +++ binaries/data/mods/public/maps/scenarios/los_perf_test_triggers.js @@ -0,0 +1,71 @@ +const UNIT_TEMPLATE = "units/athen/support_female_citizen"; + +var QuickSpawn = function(x, z, template, owner = 1) +{ + let ent = Engine.AddEntity(template); + + let cmpEntOwnership = Engine.QueryInterface(ent, IID_Ownership); + if (cmpEntOwnership) + cmpEntOwnership.SetOwner(owner); + + let cmpEntPosition = Engine.QueryInterface(ent, IID_Position); + cmpEntPosition.JumpTo(x, z); + return ent; +}; + +var WalkTo = function(x, z, ent, owner = 1) +{ + ProcessCommand(owner, { + "type": "walk", + "entities": Array.isArray(ent) ? ent : [ent], + "x": x, + "z": z, + "queued": true + }); + return ent; +}; + +var cmpTrigger = Engine.QueryInterface(SYSTEM_ENTITY, IID_Trigger); + +var entities = []; + +Trigger.prototype.SetupUnitsEverywhere = function() +{ + for (let x = 0; x < 20*16*4; x += 50) + for (let z = 0; z < 20*16*4; z += 50) + for (let owner = 1; owner <= 8; owner++) + entities.push(QuickSpawn(x+owner, z, UNIT_TEMPLATE, owner)); +}; + + +Trigger.prototype.SetupUnitsSomeAndMove = function() +{ + for (let x = 0; x < 20*16*4; x += 50*2) + for (let z = 0; z < 20*16*4; z += 50*2) + for (let owner = 1; owner <= 8; owner++) + { + let ent = QuickSpawn(x+owner, z, UNIT_TEMPLATE, owner); + WalkTo(x + 50 + owner, z+owner, ent, owner); + WalkTo(x + 0 + owner, z+owner, ent, owner); + WalkTo(x + 50 + owner, z+owner, ent, owner); + WalkTo(x + 0 + owner, z+owner, ent, owner); + WalkTo(x + 50 + owner, z+owner, ent, owner); + WalkTo(x + 0 + owner, z+owner, ent, owner); + WalkTo(x + 50 + owner, z+owner, ent, owner); + WalkTo(x + 0 + owner, z+owner, ent, owner); + WalkTo(x + 50 + owner, z+owner, ent, owner); + entities.push(ent); + } +}; + +Trigger.prototype.KillAll = function() +{ + for (let ent of entities) + Engine.DestroyEntity(ent); + entities = []; +}; + +cmpTrigger.DoAfterDelay(400, "SetupUnitsEverywhere", {}); +cmpTrigger.DoAfterDelay(800, "KillAll", {}); +cmpTrigger.DoAfterDelay(1000, "SetupUnitsSomeAndMove", {}); +cmpTrigger.DoAfterDelay(50000, "KillAll", {}); Index: source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- source/simulation2/components/CCmpRangeManager.cpp +++ source/simulation2/components/CCmpRangeManager.cpp @@ -32,6 +32,7 @@ #include "simulation2/components/ICmpVisibility.h" #include "simulation2/components/ICmpVision.h" #include "simulation2/components/ICmpWaterManager.h" +#include "simulation2/helpers/PackedArray.h" #include "simulation2/helpers/Los.h" #include "simulation2/helpers/MapEdgeTiles.h" #include "simulation2/helpers/Render.h" @@ -46,8 +47,42 @@ #define DEBUG_RANGE_MANAGER_BOUNDS 0 +namespace std +{ + template<> class numeric_limits { public: static constexpr int digits = 2; }; + template<> class numeric_limits { public: static constexpr int digits = 2; }; +} + namespace { +/** + * Use this type to store something for each player, including GAIA player(s). + */ +template +using PerPlayer = PackedArray; + +/** + * Use this type to store something for each player, including GAIA player(s), + * as well as a single bit-flag located at index -1. + */ +template +using PerPlayerAndFlag = PackedArray; + +/** + * 'Declaration of intent' typedef for a valid, non-GAIA player (range 1..MAX_NB_OF_PLAYERS). + */ +using nongaia_player_id_t = std::make_unsigned_t; + +constexpr std::array GetNonGaiaPlayers() +{ + std::array ret{}; + for (nongaia_player_id_t i = 0; i < MAX_NB_OF_PLAYERS - 1; ++i) + ret[i] = i + 1; + return ret; +} + +constexpr std::array nongaia_players = GetNonGaiaPlayers(); + /** * How many LOS vertices to have per region. * LOS regions are used to keep track of units. @@ -60,95 +95,6 @@ */ const fixed PARABOLIC_RANGE_TOLERANCE = fixed::FromInt(1)/2; -/** - * Convert an owner ID (-1 = unowned, 0 = gaia, 1..30 = players) - * into a 32-bit mask for quick set-membership tests. - */ -u32 CalcOwnerMask(player_id_t owner) -{ - if (owner >= -1 && owner < 31) - return 1 << (1+owner); - else - return 0; // owner was invalid -} - -/** - * Returns LOS mask for given player. - */ -u32 CalcPlayerLosMask(player_id_t player) -{ - if (player > 0 && player <= 16) - return (u32)LosState::MASK << (2*(player-1)); - return 0; -} - -/** - * Returns shared LOS mask for given list of players. - */ -u32 CalcSharedLosMask(std::vector players) -{ - u32 playerMask = 0; - for (size_t i = 0; i < players.size(); i++) - playerMask |= CalcPlayerLosMask(players[i]); - - return playerMask; -} - -/** - * Add/remove a player to/from mask, which is a 1-bit mask representing a list of players. - * Returns true if the mask is modified. - */ -bool SetPlayerSharedDirtyVisibilityBit(u16& mask, player_id_t player, bool enable) -{ - if (player <= 0 || player > 16) - return false; - - u16 oldMask = mask; - - if (enable) - mask |= (0x1 << (player - 1)); - else - mask &= ~(0x1 << (player - 1)); - - return oldMask != mask; -} - -/** - * Computes the 2-bit visibility for one player, given the total 32-bit visibilities - */ -LosVisibility GetPlayerVisibility(u32 visibilities, player_id_t player) -{ - if (player > 0 && player <= 16) - return static_cast( (visibilities >> (2 *(player-1))) & 0x3 ); - return LosVisibility::HIDDEN; -} - -/** - * Test whether the visibility is dirty for a given LoS region and a given player - */ -bool IsVisibilityDirty(u16 dirty, player_id_t player) -{ - if (player > 0 && player <= 16) - return (dirty >> (player - 1)) & 0x1; - return false; -} - -/** - * Test whether a player share this vision - */ -bool HasVisionSharing(u16 visionSharing, player_id_t player) -{ - return (visionSharing & (1 << (player - 1))) != 0; -} - -/** - * Computes the shared vision mask for the player - */ -u16 CalcVisionSharingMask(player_id_t player) -{ - return 1 << (player-1); -} - /** * Representation of a range query. */ @@ -159,7 +105,7 @@ entity_pos_t minRange; entity_pos_t maxRange; entity_pos_t elevationBonus; // Used for parabolas only. - u32 ownersMask; + PerPlayerAndFlag ownersMask; // Flag used for 'no owner', i.e. owner == -1. i32 interface; u8 flagsMask; bool enabled; @@ -225,14 +171,14 @@ struct EntityData { EntityData() : - visibilities(0), size(0), visionSharing(0), + visibilities(LosVisibility::HIDDEN), size(0), visionSharing(0), owner(-1), flags(FlagMasks::Normal) { } entity_pos_t x, z; entity_pos_t visionRange; - u32 visibilities; // 2-bit visibility, per player + PerPlayer visibilities; u32 size; - u16 visionSharing; // 1-bit per player + PerPlayer visionSharing; i8 owner; u8 flags; // See the FlagMasks enum @@ -291,7 +237,7 @@ serialize.NumberFixed_Unbounded("min range", value.minRange); serialize.NumberFixed_Unbounded("max range", value.maxRange); serialize.NumberFixed_Unbounded("elevation bonus", value.elevationBonus); - serialize.NumberU32_Unbounded("owners mask", value.ownersMask); + Serializer(serialize, "owners mask", value.ownersMask); serialize.NumberI32_Unbounded("interface", value.interface); Serializer(serialize, "last match", value.lastMatch); serialize.NumberU8_Unbounded("flagsMask", value.flagsMask); @@ -332,9 +278,9 @@ serialize.NumberFixed_Unbounded("x", value.x); serialize.NumberFixed_Unbounded("z", value.z); serialize.NumberFixed_Unbounded("vision", value.visionRange); - serialize.NumberU32_Unbounded("visibilities", value.visibilities); + Serializer(serialize, "visibilities", value.visibilities); serialize.NumberU32_Unbounded("size", value.size); - serialize.NumberU16_Unbounded("vision sharing", value.visionSharing); + Serializer(serialize, "vision sharing", value.visionSharing); serialize.NumberI8_Unbounded("owner", value.owner); serialize.NumberU8_Unbounded("flags", value.flags); } @@ -403,7 +349,7 @@ i32 m_LosRegionsPerSide; bool m_GlobalVisibilityUpdate; std::array m_GlobalPlayerVisibilityUpdate; - Grid m_DirtyVisibility; + Grid> m_DirtyVisibility; Grid> m_LosRegions; // List of entities that must be updated, regardless of the status of their tile std::vector m_ModifiedEntities; @@ -423,9 +369,9 @@ Grid m_LosStateRevealed; // Shared LOS masks, one per player. - std::array m_SharedLosMasks; + std::array, MAX_LOS_PLAYER_ID+2> m_SharedLosMasks; // Shared dirty visibility masks, one per player. - std::array m_SharedDirtyVisibilityMasks; + std::array, MAX_LOS_PLAYER_ID+2> m_SharedDirtyVisibilityMasks; // Cache explored vertices per player (not serialized) u32 m_TotalInworldVertices; @@ -738,13 +684,13 @@ break; ENSURE(msgData.player > 0 && msgData.player < MAX_LOS_PLAYER_ID+1); - u16 visionChanged = CalcVisionSharingMask(msgData.player); + nongaia_player_id_t player = msgData.player; if (!it->second.HasFlag()) { // Activation of the Vision Sharing - ENSURE(it->second.owner == (i8)msgData.player); - it->second.visionSharing = visionChanged; + ENSURE(nongaia_player_id_t(it->second.owner) == player); + it->second.visionSharing[player] = true; it->second.SetFlag(true); break; } @@ -754,15 +700,12 @@ entity_pos_t range = it->second.visionRange; CFixedVector2D pos(it->second.x, it->second.z); if (msgData.add) - LosAdd(msgData.player, range, pos); + LosAdd(player, range, pos); else - LosRemove(msgData.player, range, pos); + LosRemove(player, range, pos); } - - if (msgData.add) - it->second.visionSharing |= visionChanged; - else - it->second.visionSharing &= ~visionChanged; + // Add / remove the player from the mask. + it->second.visionSharing[player] = msgData.add; break; } case MT_Update: @@ -869,7 +812,7 @@ for (i32 j = 0; j < m_LosVerticesPerSide; j++) for (i32 i = 0; i < m_LosVerticesPerSide; i++) if (!LosIsOffWorld(i, j)) - for (u8 k = 1; k < MAX_LOS_PLAYER_ID+1; ++k) + for (nongaia_player_id_t k : nongaia_players) m_ExploredVertices.at(k) += ((m_LosState.get(i, j) & ((u32)LosState::EXPLORED << (2*(k-1)))) > 0); } else m_LosState.resize(m_LosVerticesPerSide, m_LosVerticesPerSide); @@ -1068,27 +1011,38 @@ virtual std::vector GetEntitiesByPlayer(player_id_t player) const { - return GetEntitiesByMask(CalcOwnerMask(player)); + std::vector entities; + + for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + if (it->second.owner == player) + entities.push_back(it->first); + + return entities; } virtual std::vector GetNonGaiaEntities() const { - return GetEntitiesByMask(~3u); // bit 0 for owner=-1 and bit 1 for gaia + PerPlayerAndFlag mask(true); + mask[-1] = false; + mask[0] = false; + return GetEntitiesByMask(mask); } virtual std::vector GetGaiaAndNonGaiaEntities() const { - return GetEntitiesByMask(~1u); // bit 0 for owner=-1 + PerPlayerAndFlag mask(true); + mask[-1] = false; + return GetEntitiesByMask(mask); } - std::vector GetEntitiesByMask(u32 ownerMask) const + std::vector GetEntitiesByMask(PerPlayerAndFlag mask) const { std::vector entities; for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { // Check owner and add to list if it matches - if (CalcOwnerMask(it->second.owner) & ownerMask) + if (mask[it->second.owner]) entities.push_back(it->first); } @@ -1167,7 +1121,7 @@ bool TestEntityQuery(const Query& q, entity_id_t id, const EntityData& entity) const { // Quick filter to ignore entities with the wrong owner - if (!(CalcOwnerMask(entity.owner) & q.ownersMask)) + if (!q.ownersMask[entity.owner]) return false; // Ignore entities not present in the world @@ -1421,13 +1375,13 @@ q.maxRange += fixed::FromInt(size); } - q.ownersMask = 0; - for (size_t i = 0; i < owners.size(); ++i) - q.ownersMask |= CalcOwnerMask(owners[i]); - - if (q.ownersMask == 0) + if (owners.empty()) LOGWARNING("CCmpRangeManager: No owners in query for entity %u", source); + q.ownersMask = PerPlayerAndFlag(false); + for (int player : owners) + q.ownersMask[player] = true; + q.interface = requiredInterface; q.flagsMask = flagsMask; @@ -1747,7 +1701,8 @@ CFixedVector2D pos = cmpPosition->GetPosition2D(); - if (IsVisibilityDirty(m_DirtyVisibility[PosToLosRegionsHelper(pos.X, pos.Y)], player)) + nongaia_player_id_t validPlayer = player; + if (m_DirtyVisibility[PosToLosRegionsHelper(pos.X, pos.Y)][validPlayer]) return ComputeLosVisibility(ent, player); if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), entId) != m_ModifiedEntities.end()) @@ -1757,7 +1712,7 @@ if (it == m_EntityData.end()) return ComputeLosVisibility(ent, player); - return static_cast(GetPlayerVisibility(it->second.visibilities, player)); + return it->second.visibilities[validPlayer]; } virtual LosVisibility GetLosVisibility(entity_id_t ent, player_id_t player) const @@ -1836,12 +1791,12 @@ for (u16 j = 0; j < m_LosRegionsPerSide; ++j) { LosRegion pos{i, j}; - for (player_id_t player = 1; player < MAX_LOS_PLAYER_ID + 1; ++player) - if (IsVisibilityDirty(m_DirtyVisibility[pos], player) || m_GlobalPlayerVisibilityUpdate[player-1] == 1 || m_GlobalVisibilityUpdate) + for (nongaia_player_id_t player : nongaia_players) + if (m_DirtyVisibility[pos][player] || m_GlobalPlayerVisibilityUpdate[player-1] == 1 || m_GlobalVisibilityUpdate) for (const entity_id_t& ent : m_LosRegions[pos]) UpdateVisibility(ent, player); - m_DirtyVisibility[pos] = 0; + m_DirtyVisibility[pos] = PerPlayer(false); } std::fill(m_GlobalPlayerVisibilityUpdate.begin(), m_GlobalPlayerVisibilityUpdate.end(), false); @@ -1868,19 +1823,19 @@ m_ModifiedEntities.push_back(ent); } - void UpdateVisibility(entity_id_t ent, player_id_t player) + void UpdateVisibility(entity_id_t ent, nongaia_player_id_t player) { EntityMap::iterator itEnts = m_EntityData.find(ent); if (itEnts == m_EntityData.end()) return; - LosVisibility oldVis = GetPlayerVisibility(itEnts->second.visibilities, player); + LosVisibility oldVis = itEnts->second.visibilities[player]; LosVisibility newVis = ComputeLosVisibility(itEnts->first, player); if (oldVis == newVis) return; - itEnts->second.visibilities = (itEnts->second.visibilities & ~(0x3 << 2 * (player - 1))) | ((u8)newVis << 2 * (player - 1)); + itEnts->second.visibilities[player] = newVis; CMessageVisibilityChanged msg(player, ent, static_cast(oldVis), static_cast(newVis)); GetSimContext().GetComponentManager().PostMessage(ent, msg); @@ -1888,7 +1843,7 @@ void UpdateVisibility(entity_id_t ent) { - for (player_id_t player = 1; player < MAX_LOS_PLAYER_ID + 1; ++player) + for (nongaia_player_id_t player : nongaia_players) UpdateVisibility(ent, player); } @@ -1933,7 +1888,23 @@ virtual void SetSharedLos(player_id_t player, const std::vector& players) { - m_SharedLosMasks[player] = CalcSharedLosMask(players); + if (player <= 0) + { + LOGERROR("Cannot set shared LOS for player %i (GAIA or invalid)", player); + return; + } + + nongaia_player_id_t validPlayer = player; + m_SharedLosMasks[validPlayer] = PerPlayer(LosState::UNEXPLORED); + for (player_id_t p : players) + { + if (p <= 0) + { + LOGERROR("Cannot share LOS of player %i (GAIA or invalid)", p); + return; + } + m_SharedLosMasks[validPlayer][nongaia_player_id_t(p)] = LosState::MASK; + } // Units belonging to any of 'players' can now trigger visibility updates for 'player'. // If shared LOS partners have been removed, we disable visibility updates from them @@ -1941,12 +1912,13 @@ // 'player' needs a global visibility update for this turn. bool modified = false; - for (player_id_t p = 1; p < MAX_LOS_PLAYER_ID+1; ++p) + for (nongaia_player_id_t p : nongaia_players) { bool inList = std::find(players.begin(), players.end(), p) != players.end(); - - if (SetPlayerSharedDirtyVisibilityBit(m_SharedDirtyVisibilityMasks[p], player, inList)) + auto&& mask = m_SharedDirtyVisibilityMasks[p][validPlayer]; + if (mask != inList) modified = true; + mask = inList; } if (modified && (size_t)player <= m_GlobalPlayerVisibilityUpdate.size()) @@ -1955,7 +1927,7 @@ virtual u32 GetSharedLosMask(player_id_t player) const { - return m_SharedLosMasks[player]; + return *m_SharedLosMasks[player].data(); } void ExploreMap(player_id_t p) @@ -2118,7 +2090,7 @@ /** * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive). */ - inline void LosAddStripHelper(u8 owner, i32 i0, i32 i1, i32 j, Grid& counts) + inline void LosAddStripHelper(nongaia_player_id_t owner, i32 i0, i32 i1, i32 j, Grid& counts) { if (i1 < i0) return; @@ -2146,7 +2118,7 @@ /** * Update the LOS state of tiles within a given horizontal strip (i0,j) to (i1,j) (inclusive). */ - inline void LosRemoveStripHelper(u8 owner, i32 i0, i32 i1, i32 j, Grid& counts) + inline void LosRemoveStripHelper(nongaia_player_id_t owner, i32 i0, i32 i1, i32 j, Grid& counts) { if (i1 < i0) return; @@ -2167,7 +2139,7 @@ } } - inline void MarkVisibilityDirtyAroundTile(u8 owner, i32 i, i32 j) + inline void MarkVisibilityDirtyAroundTile(nongaia_player_id_t owner, i32 i, i32 j) { // If we're still in the deserializing process, we must not modify m_DirtyVisibility if (m_Deserializing) @@ -2180,16 +2152,20 @@ LosRegion n3 = LosVertexToLosRegionsHelper(i, j-1); LosRegion n4 = LosVertexToLosRegionsHelper(i, j); - u16 sharedDirtyVisibilityMask = m_SharedDirtyVisibilityMasks[owner]; + PerPlayer sharedDirtyVisibilityMask = m_SharedDirtyVisibilityMasks[owner]; if (j > 0 && i > 0) - m_DirtyVisibility[n1] |= sharedDirtyVisibilityMask; + for (nongaia_player_id_t player : nongaia_players) + m_DirtyVisibility[n1][player] |= sharedDirtyVisibilityMask[player]; if (n2 != n1 && j > 0 && i < m_LosVerticesPerSide) - m_DirtyVisibility[n2] |= sharedDirtyVisibilityMask; + for (nongaia_player_id_t player : nongaia_players) + m_DirtyVisibility[n2][player] |= sharedDirtyVisibilityMask[player]; if (n3 != n1 && j < m_LosVerticesPerSide && i > 0) - m_DirtyVisibility[n3] |= sharedDirtyVisibilityMask; + for (nongaia_player_id_t player : nongaia_players) + m_DirtyVisibility[n3][player] |= sharedDirtyVisibilityMask[player]; if (n4 != n1 && j < m_LosVerticesPerSide && i < m_LosVerticesPerSide) - m_DirtyVisibility[n4] |= sharedDirtyVisibilityMask; + for (nongaia_player_id_t player : nongaia_players) + m_DirtyVisibility[n4][player] |= sharedDirtyVisibilityMask[player]; } /** @@ -2198,7 +2174,7 @@ * Assumes owner is in the valid range. */ template - void LosUpdateHelper(u8 owner, entity_pos_t visionRange, CFixedVector2D pos) + void LosUpdateHelper(nongaia_player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos) { if (m_LosVerticesPerSide == 0) // do nothing if not initialised yet return; @@ -2285,7 +2261,7 @@ * 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 LosUpdateHelperIncremental(nongaia_player_id_t owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to) { if (m_LosVerticesPerSide == 0) // do nothing if not initialised yet return; @@ -2413,16 +2389,16 @@ if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; - LosUpdateHelper((u8)owner, visionRange, pos); + LosUpdateHelper(nongaia_player_id_t(owner), visionRange, pos); } - void SharingLosAdd(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos) + void SharingLosAdd(PerPlayer visionSharing, entity_pos_t visionRange, CFixedVector2D pos) { if (visionRange.IsZero()) return; - for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i) - if (HasVisionSharing(visionSharing, i)) + for (nongaia_player_id_t i : nongaia_players) + if (visionSharing[i]) LosAdd(i, visionRange, pos); } @@ -2431,16 +2407,16 @@ if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; - LosUpdateHelper((u8)owner, visionRange, pos); + LosUpdateHelper(nongaia_player_id_t(owner), visionRange, pos); } - void SharingLosRemove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D pos) + void SharingLosRemove(PerPlayer visionSharing, entity_pos_t visionRange, CFixedVector2D pos) { if (visionRange.IsZero()) return; - for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i) - if (HasVisionSharing(visionSharing, i)) + for (nongaia_player_id_t i : nongaia_players) + if (visionSharing[i]) LosRemove(i, visionRange, pos); } @@ -2452,21 +2428,21 @@ if ((from - to).CompareLength(visionRange) > 0) { // If it's a very large move, then simply remove and add to the new position - LosUpdateHelper((u8)owner, visionRange, from); - LosUpdateHelper((u8)owner, visionRange, to); + LosUpdateHelper(nongaia_player_id_t(owner), visionRange, from); + LosUpdateHelper(nongaia_player_id_t(owner), visionRange, to); } else // Otherwise use the version optimised for mostly-overlapping circles - LosUpdateHelperIncremental((u8)owner, visionRange, from, to); + LosUpdateHelperIncremental(nongaia_player_id_t(owner), visionRange, from, to); } - void SharingLosMove(u16 visionSharing, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to) + void SharingLosMove(PerPlayer visionSharing, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to) { if (visionRange.IsZero()) return; - for (player_id_t i = 1; i < MAX_LOS_PLAYER_ID+1; ++i) - if (HasVisionSharing(visionSharing, i)) + for (nongaia_player_id_t i : nongaia_players) + if (visionSharing[i]) LosMove(i, visionRange, from, to); } Index: source/simulation2/helpers/PackedArray.h =================================================================== --- /dev/null +++ source/simulation2/helpers/PackedArray.h @@ -0,0 +1,203 @@ +/* Copyright (C) 2021 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 . + */ + +#ifndef INCLUDED_PACKEDARRAY +#define INCLUDED_PACKEDARRAY + +#include "simulation2/serialization/SerializeTemplates.h" + +#include + +/** + * This class keeps a packed representation of T for SIZE members (where N = std::numeric_limits<>::digits). + * Essentially std::vector but fixed-size and for bigger types. + * It can conveniently replace std::array for very small structs, such as booleans or small enums. + * Note that there is probably a low size (4? 5?) where a regular std::array performs better. + * @a MINUS_ONE_MEANS_LAST makes indexing at -1 index at SIZE-1 (the last value). Note that other values are not supported. + */ +template +class PackedArray +{ + friend struct SerializeHelper>; + friend class EditableReference; + friend class TestPackedArray; + +public: + + static constexpr u8 NumberOfBits = std::numeric_limits::digits; + static_assert(NumberOfBits > 0, "T has 0 digits - numeric_limits::digits may need to be specialised."); + static constexpr u16 TotalBits = NumberOfBits * SIZE; + static constexpr u16 Bytes = TotalBits / CHAR_BIT + ((TotalBits % CHAR_BIT) > 0); + + static_assert(Bytes <= 8, "PackedArray not implemented above 8 bytes of data."); + + // Determine storage type based on type. + using Storage = + std::conditional_t>>>; + + static constexpr bool StorageIsScalar = std::is_arithmetic_v; +protected: + static constexpr Storage GetMaskBits() + { + Storage ret = 0; + for (size_t i = 0; i < NumberOfBits; ++i) + ret |= 1 << i; + return ret; + } + static constexpr Storage MaskBits = GetMaskBits(); +public: + + /** + * Proxy to provide a clean interface when using operator[] in a mutable fashion. + */ + class EditableReference + { + friend class PackedArray; + public: + constexpr void operator=(const T& o) + { + m_Array.Set(m_Offset, o); + } + constexpr void operator|=(const T& o) + { + m_Array.Set(m_Offset, static_cast(o | static_cast(*this))); + } + constexpr operator T() const + { + return static_cast(m_Array)[m_Offset]; + } + constexpr bool operator==(const T& o) const + { + return static_cast(*this) == o; + } + constexpr bool operator!=(const T& o) const + { + return static_cast(*this) != o; + } + + protected: + constexpr EditableReference(PackedArray& a, size_t o) : m_Array(a), m_Offset(o) {}; + PackedArray& m_Array; + size_t m_Offset; + }; + + /** + * As a means of providing some compile-time refactoring safety, and since this class + * generally replaces unsigned integers, ensure that indexing signed numbers (e.g. -1) will trigger + * compile time failures unless explicitly handled. + */ + class IndexingWrapper + { + public: + // Unsigned integers can be implicitly converted. + template, U> = 0> + constexpr IndexingWrapper(U o) : index(o) {} + // With MINUS_ONE_MEANS_LAST, -1 becomes the last index. Note that other negative values are not supported. + template, U> = 0> + constexpr IndexingWrapper(U o) { + if (o == -1) + index = SIZE - 1; + else + index = o; + } + + constexpr operator unsigned int() { return index; } + protected: + static_assert(std::numeric_limits::max() > SIZE, "Only up to max(uint) items are supported"); + unsigned int index; + }; + + constexpr PackedArray() : m_Storage(static_cast(T{})) {} + explicit constexpr PackedArray(T val) : m_Storage(static_cast(T{})) + { + SetEverywhere(static_cast(val)); + } + constexpr PackedArray(const PackedArray&) = default; + constexpr PackedArray& operator=(const PackedArray&) = default; + constexpr PackedArray(PackedArray&&) = default; + constexpr PackedArray& operator=(PackedArray&&) = default; + + constexpr T operator[](IndexingWrapper offset) const + { + return static_cast(Mask(m_Storage >> (offset * NumberOfBits))); + } + + constexpr EditableReference operator[](IndexingWrapper offset) + { + return { *this, offset }; + } + + constexpr bool operator==(const PackedArray& o) const + { + return m_Storage == o.m_Storage; + } + /** + * Temporary stop-gap. + */ + const Storage* data() const + { + return &m_Storage; + } + +protected: + constexpr Storage Mask(Storage value) const + { + return value & MaskBits; + } + + constexpr void Set(size_t offset, T o) + { + Set(offset, static_cast(o)); + } + + constexpr void Set(size_t offset, Storage o) + { + // First clear whatever bits we had there + m_Storage &= ~(MaskBits << (offset * NumberOfBits)); + // Then set whatever we have now. + m_Storage |= o << (offset * NumberOfBits); + } + + constexpr void SetEverywhere(Storage o) + { + for (size_t i = 0; i < SIZE; ++i) + Set(i, o); + } + + Storage m_Storage; +}; + +template +struct SerializeHelper> +{ + void operator()(ISerializer& serialize, const char* UNUSED(name), const PackedArray& value) + { + Serializer(serialize, "value", value.m_Storage); + } + + void operator()(IDeserializer& deserialize, const char* UNUSED(name), PackedArray& value) + { + Serializer(deserialize, "value", value.m_Storage); + } +}; + +#endif // INCLUDED_PACKEDARRAY Index: source/simulation2/helpers/Player.h =================================================================== --- source/simulation2/helpers/Player.h +++ source/simulation2/helpers/Player.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2010 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -23,6 +23,18 @@ */ typedef int32_t player_id_t; -static const player_id_t INVALID_PLAYER = -1; +constexpr inline player_id_t INVALID_PLAYER = -1; + +/** + * Maximum # of players supported by the engine, including gaia players (but not the invalid player). + * This is hardcoded because specific data structures are used for performance that don't necessarily scale. + * Since some structures add an 'invalid player' or a 'global player', this should generally be one less than a power of two. + */ +constexpr inline player_id_t MAX_NB_OF_PLAYERS = 15; + +/** + * Provided for convenience. + */ +constexpr inline player_id_t LAST_PLAYER_ID = MAX_NB_OF_PLAYERS-1; #endif // INCLUDED_PLAYER Index: source/simulation2/tests/test_PackedArray.h =================================================================== --- /dev/null +++ source/simulation2/tests/test_PackedArray.h @@ -0,0 +1,85 @@ +/* Copyright (C) 2021 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 . + */ + +#include "lib/self_test.h" + +#include "simulation2/helpers/PackedArray.h" + +enum class SmallEnum +{ + ZERO = 0, + ONE = 1, + TWO = 2 +}; + +namespace std +{ + template<> class numeric_limits { public: static constexpr int digits = 2; }; +} + +class TestPackedArray : public CxxTest::TestSuite +{ +public: + void setUp() + { + } + + void tearDown() + { + } + + void test_compiletime() + { + static_assert(std::is_same_v::Storage, u16>); + static_assert(std::is_same_v::Storage, u8>); + static_assert(std::is_same_v::Storage, u64>); + static_assert(sizeof(PackedArray::Storage) == 2); + + static_assert(PackedArray::MaskBits == 0b11); + { + constexpr PackedArray test(SmallEnum::ONE); + static_assert(test.m_Storage == 0b0101010101010101); + } + { + constexpr PackedArray test(SmallEnum::TWO); + static_assert(test.m_Storage == 0b1010101010101010); + } + } + + void test_basic() + { + PackedArray packed; + packed[4u] = SmallEnum::TWO; + packed[7u] = SmallEnum::ONE; + TS_ASSERT_EQUALS(packed[0u], SmallEnum::ZERO) + TS_ASSERT_EQUALS(packed[4u], SmallEnum::TWO) + TS_ASSERT_EQUALS(packed[7u], SmallEnum::ONE) + TS_ASSERT_EQUALS(packed.m_Storage, 0b0100001000000000); + } + + void test_wraparound() + { + PackedArray packed; + packed[2] = SmallEnum::TWO; + packed[5] = SmallEnum::ONE; + TS_ASSERT_EQUALS(packed[0], SmallEnum::ZERO) + TS_ASSERT_EQUALS(packed[2], SmallEnum::TWO) + TS_ASSERT_EQUALS(packed[5], SmallEnum::ONE) + TS_ASSERT_EQUALS(packed[-1], SmallEnum::ONE) + TS_ASSERT_EQUALS(packed.m_Storage, 0b010000100000); + } +};