Fixes macOS warnings after adding final keyword to simulation classes in rP26537.

[0ad.git] / source / simulation2 / components / CCmpTerritoryManager.cpp

/* Copyright (C) 2022 Wildfire Games.
 * This file is part of 0 A.D.
 *
 * 0 A.D. is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * 0 A.D. is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "precompiled.h"

#include "simulation2/system/Component.h"
#include "ICmpTerritoryManager.h"

#include "graphics/Overlay.h"
#include "graphics/Terrain.h"
#include "graphics/TextureManager.h"
#include "graphics/TerritoryBoundary.h"
#include "maths/MathUtil.h"
#include "ps/Profile.h"
#include "ps/XML/Xeromyces.h"
#include "renderer/Renderer.h"
#include "renderer/Scene.h"
#include "renderer/TerrainOverlay.h"
#include "simulation2/MessageTypes.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/ICmpTerritoryDecayManager.h"
#include "simulation2/components/ICmpTerritoryInfluence.h"
#include "simulation2/helpers/Grid.h"
#include "simulation2/helpers/Render.h"

#include <queue>

class CCmpTerritoryManager;

class TerritoryOverlay final : public TerrainTextureOverlay
{
        NONCOPYABLE(TerritoryOverlay);
public:
        CCmpTerritoryManager& m_TerritoryManager;

        TerritoryOverlay(CCmpTerritoryManager& manager);
        void BuildTextureRGBA(u8* data, size_t w, size_t h) override;
};

class CCmpTerritoryManager : public ICmpTerritoryManager
{
public:
        static void ClassInit(CComponentManager& componentManager)
        {
                componentManager.SubscribeGloballyToMessageType(MT_OwnershipChanged);
                componentManager.SubscribeGloballyToMessageType(MT_PlayerColorChanged);
                componentManager.SubscribeGloballyToMessageType(MT_PositionChanged);
                componentManager.SubscribeGloballyToMessageType(MT_ValueModification);
                componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);
                componentManager.SubscribeToMessageType(MT_TerrainChanged);
                componentManager.SubscribeToMessageType(MT_WaterChanged);
                componentManager.SubscribeToMessageType(MT_Update);
                componentManager.SubscribeToMessageType(MT_Interpolate);
                componentManager.SubscribeToMessageType(MT_RenderSubmit);
        }

        DEFAULT_COMPONENT_ALLOCATOR(TerritoryManager)

        static std::string GetSchema()
        {
                return "<a:component type='system'/><empty/>";
        }

        u8 m_ImpassableCost;
        float m_BorderThickness;
        float m_BorderSeparation;

        // Player ID   in bits 0-4 (TERRITORY_PLAYER_MASK)
        // connected flag in bit 5 (TERRITORY_CONNECTED_MASK)
        // blinking flag  in bit 6 (TERRITORY_BLINKING_MASK)
        // processed flag in bit 7 (TERRITORY_PROCESSED_MASK)
        Grid<u8>* m_Territories;

        std::vector<u16> m_TerritoryCellCounts;
        u16 m_TerritoryTotalPassableCellCount;

        // Saves the cost per tile (to stop territory on impassable tiles)
        Grid<u8>* m_CostGrid;

        // Set to true when territories change; will send a TerritoriesChanged message
        // during the Update phase
        bool m_TriggerEvent;

        struct SBoundaryLine
        {
                bool blinking;
                player_id_t owner;
                CColor color;
                SOverlayTexturedLine overlay;
        };

        std::vector<SBoundaryLine> m_BoundaryLines;
        bool m_BoundaryLinesDirty;

        double m_AnimTime; // time since start of rendering, in seconds

        TerritoryOverlay* m_DebugOverlay;

        bool m_EnableLineDebugOverlays; ///< Enable node debugging overlays for boundary lines?
        std::vector<SOverlayLine> m_DebugBoundaryLineNodes;

        void Init(const CParamNode& UNUSED(paramNode)) override
        {
                m_Territories = NULL;
                m_CostGrid = NULL;
                m_DebugOverlay = NULL;
//              m_DebugOverlay = new TerritoryOverlay(*this);
                m_BoundaryLinesDirty = true;
                m_TriggerEvent = true;
                m_EnableLineDebugOverlays = false;
                m_DirtyID = 1;
                m_DirtyBlinkingID = 1;
                m_Visible = true;
                m_ColorChanged = false;

                m_AnimTime = 0.0;

                m_TerritoryTotalPassableCellCount = 0;

                // Register Relax NG validator
                CXeromyces::AddValidator(g_VFS, "territorymanager", "simulation/data/territorymanager.rng");

                CParamNode externalParamNode;
                CParamNode::LoadXML(externalParamNode, L"simulation/data/territorymanager.xml", "territorymanager");

                int impassableCost = externalParamNode.GetChild("TerritoryManager").GetChild("ImpassableCost").ToInt();
                ENSURE(0 <= impassableCost && impassableCost <= 255);
                m_ImpassableCost = (u8)impassableCost;
                m_BorderThickness = externalParamNode.GetChild("TerritoryManager").GetChild("BorderThickness").ToFixed().ToFloat();
                m_BorderSeparation = externalParamNode.GetChild("TerritoryManager").GetChild("BorderSeparation").ToFixed().ToFloat();
        }

        void Deinit() override
        {
                SAFE_DELETE(m_Territories);
                SAFE_DELETE(m_CostGrid);
                SAFE_DELETE(m_DebugOverlay);
        }

        void Serialize(ISerializer& serialize) override
        {
                // Territory state can be recomputed as required, so we don't need to serialize any of it.
                serialize.Bool("trigger event", m_TriggerEvent);
        }

        void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) override
        {
                Init(paramNode);
                deserialize.Bool("trigger event", m_TriggerEvent);
        }

        void HandleMessage(const CMessage& msg, bool UNUSED(global)) override
        {
                switch (msg.GetType())
                {
                case MT_OwnershipChanged:
                {
                        const CMessageOwnershipChanged& msgData = static_cast<const CMessageOwnershipChanged&> (msg);
                        MakeDirtyIfRelevantEntity(msgData.entity);
                        break;
                }
                case MT_PlayerColorChanged:
                {
                        MakeDirty();
                        break;
                }
                case MT_PositionChanged:
                {
                        const CMessagePositionChanged& msgData = static_cast<const CMessagePositionChanged&> (msg);
                        MakeDirtyIfRelevantEntity(msgData.entity);
                        break;
                }
                case MT_ValueModification:
                {
                        const CMessageValueModification& msgData = static_cast<const CMessageValueModification&> (msg);
                        if (msgData.component == L"TerritoryInfluence")
                                MakeDirty();
                        break;
                }
                case MT_ObstructionMapShapeChanged:
                case MT_TerrainChanged:
                case MT_WaterChanged:
                {
                        // also recalculate the cost grid to support atlas changes
                        SAFE_DELETE(m_CostGrid);
                        MakeDirty();
                        break;
                }
                case MT_Update:
                {
                        if (m_TriggerEvent)
                        {
                                m_TriggerEvent = false;
                                GetSimContext().GetComponentManager().BroadcastMessage(CMessageTerritoriesChanged());
                        }
                        break;
                }
                case MT_Interpolate:
                {
                        const CMessageInterpolate& msgData = static_cast<const CMessageInterpolate&> (msg);
                        Interpolate(msgData.deltaSimTime, msgData.offset);
                        break;
                }
                case MT_RenderSubmit:
                {
                        const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
                        RenderSubmit(msgData.collector, msgData.frustum, msgData.culling);
                        break;
                }
                }
        }

        // Check whether the entity is either a settlement or territory influence;
        // ignore any others
        void MakeDirtyIfRelevantEntity(entity_id_t ent)
        {
                CmpPtr<ICmpTerritoryInfluence> cmpTerritoryInfluence(GetSimContext(), ent);
                if (cmpTerritoryInfluence)
                        MakeDirty();
        }

        const Grid<u8>& GetTerritoryGrid() override
        {
                CalculateTerritories();
                ENSURE(m_Territories);
                return *m_Territories;
        }

        player_id_t GetOwner(entity_pos_t x, entity_pos_t z) override;
        std::vector<u32> GetNeighbours(entity_pos_t x, entity_pos_t z, bool filterConnected) override;
        bool IsConnected(entity_pos_t x, entity_pos_t z) override;

        void SetTerritoryBlinking(entity_pos_t x, entity_pos_t z, bool enable) override;
        bool IsTerritoryBlinking(entity_pos_t x, entity_pos_t z) override;

        // 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.
        // We also do the same thing for blinking updates using DirtyBlinkingID.

        size_t m_DirtyID;
        size_t m_DirtyBlinkingID;

        bool m_ColorChanged;

        void MakeDirty()
        {
                SAFE_DELETE(m_Territories);
                ++m_DirtyID;
                m_BoundaryLinesDirty = true;
                m_TriggerEvent = true;
        }

        bool NeedUpdateTexture(size_t* dirtyID) override
        {
                if (*dirtyID == m_DirtyID && !m_ColorChanged)
                        return false;

                *dirtyID = m_DirtyID;
                m_ColorChanged = false;
                return true;
        }

        bool NeedUpdateAI(size_t* dirtyID, size_t* dirtyBlinkingID) const override
        {
                if (*dirtyID == m_DirtyID && *dirtyBlinkingID == m_DirtyBlinkingID)
                        return false;

                *dirtyID = m_DirtyID;
                *dirtyBlinkingID = m_DirtyBlinkingID;
                return true;
        }

        void CalculateCostGrid();

        void CalculateTerritories();

        u8 GetTerritoryPercentage(player_id_t player) override;

        std::vector<STerritoryBoundary> ComputeBoundaries();

        void UpdateBoundaryLines();

        void Interpolate(float frameTime, float frameOffset);

        void RenderSubmit(SceneCollector& collector, const CFrustum& frustum, bool culling);

        void SetVisibility(bool visible) override
        {
                m_Visible = visible;
        }

        void UpdateColors() override;

private:

        bool m_Visible;
};

REGISTER_COMPONENT_TYPE(TerritoryManager)

// Tile data type, for easier accessing of coordinates
struct Tile
{
        Tile(u16 i, u16 j) : x(i), z(j) { }
        u16 x, z;
};

// Floodfill templates that expand neighbours from a certain source onwards
// (posX, posZ) are the coordinates of the currently expanded tile
// (nx, nz) are the coordinates of the current neighbour handled
// The user of this floodfill should use "continue" on every neighbour that
// shouldn't be expanded on its own. (without continue, an infinite loop will happen)
# define FLOODFILL(i, j, code)\
        do {\
                const int NUM_NEIGHBOURS = 8;\
                const int NEIGHBOURS_X[NUM_NEIGHBOURS] = {1,-1, 0, 0, 1,-1, 1,-1};\
                const int NEIGHBOURS_Z[NUM_NEIGHBOURS] = {0, 0, 1,-1, 1,-1,-1, 1};\
                std::queue<Tile> openTiles;\
                openTiles.emplace(i, j);\
                while (!openTiles.empty())\
                {\
                        u16 posX = openTiles.front().x;\
                        u16 posZ = openTiles.front().z;\
                        openTiles.pop();\
                        for (int n = 0; n < NUM_NEIGHBOURS; ++n)\
                        {\
                                u16 nx = posX + NEIGHBOURS_X[n];\
                                u16 nz = posZ + NEIGHBOURS_Z[n];\
                                /* Check the bounds, underflow will cause the values to be big again */\
                                if (nx >= tilesW || nz >= tilesH)\
                                        continue;\
                                code\
                                openTiles.emplace(nx, nz);\
                        }\
                }\
        }\
        while (false)

