Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Tile.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder_Tile.cpp (revision 16750) +++ ps/trunk/source/simulation2/components/CCmpPathfinder_Tile.cpp (nonexistent) @@ -1,502 +0,0 @@ -/* 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 . - */ - -/** - * @file - * Tile-based algorithm for CCmpPathfinder. - * This is a fairly naive algorithm and could probably be improved substantially - * (hopefully without needing to change the interface much). - */ - -#include "precompiled.h" - -#include "CCmpPathfinder_Common.h" - -#include "ps/Profile.h" -#include "renderer/TerrainOverlay.h" -#include "simulation2/helpers/PriorityQueue.h" - -typedef PriorityQueueHeap, u32> PriorityQueue; - -#define PATHFIND_STATS 0 - -#define USE_DIAGONAL_MOVEMENT 1 - -// Heuristic cost to move between adjacent tiles. -// This should be similar to DEFAULT_MOVE_COST. -const u32 g_CostPerTile = 256; - -/** - * Tile data for A* computation. - * (We store an array of one of these per terrain tile, so it ought to be optimised for size) - */ -struct PathfindTile -{ -public: - enum { - STATUS_UNEXPLORED = 0, - STATUS_OPEN = 1, - STATUS_CLOSED = 2 - }; - - bool IsUnexplored() { return status == STATUS_UNEXPLORED; } - bool IsOpen() { return status == STATUS_OPEN; } - bool IsClosed() { return status == STATUS_CLOSED; } - void SetStatusOpen() { status = STATUS_OPEN; } - void SetStatusClosed() { status = STATUS_CLOSED; } - - // Get pi,pj coords of predecessor to this tile on best path, given i,j coords of this tile - u16 GetPredI(u16 i) { return (u16)(i + dpi); } - u16 GetPredJ(u16 j) { return (u16)(j + dpj); } - // Set the pi,pj coords of predecessor, given i,j coords of this tile - void SetPred(u16 pi_, u16 pj_, u16 i, u16 j) - { - dpi = (i8)((int)pi_ - (int)i); - dpj = (i8)((int)pj_ - (int)j); -#if PATHFIND_DEBUG - // predecessor must be adjacent - ENSURE(pi_-i == -1 || pi_-i == 0 || pi_-i == 1); - ENSURE(pj_-j == -1 || pj_-j == 0 || pj_-j == 1); -#endif - } - -private: - u8 status; // this only needs 2 bits - i8 dpi, dpj; // these only really need 2 bits in total -public: - u32 cost; // g (cost to this tile) - u32 h; // h (heuristic cost to goal) (TODO: is it really better for performance to store this instead of recomputing?) - -#if PATHFIND_DEBUG - u32 GetStep() { return step; } - void SetStep(u32 s) { step = s; } -private: - u32 step; // step at which this tile was last processed (for debug rendering) -#else - u32 GetStep() { return 0; } - void SetStep(u32) { } -#endif - -}; - -/** - * Terrain overlay for pathfinder debugging. - * Renders a representation of the most recent pathfinding operation. - */ -class PathfinderOverlay : public TerrainOverlay -{ - NONCOPYABLE(PathfinderOverlay); -public: - CCmpPathfinder& m_Pathfinder; - - PathfinderOverlay(CCmpPathfinder& pathfinder) - : TerrainOverlay(pathfinder.GetSimContext()), m_Pathfinder(pathfinder) - { - } - - virtual void StartRender() - { - m_Pathfinder.UpdateGrid(); - } - - virtual void ProcessTile(ssize_t i, ssize_t j) - { - if (m_Pathfinder.m_Grid && !IS_PASSABLE(m_Pathfinder.m_Grid->get((int)i, (int)j), m_Pathfinder.m_DebugPassClass)) - RenderTile(CColor(1, 0, 0, 0.6f), false); - - if (m_Pathfinder.m_DebugGrid) - { - PathfindTile& n = m_Pathfinder.m_DebugGrid->get((int)i, (int)j); - - float c = clamp((float)n.GetStep() / (float)m_Pathfinder.m_DebugSteps, 0.f, 1.f); - - if (n.IsOpen()) - RenderTile(CColor(1, 1, c, 0.6f), false); - else if (n.IsClosed()) - RenderTile(CColor(0, 1, c, 0.6f), false); - } - } - - virtual void EndRender() - { - if (m_Pathfinder.m_DebugPath) - { - std::vector& wp = m_Pathfinder.m_DebugPath->m_Waypoints; - for (size_t n = 0; n < wp.size(); ++n) - { - u16 i, j; - m_Pathfinder.NearestTile(wp[n].x, wp[n].z, i, j); - RenderTileOutline(CColor(1, 1, 1, 1), 2, false, i, j); - } - } - } -}; - -void CCmpPathfinder::SetDebugOverlay(bool enabled) -{ - if (enabled && !m_DebugOverlay) - { - m_DebugOverlay = new PathfinderOverlay(*this); - } - else if (!enabled && m_DebugOverlay) - { - delete m_DebugOverlay; - m_DebugOverlay = NULL; - } -} - -void CCmpPathfinder::SetDebugPath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass) -{ - if (!m_DebugOverlay) - return; - - delete m_DebugGrid; - m_DebugGrid = NULL; - delete m_DebugPath; - m_DebugPath = new Path(); - ComputePath(x0, z0, goal, passClass, costClass, *m_DebugPath); - m_DebugPassClass = passClass; -} - -void CCmpPathfinder::ResetDebugPath() -{ - delete m_DebugGrid; - m_DebugGrid = NULL; - delete m_DebugPath; - m_DebugPath = NULL; -} - - -////////////////////////////////////////////////////////// - - -struct PathfinderState -{ - u32 steps; // number of algorithm iterations - - u16 iGoal, jGoal; // goal tile - u16 rGoal; // radius of goal (around tile center) - - ICmpPathfinder::pass_class_t passClass; - std::vector moveCosts; - - PriorityQueue open; - // (there's no explicit closed list; it's encoded in PathfindTile) - - PathfindTileGrid* tiles; - Grid* terrain; - - bool ignoreImpassable; // allows us to escape if stuck in patches of impassability - - u32 hBest; // heuristic of closest discovered tile to goal - u16 iBest, jBest; // closest tile - -#if PATHFIND_STATS - // Performance debug counters - size_t numProcessed; - size_t numImproveOpen; - size_t numImproveClosed; - size_t numAddToOpen; - size_t sumOpenSize; -#endif -}; - -static bool AtGoal(u16 i, u16 j, const ICmpPathfinder::Goal& goal) -{ - // Allow tiles slightly more than sqrt(2) from the actual goal, - // i.e. adjacent diagonally to the target tile - fixed tolerance = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*3/2); - - entity_pos_t x, z; - CCmpPathfinder::TileCenter(i, j, x, z); - fixed dist = CCmpPathfinder::DistanceToGoal(CFixedVector2D(x, z), goal); - return (dist < tolerance); -} - -// Calculate heuristic cost from tile i,j to destination -// (This ought to be an underestimate for correctness) -static u32 CalculateHeuristic(u16 i, u16 j, u16 iGoal, u16 jGoal, u16 rGoal) -{ -#if USE_DIAGONAL_MOVEMENT - CFixedVector2D pos (fixed::FromInt(i), fixed::FromInt(j)); - CFixedVector2D goal (fixed::FromInt(iGoal), fixed::FromInt(jGoal)); - fixed dist = (pos - goal).Length(); - // TODO: the heuristic could match the costs better - it's not really Euclidean movement - - fixed rdist = dist - fixed::FromInt(rGoal); - rdist = rdist.Absolute(); - - // To avoid overflows on large distances we have to convert to int before multiplying - // by the full tile cost, which means we lose some accuracy over short distances, - // so do a partial multiplication here. - // (This will overflow if sqrt(2)*tilesPerSide*premul >= 32768, so - // premul=32 means max tilesPerSide=724) - const int premul = 32; - cassert(g_CostPerTile % premul == 0); - return (rdist * premul).ToInt_RoundToZero() * (g_CostPerTile / premul); - -#else - return (abs((int)i - (int)iGoal) + abs((int)j - (int)jGoal)) * g_CostPerTile; -#endif -} - -// Calculate movement cost from predecessor tile pi,pj to tile i,j -static u32 CalculateCostDelta(u16 pi, u16 pj, u16 i, u16 j, PathfindTileGrid* tempGrid, u32 tileCost) -{ - u32 dg = tileCost; - -#if USE_DIAGONAL_MOVEMENT - // XXX: Probably a terrible hack: - // For simplicity, we only consider horizontally/vertically adjacent neighbours, but - // units can move along arbitrary lines. That results in ugly square paths, so we want - // to prefer diagonal paths. - // Instead of solving this nicely, I'll just special-case 45-degree and 30-degree lines - // by checking the three predecessor tiles (which'll be in the closed set and therefore - // likely to be reasonably stable) and reducing the cost, and use a Euclidean heuristic. - // At least this makes paths look a bit nicer for now... - - PathfindTile& p = tempGrid->get(pi, pj); - u16 ppi = p.GetPredI(pi); - u16 ppj = p.GetPredJ(pj); - if (ppi != i && ppj != j) - dg = (dg << 16) / 92682; // dg*sqrt(2)/2 - else - { - PathfindTile& pp = tempGrid->get(ppi, ppj); - int di = abs(i - pp.GetPredI(ppi)); - int dj = abs(j - pp.GetPredJ(ppj)); - if ((di == 1 && dj == 2) || (di == 2 && dj == 1)) - dg = (dg << 16) / 79742; // dg*(sqrt(5)-sqrt(2)) - } -#endif - - return dg; -} - -// Do the A* processing for a neighbour tile i,j. -static void ProcessNeighbour(u16 pi, u16 pj, u16 i, u16 j, u32 pg, PathfinderState& state) -{ -#if PATHFIND_STATS - state.numProcessed++; -#endif - - // Reject impassable tiles - TerrainTile tileTag = state.terrain->get(i, j); - if (!IS_PASSABLE(tileTag, state.passClass) && !state.ignoreImpassable) - return; - - u32 dg = CalculateCostDelta(pi, pj, i, j, state.tiles, state.moveCosts.at(GET_COST_CLASS(tileTag))); - - u32 g = pg + dg; // cost to this tile = cost to predecessor + delta from predecessor - - PathfindTile& n = state.tiles->get(i, j); - - // If this is a new tile, compute the heuristic distance - if (n.IsUnexplored()) - { - n.h = CalculateHeuristic(i, j, state.iGoal, state.jGoal, state.rGoal); - // Remember the best tile we've seen so far, in case we never actually reach the target - if (n.h < state.hBest) - { - state.hBest = n.h; - state.iBest = i; - state.jBest = j; - } - } - else - { - // If we've already seen this tile, and the new path to this tile does not have a - // better cost, then stop now - if (g >= n.cost) - return; - - // Otherwise, we have a better path. - - // If we've already added this tile to the open list: - if (n.IsOpen()) - { - // This is a better path, so replace the old one with the new cost/parent - n.cost = g; - n.SetPred(pi, pj, i, j); - n.SetStep(state.steps); - state.open.promote(std::make_pair(i, j), g + n.h); -#if PATHFIND_STATS - state.numImproveOpen++; -#endif - return; - } - - // If we've already found the 'best' path to this tile: - if (n.IsClosed()) - { - // This is a better path (possible when we use inadmissible heuristics), so reopen it -#if PATHFIND_STATS - state.numImproveClosed++; -#endif - // (fall through) - } - } - - // Add it to the open list: - n.SetStatusOpen(); - n.cost = g; - n.SetPred(pi, pj, i, j); - n.SetStep(state.steps); - PriorityQueue::Item t = { std::make_pair(i, j), g + n.h }; - state.open.push(t); -#if PATHFIND_STATS - state.numAddToOpen++; -#endif -} - -void CCmpPathfinder::ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, Path& path) -{ - UpdateGrid(); - - PROFILE3("ComputePath"); - - PathfinderState state = { 0 }; - - // Convert the start/end coordinates to tile indexes - u16 i0, j0; - NearestTile(x0, z0, i0, j0); - NearestTile(goal.x, goal.z, state.iGoal, state.jGoal); - - // If we're already at the goal tile, then move directly to the exact goal coordinates - if (AtGoal(i0, j0, goal)) - { - Waypoint w = { goal.x, goal.z }; - path.m_Waypoints.push_back(w); - return; - } - - // If the target is a circle, we want to aim for the edge of it (so e.g. if we're inside - // a large circle then the heuristics will aim us directly outwards); - // otherwise just aim at the center point. (We'll never try moving outwards to a square shape.) - if (goal.type == Goal::CIRCLE) - state.rGoal = (u16)(goal.hw / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(); - else - state.rGoal = 0; - - state.passClass = passClass; - state.moveCosts = m_MoveCosts.at(costClass); - - state.steps = 0; - - state.tiles = new PathfindTileGrid(m_MapSize, m_MapSize); - state.terrain = m_Grid; - - state.iBest = i0; - state.jBest = j0; - state.hBest = CalculateHeuristic(i0, j0, state.iGoal, state.jGoal, state.rGoal); - - PriorityQueue::Item start = { std::make_pair(i0, j0), 0 }; - state.open.push(start); - state.tiles->get(i0, j0).SetStatusOpen(); - state.tiles->get(i0, j0).SetPred(i0, j0, i0, j0); - state.tiles->get(i0, j0).cost = 0; - - // To prevent units getting very stuck, if they start on an impassable tile - // surrounded entirely by impassable tiles, we ignore the impassability - state.ignoreImpassable = !IS_PASSABLE(state.terrain->get(i0, j0), state.passClass); - - while (1) - { - ++state.steps; - - // Hack to avoid spending ages computing giant paths, particularly when - // the destination is unreachable - if (state.steps > 40000) - break; - - // If we ran out of tiles to examine, give up - if (state.open.empty()) - break; - -#if PATHFIND_STATS - state.sumOpenSize += state.open.size(); -#endif - - // Move best tile from open to closed - PriorityQueue::Item curr = state.open.pop(); - u16 i = curr.id.first; - u16 j = curr.id.second; - state.tiles->get(i, j).SetStatusClosed(); - - // If we've reached the destination, stop - if (AtGoal(i, j, goal)) - { - state.iBest = i; - state.jBest = j; - state.hBest = 0; - break; - } - - // As soon as we find an escape route from the impassable terrain, - // take it and forbid any further use of impassable tiles - if (state.ignoreImpassable) - { - if (i > 0 && IS_PASSABLE(state.terrain->get(i-1, j), state.passClass)) - state.ignoreImpassable = false; - else if (i < m_MapSize-1 && IS_PASSABLE(state.terrain->get(i+1, j), state.passClass)) - state.ignoreImpassable = false; - else if (j > 0 && IS_PASSABLE(state.terrain->get(i, j-1), state.passClass)) - state.ignoreImpassable = false; - else if (j < m_MapSize-1 && IS_PASSABLE(state.terrain->get(i, j+1), state.passClass)) - state.ignoreImpassable = false; - } - - u32 g = state.tiles->get(i, j).cost; - if (i > 0) - ProcessNeighbour(i, j, (u16)(i-1), j, g, state); - if (i < m_MapSize-1) - ProcessNeighbour(i, j, (u16)(i+1), j, g, state); - if (j > 0) - ProcessNeighbour(i, j, i, (u16)(j-1), g, state); - if (j < m_MapSize-1) - ProcessNeighbour(i, j, i, (u16)(j+1), g, state); - } - - // Reconstruct the path (in reverse) - u16 ip = state.iBest, jp = state.jBest; - while (ip != i0 || jp != j0) - { - PathfindTile& n = state.tiles->get(ip, jp); - entity_pos_t x, z; - TileCenter(ip, jp, x, z); - Waypoint w = { x, z }; - path.m_Waypoints.push_back(w); - - // Follow the predecessor link - ip = n.GetPredI(ip); - jp = n.GetPredJ(jp); - } - - // Save this grid for debug display - delete m_DebugGrid; - m_DebugGrid = state.tiles; - m_DebugSteps = state.steps; - - PROFILE2_ATTR("from: (%d, %d)", i0, j0); - PROFILE2_ATTR("to: (%d, %d)", state.iGoal, state.jGoal); - PROFILE2_ATTR("reached: (%d, %d)", state.iBest, state.jBest); - PROFILE2_ATTR("steps: %u", state.steps); - -#if PATHFIND_STATS - printf("PATHFINDER: steps=%d avgo=%d proc=%d impc=%d impo=%d addo=%d\n", state.steps, state.sumOpenSize/state.steps, state.numProcessed, state.numImproveClosed, state.numImproveOpen, state.numAddToOpen); -#endif -} Property changes on: ps/trunk/source/simulation2/components/CCmpPathfinder_Tile.cpp ___________________________________________________________________ Deleted: svn:eol-style ## -1 +0,0 ## -native \ No newline at end of property Index: ps/trunk/source/renderer/TerrainOverlay.h =================================================================== --- ps/trunk/source/renderer/TerrainOverlay.h (revision 16750) +++ ps/trunk/source/renderer/TerrainOverlay.h (revision 16751) @@ -1,197 +1,204 @@ /* Copyright (C) 2012 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 . */ /* * System for representing tile-based information on top of the * terrain. */ #ifndef INCLUDED_TERRAINOVERLAY #define INCLUDED_TERRAINOVERLAY #include "lib/ogl.h" struct CColor; +struct SColor4ub; class CTerrain; class CSimContext; /** * Common interface for terrain-tile-based and texture-based debug overlays. * * An overlay object will be rendered for as long as it is allocated * (it is automatically registered/deregistered by constructor/destructor). */ class ITerrainOverlay { NONCOPYABLE(ITerrainOverlay); public: virtual ~ITerrainOverlay(); virtual void RenderBeforeWater() { } virtual void RenderAfterWater(int UNUSED(cullGroup)) { } /** * Draw all ITerrainOverlay objects that exist * and that should be drawn before water. */ static void RenderOverlaysBeforeWater(); /** * Draw all ITerrainOverlay objects that exist * and that should be drawn after water. */ static void RenderOverlaysAfterWater(int cullGroup); protected: ITerrainOverlay(int priority); }; /** * Base class for (relatively) simple drawing of * data onto terrain tiles, intended for debugging purposes and for the Atlas * editor (hence not trying to be very efficient). * * To start drawing a terrain overlay, first create a subclass of TerrainOverlay. * Override the method GetTileExtents if you want to change the range over which * it is drawn. * Override ProcessTile to do your processing for each tile, which should call * RenderTile and RenderTileOutline as appropriate. */ class TerrainOverlay : public ITerrainOverlay { protected: /** * Construct the object and register it with the global * list of terrain overlays. *

