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