/**
 * Compute the tile indexes on the grid nearest to a given point
 */
static void NearestTerritoryTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h)
{
        entity_pos_t scale = Pathfinding::NAVCELL_SIZE * ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE;
        i = Clamp((x / scale).ToInt_RoundToNegInfinity(), 0, w - 1);
        j = Clamp((z / scale).ToInt_RoundToNegInfinity(), 0, h - 1);
}

void CCmpTerritoryManager::CalculateCostGrid()
{
        if (m_CostGrid)
                return;

        CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
        if (!cmpPathfinder)
                return;

        pass_class_t passClassTerritory = cmpPathfinder->GetPassabilityClass("default-terrain-only");
        pass_class_t passClassUnrestricted = cmpPathfinder->GetPassabilityClass("unrestricted");

        const Grid<NavcellData>& passGrid = cmpPathfinder->GetPassabilityGrid();

        int tilesW = passGrid.m_W / NAVCELLS_PER_TERRITORY_TILE;
        int tilesH = passGrid.m_H / NAVCELLS_PER_TERRITORY_TILE;

        m_CostGrid = new Grid<u8>(tilesW, tilesH);
        m_TerritoryTotalPassableCellCount = 0;

        for (int i = 0; i < tilesW; ++i)
        {
                for (int j = 0; j < tilesH; ++j)
                {
                        NavcellData c = 0;
                        for (u16 di = 0; di < NAVCELLS_PER_TERRITORY_TILE; ++di)
                                for (u16 dj = 0; dj < NAVCELLS_PER_TERRITORY_TILE; ++dj)
                                        c |= passGrid.get(
                                                i * NAVCELLS_PER_TERRITORY_TILE + di,
                                                j * NAVCELLS_PER_TERRITORY_TILE + dj);
                        if (!IS_PASSABLE(c, passClassTerritory))
                                m_CostGrid->set(i, j, m_ImpassableCost);
                        else if (!IS_PASSABLE(c, passClassUnrestricted))
                                m_CostGrid->set(i, j, 255); // off the world; use maximum cost
                        else
                        {
                                m_CostGrid->set(i, j, 1);
                                ++m_TerritoryTotalPassableCellCount;
                        }
                }
        }
}

