Index: ps/trunk/source/graphics/TerritoryTexture.cpp =================================================================== --- ps/trunk/source/graphics/TerritoryTexture.cpp +++ ps/trunk/source/graphics/TerritoryTexture.cpp @@ -1,4 +1,4 @@ -/* 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 @@ -92,7 +92,7 @@ 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); Index: ps/trunk/source/maths/Fixed.h =================================================================== --- ps/trunk/source/maths/Fixed.h +++ ps/trunk/source/maths/Fixed.h @@ -1,4 +1,4 @@ -/* 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 @@ -123,7 +123,7 @@ private: T value; - explicit CFixed(T v) : value(v) { } + constexpr explicit CFixed(T v) : value(v) { } public: enum { fract_bits = fract_bits_ }; @@ -139,12 +139,12 @@ // 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); @@ -152,7 +152,7 @@ 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); @@ -175,7 +175,7 @@ return value / (double)fract_pow2; } - int ToInt_RoundToZero() const + constexpr int ToInt_RoundToZero() const { if (value > 0) return value >> fract_bits; @@ -183,17 +183,17 @@ 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; } @@ -202,25 +202,25 @@ 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: @@ -239,10 +239,10 @@ } /// 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 @@ -282,7 +282,7 @@ } /// 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)); @@ -297,7 +297,7 @@ } /// 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) @@ -308,7 +308,7 @@ 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, @@ -326,7 +326,7 @@ /** * Multiply the value by itself. Might overflow. */ - CFixed Square() const + constexpr CFixed Square() const { return (*this).Multiply(*this); } @@ -341,7 +341,7 @@ return CFixed((T)t); } - CFixed Sqrt() const + constexpr CFixed Sqrt() const { if (value <= 0) return CFixed(0); Index: ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp +++ ps/trunk/source/simulation2/components/CCmpObstructionManager.cpp @@ -1,4 +1,4 @@ -/* 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 @@ -20,7 +20,6 @@ #include "simulation2/system/Component.h" #include "ICmpObstructionManager.h" -#include "ICmpTerrain.h" #include "ICmpPosition.h" #include "simulation2/MessageTypes.h" @@ -32,7 +31,6 @@ #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" @@ -48,6 +46,14 @@ #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 */ @@ -73,7 +79,7 @@ entity_id_t group; entity_id_t group2; }; - +} // anonymous namespace /** * Serialization helper template for UnitShape */ @@ -147,7 +153,6 @@ entity_pos_t m_WorldZ0; entity_pos_t m_WorldX1; entity_pos_t m_WorldZ1; - u16 m_TerrainTiles; static std::string GetSchema() { @@ -168,7 +173,6 @@ 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) @@ -198,7 +202,6 @@ 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) @@ -215,7 +218,8 @@ 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)) @@ -245,12 +249,8 @@ 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) @@ -259,10 +259,8 @@ 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) { @@ -557,9 +555,7 @@ 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; Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp +++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp @@ -49,7 +49,7 @@ void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode)) { - m_MapSize = 0; + m_GridSize = 0; m_Grid = NULL; m_TerrainOnlyGrid = NULL; @@ -59,7 +59,7 @@ 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(); @@ -145,7 +145,7 @@ 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) @@ -365,14 +365,16 @@ // 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); @@ -380,18 +382,18 @@ } // 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 @@ -404,10 +406,10 @@ } // 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) { @@ -420,7 +422,7 @@ ++min; } } - for (u16 x = m_MapSize; x > 0; --x) + for (u16 x = shoreGridSize; x > 0; --x) { if (!waterGrid.get(x-1, y) || expandOnWater) { @@ -434,10 +436,10 @@ } } } - 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) { @@ -450,7 +452,7 @@ ++min; } } - for (u16 y = m_MapSize; y > 0; --y) + for (u16 y = shoreGridSize; y > 0; --y) { if (!waterGrid.get(x, y-1) || expandOnWater) { @@ -476,12 +478,12 @@ 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); @@ -490,12 +492,12 @@ // 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; @@ -505,7 +507,7 @@ #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); @@ -578,25 +580,25 @@ 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; } } @@ -606,17 +608,17 @@ 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 @@ -629,8 +631,8 @@ 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: @@ -659,7 +661,7 @@ } // 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) @@ -818,7 +820,7 @@ 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); @@ -857,7 +859,7 @@ // 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; Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h +++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h @@ -83,7 +83,7 @@ // 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 @@ -266,7 +266,7 @@ 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) { } Index: ps/trunk/source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpRangeManager.cpp +++ ps/trunk/source/simulation2/components/CCmpRangeManager.cpp @@ -39,7 +39,6 @@ #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" @@ -47,13 +46,25 @@ #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); @@ -64,7 +75,7 @@ /** * 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)); @@ -74,7 +85,7 @@ /** * 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++) @@ -87,7 +98,7 @@ * 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; @@ -105,7 +116,7 @@ /** * 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 ); @@ -115,7 +126,7 @@ /** * 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; @@ -125,7 +136,7 @@ /** * 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; } @@ -133,7 +144,7 @@ /** * 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); } @@ -234,7 +245,39 @@ 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 @@ -272,8 +315,8 @@ 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 } }; @@ -298,37 +341,6 @@ }; /** - * 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. @@ -1303,7 +1315,7 @@ return r; // angle = 0 goes in the positive Z direction - u64 precisionSquared = SQUARE_U64_FIXED(entity_pos_t::FromInt(static_cast(TERRAIN_TILE_SIZE)) / 8); + u64 precisionSquared = SQUARE_U64_FIXED(PARABOLIC_RANGE_TOLERANCE); CmpPtr cmpWaterManager(GetSystemEntity()); entity_pos_t waterLevel = cmpWaterManager ? cmpWaterManager->GetWaterLevel(pos.X, pos.Z) : entity_pos_t::Zero(); Index: ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp +++ ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp @@ -834,7 +834,7 @@ } TerritoryOverlay::TerritoryOverlay(CCmpTerritoryManager& manager) : - TerrainTextureOverlay((float)Pathfinding::NAVCELLS_PER_TILE / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE), + TerrainTextureOverlay((float)Pathfinding::NAVCELLS_PER_TERRAIN_TILE / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE), m_TerritoryManager(manager) { } Index: ps/trunk/source/simulation2/components/CCmpUnitMotion.h =================================================================== --- ps/trunk/source/simulation2/components/CCmpUnitMotion.h +++ ps/trunk/source/simulation2/components/CCmpUnitMotion.h @@ -37,7 +37,6 @@ #include "simulation2/serialization/SerializedTypes.h" #include "graphics/Overlay.h" -#include "graphics/Terrain.h" #include "maths/FixedVector2D.h" #include "ps/CLogger.h" #include "ps/Profile.h" @@ -50,38 +49,40 @@ // instead of calling the pathfinder #define DISABLE_PATHFINDER 0 +namespace +{ /** * Min/Max range to restrict short path queries to. (Larger ranges are (much) slower, * smaller ranges might miss some legitimate routes around large obstacles.) * NB: keep the max-range in sync with the vertex pathfinder "move the search space" heuristic. */ -static const entity_pos_t SHORT_PATH_MIN_SEARCH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*3); -static const entity_pos_t SHORT_PATH_MAX_SEARCH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*14); -static const entity_pos_t SHORT_PATH_SEARCH_RANGE_INCREMENT = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*1); -static const u8 SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY = 1; +constexpr entity_pos_t SHORT_PATH_MIN_SEARCH_RANGE = entity_pos_t::FromInt(12 * Pathfinding::NAVCELL_SIZE_INT); +constexpr entity_pos_t SHORT_PATH_MAX_SEARCH_RANGE = entity_pos_t::FromInt(56 * Pathfinding::NAVCELL_SIZE_INT); +constexpr entity_pos_t SHORT_PATH_SEARCH_RANGE_INCREMENT = entity_pos_t::FromInt(4 * Pathfinding::NAVCELL_SIZE_INT); +constexpr u8 SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY = 1; /** * When using the short-pathfinder to rejoin a long-path waypoint, aim for a circle of this radius around the waypoint. */ -static const entity_pos_t SHORT_PATH_LONG_WAYPOINT_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*1); +constexpr entity_pos_t SHORT_PATH_LONG_WAYPOINT_RANGE = entity_pos_t::FromInt(4 * Pathfinding::NAVCELL_SIZE_INT); /** * Minimum distance to goal for a long path request */ -static const entity_pos_t LONG_PATH_MIN_DIST = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*4); +constexpr entity_pos_t LONG_PATH_MIN_DIST = entity_pos_t::FromInt(16 * Pathfinding::NAVCELL_SIZE_INT); /** * If we are this close to our target entity/point, then think about heading * for it in a straight line instead of pathfinding. */ -static const entity_pos_t DIRECT_PATH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*6); +constexpr entity_pos_t DIRECT_PATH_RANGE = entity_pos_t::FromInt(24 * Pathfinding::NAVCELL_SIZE_INT); /** * To avoid recomputing paths too often, have some leeway for target range checks * based on our distance to the target. Increase that incertainty by one navcell * for every this many tiles of distance. */ -static const entity_pos_t TARGET_UNCERTAINTY_MULTIPLIER = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*2); +constexpr entity_pos_t TARGET_UNCERTAINTY_MULTIPLIER = entity_pos_t::FromInt(8 * Pathfinding::NAVCELL_SIZE_INT); /** * When following a known imperfect path (i.e. a path that won't take us in range of our goal @@ -90,7 +91,7 @@ * This is rather arbitrary and mostly for simplicity & optimisation (a better recomputing algorithm * would not need this). */ -static const u8 KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN = 12; +constexpr u8 KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN = 12; /** * When we fail to move this many turns in a row, inform other components that the move will fail. @@ -100,23 +101,24 @@ * this could probably be lowered. * TODO: when unit pushing is implemented, this number can probably be lowered. */ -static const u8 MAX_FAILED_MOVEMENTS = 35; +constexpr u8 MAX_FAILED_MOVEMENTS = 35; /** * When computing paths but failing to move, we want to occasionally alternate pathfinder systems * to avoid getting stuck (the short pathfinder can unstuck the long-range one and vice-versa, depending). */ -static const u8 ALTERNATE_PATH_TYPE_DELAY = 3; -static const u8 ALTERNATE_PATH_TYPE_EVERY = 6; +constexpr u8 ALTERNATE_PATH_TYPE_DELAY = 3; +constexpr u8 ALTERNATE_PATH_TYPE_EVERY = 6; /** * After this many failed computations, start sending "VERY_OBSTRUCTED" messages instead. * Should probably be larger than ALTERNATE_PATH_TYPE_DELAY. */ -static const u8 VERY_OBSTRUCTED_THRESHOLD = 10; +constexpr u8 VERY_OBSTRUCTED_THRESHOLD = 10; -static const CColor OVERLAY_COLOR_LONG_PATH(1, 1, 1, 1); -static const CColor OVERLAY_COLOR_SHORT_PATH(1, 0, 0, 1); +const CColor OVERLAY_COLOR_LONG_PATH(1, 1, 1, 1); +const CColor OVERLAY_COLOR_SHORT_PATH(1, 0, 0, 1); +} // anonymous namespace class CCmpUnitMotion final : public ICmpUnitMotion { @@ -870,7 +872,7 @@ if (m_LongPath.m_Waypoints.size() >= 2) { const Waypoint& firstWpt = m_LongPath.m_Waypoints.back(); - if (CFixedVector2D(firstWpt.x - pos.X, firstWpt.z - pos.Y).CompareLength(fixed::FromInt(TERRAIN_TILE_SIZE)) <= 0) + if (CFixedVector2D(firstWpt.x - pos.X, firstWpt.z - pos.Y).CompareLength(Pathfinding::NAVCELL_SIZE * 4) <= 0) { CmpPtr cmpPathfinder(GetSystemEntity()); ENSURE(cmpPathfinder); @@ -1213,7 +1215,7 @@ // NB: this number is tricky. Make it too high, and units start going down dead ends, which looks odd (#5795) // Make it too low, and they might get stuck behind other obstructed entities. // It also has performance implications because it calls the short-pathfinder. - fixed skipbeyond = std::max(ShortPathSearchRange() / 3, fixed::FromInt(TERRAIN_TILE_SIZE*2)); + fixed skipbeyond = std::max(ShortPathSearchRange() / 3, Pathfinding::NAVCELL_SIZE * 8); if (m_LongPath.m_Waypoints.size() > 1 && (pos - CFixedVector2D(m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z)).CompareLength(skipbeyond) < 0) { @@ -1231,7 +1233,7 @@ // Compute a short path in the general vicinity of the next waypoint, to help pathfinding in crowds. // The goal here is to manage to move in the general direction of our target, not to be super accurate. - fixed radius = Clamp(skipbeyond/3, fixed::FromInt(TERRAIN_TILE_SIZE), fixed::FromInt(TERRAIN_TILE_SIZE*3)); + fixed radius = Clamp(skipbeyond/3, Pathfinding::NAVCELL_SIZE * 4, Pathfinding::NAVCELL_SIZE * 12); PathGoal subgoal = { PathGoal::CIRCLE, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z, radius }; RequestShortPath(pos, subgoal, false); return true; @@ -1559,7 +1561,7 @@ entity_pos_t goalDistance = moveRequest.m_MaxRange * 2 / 3; // multiply by slightly less than 1/sqrt(2) out.type = PathGoal::SQUARE; - entity_pos_t delta = std::max(goalDistance, m_Clearance + entity_pos_t::FromInt(TERRAIN_TILE_SIZE)/16); // ensure it's far enough to not intersect the building itself + entity_pos_t delta = std::max(goalDistance, m_Clearance + entity_pos_t::FromInt(4)/16); // ensure it's far enough to not intersect the building itself out.hw = targetObstruction.hw + delta; out.hh = targetObstruction.hh + delta; } Index: ps/trunk/source/simulation2/components/CCmpUnitMotionManager.h =================================================================== --- ps/trunk/source/simulation2/components/CCmpUnitMotionManager.h +++ ps/trunk/source/simulation2/components/CCmpUnitMotionManager.h @@ -172,8 +172,8 @@ if (!cmpTerrain) return; - size_t size = cmpTerrain->GetVerticesPerSide() - 1; - u16 gridSquareSize = static_cast(size * TERRAIN_TILE_SIZE / 20 + 1); + size_t size = cmpTerrain->GetMapSize(); + u16 gridSquareSize = static_cast(size / 20 + 1); m_MovingUnits.resize(gridSquareSize, gridSquareSize); } Index: ps/trunk/source/simulation2/components/ICmpRangeManager.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpRangeManager.h +++ ps/trunk/source/simulation2/components/ICmpRangeManager.h @@ -1,4 +1,4 @@ -/* 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 @@ -25,8 +25,6 @@ #include "simulation2/helpers/Position.h" #include "simulation2/helpers/Player.h" -#include "graphics/Terrain.h" // for TERRAIN_TILE_SIZE - class FastSpatialSubdivision; /** Index: ps/trunk/source/simulation2/components/tests/test_Pathfinder.h =================================================================== --- ps/trunk/source/simulation2/components/tests/test_Pathfinder.h +++ ps/trunk/source/simulation2/components/tests/test_Pathfinder.h @@ -203,7 +203,7 @@ sim2.LoadDefaultScripts(); sim2.ResetState(); - const entity_pos_t range = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*12); + const entity_pos_t range = entity_pos_t::FromInt(48); CmpPtr cmpObstructionMan(sim2, SYSTEM_ENTITY); CmpPtr cmpPathfinder(sim2, SYSTEM_ENTITY); @@ -405,7 +405,7 @@ stream << " title='length: " << length << "; tiles explored: " << debugSteps << "; time: " << debugTime*1000 << " msec'"; stream << " class='path' points='"; for (size_t i = 0; i < path.m_Waypoints.size(); ++i) - stream << path.m_Waypoints[i].x.ToDouble()*Pathfinding::NAVCELLS_PER_TILE/TERRAIN_TILE_SIZE << "," << path.m_Waypoints[i].z.ToDouble()*Pathfinding::NAVCELLS_PER_TILE/TERRAIN_TILE_SIZE << " "; + stream << path.m_Waypoints[i].x.ToDouble()*Pathfinding::NAVCELL_SIZE_INT << "," << path.m_Waypoints[i].z.ToDouble()*Pathfinding::NAVCELL_SIZE_INT << " "; stream << "'/>\n"; } Index: ps/trunk/source/simulation2/components/tests/test_TerritoryManager.h =================================================================== --- ps/trunk/source/simulation2/components/tests/test_TerritoryManager.h +++ ps/trunk/source/simulation2/components/tests/test_TerritoryManager.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2017 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 @@ -21,6 +21,7 @@ #include "graphics/Terrain.h" #include "graphics/TerritoryBoundary.h" #include "simulation2/helpers/Grid.h" +#include "simulation2/components/ICmpTerritoryManager.h" class TestCmpTerritoryManager : public CxxTest::TestSuite { @@ -49,7 +50,7 @@ TS_ASSERT_EQUALS((player_id_t)7, boundaries[0].owner); TS_ASSERT_EQUALS(false, boundaries[0].blinking); // high bits aren't set by GetGrid - // assumes CELL_SIZE is 2; dealt with in TestBoundaryPointsEqual + // assumes NAVCELLS_PER_TERRITORY_TILE is 8; dealt with in TestBoundaryPointsEqual int expectedPoints[][2] = {{ 4, 8}, {12, 8}, {20, 8}, {28, 8}, {36, 8}, {44, 8}, {48,12}, {48,20}, {48,28}, {44,32}, {36,32}, {28,32}, {20,32}, {12,32}, { 4,32}, @@ -281,10 +282,10 @@ // version of 'points', so that the starting position doesn't need to match exactly. for (size_t i = 0; i < points.size(); i++) { - // the input numbers in expectedPoints are defined under the assumption that CELL_SIZE is 2, so let's include - // a scaling factor to protect against that should CELL_SIZE ever change - TS_ASSERT_DELTA(points[i].X, float(expectedPoints[i][0]) * 4.f / TERRAIN_TILE_SIZE, 1e-7); - TS_ASSERT_DELTA(points[i].Y, float(expectedPoints[i][1]) * 4.f / TERRAIN_TILE_SIZE, 1e-7); + // the input numbers in expectedPoints are defined under the assumption that NAVCELLS_PER_TERRITORY_TILE is 8, so let's include + // a scaling factor to protect against that should NAVCELLS_PER_TERRITORY_TILE ever change + TS_ASSERT_DELTA(points[i].X, float(expectedPoints[i][0]) * 8.f / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE, 1e-7); + TS_ASSERT_DELTA(points[i].Y, float(expectedPoints[i][1]) * 8.f / ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE, 1e-7); } } }; Index: ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h +++ ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h @@ -303,7 +303,7 @@ HierarchicalPathfinder& m_PathfinderHier; HierarchicalOverlay(HierarchicalPathfinder& pathfinderHier) : - TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_PathfinderHier(pathfinderHier) + TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TERRAIN_TILE), m_PathfinderHier(pathfinderHier) { } Index: ps/trunk/source/simulation2/helpers/LongPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/LongPathfinder.h +++ ps/trunk/source/simulation2/helpers/LongPathfinder.h @@ -290,7 +290,7 @@ LongPathfinder& m_Pathfinder; LongOverlay(LongPathfinder& pathfinder) : - TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder) + TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TERRAIN_TILE), m_Pathfinder(pathfinder) { } Index: ps/trunk/source/simulation2/helpers/Pathfinding.h =================================================================== --- ps/trunk/source/simulation2/helpers/Pathfinding.h +++ ps/trunk/source/simulation2/helpers/Pathfinding.h @@ -1,4 +1,4 @@ -/* 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 @@ -122,7 +122,7 @@ u32 data; }; -static const int PASS_CLASS_BITS = 16; +inline constexpr int PASS_CLASS_BITS = 16; typedef u16 NavcellData; // 1 bit per passability class (up to PASS_CLASS_BITS) #define IS_PASSABLE(item, classmask) (((item) & (classmask)) == 0) #define PASS_CLASS_MASK_FROM_INDEX(id) ((pass_class_t)(1u << id)) @@ -137,23 +137,24 @@ * obstructions, all expanded outwards by the radius of the units. * Since units are much smaller than terrain tiles, the nav grid should be * higher resolution than the tiles. - * We therefore split each terrain tile into NxN "nav cells" (for some integer N, + * We therefore split each the world into NxN "nav cells" (for some integer N, * preferably a power of two). */ - const int NAVCELLS_PER_TILE = 4; + inline constexpr fixed NAVCELL_SIZE = fixed::FromInt(1); + inline constexpr int NAVCELL_SIZE_INT = 1; + inline constexpr int NAVCELL_SIZE_LOG2 = 0; /** - * Size of a navcell in metres ( = TERRAIN_TILE_SIZE / NAVCELLS_PER_TILE) + * The terrain grid is coarser, and it is often convenient to convert from one to the other. */ - const fixed NAVCELL_SIZE = fixed::FromInt((int)TERRAIN_TILE_SIZE) / Pathfinding::NAVCELLS_PER_TILE; - const int NAVCELL_SIZE_INT = 1; - const int NAVCELL_SIZE_LOG2 = 0; + inline constexpr int NAVCELLS_PER_TERRAIN_TILE = TERRAIN_TILE_SIZE / NAVCELL_SIZE_INT; + static_assert(TERRAIN_TILE_SIZE % NAVCELL_SIZE_INT == 0, "Terrain tile size is not a multiple of navcell size"); /** * To make sure the long-range pathfinder is more strict than the short-range one, * we need to slightly over-rasterize. So we extend the clearance radius by 1. */ - const entity_pos_t CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1); + inline constexpr entity_pos_t CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1); /** * Compute the navcell indexes on the grid nearest to a given point @@ -167,11 +168,11 @@ } /** - * Returns the position of the center of the given tile + * Returns the position of the center of the given terrain tile */ - inline void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z) + inline void TerrainTileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z) { - cassert(TERRAIN_TILE_SIZE % 2 == 0); + static_assert(TERRAIN_TILE_SIZE % 2 == 0); x = entity_pos_t::FromInt(i*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2); z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2); } Index: ps/trunk/source/simulation2/helpers/Position.h =================================================================== --- ps/trunk/source/simulation2/helpers/Position.h +++ ps/trunk/source/simulation2/helpers/Position.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2010 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 @@ -24,7 +24,7 @@ * @file * Entity coordinate types * - * The basic unit is the "meter". Terrain tiles are TERRAIN_TILE_SIZE (=4) meters square. + * The basic unit is the "meter". * To support deterministic computation across CPU architectures and compilers and * optimisation settings, the C++ simulation code must not use floating-point arithmetic. * We therefore use a fixed-point datatype for representing world positions. Index: ps/trunk/source/simulation2/helpers/VertexPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/VertexPathfinder.h +++ ps/trunk/source/simulation2/helpers/VertexPathfinder.h @@ -1,4 +1,4 @@ -/* 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 @@ -75,7 +75,7 @@ class VertexPathfinder { public: - VertexPathfinder(const u16& mapSize, Grid* const & terrainOnlyGrid) : m_MapSize(mapSize), m_TerrainOnlyGrid(terrainOnlyGrid), m_DebugOverlay(false) {}; + VertexPathfinder(const u16& gridSize, Grid* const & terrainOnlyGrid) : m_GridSize(gridSize), m_TerrainOnlyGrid(terrainOnlyGrid), m_DebugOverlay(false) {}; /** * Compute a precise path from the given point to the goal, and return the set of waypoints. @@ -96,7 +96,7 @@ void DebugRenderEdges(const CSimContext& simContext, bool visible, CFixedVector2D curr, CFixedVector2D npos) const; // References to the Pathfinder for convenience. - const u16& m_MapSize; + const u16& m_GridSize; Grid* const & m_TerrainOnlyGrid; std::atomic m_DebugOverlay; Index: ps/trunk/source/simulation2/helpers/VertexPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/helpers/VertexPathfinder.cpp +++ ps/trunk/source/simulation2/helpers/VertexPathfinder.cpp @@ -1,4 +1,4 @@ -/* 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 @@ -530,10 +530,10 @@ // (this makes it possible to use smaller search ranges, but still find good paths). // Don't do this for the largest ranges: it makes it harder to backtrack, and large search domains // indicate a rather stuck unit, which means having to backtrack is probable. - // (keep this in sync with unitMotion's max-search range). + // (keep this in sync, slightly below unitMotion's max-search range). // (this also ensures symmetrical behaviour for goals inside/outside the max search range). CFixedVector2D toGoal = CFixedVector2D(request.goal.x, request.goal.z) - CFixedVector2D(request.x0, request.z0); - if (toGoal.CompareLength(request.range) >= 0 && request.range < fixed::FromInt(TERRAIN_TILE_SIZE) * 10) + if (toGoal.CompareLength(request.range) >= 0 && request.range < Pathfinding::NAVCELL_SIZE * 46) { fixed toGoalLength = toGoal.Length(); fixed inv = fixed::FromInt(1) / toGoalLength; @@ -667,8 +667,8 @@ // Add terrain obstructions { u16 i0, j0, i1, j1; - Pathfinding::NearestNavcell(rangeXMin, rangeZMin, i0, j0, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE); - Pathfinding::NearestNavcell(rangeXMax, rangeZMax, i1, j1, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE); + Pathfinding::NearestNavcell(rangeXMin, rangeZMin, i0, j0, m_GridSize, m_GridSize); + Pathfinding::NearestNavcell(rangeXMax, rangeZMax, i1, j1, m_GridSize, m_GridSize); AddTerrainEdges(m_Edges, m_Vertexes, i0, j0, i1, j1, request.passClass, *m_TerrainOnlyGrid); }