Index: ps/trunk/source/graphics/TerritoryBoundary.h =================================================================== --- ps/trunk/source/graphics/TerritoryBoundary.h (revision 20629) +++ ps/trunk/source/graphics/TerritoryBoundary.h (revision 20630) @@ -1,66 +1,68 @@ /* 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 . */ #ifndef INCLUDED_TERRITORYBOUNDARY #define INCLUDED_TERRITORYBOUNDARY #include #include "maths/Vector2D.h" -#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/Player.h" +template +class Grid; + /** * Describes an outline of a territory, where the latter are understood to mean the largest sets of mutually connected tiles * ('connected' as in the mathematical sense from graph theory) that are either all reachable or all unreachable from a root * influence entity. * * Note that the latter property is also called the 'connected' flag in the territory manager terminology, because for tiles * to be reachable from a root influence entity they must in fact be mathematically connected. Hence, you should not confuse * the 'connected' flag with the pure mathematical concept of connectedness, because in the former it is implicitly * understood that the connection is to a root influence entity. */ struct STerritoryBoundary { /// Set if this boundary should blink bool blinking; player_id_t owner; /// The boundary points, in clockwise order for inner boundaries and counter-clockwise order for outer boundaries. /// Note: if you need a way to explicitly find out which winding order these are in, you can have /// CTerritoryBoundCalculator::ComputeBoundaries set it during computation -- see its implementation for details. std::vector points; }; /** * Responsible for calculating territory boundaries, given an input territory map. Factored out for testing. */ class CTerritoryBoundaryCalculator { private: CTerritoryBoundaryCalculator(){} // private ctor public: /** * Computes and returns all territory boundaries on the provided territory map (see STerritoryBoundary for a definition). * The result includes both inner and outer territory boundaries. Outer boundaries have their points in CCW order, inner * boundaries have them in CW order (because this matches the winding orders needed by the renderer to offset them * inwards/outwards appropriately). */ static std::vector ComputeBoundaries(const Grid* territories); }; #endif // INCLUDED_TERRITORYBOUNDARY Index: ps/trunk/source/graphics/TerritoryTexture.h =================================================================== --- ps/trunk/source/graphics/TerritoryTexture.h (revision 20629) +++ ps/trunk/source/graphics/TerritoryTexture.h (revision 20630) @@ -1,89 +1,90 @@ /* Copyright (C) 2011 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 2 of the License, or * (at your option) any later version. * * 0 A.D. is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with 0 A.D. If not, see . */ #include "lib/ogl.h" #include "maths/Matrix3D.h" -#include "simulation2/helpers/Grid.h" class CSimulation2; +template +class Grid; /** * Maintains the territory boundary texture, used for * rendering and for the minimap. */ class CTerritoryTexture { NONCOPYABLE(CTerritoryTexture); public: CTerritoryTexture(CSimulation2& simulation); ~CTerritoryTexture(); /** * Recomputes the territory texture if necessary, and binds it to the requested * texture unit. * Also switches the current active texture unit, and enables texturing on it. * The texture is in 32-bit BGRA format. */ void BindTexture(int unit); /** * Recomputes the territory texture if necessary, and returns the texture handle. * Also potentially switches the current active texture unit, and enables texturing on it. * The texture is in 32-bit BGRA format. */ GLuint GetTexture(); /** * Returns a matrix to map (x,y,z) world coordinates onto (u,v) texture * coordinates, in the form expected by glLoadMatrixf. * This must only be called after BindTexture. */ const float* GetTextureMatrix(); /** * Returns a matrix to map (0,0)-(1,1) texture coordinates onto texture * coordinates, in the form expected by glLoadMatrixf. * This must only be called after BindTexture. */ const CMatrix3D* GetMinimapTextureMatrix(); private: /** * Returns true if the territory state has changed since the last call to this function */ bool UpdateDirty(); void DeleteTexture(); void ConstructTexture(int unit); void RecomputeTexture(int unit); void GenerateBitmap(const Grid& territories, u8* bitmap, ssize_t w, ssize_t h); CSimulation2& m_Simulation; size_t m_DirtyID; GLuint m_Texture; ssize_t m_MapSize; // tiles per side GLsizei m_TextureSize; // texels per side CMatrix3D m_TextureMatrix; CMatrix3D m_MinimapTextureMatrix; }; Index: ps/trunk/source/simulation2/components/ICmpTerritoryManager.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpTerritoryManager.h (revision 20629) +++ ps/trunk/source/simulation2/components/ICmpTerritoryManager.h (revision 20630) @@ -1,95 +1,97 @@ /* Copyright (C) 2017 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_ICMPTERRITORYMANAGER #define INCLUDED_ICMPTERRITORYMANAGER #include "simulation2/system/Interface.h" -#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/Player.h" #include "simulation2/components/ICmpPosition.h" +template +class Grid; + class ICmpTerritoryManager : public IComponent { public: virtual bool NeedUpdate(size_t* dirtyID) const = 0; virtual bool NeedUpdate(size_t* dirtyID, size_t* dirtyBlinkingID) const = 0; /** * Number of pathfinder navcells per territory tile. * Passability data is stored per navcell, but we probably don't need that much * resolution, and a lower resolution can make the boundary lines look prettier * and will take less memory, so we downsample the passability data. */ static const int NAVCELLS_PER_TERRITORY_TILE = 8; static const int TERRITORY_PLAYER_MASK = 0x1F; static const int TERRITORY_CONNECTED_MASK = 0x20; static const int TERRITORY_BLINKING_MASK = 0x40; static const int TERRITORY_PROCESSED_MASK = 0x80; //< For internal use; marks a tile as processed. /** * For each tile, the TERRITORY_PLAYER_MASK bits are player ID; * TERRITORY_CONNECTED_MASK is set if the tile is connected to a root object * (civ center etc). */ virtual const Grid& GetTerritoryGrid() = 0; /** * Get owner of territory at given position. * @return player ID of owner; 0 if neutral territory */ virtual player_id_t GetOwner(entity_pos_t x, entity_pos_t z) = 0; /** * get the number of neighbour tiles for per player for the selected position * @return A list with the number of neighbour tiles per player */ virtual std::vector GetNeighbours(entity_pos_t x, entity_pos_t z, bool filterConnected) = 0; /** * Get whether territory at given position is connected to a root object * (civ center etc) owned by that territory's player. */ virtual bool IsConnected(entity_pos_t x, entity_pos_t z) = 0; /** * Set a piece of territory to blinking. Must be updated on every territory calculation */ virtual void SetTerritoryBlinking(entity_pos_t x, entity_pos_t z, bool enable) = 0; /** * Check if a piece of territory is blinking. */ virtual bool IsTerritoryBlinking(entity_pos_t x, entity_pos_t z) = 0; /** * Returns the percentage of the world controlled by a given player as defined by * the number of territory cells the given player owns */ virtual u8 GetTerritoryPercentage(player_id_t player) = 0; /** * Enables or disables rendering of an territory borders. */ virtual void SetVisibility(bool visible) = 0; DECLARE_INTERFACE_TYPE(TerritoryManager) }; #endif // INCLUDED_ICMPTERRITORYMANAGER Index: ps/trunk/source/simulation2/helpers/Grid.h =================================================================== --- ps/trunk/source/simulation2/helpers/Grid.h (revision 20629) +++ ps/trunk/source/simulation2/helpers/Grid.h (revision 20630) @@ -1,275 +1,291 @@ /* Copyright (C) 2017 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_GRID #define INCLUDED_GRID #include #ifdef NDEBUG #define GRID_BOUNDS_DEBUG 0 #else #define GRID_BOUNDS_DEBUG 1 #endif /** * Basic 2D array, intended for storing tile data, plus support for lazy updates * by ICmpObstructionManager. * @c T must be a POD type that can be initialised with 0s. */ template class Grid { public: Grid() : m_W(0), m_H(0), m_Data(NULL), m_DirtyID(0) { } Grid(u16 w, u16 h) : m_W(w), m_H(h), m_Data(NULL), m_DirtyID(0) { if (m_W || m_H) m_Data = new T[m_W * m_H]; reset(); } Grid(const Grid& g) : m_W(0), m_H(0), m_Data(NULL), m_DirtyID(0) { *this = g; } Grid& operator=(const Grid& g) { if (this == &g) return *this; m_DirtyID = g.m_DirtyID; if (m_W == g.m_W && m_H == g.m_H) { memcpy(m_Data, g.m_Data, m_W*m_H*sizeof(T)); return *this; } m_W = g.m_W; m_H = g.m_H; delete[] m_Data; if (g.m_Data) { m_Data = new T[m_W * m_H]; memcpy(m_Data, g.m_Data, m_W*m_H*sizeof(T)); } else m_Data = NULL; return *this; } void swap(Grid& g) { std::swap(m_DirtyID, g.m_DirtyID); std::swap(m_Data, g.m_Data); std::swap(m_H, g.m_H); std::swap(m_W, g.m_W); } ~Grid() { delete[] m_Data; } bool operator==(const Grid& g) const { if (!compare_sizes(&g) || m_DirtyID != g.m_DirtyID) return false; return memcmp(m_Data, g.m_Data, m_W*m_H*sizeof(T)) == 0; } bool blank() const { return m_W == 0 && m_H == 0; } + bool any_set_in_square(int i0, int j0, int i1, int j1) const + { + #if GRID_BOUNDS_DEBUG + ENSURE(i0 >= 0 && j0 >= 0 && i1 < m_W && j1 < m_H); + #endif + for (int j = j0; j < j1; ++j) + { + int sum = 0; + for (int i = i0; i < i1; ++i) + sum += m_Data[j*m_W + i]; + if (sum > 0) + return true; + } + return false; + } + void reset() { if (m_Data) memset(m_Data, 0, m_W*m_H*sizeof(T)); } // Add two grids of the same size void add(const Grid& g) { #if GRID_BOUNDS_DEBUG ENSURE(g.m_W == m_W && g.m_H == m_H); #endif for (int i=0; i < m_H*m_W; ++i) m_Data[i] += g.m_Data[i]; } void bitwise_or(const Grid& g) { if (this == &g) return; #if GRID_BOUNDS_DEBUG ENSURE(g.m_W == m_W && g.m_H == m_H); #endif for (int i = 0; i < m_H*m_W; ++i) m_Data[i] |= g.m_Data[i]; } void set(int i, int j, const T& value) { #if GRID_BOUNDS_DEBUG ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H); #endif m_Data[j*m_W + i] = value; } T& get(int i, int j) const { #if GRID_BOUNDS_DEBUG ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H); #endif return m_Data[j*m_W + i]; } template bool compare_sizes(const Grid* g) const { return m_W == g->m_W && m_H == g->m_H; } u16 m_W, m_H; T* m_Data; size_t m_DirtyID; // if this is < the id maintained by ICmpObstructionManager then it needs to be updated }; /** * Similar to Grid, except optimised for sparse usage (the grid is subdivided into * buckets whose contents are only initialised on demand, to save on memset cost). */ template class SparseGrid { NONCOPYABLE(SparseGrid); enum { BucketBits = 4, BucketSize = 1 << BucketBits }; T* GetBucket(int i, int j) { size_t b = (j >> BucketBits) * m_BW + (i >> BucketBits); if (!m_Data[b]) { m_Data[b] = new T[BucketSize*BucketSize]; memset(m_Data[b], 0, BucketSize*BucketSize*sizeof(T)); } return m_Data[b]; } public: SparseGrid(u16 w, u16 h) : m_W(w), m_H(h), m_DirtyID(0) { ENSURE(m_W && m_H); m_BW = (u16)((m_W + BucketSize-1) >> BucketBits); m_BH = (u16)((m_H + BucketSize-1) >> BucketBits); m_Data = new T*[m_BW*m_BH]; memset(m_Data, 0, m_BW*m_BH*sizeof(T*)); } ~SparseGrid() { reset(); delete[] m_Data; } void reset() { for (size_t i = 0; i < (size_t)(m_BW*m_BH); ++i) delete[] m_Data[i]; memset(m_Data, 0, m_BW*m_BH*sizeof(T*)); } void set(int i, int j, const T& value) { #if GRID_BOUNDS_DEBUG ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H); #endif GetBucket(i, j)[(j % BucketSize)*BucketSize + (i % BucketSize)] = value; } T& get(int i, int j) { #if GRID_BOUNDS_DEBUG ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H); #endif return GetBucket(i, j)[(j % BucketSize)*BucketSize + (i % BucketSize)]; } u16 m_W, m_H; u16 m_BW, m_BH; T** m_Data; size_t m_DirtyID; // if this is < the id maintained by ICmpObstructionManager then it needs to be updated }; /** * Structure holding grid dirtiness informations, for clever updates. */ struct GridUpdateInformation { bool dirty; bool globallyDirty; Grid dirtinessGrid; /** * Update the information with additionnal needed updates, then erase the source of additions. * This can usually be optimized through a careful memory management. */ void MergeAndClear(GridUpdateInformation& b) { ENSURE(dirtinessGrid.compare_sizes(&b.dirtinessGrid)); bool wasDirty = dirty; dirty |= b.dirty; globallyDirty |= b.globallyDirty; // If the current grid is useless, swap it if (!wasDirty) dirtinessGrid.swap(b.dirtinessGrid); // If the new grid isn't used, don't bother updating it else if (dirty && !globallyDirty) dirtinessGrid.bitwise_or(b.dirtinessGrid); b.Clean(); } /** * Mark everything as clean */ void Clean() { dirty = false; globallyDirty = false; dirtinessGrid.reset(); } }; #endif // INCLUDED_GRID Index: ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.cpp (revision 20629) +++ ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.cpp (revision 20630) @@ -1,788 +1,777 @@ /* Copyright (C) 2016 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 "HierarchicalPathfinder.h" #include "graphics/Overlay.h" #include "ps/Profile.h" // Find the root ID of a region, used by InitRegions inline u16 RootID(u16 x, const std::vector& v) { while (v[x] < x) x = v[x]; return x; } void HierarchicalPathfinder::Chunk::InitRegions(int ci, int cj, Grid* grid, pass_class_t passClass) { ENSURE(ci < 256 && cj < 256); // avoid overflows m_ChunkI = ci; m_ChunkJ = cj; memset(m_Regions, 0, sizeof(m_Regions)); int i0 = ci * CHUNK_SIZE; int j0 = cj * CHUNK_SIZE; int i1 = std::min(i0 + CHUNK_SIZE, (int)grid->m_W); int j1 = std::min(j0 + CHUNK_SIZE, (int)grid->m_H); // Efficiently flood-fill the m_Regions grid int regionID = 0; std::vector connect; u16* pCurrentID = NULL; u16 LeftID = 0; u16 DownID = 0; bool Checked = false; // prevent some unneccessary RootID calls connect.reserve(32); // TODO: What's a sensible number? connect.push_back(0); // connect[0] = 0 // Start by filling the grid with 0 for blocked, // and regionID for unblocked for (int j = j0; j < j1; ++j) { for (int i = i0; i < i1; ++i) { pCurrentID = &m_Regions[j-j0][i-i0]; if (!IS_PASSABLE(grid->get(i, j), passClass)) { *pCurrentID = 0; continue; } if (j > j0) DownID = m_Regions[j-1-j0][i-i0]; if (i == i0) LeftID = 0; else LeftID = m_Regions[j-j0][i-1-i0]; if (LeftID > 0) { *pCurrentID = LeftID; if (*pCurrentID != DownID && DownID > 0 && !Checked) { u16 id0 = RootID(DownID, connect); u16 id1 = RootID(LeftID, connect); Checked = true; // this avoids repeatedly connecting the same IDs if (id0 < id1) connect[id1] = id0; else if (id0 > id1) connect[id0] = id1; } else if (DownID == 0) Checked = false; } else if (DownID > 0) { *pCurrentID = DownID; Checked = false; } else { // New ID *pCurrentID = ++regionID; connect.push_back(regionID); Checked = false; } } } // Directly point the root ID m_NumRegions = 0; for (u16 i = 1; i < regionID+1; ++i) { if (connect[i] == i) ++m_NumRegions; else connect[i] = RootID(i, connect); } // Replace IDs by the root ID for (int j = 0; j < CHUNK_SIZE; ++j) for (int i = 0; i < CHUNK_SIZE; ++i) m_Regions[j][i] = connect[m_Regions[j][i]]; } /** * Returns a RegionID for the given global navcell coords * (which must be inside this chunk); */ HierarchicalPathfinder::RegionID HierarchicalPathfinder::Chunk::Get(int i, int j) const { ENSURE(i < CHUNK_SIZE && j < CHUNK_SIZE); return RegionID(m_ChunkI, m_ChunkJ, m_Regions[j][i]); } /** * Return the global navcell coords that correspond roughly to the * center of the given region in this chunk. * (This is not guaranteed to be actually inside the region.) */ void HierarchicalPathfinder::Chunk::RegionCenter(u16 r, int& i_out, int& j_out) const { // Find the mean of i,j coords of navcells in this region: u32 si = 0, sj = 0; // sum of i,j coords u32 n = 0; // number of navcells in region cassert(CHUNK_SIZE < 256); // conservative limit to ensure si and sj don't overflow for (int j = 0; j < CHUNK_SIZE; ++j) { for (int i = 0; i < CHUNK_SIZE; ++i) { if (m_Regions[j][i] == r) { si += i; sj += j; n += 1; } } } // Avoid divide-by-zero if (n == 0) n = 1; i_out = m_ChunkI * CHUNK_SIZE + si / n; j_out = m_ChunkJ * CHUNK_SIZE + sj / n; } /** * Returns the global navcell coords, and the squared distance to the goal * navcell, of whichever navcell inside the given region is closest to * that goal. */ void HierarchicalPathfinder::Chunk::RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const { iBest = 0; jBest = 0; dist2Best = std::numeric_limits::max(); for (int j = 0; j < CHUNK_SIZE; ++j) { for (int i = 0; i < CHUNK_SIZE; ++i) { if (m_Regions[j][i] != r) continue; u32 dist2 = (i + m_ChunkI*CHUNK_SIZE - iGoal)*(i + m_ChunkI*CHUNK_SIZE - iGoal) + (j + m_ChunkJ*CHUNK_SIZE - jGoal)*(j + m_ChunkJ*CHUNK_SIZE - jGoal); if (dist2 < dist2Best) { iBest = i + m_ChunkI*CHUNK_SIZE; jBest = j + m_ChunkJ*CHUNK_SIZE; dist2Best = dist2; } } } } /** * Gives the global navcell coords, and the squared distance to the (i0,j0) * navcell, of whichever navcell inside the given region and inside the given goal * is closest to (i0,j0) * Returns true if the goal is inside the region, false otherwise. */ bool HierarchicalPathfinder::Chunk::RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const { // TODO: this should be optimized further. // Most used cases empirically seem to be SQUARE, INVERTED_CIRCLE and then POINT and CIRCLE somehwat equally iOut = 0; jOut = 0; dist2Best = std::numeric_limits::max(); // Calculate the navcell that contains the center of the goal. int gi = (goal.x >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToNegInfinity(); int gj = (goal.z >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToNegInfinity(); switch(goal.type) { case PathGoal::POINT: { // i and j can be equal to CHUNK_SIZE on the top and right borders of the map, // specially when mapSize is a multiple of CHUNK_SIZE int i = std::min((int)CHUNK_SIZE - 1, gi - m_ChunkI * CHUNK_SIZE); int j = std::min((int)CHUNK_SIZE - 1, gj - m_ChunkJ * CHUNK_SIZE); if (m_Regions[j][i] == r) { iOut = gi; jOut = gj; dist2Best = (gi - i0)*(gi - i0) + (gj - j0)*(gj - j0); return true; } return false; } case PathGoal::CIRCLE: case PathGoal::SQUARE: { // restrict ourselves to a square surrounding the goal. int radius = (std::max(goal.hw*3/2,goal.hh*3/2) >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToInfinity(); int imin = std::max(0, gi-m_ChunkI*CHUNK_SIZE-radius); int imax = std::min((int)CHUNK_SIZE, gi-m_ChunkI*CHUNK_SIZE+radius+1); int jmin = std::max(0, gj-m_ChunkJ*CHUNK_SIZE-radius); int jmax = std::min((int)CHUNK_SIZE, gj-m_ChunkJ*CHUNK_SIZE+radius+1); bool found = false; u32 dist2 = std::numeric_limits::max(); for (u16 j = jmin; j < jmax; ++j) { for (u16 i = imin; i < imax; ++i) { if (m_Regions[j][i] != r) continue; if (found) { dist2 = (i + m_ChunkI*CHUNK_SIZE - i0)*(i + m_ChunkI*CHUNK_SIZE - i0) + (j + m_ChunkJ*CHUNK_SIZE - j0)*(j + m_ChunkJ*CHUNK_SIZE - j0); if (dist2 >= dist2Best) continue; } if (goal.NavcellContainsGoal(m_ChunkI * CHUNK_SIZE + i, m_ChunkJ * CHUNK_SIZE + j)) { if (!found) { found = true; dist2 = (i + m_ChunkI*CHUNK_SIZE - i0)*(i + m_ChunkI*CHUNK_SIZE - i0) + (j + m_ChunkJ*CHUNK_SIZE - j0)*(j + m_ChunkJ*CHUNK_SIZE - j0); } iOut = i + m_ChunkI*CHUNK_SIZE; jOut = j + m_ChunkJ*CHUNK_SIZE; dist2Best = dist2; } } } return found; } case PathGoal::INVERTED_CIRCLE: case PathGoal::INVERTED_SQUARE: { bool found = false; u32 dist2 = std::numeric_limits::max(); // loop over all navcells. for (u16 j = 0; j < CHUNK_SIZE; ++j) { for (u16 i = 0; i < CHUNK_SIZE; ++i) { if (m_Regions[j][i] != r) continue; if (found) { dist2 = (i + m_ChunkI*CHUNK_SIZE - i0)*(i + m_ChunkI*CHUNK_SIZE - i0) + (j + m_ChunkJ*CHUNK_SIZE - j0)*(j + m_ChunkJ*CHUNK_SIZE - j0); if (dist2 >= dist2Best) continue; } if (goal.NavcellContainsGoal(m_ChunkI * CHUNK_SIZE + i, m_ChunkJ * CHUNK_SIZE + j)) { if (!found) { found = true; dist2 = (i + m_ChunkI*CHUNK_SIZE - i0)*(i + m_ChunkI*CHUNK_SIZE - i0) + (j + m_ChunkJ*CHUNK_SIZE - j0)*(j + m_ChunkJ*CHUNK_SIZE - j0); } iOut = i + m_ChunkI*CHUNK_SIZE; jOut = j + m_ChunkJ*CHUNK_SIZE; dist2Best = dist2; } } } return found; } } return false; } HierarchicalPathfinder::HierarchicalPathfinder() : m_DebugOverlay(NULL) { } HierarchicalPathfinder::~HierarchicalPathfinder() { SAFE_DELETE(m_DebugOverlay); } void HierarchicalPathfinder::SetDebugOverlay(bool enabled, const CSimContext* simContext) { if (enabled && !m_DebugOverlay) { m_DebugOverlay = new HierarchicalOverlay(*this); m_DebugOverlayLines.clear(); m_SimContext = simContext; AddDebugEdges(GetPassabilityClass("default")); } else if (!enabled && m_DebugOverlay) { SAFE_DELETE(m_DebugOverlay); m_DebugOverlayLines.clear(); m_SimContext = NULL; } } void HierarchicalPathfinder::Recompute(Grid* grid, const std::map& nonPathfindingPassClassMasks, const std::map& pathfindingPassClassMasks) { PROFILE3("Hierarchical Recompute"); m_PassClassMasks = pathfindingPassClassMasks; std::map allPassClasses = m_PassClassMasks; allPassClasses.insert(nonPathfindingPassClassMasks.begin(), nonPathfindingPassClassMasks.end()); m_W = grid->m_W; m_H = grid->m_H; // Divide grid into chunks with round-to-positive-infinity m_ChunksW = (grid->m_W + CHUNK_SIZE - 1) / CHUNK_SIZE; m_ChunksH = (grid->m_H + CHUNK_SIZE - 1) / CHUNK_SIZE; ENSURE(m_ChunksW < 256 && m_ChunksH < 256); // else the u8 Chunk::m_ChunkI will overflow m_Chunks.clear(); m_Edges.clear(); for (auto& passClassMask : allPassClasses) { pass_class_t passClass = passClassMask.second; // Compute the regions within each chunk m_Chunks[passClass].resize(m_ChunksW*m_ChunksH); for (int cj = 0; cj < m_ChunksH; ++cj) { for (int ci = 0; ci < m_ChunksW; ++ci) { m_Chunks[passClass].at(cj*m_ChunksW + ci).InitRegions(ci, cj, grid, passClass); } } // Construct the search graph over the regions EdgesMap& edges = m_Edges[passClass]; for (int cj = 0; cj < m_ChunksH; ++cj) { for (int ci = 0; ci < m_ChunksW; ++ci) { FindEdges(ci, cj, passClass, edges); } } } if (m_DebugOverlay) { PROFILE("debug overlay"); m_DebugOverlayLines.clear(); AddDebugEdges(GetPassabilityClass("default")); } } void HierarchicalPathfinder::Update(Grid* grid, const Grid& dirtinessGrid) { PROFILE3("Hierarchical Update"); for (int cj = 0; cj < m_ChunksH; ++cj) { + int j0 = cj * CHUNK_SIZE; + int j1 = std::min(j0 + CHUNK_SIZE, (int)dirtinessGrid.m_H); for (int ci = 0; ci < m_ChunksW; ++ci) { - if (!IsChunkDirty(ci, cj, dirtinessGrid)) + // Skip chunks where no navcells are dirty. + int i0 = ci * CHUNK_SIZE; + int i1 = std::min(i0 + CHUNK_SIZE, (int)dirtinessGrid.m_W); + if (!dirtinessGrid.any_set_in_square(i0, j0, i1, j1)) continue; + for (const std::pair& passClassMask : m_PassClassMasks) { pass_class_t passClass = passClassMask.second; Chunk& a = m_Chunks[passClass].at(ci + cj*m_ChunksW); a.InitRegions(ci, cj, grid, passClass); } } } // TODO: Also be clever with edges m_Edges.clear(); for (const std::pair& passClassMask : m_PassClassMasks) { pass_class_t passClass = passClassMask.second; EdgesMap& edges = m_Edges[passClass]; for (int cj = 0; cj < m_ChunksH; ++cj) { for (int ci = 0; ci < m_ChunksW; ++ci) { FindEdges(ci, cj, passClass, edges); } } } if (m_DebugOverlay) { PROFILE("debug overlay"); m_DebugOverlayLines.clear(); AddDebugEdges(GetPassabilityClass("default")); } } -bool HierarchicalPathfinder::IsChunkDirty(int ci, int cj, const Grid& dirtinessGrid) const -{ - int i0 = ci * CHUNK_SIZE; - int j0 = cj * CHUNK_SIZE; - int i1 = std::min(i0 + CHUNK_SIZE, (int)dirtinessGrid.m_W); - int j1 = std::min(j0 + CHUNK_SIZE, (int)dirtinessGrid.m_H); - for (int j = j0; j < j1; ++j) - { - for (int i = i0; i < i1; ++i) - { - if (dirtinessGrid.get(i, j)) - return true; - } - } - return false; -} - /** * Find edges between regions in this chunk and the adjacent below/left chunks. */ void HierarchicalPathfinder::FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges) { std::vector& chunks = m_Chunks[passClass]; Chunk& a = chunks.at(cj*m_ChunksW + ci); // For each edge between chunks, we loop over every adjacent pair of // navcells in the two chunks. If they are both in valid regions // (i.e. are passable navcells) then add a graph edge between those regions. // (We don't need to test for duplicates since EdgesMap already uses a // std::set which will drop duplicate entries.) // But as set.insert can be quite slow on large collection, and that we usually // try to insert the same values, we cache the previous one for a fast test. if (ci > 0) { Chunk& b = chunks.at(cj*m_ChunksW + (ci-1)); RegionID raPrev(0,0,0); RegionID rbPrev(0,0,0); for (int j = 0; j < CHUNK_SIZE; ++j) { RegionID ra = a.Get(0, j); RegionID rb = b.Get(CHUNK_SIZE-1, j); if (ra.r && rb.r) { if (ra == raPrev && rb == rbPrev) continue; edges[ra].insert(rb); edges[rb].insert(ra); raPrev = ra; rbPrev = rb; } } } if (cj > 0) { Chunk& b = chunks.at((cj-1)*m_ChunksW + ci); RegionID raPrev(0,0,0); RegionID rbPrev(0,0,0); for (int i = 0; i < CHUNK_SIZE; ++i) { RegionID ra = a.Get(i, 0); RegionID rb = b.Get(i, CHUNK_SIZE-1); if (ra.r && rb.r) { if (ra == raPrev && rb == rbPrev) continue; edges[ra].insert(rb); edges[rb].insert(ra); raPrev = ra; rbPrev = rb; } } } } /** * Debug visualisation of graph edges between regions. */ void HierarchicalPathfinder::AddDebugEdges(pass_class_t passClass) { const EdgesMap& edges = m_Edges[passClass]; const std::vector& chunks = m_Chunks[passClass]; for (auto& edge : edges) { for (const RegionID& region: edge.second) { // Draw a line between the two regions' centers int i0, j0, i1, j1; chunks[edge.first.cj * m_ChunksW + edge.first.ci].RegionCenter(edge.first.r, i0, j0); chunks[region.cj * m_ChunksW + region.ci].RegionCenter(region.r, i1, j1); CFixedVector2D a, b; Pathfinding::NavcellCenter(i0, j0, a.X, a.Y); Pathfinding::NavcellCenter(i1, j1, b.X, b.Y); // Push the endpoints inwards a little to avoid overlaps CFixedVector2D d = b - a; d.Normalize(entity_pos_t::FromInt(1)); a += d; b -= d; std::vector xz; xz.push_back(a.X.ToFloat()); xz.push_back(a.Y.ToFloat()); xz.push_back(b.X.ToFloat()); xz.push_back(b.Y.ToFloat()); m_DebugOverlayLines.emplace_back(); m_DebugOverlayLines.back().m_Color = CColor(1.0, 1.0, 1.0, 1.0); SimRender::ConstructLineOnGround(*m_SimContext, xz, m_DebugOverlayLines.back(), true); } } } HierarchicalPathfinder::RegionID HierarchicalPathfinder::Get(u16 i, u16 j, pass_class_t passClass) { int ci = i / CHUNK_SIZE; int cj = j / CHUNK_SIZE; ENSURE(ci < m_ChunksW && cj < m_ChunksH); return m_Chunks[passClass][cj*m_ChunksW + ci].Get(i % CHUNK_SIZE, j % CHUNK_SIZE); } void HierarchicalPathfinder::MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass) { PROFILE2("MakeGoalReachable"); RegionID source = Get(i0, j0, passClass); // Find everywhere that's reachable std::set reachableRegions; FindReachableRegions(source, reachableRegions, passClass); // Check whether any reachable region contains the goal // And get the navcell that's the closest to the point u16 bestI = 0; u16 bestJ = 0; u32 dist2Best = std::numeric_limits::max(); for (const RegionID& region : reachableRegions) { // Skip region if its chunk doesn't contain the goal area entity_pos_t x0 = Pathfinding::NAVCELL_SIZE * (region.ci * CHUNK_SIZE); entity_pos_t z0 = Pathfinding::NAVCELL_SIZE * (region.cj * CHUNK_SIZE); entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE * CHUNK_SIZE; entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE * CHUNK_SIZE; if (!goal.RectContainsGoal(x0, z0, x1, z1)) continue; u16 i,j; u32 dist2; // If the region contains the goal area, the goal is reachable // Remember the best point for optimization. if (GetChunk(region.ci, region.cj, passClass).RegionNearestNavcellInGoal(region.r, i0, j0, goal, i, j, dist2)) { // If it's a point, no need to move it, we're done if (goal.type == PathGoal::POINT) return; if (dist2 < dist2Best) { bestI = i; bestJ = j; dist2Best = dist2; } } } // If the goal area wasn't reachable, // find the navcell that's nearest to the goal's center if (dist2Best == std::numeric_limits::max()) { u16 iGoal, jGoal; Pathfinding::NearestNavcell(goal.x, goal.z, iGoal, jGoal, m_W, m_H); FindNearestNavcellInRegions(reachableRegions, iGoal, jGoal, passClass); // Construct a new point goal at the nearest reachable navcell PathGoal newGoal; newGoal.type = PathGoal::POINT; Pathfinding::NavcellCenter(iGoal, jGoal, newGoal.x, newGoal.z); goal = newGoal; return; } ENSURE(dist2Best != std::numeric_limits::max()); PathGoal newGoal; newGoal.type = PathGoal::POINT; Pathfinding::NavcellCenter(bestI, bestJ, newGoal.x, newGoal.z); goal = newGoal; } void HierarchicalPathfinder::FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass) { std::set regions; FindPassableRegions(regions, passClass); FindNearestNavcellInRegions(regions, i, j, passClass); } void HierarchicalPathfinder::FindNearestNavcellInRegions(const std::set& regions, u16& iGoal, u16& jGoal, pass_class_t passClass) { // Find the navcell in the given regions that's nearest to the goal navcell: // * For each region, record the (squared) minimal distance to the goal point // * Sort regions by that underestimated distance // * For each region, find the actual nearest navcell // * Stop when the underestimated distances are worse than the best real distance std::vector > regionDistEsts; // pair of (distance^2, region) for (const RegionID& region : regions) { int i0 = region.ci * CHUNK_SIZE; int j0 = region.cj * CHUNK_SIZE; int i1 = i0 + CHUNK_SIZE - 1; int j1 = j0 + CHUNK_SIZE - 1; // Pick the point in the chunk nearest the goal int iNear = Clamp((int)iGoal, i0, i1); int jNear = Clamp((int)jGoal, j0, j1); int dist2 = (iNear - iGoal)*(iNear - iGoal) + (jNear - jGoal)*(jNear - jGoal); regionDistEsts.emplace_back(dist2, region); } // Sort by increasing distance (tie-break on RegionID) std::sort(regionDistEsts.begin(), regionDistEsts.end()); int iBest = iGoal; int jBest = jGoal; u32 dist2Best = std::numeric_limits::max(); for (auto& pair : regionDistEsts) { if (pair.first >= dist2Best) break; RegionID region = pair.second; int i, j; u32 dist2; GetChunk(region.ci, region.cj, passClass).RegionNavcellNearest(region.r, iGoal, jGoal, i, j, dist2); if (dist2 < dist2Best) { iBest = i; jBest = j; dist2Best = dist2; } } iGoal = iBest; jGoal = jBest; } void HierarchicalPathfinder::FindReachableRegions(RegionID from, std::set& reachable, pass_class_t passClass) { // Flood-fill the region graph, starting at 'from', // collecting all the regions that are reachable via edges std::vector open; open.push_back(from); reachable.insert(from); while (!open.empty()) { RegionID curr = open.back(); open.pop_back(); for (const RegionID& region : m_Edges[passClass][curr]) // Add to the reachable set; if this is the first time we added // it then also add it to the open list if (reachable.insert(region).second) open.push_back(region); } } void HierarchicalPathfinder::FindPassableRegions(std::set& regions, pass_class_t passClass) { // Construct a set of all regions of all chunks for this pass class for (const Chunk& chunk : m_Chunks[passClass]) { // region 0 is impassable tiles for (int r = 1; r <= chunk.m_NumRegions; ++r) regions.insert(RegionID(chunk.m_ChunkI, chunk.m_ChunkJ, r)); } } void HierarchicalPathfinder::FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid& grid) { ENSURE(grid.m_W == m_W && grid.m_H == m_H); int i0 = region.ci * CHUNK_SIZE; int j0 = region.cj * CHUNK_SIZE; const Chunk& c = m_Chunks[passClass][region.cj * m_ChunksW + region.ci]; for (int j = 0; j < CHUNK_SIZE; ++j) for (int i = 0; i < CHUNK_SIZE; ++i) if (c.m_Regions[j][i] == region.r) grid.set(i0 + i, j0 + j, value); } Grid HierarchicalPathfinder::GetConnectivityGrid(pass_class_t passClass) { Grid connectivityGrid(m_W, m_H); connectivityGrid.reset(); u16 idx = 1; for (size_t i = 0; i < m_W; ++i) { for (size_t j = 0; j < m_H; ++j) { if (connectivityGrid.get(i, j) != 0) continue; RegionID from = Get(i, j, passClass); if (from.r == 0) continue; std::set reachable; FindReachableRegions(from, reachable, passClass); for (const RegionID& region : reachable) FillRegionOnGrid(region, passClass, idx, connectivityGrid); ++idx; } } return connectivityGrid; } Index: ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h (revision 20629) +++ ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h (revision 20630) @@ -1,226 +1,224 @@ /* 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_HIERPATHFINDER #define INCLUDED_HIERPATHFINDER #include "Pathfinding.h" #include "renderer/TerrainOverlay.h" #include "Render.h" #include "graphics/SColor.h" /** * Hierarchical pathfinder. * * It doesn't find shortest paths, but deals with connectivity. * * The navcell-grid representation of the map is split into fixed-size chunks. * Within a chunk, each maximal set of adjacently-connected passable navcells * is defined as a region. * Each region is a vertex in the hierarchical pathfinder's graph. * When two regions in adjacent chunks are connected by passable navcells, * the graph contains an edge between the corresponding two vertexes. * (There will never be an edge between two regions in the same chunk.) * * Since regions are typically fairly large, it is possible to determine * connectivity between any two navcells by mapping them onto their appropriate * region and then doing a relatively small graph search. */ class HierarchicalOverlay; class HierarchicalPathfinder { public: struct RegionID { u8 ci, cj; // chunk ID u16 r; // unique-per-chunk local region ID RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { } bool operator<(RegionID b) const { // Sort by chunk ID, then by per-chunk region ID if (ci < b.ci) return true; if (b.ci < ci) return false; if (cj < b.cj) return true; if (b.cj < cj) return false; return r < b.r; } bool operator==(RegionID b) const { return ((ci == b.ci) && (cj == b.cj) && (r == b.r)); } }; HierarchicalPathfinder(); ~HierarchicalPathfinder(); void SetDebugOverlay(bool enabled, const CSimContext* simContext); // Non-pathfinding grids will never be recomputed on calling HierarchicalPathfinder::Update void Recompute(Grid* passabilityGrid, const std::map& nonPathfindingPassClassMasks, const std::map& pathfindingPassClassMasks); void Update(Grid* grid, const Grid& dirtinessGrid); - bool IsChunkDirty(int ci, int cj, const Grid& dirtinessGrid) const; - RegionID Get(u16 i, u16 j, pass_class_t passClass); /** * Updates @p goal so that it's guaranteed to be reachable from the navcell * @p i0, @p j0 (which is assumed to be on a passable navcell). * * If the goal is not reachable, it is replaced with a point goal nearest to * the goal center. * * In the case of a non-point reachable goal, it is replaced with a point goal * at the reachable navcell of the goal which is nearest to the starting navcell. */ void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass); /** * Updates @p i, @p j (which is assumed to be an impassable navcell) * to the nearest passable navcell. */ void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass); /** * Generates the connectivity grid associated with the given pass_class */ Grid GetConnectivityGrid(pass_class_t passClass); pass_class_t GetPassabilityClass(const std::string& name) const { auto it = m_PassClassMasks.find(name); if (it != m_PassClassMasks.end()) return it->second; LOGERROR("Invalid passability class name '%s'", name.c_str()); return 0; } private: static const u8 CHUNK_SIZE = 96; // number of navcells per side // TODO PATHFINDER: figure out best number. Probably 64 < n < 128 struct Chunk { u8 m_ChunkI, m_ChunkJ; // chunk ID u16 m_NumRegions; // number of local region IDs (starting from 1) u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_NumRegions with a checkerboard pattern void InitRegions(int ci, int cj, Grid* grid, pass_class_t passClass); RegionID Get(int i, int j) const; void RegionCenter(u16 r, int& i, int& j) const; void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const; bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const; }; typedef std::map > EdgesMap; void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges); void FindReachableRegions(RegionID from, std::set& reachable, pass_class_t passClass); void FindPassableRegions(std::set& regions, pass_class_t passClass); /** * Updates @p iGoal and @p jGoal to the navcell that is the nearest to the * initial goal coordinates, in one of the given @p regions. * (Assumes @p regions is non-empty.) */ void FindNearestNavcellInRegions(const std::set& regions, u16& iGoal, u16& jGoal, pass_class_t passClass); Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) { return m_Chunks[passClass].at(cj * m_ChunksW + ci); } void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid& grid); u16 m_W, m_H; u16 m_ChunksW, m_ChunksH; std::map > m_Chunks; std::map m_Edges; // Passability classes for which grids will be updated when calling Update std::map m_PassClassMasks; void AddDebugEdges(pass_class_t passClass); HierarchicalOverlay* m_DebugOverlay; const CSimContext* m_SimContext; // Used for drawing the debug lines public: std::vector m_DebugOverlayLines; }; class HierarchicalOverlay : public TerrainTextureOverlay { public: HierarchicalPathfinder& m_PathfinderHier; HierarchicalOverlay(HierarchicalPathfinder& pathfinderHier) : TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_PathfinderHier(pathfinderHier) { } virtual void BuildTextureRGBA(u8* data, size_t w, size_t h) { pass_class_t passClass = m_PathfinderHier.GetPassabilityClass("default"); for (size_t j = 0; j < h; ++j) { for (size_t i = 0; i < w; ++i) { SColor4ub color; HierarchicalPathfinder::RegionID rid = m_PathfinderHier.Get(i, j, passClass); if (rid.r == 0) color = SColor4ub(0, 0, 0, 0); else if (rid.r == 0xFFFF) color = SColor4ub(255, 0, 255, 255); else color = GetColor(rid.r + rid.ci*5 + rid.cj*7, 127); *data++ = color.R; *data++ = color.G; *data++ = color.B; *data++ = color.A; } } } }; #endif // INCLUDED_HIERPATHFINDER