void CCmpTerritoryManager::CalculateTerritories()
{
        if (m_Territories)
                return;

        PROFILE("CalculateTerritories");

        // If the pathfinder hasn't been loaded (e.g. this is called during map initialisation),
        // abort the computation (and assume callers can cope with m_Territories == NULL)
        CalculateCostGrid();
        if (!m_CostGrid)
                return;

        const u16 tilesW = m_CostGrid->m_W;
        const u16 tilesH = m_CostGrid->m_H;

        m_Territories = new Grid<u8>(tilesW, tilesH);

        // Reset territory counts for all players
        CmpPtr<ICmpPlayerManager> cmpPlayerManager(GetSystemEntity());
        if (cmpPlayerManager && (size_t)cmpPlayerManager->GetNumPlayers() != m_TerritoryCellCounts.size())
                m_TerritoryCellCounts.resize(cmpPlayerManager->GetNumPlayers());
        for (u16& count : m_TerritoryCellCounts)
                count = 0;

        // Find all territory influence entities
        CComponentManager::InterfaceList influences = GetSimContext().GetComponentManager().GetEntitiesWithInterface(IID_TerritoryInfluence);

        // Split influence entities into per-player lists, ignoring any with invalid properties
        std::map<player_id_t, std::vector<entity_id_t> > influenceEntities;
        for (const CComponentManager::InterfacePair& pair : influences)
        {
                entity_id_t ent = pair.first;

                CmpPtr<ICmpOwnership> cmpOwnership(GetSimContext(), ent);
                if (!cmpOwnership)
                        continue;

                // Ignore Gaia and unassigned or players we can't represent
                player_id_t owner = cmpOwnership->GetOwner();
                if (owner <= 0 || owner > TERRITORY_PLAYER_MASK)
                        continue;

                influenceEntities[owner].push_back(ent);
        }

        // Store the overall best weight for comparison
        Grid<u32> bestWeightGrid(tilesW, tilesH);
        // store the root influences to mark territory as connected
        std::vector<entity_id_t> rootInfluenceEntities;

        for (const std::pair<const player_id_t, std::vector<entity_id_t>>& pair : influenceEntities)
        {
                // entityGrid stores the weight for a single entity, and is reset per entity
                Grid<u32> entityGrid(tilesW, tilesH);
                // playerGrid stores the combined weight of all entities for this player
                Grid<u32> playerGrid(tilesW, tilesH);

                u8 owner = static_cast<u8>(pair.first);
                const std::vector<entity_id_t>& ents = pair.second;
                // With 2^16 entities, we're safe against overflows as the weight is also limited to 2^16
                ENSURE(ents.size() < 1 << 16);
                // Compute the influence map of the current entity, then add it to the player grid
                for (entity_id_t ent : ents)
                {
                        CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), ent);
                        if (!cmpPosition || !cmpPosition->IsInWorld())
                                continue;

                        CmpPtr<ICmpTerritoryInfluence> cmpTerritoryInfluence(GetSimContext(), ent);
                        u32 weight = cmpTerritoryInfluence->GetWeight();
                        u32 radius = cmpTerritoryInfluence->GetRadius();
                        if (weight == 0 || radius == 0)
                                continue;
                        u32 falloff = weight * (Pathfinding::NAVCELL_SIZE * NAVCELLS_PER_TERRITORY_TILE).ToInt_RoundToNegInfinity() / radius;

                        CFixedVector2D pos = cmpPosition->GetPosition2D();
                        u16 i, j;
                        NearestTerritoryTile(pos.X, pos.Y, i, j, tilesW, tilesH);

                        if (cmpTerritoryInfluence->IsRoot())
                                rootInfluenceEntities.push_back(ent);

                        // Initialise the tile under the entity
                        entityGrid.set(i, j, weight);
                        if (weight > bestWeightGrid.get(i, j))
                        {
                                bestWeightGrid.set(i, j, weight);
                                m_Territories->set(i, j, owner);
                        }

                        // Expand influences outwards
                        FLOODFILL(i, j,
                                u32 dg = falloff * m_CostGrid->get(nx, nz);

                                // diagonal neighbour -> multiply with approx sqrt(2)
                                if (nx != posX && nz != posZ)
                                        dg = (dg * 362) / 256;

                                // Don't expand if new cost is not better than previous value for that tile
                                // (arranged to avoid underflow if entityGrid.get(x, z) < dg)
                                if (entityGrid.get(posX, posZ) <= entityGrid.get(nx, nz) + dg)
                                        continue;

                                // weight of this tile = weight of predecessor - falloff from predecessor
                                u32 newWeight = entityGrid.get(posX, posZ) - dg;
                                u32 totalWeight = playerGrid.get(nx, nz) - entityGrid.get(nx, nz) + newWeight;
                                playerGrid.set(nx, nz, totalWeight);
                                entityGrid.set(nx, nz, newWeight);
                                // if this weight is better than the best thus far, set the owner
                                if (totalWeight > bestWeightGrid.get(nx, nz))
                                {
                                        bestWeightGrid.set(nx, nz, totalWeight);
                                        m_Territories->set(nx, nz, owner);
                                }
                        );

                        entityGrid.reset();
                }
        }

        // Detect territories connected to a 'root' influence (typically a civ center)
        // belonging to their player, and mark them with the connected flag
        for (entity_id_t ent : rootInfluenceEntities)
        {
                // (These components must be valid else the entities wouldn't be added to this list)
                CmpPtr<ICmpOwnership> cmpOwnership(GetSimContext(), ent);
                CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), ent);

                CFixedVector2D pos = cmpPosition->GetPosition2D();
                u16 i, j;
                NearestTerritoryTile(pos.X, pos.Y, i, j, tilesW, tilesH);

                u8 owner = (u8)cmpOwnership->GetOwner();

                if (m_Territories->get(i, j) != owner)
                        continue;

                m_Territories->set(i, j, owner | TERRITORY_CONNECTED_MASK);

                FLOODFILL(i, j,
                        // Don't expand non-owner tiles, or tiles that already have a connected mask
                        if (m_Territories->get(nx, nz) != owner)
                                continue;
                        m_Territories->set(nx, nz, owner | TERRITORY_CONNECTED_MASK);
                        if (m_CostGrid->get(nx, nz) < m_ImpassableCost)
                                ++m_TerritoryCellCounts[owner];
                );
        }

        // Then recomputes the blinking tiles
        CmpPtr<ICmpTerritoryDecayManager> cmpTerritoryDecayManager(GetSystemEntity());
        if (cmpTerritoryDecayManager)
        {
                size_t dirtyBlinkingID = m_DirtyBlinkingID;
                cmpTerritoryDecayManager->SetBlinkingEntities();
                m_DirtyBlinkingID = dirtyBlinkingID;
        }
}

