Index: ps/trunk/source/simulation2/MessageTypes.h =================================================================== --- ps/trunk/source/simulation2/MessageTypes.h (revision 9950) +++ ps/trunk/source/simulation2/MessageTypes.h (revision 9951) @@ -1,347 +1,347 @@ /* Copyright (C) 2010 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_MESSAGETYPES #define INCLUDED_MESSAGETYPES #include "simulation2/system/Components.h" #include "simulation2/system/Entity.h" #include "simulation2/system/Message.h" #include "simulation2/helpers/Position.h" #include "simulation2/components/ICmpPathfinder.h" #define DEFAULT_MESSAGE_IMPL(name) \ virtual int GetType() const { return MT_##name; } \ virtual const char* GetScriptHandlerName() const { return "On" #name; } \ virtual const char* GetScriptGlobalHandlerName() const { return "OnGlobal" #name; } \ virtual jsval ToJSVal(ScriptInterface& scriptInterface) const; \ static CMessage* FromJSVal(ScriptInterface&, jsval val); class SceneCollector; class CFrustum; class CMessageTurnStart : public CMessage { public: DEFAULT_MESSAGE_IMPL(TurnStart) CMessageTurnStart() { } }; // The update process is split into a number of phases, in an attempt // to cope with dependencies between components. Each phase is implemented // as a separate message. Simulation2.cpp sends them in sequence. /** * Generic per-turn update message, for things that don't care much about ordering. */ class CMessageUpdate : public CMessage { public: DEFAULT_MESSAGE_IMPL(Update) CMessageUpdate(fixed turnLength) : turnLength(turnLength) { } fixed turnLength; }; /** * Update phase for formation controller movement (must happen before individual * units move to follow their formation). */ class CMessageUpdate_MotionFormation : public CMessage { public: DEFAULT_MESSAGE_IMPL(Update_MotionFormation) CMessageUpdate_MotionFormation(fixed turnLength) : turnLength(turnLength) { } fixed turnLength; }; /** * Update phase for non-formation-controller unit movement. */ class CMessageUpdate_MotionUnit : public CMessage { public: DEFAULT_MESSAGE_IMPL(Update_MotionUnit) CMessageUpdate_MotionUnit(fixed turnLength) : turnLength(turnLength) { } fixed turnLength; }; /** * Final update phase, after all other updates. */ class CMessageUpdate_Final : public CMessage { public: DEFAULT_MESSAGE_IMPL(Update_Final) CMessageUpdate_Final(fixed turnLength) : turnLength(turnLength) { } fixed turnLength; }; /** * Prepare for rendering a new frame (set up model positions etc). */ class CMessageInterpolate : public CMessage { public: DEFAULT_MESSAGE_IMPL(Interpolate) CMessageInterpolate(float frameTime, float offset) : frameTime(frameTime), offset(offset) { } float frameTime; // time in seconds since previous interpolate float offset; // range [0, 1] (inclusive); fractional time of current frame between previous/next simulation turns }; /** * Add renderable objects to the scene collector. * Called after CMessageInterpolate. */ class CMessageRenderSubmit : public CMessage { public: DEFAULT_MESSAGE_IMPL(RenderSubmit) CMessageRenderSubmit(SceneCollector& collector, const CFrustum& frustum, bool culling) : collector(collector), frustum(frustum), culling(culling) { } SceneCollector& collector; const CFrustum& frustum; bool culling; }; /** * Handle progressive loading of resources. * A component that listens to this message must do the following: * - Increase *msg.total by the non-zero number of loading tasks this component can perform. * - If *msg.progressed == true, return and do nothing. * - If you've loaded everything, increase *msg.progress by the value you added to .total * - Otherwise do some loading, set *msg.progressed = true, and increase *msg.progress by a * value indicating how much progress you've made in total (0 <= p <= what you added to .total) * In some situations these messages will never be sent - components must ensure they * load all their data themselves before using it in that case. */ class CMessageProgressiveLoad : public CMessage { public: DEFAULT_MESSAGE_IMPL(ProgressiveLoad) CMessageProgressiveLoad(bool* progressed, int* total, int* progress) : progressed(progressed), total(total), progress(progress) { } bool* progressed; int* total; int* progress; }; /** * This is sent immediately after a new entity's components have all been created * and initialised. */ class CMessageCreate : public CMessage { public: DEFAULT_MESSAGE_IMPL(Create) CMessageCreate(entity_id_t entity) : entity(entity) { } entity_id_t entity; }; /** * This is sent immediately before a destroyed entity is flushed and really destroyed. * (That is, after CComponentManager::DestroyComponentsSoon and inside FlushDestroyedComponents). * The entity will still exist at the time this message is sent. * It's possible for this message to be sent multiple times for one entity, but all its components * will have been deleted after the first time. */ class CMessageDestroy : public CMessage { public: DEFAULT_MESSAGE_IMPL(Destroy) CMessageDestroy(entity_id_t entity) : entity(entity) { } entity_id_t entity; }; class CMessageOwnershipChanged : public CMessage { public: DEFAULT_MESSAGE_IMPL(OwnershipChanged) CMessageOwnershipChanged(entity_id_t entity, int32_t from, int32_t to) : entity(entity), from(from), to(to) { } entity_id_t entity; int32_t from; int32_t to; }; /** * Sent during TurnStart. * * If @c inWorld is false, then the other fields are invalid and meaningless. * Otherwise they represent the current position. */ class CMessagePositionChanged : public CMessage { public: DEFAULT_MESSAGE_IMPL(PositionChanged) CMessagePositionChanged(entity_id_t entity, bool inWorld, entity_pos_t x, entity_pos_t z, entity_angle_t a) : entity(entity), inWorld(inWorld), x(x), z(z), a(a) { } entity_id_t entity; bool inWorld; entity_pos_t x, z; entity_angle_t a; }; /** * Sent by CCmpUnitMotion during Update, whenever the motion status has changed * since the previous update. */ class CMessageMotionChanged : public CMessage { public: DEFAULT_MESSAGE_IMPL(MotionChanged) CMessageMotionChanged(bool starting, bool error) : starting(starting), error(error) { } bool starting; // whether this is a start or end of movement bool error; // whether we failed to start moving (couldn't find any path) }; /** * Sent when terrain (texture or elevation) has been changed. */ class CMessageTerrainChanged : public CMessage { public: DEFAULT_MESSAGE_IMPL(TerrainChanged) - CMessageTerrainChanged(ssize_t i0, ssize_t j0, ssize_t i1, ssize_t j1) : + CMessageTerrainChanged(int32_t i0, int32_t j0, int32_t i1, int32_t j1) : i0(i0), j0(j0), i1(i1), j1(j1) { } - ssize_t i0, j0, i1, j1; // inclusive lower bound, exclusive upper bound, in tiles + int32_t i0, j0, i1, j1; // inclusive lower bound, exclusive upper bound, in tiles }; /** * Sent by CCmpRangeManager at most once per turn, when an active range query * has had matching units enter/leave the range since the last RangeUpdate. */ class CMessageRangeUpdate : public CMessage { public: DEFAULT_MESSAGE_IMPL(RangeUpdate) CMessageRangeUpdate(u32 tag, const std::vector& added, const std::vector& removed) : tag(tag), added(added), removed(removed) { } u32 tag; std::vector added; std::vector removed; // CCmpRangeManager wants to store a vector of messages and wants to // swap vectors instead of copying (to save on memory allocations), // so add some constructors for it: CMessageRangeUpdate(u32 tag) : tag(tag) { } CMessageRangeUpdate(const CMessageRangeUpdate& other) : CMessage(), tag(other.tag), added(other.added), removed(other.removed) { } CMessageRangeUpdate& operator=(const CMessageRangeUpdate& other) { tag = other.tag; added = other.added; removed = other.removed; return *this; } }; /** * Sent by CCmpPathfinder after async path requests. */ class CMessagePathResult : public CMessage { public: DEFAULT_MESSAGE_IMPL(PathResult) CMessagePathResult(u32 ticket, const ICmpPathfinder::Path& path) : ticket(ticket), path(path) { } u32 ticket; ICmpPathfinder::Path path; }; #endif // INCLUDED_MESSAGETYPES Index: ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp (revision 9950) +++ ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp (revision 9951) @@ -1,712 +1,711 @@ /* Copyright (C) 2011 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 "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpTerritoryManager.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "graphics/TextureManager.h" #include "maths/MathUtil.h" #include "maths/Vector2D.h" #include "ps/Overlay.h" #include "renderer/Renderer.h" #include "renderer/Scene.h" #include "renderer/TerrainOverlay.h" #include "simulation2/MessageTypes.h" #include "simulation2/components/ICmpObstruction.h" #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/components/ICmpOwnership.h" #include "simulation2/components/ICmpPathfinder.h" #include "simulation2/components/ICmpPlayer.h" #include "simulation2/components/ICmpPlayerManager.h" #include "simulation2/components/ICmpPosition.h" #include "simulation2/components/ICmpSettlement.h" #include "simulation2/components/ICmpTerrain.h" #include "simulation2/components/ICmpTerritoryInfluence.h" #include "simulation2/helpers/Geometry.h" #include "simulation2/helpers/Grid.h" #include "simulation2/helpers/PriorityQueue.h" #include "simulation2/helpers/Render.h" class CCmpTerritoryManager; class TerritoryOverlay : public TerrainOverlay { NONCOPYABLE(TerritoryOverlay); public: CCmpTerritoryManager& m_TerritoryManager; TerritoryOverlay(CCmpTerritoryManager& manager) : m_TerritoryManager(manager) { } virtual void StartRender(); virtual void ProcessTile(ssize_t i, ssize_t j); }; class CCmpTerritoryManager : public ICmpTerritoryManager { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeGloballyToMessageType(MT_OwnershipChanged); componentManager.SubscribeGloballyToMessageType(MT_PositionChanged); componentManager.SubscribeToMessageType(MT_TerrainChanged); componentManager.SubscribeToMessageType(MT_RenderSubmit); } DEFAULT_COMPONENT_ALLOCATOR(TerritoryManager) static std::string GetSchema() { return ""; } u8 m_ImpassableCost; float m_BorderThickness; float m_BorderSeparation; Grid* m_Territories; TerritoryOverlay* m_DebugOverlay; std::vector m_BoundaryLines; bool m_BoundaryLinesDirty; virtual void Init(const CParamNode& UNUSED(paramNode)) { m_Territories = NULL; m_DebugOverlay = NULL; // m_DebugOverlay = new TerritoryOverlay(*this); m_BoundaryLinesDirty = true; m_DirtyID = 1; CParamNode externalParamNode; CParamNode::LoadXML(externalParamNode, L"simulation/data/territorymanager.xml"); m_ImpassableCost = externalParamNode.GetChild("TerritoryManager").GetChild("ImpassableCost").ToInt(); m_BorderThickness = externalParamNode.GetChild("TerritoryManager").GetChild("BorderThickness").ToFixed().ToFloat(); m_BorderSeparation = externalParamNode.GetChild("TerritoryManager").GetChild("BorderSeparation").ToFixed().ToFloat(); } virtual void Deinit() { SAFE_DELETE(m_Territories); SAFE_DELETE(m_DebugOverlay); } virtual void Serialize(ISerializer& serialize) { // TODO } virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) { Init(paramNode); } virtual void HandleMessage(const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_OwnershipChanged: { const CMessageOwnershipChanged& msgData = static_cast (msg); MakeDirtyIfRelevantEntity(msgData.entity); break; } case MT_PositionChanged: { const CMessagePositionChanged& msgData = static_cast (msg); MakeDirtyIfRelevantEntity(msgData.entity); break; } case MT_TerrainChanged: { MakeDirty(); break; } case MT_RenderSubmit: { const CMessageRenderSubmit& msgData = static_cast (msg); RenderSubmit(msgData.collector); break; } } } // Check whether the entity is either a settlement or territory influence; // ignore any others void MakeDirtyIfRelevantEntity(entity_id_t ent) { CmpPtr cmpSettlement(GetSimContext(), ent); if (!cmpSettlement.null()) MakeDirty(); CmpPtr cmpTerritoryInfluence(GetSimContext(), ent); if (!cmpTerritoryInfluence.null()) MakeDirty(); } virtual const Grid& GetTerritoryGrid() { CalculateTerritories(); return *m_Territories; } // To support lazy updates of territory render data, // we maintain a DirtyID here and increment it whenever territories change; // if a caller has a lower DirtyID then it needs to be updated. size_t m_DirtyID; void MakeDirty() { SAFE_DELETE(m_Territories); ++m_DirtyID; m_BoundaryLinesDirty = true; } virtual bool NeedUpdate(size_t* dirtyID) { - ENSURE(*dirtyID <= m_DirtyID); - if (*dirtyID < m_DirtyID) + if (*dirtyID != m_DirtyID) { *dirtyID = m_DirtyID; return true; } return false; } void CalculateTerritories(); /** * Updates @p grid based on the obstruction shapes of all entities with * a TerritoryInfluence component. Grid cells are 0 if no influence, * or 1+c if the influence have cost c (assumed between 0 and 254). */ void RasteriseInfluences(CComponentManager::InterfaceList& infls, Grid& grid); struct TerritoryBoundary { player_id_t owner; std::vector points; }; std::vector ComputeBoundaries(); void UpdateBoundaryLines(); void RenderSubmit(SceneCollector& collector); }; REGISTER_COMPONENT_TYPE(TerritoryManager) /* We compute the territory influence of an entity with a kind of best-first search, storing an 'open' list of tiles that have not yet been processed, then taking the highest-weight tile (closest to origin) and updating the weight of extending to each neighbour (based on radius-determining 'falloff' value, adjusted by terrain movement cost), and repeating until all tiles are processed. */ typedef PriorityQueueHeap, u32, std::greater > OpenQueue; static void ProcessNeighbour(u32 falloff, u16 i, u16 j, u32 pg, bool diagonal, Grid& grid, OpenQueue& queue, const Grid& costGrid) { u32 dg = falloff * costGrid.get(i, j); if (diagonal) dg = (dg * 362) / 256; // Stop if new cost g=pg-dg is not better than previous value for that tile // (arranged to avoid underflow if pg < dg) if (pg <= grid.get(i, j) + dg) return; u32 g = pg - dg; // cost to this tile = cost to predecessor - falloff from predecessor grid.set(i, j, g); OpenQueue::Item tile = { std::make_pair(i, j), g }; queue.push(tile); } static void FloodFill(Grid& grid, Grid& costGrid, OpenQueue& openTiles, u32 falloff) { u32 tilesW = grid.m_W; u32 tilesH = grid.m_H; while (!openTiles.empty()) { OpenQueue::Item tile = openTiles.pop(); // Process neighbours (if they're not off the edge of the map) u16 x = tile.id.first; u16 z = tile.id.second; if (x > 0) ProcessNeighbour(falloff, x-1, z, tile.rank, false, grid, openTiles, costGrid); if (x < tilesW-1) ProcessNeighbour(falloff, x+1, z, tile.rank, false, grid, openTiles, costGrid); if (z > 0) ProcessNeighbour(falloff, x, z-1, tile.rank, false, grid, openTiles, costGrid); if (z < tilesH-1) ProcessNeighbour(falloff, x, z+1, tile.rank, false, grid, openTiles, costGrid); if (x > 0 && z > 0) ProcessNeighbour(falloff, x-1, z-1, tile.rank, true, grid, openTiles, costGrid); if (x > 0 && z < tilesH-1) ProcessNeighbour(falloff, x-1, z+1, tile.rank, true, grid, openTiles, costGrid); if (x < tilesW-1 && z > 0) ProcessNeighbour(falloff, x+1, z-1, tile.rank, true, grid, openTiles, costGrid); if (x < tilesW-1 && z < tilesH-1) ProcessNeighbour(falloff, x+1, z+1, tile.rank, true, grid, openTiles, costGrid); } } void CCmpTerritoryManager::CalculateTerritories() { PROFILE("CalculateTerritories"); if (m_Territories) return; CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); uint32_t tilesW = cmpTerrain->GetVerticesPerSide() - 1; uint32_t tilesH = cmpTerrain->GetVerticesPerSide() - 1; SAFE_DELETE(m_Territories); m_Territories = new Grid(tilesW, tilesH); // Compute terrain-passability-dependent costs per tile Grid influenceGrid(tilesW, tilesH); CmpPtr cmpPathfinder(GetSimContext(), SYSTEM_ENTITY); ICmpPathfinder::pass_class_t passClassUnrestricted = cmpPathfinder->GetPassabilityClass("unrestricted"); ICmpPathfinder::pass_class_t passClassDefault = cmpPathfinder->GetPassabilityClass("default"); const Grid& passGrid = cmpPathfinder->GetPassabilityGrid(); for (u32 j = 0; j < tilesH; ++j) { for (u32 i = 0; i < tilesW; ++i) { u8 g = passGrid.get(i, j); u8 cost; if (g & passClassUnrestricted) cost = 255; // off the world; use maximum cost else if (g & passClassDefault) cost = m_ImpassableCost; else cost = 1; influenceGrid.set(i, j, cost); } } // Find all territory influence entities CComponentManager::InterfaceList influences = GetSimContext().GetComponentManager().GetEntitiesWithInterface(IID_TerritoryInfluence); // Allow influence entities to override the terrain costs RasteriseInfluences(influences, influenceGrid); // Split influence entities into per-player lists, ignoring any with invalid properties std::map > influenceEntities; for (CComponentManager::InterfaceList::iterator it = influences.begin(); it != influences.end(); ++it) { // Ignore any with no weight or radius (to avoid divide-by-zero later) ICmpTerritoryInfluence* cmpTerritoryInfluence = static_cast(it->second); if (cmpTerritoryInfluence->GetWeight() == 0 || cmpTerritoryInfluence->GetRadius() == 0) continue; CmpPtr cmpOwnership(GetSimContext(), it->first); if (cmpOwnership.null()) continue; // Ignore Gaia and unassigned player_id_t owner = cmpOwnership->GetOwner(); if (owner <= 0) continue; // Ignore if invalid position CmpPtr cmpPosition(GetSimContext(), it->first); if (cmpPosition.null() || !cmpPosition->IsInWorld()) continue; influenceEntities[owner].push_back(it->first); } // For each player, store the sum of influences on each tile std::vector > > playerGrids; // TODO: this is a large waste of memory; we don't really need to store // all the intermediate grids for (std::map >::iterator it = influenceEntities.begin(); it != influenceEntities.end(); ++it) { Grid playerGrid(tilesW, tilesH); std::vector& ents = it->second; for (std::vector::iterator eit = ents.begin(); eit != ents.end(); ++eit) { // Compute the influence map of the current entity, then add it to the player grid Grid entityGrid(tilesW, tilesH); CmpPtr cmpPosition(GetSimContext(), *eit); CFixedVector2D pos = cmpPosition->GetPosition2D(); int i = clamp((pos.X / (int)CELL_SIZE).ToInt_RoundToNegInfinity(), 0, (int)tilesW-1); int j = clamp((pos.Y / (int)CELL_SIZE).ToInt_RoundToNegInfinity(), 0, (int)tilesH-1); CmpPtr cmpTerritoryInfluence(GetSimContext(), *eit); u32 weight = cmpTerritoryInfluence->GetWeight(); u32 radius = cmpTerritoryInfluence->GetRadius() / CELL_SIZE; u32 falloff = weight / radius; // earlier check for GetRadius() == 0 prevents divide-by-zero // TODO: we should have some maximum value on weight, to avoid overflow // when doing all the sums // Initialise the tile under the entity entityGrid.set(i, j, weight); OpenQueue openTiles; OpenQueue::Item tile = { std::make_pair((u16)i, (i16)j), weight }; openTiles.push(tile); // Expand influences outwards FloodFill(entityGrid, influenceGrid, openTiles, falloff); // TODO: we should do a sparse grid and only add the non-zero regions, for performance for (u16 j = 0; j < entityGrid.m_H; ++j) for (u16 i = 0; i < entityGrid.m_W; ++i) playerGrid.set(i, j, playerGrid.get(i, j) + entityGrid.get(i, j)); } playerGrids.push_back(std::make_pair(it->first, playerGrid)); } // Set m_Territories to the player ID with the highest influence for each tile for (u16 j = 0; j < tilesH; ++j) { for (u16 i = 0; i < tilesW; ++i) { u32 bestWeight = 0; for (size_t k = 0; k < playerGrids.size(); ++k) { u32 w = playerGrids[k].second.get(i, j); if (w > bestWeight) { player_id_t id = playerGrids[k].first; m_Territories->set(i, j, (u8)id); bestWeight = w; } } } } } /** * Compute the tile indexes on the grid nearest to a given point */ static void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h) { i = clamp((x / (int)CELL_SIZE).ToInt_RoundToZero(), 0, w-1); j = clamp((z / (int)CELL_SIZE).ToInt_RoundToZero(), 0, h-1); } /** * Returns the position of the center of the given tile */ static void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z) { x = entity_pos_t::FromInt(i*(int)CELL_SIZE + CELL_SIZE/2); z = entity_pos_t::FromInt(j*(int)CELL_SIZE + CELL_SIZE/2); } // TODO: would be nice not to duplicate those two functions from CCmpObstructionManager.cpp void CCmpTerritoryManager::RasteriseInfluences(CComponentManager::InterfaceList& infls, Grid& grid) { for (CComponentManager::InterfaceList::iterator it = infls.begin(); it != infls.end(); ++it) { ICmpTerritoryInfluence* cmpTerritoryInfluence = static_cast(it->second); int cost = cmpTerritoryInfluence->GetCost(); if (cost == -1) continue; CmpPtr cmpObstruction(GetSimContext(), it->first); if (cmpObstruction.null()) continue; ICmpObstructionManager::ObstructionSquare square; if (!cmpObstruction->GetObstructionSquare(square)) continue; CFixedVector2D halfSize(square.hw, square.hh); CFixedVector2D halfBound = Geometry::GetHalfBoundingBox(square.u, square.v, halfSize); u16 i0, j0, i1, j1; NearestTile(square.x - halfBound.X, square.z - halfBound.Y, i0, j0, grid.m_W, grid.m_H); NearestTile(square.x + halfBound.X, square.z + halfBound.Y, i1, j1, grid.m_W, grid.m_H); for (u16 j = j0; j <= j1; ++j) { for (u16 i = i0; i <= i1; ++i) { entity_pos_t x, z; TileCenter(i, j, x, z); if (Geometry::PointIsInSquare(CFixedVector2D(x - square.x, z - square.z), square.u, square.v, halfSize)) grid.set(i, j, cost); } } } } std::vector CCmpTerritoryManager::ComputeBoundaries() { PROFILE("ComputeBoundaries"); std::vector boundaries; CalculateTerritories(); // Copy the territories grid so we can mess with it Grid grid (*m_Territories); // Some constants for the border walk CVector2D edgeOffsets[] = { CVector2D(0.5f, 0.0f), CVector2D(1.0f, 0.5f), CVector2D(0.5f, 1.0f), CVector2D(0.0f, 0.5f) }; // Try to find an assigned tile for (int j = 0; j < grid.m_H; ++j) { for (int i = 0; i < grid.m_W; ++i) { u8 owner = grid.get(i, j); if (owner) { // Found the first tile (which must be the lowest j value of any non-zero tile); // start at the bottom edge of it and chase anticlockwise around the border until // we reach the starting point again boundaries.push_back(TerritoryBoundary()); boundaries.back().owner = owner; std::vector& points = boundaries.back().points; int dir = 0; // 0 == bottom edge of tile, 1 == right, 2 == top, 3 == left int cdir = dir; int ci = i, cj = j; while (true) { points.push_back((CVector2D(ci, cj) + edgeOffsets[cdir]) * CELL_SIZE); // Given that we're on an edge on a continuous boundary and aiming anticlockwise, // we can either carry on straight or turn left or turn right, so examine each // of the three possible cases (depending on initial direction): switch (cdir) { case 0: if (ci < grid.m_W-1 && cj > 0 && grid.get(ci+1, cj-1) == owner) { ++ci; --cj; cdir = 3; } else if (ci < grid.m_W-1 && grid.get(ci+1, cj) == owner) ++ci; else cdir = 1; break; case 1: if (ci < grid.m_W-1 && cj < grid.m_H-1 && grid.get(ci+1, cj+1) == owner) { ++ci; ++cj; cdir = 0; } else if (cj < grid.m_H-1 && grid.get(ci, cj+1) == owner) ++cj; else cdir = 2; break; case 2: if (ci > 0 && cj < grid.m_H-1 && grid.get(ci-1, cj+1) == owner) { --ci; ++cj; cdir = 1; } else if (ci > 0 && grid.get(ci-1, cj) == owner) --ci; else cdir = 3; break; case 3: if (ci > 0 && cj > 0 && grid.get(ci-1, cj-1) == owner) { --ci; --cj; cdir = 2; } else if (cj > 0 && grid.get(ci, cj-1) == owner) --cj; else cdir = 0; break; } // Stop when we've reached the starting point again if (ci == i && cj == j && cdir == dir) break; } // Zero out this whole territory with a simple flood fill, so we don't // process it a second time std::vector > tileStack; #define ZERO_AND_PUSH(i, j) STMT(grid.set(i, j, 0); tileStack.push_back(std::make_pair(i, j)); ) ZERO_AND_PUSH(i, j); while (!tileStack.empty()) { int ti = tileStack.back().first; int tj = tileStack.back().second; tileStack.pop_back(); if (ti > 0 && grid.get(ti-1, tj) == owner) ZERO_AND_PUSH(ti-1, tj); if (ti < grid.m_W-1 && grid.get(ti+1, tj) == owner) ZERO_AND_PUSH(ti+1, tj); if (tj > 0 && grid.get(ti, tj-1) == owner) ZERO_AND_PUSH(ti, tj-1); if (tj < grid.m_H-1 && grid.get(ti, tj+1) == owner) ZERO_AND_PUSH(ti, tj+1); if (ti > 0 && tj > 0 && grid.get(ti-1, tj-1) == owner) ZERO_AND_PUSH(ti-1, tj-1); if (ti > 0 && tj < grid.m_H-1 && grid.get(ti-1, tj+1) == owner) ZERO_AND_PUSH(ti-1, tj+1); if (ti < grid.m_W-1 && tj > 0 && grid.get(ti+1, tj-1) == owner) ZERO_AND_PUSH(ti+1, tj-1); if (ti < grid.m_W-1 && tj < grid.m_H-1 && grid.get(ti+1, tj+1) == owner) ZERO_AND_PUSH(ti+1, tj+1); } #undef ZERO_AND_PUSH } } } return boundaries; } void CCmpTerritoryManager::UpdateBoundaryLines() { PROFILE("update boundary lines"); m_BoundaryLines.clear(); std::vector boundaries = ComputeBoundaries(); CTextureProperties texturePropsBase("art/textures/misc/territory_border.png"); texturePropsBase.SetWrap(GL_CLAMP_TO_BORDER, GL_CLAMP_TO_EDGE); texturePropsBase.SetMaxAnisotropy(2.f); CTexturePtr textureBase = g_Renderer.GetTextureManager().CreateTexture(texturePropsBase); CTextureProperties texturePropsMask("art/textures/misc/territory_border_mask.png"); texturePropsMask.SetWrap(GL_CLAMP_TO_BORDER, GL_CLAMP_TO_EDGE); texturePropsMask.SetMaxAnisotropy(2.f); CTexturePtr textureMask = g_Renderer.GetTextureManager().CreateTexture(texturePropsMask); CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); if (cmpTerrain.null()) return; CTerrain* terrain = cmpTerrain->GetCTerrain(); CmpPtr cmpPlayerManager(GetSimContext(), SYSTEM_ENTITY); if (cmpPlayerManager.null()) return; for (size_t i = 0; i < boundaries.size(); ++i) { if (boundaries[i].points.empty()) continue; CColor color(1, 0, 1, 1); CmpPtr cmpPlayer(GetSimContext(), cmpPlayerManager->GetPlayerByID(boundaries[i].owner)); if (!cmpPlayer.null()) color = cmpPlayer->GetColour(); m_BoundaryLines.push_back(SOverlayTexturedLine()); m_BoundaryLines.back().m_Terrain = terrain; m_BoundaryLines.back().m_TextureBase = textureBase; m_BoundaryLines.back().m_TextureMask = textureMask; m_BoundaryLines.back().m_Color = color; m_BoundaryLines.back().m_Thickness = m_BorderThickness; SimRender::SmoothPointsAverage(boundaries[i].points, true); SimRender::InterpolatePointsRNS(boundaries[i].points, true, m_BorderSeparation); std::vector& points = m_BoundaryLines.back().m_Coords; for (size_t j = 0; j < boundaries[i].points.size(); ++j) { points.push_back(boundaries[i].points[j].X); points.push_back(boundaries[i].points[j].Y); } } } void CCmpTerritoryManager::RenderSubmit(SceneCollector& collector) { if (m_BoundaryLinesDirty) { UpdateBoundaryLines(); m_BoundaryLinesDirty = false; } for (size_t i = 0; i < m_BoundaryLines.size(); ++i) collector.Submit(&m_BoundaryLines[i]); } void TerritoryOverlay::StartRender() { m_TerritoryManager.CalculateTerritories(); } void TerritoryOverlay::ProcessTile(ssize_t i, ssize_t j) { if (!m_TerritoryManager.m_Territories) return; u8 id = m_TerritoryManager.m_Territories->get(i, j); float a = 0.2f; switch (id) { case 0: break; case 1: RenderTile(CColor(1, 0, 0, a), false); break; case 2: RenderTile(CColor(0, 1, 0, a), false); break; case 3: RenderTile(CColor(0, 0, 1, a), false); break; case 4: RenderTile(CColor(1, 1, 0, a), false); break; case 5: RenderTile(CColor(0, 1, 1, a), false); break; case 6: RenderTile(CColor(1, 0, 1, a), false); break; default: RenderTile(CColor(1, 1, 1, a), false); break; } } Index: ps/trunk/source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpRangeManager.cpp (revision 9950) +++ ps/trunk/source/simulation2/components/CCmpRangeManager.cpp (revision 9951) @@ -1,1216 +1,1256 @@ /* Copyright (C) 2011 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 "precompiled.h" #include "simulation2/system/Component.h" #include "ICmpRangeManager.h" -#include "ICmpPosition.h" -#include "ICmpVision.h" #include "simulation2/MessageTypes.h" +#include "simulation2/components/ICmpPosition.h" +#include "simulation2/components/ICmpTerritoryManager.h" +#include "simulation2/components/ICmpVision.h" #include "simulation2/helpers/Render.h" #include "simulation2/helpers/Spatial.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "lib/timer.h" #include "maths/FixedVector2D.h" #include "ps/CLogger.h" #include "ps/Overlay.h" #include "ps/Profile.h" #include "renderer/Scene.h" /** * Representation of a range query. */ struct Query { bool enabled; entity_id_t source; entity_pos_t minRange; entity_pos_t maxRange; u32 ownersMask; i32 interface; std::vector lastMatch; }; /** * Convert an owner ID (-1 = unowned, 0 = gaia, 1..30 = players) * into a 32-bit mask for quick set-membership tests. */ static u32 CalcOwnerMask(i32 owner) { if (owner >= -1 && owner < 31) return 1 << (1+owner); else return 0; // owner was invalid } /** * Representation of an entity, with the data needed for queries. */ struct EntityData { EntityData() : retainInFog(0), owner(-1), inWorld(0) { } entity_pos_t x, z; entity_pos_t visionRange; u8 retainInFog; // boolean i8 owner; u8 inWorld; // boolean }; cassert(sizeof(EntityData) == 16); /** * Serialization helper template for Query */ struct SerializeQuery { template void operator()(S& serialize, const char* UNUSED(name), Query& value) { serialize.Bool("enabled", value.enabled); serialize.NumberU32_Unbounded("source", value.source); serialize.NumberFixed_Unbounded("min range", value.minRange); serialize.NumberFixed_Unbounded("max range", value.maxRange); serialize.NumberU32_Unbounded("owners mask", value.ownersMask); serialize.NumberI32_Unbounded("interface", value.interface); SerializeVector()(serialize, "last match", value.lastMatch); } }; /** * Serialization helper template for EntityData */ struct SerializeEntityData { template void operator()(S& serialize, const char* UNUSED(name), EntityData& value) { serialize.NumberFixed_Unbounded("x", value.x); serialize.NumberFixed_Unbounded("z", value.z); serialize.NumberFixed_Unbounded("vision", value.visionRange); serialize.NumberU8("retain in fog", value.retainInFog, 0, 1); serialize.NumberI8_Unbounded("owner", value.owner); serialize.NumberU8("in world", value.inWorld, 0, 1); } }; /** * Functor for sorting entities by distance from a source point. * It must only be passed entities that are in 'entities' * and are currently in the world. */ struct EntityDistanceOrdering { EntityDistanceOrdering(const std::map& entities, const CFixedVector2D& source) : m_EntityData(entities), m_Source(source) { } bool operator()(entity_id_t a, entity_id_t b) { const EntityData& da = m_EntityData.find(a)->second; const EntityData& db = m_EntityData.find(b)->second; CFixedVector2D vecA = CFixedVector2D(da.x, da.z) - m_Source; CFixedVector2D vecB = CFixedVector2D(db.x, db.z) - m_Source; return (vecA.CompareLength(vecB) < 0); } const std::map& m_EntityData; CFixedVector2D m_Source; private: EntityDistanceOrdering& operator=(const EntityDistanceOrdering&); }; /** * 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 : public ICmpRangeManager { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeGloballyToMessageType(MT_Create); componentManager.SubscribeGloballyToMessageType(MT_PositionChanged); componentManager.SubscribeGloballyToMessageType(MT_OwnershipChanged); componentManager.SubscribeGloballyToMessageType(MT_Destroy); componentManager.SubscribeToMessageType(MT_Update); componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays } DEFAULT_COMPONENT_ALLOCATOR(RangeManager) bool m_DebugOverlayEnabled; bool m_DebugOverlayDirty; std::vector m_DebugOverlayLines; // 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 m_Queries; std::map m_EntityData; SpatialSubdivision m_Subdivision; // spatial index of m_EntityData // LOS state: std::map m_LosRevealAll; bool m_LosCircular; i32 m_TerrainVerticesPerSide; + size_t m_TerritoriesDirtyID; // 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::vector > m_LosPlayerCounts; // 2-bit ELosState per player, starting with player 1 (not 0!) up to player MAX_LOS_PLAYER_ID (inclusive) std::vector m_LosState; static const int MAX_LOS_PLAYER_ID = 16; // Special static visibility data for the "reveal whole map" mode // (TODO: this is usually a waste of memory) std::vector m_LosStateRevealed; static std::string GetSchema() { return ""; } virtual void Init(const CParamNode& UNUSED(paramNode)) { m_QueryNext = 1; m_DebugOverlayEnabled = false; m_DebugOverlayDirty = true; m_WorldX0 = m_WorldZ0 = m_WorldX1 = m_WorldZ1 = entity_pos_t::Zero(); // Initialise with bogus values (these will get replaced when // SetBounds is called) ResetSubdivisions(entity_pos_t::FromInt(1), entity_pos_t::FromInt(1)); // The whole map should be visible to Gaia by default, else e.g. animals // will get confused when trying to run from enemies m_LosRevealAll[0] = true; m_LosCircular = false; m_TerrainVerticesPerSide = 0; + + m_TerritoriesDirtyID = 0; } virtual void Deinit() { } template 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); SerializeMap()(serialize, "queries", m_Queries); SerializeMap()(serialize, "entity data", m_EntityData); SerializeMap()(serialize, "los reveal all", m_LosRevealAll); serialize.Bool("los circular", m_LosCircular); serialize.NumberI32_Unbounded("terrain verts per side", m_TerrainVerticesPerSide); - // We don't serialize m_Subdivision, m_LosPlayerCounts, m_LosState - // since they can be recomputed from the entity data when deserializing + // We don't serialize m_Subdivision or m_LosPlayerCounts + // since they can be recomputed from the entity data when deserializing; + // m_LosState must be serialized since it depends on the history of exploration + + SerializeVector()(serialize, "los state", m_LosState); } virtual void Serialize(ISerializer& serialize) { SerializeCommon(serialize); } virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) { Init(paramNode); SerializeCommon(deserialize); // Reinitialise subdivisions and LOS data - ResetDerivedData(); + ResetDerivedData(true); } virtual void HandleMessage(const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_Create: { const CMessageCreate& msgData = static_cast (msg); entity_id_t ent = msgData.entity; // Ignore local entities - we shouldn't let them influence anything if (ENTITY_IS_LOCAL(ent)) break; // Ignore non-positional entities CmpPtr cmpPosition(GetSimContext(), ent); if (cmpPosition.null()) break; // The newly-created entity will have owner -1 and position out-of-world // (any initialisation of those values will happen later), so we can just // use the default-constructed EntityData here EntityData entdata; // Store the LOS data, if any CmpPtr cmpVision(GetSimContext(), ent); if (!cmpVision.null()) { entdata.visionRange = cmpVision->GetRange(); entdata.retainInFog = (cmpVision->GetRetainInFog() ? 1 : 0); } // Remember this entity m_EntityData.insert(std::make_pair(ent, entdata)); break; } case MT_PositionChanged: { const CMessagePositionChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; std::map::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) break; if (msgData.inWorld) { if (it->second.inWorld) { CFixedVector2D from(it->second.x, it->second.z); CFixedVector2D to(msgData.x, msgData.z); m_Subdivision.Move(ent, from, to); LosMove(it->second.owner, it->second.visionRange, from, to); } else { CFixedVector2D to(msgData.x, msgData.z); m_Subdivision.Add(ent, to); LosAdd(it->second.owner, it->second.visionRange, to); } it->second.inWorld = 1; it->second.x = msgData.x; it->second.z = msgData.z; } else { if (it->second.inWorld) { CFixedVector2D from(it->second.x, it->second.z); m_Subdivision.Remove(ent, from); LosRemove(it->second.owner, it->second.visionRange, from); } it->second.inWorld = 0; it->second.x = entity_pos_t::Zero(); it->second.z = entity_pos_t::Zero(); } break; } case MT_OwnershipChanged: { const CMessageOwnershipChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; std::map::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) break; if (it->second.inWorld) { CFixedVector2D pos(it->second.x, it->second.z); LosRemove(it->second.owner, it->second.visionRange, pos); LosAdd(msgData.to, it->second.visionRange, pos); } it->second.owner = msgData.to; break; } case MT_Destroy: { const CMessageDestroy& msgData = static_cast (msg); entity_id_t ent = msgData.entity; std::map::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) break; if (it->second.inWorld) m_Subdivision.Remove(ent, CFixedVector2D(it->second.x, it->second.z)); m_EntityData.erase(it); break; } case MT_Update: { m_DebugOverlayDirty = true; + UpdateTerritoriesLos(); ExecuteActiveQueries(); break; } case MT_RenderSubmit: { const CMessageRenderSubmit& msgData = static_cast (msg); RenderSubmit(msgData.collector); break; } } } virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, ssize_t vertices) { m_WorldX0 = x0; m_WorldZ0 = z0; m_WorldX1 = x1; m_WorldZ1 = z1; m_TerrainVerticesPerSide = vertices; - ResetDerivedData(); + ResetDerivedData(false); } // Reinitialise subdivisions and LOS data, based on entity data - void ResetDerivedData() + void ResetDerivedData(bool skipLosState) { ENSURE(m_WorldX0.IsZero() && m_WorldZ0.IsZero()); // don't bother implementing non-zero offsets yet ResetSubdivisions(m_WorldX1, m_WorldZ1); m_LosPlayerCounts.clear(); m_LosPlayerCounts.resize(MAX_LOS_PLAYER_ID+1); - m_LosState.clear(); - m_LosState.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + if (!skipLosState) + { + m_LosState.clear(); + m_LosState.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); + } m_LosStateRevealed.clear(); m_LosStateRevealed.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); for (std::map::iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) LosAdd(it->second.owner, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); for (ssize_t j = 0; j < m_TerrainVerticesPerSide; ++j) for (ssize_t i = 0; i < m_TerrainVerticesPerSide; ++i) m_LosStateRevealed[i + j*m_TerrainVerticesPerSide] = LosIsOffWorld(i, j) ? 0 : 0xFFFFFFFFu; } void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1) { // Use 8x8 tile subdivisions // (TODO: find the optimal number instead of blindly guessing) m_Subdivision.Reset(x1, z1, entity_pos_t::FromInt(8*CELL_SIZE)); for (std::map::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { if (it->second.inWorld) m_Subdivision.Add(it->first, CFixedVector2D(it->second.x, it->second.z)); } } virtual tag_t CreateActiveQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, std::vector owners, int requiredInterface) { size_t id = m_QueryNext++; m_Queries[id] = ConstructQuery(source, minRange, maxRange, owners, requiredInterface); return (tag_t)id; } virtual void DestroyActiveQuery(tag_t tag) { if (m_Queries.find(tag) == m_Queries.end()) { LOGERROR(L"CCmpRangeManager: DestroyActiveQuery called with invalid tag %d", tag); return; } m_Queries.erase(tag); } virtual void EnableActiveQuery(tag_t tag) { std::map::iterator it = m_Queries.find(tag); if (it == m_Queries.end()) { LOGERROR(L"CCmpRangeManager: EnableActiveQuery called with invalid tag %d", tag); return; } Query& q = it->second; q.enabled = true; } virtual void DisableActiveQuery(tag_t tag) { std::map::iterator it = m_Queries.find(tag); if (it == m_Queries.end()) { LOGERROR(L"CCmpRangeManager: DisableActiveQuery called with invalid tag %d", tag); return; } Query& q = it->second; q.enabled = false; } virtual std::vector ExecuteQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, std::vector owners, int requiredInterface) { PROFILE("ExecuteQuery"); Query q = ConstructQuery(source, minRange, maxRange, owners, requiredInterface); std::vector r; CmpPtr cmpSourcePosition(GetSimContext(), q.source); if (cmpSourcePosition.null() || !cmpSourcePosition->IsInWorld()) { // If the source doesn't have a position, then the result is just the empty list return r; } PerformQuery(q, r); // Return the list sorted by distance from the entity CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); std::stable_sort(r.begin(), r.end(), EntityDistanceOrdering(m_EntityData, pos)); return r; } virtual std::vector ResetActiveQuery(tag_t tag) { PROFILE("ResetActiveQuery"); std::vector r; std::map::iterator it = m_Queries.find(tag); if (it == m_Queries.end()) { LOGERROR(L"CCmpRangeManager: ResetActiveQuery called with invalid tag %d", tag); return r; } Query& q = it->second; q.enabled = true; CmpPtr cmpSourcePosition(GetSimContext(), q.source); if (cmpSourcePosition.null() || !cmpSourcePosition->IsInWorld()) { // If the source doesn't have a position, then the result is just the empty list q.lastMatch = r; return r; } PerformQuery(q, r); q.lastMatch = r; // Return the list sorted by distance from the entity CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); std::stable_sort(r.begin(), r.end(), EntityDistanceOrdering(m_EntityData, pos)); return r; } virtual std::vector GetEntitiesByPlayer(player_id_t player) { std::vector entities; u32 ownerMask = CalcOwnerMask(player); for (std::map::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) entities.push_back(it->first); } return entities; } virtual void SetDebugOverlay(bool enabled) { m_DebugOverlayEnabled = enabled; m_DebugOverlayDirty = true; if (!enabled) m_DebugOverlayLines.clear(); } /** * Update all currently-enabled active queries. */ void ExecuteActiveQueries() { PROFILE("ExecuteActiveQueries"); // Store a queue of all messages before sending any, so we can assume // no entities will move until we've finished checking all the ranges std::vector > messages; for (std::map::iterator it = m_Queries.begin(); it != m_Queries.end(); ++it) { Query& q = it->second; if (!q.enabled) continue; CmpPtr cmpSourcePosition(GetSimContext(), q.source); if (cmpSourcePosition.null() || !cmpSourcePosition->IsInWorld()) continue; std::vector r; r.reserve(q.lastMatch.size()); PerformQuery(q, r); // Compute the changes vs the last match std::vector added; std::vector removed; std::set_difference(r.begin(), r.end(), q.lastMatch.begin(), q.lastMatch.end(), std::back_inserter(added)); std::set_difference(q.lastMatch.begin(), q.lastMatch.end(), r.begin(), r.end(), std::back_inserter(removed)); if (added.empty() && removed.empty()) continue; // Return the 'added' list sorted by distance from the entity // (Don't bother sorting 'removed' because they might not even have positions or exist any more) CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); std::stable_sort(added.begin(), added.end(), EntityDistanceOrdering(m_EntityData, pos)); messages.push_back(std::make_pair(q.source, CMessageRangeUpdate(it->first))); messages.back().second.added.swap(added); messages.back().second.removed.swap(removed); it->second.lastMatch.swap(r); } for (size_t i = 0; i < messages.size(); ++i) GetSimContext().GetComponentManager().PostMessage(messages[i].first, messages[i].second); } /** * Returns whether the given entity matches the given query (ignoring maxRange) */ bool TestEntityQuery(const Query& q, entity_id_t id, const EntityData& entity) { // Quick filter to ignore entities with the wrong owner if (!(CalcOwnerMask(entity.owner) & q.ownersMask)) return false; // Ignore entities not present in the world if (!entity.inWorld) return false; // Ignore self if (id == q.source) return false; // Ignore if it's missing the required interface if (q.interface && !GetSimContext().GetComponentManager().QueryInterface(id, q.interface)) return false; return true; } /** * Returns a list of distinct entity IDs that match the given query, sorted by ID. */ void PerformQuery(const Query& q, std::vector& r) { CmpPtr cmpSourcePosition(GetSimContext(), q.source); if (cmpSourcePosition.null() || !cmpSourcePosition->IsInWorld()) return; CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); // Special case: range -1.0 means check all entities ignoring distance if (q.maxRange == entity_pos_t::FromInt(-1)) { for (std::map::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { if (!TestEntityQuery(q, it->first, it->second)) continue; r.push_back(it->first); } } else { // Get a quick list of entities that are potentially in range std::vector ents = m_Subdivision.GetNear(pos, q.maxRange); for (size_t i = 0; i < ents.size(); ++i) { std::map::const_iterator it = m_EntityData.find(ents[i]); ENSURE(it != m_EntityData.end()); if (!TestEntityQuery(q, it->first, it->second)) continue; // Restrict based on precise distance int distVsMax = (CFixedVector2D(it->second.x, it->second.z) - pos).CompareLength(q.maxRange); if (distVsMax > 0) continue; if (!q.minRange.IsZero()) { int distVsMin = (CFixedVector2D(it->second.x, it->second.z) - pos).CompareLength(q.minRange); if (distVsMin < 0) continue; } r.push_back(it->first); } } } Query ConstructQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, const std::vector& owners, int requiredInterface) { // Min range must be non-negative if (minRange < entity_pos_t::Zero()) LOGWARNING(L"CCmpRangeManager: Invalid min range %f in query for entity %d", minRange.ToDouble(), source); // Max range must be non-negative, or else -1 if (maxRange < entity_pos_t::Zero() && maxRange != entity_pos_t::FromInt(-1)) LOGWARNING(L"CCmpRangeManager: Invalid max range %f in query for entity %d", maxRange.ToDouble(), source); Query q; q.enabled = false; q.source = source; q.minRange = minRange; q.maxRange = maxRange; q.ownersMask = 0; for (size_t i = 0; i < owners.size(); ++i) q.ownersMask |= CalcOwnerMask(owners[i]); q.interface = requiredInterface; return q; } void RenderSubmit(SceneCollector& collector) { if (!m_DebugOverlayEnabled) return; CColor enabledRingColour(0, 1, 0, 1); CColor disabledRingColour(1, 0, 0, 1); CColor rayColour(1, 1, 0, 0.2f); if (m_DebugOverlayDirty) { m_DebugOverlayLines.clear(); for (std::map::iterator it = m_Queries.begin(); it != m_Queries.end(); ++it) { Query& q = it->second; CmpPtr cmpSourcePosition(GetSimContext(), q.source); if (cmpSourcePosition.null() || !cmpSourcePosition->IsInWorld()) continue; CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); // Draw the max range circle m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = (q.enabled ? enabledRingColour : disabledRingColour); SimRender::ConstructCircleOnGround(GetSimContext(), pos.X.ToFloat(), pos.Y.ToDouble(), q.maxRange.ToFloat(), m_DebugOverlayLines.back(), true); // Draw the min range circle if (!q.minRange.IsZero()) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = (q.enabled ? enabledRingColour : disabledRingColour); SimRender::ConstructCircleOnGround(GetSimContext(), pos.X.ToFloat(), pos.Y.ToDouble(), q.minRange.ToFloat(), m_DebugOverlayLines.back(), true); } // Draw a ray from the source to each matched entity for (size_t i = 0; i < q.lastMatch.size(); ++i) { CmpPtr cmpTargetPosition(GetSimContext(), q.lastMatch[i]); if (cmpTargetPosition.null() || !cmpTargetPosition->IsInWorld()) continue; CFixedVector2D targetPos = cmpTargetPosition->GetPosition2D(); std::vector coords; coords.push_back(pos.X.ToFloat()); coords.push_back(pos.Y.ToFloat()); coords.push_back(targetPos.X.ToFloat()); coords.push_back(targetPos.Y.ToFloat()); m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = rayColour; SimRender::ConstructLineOnGround(GetSimContext(), coords, m_DebugOverlayLines.back(), true); } } m_DebugOverlayDirty = false; } for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i) collector.Submit(&m_DebugOverlayLines[i]); } + // **************************************************************** // LOS implementation: virtual CLosQuerier GetLosQuerier(player_id_t player) { if (GetLosRevealAll(player)) return CLosQuerier(player, m_LosStateRevealed, m_TerrainVerticesPerSide); else return CLosQuerier(player, m_LosState, m_TerrainVerticesPerSide); } virtual ELosVisibility GetLosVisibility(entity_id_t ent, player_id_t player) { // (We can't use m_EntityData since this needs to handle LOCAL entities too) // Entities not with positions in the world are never visible CmpPtr cmpPosition(GetSimContext(), ent); if (cmpPosition.null() || !cmpPosition->IsInWorld()) return VIS_HIDDEN; CFixedVector2D pos = cmpPosition->GetPosition2D(); int i = (pos.X / (int)CELL_SIZE).ToInt_RoundToNearest(); int j = (pos.Y / (int)CELL_SIZE).ToInt_RoundToNearest(); // Reveal flag makes all positioned entities visible if (GetLosRevealAll(player)) { if (LosIsOffWorld(i, j)) return VIS_HIDDEN; else return VIS_VISIBLE; } // Visible if within a visible region CLosQuerier los(player, m_LosState, m_TerrainVerticesPerSide); if (los.IsVisible(i, j)) return VIS_VISIBLE; // Fogged if the 'retain in fog' flag is set, and in a non-visible explored region if (los.IsExplored(i, j)) { CmpPtr cmpVision(GetSimContext(), ent); if (!cmpVision.null() && cmpVision->GetRetainInFog()) return VIS_FOGGED; } // Otherwise not visible return VIS_HIDDEN; } virtual void SetLosRevealAll(player_id_t player, bool enabled) { m_LosRevealAll[player] = enabled; } virtual bool GetLosRevealAll(player_id_t player) { std::map::const_iterator it; // Special player value can force reveal-all for every player it = m_LosRevealAll.find(-1); if (it != m_LosRevealAll.end() && it->second) return true; // Otherwise check the player-specific flag it = m_LosRevealAll.find(player); if (it != m_LosRevealAll.end() && it->second) return true; return false; } virtual void SetLosCircular(bool enabled) { m_LosCircular = enabled; - ResetDerivedData(); + ResetDerivedData(false); } virtual bool GetLosCircular() { return m_LosCircular; } + void UpdateTerritoriesLos() + { + CmpPtr cmpTerritoryManager(GetSimContext(), SYSTEM_ENTITY); + if (cmpTerritoryManager.null() || !cmpTerritoryManager->NeedUpdate(&m_TerritoriesDirtyID)) + return; + + const Grid& grid = cmpTerritoryManager->GetTerritoryGrid(); + ENSURE(grid.m_W == m_TerrainVerticesPerSide-1 && grid.m_H == m_TerrainVerticesPerSide-1); + + // For each tile, if it is owned by a valid player then update the LOS + // for every vertex around that tile, to mark them as explored + + for (size_t j = 0; j < grid.m_H; ++j) + { + for (size_t i = 0; i < grid.m_W; ++i) + { + u8 p = grid.get(i, j); + if (p > 0 && p <= MAX_LOS_PLAYER_ID) + { + m_LosState[i + j*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); + m_LosState[i+1 + j*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); + m_LosState[i + (j+1)*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); + m_LosState[i+1 + (j+1)*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); + } + } + } + } + /** * Returns whether the given vertex is outside the normal bounds of the world * (i.e. outside the range of a circular map) */ inline bool LosIsOffWorld(ssize_t i, ssize_t j) { // WARNING: CCmpObstructionManager::Rasterise needs to be kept in sync with this const ssize_t edgeSize = 3; // number of vertexes around the edge that will be off-world if (m_LosCircular) { // With a circular map, vertex is off-world if hypot(i - size/2, j - size/2) >= size/2: ssize_t dist2 = (i - m_TerrainVerticesPerSide/2)*(i - m_TerrainVerticesPerSide/2) + (j - m_TerrainVerticesPerSide/2)*(j - m_TerrainVerticesPerSide/2); ssize_t r = m_TerrainVerticesPerSide/2 - edgeSize + 1; // subtract a bit from the radius to ensure nice // SoD blurring around the edges of the map return (dist2 >= r*r); } else { // With a square map, the outermost edge of the map should be off-world, // so the SoD texture blends out nicely return (i < edgeSize || j < edgeSize || i >= m_TerrainVerticesPerSide-edgeSize || j >= m_TerrainVerticesPerSide-edgeSize); } } /** * 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, u16* counts) { if (i1 < i0) return; i32 idx0 = j*m_TerrainVerticesPerSide + i0; i32 idx1 = j*m_TerrainVerticesPerSide + i1; for (i32 idx = idx0; idx <= idx1; ++idx) { // Increasing from zero to non-zero - move from unexplored/explored to visible+explored if (counts[idx] == 0) { i32 i = i0 + idx - idx0; if (!LosIsOffWorld(i, j)) m_LosState[idx] |= ((LOS_VISIBLE | LOS_EXPLORED) << (2*(owner-1))); } counts[idx] += 1; } } /** * 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, u16* counts) { if (i1 < i0) return; i32 idx0 = j*m_TerrainVerticesPerSide + i0; i32 idx1 = j*m_TerrainVerticesPerSide + i1; for (i32 idx = idx0; idx <= idx1; ++idx) { counts[idx] -= 1; // Decreasing from non-zero to zero - move from visible+explored to explored if (counts[idx] == 0) { // (If LosIsOffWorld then this is a no-op, so don't bother doing the check) m_LosState[idx] &= ~(LOS_VISIBLE << (2*(owner-1))); } } } /** * 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 void LosUpdateHelper(u8 owner, entity_pos_t visionRange, CFixedVector2D pos) { if (m_TerrainVerticesPerSide == 0) // do nothing if not initialised yet return; PROFILE("LosUpdateHelper"); std::vector& counts = m_LosPlayerCounts.at(owner); // Lazy initialisation of counts: if (counts.empty()) counts.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); u16* countsData = &counts[0]; // 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)/(int)CELL_SIZE).ToInt_RoundToInfinity(); i32 j1 = ((pos.Y + visionRange)/(int)CELL_SIZE).ToInt_RoundToNegInfinity(); i32 j0clamp = std::max(j0, 1); i32 j1clamp = std::min(j1, m_TerrainVerticesPerSide-2); // Translate world coordinates into fractional tile-space coordinates entity_pos_t x = pos.X / (int)CELL_SIZE; entity_pos_t y = pos.Y / (int)CELL_SIZE; entity_pos_t r = visionRange / (int)CELL_SIZE; entity_pos_t r2 = r.Square(); // Compute the integers on either side of x i32 xfloor = x.ToInt_RoundToNegInfinity(); i32 xceil = x.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; // 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_TerrainVerticesPerSide-2); if (adding) LosAddStripHelper(owner, i0clamp, i1clamp, j, countsData); else LosRemoveStripHelper(owner, i0clamp, i1clamp, j, countsData); } } /** * 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) { if (m_TerrainVerticesPerSide == 0) // do nothing if not initialised yet return; PROFILE("LosUpdateHelperIncremental"); std::vector& counts = m_LosPlayerCounts.at(owner); // Lazy initialisation of counts: if (counts.empty()) counts.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); u16* countsData = &counts[0]; // See comments in LosUpdateHelper. // This does exactly the same, except computing the strips for // both circles simultaneously. // (The idea is that the circles will be heavily overlapping, // so we can compute the difference between the removed/added strips // and only have to touch tiles that have a net change.) i32 j0_from = ((from.Y - visionRange)/(int)CELL_SIZE).ToInt_RoundToInfinity(); i32 j1_from = ((from.Y + visionRange)/(int)CELL_SIZE).ToInt_RoundToNegInfinity(); i32 j0_to = ((to.Y - visionRange)/(int)CELL_SIZE).ToInt_RoundToInfinity(); i32 j1_to = ((to.Y + visionRange)/(int)CELL_SIZE).ToInt_RoundToNegInfinity(); i32 j0clamp = std::max(std::min(j0_from, j0_to), 1); i32 j1clamp = std::min(std::max(j1_from, j1_to), m_TerrainVerticesPerSide-2); entity_pos_t x_from = from.X / (int)CELL_SIZE; entity_pos_t y_from = from.Y / (int)CELL_SIZE; entity_pos_t x_to = to.X / (int)CELL_SIZE; entity_pos_t y_to = to.Y / (int)CELL_SIZE; entity_pos_t r = visionRange / (int)CELL_SIZE; entity_pos_t r2 = r.Square(); i32 xfloor_from = x_from.ToInt_RoundToNegInfinity(); i32 xceil_from = x_from.ToInt_RoundToInfinity(); i32 xfloor_to = x_to.ToInt_RoundToNegInfinity(); i32 xceil_to = x_to.ToInt_RoundToInfinity(); i32 i0_from = xfloor_from; i32 i1_from = xceil_from; i32 i0_to = xfloor_to; i32 i1_to = xceil_to; for (i32 j = j0clamp; j <= j1clamp; ++j) { entity_pos_t dy_from = entity_pos_t::FromInt(j) - y_from; entity_pos_t dy2_from = dy_from.Square(); while (dy2_from + (entity_pos_t::FromInt(i0_from-1) - x_from).Square() <= r2) --i0_from; while (i0_from <= xceil_from && dy2_from + (entity_pos_t::FromInt(i0_from) - x_from).Square() > r2) ++i0_from; while (dy2_from + (entity_pos_t::FromInt(i1_from+1) - x_from).Square() <= r2) ++i1_from; while (i1_from >= xfloor_from && dy2_from + (entity_pos_t::FromInt(i1_from) - x_from).Square() > r2) --i1_from; entity_pos_t dy_to = entity_pos_t::FromInt(j) - y_to; entity_pos_t dy2_to = dy_to.Square(); while (dy2_to + (entity_pos_t::FromInt(i0_to-1) - x_to).Square() <= r2) --i0_to; while (i0_to <= xceil_to && dy2_to + (entity_pos_t::FromInt(i0_to) - x_to).Square() > r2) ++i0_to; while (dy2_to + (entity_pos_t::FromInt(i1_to+1) - x_to).Square() <= r2) ++i1_to; while (i1_to >= xfloor_to && dy2_to + (entity_pos_t::FromInt(i1_to) - x_to).Square() > r2) --i1_to; // Check whether this strip moved at all if (!(i0_to == i0_from && i1_to == i1_from)) { i32 i0clamp_from = std::max(i0_from, 1); i32 i1clamp_from = std::min(i1_from, m_TerrainVerticesPerSide-2); i32 i0clamp_to = std::max(i0_to, 1); i32 i1clamp_to = std::min(i1_to, m_TerrainVerticesPerSide-2); // Check whether one strip is negative width, // and we can just add/remove the entire other strip if (i1clamp_from < i0clamp_from) { LosAddStripHelper(owner, i0clamp_to, i1clamp_to, j, countsData); } else if (i1clamp_to < i0clamp_to) { LosRemoveStripHelper(owner, i0clamp_from, i1clamp_from, j, countsData); } else { // There are four possible regions of overlap between the two strips // (remove before add, remove after add, add before remove, add after remove). // Process each of the regions as its own strip. // (If this produces negative-width strips then they'll just get ignored // which is fine.) LosRemoveStripHelper(owner, i0clamp_from, i0clamp_to-1, j, countsData); LosRemoveStripHelper(owner, i1clamp_to+1, i1clamp_from, j, countsData); LosAddStripHelper(owner, i0clamp_to, i0clamp_from-1, j, countsData); LosAddStripHelper(owner, i1clamp_from+1, i1clamp_to, j, countsData); } } } } void LosAdd(i8 owner, entity_pos_t visionRange, CFixedVector2D pos) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; LosUpdateHelper(owner, visionRange, pos); } void LosRemove(i8 owner, entity_pos_t visionRange, CFixedVector2D pos) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; LosUpdateHelper(owner, visionRange, pos); } void LosMove(i8 owner, entity_pos_t visionRange, CFixedVector2D from, CFixedVector2D to) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; if ((from - to).CompareLength(visionRange) > 0) { // If it's a very large move, then simply remove and add to the new position LosUpdateHelper(owner, visionRange, from); LosUpdateHelper(owner, visionRange, to); } else { // Otherwise use the version optimised for mostly-overlapping circles LosUpdateHelperIncremental(owner, visionRange, from, to); } } virtual i32 GetPercentMapExplored(player_id_t player) { i32 exploredVertices = 0; i32 overallVisibleVertices = 0; CLosQuerier los(player, m_LosState, m_TerrainVerticesPerSide); for (i32 j = 0; j < m_TerrainVerticesPerSide; j++) { for (i32 i = 0; i < m_TerrainVerticesPerSide; i++) { if (!LosIsOffWorld(i, j)) { overallVisibleVertices++; exploredVertices += (i32)los.IsExplored_UncheckedRange(i, j); } } } return exploredVertices * 100 / overallVisibleVertices; } }; REGISTER_COMPONENT_TYPE(RangeManager)