* The priority parameter controls the order in which overlays are drawn, * if several exist - they are processed in order of increasing priority, * so later ones draw on top of earlier ones. * Most should use the default of 100. Numbers from 200 are used * by Atlas. * * @param priority controls the order of drawing */ TerrainOverlay(const CSimContext& simContext, int priority = 100); /** * Override to perform processing at the start of the overlay rendering, * before the ProcessTile calls */ virtual void StartRender(); /** * Override to perform processing at the end of the overlay rendering, * after the ProcessTile calls */ virtual void EndRender(); /** * Override to limit the range over which ProcessTile will * be called. Defaults to the size of the map. * * @param min_i_inclusive [output] smallest i coordinate, in tile-space units * (1 unit per tile, +i is world-space +x and game-space East) * @param min_j_inclusive [output] smallest j coordinate * (+j is world-space +z and game-space North) * @param max_i_inclusive [output] largest i coordinate * @param max_j_inclusive [output] largest j coordinate */ virtual void GetTileExtents(ssize_t& min_i_inclusive, ssize_t& min_j_inclusive, ssize_t& max_i_inclusive, ssize_t& max_j_inclusive); /** * Override to perform processing of each tile. Typically calls * RenderTile and/or RenderTileOutline. * * @param i i coordinate of tile being processed * @param j j coordinate of tile being processed */ virtual void ProcessTile(ssize_t i, ssize_t j) = 0; /** * Draw a filled quad on top of the current tile. * * @param color color to draw. May be transparent (alpha < 1) * @param draw_hidden true if hidden tiles (i.e. those behind other tiles) * should be drawn */ void RenderTile(const CColor& color, bool draw_hidden); /** * Draw a filled quad on top of the given tile. */ void RenderTile(const CColor& color, bool draw_hidden, ssize_t i, ssize_t j); /** * Draw an outlined quad on top of the current tile. * * @param color color to draw. May be transparent (alpha < 1) * @param line_width width of lines in pixels. 1 is a sensible value * @param draw_hidden true if hidden tiles (i.e. those behind other tiles) * should be drawn */ void RenderTileOutline(const CColor& color, int line_width, bool draw_hidden); /** * Draw an outlined quad on top of the given tile. */ void RenderTileOutline(const CColor& color, int line_width, bool draw_hidden, ssize_t i, ssize_t j); private: // Process all tiles virtual void RenderBeforeWater(); // Temporary storage of tile coordinates, so ProcessTile doesn't need to // pass it to RenderTile/etc (and doesn't have a chance to get it wrong) ssize_t m_i, m_j; CTerrain* m_Terrain; }; /** * Base class for texture-based terrain overlays, with an arbitrary number of * texels per terrain tile, intended for debugging purposes. * Subclasses must implement BuildTextureRGBA which will be called each frame. */ class TerrainTextureOverlay : public ITerrainOverlay { public: TerrainTextureOverlay(float texelsPerTile, int priority = 100); virtual ~TerrainTextureOverlay(); protected: /** * Called each frame to generate the texture to render on the terrain. * @p data is w*h*4 bytes, where w and h are the terrain size multiplied * by texelsPerTile. @p data defaults to fully transparent, and should * be filled with data in RGBA order. */ virtual void BuildTextureRGBA(u8* data, size_t w, size_t h) = 0; + /** + * Returns an arbitrary color, for subclasses that want to distinguish + * different integers visually. + */ + SColor4ub GetColor(size_t idx, u8 alpha) const; + private: void RenderAfterWater(int cullGroup); float m_TexelsPerTile; GLuint m_Texture; GLsizei m_TextureW, m_TextureH; }; #endif // INCLUDED_TERRAINOVERLAY Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 16750) +++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 16751) @@ -1,311 +1,235 @@ /* Copyright (C) 2015 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_CCMPPATHFINDER_COMMON #define INCLUDED_CCMPPATHFINDER_COMMON /** * @file - * Declares CCmpPathfinder, whose implementation is split into multiple source files, - * and provides common code needed for more than one of those files. - * CCmpPathfinder includes two pathfinding algorithms (one tile-based, one vertex-based) - * with some shared state and functionality, so the code is split into - * CCmpPathfinder_Vertex.cpp, CCmpPathfinder_Tile.cpp and CCmpPathfinder.cpp + * Declares CCmpPathfinder. Its implementation is mainly done in CCmpPathfinder.cpp, + * but the short-range (vertex) pathfinding is done in CCmpPathfinder_Vertex.cpp. + * This file provides common code needed for both files. + * + * The long-range pathfinding is done by a LongPathfinder object. */ #include "simulation2/system/Component.h" #include "ICmpPathfinder.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/MathUtil.h" +#include "ps/CLogger.h" +#include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/helpers/Geometry.h" -#include "simulation2/helpers/Grid.h" +#include "simulation2/helpers/LongPathfinder.h" -class PathfinderOverlay; class SceneCollector; -struct PathfindTile; #ifdef NDEBUG #define PATHFIND_DEBUG 0 #else #define PATHFIND_DEBUG 1 #endif -/* - * For efficient pathfinding we want to try hard to minimise the per-tile search cost, - * so we precompute the tile passability flags and movement costs for the various different - * types of unit. - * We also want to minimise memory usage (there can easily be 100K tiles so we don't want - * to store many bytes for each). - * - * To handle passability efficiently, we have a small number of passability classes - * (e.g. "infantry", "ship"). Each unit belongs to a single passability class, and - * uses that for all its pathfinding. - * Passability is determined by water depth, terrain slope, forestness, buildingness. - * We need at least one bit per class per tile to represent passability. - * - * We use a separate bit to indicate building obstructions (instead of folding it into - * the class passabilities) so that it can be ignored when doing the accurate short paths. - * We use another bit to indicate tiles near obstructions that block construction, - * for the AI to plan safe building spots. - * - * To handle movement costs, we have an arbitrary number of unit cost classes (e.g. "infantry", "camel"), - * and a small number of terrain cost classes (e.g. "grass", "steep grass", "road", "sand"), - * and a cost mapping table between the classes (e.g. camels are fast on sand). - * We need log2(|terrain cost classes|) bits per tile to represent costs. - * - * We could have one passability bitmap per class, and another array for cost classes, - * but instead (for no particular reason) we'll pack them all into a single u16 array. - * - * We handle dynamic updates currently by recomputing the entire array, which is stupid; - * it should only bother updating the region that has changed. - */ -class PathfinderPassability -{ -public: - PathfinderPassability(ICmpPathfinder::pass_class_t mask, const CParamNode& node) : - m_Mask(mask) - { - if (node.GetChild("MinWaterDepth").IsOk()) - m_MinDepth = node.GetChild("MinWaterDepth").ToFixed(); - else - m_MinDepth = std::numeric_limits::min(); - - if (node.GetChild("MaxWaterDepth").IsOk()) - m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed(); - else - m_MaxDepth = std::numeric_limits::max(); - - if (node.GetChild("MaxTerrainSlope").IsOk()) - m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed(); - else - m_MaxSlope = std::numeric_limits::max(); - - if (node.GetChild("MinShoreDistance").IsOk()) - m_MinShore = node.GetChild("MinShoreDistance").ToFixed(); - else - m_MinShore = std::numeric_limits::min(); - - if (node.GetChild("MaxShoreDistance").IsOk()) - m_MaxShore = node.GetChild("MaxShoreDistance").ToFixed(); - else - m_MaxShore = std::numeric_limits::max(); - - } - - bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) - { - return ((m_MinDepth <= waterdepth && waterdepth <= m_MaxDepth) && (steepness < m_MaxSlope) && (m_MinShore <= shoredist && shoredist <= m_MaxShore)); - } - - ICmpPathfinder::pass_class_t m_Mask; -private: - fixed m_MinDepth; - fixed m_MaxDepth; - fixed m_MaxSlope; - fixed m_MinShore; - fixed m_MaxShore; -}; - -typedef u16 TerrainTile; -// 1 bit for pathfinding obstructions, -// 1 bit for construction obstructions (used by AI), -// PASS_CLASS_BITS for terrain passability (allowing PASS_CLASS_BITS classes), -// COST_CLASS_BITS for movement costs (allowing 2^COST_CLASS_BITS classes) - -const int PASS_CLASS_BITS = 10; -const int COST_CLASS_BITS = 16 - (PASS_CLASS_BITS + 2); -#define IS_TERRAIN_PASSABLE(item, classmask) (((item) & (classmask)) == 0) -#define IS_PASSABLE(item, classmask) (((item) & ((classmask) | 1)) == 0) -#define GET_COST_CLASS(item) ((item) >> (PASS_CLASS_BITS + 2)) -#define COST_CLASS_MASK(id) ( (TerrainTile) ((id) << (PASS_CLASS_BITS + 2)) ) - -typedef SparseGrid PathfindTileGrid; struct AsyncLongPathRequest { u32 ticket; entity_pos_t x0; entity_pos_t z0; - ICmpPathfinder::Goal goal; - ICmpPathfinder::pass_class_t passClass; - ICmpPathfinder::cost_class_t costClass; + PathGoal goal; + pass_class_t passClass; entity_id_t notify; }; struct AsyncShortPathRequest { u32 ticket; entity_pos_t x0; entity_pos_t z0; entity_pos_t r; entity_pos_t range; - ICmpPathfinder::Goal goal; - ICmpPathfinder::pass_class_t passClass; + PathGoal goal; + pass_class_t passClass; bool avoidMovingUnits; entity_id_t group; entity_id_t notify; }; /** * Implementation of ICmpPathfinder */ class CCmpPathfinder : public ICmpPathfinder { public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_Update); componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays componentManager.SubscribeToMessageType(MT_TerrainChanged); componentManager.SubscribeToMessageType(MT_WaterChanged); componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged); componentManager.SubscribeToMessageType(MT_TurnStart); } DEFAULT_COMPONENT_ALLOCATOR(Pathfinder) // Template state: std::map m_PassClassMasks; std::vector m_PassClasses; - std::map m_TerrainCostClassTags; - std::map m_UnitCostClassTags; - std::vector > m_MoveCosts; // costs[unitClass][terrainClass] - std::vector > m_MoveSpeeds; // speeds[unitClass][terrainClass] - // Dynamic state: std::vector m_AsyncLongPathRequests; std::vector m_AsyncShortPathRequests; u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn // Lazily-constructed dynamic state (not serialized): u16 m_MapSize; // tiles per side - Grid* m_Grid; // terrain/passability information - Grid* m_ObstructionGrid; // cached obstruction information (TODO: we shouldn't bother storing this, it's redundant with LSBs of m_Grid) + Grid* m_Grid; // terrain/passability information + Grid* m_BaseGrid; // same as m_Grid, but only with terrain, to avoid some recomputations bool m_TerrainDirty; // indicates if m_Grid has been updated since terrain changed - + + // Update data, stored for the AI manager + bool m_ObstructionsDirty; + bool m_ObstructionsGlobalUpdate; + Grid m_DirtinessGrid; + + // Interface to the long-range pathfinder. + LongPathfinder m_LongPathfinder; + // For responsiveness we will process some moves in the same turn they were generated in u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn - // Debugging - output from last pathfind operation: - - PathfindTileGrid* m_DebugGrid; - u32 m_DebugSteps; - Path* m_DebugPath; - PathfinderOverlay* m_DebugOverlay; - pass_class_t m_DebugPassClass; - + bool m_DebugOverlay; std::vector m_DebugOverlayShortPathLines; static std::string GetSchema() { return ""; } virtual void Init(const CParamNode& paramNode); virtual void Deinit(); virtual void Serialize(ISerializer& serialize); virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize); virtual void HandleMessage(const CMessage& msg, bool global); virtual pass_class_t GetPassabilityClass(const std::string& name); virtual std::map GetPassabilityClasses(); - virtual cost_class_t GetCostClass(const std::string& name); + const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const; + + virtual entity_pos_t GetClearance(pass_class_t passClass) const + { + const PathfinderPassability* passability = GetPassabilityFromMask(passClass); + + if (!passability->m_HasClearance) + return fixed::Zero(); + + return passability->m_Clearance; + } + + virtual entity_pos_t GetMaximumClearance() const + { + entity_pos_t max = fixed::Zero(); + + for (const PathfinderPassability& passability : m_PassClasses) + { + if (passability.m_HasClearance && passability.m_Clearance > max) + max = passability.m_Clearance; + } + + return max; + } virtual const Grid& GetPassabilityGrid(); - virtual Grid ComputeShoreGrid(bool expandOnWater = false); + virtual bool GetDirtinessData(Grid& dirtinessGrid, bool& globalUpdateNeeded); - virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, Path& ret); + virtual Grid ComputeShoreGrid(bool expandOnWater = false); - virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, entity_id_t notify); + virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) + { + m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret); + } - virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, pass_class_t passClass, Path& ret); + virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify); - virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify); + virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret); - virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass); + virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify); - virtual void ResetDebugPath(); + virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) + { + m_LongPathfinder.SetDebugPath(x0, z0, goal, passClass); + } - virtual void SetDebugOverlay(bool enabled); + virtual void SetDebugOverlay(bool enabled) + { + m_DebugOverlay = enabled; + m_LongPathfinder.SetDebugOverlay(enabled); + } - virtual fixed GetMovementSpeed(entity_pos_t x0, entity_pos_t z0, cost_class_t costClass); + virtual void SetHierDebugOverlay(bool enabled) + { + m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext()); + } - virtual CFixedVector2D GetNearestPointOnGoal(CFixedVector2D pos, const Goal& goal); + virtual void GetDebugData(u32& steps, double& time, Grid& grid) + { + m_LongPathfinder.GetDebugData(steps, time, grid); + } virtual bool CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, pass_class_t passClass); - virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass); - -virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint); + virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint); virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass); virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool onlyCenterPoint); virtual void FinishAsyncRequests(); void ProcessLongRequests(const std::vector& longRequests); void ProcessShortRequests(const std::vector& shortRequests); virtual void ProcessSameTurnMoves(); /** - * Returns the tile containing the given position - */ - void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j) - { - i = (u16)clamp((x / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1); - j = (u16)clamp((z / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(), 0, m_MapSize-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)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE/2); - z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE/2); - } - - static fixed DistanceToGoal(CFixedVector2D pos, const CCmpPathfinder::Goal& goal); - - /** * Regenerates the grid based on the current obstruction list, if necessary */ - void UpdateGrid(); + virtual void UpdateGrid(); + + void ComputeTerrainPassabilityGrid(const Grid& shoreGrid); void RenderSubmit(SceneCollector& collector); }; #endif // INCLUDED_CCMPPATHFINDER_COMMON Index: ps/trunk/source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpRangeManager.cpp (revision 16750) +++ ps/trunk/source/simulation2/components/CCmpRangeManager.cpp (revision 16751) @@ -1,2241 +1,2258 @@ /* Copyright (C) 2015 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 "ICmpTerrain.h" #include "simulation2/system/EntityMap.h" #include "simulation2/MessageTypes.h" #include "simulation2/components/ICmpFogging.h" #include "simulation2/components/ICmpMirage.h" #include "simulation2/components/ICmpOwnership.h" #include "simulation2/components/ICmpPosition.h" +#include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/components/ICmpTerritoryManager.h" #include "simulation2/components/ICmpVisibility.h" #include "simulation2/components/ICmpVision.h" #include "simulation2/components/ICmpWaterManager.h" #include "simulation2/helpers/Render.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "lib/timer.h" #include "ps/CLogger.h" #include "ps/Profile.h" #include "renderer/Scene.h" #define LOS_TILES_RATIO 8 #define DEBUG_RANGE_MANAGER_BOUNDS 0 /** * Representation of a range query. */ struct Query { bool enabled; bool parabolic; CEntityHandle source; // TODO: this could crash if an entity is destroyed while a Query is still referencing it entity_pos_t minRange; entity_pos_t maxRange; entity_pos_t elevationBonus; u32 ownersMask; i32 interface; std::vector lastMatch; u8 flagsMask; }; /** * Convert an owner ID (-1 = unowned, 0 = gaia, 1..30 = players) * into a 32-bit mask for quick set-membership tests. */ static inline u32 CalcOwnerMask(player_id_t owner) { if (owner >= -1 && owner < 31) return 1 << (1+owner); else return 0; // owner was invalid } /** * Returns LOS mask for given player. */ static inline u32 CalcPlayerLosMask(player_id_t player) { if (player > 0 && player <= 16) return ICmpRangeManager::LOS_MASK << (2*(player-1)); return 0; } /** * Returns shared LOS mask for given list of players. */ static u32 CalcSharedLosMask(std::vector players) { u32 playerMask = 0; for (size_t i = 0; i < players.size(); i++) playerMask |= CalcPlayerLosMask(players[i]); return playerMask; } /** * Returns shared 1-bit mask for given list of players. */ static u32 CalcSharedDirtyVisibilityMask(std::vector players) { u16 playerMask = 0; for (size_t i = 0; i < players.size(); i++) { if (players[i] > 0 && players[i] <= 16) playerMask |= (0x1 << (players[i] - 1)); } return playerMask; } /** * Computes the 2-bit visibility for one player, given the total 32-bit visibilities */ static inline u8 GetPlayerVisibility(u32 visibilities, player_id_t player) { if (player > 0 && player <= 16) return (visibilities >> (2 *(player-1))) & 0x3; return 0; } /** * Test whether the visibility is dirty for a given LoS tile and a given player */ static inline bool IsVisibilityDirty(u16 dirty, player_id_t player) { if (player > 0 && player <= 16) return (dirty >> (player - 1)) & 0x1; return false; } /** * Checks whether v is in a parabolic range of (0,0,0) * The highest point of the paraboloid is (0,range/2,0) * and the circle of distance 'range' around (0,0,0) on height y=0 is part of the paraboloid * * Avoids sqrting and overflowing. */ static bool InParabolicRange(CFixedVector3D v, fixed range) { i32 x = v.X.GetInternalValue(); // abs(x) <= 2^31 i32 z = v.Z.GetInternalValue(); u64 xx = (u64)FIXED_MUL_I64_I32_I32(x, x); // xx <= 2^62 u64 zz = (u64)FIXED_MUL_I64_I32_I32(z, z); i64 d2 = (xx + zz) >> 1; // d2 <= 2^62 (no overflow) i32 y = v.Y.GetInternalValue(); i32 c = range.GetInternalValue(); i32 c_2 = c >> 1; i64 c2 = FIXED_MUL_I64_I32_I32(c_2 - y, c); if (d2 <= c2) return true; return false; } struct EntityParabolicRangeOutline { entity_id_t source; CFixedVector3D position; entity_pos_t range; std::vector outline; }; static std::map ParabolicRangesOutlines; /** * Representation of an entity, with the data needed for queries. */ struct EntityData { EntityData() : visibilities(0), size(0), retainInFog(0), owner(-1), inWorld(0), flags(1), scriptedVisibility(0) { } entity_pos_t x, z; entity_pos_t visionRange; u32 visibilities; // 2-bit visibility, per player u32 size; u8 retainInFog; // boolean i8 owner; u8 inWorld; // boolean u8 flags; // See GetEntityFlagMask u8 scriptedVisibility; // boolean, see ComputeLosVisibility }; cassert(sizeof(EntityData) == 28); /** * Serialization helper template for Query */ struct SerializeQuery { template void Common(S& serialize, const char* UNUSED(name), Query& value) { serialize.Bool("enabled", value.enabled); serialize.Bool("parabolic",value.parabolic); serialize.NumberFixed_Unbounded("min range", value.minRange); serialize.NumberFixed_Unbounded("max range", value.maxRange); serialize.NumberFixed_Unbounded("elevation bonus", value.elevationBonus); serialize.NumberU32_Unbounded("owners mask", value.ownersMask); serialize.NumberI32_Unbounded("interface", value.interface); SerializeVector()(serialize, "last match", value.lastMatch); serialize.NumberU8_Unbounded("flagsMask", value.flagsMask); } void operator()(ISerializer& serialize, const char* name, Query& value, const CSimContext& UNUSED(context)) { Common(serialize, name, value); uint32_t id = value.source.GetId(); serialize.NumberU32_Unbounded("source", id); } void operator()(IDeserializer& deserialize, const char* name, Query& value, const CSimContext& context) { Common(deserialize, name, value); uint32_t id; deserialize.NumberU32_Unbounded("source", id); value.source = context.GetComponentManager().LookupEntityHandle(id, true); // the referenced entity might not have been deserialized yet, // so tell LookupEntityHandle to allocate the handle if necessary } }; /** * 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.NumberU32_Unbounded("visibilities", value.visibilities); serialize.NumberU32_Unbounded("size", value.size); serialize.NumberU8("retain in fog", value.retainInFog, 0, 1); serialize.NumberI8_Unbounded("owner", value.owner); serialize.NumberU8("in world", value.inWorld, 0, 1); serialize.NumberU8_Unbounded("flags", value.flags); } }; /** * 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 EntityMap& 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 EntityMap& 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.SubscribeGloballyToMessageType(MT_VisionRangeChanged); 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; EntityMap m_EntityData; FastSpatialSubdivision m_Subdivision; // spatial index of m_EntityData // LOS state: static const player_id_t MAX_LOS_PLAYER_ID = 16; std::vector m_LosRevealAll; bool m_LosCircular; i32 m_TerrainVerticesPerSide; // Cache for visibility tracking (not serialized) i32 m_LosTilesPerSide; bool m_GlobalVisibilityUpdate; std::vector m_GlobalPlayerVisibilityUpdate; std::vector m_DirtyVisibility; std::vector > m_LosTiles; // List of entities that must be updated, regardless of the status of their tile std::vector m_ModifiedEntities; // Counts of units seeing vertex, per vertex, per player (starting with player 0). // Use u16 to avoid overflows when we have very large (but not infeasibly large) numbers // of units in a very small area. // (Note we use vertexes, not tiles, to better match the renderer.) // Lazily constructed when it's needed, to save memory in smaller games. std::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; // Special static visibility data for the "reveal whole map" mode // (TODO: this is usually a waste of memory) std::vector m_LosStateRevealed; // Shared LOS masks, one per player. std::vector m_SharedLosMasks; // Shared dirty visibility masks, one per player. std::vector m_SharedDirtyVisibilityMasks; // Cache explored vertices per player (not serialized) u32 m_TotalInworldVertices; std::vector m_ExploredVertices; 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(1024), entity_pos_t::FromInt(1024)); // 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.resize(MAX_LOS_PLAYER_ID+2,false); m_LosRevealAll[0] = true; m_SharedLosMasks.resize(MAX_LOS_PLAYER_ID+2,0); m_SharedDirtyVisibilityMasks.resize(MAX_LOS_PLAYER_ID + 2, 0); m_LosCircular = false; m_TerrainVerticesPerSide = 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, GetSimContext()); SerializeEntityMap()(serialize, "entity data", m_EntityData); SerializeVector()(serialize, "los reveal all", m_LosRevealAll); serialize.Bool("los circular", m_LosCircular); serialize.NumberI32_Unbounded("terrain verts per side", m_TerrainVerticesPerSide); SerializeVector()(serialize, "modified entities", m_ModifiedEntities); // We don't serialize m_Subdivision, m_LosPlayerCounts or m_LosTiles // 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); SerializeVector()(serialize, "shared los masks", m_SharedLosMasks); SerializeVector()(serialize, "shared dirty visibility masks", m_SharedDirtyVisibilityMasks); } 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(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) 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) entdata.visionRange = cmpVision->GetRange(); CmpPtr cmpVisibility(GetSimContext(), ent); if (cmpVisibility) entdata.retainInFog = (cmpVisibility->GetRetainInFog() ? 1 : 0); // Store the size CmpPtr cmpObstruction(GetSimContext(), ent); if (cmpObstruction) entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity(); // Remember this entity m_EntityData.insert(ent, entdata); break; } case MT_PositionChanged: { const CMessagePositionChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; EntityMap::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, it->second.size); LosMove(it->second.owner, it->second.visionRange, from, to); i32 oldLosTile = PosToLosTilesHelper(it->second.x, it->second.z); i32 newLosTile = PosToLosTilesHelper(msgData.x, msgData.z); if (oldLosTile != newLosTile) { RemoveFromTile(oldLosTile, ent); AddToTile(newLosTile, ent); } } else { CFixedVector2D to(msgData.x, msgData.z); m_Subdivision.Add(ent, to, it->second.size); LosAdd(it->second.owner, it->second.visionRange, to); AddToTile(PosToLosTilesHelper(msgData.x, msgData.z), ent); } 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, it->second.size); LosRemove(it->second.owner, it->second.visionRange, from); RemoveFromTile(PosToLosTilesHelper(it->second.x, it->second.z), ent); } it->second.inWorld = 0; it->second.x = entity_pos_t::Zero(); it->second.z = entity_pos_t::Zero(); } RequestVisibilityUpdate(ent); break; } case MT_OwnershipChanged: { const CMessageOwnershipChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; EntityMap::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); } ENSURE(-128 <= msgData.to && msgData.to <= 127); it->second.owner = (i8)msgData.to; break; } case MT_Destroy: { const CMessageDestroy& msgData = static_cast (msg); entity_id_t ent = msgData.entity; EntityMap::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), it->second.size); RemoveFromTile(PosToLosTilesHelper(it->second.x, it->second.z), ent); } // This will be called after Ownership's OnDestroy, so ownership will be set // to -1 already and we don't have to do a LosRemove here ENSURE(it->second.owner == -1); m_EntityData.erase(it); break; } case MT_VisionRangeChanged: { const CMessageVisionRangeChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) break; CmpPtr cmpVision(GetSimContext(), ent); if (!cmpVision) break; entity_pos_t oldRange = it->second.visionRange; entity_pos_t newRange = msgData.newRange; // If the range changed and the entity's in-world, we need to manually adjust it // but if it's not in-world, we only need to set the new vision range CFixedVector2D pos(it->second.x, it->second.z); if (it->second.inWorld) LosRemove(it->second.owner, oldRange, pos); it->second.visionRange = newRange; if (it->second.inWorld) LosAdd(it->second.owner, newRange, pos); break; } case MT_Update: { m_DebugOverlayDirty = true; ExecuteActiveQueries(); UpdateVisibilityData(); 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 = (i32)vertices; ResetDerivedData(false); } virtual void Verify() { // Ignore if map not initialised yet if (m_WorldX1.IsZero()) return; // Check that calling ResetDerivedData (i.e. recomputing all the state from scratch) // does not affect the incrementally-computed state std::vector > oldPlayerCounts = m_LosPlayerCounts; std::vector oldStateRevealed = m_LosStateRevealed; FastSpatialSubdivision oldSubdivision = m_Subdivision; std::vector > oldLosTiles = m_LosTiles; ResetDerivedData(true); if (oldPlayerCounts != m_LosPlayerCounts) { for (size_t i = 0; i < oldPlayerCounts.size(); ++i) { debug_printf("%d: ", (int)i); for (size_t j = 0; j < oldPlayerCounts[i].size(); ++j) debug_printf("%d ", oldPlayerCounts[i][j]); debug_printf("\n"); } for (size_t i = 0; i < m_LosPlayerCounts.size(); ++i) { debug_printf("%d: ", (int)i); for (size_t j = 0; j < m_LosPlayerCounts[i].size(); ++j) debug_printf("%d ", m_LosPlayerCounts[i][j]); debug_printf("\n"); } debug_warn(L"inconsistent player counts"); } if (oldStateRevealed != m_LosStateRevealed) debug_warn(L"inconsistent revealed"); if (oldSubdivision != m_Subdivision) debug_warn(L"inconsistent subdivs"); if (oldLosTiles != m_LosTiles) debug_warn(L"inconsistent los tiles"); } FastSpatialSubdivision* GetSubdivision() { return &m_Subdivision; } // Reinitialise subdivisions and LOS data, based on entity data 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_LosTilesPerSide = (m_TerrainVerticesPerSide - 1)/LOS_TILES_RATIO; m_LosPlayerCounts.clear(); m_LosPlayerCounts.resize(MAX_LOS_PLAYER_ID+1); m_ExploredVertices.clear(); m_ExploredVertices.resize(MAX_LOS_PLAYER_ID+1, 0); if (skipLosState) { // recalc current exploration stats. for (i32 j = 0; j < m_TerrainVerticesPerSide; j++) { for (i32 i = 0; i < m_TerrainVerticesPerSide; i++) { if (!LosIsOffWorld(i, j)) { for (u8 k = 1; k < MAX_LOS_PLAYER_ID+1; ++k) m_ExploredVertices.at(k) += ((m_LosState[j*m_TerrainVerticesPerSide + i] & (LOS_EXPLORED << (2*(k-1)))) > 0); } } } } else { m_LosState.clear(); m_LosState.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); } m_LosStateRevealed.clear(); m_LosStateRevealed.resize(m_TerrainVerticesPerSide*m_TerrainVerticesPerSide); m_DirtyVisibility.clear(); m_DirtyVisibility.resize(m_LosTilesPerSide*m_LosTilesPerSide); m_LosTiles.clear(); m_LosTiles.resize(m_LosTilesPerSide*m_LosTilesPerSide); m_GlobalVisibilityUpdate = true; m_GlobalPlayerVisibilityUpdate.clear(); m_GlobalPlayerVisibilityUpdate.resize(MAX_LOS_PLAYER_ID); for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { if (it->second.inWorld) { LosAdd(it->second.owner, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); AddToTile(PosToLosTilesHelper(it->second.x, it->second.z), it->first); } } m_TotalInworldVertices = 0; for (ssize_t j = 0; j < m_TerrainVerticesPerSide; ++j) for (ssize_t i = 0; i < m_TerrainVerticesPerSide; ++i) { if (LosIsOffWorld(i,j)) m_LosStateRevealed[i + j*m_TerrainVerticesPerSide] = 0; else { m_LosStateRevealed[i + j*m_TerrainVerticesPerSide] = 0xFFFFFFFFu; m_TotalInworldVertices++; } } } void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1) { m_Subdivision.Reset(x1, z1); for (EntityMap::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), it->second.size); } } virtual tag_t CreateActiveQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, std::vector owners, int requiredInterface, u8 flags) { tag_t id = m_QueryNext++; m_Queries[id] = ConstructQuery(source, minRange, maxRange, owners, requiredInterface, flags); return id; } virtual tag_t CreateActiveParabolicQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t elevationBonus, std::vector owners, int requiredInterface, u8 flags) { tag_t id = m_QueryNext++; m_Queries[id] = ConstructParabolicQuery(source, minRange, maxRange, elevationBonus, owners, requiredInterface, flags); return id; } virtual void DestroyActiveQuery(tag_t tag) { if (m_Queries.find(tag) == m_Queries.end()) { LOGERROR("CCmpRangeManager: DestroyActiveQuery called with invalid tag %u", 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("CCmpRangeManager: EnableActiveQuery called with invalid tag %u", 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("CCmpRangeManager: DisableActiveQuery called with invalid tag %u", tag); return; } Query& q = it->second; q.enabled = false; } virtual std::vector ExecuteQueryAroundPos(CFixedVector2D pos, entity_pos_t minRange, entity_pos_t maxRange, std::vector owners, int requiredInterface) { Query q = ConstructQuery(INVALID_ENTITY, minRange, maxRange, owners, requiredInterface, GetEntityFlagMask("normal")); std::vector r; PerformQuery(q, r, pos); // Return the list sorted by distance from the entity std::stable_sort(r.begin(), r.end(), EntityDistanceOrdering(m_EntityData, pos)); return r; } 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, GetEntityFlagMask("normal")); std::vector r; CmpPtr cmpSourcePosition(q.source); if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld()) { // If the source doesn't have a position, then the result is just the empty list return r; } CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); PerformQuery(q, r, pos); // Return the list sorted by distance from the entity 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("CCmpRangeManager: ResetActiveQuery called with invalid tag %u", tag); return r; } Query& q = it->second; q.enabled = true; CmpPtr cmpSourcePosition(q.source); if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld()) { // If the source doesn't have a position, then the result is just the empty list q.lastMatch = r; return r; } CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); PerformQuery(q, r, pos); q.lastMatch = r; // Return the list sorted by distance from the entity 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 (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { // Check owner and add to list if it matches if (CalcOwnerMask(it->second.owner) & ownerMask) 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() { PROFILE3("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; std::vector results; std::vector added; std::vector removed; for (std::map::iterator it = m_Queries.begin(); it != m_Queries.end(); ++it) { Query& query = it->second; if (!query.enabled) continue; CmpPtr cmpSourcePosition(query.source); if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld()) continue; results.clear(); results.reserve(query.lastMatch.size()); CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); PerformQuery(query, results, pos); // Compute the changes vs the last match added.clear(); removed.clear(); // 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) std::set_difference(results.begin(), results.end(), query.lastMatch.begin(), query.lastMatch.end(), std::back_inserter(added)); std::set_difference(query.lastMatch.begin(), query.lastMatch.end(), results.begin(), results.end(), std::back_inserter(removed)); if (added.empty() && removed.empty()) continue; std::stable_sort(added.begin(), added.end(), EntityDistanceOrdering(m_EntityData, cmpSourcePosition->GetPosition2D())); messages.resize(messages.size() + 1); std::pair& back = messages.back(); back.first = query.source.GetId(); back.second.tag = it->first; back.second.added.swap(added); back.second.removed.swap(removed); it->second.lastMatch.swap(results); } CComponentManager& cmpMgr = GetSimContext().GetComponentManager(); for (size_t i = 0; i < messages.size(); ++i) cmpMgr.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 entities that don't match the current flags if (!(entity.flags & q.flagsMask)) return false; // Ignore self if (id == q.source.GetId()) 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, CFixedVector2D pos) { // Special case: range -1.0 means check all entities ignoring distance if (q.maxRange == entity_pos_t::FromInt(-1)) { for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { if (!TestEntityQuery(q, it->first, it->second)) continue; r.push_back(it->first); } } // Not the entire world, so check a parabolic range, or a regular range else if (q.parabolic) { // elevationBonus is part of the 3D position, as the source is really that much heigher CmpPtr cmpSourcePosition(q.source); CFixedVector3D pos3d = cmpSourcePosition->GetPosition()+ CFixedVector3D(entity_pos_t::Zero(), q.elevationBonus, entity_pos_t::Zero()) ; // Get a quick list of entities that are potentially in range, with a cutoff of 2*maxRange std::vector ents; m_Subdivision.GetNear(ents, pos, q.maxRange*2); for (size_t i = 0; i < ents.size(); ++i) { EntityMap::const_iterator it = m_EntityData.find(ents[i]); ENSURE(it != m_EntityData.end()); if (!TestEntityQuery(q, it->first, it->second)) continue; CmpPtr cmpSecondPosition(GetSimContext(), ents[i]); if (!cmpSecondPosition || !cmpSecondPosition->IsInWorld()) continue; CFixedVector3D secondPosition = cmpSecondPosition->GetPosition(); // Restrict based on precise distance if (!InParabolicRange( CFixedVector3D(it->second.x, secondPosition.Y, it->second.z) - pos3d, q.maxRange)) 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); } } // check a regular range (i.e. not the entire world, and not parabolic) else { // Get a quick list of entities that are potentially in range std::vector ents; m_Subdivision.GetNear(ents, pos, q.maxRange); for (size_t i = 0; i < ents.size(); ++i) { EntityMap::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); } } } virtual entity_pos_t GetElevationAdaptedRange(CFixedVector3D pos, CFixedVector3D rot, entity_pos_t range, entity_pos_t elevationBonus, entity_pos_t angle) { entity_pos_t r = entity_pos_t::Zero() ; pos.Y += elevationBonus; entity_pos_t orientation = rot.Y; entity_pos_t maxAngle = orientation + angle/2; entity_pos_t minAngle = orientation - angle/2; int numberOfSteps = 16; if (angle == entity_pos_t::Zero()) numberOfSteps = 1; std::vector coords = getParabolicRangeForm(pos, range, range*2, minAngle, maxAngle, numberOfSteps); entity_pos_t part = entity_pos_t::FromInt(numberOfSteps); for (int i = 0; i < numberOfSteps; i++) { r = r + CFixedVector2D(coords[2*i],coords[2*i+1]).Length() / part; } return r; } virtual std::vector getParabolicRangeForm(CFixedVector3D pos, entity_pos_t maxRange, entity_pos_t cutoff, entity_pos_t minAngle, entity_pos_t maxAngle, int numberOfSteps) { // angle = 0 goes in the positive Z direction entity_pos_t precision = entity_pos_t::FromInt((int)TERRAIN_TILE_SIZE)/8; std::vector r; CmpPtr cmpTerrain(GetSystemEntity()); CmpPtr cmpWaterManager(GetSystemEntity()); entity_pos_t waterLevel = cmpWaterManager->GetWaterLevel(pos.X,pos.Z); entity_pos_t thisHeight = pos.Y > waterLevel ? pos.Y : waterLevel; if (cmpTerrain) { for (int i = 0; i < numberOfSteps; i++) { entity_pos_t angle = minAngle + (maxAngle - minAngle) / numberOfSteps * i; entity_pos_t sin; entity_pos_t cos; entity_pos_t minDistance = entity_pos_t::Zero(); entity_pos_t maxDistance = cutoff; sincos_approx(angle,sin,cos); CFixedVector2D minVector = CFixedVector2D(entity_pos_t::Zero(),entity_pos_t::Zero()); CFixedVector2D maxVector = CFixedVector2D(sin,cos).Multiply(cutoff); entity_pos_t targetHeight = cmpTerrain->GetGroundLevel(pos.X+maxVector.X,pos.Z+maxVector.Y); // use water level to display range on water targetHeight = targetHeight > waterLevel ? targetHeight : waterLevel; if (InParabolicRange(CFixedVector3D(maxVector.X,targetHeight-thisHeight,maxVector.Y),maxRange)) { r.push_back(maxVector.X); r.push_back(maxVector.Y); continue; } // Loop until vectors come close enough while ((maxVector - minVector).CompareLength(precision) > 0) { // difference still bigger than precision, bisect to get smaller difference entity_pos_t newDistance = (minDistance+maxDistance)/entity_pos_t::FromInt(2); CFixedVector2D newVector = CFixedVector2D(sin,cos).Multiply(newDistance); // get the height of the ground targetHeight = cmpTerrain->GetGroundLevel(pos.X+newVector.X,pos.Z+newVector.Y); targetHeight = targetHeight > waterLevel ? targetHeight : waterLevel; if (InParabolicRange(CFixedVector3D(newVector.X,targetHeight-thisHeight,newVector.Y),maxRange)) { // new vector is in parabolic range, so this is a new minVector minVector = newVector; minDistance = newDistance; } else { // new vector is out parabolic range, so this is a new maxVector maxVector = newVector; maxDistance = newDistance; } } r.push_back(maxVector.X); r.push_back(maxVector.Y); } r.push_back(r[0]); r.push_back(r[1]); } return r; } Query ConstructQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, const std::vector& owners, int requiredInterface, u8 flagsMask) { // Min range must be non-negative if (minRange < entity_pos_t::Zero()) LOGWARNING("CCmpRangeManager: Invalid min range %f in query for entity %u", 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("CCmpRangeManager: Invalid max range %f in query for entity %u", maxRange.ToDouble(), source); Query q; q.enabled = false; q.parabolic = false; q.source = GetSimContext().GetComponentManager().LookupEntityHandle(source); q.minRange = minRange; q.maxRange = maxRange; q.elevationBonus = entity_pos_t::Zero(); q.ownersMask = 0; for (size_t i = 0; i < owners.size(); ++i) q.ownersMask |= CalcOwnerMask(owners[i]); q.interface = requiredInterface; q.flagsMask = flagsMask; return q; } Query ConstructParabolicQuery(entity_id_t source, entity_pos_t minRange, entity_pos_t maxRange, entity_pos_t elevationBonus, const std::vector& owners, int requiredInterface, u8 flagsMask) { Query q = ConstructQuery(source,minRange,maxRange,owners,requiredInterface,flagsMask); q.parabolic = true; q.elevationBonus = elevationBonus; return q; } void RenderSubmit(SceneCollector& collector) { if (!m_DebugOverlayEnabled) return; static CColor disabledRingColor(1, 0, 0, 1); // red static CColor enabledRingColor(0, 1, 0, 1); // green static CColor subdivColor(0, 0, 1, 1); // blue static CColor rayColor(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(q.source); if (!cmpSourcePosition || !cmpSourcePosition->IsInWorld()) continue; CFixedVector2D pos = cmpSourcePosition->GetPosition2D(); // Draw the max range circle if (!q.parabolic) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = (q.enabled ? enabledRingColor : disabledRingColor); SimRender::ConstructCircleOnGround(GetSimContext(), pos.X.ToFloat(), pos.Y.ToFloat(), q.maxRange.ToFloat(), m_DebugOverlayLines.back(), true); } else { // elevation bonus is part of the 3D position. As if the unit is really that much higher CFixedVector3D pos = cmpSourcePosition->GetPosition(); pos.Y += q.elevationBonus; std::vector coords; // Get the outline from cache if possible if (ParabolicRangesOutlines.find(q.source.GetId()) != ParabolicRangesOutlines.end()) { EntityParabolicRangeOutline e = ParabolicRangesOutlines[q.source.GetId()]; if (e.position == pos && e.range == q.maxRange) { // outline is cached correctly, use it coords = e.outline; } else { // outline was cached, but important parameters changed // (position, elevation, range) // update it coords = getParabolicRangeForm(pos,q.maxRange,q.maxRange*2, entity_pos_t::Zero(), entity_pos_t::FromFloat(2.0f*3.14f),70); e.outline = coords; e.range = q.maxRange; e.position = pos; ParabolicRangesOutlines[q.source.GetId()] = e; } } else { // outline wasn't cached (first time you enable the range overlay // or you created a new entiy) // cache a new outline coords = getParabolicRangeForm(pos,q.maxRange,q.maxRange*2, entity_pos_t::Zero(), entity_pos_t::FromFloat(2.0f*3.14f),70); EntityParabolicRangeOutline e; e.source = q.source.GetId(); e.range = q.maxRange; e.position = pos; e.outline = coords; ParabolicRangesOutlines[q.source.GetId()] = e; } CColor thiscolor = q.enabled ? enabledRingColor : disabledRingColor; // draw the outline (piece by piece) for (size_t i = 3; i < coords.size(); i += 2) { std::vector c; c.push_back((coords[i-3]+pos.X).ToFloat()); c.push_back((coords[i-2]+pos.Z).ToFloat()); c.push_back((coords[i-1]+pos.X).ToFloat()); c.push_back((coords[i]+pos.Z).ToFloat()); m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = thiscolor; SimRender::ConstructLineOnGround(GetSimContext(), c, m_DebugOverlayLines.back(), true); } } // Draw the min range circle if (!q.minRange.IsZero()) { SimRender::ConstructCircleOnGround(GetSimContext(), pos.X.ToFloat(), pos.Y.ToFloat(), 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 || !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 = rayColor; SimRender::ConstructLineOnGround(GetSimContext(), coords, m_DebugOverlayLines.back(), true); } } // render subdivision grid float divSize = m_Subdivision.GetDivisionSize(); int size = m_Subdivision.GetWidth(); for (int x = 0; x < size; ++x) { for (int y = 0; y < size; ++y) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = subdivColor; float xpos = x*divSize + divSize/2; float zpos = y*divSize + divSize/2; SimRender::ConstructSquareOnGround(GetSimContext(), xpos, zpos, divSize, divSize, 0.0f, m_DebugOverlayLines.back(), false, 1.0f); } } m_DebugOverlayDirty = false; } for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i) collector.Submit(&m_DebugOverlayLines[i]); } virtual u8 GetEntityFlagMask(std::string identifier) { if (identifier == "normal") return 1; if (identifier == "injured") return 2; LOGWARNING("CCmpRangeManager: Invalid flag identifier %s", identifier.c_str()); return 0; } virtual void SetEntityFlag(entity_id_t ent, std::string identifier, bool value) { EntityMap::iterator it = m_EntityData.find(ent); // We don't have this entity if (it == m_EntityData.end()) return; u8 flag = GetEntityFlagMask(identifier); // We don't have a flag set if (flag == 0) { LOGWARNING("CCmpRangeManager: Invalid flag identifier %s for entity %u", identifier.c_str(), ent); return; } if (value) it->second.flags |= flag; else it->second.flags &= ~flag; } // **************************************************************** // LOS implementation: virtual CLosQuerier GetLosQuerier(player_id_t player) { if (GetLosRevealAll(player)) return CLosQuerier(0xFFFFFFFFu, m_LosStateRevealed, m_TerrainVerticesPerSide); else return CLosQuerier(GetSharedLosMask(player), m_LosState, m_TerrainVerticesPerSide); } virtual void ActivateScriptedVisibility(entity_id_t ent, bool status) { EntityMap::iterator it = m_EntityData.find(ent); if (it != m_EntityData.end()) it->second.scriptedVisibility = status ? 1 : 0; } ELosVisibility ComputeLosVisibility(CEntityHandle ent, player_id_t player) { // Entities not with positions in the world are never visible if (ent.GetId() == INVALID_ENTITY) return VIS_HIDDEN; CmpPtr cmpPosition(ent); if (!cmpPosition || !cmpPosition->IsInWorld()) return VIS_HIDDEN; // Mirage entities, whatever the situation, are visible for one specific player CmpPtr cmpMirage(ent); if (cmpMirage && cmpMirage->GetPlayer() != player) return VIS_HIDDEN; CFixedVector2D pos = cmpPosition->GetPosition2D(); int i = (pos.X / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNearest(); int j = (pos.Y / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNearest(); // Reveal flag makes all positioned entities visible and all mirages useless if (GetLosRevealAll(player)) { if (LosIsOffWorld(i, j) || cmpMirage) return VIS_HIDDEN; else return VIS_VISIBLE; } // Get visible regions CLosQuerier los(GetSharedLosMask(player), m_LosState, m_TerrainVerticesPerSide); CmpPtr cmpVisibility(ent); // Possibly ask the scripted Visibility component EntityMap::iterator it = m_EntityData.find(ent.GetId()); if (it != m_EntityData.end()) { if (it->second.scriptedVisibility == 1 && cmpVisibility) return cmpVisibility->GetVisibility(player, los.IsVisible(i, j), los.IsExplored(i, j)); } else { if (cmpVisibility && cmpVisibility->IsActivated()) return cmpVisibility->GetVisibility(player, los.IsVisible(i, j), los.IsExplored(i, j)); } // Else, default behavior if (los.IsVisible(i, j)) { if (cmpMirage) return VIS_HIDDEN; return VIS_VISIBLE; } if (!los.IsExplored(i, j)) return VIS_HIDDEN; // Invisible if the 'retain in fog' flag is not set, and in a non-visible explored region // Try using the 'retainInFog' flag in m_EntityData to save a script call if (it != m_EntityData.end()) { if (it->second.retainInFog != 1) return VIS_HIDDEN; } else { if (!(cmpVisibility && cmpVisibility->GetRetainInFog())) return VIS_HIDDEN; } if (cmpMirage) return VIS_FOGGED; CmpPtr cmpOwnership(ent); if (!cmpOwnership) return VIS_FOGGED; if (cmpOwnership->GetOwner() == player) { CmpPtr cmpFogging(ent); if (!(cmpFogging && cmpFogging->IsMiraged(player))) return VIS_FOGGED; return VIS_HIDDEN; } // Fogged entities are hidden in two cases: // - They were not scouted // - A mirage replaces them CmpPtr cmpFogging(ent); if (cmpFogging && cmpFogging->IsActivated() && (!cmpFogging->WasSeen(player) || cmpFogging->IsMiraged(player))) return VIS_HIDDEN; return VIS_FOGGED; } ELosVisibility ComputeLosVisibility(entity_id_t ent, player_id_t player) { CEntityHandle handle = GetSimContext().GetComponentManager().LookupEntityHandle(ent); return ComputeLosVisibility(handle, player); } virtual ELosVisibility GetLosVisibility(CEntityHandle ent, player_id_t player) { entity_id_t entId = ent.GetId(); // Entities not with positions in the world are never visible if (entId == INVALID_ENTITY) return VIS_HIDDEN; CmpPtr cmpPosition(ent); if (!cmpPosition || !cmpPosition->IsInWorld()) return VIS_HIDDEN; CFixedVector2D pos = cmpPosition->GetPosition2D(); i32 n = PosToLosTilesHelper(pos.X, pos.Y); // Gaia and observers do not have a visibility cache if (player <= 0) return ComputeLosVisibility(ent, player); if (IsVisibilityDirty(m_DirtyVisibility[n], player)) return ComputeLosVisibility(ent, player); if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), entId) != m_ModifiedEntities.end()) return ComputeLosVisibility(ent, player); EntityMap::iterator it = m_EntityData.find(entId); if (it == m_EntityData.end()) return ComputeLosVisibility(ent, player); return static_cast(GetPlayerVisibility(it->second.visibilities, player)); } virtual ELosVisibility GetLosVisibility(entity_id_t ent, player_id_t player) { CEntityHandle handle = GetSimContext().GetComponentManager().LookupEntityHandle(ent); return GetLosVisibility(handle, player); } i32 PosToLosTilesHelper(entity_pos_t x, entity_pos_t z) { i32 i = Clamp( (x/(entity_pos_t::FromInt(TERRAIN_TILE_SIZE * LOS_TILES_RATIO))).ToInt_RoundToZero(), 0, m_LosTilesPerSide - 1); i32 j = Clamp( (z/(entity_pos_t::FromInt(TERRAIN_TILE_SIZE * LOS_TILES_RATIO))).ToInt_RoundToZero(), 0, m_LosTilesPerSide - 1); return j*m_LosTilesPerSide + i; } void AddToTile(i32 tile, entity_id_t ent) { m_LosTiles[tile].insert(ent); } void RemoveFromTile(i32 tile, entity_id_t ent) { for (std::set::iterator tileIt = m_LosTiles[tile].begin(); tileIt != m_LosTiles[tile].end(); ++tileIt) { if (*tileIt == ent) { m_LosTiles[tile].erase(tileIt); return; } } } void UpdateVisibilityData() { PROFILE("UpdateVisibilityData"); for (i32 n = 0; n < m_LosTilesPerSide * m_LosTilesPerSide; ++n) { for (player_id_t player = 1; player < MAX_LOS_PLAYER_ID + 1; ++player) { if (IsVisibilityDirty(m_DirtyVisibility[n], player) || m_GlobalPlayerVisibilityUpdate[player-1] == 1 || m_GlobalVisibilityUpdate) { for (auto& ent : m_LosTiles[n]) UpdateVisibility(ent, player); } } m_DirtyVisibility[n] = 0; } std::fill(m_GlobalPlayerVisibilityUpdate.begin(), m_GlobalPlayerVisibilityUpdate.end(), 0); // Don't bother updating modified entities if the update was global if (!m_GlobalVisibilityUpdate) { for (auto& ent : m_ModifiedEntities) UpdateVisibility(ent); } m_ModifiedEntities.clear(); m_GlobalVisibilityUpdate = false; } virtual void RequestVisibilityUpdate(entity_id_t ent) { if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), ent) == m_ModifiedEntities.end()) m_ModifiedEntities.push_back(ent); } void UpdateVisibility(entity_id_t ent, player_id_t player) { EntityMap::iterator itEnts = m_EntityData.find(ent); if (itEnts == m_EntityData.end()) return; u8 oldVis = GetPlayerVisibility(itEnts->second.visibilities, player); u8 newVis = ComputeLosVisibility(itEnts->first, player); if (oldVis == newVis) return; itEnts->second.visibilities = (itEnts->second.visibilities & ~(0x3 << 2 * (player - 1))) | (newVis << 2 * (player - 1)); CMessageVisibilityChanged msg(player, ent, oldVis, newVis); GetSimContext().GetComponentManager().PostMessage(ent, msg); } void UpdateVisibility(entity_id_t ent) { for (player_id_t player = 1; player < MAX_LOS_PLAYER_ID + 1; ++player) UpdateVisibility(ent, player); } virtual void SetLosRevealAll(player_id_t player, bool enabled) { if (player == -1) m_LosRevealAll[MAX_LOS_PLAYER_ID+1] = enabled; else { ENSURE(player >= 0 && player <= MAX_LOS_PLAYER_ID); m_LosRevealAll[player] = enabled; } // On next update, update the visibility of every entity in the world m_GlobalVisibilityUpdate = true; } virtual bool GetLosRevealAll(player_id_t player) { // Special player value can force reveal-all for every player if (m_LosRevealAll[MAX_LOS_PLAYER_ID+1] || player == -1) return true; ENSURE(player >= 0 && player <= MAX_LOS_PLAYER_ID+1); // Otherwise check the player-specific flag if (m_LosRevealAll[player]) return true; return false; } virtual void SetLosCircular(bool enabled) { m_LosCircular = enabled; ResetDerivedData(false); } virtual bool GetLosCircular() { return m_LosCircular; } virtual void SetSharedLos(player_id_t player, std::vector players) { m_SharedLosMasks[player] = CalcSharedLosMask(players); u16 oldMask = m_SharedDirtyVisibilityMasks[player]; m_SharedDirtyVisibilityMasks[player] = CalcSharedDirtyVisibilityMask(players); if (oldMask != m_SharedDirtyVisibilityMasks[player] && (size_t)player <= m_GlobalPlayerVisibilityUpdate.size()) m_GlobalPlayerVisibilityUpdate[player-1] = 1; } virtual u32 GetSharedLosMask(player_id_t player) { return m_SharedLosMasks[player]; } void ExploreAllTiles(player_id_t p) { for (u16 j = 0; j < m_TerrainVerticesPerSide; ++j) { for (u16 i = 0; i < m_TerrainVerticesPerSide; ++i) { if (LosIsOffWorld(i,j)) continue; u32 &explored = m_ExploredVertices.at(p); explored += !(m_LosState[i + j*m_TerrainVerticesPerSide] & (LOS_EXPLORED << (2*(p-1)))); m_LosState[i + j*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); } } SeeExploredEntities(p); } virtual void ExploreTerritories() { - CmpPtr cmpTerritoryManager(GetSystemEntity()); + PROFILE3("ExploreTerritories"); + CmpPtr cmpTerritoryManager(GetSystemEntity()); 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 + // Territory data is stored per territory-tile (typically a multiple of terrain-tiles). + // LOS data is stored per terrain-tile vertex. + + // For each territory-tile, if it is owned by a valid player then update the LOS + // for every vertex inside/around that tile, to mark them as explored. + + // Currently this code doesn't support territory-tiles smaller than terrain-tiles + // (it will get scale==0 and break), or a non-integer multiple, so check that first + cassert(ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE >= Pathfinding::NAVCELLS_PER_TILE); + cassert(ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE % Pathfinding::NAVCELLS_PER_TILE == 0); + + int scale = ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE / Pathfinding::NAVCELLS_PER_TILE; + + ENSURE(grid.m_W*scale == m_TerrainVerticesPerSide-1 && grid.m_H*scale == m_TerrainVerticesPerSide-1); for (u16 j = 0; j < grid.m_H; ++j) { for (u16 i = 0; i < grid.m_W; ++i) { u8 p = grid.get(i, j) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK; if (p > 0 && p <= MAX_LOS_PLAYER_ID) { - u32 &explored = m_ExploredVertices.at(p); - explored += !(m_LosState[i + j*m_TerrainVerticesPerSide] & (LOS_EXPLORED << (2*(p-1)))); - m_LosState[i + j*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); - explored += !(m_LosState[i+1 + j*m_TerrainVerticesPerSide] & (LOS_EXPLORED << (2*(p-1)))); - m_LosState[i+1 + j*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); - explored += !(m_LosState[i + (j+1)*m_TerrainVerticesPerSide] & (LOS_EXPLORED << (2*(p-1)))); - m_LosState[i + (j+1)*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); - explored += !(m_LosState[i+1 + (j+1)*m_TerrainVerticesPerSide] & (LOS_EXPLORED << (2*(p-1)))); - m_LosState[i+1 + (j+1)*m_TerrainVerticesPerSide] |= (LOS_EXPLORED << (2*(p-1))); + u32& explored = m_ExploredVertices.at(p); + for (int dj = 0; dj <= scale; ++dj) + { + for (int di = 0; di <= scale; ++di) + { + u32& losState = m_LosState[(i*scale+di) + (j*scale+dj)*m_TerrainVerticesPerSide]; + if (!(losState & (LOS_EXPLORED << (2*(p-1))))) + { + explored++; + losState |= (LOS_EXPLORED << (2*(p-1))); + } + } + } } } } for (player_id_t p = 1; p < MAX_LOS_PLAYER_ID+1; ++p) SeeExploredEntities(p); } /** * Force any entity in explored territory to appear for player p. * This is useful for miraging entities inside the territory borders at the beginning of a game, * or if the "Explore Map" option has been set. */ void SeeExploredEntities(player_id_t p) { // Warning: Code related to fogging (like ForceMiraging) shouldn't be // invoked while iterating through m_EntityData. // Otherwise, by deleting mirage entities and so on, that code will // change the indexes in the map, leading to segfaults. // So we just remember what entities to mirage and do that later. std::vector miragableEntities; for (EntityMap::iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { CmpPtr cmpPosition(GetSimContext(), it->first); if (!cmpPosition || !cmpPosition->IsInWorld()) continue; CFixedVector2D pos = cmpPosition->GetPosition2D(); int i = (pos.X / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNearest(); int j = (pos.Y / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNearest(); CLosQuerier los(GetSharedLosMask(p), m_LosState, m_TerrainVerticesPerSide); if (!los.IsExplored(i,j) || los.IsVisible(i,j)) continue; CmpPtr cmpFogging(GetSimContext(), it->first); if (cmpFogging) miragableEntities.push_back(it->first); } for (std::vector::iterator it = miragableEntities.begin(); it != miragableEntities.end(); ++it) { CmpPtr cmpFogging(GetSimContext(), *it); ENSURE(cmpFogging && "Impossible to retrieve Fogging component, previously achieved"); cmpFogging->ForceMiraging(p); } } virtual void RevealShore(player_id_t p, bool enable) { if (p <= 0 || p > MAX_LOS_PLAYER_ID) return; // Maximum distance to the shore const u16 maxdist = 10; CmpPtr cmpPathfinder(GetSystemEntity()); const Grid& shoreGrid = cmpPathfinder->ComputeShoreGrid(true); ENSURE(shoreGrid.m_W == m_TerrainVerticesPerSide-1 && shoreGrid.m_H == m_TerrainVerticesPerSide-1); std::vector& counts = m_LosPlayerCounts.at(p); ENSURE(!counts.empty()); u16* countsData = &counts[0]; for (u16 j = 0; j < shoreGrid.m_H; ++j) { for (u16 i = 0; i < shoreGrid.m_W; ++i) { u16 shoredist = shoreGrid.get(i, j); if (shoredist > maxdist) continue; // Maybe we could be more clever and don't add dummy strips of one tile if (enable) LosAddStripHelper(p, i, i, j, countsData); else LosRemoveStripHelper(p, i, i, j, countsData); } } } /** * 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 + // WARNING: CCmpPathfinder::UpdateGrid 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; u32 &explored = m_ExploredVertices.at(owner); 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)) { explored += !(m_LosState[idx] & (LOS_EXPLORED << (2*(owner-1)))); m_LosState[idx] |= ((LOS_VISIBLE | LOS_EXPLORED) << (2*(owner-1))); } MarkVisibilityDirtyAroundTile(owner, i, j); } ASSERT(counts[idx] < 65535); counts[idx] = (u16)(counts[idx] + 1); // ignore overflow; the player should never have 64K units } } /** * 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) { ASSERT(counts[idx] > 0); counts[idx] = (u16)(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))); i32 i = i0 + idx - idx0; MarkVisibilityDirtyAroundTile(owner, i, j); } } } inline void MarkVisibilityDirtyAroundTile(u8 owner, i32 i, i32 j) { // Mark the LoS tiles around the updated vertex // 1: left-up, 2: right-up, 3: left-down, 4: right-down int n1 = ((j-1)/LOS_TILES_RATIO)*m_LosTilesPerSide + (i-1)/LOS_TILES_RATIO; int n2 = ((j-1)/LOS_TILES_RATIO)*m_LosTilesPerSide + i/LOS_TILES_RATIO; int n3 = (j/LOS_TILES_RATIO)*m_LosTilesPerSide + (i-1)/LOS_TILES_RATIO; int n4 = (j/LOS_TILES_RATIO)*m_LosTilesPerSide + i/LOS_TILES_RATIO; u16 sharedDirtyVisibilityMask = m_SharedDirtyVisibilityMasks[owner]; if (j > 0 && i > 0) m_DirtyVisibility[n1] |= sharedDirtyVisibilityMask; if (n2 != n1 && j > 0 && i < m_TerrainVerticesPerSide) m_DirtyVisibility[n2] |= sharedDirtyVisibilityMask; if (n3 != n1 && j < m_TerrainVerticesPerSide && i > 0) m_DirtyVisibility[n3] |= sharedDirtyVisibilityMask; if (n4 != n1 && j < m_TerrainVerticesPerSide && i < m_TerrainVerticesPerSide) m_DirtyVisibility[n4] |= sharedDirtyVisibilityMask; } /** * 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)TERRAIN_TILE_SIZE).ToInt_RoundToInfinity(); i32 j1 = ((pos.Y + visionRange)/(int)TERRAIN_TILE_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)TERRAIN_TILE_SIZE; entity_pos_t y = pos.Y / (int)TERRAIN_TILE_SIZE; entity_pos_t r = visionRange / (int)TERRAIN_TILE_SIZE; entity_pos_t r2 = r.Square(); // Compute the integers on either side of x i32 xfloor = (x - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); i32 xceil = (x + entity_pos_t::Epsilon()).ToInt_RoundToInfinity(); // Initialise the strip (i0, i1) to a rough guess i32 i0 = xfloor; i32 i1 = xceil; for (i32 j = j0clamp; j <= j1clamp; ++j) { // Adjust i0 and i1 to be the outermost values that don't exceed // the circle's radius (i.e. require dy^2 + dx^2 <= r^2). // When moving the points inwards, clamp them to xceil+1 or xfloor-1 // so they don't accidentally shoot off in the wrong direction forever. entity_pos_t dy = entity_pos_t::FromInt(j) - y; entity_pos_t dy2 = dy.Square(); while (dy2 + (entity_pos_t::FromInt(i0-1) - x).Square() <= r2) --i0; while (i0 < xceil && dy2 + (entity_pos_t::FromInt(i0) - x).Square() > r2) ++i0; while (dy2 + (entity_pos_t::FromInt(i1+1) - x).Square() <= r2) ++i1; while (i1 > xfloor && dy2 + (entity_pos_t::FromInt(i1) - x).Square() > r2) --i1; #if DEBUG_RANGE_MANAGER_BOUNDS if (i0 <= i1) { ENSURE(dy2 + (entity_pos_t::FromInt(i0) - x).Square() <= r2); ENSURE(dy2 + (entity_pos_t::FromInt(i1) - x).Square() <= r2); } ENSURE(dy2 + (entity_pos_t::FromInt(i0 - 1) - x).Square() > r2); ENSURE(dy2 + (entity_pos_t::FromInt(i1 + 1) - x).Square() > r2); #endif // Clamp the strip to exclude the 1-tile border, // then add or remove the strip as requested i32 i0clamp = std::max(i0, 1); i32 i1clamp = std::min(i1, m_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)TERRAIN_TILE_SIZE).ToInt_RoundToInfinity(); i32 j1_from = ((from.Y + visionRange)/(int)TERRAIN_TILE_SIZE).ToInt_RoundToNegInfinity(); i32 j0_to = ((to.Y - visionRange)/(int)TERRAIN_TILE_SIZE).ToInt_RoundToInfinity(); i32 j1_to = ((to.Y + visionRange)/(int)TERRAIN_TILE_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)TERRAIN_TILE_SIZE; entity_pos_t y_from = from.Y / (int)TERRAIN_TILE_SIZE; entity_pos_t x_to = to.X / (int)TERRAIN_TILE_SIZE; entity_pos_t y_to = to.Y / (int)TERRAIN_TILE_SIZE; entity_pos_t r = visionRange / (int)TERRAIN_TILE_SIZE; entity_pos_t r2 = r.Square(); i32 xfloor_from = (x_from - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); i32 xceil_from = (x_from + entity_pos_t::Epsilon()).ToInt_RoundToInfinity(); i32 xfloor_to = (x_to - entity_pos_t::Epsilon()).ToInt_RoundToNegInfinity(); i32 xceil_to = (x_to + entity_pos_t::Epsilon()).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; #if DEBUG_RANGE_MANAGER_BOUNDS if (i0_from <= i1_from) { ENSURE(dy2_from + (entity_pos_t::FromInt(i0_from) - x_from).Square() <= r2); ENSURE(dy2_from + (entity_pos_t::FromInt(i1_from) - x_from).Square() <= r2); } ENSURE(dy2_from + (entity_pos_t::FromInt(i0_from - 1) - x_from).Square() > r2); ENSURE(dy2_from + (entity_pos_t::FromInt(i1_from + 1) - x_from).Square() > r2); if (i0_to <= i1_to) { ENSURE(dy2_to + (entity_pos_t::FromInt(i0_to) - x_to).Square() <= r2); ENSURE(dy2_to + (entity_pos_t::FromInt(i1_to) - x_to).Square() <= r2); } ENSURE(dy2_to + (entity_pos_t::FromInt(i0_to - 1) - x_to).Square() > r2); ENSURE(dy2_to + (entity_pos_t::FromInt(i1_to + 1) - x_to).Square() > r2); #endif // 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.) // (If the strips don't actually overlap (which is very rare with normal unit // movement speeds), the region between them will be both added and removed, // so we have to do the add first to avoid overflowing to -1 and triggering // assertion failures.) LosAddStripHelper(owner, i0clamp_to, i0clamp_from-1, j, countsData); LosAddStripHelper(owner, i1clamp_from+1, i1clamp_to, j, countsData); LosRemoveStripHelper(owner, i0clamp_from, i0clamp_to-1, j, countsData); LosRemoveStripHelper(owner, i1clamp_to+1, i1clamp_from, j, countsData); } } } } void LosAdd(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; LosUpdateHelper((u8)owner, visionRange, pos); } void LosRemove(player_id_t owner, entity_pos_t visionRange, CFixedVector2D pos) { if (visionRange.IsZero() || owner <= 0 || owner > MAX_LOS_PLAYER_ID) return; LosUpdateHelper((u8)owner, visionRange, pos); } void LosMove(player_id_t 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((u8)owner, visionRange, from); LosUpdateHelper((u8)owner, visionRange, to); } else { // Otherwise use the version optimised for mostly-overlapping circles LosUpdateHelperIncremental((u8)owner, visionRange, from, to); } } virtual u8 GetPercentMapExplored(player_id_t player) { return m_ExploredVertices.at((u8)player) * 100 / m_TotalInworldVertices; } virtual u8 GetUnionPercentMapExplored(std::vector players) { u32 exploredVertices = 0; std::vector::iterator playerIt; for (i32 j = 0; j < m_TerrainVerticesPerSide; j++) { for (i32 i = 0; i < m_TerrainVerticesPerSide; i++) { if (LosIsOffWorld(i, j)) continue; for (playerIt = players.begin(); playerIt != players.end(); ++playerIt) { if (m_LosState[j*m_TerrainVerticesPerSide + i] & (LOS_EXPLORED << (2*((*playerIt)-1)))) { exploredVertices += 1; break; } } } } return exploredVertices * 100 / m_TotalInworldVertices; } }; REGISTER_COMPONENT_TYPE(RangeManager) Index: ps/trunk/binaries/data/mods/public/gui/session/session.xml =================================================================== --- ps/trunk/binaries/data/mods/public/gui/session/session.xml (revision 16750) +++ ps/trunk/binaries/data/mods/public/gui/session/session.xml (revision 16751) @@ -1,348 +1,355 @@