std::vector<STerritoryBoundary> CCmpTerritoryManager::ComputeBoundaries()
{
        PROFILE("ComputeBoundaries");

        CalculateTerritories();
        ENSURE(m_Territories);

        return CTerritoryBoundaryCalculator::ComputeBoundaries(m_Territories);
}

u8 CCmpTerritoryManager::GetTerritoryPercentage(player_id_t player)
{
        if (player <= 0 || static_cast<size_t>(player) >= m_TerritoryCellCounts.size())
                return 0;

        CalculateTerritories();

        // Territories may have been recalculated, check whether player is still there.
        if (m_TerritoryTotalPassableCellCount == 0 || static_cast<size_t>(player) >= m_TerritoryCellCounts.size())
                return 0;

        u8 percentage = (m_TerritoryCellCounts[player] * 100) / m_TerritoryTotalPassableCellCount;
        ENSURE(percentage <= 100);
        return percentage;
}

void CCmpTerritoryManager::UpdateBoundaryLines()
{
        PROFILE("update boundary lines");

        m_BoundaryLines.clear();
        m_DebugBoundaryLineNodes.clear();

        if (!CRenderer::IsInitialised())
                return;

        std::vector<STerritoryBoundary> boundaries = ComputeBoundaries();

        CTextureProperties texturePropsBase("art/textures/misc/territory_border.png");
        texturePropsBase.SetAddressMode(
                Renderer::Backend::Sampler::AddressMode::CLAMP_TO_BORDER,
                Renderer::Backend::Sampler::AddressMode::CLAMP_TO_EDGE);
        texturePropsBase.SetAnisotropicFilter(true);
        CTexturePtr textureBase = g_Renderer.GetTextureManager().CreateTexture(texturePropsBase);

        CTextureProperties texturePropsMask("art/textures/misc/territory_border_mask.png");
        texturePropsMask.SetAddressMode(
                Renderer::Backend::Sampler::AddressMode::CLAMP_TO_BORDER,
                Renderer::Backend::Sampler::AddressMode::CLAMP_TO_EDGE);
        texturePropsMask.SetAnisotropicFilter(true);
        CTexturePtr textureMask = g_Renderer.GetTextureManager().CreateTexture(texturePropsMask);

        CmpPtr<ICmpPlayerManager> cmpPlayerManager(GetSystemEntity());
        if (!cmpPlayerManager)
                return;

        for (size_t i = 0; i < boundaries.size(); ++i)
        {
                if (boundaries[i].points.empty())
                        continue;

                CColor color(1, 0, 1, 1);
                CmpPtr<ICmpPlayer> cmpPlayer(GetSimContext(), cmpPlayerManager->GetPlayerByID(boundaries[i].owner));
                if (cmpPlayer)
                        color = cmpPlayer->GetDisplayedColor();

                m_BoundaryLines.push_back(SBoundaryLine());
                m_BoundaryLines.back().blinking = boundaries[i].blinking;
                m_BoundaryLines.back().owner = boundaries[i].owner;
                m_BoundaryLines.back().color = color;
                m_BoundaryLines.back().overlay.m_SimContext = &GetSimContext();
                m_BoundaryLines.back().overlay.m_TextureBase = textureBase;
                m_BoundaryLines.back().overlay.m_TextureMask = textureMask;
                m_BoundaryLines.back().overlay.m_Color = color;
                m_BoundaryLines.back().overlay.m_Thickness = m_BorderThickness;
                m_BoundaryLines.back().overlay.m_Closed = true;

                SimRender::SmoothPointsAverage(boundaries[i].points, m_BoundaryLines.back().overlay.m_Closed);
                SimRender::InterpolatePointsRNS(boundaries[i].points, m_BoundaryLines.back().overlay.m_Closed, m_BorderSeparation);

                std::vector<CVector2D>& points = m_BoundaryLines.back().overlay.m_Coords;
                for (size_t j = 0; j < boundaries[i].points.size(); ++j)
                {
                        points.push_back(boundaries[i].points[j]);

                        if (m_EnableLineDebugOverlays)
                        {
                                const size_t numHighlightNodes = 7; // highlight the X last nodes on either end to see where they meet (if closed)
                                SOverlayLine overlayNode;
                                if (j > boundaries[i].points.size() - 1 - numHighlightNodes)
                                        overlayNode.m_Color = CColor(1.f, 0.f, 0.f, 1.f);
                                else if (j < numHighlightNodes)
                                        overlayNode.m_Color = CColor(0.f, 1.f, 0.f, 1.f);
                                else
                                        overlayNode.m_Color = CColor(1.0f, 1.0f, 1.0f, 1.0f);

                                overlayNode.m_Thickness = 0.1f;
                                SimRender::ConstructCircleOnGround(GetSimContext(), boundaries[i].points[j].X, boundaries[i].points[j].Y, 0.1f, overlayNode, true);
                                m_DebugBoundaryLineNodes.push_back(overlayNode);
                        }
                }

        }
}

