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 @@
ExitleaveGame()
Index: ps/trunk/source/simulation2/MessageTypes.h
===================================================================
--- ps/trunk/source/simulation2/MessageTypes.h (revision 16750)
+++ ps/trunk/source/simulation2/MessageTypes.h (revision 16751)
@@ -1,541 +1,541 @@
-/* Copyright (C) 2014 Wildfire Games.
+/* 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_MESSAGETYPES
#define INCLUDED_MESSAGETYPES
#include "simulation2/system/Components.h"
#include "simulation2/system/Entity.h"
#include "simulation2/system/Message.h"
#include "simulation2/helpers/Player.h"
#include "simulation2/helpers/Position.h"
#include "simulation2/components/ICmpPathfinder.h"
#include "maths/Vector3D.h"
#define DEFAULT_MESSAGE_IMPL(name) \
virtual int GetType() const { return MT_##name; } \
virtual const char* GetScriptHandlerName() const { return "On" #name; } \
virtual const char* GetScriptGlobalHandlerName() const { return "OnGlobal" #name; } \
virtual JS::Value ToJSVal(ScriptInterface& scriptInterface) const; \
static CMessage* FromJSVal(ScriptInterface&, JS::HandleValue val);
class SceneCollector;
class CFrustum;
class CMessageTurnStart : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(TurnStart)
CMessageTurnStart()
{
}
};
// The update process is split into a number of phases, in an attempt
// to cope with dependencies between components. Each phase is implemented
// as a separate message. Simulation2.cpp sends them in sequence.
/**
* Generic per-turn update message, for things that don't care much about ordering.
*/
class CMessageUpdate : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Update)
CMessageUpdate(fixed turnLength) :
turnLength(turnLength)
{
}
fixed turnLength;
};
/**
* Update phase for formation controller movement (must happen before individual
* units move to follow their formation).
*/
class CMessageUpdate_MotionFormation : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Update_MotionFormation)
CMessageUpdate_MotionFormation(fixed turnLength) :
turnLength(turnLength)
{
}
fixed turnLength;
};
/**
* Update phase for non-formation-controller unit movement.
*/
class CMessageUpdate_MotionUnit : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Update_MotionUnit)
CMessageUpdate_MotionUnit(fixed turnLength) :
turnLength(turnLength)
{
}
fixed turnLength;
};
/**
* Final update phase, after all other updates.
*/
class CMessageUpdate_Final : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Update_Final)
CMessageUpdate_Final(fixed turnLength) :
turnLength(turnLength)
{
}
fixed turnLength;
};
/**
* Prepare for rendering a new frame (set up model positions etc).
*/
class CMessageInterpolate : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Interpolate)
CMessageInterpolate(float deltaSimTime, float offset, float deltaRealTime) :
deltaSimTime(deltaSimTime), offset(offset), deltaRealTime(deltaRealTime)
{
}
/// Elapsed simulation time since previous interpolate, in seconds. This is similar to the elapsed real time, except
/// it is scaled by the current simulation rate (and might indeed be zero).
float deltaSimTime;
/// Range [0, 1] (inclusive); fractional time of current frame between previous/next simulation turns.
float offset;
/// Elapsed real time since previous interpolate, in seconds.
float deltaRealTime;
};
/**
* Add renderable objects to the scene collector.
* Called after CMessageInterpolate.
*/
class CMessageRenderSubmit : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(RenderSubmit)
CMessageRenderSubmit(SceneCollector& collector, const CFrustum& frustum, bool culling) :
collector(collector), frustum(frustum), culling(culling)
{
}
SceneCollector& collector;
const CFrustum& frustum;
bool culling;
};
/**
* Handle progressive loading of resources.
* A component that listens to this message must do the following:
* - Increase *msg.total by the non-zero number of loading tasks this component can perform.
* - If *msg.progressed == true, return and do nothing.
* - If you've loaded everything, increase *msg.progress by the value you added to .total
* - Otherwise do some loading, set *msg.progressed = true, and increase *msg.progress by a
* value indicating how much progress you've made in total (0 <= p <= what you added to .total)
* In some situations these messages will never be sent - components must ensure they
* load all their data themselves before using it in that case.
*/
class CMessageProgressiveLoad : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(ProgressiveLoad)
CMessageProgressiveLoad(bool* progressed, int* total, int* progress) :
progressed(progressed), total(total), progress(progress)
{
}
bool* progressed;
int* total;
int* progress;
};
/**
* Broadcast after the entire simulation state has been deserialized.
* Components should do all their self-contained work in their Deserialize
* function when possible. But any reinitialisation that depends on other
* components or other entities, that might not be constructed until later
* in the deserialization process, may be done in response to this message
* instead.
*/
class CMessageDeserialized : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Deserialized)
CMessageDeserialized()
{
}
};
/**
* This is sent immediately after a new entity's components have all been created
* and initialised.
*/
class CMessageCreate : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Create)
CMessageCreate(entity_id_t entity) :
entity(entity)
{
}
entity_id_t entity;
};
/**
* This is sent immediately before a destroyed entity is flushed and really destroyed.
* (That is, after CComponentManager::DestroyComponentsSoon and inside FlushDestroyedComponents).
* The entity will still exist at the time this message is sent.
* It's possible for this message to be sent multiple times for one entity, but all its components
* will have been deleted after the first time.
*/
class CMessageDestroy : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(Destroy)
CMessageDestroy(entity_id_t entity) :
entity(entity)
{
}
entity_id_t entity;
};
class CMessageOwnershipChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(OwnershipChanged)
CMessageOwnershipChanged(entity_id_t entity, player_id_t from, player_id_t to) :
entity(entity), from(from), to(to)
{
}
entity_id_t entity;
player_id_t from;
player_id_t to;
};
/**
* Sent by CCmpPosition whenever anything has changed that will affect the
* return value of GetPosition2D() or GetRotation().Y
*
* If @c inWorld is false, then the other fields are invalid and meaningless.
* Otherwise they represent the current position.
*/
class CMessagePositionChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(PositionChanged)
CMessagePositionChanged(entity_id_t entity, bool inWorld, entity_pos_t x, entity_pos_t z, entity_angle_t a) :
entity(entity), inWorld(inWorld), x(x), z(z), a(a)
{
}
entity_id_t entity;
bool inWorld;
entity_pos_t x, z;
entity_angle_t a;
};
/**
* Sent by CCmpPosition whenever anything has changed that will affect the
* return value of GetInterpolatedTransform()
*/
class CMessageInterpolatedPositionChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(InterpolatedPositionChanged)
CMessageInterpolatedPositionChanged(entity_id_t entity, bool inWorld, const CVector3D& pos0, const CVector3D& pos1) :
entity(entity), inWorld(inWorld), pos0(pos0), pos1(pos1)
{
}
entity_id_t entity;
bool inWorld;
CVector3D pos0;
CVector3D pos1;
};
/*Sent whenever the territory type (neutral,own,enemy) differs from the former type*/
class CMessageTerritoryPositionChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(TerritoryPositionChanged)
CMessageTerritoryPositionChanged(entity_id_t entity, player_id_t newTerritory) :
entity(entity), newTerritory(newTerritory)
{
}
entity_id_t entity;
player_id_t newTerritory;
};
/**
* Sent by CCmpUnitMotion during Update, whenever the motion status has changed
* since the previous update.
*/
class CMessageMotionChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(MotionChanged)
CMessageMotionChanged(bool starting, bool error) :
starting(starting), error(error)
{
}
bool starting; // whether this is a start or end of movement
bool error; // whether we failed to start moving (couldn't find any path)
};
/**
* Sent when water height has been changed.
*/
class CMessageWaterChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(WaterChanged)
CMessageWaterChanged()
{
}
};
/**
* Sent when terrain (texture or elevation) has been changed.
*/
class CMessageTerrainChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(TerrainChanged)
CMessageTerrainChanged(int32_t i0, int32_t j0, int32_t i1, int32_t j1) :
i0(i0), j0(j0), i1(i1), j1(j1)
{
}
int32_t i0, j0, i1, j1; // inclusive lower bound, exclusive upper bound, in tiles
};
/**
* Sent, at most once per turn, when the visibility of an entity changed
*/
class CMessageVisibilityChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(VisibilityChanged)
CMessageVisibilityChanged(player_id_t player, entity_id_t ent, int oldVisibility, int newVisibility) :
player(player), ent(ent), oldVisibility(oldVisibility), newVisibility(newVisibility)
{
}
player_id_t player;
entity_id_t ent;
int oldVisibility;
int newVisibility;
};
/**
* Sent when ObstructionManager's view of the shape of the world has changed
* (changing the TILE_OUTOFBOUNDS tiles returned by Rasterise).
*/
class CMessageObstructionMapShapeChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(ObstructionMapShapeChanged)
CMessageObstructionMapShapeChanged()
{
}
};
/**
* Sent when territory assignments have changed.
*/
class CMessageTerritoriesChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(TerritoriesChanged)
CMessageTerritoriesChanged()
{
}
};
/**
* Sent by CCmpRangeManager at most once per turn, when an active range query
* has had matching units enter/leave the range since the last RangeUpdate.
*/
class CMessageRangeUpdate : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(RangeUpdate)
u32 tag;
std::vector added;
std::vector removed;
// CCmpRangeManager wants to store a vector of messages and wants to
// swap vectors instead of copying (to save on memory allocations),
// so add some constructors for it:
// don't init tag in empty ctor
CMessageRangeUpdate()
{
}
CMessageRangeUpdate(u32 tag) : tag(tag)
{
}
CMessageRangeUpdate(u32 tag, const std::vector& added, const std::vector& removed)
: tag(tag), added(added), removed(removed)
{
}
CMessageRangeUpdate(const CMessageRangeUpdate& other)
: CMessage(), tag(other.tag), added(other.added), removed(other.removed)
{
}
CMessageRangeUpdate& operator=(const CMessageRangeUpdate& other)
{
tag = other.tag;
added = other.added;
removed = other.removed;
return *this;
}
};
/**
* Sent by CCmpPathfinder after async path requests.
*/
class CMessagePathResult : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(PathResult)
- CMessagePathResult(u32 ticket, const ICmpPathfinder::Path& path) :
+ CMessagePathResult(u32 ticket, const WaypointPath& path) :
ticket(ticket), path(path)
{
}
u32 ticket;
- ICmpPathfinder::Path path;
+ WaypointPath path;
};
/**
* Sent by aura manager when a value of a certain entity's component is changed
*/
class CMessageValueModification : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(ValueModification)
CMessageValueModification(const std::vector& entities, std::wstring component, const std::vector& valueNames) :
entities(entities),
component(component),
valueNames(valueNames)
{
}
std::vector entities;
std::wstring component;
std::vector valueNames;
};
/**
* Sent by aura and tech managers when a value of a certain template's component is changed
*/
class CMessageTemplateModification : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(TemplateModification)
CMessageTemplateModification(player_id_t player, std::wstring component, const std::vector& valueNames) :
player(player),
component(component),
valueNames(valueNames)
{
}
player_id_t player;
std::wstring component;
std::vector valueNames;
};
/**
* Sent by CCmpVision when an entity's vision range changes.
*/
class CMessageVisionRangeChanged : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(VisionRangeChanged)
CMessageVisionRangeChanged(entity_id_t entity, entity_pos_t oldRange, entity_pos_t newRange) :
entity(entity), oldRange(oldRange), newRange(newRange)
{
}
entity_id_t entity;
entity_pos_t oldRange;
entity_pos_t newRange;
};
/**
* Sent when an entity pings the minimap
*/
class CMessageMinimapPing : public CMessage
{
public:
DEFAULT_MESSAGE_IMPL(MinimapPing)
CMessageMinimapPing()
{
}
};
#endif // INCLUDED_MESSAGETYPES
Index: ps/trunk/source/simulation2/components/ICmpObstruction.h
===================================================================
--- ps/trunk/source/simulation2/components/ICmpObstruction.h (revision 16750)
+++ ps/trunk/source/simulation2/components/ICmpObstruction.h (revision 16751)
@@ -1,121 +1,123 @@
-/* Copyright (C) 2013 Wildfire Games.
+/* 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_ICMPOBSTRUCTION
#define INCLUDED_ICMPOBSTRUCTION
#include "simulation2/system/Interface.h"
#include "simulation2/components/ICmpObstructionManager.h"
/**
* Flags an entity as obstructing movement for other units,
* and handles the processing of collision queries.
*/
class ICmpObstruction : public IComponent
{
public:
enum EFoundationCheck {
FOUNDATION_CHECK_SUCCESS,
FOUNDATION_CHECK_FAIL_ERROR,
FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION,
FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION,
FOUNDATION_CHECK_FAIL_TERRAIN_CLASS
};
virtual ICmpObstructionManager::tag_t GetObstruction() = 0;
/**
* Gets the square corresponding to this obstruction shape.
* @return true and updates @p out on success;
* false on failure (e.g. object not in the world).
*/
virtual bool GetObstructionSquare(ICmpObstructionManager::ObstructionSquare& out) = 0;
/**
* Same as the method above, but returns an obstruction shape for the previous turn
*/
virtual bool GetPreviousObstructionSquare(ICmpObstructionManager::ObstructionSquare& out) = 0;
virtual entity_pos_t GetSize() = 0;
virtual entity_pos_t GetUnitRadius() = 0;
+ virtual void SetUnitClearance(const entity_pos_t& clearance) = 0;
+
virtual bool IsControlPersistent() = 0;
/**
* Test whether this entity is colliding with any obstruction that are set to
* block the creation of foundations.
* @param ignoredEntities List of entities to ignore during the test.
* @return FOUNDATION_CHECK_SUCCESS if check passes, else an EFoundationCheck
* value describing the type of failure.
*/
virtual EFoundationCheck CheckFoundation(std::string className) = 0;
virtual EFoundationCheck CheckFoundation(std::string className, bool onlyCenterPoint) = 0;
/**
* CheckFoundation wrapper for script calls, to return friendly strings instead of an EFoundationCheck.
* @return "success" if check passes, else a string describing the type of failure.
*/
virtual std::string CheckFoundation_wrapper(std::string className, bool onlyCenterPoint);
/**
* Test whether this entity is colliding with any obstructions that share its
* control groups and block the creation of foundations.
* @return true if foundation is valid (not obstructed)
*/
virtual bool CheckDuplicateFoundation() = 0;
/**
* Returns a list of entities that are colliding with this entity,
* filtered depending on type of entities that are requested.
* @return vector of blocking entities
*/
virtual std::vector GetEntityCollisions(bool checkStructures, bool checkUnits) = 0;
/**
* Detects collisions between foundation-blocking entities and
* tries to fix them by setting control groups, if appropriate.
*/
virtual void ResolveFoundationCollisions() = 0;
virtual void SetActive(bool active) = 0;
virtual void SetMovingFlag(bool enabled) = 0;
virtual void SetDisableBlockMovementPathfinding(bool movementDisabled, bool pathfindingDisabled, int32_t shape) = 0;
virtual bool GetBlockMovementFlag() = 0;
/**
* Change the control group that the entity belongs to.
* Control groups are used to let units ignore collisions with other units from
* the same group. Default is the entity's own ID.
*/
virtual void SetControlGroup(entity_id_t group) = 0;
/// See SetControlGroup.
virtual entity_id_t GetControlGroup() = 0;
virtual void SetControlGroup2(entity_id_t group2) = 0;
virtual entity_id_t GetControlGroup2() = 0;
DECLARE_INTERFACE_TYPE(Obstruction)
};
#endif // INCLUDED_ICMPOBSTRUCTION
Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h
===================================================================
--- ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 16750)
+++ ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 16751)
@@ -1,211 +1,187 @@
/* 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_ICMPPATHFINDER
#define INCLUDED_ICMPPATHFINDER
#include "simulation2/system/Interface.h"
#include "simulation2/components/ICmpObstruction.h"
-#include "simulation2/helpers/Position.h"
+#include "simulation2/helpers/PathGoal.h"
+#include "simulation2/helpers/Pathfinding.h"
#include "maths/FixedVector2D.h"
#include