Index: ps/trunk/source/graphics/TerritoryTexture.cpp
===================================================================
--- ps/trunk/source/graphics/TerritoryTexture.cpp (revision 25359)
+++ ps/trunk/source/graphics/TerritoryTexture.cpp (revision 25360)
@@ -1,256 +1,256 @@
-/* Copyright (C) 2019 Wildfire Games.
+/* Copyright (C) 2021 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 "TerritoryTexture.h"
#include "graphics/Color.h"
#include "graphics/Terrain.h"
#include "lib/bits.h"
#include "ps/Profile.h"
#include "renderer/Renderer.h"
#include "simulation2/Simulation2.h"
#include "simulation2/helpers/Grid.h"
#include "simulation2/helpers/Pathfinding.h"
#include "simulation2/components/ICmpPlayer.h"
#include "simulation2/components/ICmpPlayerManager.h"
#include "simulation2/components/ICmpTerrain.h"
#include "simulation2/components/ICmpTerritoryManager.h"
// TODO: There's a lot of duplication with CLOSTexture - might be nice to refactor a bit
CTerritoryTexture::CTerritoryTexture(CSimulation2& simulation) :
m_Simulation(simulation), m_DirtyID(0), m_Texture(0), m_MapSize(0), m_TextureSize(0)
{
}
CTerritoryTexture::~CTerritoryTexture()
{
if (m_Texture)
DeleteTexture();
}
void CTerritoryTexture::DeleteTexture()
{
glDeleteTextures(1, &m_Texture);
m_Texture = 0;
}
bool CTerritoryTexture::UpdateDirty()
{
CmpPtr cmpTerritoryManager(m_Simulation, SYSTEM_ENTITY);
return cmpTerritoryManager && cmpTerritoryManager->NeedUpdateTexture(&m_DirtyID);
}
void CTerritoryTexture::BindTexture(int unit)
{
if (UpdateDirty())
RecomputeTexture(unit);
g_Renderer.BindTexture(unit, m_Texture);
}
GLuint CTerritoryTexture::GetTexture()
{
if (UpdateDirty())
RecomputeTexture(0);
return m_Texture;
}
const float* CTerritoryTexture::GetTextureMatrix()
{
ENSURE(!UpdateDirty());
return &m_TextureMatrix._11;
}
const CMatrix3D* CTerritoryTexture::GetMinimapTextureMatrix()
{
ENSURE(!UpdateDirty());
return &m_MinimapTextureMatrix;
}
void CTerritoryTexture::ConstructTexture(int unit)
{
CmpPtr cmpTerrain(m_Simulation, SYSTEM_ENTITY);
if (!cmpTerrain)
return;
// Convert size from terrain tiles to territory tiles
- m_MapSize = cmpTerrain->GetTilesPerSide() * Pathfinding::NAVCELLS_PER_TILE / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE;
+ m_MapSize = cmpTerrain->GetMapSize() * Pathfinding::NAVCELL_SIZE_INT / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE;
m_TextureSize = (GLsizei)round_up_to_pow2((size_t)m_MapSize);
glGenTextures(1, &m_Texture);
g_Renderer.BindTexture(unit, m_Texture);
// Initialise texture with transparency, for the areas we don't
// overwrite with glTexSubImage2D later
u8* texData = new u8[m_TextureSize * m_TextureSize * 4];
memset(texData, 0x00, m_TextureSize * m_TextureSize * 4);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, m_TextureSize, m_TextureSize, 0, GL_RGBA, GL_UNSIGNED_BYTE, texData);
delete[] texData;
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_EDGE);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
{
// Texture matrix: We want to map
// world pos (0, y, 0) (i.e. bottom-left of first tile)
// onto texcoord (0, 0) (i.e. bottom-left of first texel);
// world pos (mapsize*cellsize, y, mapsize*cellsize) (i.e. top-right of last tile)
// onto texcoord (mapsize / texsize, mapsize / texsize) (i.e. top-right of last texel)
float s = 1.f / (float)(m_TextureSize * TERRAIN_TILE_SIZE);
float t = 0.f;
m_TextureMatrix.SetZero();
m_TextureMatrix._11 = s;
m_TextureMatrix._23 = s;
m_TextureMatrix._14 = t;
m_TextureMatrix._24 = t;
m_TextureMatrix._44 = 1;
}
{
// Minimap matrix: We want to map UV (0,0)-(1,1) onto (0,0)-(mapsize/texsize, mapsize/texsize)
float s = m_MapSize / (float)m_TextureSize;
m_MinimapTextureMatrix.SetZero();
m_MinimapTextureMatrix._11 = s;
m_MinimapTextureMatrix._22 = s;
m_MinimapTextureMatrix._44 = 1;
}
}
void CTerritoryTexture::RecomputeTexture(int unit)
{
// If the map was resized, delete and regenerate the texture
if (m_Texture)
{
CmpPtr cmpTerrain(m_Simulation, SYSTEM_ENTITY);
if (cmpTerrain && m_MapSize != (ssize_t)cmpTerrain->GetVerticesPerSide())
DeleteTexture();
}
if (!m_Texture)
ConstructTexture(unit);
PROFILE("recompute territory texture");
CmpPtr cmpTerritoryManager(m_Simulation, SYSTEM_ENTITY);
if (!cmpTerritoryManager)
return;
std::vector bitmap(m_MapSize * m_MapSize * 4);
GenerateBitmap(cmpTerritoryManager->GetTerritoryGrid(), &bitmap[0], m_MapSize, m_MapSize);
g_Renderer.BindTexture(unit, m_Texture);
glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, m_MapSize, m_MapSize, GL_RGBA, GL_UNSIGNED_BYTE, &bitmap[0]);
}
void CTerritoryTexture::GenerateBitmap(const Grid& territories, u8* bitmap, ssize_t w, ssize_t h)
{
int alphaMax = 0xC0;
int alphaFalloff = 0x20;
CmpPtr cmpPlayerManager(m_Simulation, SYSTEM_ENTITY);
std::vector colors;
i32 numPlayers = cmpPlayerManager->GetNumPlayers();
for (i32 p = 0; p < numPlayers; ++p)
{
CColor color(1, 0, 1, 1);
CmpPtr cmpPlayer(m_Simulation, cmpPlayerManager->GetPlayerByID(p));
if (cmpPlayer)
color = cmpPlayer->GetDisplayedColor();
colors.push_back(color);
}
u8* p = bitmap;
for (ssize_t j = 0; j < h; ++j)
for (ssize_t i = 0; i < w; ++i)
{
u8 val = territories.get(i, j) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK;
CColor color(1, 0, 1, 1);
if (val < colors.size())
color = colors[val];
*p++ = (int)(color.r * 255.f);
*p++ = (int)(color.g * 255.f);
*p++ = (int)(color.b * 255.f);
// Use alphaMax for borders and gaia territory; these tiles will be deleted later
if (val == 0 ||
(i > 0 && (territories.get(i-1, j) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK) != val) ||
(i < w-1 && (territories.get(i+1, j) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK) != val) ||
(j > 0 && (territories.get(i, j-1) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK) != val) ||
(j < h-1 && (territories.get(i, j+1) & ICmpTerritoryManager::TERRITORY_PLAYER_MASK) != val))
*p++ = alphaMax;
else
*p++ = 0x00;
}
// Do a low-quality cheap blur effect
for (ssize_t j = 0; j < h; ++j)
{
int a;
a = 0;
for (ssize_t i = 0; i < w; ++i)
{
a = std::max(a - alphaFalloff, (int)bitmap[(j*w+i)*4 + 3]);
bitmap[(j*w+i)*4 + 3] = a;
}
a = 0;
for (ssize_t i = w-1; i >= 0; --i)
{
a = std::max(a - alphaFalloff, (int)bitmap[(j*w+i)*4 + 3]);
bitmap[(j*w+i)*4 + 3] = a;
}
}
for (ssize_t i = 0; i < w; ++i)
{
int a;
a = 0;
for (ssize_t j = 0; j < w; ++j)
{
a = std::max(a - alphaFalloff, (int)bitmap[(j*w+i)*4 + 3]);
bitmap[(j*w+i)*4 + 3] = a;
}
a = 0;
for (ssize_t j = w-1; j >= 0; --j)
{
a = std::max(a - alphaFalloff, (int)bitmap[(j*w+i)*4 + 3]);
bitmap[(j*w+i)*4 + 3] = a;
}
}
// Add a gap between the boundaries, by deleting the max-alpha tiles
for (ssize_t j = 0; j < h; ++j)
for (ssize_t i = 0; i < w; ++i)
if (bitmap[(j*w+i)*4 + 3] == alphaMax)
bitmap[(j*w+i)*4 + 3] = 0;
}
Index: ps/trunk/source/maths/Fixed.h
===================================================================
--- ps/trunk/source/maths/Fixed.h (revision 25359)
+++ ps/trunk/source/maths/Fixed.h (revision 25360)
@@ -1,396 +1,396 @@
-/* Copyright (C) 2020 Wildfire Games.
+/* Copyright (C) 2021 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_FIXED
#define INCLUDED_FIXED
#include "lib/types.h"
#include "maths/Sqrt.h"
class CStr8;
class CStrW;
#ifndef NDEBUG
#define USE_FIXED_OVERFLOW_CHECKS
#endif
#if MSC_VERSION
// i32*i32 -> i64 multiply: MSVC x86 doesn't optimise i64 multiplies automatically, so use the intrinsic
#include
#define MUL_I64_I32_I32(a, b)\
(__emul((a), (b)))
#define SQUARE_U64_FIXED(a)\
static_cast(__emul((a).GetInternalValue(), (a).GetInternalValue()))
#else
#define MUL_I64_I32_I32(a, b)\
static_cast(a) * static_cast(b)
#define SQUARE_U64_FIXED(a)\
static_cast(static_cast((a).GetInternalValue()) * static_cast((a).GetInternalValue()))
#endif
//define overflow macros
#ifndef USE_FIXED_OVERFLOW_CHECKS
#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning)
#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning)
#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning)
#define CheckU32CastOverflow(var, targetType, overflowWarning)
#define CheckUnsignedAdditionOverflow(result, operand, overflowWarning)
#define CheckUnsignedSubtractionOverflow(result, operand, overflowWarning)
#define CheckNegationOverflow(var, type, overflowWarning)
#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning)
#define CheckDivisionOverflow(type, left, right, overflowWarning)
#else // USE_FIXED_OVERFLOW_CHECKS
#define CheckSignedSubtractionOverflow(type, left, right, overflowWarning, underflowWarning) \
if(left > 0 && right < 0 && left > std::numeric_limits::max() + right) \
debug_warn(overflowWarning); \
else if(left < 0 && right > 0 && left < std::numeric_limits::min() + right) \
debug_warn(underflowWarning);
#define CheckSignedAdditionOverflow(type, left, right, overflowWarning, underflowWarning) \
if(left > 0 && right > 0 && std::numeric_limits::max() - left < right) \
debug_warn(overflowWarning); \
else if(left < 0 && right < 0 && std::numeric_limits::min() - left > right) \
debug_warn(underflowWarning);
#define CheckCastOverflow(var, targetType, overflowWarning, underflowWarning) \
if(var > std::numeric_limits::max()) \
debug_warn(overflowWarning); \
else if(var < std::numeric_limits::min()) \
debug_warn(underflowWarning);
#define CheckU32CastOverflow(var, targetType, overflowWarning) \
if(var > (u32)std::numeric_limits::max()) \
debug_warn(overflowWarning);
#define CheckUnsignedAdditionOverflow(result, operand, overflowWarning) \
if(result < operand) \
debug_warn(overflowWarning);
#define CheckUnsignedSubtractionOverflow(result, left, overflowWarning) \
if(result > left) \
debug_warn(overflowWarning);
#define CheckNegationOverflow(var, type, overflowWarning) \
if(value == std::numeric_limits::min()) \
debug_warn(overflowWarning);
#define CheckMultiplicationOverflow(type, left, right, overflowWarning, underflowWarning) \
i64 res##left = (i64)left * (i64)right; \
CheckCastOverflow(res##left, type, overflowWarning, underflowWarning)
#define CheckDivisionOverflow(type, left, right, overflowWarning) \
if(right == -1) { CheckNegationOverflow(left, type, overflowWarning) }
#endif // USE_FIXED_OVERFLOW_CHECKS
template
inline T round_away_from_zero(float value)
{
return (T)(value >= 0 ? value + 0.5f : value - 0.5f);
}
template
inline T round_away_from_zero(double value)
{
return (T)(value >= 0 ? value + 0.5 : value - 0.5);
}
/**
* A simple fixed-point number class.
*
* Use 'fixed' rather than using this class directly.
*/
template
class CFixed
{
private:
T value;
- explicit CFixed(T v) : value(v) { }
+ constexpr explicit CFixed(T v) : value(v) { }
public:
enum { fract_bits = fract_bits_ };
CFixed() : value(0) { }
static CFixed Zero() { return CFixed(0); }
static CFixed Epsilon() { return CFixed(1); }
static CFixed Pi();
T GetInternalValue() const { return value; }
void SetInternalValue(T n) { value = n; }
// Conversion to/from primitive types:
- static CFixed FromInt(int n)
+ static constexpr CFixed FromInt(int n)
{
return CFixed(n << fract_bits);
}
- static CFixed FromFloat(float n)
+ static constexpr CFixed FromFloat(float n)
{
if (!std::isfinite(n))
return CFixed(0);
float scaled = n * fract_pow2;
return CFixed(round_away_from_zero(scaled));
}
- static CFixed FromDouble(double n)
+ static constexpr CFixed FromDouble(double n)
{
if (!std::isfinite(n))
return CFixed(0);
double scaled = n * fract_pow2;
return CFixed(round_away_from_zero(scaled));
}
static CFixed FromString(const CStr8& s);
static CFixed FromString(const CStrW& s);
/// Convert to float. May be lossy - float can't represent all values.
float ToFloat() const
{
return (float)value / (float)fract_pow2;
}
/// Convert to double. Won't be lossy - double can precisely represent all values.
double ToDouble() const
{
return value / (double)fract_pow2;
}
- int ToInt_RoundToZero() const
+ constexpr int ToInt_RoundToZero() const
{
if (value > 0)
return value >> fract_bits;
else
return (value + fract_pow2 - 1) >> fract_bits;
}
- int ToInt_RoundToInfinity() const
+ constexpr int ToInt_RoundToInfinity() const
{
return (value + fract_pow2 - 1) >> fract_bits;
}
- int ToInt_RoundToNegInfinity() const
+ constexpr int ToInt_RoundToNegInfinity() const
{
return value >> fract_bits;
}
- int ToInt_RoundToNearest() const // (ties to infinity)
+ constexpr int ToInt_RoundToNearest() const // (ties to infinity)
{
return (value + fract_pow2/2) >> fract_bits;
}
/// Returns the shortest string such that FromString will parse to the correct value.
CStr8 ToString() const;
/// Returns true if the number is precisely 0.
- bool IsZero() const { return value == 0; }
+ constexpr bool IsZero() const { return value == 0; }
/// Equality.
- bool operator==(CFixed n) const { return (value == n.value); }
+ constexpr bool operator==(CFixed n) const { return (value == n.value); }
/// Inequality.
- bool operator!=(CFixed n) const { return (value != n.value); }
+ constexpr bool operator!=(CFixed n) const { return (value != n.value); }
/// Numeric comparison.
- bool operator<=(CFixed n) const { return (value <= n.value); }
+ constexpr bool operator<=(CFixed n) const { return (value <= n.value); }
/// Numeric comparison.
- bool operator<(CFixed n) const { return (value < n.value); }
+ constexpr bool operator<(CFixed n) const { return (value < n.value); }
/// Numeric comparison.
- bool operator>=(CFixed n) const { return (value >= n.value); }
+ constexpr bool operator>=(CFixed n) const { return (value >= n.value); }
/// Numeric comparison.
- bool operator>(CFixed n) const { return (value > n.value); }
+ constexpr bool operator>(CFixed n) const { return (value > n.value); }
// Basic arithmetic:
/// Add a CFixed. Might overflow.
CFixed operator+(CFixed n) const
{
CheckSignedAdditionOverflow(T, value, n.value, L"Overflow in CFixed::operator+(CFixed n)", L"Underflow in CFixed::operator+(CFixed n)")
return CFixed(value + n.value);
}
/// Subtract a CFixed. Might overflow.
CFixed operator-(CFixed n) const
{
CheckSignedSubtractionOverflow(T, value, n.value, L"Overflow in CFixed::operator-(CFixed n)", L"Underflow in CFixed::operator-(CFixed n)")
return CFixed(value - n.value);
}
/// Add a CFixed. Might overflow.
- CFixed& operator+=(CFixed n) { *this = *this + n; return *this; }
+ constexpr CFixed& operator+=(CFixed n) { *this = *this + n; return *this; }
/// Subtract a CFixed. Might overflow.
- CFixed& operator-=(CFixed n) { *this = *this - n; return *this; }
+ constexpr CFixed& operator-=(CFixed n) { *this = *this - n; return *this; }
/// Negate a CFixed.
CFixed operator-() const
{
CheckNegationOverflow(value, T, L"Overflow in CFixed::operator-()")
return CFixed(-value);
}
CFixed operator>>(int n) const
{
ASSERT(n >= 0 && n < 32);
return CFixed(value >> n);
}
CFixed operator<<(int n) const
{
ASSERT(n >= 0 && n < 32);
// TODO: check for overflow
return CFixed(value << n);
}
/// Divide by a CFixed. Must not have n.IsZero(). Might overflow.
CFixed operator/(CFixed n) const
{
i64 t = (i64)value << fract_bits;
i64 result = t / (i64)n.value;
CheckCastOverflow(result, T, L"Overflow in CFixed::operator/(CFixed n)", L"Underflow in CFixed::operator/(CFixed n)")
return CFixed((T)result);
}
/// Multiply by an integer. Might overflow.
CFixed operator*(int n) const
{
CheckMultiplicationOverflow(T, value, n, L"Overflow in CFixed::operator*(int n)", L"Underflow in CFixed::operator*(int n)")
return CFixed(value * n);
}
/// Multiply by an integer. Avoids overflow by clamping to min/max representable value.
- CFixed MultiplyClamp(int n) const
+ constexpr CFixed MultiplyClamp(int n) const
{
i64 t = (i64)value * n;
t = std::max((i64)std::numeric_limits::min(), std::min((i64)std::numeric_limits::max(), t));
return CFixed((i32)t);
}
/// Divide by an integer. Must not have n == 0. Cannot overflow unless n == -1.
CFixed operator/(int n) const
{
CheckDivisionOverflow(T, value, n, L"Overflow in CFixed::operator/(int n)")
return CFixed(value / n);
}
/// Mod by a fixed. Must not have n == 0. Result has the same sign as n.
- CFixed operator%(CFixed n) const
+ constexpr CFixed operator%(CFixed n) const
{
T t = value % n.value;
if (n.value > 0 && t < 0)
t += n.value;
else if (n.value < 0 && t > 0)
t += n.value;
return CFixed(t);
}
- CFixed Absolute() const { return CFixed(abs(value)); }
+ constexpr CFixed Absolute() const { return CFixed(abs(value)); }
/**
* Multiply by a CFixed. Likely to overflow if both numbers are large,
* so we use an ugly name instead of operator* to make it obvious.
*/
CFixed Multiply(CFixed n) const
{
i64 t = MUL_I64_I32_I32(value, n.value);
t >>= fract_bits;
CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
return CFixed((T)t);
}
/**
* Multiply the value by itself. Might overflow.
*/
- CFixed Square() const
+ constexpr CFixed Square() const
{
return (*this).Multiply(*this);
}
/**
* Compute this*m/d. Must not have d == 0. Won't overflow if the result can be represented as a CFixed.
*/
CFixed MulDiv(CFixed m, CFixed d) const
{
i64 t = MUL_I64_I32_I32(value, m.value) / static_cast(d.value);
CheckCastOverflow(t, T, L"Overflow in CFixed::Multiply(CFixed n)", L"Underflow in CFixed::Multiply(CFixed n)")
return CFixed((T)t);
}
- CFixed Sqrt() const
+ constexpr CFixed Sqrt() const
{
if (value <= 0)
return CFixed(0);
u32 s = isqrt64((u64)value << fract_bits);
return CFixed(s);
}
private:
// Prevent dangerous accidental implicit conversions of floats to ints in certain operations
CFixed operator*(float n) const;
CFixed operator/(float n) const;
};
/**
* A fixed-point number class with 1-bit sign, 15-bit integral part, 16-bit fractional part.
*/
typedef CFixed CFixed_15_16;
/**
* Default fixed-point type used by the engine.
*/
typedef CFixed_15_16 fixed;
namespace std
{
/**
* std::numeric_limits specialisation, currently just providing min and max
*/
template
struct numeric_limits >
{
typedef CFixed fixed;
public:
static const bool is_specialized = true;
static fixed min() throw() { fixed f; f.SetInternalValue(std::numeric_limits::min()); return f; }
static fixed max() throw() { fixed f; f.SetInternalValue(std::numeric_limits::max()); return f; }
};
}
/**
* Inaccurate approximation of atan2 over fixed-point numbers.
* Maximum error is almost 0.08 radians (4.5 degrees).
*/
CFixed_15_16 atan2_approx(CFixed_15_16 y, CFixed_15_16 x);
/**
* Compute sin(a) and cos(a).
* Maximum error for -2pi < a < 2pi is almost 0.0005.
*/
void sincos_approx(CFixed_15_16 a, CFixed_15_16& sin_out, CFixed_15_16& cos_out);
#endif // INCLUDED_FIXED
Index: ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp (revision 25359)
+++ ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp (revision 25360)
@@ -1,1350 +1,1346 @@
-/* Copyright (C) 2020 Wildfire Games.
+/* Copyright (C) 2021 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 "ICmpObstructionManager.h"
-#include "ICmpTerrain.h"
#include "ICmpPosition.h"
#include "simulation2/MessageTypes.h"
#include "simulation2/helpers/Geometry.h"
#include "simulation2/helpers/Grid.h"
#include "simulation2/helpers/Rasterize.h"
#include "simulation2/helpers/Render.h"
#include "simulation2/helpers/Spatial.h"
#include "simulation2/serialization/SerializedTypes.h"
#include "graphics/Overlay.h"
-#include "graphics/Terrain.h"
#include "maths/MathUtil.h"
#include "ps/Profile.h"
#include "renderer/Scene.h"
#include "ps/CLogger.h"
// Externally, tags are opaque non-zero positive integers.
// Internally, they are tagged (by shape) indexes into shape lists.
// idx must be non-zero.
#define TAG_IS_VALID(tag) ((tag).valid())
#define TAG_IS_UNIT(tag) (((tag).n & 1) == 0)
#define TAG_IS_STATIC(tag) (((tag).n & 1) == 1)
#define UNIT_INDEX_TO_TAG(idx) tag_t(((idx) << 1) | 0)
#define STATIC_INDEX_TO_TAG(idx) tag_t(((idx) << 1) | 1)
#define TAG_TO_INDEX(tag) ((tag).n >> 1)
+namespace
+{
+/**
+ * Size of each obstruction subdivision square.
+ * TODO: find the optimal number instead of blindly guessing.
+ */
+constexpr entity_pos_t OBSTRUCTION_SUBDIVISION_SIZE = entity_pos_t::FromInt(32);
+
/**
* Internal representation of axis-aligned circular shapes for moving units
*/
struct UnitShape
{
entity_id_t entity;
entity_pos_t x, z;
entity_pos_t clearance;
ICmpObstructionManager::flags_t flags;
entity_id_t group; // control group (typically the owner entity, or a formation controller entity) (units ignore collisions with others in the same group)
};
/**
* Internal representation of arbitrary-rotation static square shapes for buildings
*/
struct StaticShape
{
entity_id_t entity;
entity_pos_t x, z; // world-space coordinates
CFixedVector2D u, v; // orthogonal unit vectors - axes of local coordinate space
entity_pos_t hw, hh; // half width/height in local coordinate space
ICmpObstructionManager::flags_t flags;
entity_id_t group;
entity_id_t group2;
};
-
+} // anonymous namespace
/**
* Serialization helper template for UnitShape
*/
template<>
struct SerializeHelper
{
template
void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify value) const
{
serialize.NumberU32_Unbounded("entity", value.entity);
serialize.NumberFixed_Unbounded("x", value.x);
serialize.NumberFixed_Unbounded("z", value.z);
serialize.NumberFixed_Unbounded("clearance", value.clearance);
serialize.NumberU8_Unbounded("flags", value.flags);
serialize.NumberU32_Unbounded("group", value.group);
}
};
/**
* Serialization helper template for StaticShape
*/
template<>
struct SerializeHelper
{
template
void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify value) const
{
serialize.NumberU32_Unbounded("entity", value.entity);
serialize.NumberFixed_Unbounded("x", value.x);
serialize.NumberFixed_Unbounded("z", value.z);
serialize.NumberFixed_Unbounded("u.x", value.u.X);
serialize.NumberFixed_Unbounded("u.y", value.u.Y);
serialize.NumberFixed_Unbounded("v.x", value.v.X);
serialize.NumberFixed_Unbounded("v.y", value.v.Y);
serialize.NumberFixed_Unbounded("hw", value.hw);
serialize.NumberFixed_Unbounded("hh", value.hh);
serialize.NumberU8_Unbounded("flags", value.flags);
serialize.NumberU32_Unbounded("group", value.group);
serialize.NumberU32_Unbounded("group2", value.group2);
}
};
class CCmpObstructionManager : public ICmpObstructionManager
{
public:
static void ClassInit(CComponentManager& componentManager)
{
componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
}
DEFAULT_COMPONENT_ALLOCATOR(ObstructionManager)
bool m_DebugOverlayEnabled;
bool m_DebugOverlayDirty;
std::vector m_DebugOverlayLines;
SpatialSubdivision m_UnitSubdivision;
SpatialSubdivision m_StaticSubdivision;
// TODO: using std::map is a bit inefficient; is there a better way to store these?
std::map m_UnitShapes;
std::map m_StaticShapes;
u32 m_UnitShapeNext; // next allocated id
u32 m_StaticShapeNext;
entity_pos_t m_MaxClearance;
bool m_PassabilityCircular;
entity_pos_t m_WorldX0;
entity_pos_t m_WorldZ0;
entity_pos_t m_WorldX1;
entity_pos_t m_WorldZ1;
- u16 m_TerrainTiles;
static std::string GetSchema()
{
return "";
}
virtual void Init(const CParamNode& UNUSED(paramNode))
{
m_DebugOverlayEnabled = false;
m_DebugOverlayDirty = true;
m_UnitShapeNext = 1;
m_StaticShapeNext = 1;
m_UpdateInformations.dirty = true;
m_UpdateInformations.globallyDirty = true;
m_PassabilityCircular = false;
m_WorldX0 = m_WorldZ0 = m_WorldX1 = m_WorldZ1 = entity_pos_t::Zero();
- m_TerrainTiles = 0;
// Initialise with bogus values (these will get replaced when
// SetBounds is called)
ResetSubdivisions(entity_pos_t::FromInt(1024), entity_pos_t::FromInt(1024));
}
virtual void Deinit()
{
}
template
void SerializeCommon(S& serialize)
{
Serializer(serialize, "unit subdiv", m_UnitSubdivision);
Serializer(serialize, "static subdiv", m_StaticSubdivision);
serialize.NumberFixed_Unbounded("max clearance", m_MaxClearance);
Serializer(serialize, "unit shapes", m_UnitShapes);
Serializer(serialize, "static shapes", m_StaticShapes);
serialize.NumberU32_Unbounded("unit shape next", m_UnitShapeNext);
serialize.NumberU32_Unbounded("static shape next", m_StaticShapeNext);
serialize.Bool("circular", m_PassabilityCircular);
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.NumberU16_Unbounded("terrain tiles", m_TerrainTiles);
}
virtual void Serialize(ISerializer& serialize)
{
// TODO: this could perhaps be optimised by not storing all the obstructions,
// and instead regenerating them from the other entities on Deserialize
SerializeCommon(serialize);
}
virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
{
Init(paramNode);
SerializeCommon(deserialize);
- m_UpdateInformations.dirtinessGrid = Grid(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE);
+ i32 size = ((m_WorldX1-m_WorldX0)/Pathfinding::NAVCELL_SIZE_INT).ToInt_RoundToInfinity();
+ m_UpdateInformations.dirtinessGrid = Grid(size, size);
}
virtual void HandleMessage(const CMessage& msg, bool UNUSED(global))
{
switch (msg.GetType())
{
case MT_RenderSubmit:
{
const CMessageRenderSubmit& msgData = static_cast (msg);
RenderSubmit(msgData.collector);
break;
}
}
}
// NB: on deserialization, this function is not called after the component is reset.
// So anything that happens here should be safely serialized.
virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1)
{
m_WorldX0 = x0;
m_WorldZ0 = z0;
m_WorldX1 = x1;
m_WorldZ1 = z1;
MakeDirtyAll();
// Subdivision system bounds:
ENSURE(x0.IsZero() && z0.IsZero()); // don't bother implementing non-zero offsets yet
ResetSubdivisions(x1, z1);
- CmpPtr cmpTerrain(GetSystemEntity());
- if (!cmpTerrain)
- return;
-
- m_TerrainTiles = cmpTerrain->GetTilesPerSide();
- m_UpdateInformations.dirtinessGrid = Grid(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE);
+ i32 size = ((m_WorldX1-m_WorldX0)/Pathfinding::NAVCELL_SIZE_INT).ToInt_RoundToInfinity();
+ m_UpdateInformations.dirtinessGrid = Grid(size, size);
CmpPtr cmpPathfinder(GetSystemEntity());
if (cmpPathfinder)
m_MaxClearance = cmpPathfinder->GetMaximumClearance();
}
void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1)
{
- // Use 8x8 tile subdivisions
- // (TODO: find the optimal number instead of blindly guessing)
- m_UnitSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE));
- m_StaticSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE));
+ m_UnitSubdivision.Reset(x1, z1, OBSTRUCTION_SUBDIVISION_SIZE);
+ m_StaticSubdivision.Reset(x1, z1, OBSTRUCTION_SUBDIVISION_SIZE);
for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it)
{
CFixedVector2D center(it->second.x, it->second.z);
CFixedVector2D halfSize(it->second.clearance, it->second.clearance);
m_UnitSubdivision.Add(it->first, center - halfSize, center + halfSize);
}
for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it)
{
CFixedVector2D center(it->second.x, it->second.z);
CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(it->second.u, it->second.v, CFixedVector2D(it->second.hw, it->second.hh));
m_StaticSubdivision.Add(it->first, center - bbHalfSize, center + bbHalfSize);
}
}
virtual tag_t AddUnitShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, flags_t flags, entity_id_t group)
{
UnitShape shape = { ent, x, z, clearance, flags, group };
u32 id = m_UnitShapeNext++;
m_UnitShapes[id] = shape;
m_UnitSubdivision.Add(id, CFixedVector2D(x - clearance, z - clearance), CFixedVector2D(x + clearance, z + clearance));
MakeDirtyUnit(flags, id, shape);
return UNIT_INDEX_TO_TAG(id);
}
virtual tag_t AddStaticShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h, flags_t flags, entity_id_t group, entity_id_t group2 /* = INVALID_ENTITY */)
{
fixed s, c;
sincos_approx(a, s, c);
CFixedVector2D u(c, -s);
CFixedVector2D v(s, c);
StaticShape shape = { ent, x, z, u, v, w/2, h/2, flags, group, group2 };
u32 id = m_StaticShapeNext++;
m_StaticShapes[id] = shape;
CFixedVector2D center(x, z);
CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(w/2, h/2));
m_StaticSubdivision.Add(id, center - bbHalfSize, center + bbHalfSize);
MakeDirtyStatic(flags, id, shape);
return STATIC_INDEX_TO_TAG(id);
}
virtual ObstructionSquare GetUnitShapeObstruction(entity_pos_t x, entity_pos_t z, entity_pos_t clearance) const
{
CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero());
CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1));
ObstructionSquare o = { x, z, u, v, clearance, clearance };
return o;
}
virtual ObstructionSquare GetStaticShapeObstruction(entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h) const
{
fixed s, c;
sincos_approx(a, s, c);
CFixedVector2D u(c, -s);
CFixedVector2D v(s, c);
ObstructionSquare o = { x, z, u, v, w/2, h/2 };
return o;
}
virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a)
{
ENSURE(TAG_IS_VALID(tag));
if (TAG_IS_UNIT(tag))
{
UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region
m_UnitSubdivision.Move(TAG_TO_INDEX(tag),
CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance),
CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance),
CFixedVector2D(x - shape.clearance, z - shape.clearance),
CFixedVector2D(x + shape.clearance, z + shape.clearance));
shape.x = x;
shape.z = z;
MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the new shape region
}
else
{
fixed s, c;
sincos_approx(a, s, c);
CFixedVector2D u(c, -s);
CFixedVector2D v(s, c);
StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)];
MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region
CFixedVector2D fromBbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh));
CFixedVector2D toBbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(shape.hw, shape.hh));
m_StaticSubdivision.Move(TAG_TO_INDEX(tag),
CFixedVector2D(shape.x, shape.z) - fromBbHalfSize,
CFixedVector2D(shape.x, shape.z) + fromBbHalfSize,
CFixedVector2D(x, z) - toBbHalfSize,
CFixedVector2D(x, z) + toBbHalfSize);
shape.x = x;
shape.z = z;
shape.u = u;
shape.v = v;
MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the new shape region
}
}
virtual void SetUnitMovingFlag(tag_t tag, bool moving)
{
ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag));
if (TAG_IS_UNIT(tag))
{
UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
if (moving)
shape.flags |= FLAG_MOVING;
else
shape.flags &= (flags_t)~FLAG_MOVING;
MakeDirtyDebug();
}
}
virtual void SetUnitControlGroup(tag_t tag, entity_id_t group)
{
ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag));
if (TAG_IS_UNIT(tag))
{
UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
shape.group = group;
}
}
virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2)
{
ENSURE(TAG_IS_VALID(tag) && TAG_IS_STATIC(tag));
if (TAG_IS_STATIC(tag))
{
StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)];
shape.group = group;
shape.group2 = group2;
}
}
virtual void RemoveShape(tag_t tag)
{
ENSURE(TAG_IS_VALID(tag));
if (TAG_IS_UNIT(tag))
{
UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)];
m_UnitSubdivision.Remove(TAG_TO_INDEX(tag),
CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance),
CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance));
MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape);
m_UnitShapes.erase(TAG_TO_INDEX(tag));
}
else
{
StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)];
CFixedVector2D center(shape.x, shape.z);
CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh));
m_StaticSubdivision.Remove(TAG_TO_INDEX(tag), center - bbHalfSize, center + bbHalfSize);
MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape);
m_StaticShapes.erase(TAG_TO_INDEX(tag));
}
}
virtual ObstructionSquare GetObstruction(tag_t tag) const
{
ENSURE(TAG_IS_VALID(tag));
if (TAG_IS_UNIT(tag))
{
const UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag));
CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero());
CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1));
ObstructionSquare o = { shape.x, shape.z, u, v, shape.clearance, shape.clearance };
return o;
}
else
{
const StaticShape& shape = m_StaticShapes.at(TAG_TO_INDEX(tag));
ObstructionSquare o = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh };
return o;
}
}
virtual fixed DistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const;
virtual fixed MaxDistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const;
virtual fixed DistanceToTarget(entity_id_t ent, entity_id_t target) const;
virtual fixed MaxDistanceToTarget(entity_id_t ent, entity_id_t target) const;
virtual fixed DistanceBetweenShapes(const ObstructionSquare& source, const ObstructionSquare& target) const;
virtual fixed MaxDistanceBetweenShapes(const ObstructionSquare& source, const ObstructionSquare& target) const;
virtual bool IsInPointRange(entity_id_t ent, entity_pos_t px, entity_pos_t pz, entity_pos_t minRange, entity_pos_t maxRange, bool opposite) const;
virtual bool IsInTargetRange(entity_id_t ent, entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange, bool opposite) const;
virtual bool IsPointInPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t px, entity_pos_t pz, entity_pos_t minRange, entity_pos_t maxRange) const;
virtual bool AreShapesInRange(const ObstructionSquare& source, const ObstructionSquare& target, entity_pos_t minRange, entity_pos_t maxRange, bool opposite) const;
virtual bool TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits = false) const;
virtual bool TestStaticShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, std::vector* out) const;
virtual bool TestUnitShape(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, std::vector* out) const;
virtual void Rasterize(Grid& grid, const std::vector& passClasses, bool fullUpdate);
virtual void GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const;
virtual void GetUnitObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const;
virtual void GetStaticObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const;
virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false) const;
virtual void GetStaticObstructionsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const;
virtual void SetPassabilityCircular(bool enabled)
{
m_PassabilityCircular = enabled;
MakeDirtyAll();
CMessageObstructionMapShapeChanged msg;
GetSimContext().GetComponentManager().BroadcastMessage(msg);
}
virtual bool GetPassabilityCircular() const
{
return m_PassabilityCircular;
}
virtual void SetDebugOverlay(bool enabled)
{
m_DebugOverlayEnabled = enabled;
m_DebugOverlayDirty = true;
if (!enabled)
m_DebugOverlayLines.clear();
}
void RenderSubmit(SceneCollector& collector);
virtual void UpdateInformations(GridUpdateInformation& informations)
{
if (!m_UpdateInformations.dirtinessGrid.blank())
informations.MergeAndClear(m_UpdateInformations);
}
private:
// Dynamic updates for the long-range pathfinder
GridUpdateInformation m_UpdateInformations;
// These vectors might contain shapes that were deleted
std::vector m_DirtyStaticShapes;
std::vector m_DirtyUnitShapes;
/**
* Mark all previous Rasterize()d grids as dirty, and the debug display.
* Call this when the world bounds have changed.
*/
void MakeDirtyAll()
{
m_UpdateInformations.dirty = true;
m_UpdateInformations.globallyDirty = true;
m_UpdateInformations.dirtinessGrid.reset();
m_DebugOverlayDirty = true;
}
/**
* Mark the debug display as dirty.
* Call this when nothing has changed except a unit's 'moving' flag.
*/
void MakeDirtyDebug()
{
m_DebugOverlayDirty = true;
}
inline void MarkDirtinessGrid(const entity_pos_t& x, const entity_pos_t& z, const entity_pos_t& r)
{
MarkDirtinessGrid(x, z, CFixedVector2D(r, r));
}
inline void MarkDirtinessGrid(const entity_pos_t& x, const entity_pos_t& z, const CFixedVector2D& hbox)
{
- ENSURE(m_UpdateInformations.dirtinessGrid.m_W == m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE &&
- m_UpdateInformations.dirtinessGrid.m_H == m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE);
- if (m_TerrainTiles == 0)
+ if (m_UpdateInformations.dirtinessGrid.m_W == 0)
return;
u16 j0, j1, i0, i1;
Pathfinding::NearestNavcell(x - hbox.X, z - hbox.Y, i0, j0, m_UpdateInformations.dirtinessGrid.m_W, m_UpdateInformations.dirtinessGrid.m_H);
Pathfinding::NearestNavcell(x + hbox.X, z + hbox.Y, i1, j1, m_UpdateInformations.dirtinessGrid.m_W, m_UpdateInformations.dirtinessGrid.m_H);
for (int j = j0; j < j1; ++j)
for (int i = i0; i < i1; ++i)
m_UpdateInformations.dirtinessGrid.set(i, j, 1);
}
/**
* Mark all previous Rasterize()d grids as dirty, if they depend on this shape.
* Call this when a static shape has changed.
*/
void MakeDirtyStatic(flags_t flags, u32 index, const StaticShape& shape)
{
m_DebugOverlayDirty = true;
if (flags & (FLAG_BLOCK_PATHFINDING | FLAG_BLOCK_FOUNDATION))
{
m_UpdateInformations.dirty = true;
if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), index) == m_DirtyStaticShapes.end())
m_DirtyStaticShapes.push_back(index);
// All shapes overlapping the updated part of the grid should be dirtied too.
// We are going to invalidate the region of the grid corresponding to the modified shape plus its clearance,
// and we need to get the shapes whose clearance can overlap this area. So we need to extend the search area
// by two times the maximum clearance.
CFixedVector2D center(shape.x, shape.z);
CFixedVector2D hbox = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh));
CFixedVector2D expand(m_MaxClearance, m_MaxClearance);
std::vector staticsNear;
m_StaticSubdivision.GetInRange(staticsNear, center - hbox - expand*2, center + hbox + expand*2);
for (u32& staticId : staticsNear)
if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end())
m_DirtyStaticShapes.push_back(staticId);
std::vector unitsNear;
m_UnitSubdivision.GetInRange(unitsNear, center - hbox - expand*2, center + hbox + expand*2);
for (u32& unitId : unitsNear)
if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end())
m_DirtyUnitShapes.push_back(unitId);
MarkDirtinessGrid(shape.x, shape.z, hbox + expand);
}
}
/**
* Mark all previous Rasterize()d grids as dirty, if they depend on this shape.
* Call this when a unit shape has changed.
*/
void MakeDirtyUnit(flags_t flags, u32 index, const UnitShape& shape)
{
m_DebugOverlayDirty = true;
if (flags & (FLAG_BLOCK_PATHFINDING | FLAG_BLOCK_FOUNDATION))
{
m_UpdateInformations.dirty = true;
if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), index) == m_DirtyUnitShapes.end())
m_DirtyUnitShapes.push_back(index);
// All shapes overlapping the updated part of the grid should be dirtied too.
// We are going to invalidate the region of the grid corresponding to the modified shape plus its clearance,
// and we need to get the shapes whose clearance can overlap this area. So we need to extend the search area
// by two times the maximum clearance.
CFixedVector2D center(shape.x, shape.z);
std::vector staticsNear;
m_StaticSubdivision.GetNear(staticsNear, center, shape.clearance + m_MaxClearance*2);
for (u32& staticId : staticsNear)
if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end())
m_DirtyStaticShapes.push_back(staticId);
std::vector unitsNear;
m_UnitSubdivision.GetNear(unitsNear, center, shape.clearance + m_MaxClearance*2);
for (u32& unitId : unitsNear)
if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end())
m_DirtyUnitShapes.push_back(unitId);
MarkDirtinessGrid(shape.x, shape.z, shape.clearance + m_MaxClearance);
}
}
/**
* Return whether the given point is within the world bounds by at least r
*/
inline bool IsInWorld(entity_pos_t x, entity_pos_t z, entity_pos_t r) const
{
return (m_WorldX0+r <= x && x <= m_WorldX1-r && m_WorldZ0+r <= z && z <= m_WorldZ1-r);
}
/**
* Return whether the given point is within the world bounds
*/
inline bool IsInWorld(const CFixedVector2D& p) const
{
return (m_WorldX0 <= p.X && p.X <= m_WorldX1 && m_WorldZ0 <= p.Y && p.Y <= m_WorldZ1);
}
void RasterizeHelper(Grid& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance = fixed::Zero()) const;
};
REGISTER_COMPONENT_TYPE(ObstructionManager)
/**
* DistanceTo function family, all end up in calculating a vector length, DistanceBetweenShapes or
* MaxDistanceBetweenShapes. The MaxFoo family calculates the opposite edge opposite edge distance.
* When the distance is undefined we return -1.
*/
fixed CCmpObstructionManager::DistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const
{
ObstructionSquare obstruction;
CmpPtr cmpObstruction(GetSimContext(), ent);
if (cmpObstruction && cmpObstruction->GetObstructionSquare(obstruction))
{
ObstructionSquare point;
point.x = px;
point.z = pz;
return DistanceBetweenShapes(obstruction, point);
}
CmpPtr cmpPosition(GetSimContext(), ent);
if (!cmpPosition || !cmpPosition->IsInWorld())
return fixed::FromInt(-1);
return (CFixedVector2D(cmpPosition->GetPosition2D().X, cmpPosition->GetPosition2D().Y) - CFixedVector2D(px, pz)).Length();
}
fixed CCmpObstructionManager::MaxDistanceToPoint(entity_id_t ent, entity_pos_t px, entity_pos_t pz) const
{
ObstructionSquare obstruction;
CmpPtr cmpObstruction(GetSimContext(), ent);
if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(obstruction))
{
ObstructionSquare point;
point.x = px;
point.z = pz;
return MaxDistanceBetweenShapes(obstruction, point);
}
CmpPtr cmpPosition(GetSimContext(), ent);
if (!cmpPosition || !cmpPosition->IsInWorld())
return fixed::FromInt(-1);
return (CFixedVector2D(cmpPosition->GetPosition2D().X, cmpPosition->GetPosition2D().Y) - CFixedVector2D(px, pz)).Length();
}
fixed CCmpObstructionManager::DistanceToTarget(entity_id_t ent, entity_id_t target) const
{
ObstructionSquare obstruction;
CmpPtr cmpObstruction(GetSimContext(), ent);
if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(obstruction))
{
CmpPtr cmpPosition(GetSimContext(), ent);
if (!cmpPosition || !cmpPosition->IsInWorld())
return fixed::FromInt(-1);
return DistanceToPoint(target, cmpPosition->GetPosition2D().X, cmpPosition->GetPosition2D().Y);
}
ObstructionSquare target_obstruction;
CmpPtr cmpObstructionTarget(GetSimContext(), target);
if (!cmpObstructionTarget || !cmpObstructionTarget->GetObstructionSquare(target_obstruction))
{
CmpPtr cmpPositionTarget(GetSimContext(), target);
if (!cmpPositionTarget || !cmpPositionTarget->IsInWorld())
return fixed::FromInt(-1);
return DistanceToPoint(ent, cmpPositionTarget->GetPosition2D().X, cmpPositionTarget->GetPosition2D().Y);
}
return DistanceBetweenShapes(obstruction, target_obstruction);
}
fixed CCmpObstructionManager::MaxDistanceToTarget(entity_id_t ent, entity_id_t target) const
{
ObstructionSquare obstruction;
CmpPtr cmpObstruction(GetSimContext(), ent);
if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(obstruction))
{
CmpPtr cmpPosition(GetSimContext(), ent);
if (!cmpPosition || !cmpPosition->IsInWorld())
return fixed::FromInt(-1);
return MaxDistanceToPoint(target, cmpPosition->GetPosition2D().X, cmpPosition->GetPosition2D().Y);
}
ObstructionSquare target_obstruction;
CmpPtr cmpObstructionTarget(GetSimContext(), target);
if (!cmpObstructionTarget || !cmpObstructionTarget->GetObstructionSquare(target_obstruction))
{
CmpPtr cmpPositionTarget(GetSimContext(), target);
if (!cmpPositionTarget || !cmpPositionTarget->IsInWorld())
return fixed::FromInt(-1);
return MaxDistanceToPoint(ent, cmpPositionTarget->GetPosition2D().X, cmpPositionTarget->GetPosition2D().Y);
}
return MaxDistanceBetweenShapes(obstruction, target_obstruction);
}
fixed CCmpObstructionManager::DistanceBetweenShapes(const ObstructionSquare& source, const ObstructionSquare& target) const
{
// Sphere-sphere collision.
if (source.hh == fixed::Zero() && target.hh == fixed::Zero())
return (CFixedVector2D(target.x, target.z) - CFixedVector2D(source.x, source.z)).Length() - source.hw - target.hw;
// Square to square.
if (source.hh != fixed::Zero() && target.hh != fixed::Zero())
return Geometry::DistanceSquareToSquare(
CFixedVector2D(target.x, target.z) - CFixedVector2D(source.x, source.z),
source.u, source.v, CFixedVector2D(source.hw, source.hh),
target.u, target.v, CFixedVector2D(target.hw, target.hh));
// To cover both remaining cases, shape a is the square one, shape b is the circular one.
const ObstructionSquare& a = source.hh == fixed::Zero() ? target : source;
const ObstructionSquare& b = source.hh == fixed::Zero() ? source : target;
return Geometry::DistanceToSquare(
CFixedVector2D(b.x, b.z) - CFixedVector2D(a.x, a.z),
a.u, a.v, CFixedVector2D(a.hw, a.hh), true) - b.hw;
}
fixed CCmpObstructionManager::MaxDistanceBetweenShapes(const ObstructionSquare& source, const ObstructionSquare& target) const
{
// Sphere-sphere collision.
if (source.hh == fixed::Zero() && target.hh == fixed::Zero())
return (CFixedVector2D(target.x, target.z) - CFixedVector2D(source.x, source.z)).Length() + source.hw + target.hw;
// Square to square.
if (source.hh != fixed::Zero() && target.hh != fixed::Zero())
return Geometry::MaxDistanceSquareToSquare(
CFixedVector2D(target.x, target.z) - CFixedVector2D(source.x, source.z),
source.u, source.v, CFixedVector2D(source.hw, source.hh),
target.u, target.v, CFixedVector2D(target.hw, target.hh));
// To cover both remaining cases, shape a is the square one, shape b is the circular one.
const ObstructionSquare& a = source.hh == fixed::Zero() ? target : source;
const ObstructionSquare& b = source.hh == fixed::Zero() ? source : target;
return Geometry::MaxDistanceToSquare(
CFixedVector2D(b.x, b.z) - CFixedVector2D(a.x, a.z),
a.u, a.v, CFixedVector2D(a.hw, a.hh), true) + b.hw;
}
/**
* IsInRange function family depending on the DistanceTo family.
*
* In range if the edge to edge distance is inferior to maxRange
* and if the opposite edge to opposite edge distance is greater than minRange when the opposite bool is true
* or when the opposite bool is false the edge to edge distance is more than minRange.
*
* Using the opposite egde for minRange means that a unit is in range of a building if it is farther than
* clearance-buildingsize, which is generally going to be negative (and thus this returns true).
* NB: from a game POV, this means units can easily fire on buildings, which is good,
* but it also means that buildings can easily fire on units. Buildings are usually meant
* to fire from the edge, not the opposite edge, so this looks odd. For this reason one can choose
* to set the opposite bool false and use the edge to egde distance.
*
* We don't use squares because the are likely to overflow.
* We use a 0.0001 margin to avoid rounding errors.
*/
bool CCmpObstructionManager::IsInPointRange(entity_id_t ent, entity_pos_t px, entity_pos_t pz, entity_pos_t minRange, entity_pos_t maxRange, bool opposite) const
{
fixed dist = DistanceToPoint(ent, px, pz);
// Treat -1 max range as infinite
return dist != fixed::FromInt(-1) &&
(dist <= (maxRange + fixed::FromFloat(0.0001f)) || maxRange < fixed::Zero()) &&
(opposite ? MaxDistanceToPoint(ent, px, pz) : dist) >= minRange - fixed::FromFloat(0.0001f);
}
bool CCmpObstructionManager::IsInTargetRange(entity_id_t ent, entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange, bool opposite) const
{
fixed dist = DistanceToTarget(ent, target);
// Treat -1 max range as infinite
return dist != fixed::FromInt(-1) &&
(dist <= (maxRange + fixed::FromFloat(0.0001f)) || maxRange < fixed::Zero()) &&
(opposite ? MaxDistanceToTarget(ent, target) : dist) >= minRange - fixed::FromFloat(0.0001f);
}
bool CCmpObstructionManager::IsPointInPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t px, entity_pos_t pz, entity_pos_t minRange, entity_pos_t maxRange) const
{
entity_pos_t distance = (CFixedVector2D(x, z) - CFixedVector2D(px, pz)).Length();
// Treat -1 max range as infinite
return (distance <= (maxRange + fixed::FromFloat(0.0001f)) || maxRange < fixed::Zero()) &&
distance >= minRange - fixed::FromFloat(0.0001f);
}
bool CCmpObstructionManager::AreShapesInRange(const ObstructionSquare& source, const ObstructionSquare& target, entity_pos_t minRange, entity_pos_t maxRange, bool opposite) const
{
fixed dist = DistanceBetweenShapes(source, target);
// Treat -1 max range as infinite
return dist != fixed::FromInt(-1) &&
(dist <= (maxRange + fixed::FromFloat(0.0001f)) || maxRange < fixed::Zero()) &&
(opposite ? MaxDistanceBetweenShapes(source, target) : dist) >= minRange - fixed::FromFloat(0.0001f);
}
bool CCmpObstructionManager::TestLine(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, bool relaxClearanceForUnits) const
{
PROFILE("TestLine");
// Check that both end points are within the world (which means the whole line must be)
if (!IsInWorld(x0, z0, r) || !IsInWorld(x1, z1, r))
return true;
CFixedVector2D posMin (std::min(x0, x1) - r, std::min(z0, z1) - r);
CFixedVector2D posMax (std::max(x0, x1) + r, std::max(z0, z1) + r);
// actual radius used for unit-unit collisions. If relaxClearanceForUnits, will be smaller to allow more overlap.
entity_pos_t unitUnitRadius = r;
if (relaxClearanceForUnits)
unitUnitRadius -= entity_pos_t::FromInt(1)/2;
std::vector unitShapes;
m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax);
for (const entity_id_t& shape : unitShapes)
{
std::map::const_iterator it = m_UnitShapes.find(shape);
ENSURE(it != m_UnitShapes.end());
if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
continue;
CFixedVector2D center(it->second.x, it->second.z);
CFixedVector2D halfSize(it->second.clearance + unitUnitRadius, it->second.clearance + unitUnitRadius);
if (Geometry::TestRayAASquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, halfSize))
return true;
}
std::vector staticShapes;
m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax);
for (const entity_id_t& shape : staticShapes)
{
std::map::const_iterator it = m_StaticShapes.find(shape);
ENSURE(it != m_StaticShapes.end());
if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
continue;
CFixedVector2D center(it->second.x, it->second.z);
CFixedVector2D halfSize(it->second.hw + r, it->second.hh + r);
if (Geometry::TestRaySquare(CFixedVector2D(x0, z0) - center, CFixedVector2D(x1, z1) - center, it->second.u, it->second.v, halfSize))
return true;
}
return false;
}
bool CCmpObstructionManager::TestStaticShape(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h,
std::vector* out) const
{
PROFILE("TestStaticShape");
if (out)
out->clear();
fixed s, c;
sincos_approx(a, s, c);
CFixedVector2D u(c, -s);
CFixedVector2D v(s, c);
CFixedVector2D center(x, z);
CFixedVector2D halfSize(w/2, h/2);
CFixedVector2D corner1 = u.Multiply(halfSize.X) + v.Multiply(halfSize.Y);
CFixedVector2D corner2 = u.Multiply(halfSize.X) - v.Multiply(halfSize.Y);
// Check that all corners are within the world (which means the whole shape must be)
if (!IsInWorld(center + corner1) || !IsInWorld(center + corner2) ||
!IsInWorld(center - corner1) || !IsInWorld(center - corner2))
{
if (out)
out->push_back(INVALID_ENTITY); // no entity ID, so just push an arbitrary marker
else
return true;
}
fixed bbHalfWidth = std::max(corner1.X.Absolute(), corner2.X.Absolute());
fixed bbHalfHeight = std::max(corner1.Y.Absolute(), corner2.Y.Absolute());
CFixedVector2D posMin(x - bbHalfWidth, z - bbHalfHeight);
CFixedVector2D posMax(x + bbHalfWidth, z + bbHalfHeight);
std::vector unitShapes;
m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax);
for (entity_id_t& shape : unitShapes)
{
std::map::const_iterator it = m_UnitShapes.find(shape);
ENSURE(it != m_UnitShapes.end());
if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
continue;
CFixedVector2D center1(it->second.x, it->second.z);
if (Geometry::PointIsInSquare(center1 - center, u, v, CFixedVector2D(halfSize.X + it->second.clearance, halfSize.Y + it->second.clearance)))
{
if (out)
out->push_back(it->second.entity);
else
return true;
}
}
std::vector staticShapes;
m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax);
for (entity_id_t& shape : staticShapes)
{
std::map::const_iterator it = m_StaticShapes.find(shape);
ENSURE(it != m_StaticShapes.end());
if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
continue;
CFixedVector2D center1(it->second.x, it->second.z);
CFixedVector2D halfSize1(it->second.hw, it->second.hh);
if (Geometry::TestSquareSquare(center, u, v, halfSize, center1, it->second.u, it->second.v, halfSize1))
{
if (out)
out->push_back(it->second.entity);
else
return true;
}
}
if (out)
return !out->empty(); // collided if the list isn't empty
else
return false; // didn't collide, if we got this far
}
bool CCmpObstructionManager::TestUnitShape(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t clearance,
std::vector* out) const
{
PROFILE("TestUnitShape");
// Check that the shape is within the world
if (!IsInWorld(x, z, clearance))
{
if (out)
out->push_back(INVALID_ENTITY); // no entity ID, so just push an arbitrary marker
else
return true;
}
CFixedVector2D center(x, z);
CFixedVector2D posMin(x - clearance, z - clearance);
CFixedVector2D posMax(x + clearance, z + clearance);
std::vector unitShapes;
m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax);
for (const entity_id_t& shape : unitShapes)
{
std::map::const_iterator it = m_UnitShapes.find(shape);
ENSURE(it != m_UnitShapes.end());
if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
continue;
entity_pos_t c1 = it->second.clearance;
if (!(
it->second.x + c1 < x - clearance ||
it->second.x - c1 > x + clearance ||
it->second.z + c1 < z - clearance ||
it->second.z - c1 > z + clearance))
{
if (out)
out->push_back(it->second.entity);
else
return true;
}
}
std::vector staticShapes;
m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax);
for (const entity_id_t& shape : staticShapes)
{
std::map::const_iterator it = m_StaticShapes.find(shape);
ENSURE(it != m_StaticShapes.end());
if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
continue;
CFixedVector2D center1(it->second.x, it->second.z);
if (Geometry::PointIsInSquare(center1 - center, it->second.u, it->second.v, CFixedVector2D(it->second.hw + clearance, it->second.hh + clearance)))
{
if (out)
out->push_back(it->second.entity);
else
return true;
}
}
if (out)
return !out->empty(); // collided if the list isn't empty
else
return false; // didn't collide, if we got this far
}
void CCmpObstructionManager::Rasterize(Grid& grid, const std::vector& passClasses, bool fullUpdate)
{
PROFILE3("Rasterize Obstructions");
// Cells are only marked as blocked if the whole cell is strictly inside the shape.
// (That ensures the shape's geometric border is always reachable.)
// Pass classes will get shapes rasterized on them depending on their Obstruction value.
// Classes with another value than "pathfinding" should not use Clearance.
std::map pathfindingMasks;
u16 foundationMask = 0;
for (const PathfinderPassability& passability : passClasses)
{
switch (passability.m_Obstructions)
{
case PathfinderPassability::PATHFINDING:
{
std::map::iterator it = pathfindingMasks.find(passability.m_Clearance);
if (it == pathfindingMasks.end())
pathfindingMasks[passability.m_Clearance] = passability.m_Mask;
else
it->second |= passability.m_Mask;
break;
}
case PathfinderPassability::FOUNDATION:
foundationMask |= passability.m_Mask;
break;
default:
continue;
}
}
// FLAG_BLOCK_PATHFINDING and FLAG_BLOCK_FOUNDATION are the only flags taken into account by MakeDirty* functions,
// so they should be the only ones rasterized using with the help of m_Dirty*Shapes vectors.
for (auto& maskPair : pathfindingMasks)
RasterizeHelper(grid, FLAG_BLOCK_PATHFINDING, fullUpdate, maskPair.second, maskPair.first);
RasterizeHelper(grid, FLAG_BLOCK_FOUNDATION, fullUpdate, foundationMask);
m_DirtyStaticShapes.clear();
m_DirtyUnitShapes.clear();
}
void CCmpObstructionManager::RasterizeHelper(Grid& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance) const
{
for (auto& pair : m_StaticShapes)
{
const StaticShape& shape = pair.second;
if (!(shape.flags & requireMask))
continue;
if (!fullUpdate && std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), pair.first) == m_DirtyStaticShapes.end())
continue;
// TODO: it might be nice to rasterize with rounded corners for large 'expand' values.
ObstructionSquare square = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh };
SimRasterize::Spans spans;
SimRasterize::RasterizeRectWithClearance(spans, square, clearance, Pathfinding::NAVCELL_SIZE);
for (SimRasterize::Span& span : spans)
{
i16 j = Clamp(span.j, (i16)0, (i16)(grid.m_H-1));
i16 i0 = std::max(span.i0, (i16)0);
i16 i1 = std::min(span.i1, (i16)grid.m_W);
for (i16 i = i0; i < i1; ++i)
grid.set(i, j, grid.get(i, j) | appliedMask);
}
}
for (auto& pair : m_UnitShapes)
{
if (!(pair.second.flags & requireMask))
continue;
if (!fullUpdate && std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), pair.first) == m_DirtyUnitShapes.end())
continue;
CFixedVector2D center(pair.second.x, pair.second.z);
entity_pos_t r = pair.second.clearance + clearance;
u16 i0, j0, i1, j1;
Pathfinding::NearestNavcell(center.X - r, center.Y - r, i0, j0, grid.m_W, grid.m_H);
Pathfinding::NearestNavcell(center.X + r, center.Y + r, i1, j1, grid.m_W, grid.m_H);
for (u16 j = j0+1; j < j1; ++j)
for (u16 i = i0+1; i < i1; ++i)
grid.set(i, j, grid.get(i, j) | appliedMask);
}
}
void CCmpObstructionManager::GetObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const
{
GetUnitObstructionsInRange(filter, x0, z0, x1, z1, squares);
GetStaticObstructionsInRange(filter, x0, z0, x1, z1, squares);
}
void CCmpObstructionManager::GetUnitObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const
{
PROFILE("GetObstructionsInRange");
ENSURE(x0 <= x1 && z0 <= z1);
std::vector unitShapes;
m_UnitSubdivision.GetInRange(unitShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1));
for (entity_id_t& unitShape : unitShapes)
{
std::map::const_iterator it = m_UnitShapes.find(unitShape);
ENSURE(it != m_UnitShapes.end());
if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY))
continue;
entity_pos_t c = it->second.clearance;
// Skip this object if it's completely outside the requested range
if (it->second.x + c < x0 || it->second.x - c > x1 || it->second.z + c < z0 || it->second.z - c > z1)
continue;
CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero());
CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1));
squares.emplace_back(ObstructionSquare{ it->second.x, it->second.z, u, v, c, c });
}
}
void CCmpObstructionManager::GetStaticObstructionsInRange(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, std::vector& squares) const
{
PROFILE("GetObstructionsInRange");
ENSURE(x0 <= x1 && z0 <= z1);
std::vector staticShapes;
m_StaticSubdivision.GetInRange(staticShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1));
for (entity_id_t& staticShape : staticShapes)
{
std::map::const_iterator it = m_StaticShapes.find(staticShape);
ENSURE(it != m_StaticShapes.end());
if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2))
continue;
entity_pos_t r = it->second.hw + it->second.hh; // overestimate the max dist of an edge from the center
// Skip this object if its overestimated bounding box is completely outside the requested range
if (it->second.x + r < x0 || it->second.x - r > x1 || it->second.z + r < z0 || it->second.z - r > z1)
continue;
// TODO: maybe we should use Geometry::GetHalfBoundingBox to be more precise?
squares.emplace_back(ObstructionSquare{ it->second.x, it->second.z, it->second.u, it->second.v, it->second.hw, it->second.hh });
}
}
void CCmpObstructionManager::GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict) const
{
PROFILE("GetUnitsOnObstruction");
// In order to avoid getting units on impassable cells, we want to find all
// units subject to the RasterizeRectWithClearance of the building's shape with the
// unit's clearance covers the navcell the unit is on.
std::vector unitShapes;
CFixedVector2D center(square.x, square.z);
CFixedVector2D expandedBox =
Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh)) +
CFixedVector2D(m_MaxClearance, m_MaxClearance);
m_UnitSubdivision.GetInRange(unitShapes, center - expandedBox, center + expandedBox);
std::map rasterizedRects;
for (const u32& unitShape : unitShapes)
{
std::map::const_iterator it = m_UnitShapes.find(unitShape);
ENSURE(it != m_UnitShapes.end());
const UnitShape& shape = it->second;
if (!filter.TestShape(UNIT_INDEX_TO_TAG(unitShape), shape.flags, shape.group, INVALID_ENTITY))
continue;
if (rasterizedRects.find(shape.clearance) == rasterizedRects.end())
{
// The rasterization is an approximation of the real shapes.
// Depending on your use, you may want to be more or less strict on the rasterization,
// ie this may either return some units that aren't actually on the shape (if strict is set)
// or this may not return some units that are on the shape (if strict is not set).
// Foundations need to be non-strict, as otherwise it sometimes detects the builder units
// as being on the shape, so it orders them away.
SimRasterize::Spans& newSpans = rasterizedRects[shape.clearance];
if (strict)
SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance, Pathfinding::NAVCELL_SIZE);
else
SimRasterize::RasterizeRectWithClearance(newSpans, square, shape.clearance-Pathfinding::CLEARANCE_EXTENSION_RADIUS, Pathfinding::NAVCELL_SIZE);
}
SimRasterize::Spans& spans = rasterizedRects[shape.clearance];
// Check whether the unit's center is on a navcell that's in
// any of the spans
u16 i = (shape.x / Pathfinding::NAVCELL_SIZE).ToInt_RoundToNegInfinity();
u16 j = (shape.z / Pathfinding::NAVCELL_SIZE).ToInt_RoundToNegInfinity();
for (const SimRasterize::Span& span : spans)
{
if (j == span.j && span.i0 <= i && i < span.i1)
{
out.push_back(shape.entity);
break;
}
}
}
}
void CCmpObstructionManager::GetStaticObstructionsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const
{
PROFILE("GetStaticObstructionsOnObstruction");
std::vector staticShapes;
CFixedVector2D center(square.x, square.z);
CFixedVector2D expandedBox = Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh));
m_StaticSubdivision.GetInRange(staticShapes, center - expandedBox, center + expandedBox);
for (const u32& staticShape : staticShapes)
{
std::map::const_iterator it = m_StaticShapes.find(staticShape);
ENSURE(it != m_StaticShapes.end());
const StaticShape& shape = it->second;
if (!filter.TestShape(STATIC_INDEX_TO_TAG(staticShape), shape.flags, shape.group, shape.group2))
continue;
if (Geometry::TestSquareSquare(
center,
square.u,
square.v,
CFixedVector2D(square.hw, square.hh),
CFixedVector2D(shape.x, shape.z),
shape.u,
shape.v,
CFixedVector2D(shape.hw, shape.hh)))
{
out.push_back(shape.entity);
}
}
}
void CCmpObstructionManager::RenderSubmit(SceneCollector& collector)
{
if (!m_DebugOverlayEnabled)
return;
CColor defaultColor(0, 0, 1, 1);
CColor movingColor(1, 0, 1, 1);
CColor boundsColor(1, 1, 0, 1);
// If the shapes have changed, then regenerate all the overlays
if (m_DebugOverlayDirty)
{
m_DebugOverlayLines.clear();
m_DebugOverlayLines.push_back(SOverlayLine());
m_DebugOverlayLines.back().m_Color = boundsColor;
SimRender::ConstructSquareOnGround(GetSimContext(),
(m_WorldX0+m_WorldX1).ToFloat()/2.f, (m_WorldZ0+m_WorldZ1).ToFloat()/2.f,
(m_WorldX1-m_WorldX0).ToFloat(), (m_WorldZ1-m_WorldZ0).ToFloat(),
0, m_DebugOverlayLines.back(), true);
for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it)
{
m_DebugOverlayLines.push_back(SOverlayLine());
m_DebugOverlayLines.back().m_Color = ((it->second.flags & FLAG_MOVING) ? movingColor : defaultColor);
SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.clearance.ToFloat(), it->second.clearance.ToFloat(), 0, m_DebugOverlayLines.back(), true);
}
for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it)
{
m_DebugOverlayLines.push_back(SOverlayLine());
m_DebugOverlayLines.back().m_Color = defaultColor;
float a = atan2f(it->second.v.X.ToFloat(), it->second.v.Y.ToFloat());
SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.hw.ToFloat()*2, it->second.hh.ToFloat()*2, a, m_DebugOverlayLines.back(), true);
}
m_DebugOverlayDirty = false;
}
for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i)
collector.Submit(&m_DebugOverlayLines[i]);
}
Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 25359)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 25360)
@@ -1,922 +1,924 @@
/* Copyright (C) 2021 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
* Common code and setup code for CCmpPathfinder.
*/
#include "precompiled.h"
#include "CCmpPathfinder_Common.h"
#include "simulation2/MessageTypes.h"
#include "simulation2/components/ICmpObstruction.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/components/ICmpTerrain.h"
#include "simulation2/components/ICmpWaterManager.h"
#include "simulation2/helpers/HierarchicalPathfinder.h"
#include "simulation2/helpers/LongPathfinder.h"
#include "simulation2/helpers/MapEdgeTiles.h"
#include "simulation2/helpers/Rasterize.h"
#include "simulation2/helpers/VertexPathfinder.h"
#include "simulation2/serialization/SerializedPathfinder.h"
#include "simulation2/serialization/SerializedTypes.h"
#include "ps/CLogger.h"
#include "ps/CStr.h"
#include "ps/Profile.h"
#include "ps/XML/Xeromyces.h"
#include "renderer/Scene.h"
#include
REGISTER_COMPONENT_TYPE(Pathfinder)
void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
{
- m_MapSize = 0;
+ m_GridSize = 0;
m_Grid = NULL;
m_TerrainOnlyGrid = NULL;
FlushAIPathfinderDirtinessInformation();
m_NextAsyncTicket = 1;
m_AtlasOverlay = NULL;
- m_VertexPathfinder = std::make_unique(m_MapSize, m_TerrainOnlyGrid);
+ m_VertexPathfinder = std::make_unique(m_GridSize, m_TerrainOnlyGrid);
m_LongPathfinder = std::make_unique();
m_PathfinderHier = std::make_unique();
// Register Relax NG validator
CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
// Since this is used as a system component (not loaded from an entity template),
// we can't use the real paramNode (it won't get handled properly when deserializing),
// so load the data from a special XML file.
CParamNode externalParamNode;
CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
// Paths are computed:
// - Before MT_Update
// - Before MT_MotionUnitFormation
// - 'in-between' turns (effectively at the start until threading is implemented).
// The latter of these must compute all outstanding requests, but the former two are capped
// to avoid spending too much time there (since the latter are designed to be threaded and thus not block the GUI).
// This loads that maximum number (note that it's per computation call, not per turn for now).
const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
{
std::string name = it->first;
ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);
pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());
m_PassClasses.push_back(PathfinderPassability(mask, it->second));
m_PassClassMasks[name] = mask;
}
}
CCmpPathfinder::~CCmpPathfinder() {};
void CCmpPathfinder::Deinit()
{
SetDebugOverlay(false); // cleans up memory
SAFE_DELETE(m_AtlasOverlay);
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);
}
template<>
struct SerializeHelper
{
template
void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify value)
{
serialize.NumberU32_Unbounded("ticket", value.ticket);
serialize.NumberFixed_Unbounded("x0", value.x0);
serialize.NumberFixed_Unbounded("z0", value.z0);
Serializer(serialize, "goal", value.goal);
serialize.NumberU16_Unbounded("pass class", value.passClass);
serialize.NumberU32_Unbounded("notify", value.notify);
}
};
template<>
struct SerializeHelper
{
template
void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify value)
{
serialize.NumberU32_Unbounded("ticket", value.ticket);
serialize.NumberFixed_Unbounded("x0", value.x0);
serialize.NumberFixed_Unbounded("z0", value.z0);
serialize.NumberFixed_Unbounded("clearance", value.clearance);
serialize.NumberFixed_Unbounded("range", value.range);
Serializer(serialize, "goal", value.goal);
serialize.NumberU16_Unbounded("pass class", value.passClass);
serialize.Bool("avoid moving units", value.avoidMovingUnits);
serialize.NumberU32_Unbounded("group", value.group);
serialize.NumberU32_Unbounded("notify", value.notify);
}
};
template
void CCmpPathfinder::SerializeCommon(S& serialize)
{
Serializer(serialize, "long requests", m_LongPathRequests.m_Requests);
Serializer(serialize, "short requests", m_ShortPathRequests.m_Requests);
serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
- serialize.NumberU16_Unbounded("map size", m_MapSize);
+ serialize.NumberU16_Unbounded("grid size", m_GridSize);
}
void CCmpPathfinder::Serialize(ISerializer& serialize)
{
SerializeCommon(serialize);
}
void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
{
Init(paramNode);
SerializeCommon(deserialize);
}
void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
{
switch (msg.GetType())
{
case MT_RenderSubmit:
{
const CMessageRenderSubmit& msgData = static_cast (msg);
RenderSubmit(msgData.collector);
break;
}
case MT_TerrainChanged:
{
const CMessageTerrainChanged& msgData = static_cast(msg);
m_TerrainDirty = true;
MinimalTerrainUpdate(msgData.i0, msgData.j0, msgData.i1, msgData.j1);
break;
}
case MT_WaterChanged:
case MT_ObstructionMapShapeChanged:
m_TerrainDirty = true;
UpdateGrid();
break;
case MT_Deserialized:
UpdateGrid();
// In case we were serialised with requests pending, we need to process them.
if (!m_ShortPathRequests.m_Requests.empty() || !m_LongPathRequests.m_Requests.empty())
{
ENSURE(CmpPtr(GetSystemEntity()));
StartProcessingMoves(false);
}
break;
}
}
void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
{
m_VertexPathfinder->RenderSubmit(collector);
m_PathfinderHier->RenderSubmit(collector);
}
void CCmpPathfinder::SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
{
m_LongPathfinder->SetDebugPath(*m_PathfinderHier, x0, z0, goal, passClass);
}
void CCmpPathfinder::SetDebugOverlay(bool enabled)
{
m_VertexPathfinder->SetDebugOverlay(enabled);
m_LongPathfinder->SetDebugOverlay(enabled);
}
void CCmpPathfinder::SetHierDebugOverlay(bool enabled)
{
m_PathfinderHier->SetDebugOverlay(enabled, &GetSimContext());
}
void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid& grid) const
{
m_LongPathfinder->GetDebugData(steps, time, grid);
}
void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
{
if (enable)
{
if (!m_AtlasOverlay)
m_AtlasOverlay = new AtlasOverlay(this, passClass);
m_AtlasOverlay->m_PassClass = passClass;
}
else
SAFE_DELETE(m_AtlasOverlay);
}
pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
{
std::map::const_iterator it = m_PassClassMasks.find(name);
if (it == m_PassClassMasks.end())
{
LOGERROR("Invalid passability class name '%s'", name.c_str());
return 0;
}
return it->second;
}
void CCmpPathfinder::GetPassabilityClasses(std::map& passClasses) const
{
passClasses = m_PassClassMasks;
}
void CCmpPathfinder::GetPassabilityClasses(std::map& nonPathfindingPassClasses, std::map& pathfindingPassClasses) const
{
for (const std::pair& pair : m_PassClassMasks)
{
if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
pathfindingPassClasses[pair.first] = pair.second;
else
nonPathfindingPassClasses[pair.first] = pair.second;
}
}
const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
{
for (const PathfinderPassability& passability : m_PassClasses)
{
if (passability.m_Mask == passClass)
return &passability;
}
return NULL;
}
const Grid& CCmpPathfinder::GetPassabilityGrid()
{
if (!m_Grid)
UpdateGrid();
return *m_Grid;
}
/**
* Given a grid of passable/impassable navcells (based on some passability mask),
* computes a new grid where a navcell is impassable (per that mask) if
* it is <=clearance navcells away from an impassable navcell in the original grid.
* The results are ORed onto the original grid.
*
* This is used for adding clearance onto terrain-based navcell passability.
*
* TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
* Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
* This would only really be a problem for big clearances.
*/
static void ExpandImpassableCells(Grid& grid, u16 clearance, pass_class_t mask)
{
PROFILE3("ExpandImpassableCells");
u16 w = grid.m_W;
u16 h = grid.m_H;
// First expand impassable cells horizontally into a temporary 1-bit grid
Grid tempGrid(w, h);
for (u16 j = 0; j < h; ++j)
{
// New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance
// Count the number of blocked cells around i=0
u16 numBlocked = 0;
for (u16 i = 0; i <= clearance && i < w; ++i)
if (!IS_PASSABLE(grid.get(i, j), mask))
++numBlocked;
for (u16 i = 0; i < w; ++i)
{
// Store a flag if blocked by at least one nearby cell
if (numBlocked)
tempGrid.set(i, j, 1);
// Slide the numBlocked window along:
// remove the old i-clearance value, add the new (i+1)+clearance
// (avoiding overflowing the grid)
if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))
--numBlocked;
if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))
++numBlocked;
}
}
for (u16 i = 0; i < w; ++i)
{
// New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance
// Count the number of blocked cells around j=0
u16 numBlocked = 0;
for (u16 j = 0; j <= clearance && j < h; ++j)
if (tempGrid.get(i, j))
++numBlocked;
for (u16 j = 0; j < h; ++j)
{
// Add the mask if blocked by at least one nearby cell
if (numBlocked)
grid.set(i, j, grid.get(i, j) | mask);
// Slide the numBlocked window along:
// remove the old j-clearance value, add the new (j+1)+clearance
// (avoiding overflowing the grid)
if (j >= clearance && tempGrid.get(i, j-clearance))
--numBlocked;
if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))
++numBlocked;
}
}
}
Grid CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
{
PROFILE3("ComputeShoreGrid");
CmpPtr cmpWaterManager(GetSystemEntity());
// TODO: these bits should come from ICmpTerrain
CTerrain& terrain = GetSimContext().GetTerrain();
// avoid integer overflow in intermediate calculation
const u16 shoreMax = 32767;
+ u16 shoreGridSize = terrain.GetTilesPerSide();
+
// First pass - find underwater tiles
- Grid waterGrid(m_MapSize, m_MapSize);
- for (u16 j = 0; j < m_MapSize; ++j)
+ Grid waterGrid(shoreGridSize, shoreGridSize);
+ for (u16 j = 0; j < shoreGridSize; ++j)
{
- for (u16 i = 0; i < m_MapSize; ++i)
+ for (u16 i = 0; i < shoreGridSize; ++i)
{
fixed x, z;
- Pathfinding::TileCenter(i, j, x, z);
+ Pathfinding::TerrainTileCenter(i, j, x, z);
bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
waterGrid.set(i, j, underWater ? 1 : 0);
}
}
// Second pass - find shore tiles
- Grid shoreGrid(m_MapSize, m_MapSize);
- for (u16 j = 0; j < m_MapSize; ++j)
+ Grid shoreGrid(shoreGridSize, shoreGridSize);
+ for (u16 j = 0; j < shoreGridSize; ++j)
{
- for (u16 i = 0; i < m_MapSize; ++i)
+ for (u16 i = 0; i < shoreGridSize; ++i)
{
// Find a land tile
if (!waterGrid.get(i, j))
{
// If it's bordered by water, it's a shore tile
- if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < m_MapSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1))
- || (i < m_MapSize-1 && waterGrid.get(i+1, j)) || (i < m_MapSize-1 && j < m_MapSize-1 && waterGrid.get(i+1, j+1)) || (i < m_MapSize-1 && j > 0 && waterGrid.get(i+1, j-1))
- || (j > 0 && waterGrid.get(i, j-1)) || (j < m_MapSize-1 && waterGrid.get(i, j+1))
+ if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < shoreGridSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1))
+ || (i < shoreGridSize-1 && waterGrid.get(i+1, j)) || (i < shoreGridSize-1 && j < shoreGridSize-1 && waterGrid.get(i+1, j+1)) || (i < shoreGridSize-1 && j > 0 && waterGrid.get(i+1, j-1))
+ || (j > 0 && waterGrid.get(i, j-1)) || (j < shoreGridSize-1 && waterGrid.get(i, j+1))
)
shoreGrid.set(i, j, 0);
else
shoreGrid.set(i, j, shoreMax);
}
// If we want to expand on water, we want water tiles not to be shore tiles
else if (expandOnWater)
shoreGrid.set(i, j, shoreMax);
}
}
// Expand influences on land to find shore distance
- for (u16 y = 0; y < m_MapSize; ++y)
+ for (u16 y = 0; y < shoreGridSize; ++y)
{
u16 min = shoreMax;
- for (u16 x = 0; x < m_MapSize; ++x)
+ for (u16 x = 0; x < shoreGridSize; ++x)
{
if (!waterGrid.get(x, y) || expandOnWater)
{
u16 g = shoreGrid.get(x, y);
if (g > min)
shoreGrid.set(x, y, min);
else if (g < min)
min = g;
++min;
}
}
- for (u16 x = m_MapSize; x > 0; --x)
+ for (u16 x = shoreGridSize; x > 0; --x)
{
if (!waterGrid.get(x-1, y) || expandOnWater)
{
u16 g = shoreGrid.get(x-1, y);
if (g > min)
shoreGrid.set(x-1, y, min);
else if (g < min)
min = g;
++min;
}
}
}
- for (u16 x = 0; x < m_MapSize; ++x)
+ for (u16 x = 0; x < shoreGridSize; ++x)
{
u16 min = shoreMax;
- for (u16 y = 0; y < m_MapSize; ++y)
+ for (u16 y = 0; y < shoreGridSize; ++y)
{
if (!waterGrid.get(x, y) || expandOnWater)
{
u16 g = shoreGrid.get(x, y);
if (g > min)
shoreGrid.set(x, y, min);
else if (g < min)
min = g;
++min;
}
}
- for (u16 y = m_MapSize; y > 0; --y)
+ for (u16 y = shoreGridSize; y > 0; --y)
{
if (!waterGrid.get(x, y-1) || expandOnWater)
{
u16 g = shoreGrid.get(x, y-1);
if (g > min)
shoreGrid.set(x, y-1, min);
else if (g < min)
min = g;
++min;
}
}
}
return shoreGrid;
}
void CCmpPathfinder::UpdateGrid()
{
PROFILE3("UpdateGrid");
CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
if (!cmpTerrain)
return; // error
- u16 terrainSize = cmpTerrain->GetTilesPerSide();
- if (terrainSize == 0)
+ u16 gridSize = cmpTerrain->GetMapSize() / Pathfinding::NAVCELL_SIZE_INT;
+ if (gridSize == 0)
return;
// If the terrain was resized then delete the old grid data
- if (m_Grid && m_MapSize != terrainSize)
+ if (m_Grid && m_GridSize != gridSize)
{
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);
}
// Initialise the terrain data when first needed
if (!m_Grid)
{
- m_MapSize = terrainSize;
- m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
+ m_GridSize = gridSize;
+ m_Grid = new Grid(m_GridSize, m_GridSize);
SAFE_DELETE(m_TerrainOnlyGrid);
- m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
+ m_TerrainOnlyGrid = new Grid(m_GridSize, m_GridSize);
- m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
+ m_DirtinessInformation = { true, true, Grid(m_GridSize, m_GridSize) };
m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
m_TerrainDirty = true;
}
// The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
#ifdef NDEBUG
ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
#else
- ENSURE(m_DirtinessInformation.dirtinessGrid == Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));
+ ENSURE(m_DirtinessInformation.dirtinessGrid == Grid(m_GridSize, m_GridSize));
#endif
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
cmpObstructionManager->UpdateInformations(m_DirtinessInformation);
if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
return;
// If the terrain has changed, recompute m_Grid
// Else, use data from m_TerrainOnlyGrid and add obstructions
if (m_TerrainDirty)
{
TerrainUpdateHelper();
*m_Grid = *m_TerrainOnlyGrid;
m_TerrainDirty = false;
m_DirtinessInformation.globallyDirty = true;
}
else if (m_DirtinessInformation.globallyDirty)
{
ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)*(m_Grid->m_H)*sizeof(NavcellData));
}
else
{
ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
}
// Add obstructions onto the grid
cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);
// Update the long-range and hierarchical pathfinders.
if (m_DirtinessInformation.globallyDirty)
{
std::map nonPathfindingPassClasses, pathfindingPassClasses;
GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
m_LongPathfinder->Reload(m_Grid);
m_PathfinderHier->Recompute(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
}
else
{
m_LongPathfinder->Update(m_Grid);
m_PathfinderHier->Update(m_Grid, m_DirtinessInformation.dirtinessGrid);
}
// Remember the necessary updates that the AI pathfinder will have to perform as well
m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);
}
void CCmpPathfinder::MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1)
{
TerrainUpdateHelper(false, itile0, jtile0, itile1, jtile1);
}
void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability, int itile0, int jtile0, int itile1, int jtile1)
{
PROFILE3("TerrainUpdateHelper");
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
CmpPtr cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
CTerrain& terrain = GetSimContext().GetTerrain();
if (!cmpTerrain || !cmpObstructionManager)
return;
- u16 terrainSize = cmpTerrain->GetTilesPerSide();
- if (terrainSize == 0)
+ u16 gridSize = cmpTerrain->GetMapSize() / Pathfinding::NAVCELL_SIZE_INT;
+ if (gridSize == 0)
return;
- const bool needsNewTerrainGrid = !m_TerrainOnlyGrid || m_MapSize != terrainSize;
+ const bool needsNewTerrainGrid = !m_TerrainOnlyGrid || m_GridSize != gridSize;
if (needsNewTerrainGrid)
{
- m_MapSize = terrainSize;
+ m_GridSize = gridSize;
SAFE_DELETE(m_TerrainOnlyGrid);
- m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
+ m_TerrainOnlyGrid = new Grid(m_GridSize, m_GridSize);
// If this update comes from a map resizing, we must reinitialize the other grids as well
if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
{
SAFE_DELETE(m_Grid);
- m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
+ m_Grid = new Grid(m_GridSize, m_GridSize);
- m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
+ m_DirtinessInformation = { true, true, Grid(m_GridSize, m_GridSize) };
m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
}
}
Grid shoreGrid = ComputeShoreGrid();
const bool partialTerrainGridUpdate =
!expandPassability && !needsNewTerrainGrid &&
itile0 != -1 && jtile0 != -1 && itile1 != -1 && jtile1 != -1;
- int istart = 0, iend = m_MapSize * Pathfinding::NAVCELLS_PER_TILE;
- int jstart = 0, jend = m_MapSize * Pathfinding::NAVCELLS_PER_TILE;
+ int istart = 0, iend = m_GridSize;
+ int jstart = 0, jend = m_GridSize;
if (partialTerrainGridUpdate)
{
// We need to extend the boundaries by 1 tile, because slope and ground
// level are calculated by multiple neighboring tiles.
// TODO: add CTerrain constant instead of 1.
- istart = Clamp(itile0 - 1, 0, m_MapSize) * Pathfinding::NAVCELLS_PER_TILE;
- iend = Clamp(itile1 + 1, 0, m_MapSize) * Pathfinding::NAVCELLS_PER_TILE;
- jstart = Clamp(jtile0 - 1, 0, m_MapSize) * Pathfinding::NAVCELLS_PER_TILE;
- jend = Clamp(jtile1 + 1, 0, m_MapSize) * Pathfinding::NAVCELLS_PER_TILE;
+ istart = Clamp(itile0 - 1, 0, m_GridSize);
+ iend = Clamp(itile1 + 1, 0, m_GridSize);
+ jstart = Clamp(jtile0 - 1, 0, m_GridSize);
+ jend = Clamp(jtile1 + 1, 0, m_GridSize);
}
// Compute initial terrain-dependent passability
for (int j = jstart; j < jend; ++j)
{
for (int i = istart; i < iend; ++i)
{
// World-space coordinates for this navcell
fixed x, z;
Pathfinding::NavcellCenter(i, j, x, z);
// Terrain-tile coordinates for this navcell
- int itile = i / Pathfinding::NAVCELLS_PER_TILE;
- int jtile = j / Pathfinding::NAVCELLS_PER_TILE;
+ int itile = i / Pathfinding::NAVCELLS_PER_TERRAIN_TILE;
+ int jtile = j / Pathfinding::NAVCELLS_PER_TERRAIN_TILE;
// Gather all the data potentially needed to determine passability:
fixed height = terrain.GetExactGroundLevelFixed(x, z);
fixed water;
if (cmpWaterManager)
water = cmpWaterManager->GetWaterLevel(x, z);
fixed depth = water - height;
// Exact slopes give kind of weird output, so just use rough tile-based slopes
fixed slope = terrain.GetSlopeFixed(itile, jtile);
// Get world-space coordinates from shoreGrid (which uses terrain tiles)
fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);
// Compute the passability for every class for this cell
NavcellData t = 0;
for (const PathfinderPassability& passability : m_PassClasses)
if (!passability.IsPassable(depth, slope, shoredist))
t |= passability.m_Mask;
m_TerrainOnlyGrid->set(i, j, t);
}
}
// Compute off-world passability
- const int edgeSize = MAP_EDGE_TILES * Pathfinding::NAVCELLS_PER_TILE;
+ const int edgeSize = MAP_EDGE_TILES * Pathfinding::NAVCELLS_PER_TERRAIN_TILE;
NavcellData edgeMask = 0;
for (const PathfinderPassability& passability : m_PassClasses)
edgeMask |= passability.m_Mask;
int w = m_TerrainOnlyGrid->m_W;
int h = m_TerrainOnlyGrid->m_H;
if (cmpObstructionManager->GetPassabilityCircular())
{
for (int j = jstart; j < jend; ++j)
{
for (int i = istart; i < iend; ++i)
{
// Based on CCmpRangeManager::LosIsOffWorld
// but tweaked since it's tile-based instead.
// (We double all the values so we can handle half-tile coordinates.)
// This needs to be slightly tighter than the LOS circle,
// else units might get themselves lost in the SoD around the edge.
int dist2 = (i*2 + 1 - w)*(i*2 + 1 - w)
+ (j*2 + 1 - h)*(j*2 + 1 - h);
if (dist2 >= (w - 2*edgeSize) * (h - 2*edgeSize))
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
}
}
}
else
{
for (u16 j = 0; j < h; ++j)
for (u16 i = 0; i < edgeSize; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
for (u16 j = 0; j < h; ++j)
for (u16 i = w-edgeSize+1; i < w; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
for (u16 j = 0; j < edgeSize; ++j)
for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
for (u16 j = h-edgeSize+1; j < h; ++j)
for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
}
if (!expandPassability)
return;
// Expand the impassability grid, for any class with non-zero clearance,
// so that we can stop units getting too close to impassable navcells.
// Note: It's not possible to perform this expansion once for all passabilities
// with the same clearance, because the impassable cells are not necessarily the
// same for all these passabilities.
for (PathfinderPassability& passability : m_PassClasses)
{
if (passability.m_Clearance == fixed::Zero())
continue;
int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();
ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);
}
}
//////////////////////////////////////////////////////////
u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
{
LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
m_LongPathRequests.m_Requests.push_back(req);
return req.ticket;
}
u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range,
const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits,
entity_id_t group, entity_id_t notify)
{
ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
m_ShortPathRequests.m_Requests.push_back(req);
return req.ticket;
}
void CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const
{
m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret);
}
WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const
{
return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity()));
}
template
template
void CCmpPathfinder::PathRequests::Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder)
{
static_assert((std::is_same_v && std::is_same_v) ||
(std::is_same_v && std::is_same_v));
size_t maxN = m_Results.size();
size_t startIndex = m_Requests.size() - m_Results.size();
do
{
size_t workIndex = m_NextPathToCompute++;
if (workIndex >= maxN)
break;
const T& req = m_Requests[startIndex + workIndex];
PathResult& result = m_Results[workIndex];
result.ticket = req.ticket;
result.notify = req.notify;
if constexpr (std::is_same_v)
pathfinder.ComputePath(*cmpPathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, result.path);
else
result.path = pathfinder.ComputeShortPath(req, CmpPtr(cmpPathfinder.GetSystemEntity()));
if (workIndex == maxN - 1)
m_ComputeDone = true;
}
while (true);
}
void CCmpPathfinder::SendRequestedPaths()
{
PROFILE2("SendRequestedPaths");
if (!m_LongPathRequests.m_ComputeDone || !m_ShortPathRequests.m_ComputeDone)
{
m_ShortPathRequests.Compute(*this, *m_VertexPathfinder);
m_LongPathRequests.Compute(*this, *m_LongPathfinder);
}
{
PROFILE2("PostMessages");
for (PathResult& path : m_ShortPathRequests.m_Results)
{
CMessagePathResult msg(path.ticket, path.path);
GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
}
for (PathResult& path : m_LongPathRequests.m_Results)
{
CMessagePathResult msg(path.ticket, path.path);
GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
}
}
m_ShortPathRequests.ClearComputed();
m_LongPathRequests.ClearComputed();
}
void CCmpPathfinder::StartProcessingMoves(bool useMax)
{
m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
}
//////////////////////////////////////////////////////////
bool CCmpPathfinder::IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
{
PROFILE2("IsGoalReachable");
u16 i, j;
- Pathfinding::NearestNavcell(x0, z0, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
+ Pathfinding::NearestNavcell(x0, z0, i, j, m_GridSize, m_GridSize);
if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
m_PathfinderHier->FindNearestPassableNavcell(i, j, passClass);
return m_PathfinderHier->IsGoalReachable(i, j, goal, passClass);
}
bool CCmpPathfinder::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) const
{
PROFILE2_IFSPIKE("Check Movement", 0.001);
// Test against obstructions first. filter may discard pathfinding-blocking obstructions.
// Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
// This makes movement smoother and more natural for units, overall.
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
return false;
// Then test against the terrain grid. This should not be necessary
// But in case we allow terrain to change it will become so.
return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
{
// Check unit obstruction
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
// Test against terrain and static obstructions:
u16 i, j;
- Pathfinding::NearestNavcell(x, z, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
+ Pathfinding::NearestNavcell(x, z, i, j, m_GridSize, m_GridSize);
if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
// (Static obstructions will be redundantly tested against in both the
// obstruction-shape test and navcell-passability test, which is slightly
// inefficient but shouldn't affect behaviour)
return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::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) const
{
return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::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 UNUSED(onlyCenterPoint)) const
{
// Check unit obstruction
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
// Test against terrain:
ICmpObstructionManager::ObstructionSquare square;
CmpPtr cmpObstruction(GetSimContext(), id);
if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;
entity_pos_t expand;
const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
if (passability)
expand = passability->m_Clearance;
SimRasterize::Spans spans;
SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
for (const SimRasterize::Span& span : spans)
{
i16 i0 = span.i0;
i16 i1 = span.i1;
i16 j = span.j;
// Fail if any span extends outside the grid
if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
// Fail if any span includes an impassable tile
for (i16 i = i0; i < i1; ++i)
if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
}
return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
}
Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 25359)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 25360)
@@ -1,294 +1,294 @@
/* Copyright (C) 2021 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. 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 "renderer/TerrainOverlay.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/helpers/Grid.h"
#include
class HierarchicalPathfinder;
class LongPathfinder;
class VertexPathfinder;
class SceneCollector;
class AtlasOverlay;
#ifdef NDEBUG
#define PATHFIND_DEBUG 0
#else
#define PATHFIND_DEBUG 1
#endif
/**
* Implementation of ICmpPathfinder
*/
class CCmpPathfinder final : public ICmpPathfinder
{
public:
static void ClassInit(CComponentManager& componentManager)
{
componentManager.SubscribeToMessageType(MT_Deserialized);
componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
componentManager.SubscribeToMessageType(MT_TerrainChanged);
componentManager.SubscribeToMessageType(MT_WaterChanged);
componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);
}
~CCmpPathfinder();
DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)
// Template state:
std::map m_PassClassMasks;
std::vector m_PassClasses;
u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves.
// Dynamic state:
// Lazily-constructed dynamic state (not serialized):
- u16 m_MapSize; // tiles per side
+ u16 m_GridSize; // Navcells per side of the map.
Grid* m_Grid; // terrain/passability information
Grid* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations
// Keep clever updates in memory to avoid memory fragmentation from the grid.
// This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else.
GridUpdateInformation m_DirtinessInformation;
// The data from clever updates is stored for the AI manager
GridUpdateInformation m_AIPathfinderDirtinessInformation;
bool m_TerrainDirty;
std::unique_ptr m_VertexPathfinder;
std::unique_ptr m_PathfinderHier;
std::unique_ptr m_LongPathfinder;
template
class PathRequests {
public:
std::vector m_Requests;
std::vector m_Results;
// This is the array index of the next path to compute.
size_t m_NextPathToCompute = 0;
// This is false until all scheduled paths have been computed.
bool m_ComputeDone = true;
void ClearComputed()
{
if (m_Results.size() == m_Requests.size())
m_Requests.clear();
else
m_Requests.erase(m_Requests.end() - m_Results.size(), m_Requests.end());
m_Results.clear();
}
/**
* @param max - if non-zero, how many paths to process.
*/
void PrepareForComputation(u16 max)
{
size_t n = m_Requests.size();
if (max && n > max)
n = max;
m_NextPathToCompute = 0;
m_Results.resize(n);
m_ComputeDone = n == 0;
}
template
void Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder);
};
PathRequests m_LongPathRequests;
PathRequests m_ShortPathRequests;
u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests.
AtlasOverlay* m_AtlasOverlay;
static std::string GetSchema()
{
return "";
}
virtual void Init(const CParamNode& paramNode);
virtual void Deinit();
template
void SerializeCommon(S& serialize);
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) const;
virtual void GetPassabilityClasses(std::map& passClasses) const;
virtual void GetPassabilityClasses(
std::map& nonPathfindingPassClasses,
std::map& pathfindingPassClasses) const;
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)
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_Clearance > max)
max = passability.m_Clearance;
return max + Pathfinding::CLEARANCE_EXTENSION_RADIUS;
}
virtual const Grid& GetPassabilityGrid();
virtual const GridUpdateInformation& GetAIPathfinderDirtinessInformation() const
{
return m_AIPathfinderDirtinessInformation;
}
virtual void FlushAIPathfinderDirtinessInformation()
{
m_AIPathfinderDirtinessInformation.Clean();
}
virtual Grid ComputeShoreGrid(bool expandOnWater = false);
virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const;
virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify);
virtual WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const;
virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify);
virtual bool IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass);
virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass);
virtual void SetDebugOverlay(bool enabled);
virtual void SetHierDebugOverlay(bool enabled);
virtual void GetDebugData(u32& steps, double& time, Grid& grid) const;
virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0);
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) const;
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) const;
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) const;
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) const;
virtual void SendRequestedPaths();
virtual void StartProcessingMoves(bool useMax);
template
std::vector GetMovesToProcess(std::vector& requests, bool useMax = false, size_t maxMoves = 0);
template
void PushRequestsToWorkers(std::vector& from);
/**
* Regenerates the grid based on the current obstruction list, if necessary
*/
virtual void UpdateGrid();
/**
* Updates the terrain-only grid without updating the dirtiness informations.
* Useful for fast passability updates in Atlas.
*/
void MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1);
/**
* Regenerates the terrain-only grid.
* Atlas doesn't need to have passability cells expanded.
*/
void TerrainUpdateHelper(bool expandPassability = true, int itile0 = -1, int jtile0 = -1, int itile1 = -1, int jtile1 = -1);
void RenderSubmit(SceneCollector& collector);
};
class AtlasOverlay : public TerrainTextureOverlay
{
public:
const CCmpPathfinder* m_Pathfinder;
pass_class_t m_PassClass;
AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) :
- TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
+ TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TERRAIN_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
{
}
virtual void BuildTextureRGBA(u8* data, size_t w, size_t h)
{
// Render navcell passability, based on the terrain-only grid
u8* p = data;
for (size_t j = 0; j < h; ++j)
{
for (size_t i = 0; i < w; ++i)
{
SColor4ub color(0, 0, 0, 0);
if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
color = SColor4ub(255, 0, 0, 127);
*p++ = color.R;
*p++ = color.G;
*p++ = color.B;
*p++ = color.A;
}
}
}
};
#endif // INCLUDED_CCMPPATHFINDER_COMMON
Index: ps/trunk/source/simulation2/components/CCmpRangeManager.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpRangeManager.cpp (revision 25359)
+++ ps/trunk/source/simulation2/components/CCmpRangeManager.cpp (revision 25360)
@@ -1,2489 +1,2501 @@
/* Copyright (C) 2021 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/Los.h"
#include "simulation2/helpers/MapEdgeTiles.h"
#include "simulation2/helpers/Render.h"
#include "simulation2/helpers/Spatial.h"
#include "simulation2/serialization/SerializedTypes.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 DEBUG_RANGE_MANAGER_BOUNDS 0
+namespace
+{
+/**
+ * How many LOS vertices to have per region.
+ * LOS regions are used to keep track of units.
+ */
constexpr int LOS_REGION_RATIO = 8;
/**
+ * Tolerance for parabolic range calculations.
+ * TODO C++20: change this to constexpr by fixing CFixed with std::is_constant_evaluated
+ */
+const fixed PARABOLIC_RANGE_TOLERANCE = fixed::FromInt(1)/2;
+
+/**
* 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)
+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)
+u32 CalcPlayerLosMask(player_id_t player)
{
if (player > 0 && player <= 16)
return (u32)LosState::MASK << (2*(player-1));
return 0;
}
/**
* Returns shared LOS mask for given list of players.
*/
-static u32 CalcSharedLosMask(std::vector players)
+u32 CalcSharedLosMask(std::vector players)
{
u32 playerMask = 0;
for (size_t i = 0; i < players.size(); i++)
playerMask |= CalcPlayerLosMask(players[i]);
return playerMask;
}
/**
* Add/remove a player to/from mask, which is a 1-bit mask representing a list of players.
* Returns true if the mask is modified.
*/
-static bool SetPlayerSharedDirtyVisibilityBit(u16& mask, player_id_t player, bool enable)
+bool SetPlayerSharedDirtyVisibilityBit(u16& mask, player_id_t player, bool enable)
{
if (player <= 0 || player > 16)
return false;
u16 oldMask = mask;
if (enable)
mask |= (0x1 << (player - 1));
else
mask &= ~(0x1 << (player - 1));
return oldMask != mask;
}
/**
* Computes the 2-bit visibility for one player, given the total 32-bit visibilities
*/
-static inline LosVisibility GetPlayerVisibility(u32 visibilities, player_id_t player)
+LosVisibility GetPlayerVisibility(u32 visibilities, player_id_t player)
{
if (player > 0 && player <= 16)
return static_cast( (visibilities >> (2 *(player-1))) & 0x3 );
return LosVisibility::HIDDEN;
}
/**
* Test whether the visibility is dirty for a given LoS region and a given player
*/
-static inline bool IsVisibilityDirty(u16 dirty, player_id_t player)
+bool IsVisibilityDirty(u16 dirty, player_id_t player)
{
if (player > 0 && player <= 16)
return (dirty >> (player - 1)) & 0x1;
return false;
}
/**
* Test whether a player share this vision
*/
-static inline bool HasVisionSharing(u16 visionSharing, player_id_t player)
+bool HasVisionSharing(u16 visionSharing, player_id_t player)
{
return (visionSharing & (1 << (player - 1))) != 0;
}
/**
* Computes the shared vision mask for the player
*/
-static inline u16 CalcVisionSharingMask(player_id_t player)
+u16 CalcVisionSharingMask(player_id_t player)
{
return 1 << (player-1);
}
/**
* Representation of a range query.
*/
struct Query
{
std::vector lastMatch;
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; // Used for parabolas only.
u32 ownersMask;
i32 interface;
u8 flagsMask;
bool enabled;
bool parabolic;
bool accountForSize; // If true, the query accounts for unit sizes, otherwise it treats all entities as points.
};
/**
* 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
* This equates to computing f(x, z) = y = -(xx + zz)/(2*range) + range/2 > 0,
* or alternatively sqrt(xx+zz) <= sqrt(range^2 - 2range*y).
*
* Avoids sqrting and overflowing.
*/
static bool InParabolicRange(CFixedVector3D v, fixed range)
{
u64 xx = SQUARE_U64_FIXED(v.X); // xx <= 2^62
u64 zz = SQUARE_U64_FIXED(v.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 = MUL_I64_I32_I32(c_2 - y, c);
return d2 <= c2;
}
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.
*/
enum FlagMasks
{
// flags used for queries
None = 0x00,
Normal = 0x01,
Injured = 0x02,
AllQuery = Normal | Injured,
// 0x04 reserved for future use
// general flags
InWorld = 0x08,
RetainInFog = 0x10,
RevealShore = 0x20,
ScriptedVisibility = 0x40,
SharedVision = 0x80
};
struct EntityData
{
EntityData() :
visibilities(0), size(0), visionSharing(0),
owner(-1), flags(FlagMasks::Normal)
{ }
entity_pos_t x, z;
entity_pos_t visionRange;
u32 visibilities; // 2-bit visibility, per player
u32 size;
u16 visionSharing; // 1-bit per player
i8 owner;
u8 flags; // See the FlagMasks enum
template
inline bool HasFlag() const { return (flags & mask) != 0; }
template
inline void SetFlag(bool val) { flags = val ? (flags | mask) : (flags & ~mask); }
inline void SetFlag(u8 mask, bool val) { flags = val ? (flags | mask) : (flags & ~mask); }
};
-cassert(sizeof(EntityData) == 24);
+static_assert(sizeof(EntityData) == 24);
+
+/**
+ * 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.
+ */
+class EntityDistanceOrdering
+{
+public:
+ EntityDistanceOrdering(const EntityMap& entities, const CFixedVector2D& source) :
+ m_EntityData(entities), m_Source(source)
+ {
+ }
+
+ EntityDistanceOrdering(const EntityDistanceOrdering& entity) = default;
+
+ bool operator()(entity_id_t a, entity_id_t b) const
+ {
+ 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&);
+};
+} // anonymous namespace
/**
* Serialization helper template for Query
*/
template<>
struct SerializeHelper
{
template
void Common(S& serialize, const char* UNUSED(name), Serialize::qualify value)
{
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);
Serializer(serialize, "last match", value.lastMatch);
serialize.NumberU8_Unbounded("flagsMask", value.flagsMask);
serialize.Bool("enabled", value.enabled);
serialize.Bool("parabolic",value.parabolic);
serialize.Bool("account for size",value.accountForSize);
}
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
+ // the referenced entity might not have been deserialized yet,
+ // so tell LookupEntityHandle to allocate the handle if necessary
}
};
/**
* Serialization helper template for EntityData
*/
template<>
struct SerializeHelper
{
template
void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify 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.NumberU16_Unbounded("vision sharing", value.visionSharing);
serialize.NumberI8_Unbounded("owner", value.owner);
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.
- */
-class EntityDistanceOrdering
-{
-public:
- EntityDistanceOrdering(const EntityMap& entities, const CFixedVector2D& source) :
- m_EntityData(entities), m_Source(source)
- {
- }
-
- EntityDistanceOrdering(const EntityDistanceOrdering& entity) = default;
-
- bool operator()(entity_id_t a, entity_id_t b) const
- {
- 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.SubscribeGloballyToMessageType(MT_VisionSharingChanged);
componentManager.SubscribeToMessageType(MT_Deserialized);
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;
// Deserialization flag. A lot of different functions are called by Deserialize()
// and we don't want to pass isDeserializing bool arguments to all of them...
bool m_Deserializing;
// 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
std::vector m_SubdivisionResults;
// LOS state:
static const player_id_t MAX_LOS_PLAYER_ID = 16;
using LosRegion = std::pair;
std::array m_LosRevealAll;
bool m_LosCircular;
i32 m_LosVerticesPerSide;
// Cache for visibility tracking
i32 m_LosRegionsPerSide;
bool m_GlobalVisibilityUpdate;
std::array m_GlobalPlayerVisibilityUpdate;
Grid m_DirtyVisibility;
Grid> m_LosRegions;
// 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::array, MAX_LOS_PLAYER_ID> m_LosPlayerCounts;
// 2-bit LosState per player, starting with player 1 (not 0!) up to player MAX_LOS_PLAYER_ID (inclusive)
Grid m_LosState;
// Special static visibility data for the "reveal whole map" mode
// (TODO: this is usually a waste of memory)
Grid m_LosStateRevealed;
// Shared LOS masks, one per player.
std::array m_SharedLosMasks;
// Shared dirty visibility masks, one per player.
std::array m_SharedDirtyVisibilityMasks;
// Cache explored vertices per player (not serialized)
u32 m_TotalInworldVertices;
std::vector m_ExploredVertices;
static std::string GetSchema()
{
return "