void CCmpTerritoryManager::Interpolate(float frameTime, float UNUSED(frameOffset))
{
        m_AnimTime += frameTime;

        if (m_BoundaryLinesDirty)
        {
                UpdateBoundaryLines();
                m_BoundaryLinesDirty = false;
        }

        for (size_t i = 0; i < m_BoundaryLines.size(); ++i)
        {
                if (m_BoundaryLines[i].blinking)
                {
                        CColor c = m_BoundaryLines[i].color;
                        c.a *= 0.2f + 0.8f * fabsf((float)cos(m_AnimTime * M_PI)); // TODO: should let artists tweak this
                        m_BoundaryLines[i].overlay.m_Color = c;
                }
        }
}

void CCmpTerritoryManager::RenderSubmit(SceneCollector& collector, const CFrustum& frustum, bool culling)
{
        if (!m_Visible)
                return;

        for (size_t i = 0; i < m_BoundaryLines.size(); ++i)
        {
                if (culling && !m_BoundaryLines[i].overlay.IsVisibleInFrustum(frustum))
                        continue;
                collector.Submit(&m_BoundaryLines[i].overlay);
        }

        for (size_t i = 0; i < m_DebugBoundaryLineNodes.size(); ++i)
                collector.Submit(&m_DebugBoundaryLineNodes[i]);

}

player_id_t CCmpTerritoryManager::GetOwner(entity_pos_t x, entity_pos_t z)
{
        u16 i, j;
        if (!m_Territories)
        {
                CalculateTerritories();
                if (!m_Territories)
                        return 0;
        }

        NearestTerritoryTile(x, z, i, j, m_Territories->m_W, m_Territories->m_H);
        return m_Territories->get(i, j) & TERRITORY_PLAYER_MASK;
}

std::vector<u32> CCmpTerritoryManager::GetNeighbours(entity_pos_t x, entity_pos_t z, bool filterConnected)
{
        CmpPtr<ICmpPlayerManager> cmpPlayerManager(GetSystemEntity());
        if (!cmpPlayerManager)
                return std::vector<u32>();

        std::vector<u32> ret(cmpPlayerManager->GetNumPlayers(), 0);
        CalculateTerritories();
        if (!m_Territories)
                return ret;

        u16 i, j;
        NearestTerritoryTile(x, z, i, j, m_Territories->m_W, m_Territories->m_H);

        // calculate the neighbours
        player_id_t thisOwner = m_Territories->get(i, j) & TERRITORY_PLAYER_MASK;

        u16 tilesW = m_Territories->m_W;
        u16 tilesH = m_Territories->m_H;

        // use a flood-fill algorithm that fills up to the borders and remembers the owners
        Grid<bool> markerGrid(tilesW, tilesH);
        markerGrid.set(i, j, true);

        FLOODFILL(i, j,
                if (markerGrid.get(nx, nz))
                        continue;
                // mark the tile as visited in any case
                markerGrid.set(nx, nz, true);
                int owner = m_Territories->get(nx, nz) & TERRITORY_PLAYER_MASK;
                if (owner != thisOwner)
                {
                        if (owner == 0 || !filterConnected || (m_Territories->get(nx, nz) & TERRITORY_CONNECTED_MASK) != 0)
                                ret[owner]++; // add player to the neighbour list when requested
                        continue; // don't expand non-owner tiles further
                }
        );

        return ret;
}

bool CCmpTerritoryManager::IsConnected(entity_pos_t x, entity_pos_t z)
{
        u16 i, j;
        CalculateTerritories();
        if (!m_Territories)
                return false;

        NearestTerritoryTile(x, z, i, j, m_Territories->m_W, m_Territories->m_H);
        return (m_Territories->get(i, j) & TERRITORY_CONNECTED_MASK) != 0;
}

void CCmpTerritoryManager::SetTerritoryBlinking(entity_pos_t x, entity_pos_t z, bool enable)
{
        CalculateTerritories();
        if (!m_Territories)
                return;

        u16 i, j;
        NearestTerritoryTile(x, z, i, j, m_Territories->m_W, m_Territories->m_H);

        u16 tilesW = m_Territories->m_W;
        u16 tilesH = m_Territories->m_H;

        player_id_t thisOwner = m_Territories->get(i, j) & TERRITORY_PLAYER_MASK;

        FLOODFILL(i, j,
                u8 bitmask = m_Territories->get(nx, nz);
                if ((bitmask & TERRITORY_PLAYER_MASK) != thisOwner)
                        continue;
                u8 blinking = bitmask & TERRITORY_BLINKING_MASK;
                if (enable && !blinking)
                        m_Territories->set(nx, nz, bitmask | TERRITORY_BLINKING_MASK);
                else if (!enable && blinking)
                        m_Territories->set(nx, nz, bitmask & ~TERRITORY_BLINKING_MASK);
                else
                        continue;
        );
        ++m_DirtyBlinkingID;
        m_BoundaryLinesDirty = true;
}

bool CCmpTerritoryManager::IsTerritoryBlinking(entity_pos_t x, entity_pos_t z)
{
        CalculateTerritories();
        if (!m_Territories)
                return false;

        u16 i, j;
        NearestTerritoryTile(x, z, i, j, m_Territories->m_W, m_Territories->m_H);
        return (m_Territories->get(i, j) & TERRITORY_BLINKING_MASK) != 0;
}

void CCmpTerritoryManager::UpdateColors()
{
        m_ColorChanged = true;

        CmpPtr<ICmpPlayerManager> cmpPlayerManager(GetSystemEntity());
        if (!cmpPlayerManager)
                return;

        for (SBoundaryLine& boundaryLine : m_BoundaryLines)
        {
                CmpPtr<ICmpPlayer> cmpPlayer(GetSimContext(), cmpPlayerManager->GetPlayerByID(boundaryLine.owner));
                if (!cmpPlayer)
                        continue;

                boundaryLine.color = cmpPlayer->GetDisplayedColor();
                boundaryLine.overlay.m_Color = boundaryLine.color;
        }
}

TerritoryOverlay::TerritoryOverlay(CCmpTerritoryManager& manager) :
        TerrainTextureOverlay((float)Pathfinding::NAVCELLS_PER_TERRAIN_TILE / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE),
        m_TerritoryManager(manager)
{ }

void TerritoryOverlay::BuildTextureRGBA(u8* data, size_t w, size_t h)
{
        for (size_t j = 0; j < h; ++j)
        {
                for (size_t i = 0; i < w; ++i)
                {
                        SColor4ub color;
                        u8 id = (m_TerritoryManager.m_Territories->get((int)i, (int)j) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK);
                        color = GetColor(id, 64);
                        *data++ = color.R;
                        *data++ = color.G;
                        *data++ = color.B;
                        *data++ = color.A;
                }
        }
}

#undef FLOODFILL