Index: source/graphics/CameraController.cpp =================================================================== --- source/graphics/CameraController.cpp +++ source/graphics/CameraController.cpp @@ -40,6 +40,7 @@ #include "simulation2/Simulation2.h" #include "simulation2/components/ICmpPosition.h" #include "simulation2/components/ICmpRangeManager.h" +#include "simulation2/helpers/Los.h" extern int g_xres, g_yres; Index: source/graphics/LOSTexture.h =================================================================== --- source/graphics/LOSTexture.h +++ source/graphics/LOSTexture.h @@ -83,7 +83,7 @@ void RecomputeTexture(int unit); size_t GetBitmapSize(size_t w, size_t h, size_t* pitch); - void GenerateBitmap(const ICmpRangeManager::CLosQuerier& los, u8* losData, size_t w, size_t h, size_t pitch); + void GenerateBitmap(const CLosQuerier& los, u8* losData, size_t w, size_t h, size_t pitch); CSimulation2& m_Simulation; Index: source/graphics/LOSTexture.cpp =================================================================== --- source/graphics/LOSTexture.cpp +++ source/graphics/LOSTexture.cpp @@ -32,6 +32,7 @@ #include "simulation2/Simulation2.h" #include "simulation2/components/ICmpRangeManager.h" #include "simulation2/components/ICmpTerrain.h" +#include "simulation2/helpers/Los.h" /* @@ -341,7 +342,7 @@ if (!cmpRangeManager) return; - ICmpRangeManager::CLosQuerier los(cmpRangeManager->GetLosQuerier(g_Game->GetSimulation2()->GetSimContext().GetCurrentDisplayedPlayer())); + CLosQuerier los(cmpRangeManager->GetLosQuerier(g_Game->GetSimulation2()->GetSimContext().GetCurrentDisplayedPlayer())); GenerateBitmap(los, &losData[0], m_MapSize, m_MapSize, pitch); @@ -363,7 +364,7 @@ return *pitch * (h + g_BlurSize - 1); } -void CLOSTexture::GenerateBitmap(const ICmpRangeManager::CLosQuerier& los, u8* losData, size_t w, size_t h, size_t pitch) +void CLOSTexture::GenerateBitmap(const CLosQuerier& los, u8* losData, size_t w, size_t h, size_t pitch) { u8 *dataPtr = losData; Index: source/graphics/TerritoryBoundary.cpp =================================================================== --- source/graphics/TerritoryBoundary.cpp +++ source/graphics/TerritoryBoundary.cpp @@ -21,6 +21,7 @@ #include // for reverse #include "graphics/Terrain.h" +#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/Pathfinding.h" #include "simulation2/components/ICmpTerritoryManager.h" Index: source/graphics/TerritoryTexture.cpp =================================================================== --- source/graphics/TerritoryTexture.cpp +++ source/graphics/TerritoryTexture.cpp @@ -25,6 +25,7 @@ #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" Index: source/graphics/tests/test_LOSTexture.h =================================================================== --- source/graphics/tests/test_LOSTexture.h +++ source/graphics/tests/test_LOSTexture.h @@ -21,6 +21,7 @@ #include "lib/timer.h" #include "scriptinterface/ScriptInterface.h" #include "simulation2/Simulation2.h" +#include "simulation2/helpers/Los.h" class TestLOSTexture : public CxxTest::TestSuite { @@ -50,7 +51,7 @@ // LosState::MASK should be cmpRanageManager->GetSharedLosMask(1), // but that would mean adding a huge mock component for this and it // should always be LosState::MASK for player 1 (as the other players are bit-shifted). - ICmpRangeManager::CLosQuerier los((u32)LosState::MASK, inputDataVec, size); + CLosQuerier los((u32)LosState::MASK, inputDataVec, size); std::vector losData; size_t pitch; @@ -75,7 +76,7 @@ // LosState::MASK should be cmpRanageManager->GetSharedLosMask(1), // but that would mean adding a huge mock component for this and it // should always be LosState::MASK for player 1 (as the other players are bit-shifted). - ICmpRangeManager::CLosQuerier los((u32)LosState::MASK, inputDataVec, size); + CLosQuerier los((u32)LosState::MASK, inputDataVec, size); size_t reps = 128; double t = timer_Time(); Index: source/gui/ObjectTypes/CMiniMap.cpp =================================================================== --- source/gui/ObjectTypes/CMiniMap.cpp +++ source/gui/ObjectTypes/CMiniMap.cpp @@ -44,8 +44,9 @@ #include "renderer/RenderingOptions.h" #include "renderer/WaterManager.h" #include "scriptinterface/ScriptInterface.h" -#include "simulation2/components/ICmpMinimap.h" #include "simulation2/Simulation2.h" +#include "simulation2/components/ICmpMinimap.h" +#include "simulation2/helpers/Los.h" #include "simulation2/system/ParamNode.h" #include Index: source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- source/simulation2/components/CCmpObstructionManager.cpp +++ source/simulation2/components/CCmpObstructionManager.cpp @@ -25,6 +25,7 @@ #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" Index: source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- source/simulation2/components/CCmpPathfinder_Common.h +++ source/simulation2/components/CCmpPathfinder_Common.h @@ -37,6 +37,7 @@ #include "ps/CLogger.h" #include "renderer/TerrainOverlay.h" #include "simulation2/components/ICmpObstructionManager.h" +#include "simulation2/helpers/Grid.h" class HierarchicalPathfinder; Index: source/simulation2/components/CCmpProjectileManager.cpp =================================================================== --- source/simulation2/components/CCmpProjectileManager.cpp +++ source/simulation2/components/CCmpProjectileManager.cpp @@ -25,6 +25,7 @@ #include "ICmpPosition.h" #include "ICmpRangeManager.h" #include "ICmpTerrain.h" +#include "simulation2/helpers/Los.h" #include "simulation2/MessageTypes.h" #include "graphics/Frustum.h" @@ -114,7 +115,7 @@ virtual void RemoveProjectile(uint32_t); void RenderModel(CModelAbstract& model, const CVector3D& position, SceneCollector& collector, const CFrustum& frustum, bool culling, - const ICmpRangeManager::CLosQuerier& los, bool losRevealAll) const; + const CLosQuerier& los, bool losRevealAll) const; private: struct Projectile @@ -358,7 +359,7 @@ } void CCmpProjectileManager::RenderModel(CModelAbstract& model, const CVector3D& position, SceneCollector& collector, - const CFrustum& frustum, bool culling, const ICmpRangeManager::CLosQuerier& los, bool losRevealAll) const + const CFrustum& frustum, bool culling, const CLosQuerier& los, bool losRevealAll) const { // Don't display objects outside the visible area ssize_t posi = (ssize_t)(0.5f + position.X / TERRAIN_TILE_SIZE); @@ -380,7 +381,7 @@ { CmpPtr cmpRangeManager(GetSystemEntity()); int player = GetSimContext().GetCurrentDisplayedPlayer(); - ICmpRangeManager::CLosQuerier los(cmpRangeManager->GetLosQuerier(player)); + CLosQuerier los(cmpRangeManager->GetLosQuerier(player)); bool losRevealAll = cmpRangeManager->GetLosRevealAll(player); for (const Projectile& projectile : m_Projectiles) Index: source/simulation2/components/CCmpRallyPointRenderer.h =================================================================== --- source/simulation2/components/CCmpRallyPointRenderer.h +++ source/simulation2/components/CCmpRallyPointRenderer.h @@ -29,7 +29,6 @@ #include "simulation2/components/ICmpPlayer.h" #include "simulation2/components/ICmpPlayerManager.h" #include "simulation2/components/ICmpPosition.h" -#include "simulation2/components/ICmpRangeManager.h" #include "simulation2/components/ICmpTerrain.h" #include "simulation2/components/ICmpVisual.h" #include "simulation2/components/ICmpWaterManager.h" Index: source/simulation2/components/CCmpRallyPointRenderer.cpp =================================================================== --- source/simulation2/components/CCmpRallyPointRenderer.cpp +++ source/simulation2/components/CCmpRallyPointRenderer.cpp @@ -18,6 +18,9 @@ #include "precompiled.h" #include "CCmpRallyPointRenderer.h" +#include "simulation2/components/ICmpRangeManager.h" +#include "simulation2/helpers/Los.h" + std::string CCmpRallyPointRenderer::GetSchema() { return @@ -814,7 +817,7 @@ CmpPtr cmpRangeMgr(GetSystemEntity()); player_id_t currentPlayer = static_cast(GetSimContext().GetCurrentDisplayedPlayer()); - ICmpRangeManager::CLosQuerier losQuerier(cmpRangeMgr->GetLosQuerier(currentPlayer)); + CLosQuerier losQuerier(cmpRangeMgr->GetLosQuerier(currentPlayer)); // Go through the path node list, comparing each node's visibility with the previous one. If it changes, end the current segment and start // a new one at the next point. Index: source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- source/simulation2/components/CCmpRangeManager.cpp +++ source/simulation2/components/CCmpRangeManager.cpp @@ -32,6 +32,7 @@ #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" Index: source/simulation2/components/ICmpObstructionManager.h =================================================================== --- source/simulation2/components/ICmpObstructionManager.h +++ source/simulation2/components/ICmpObstructionManager.h @@ -25,6 +25,9 @@ #include "maths/FixedVector2D.h" class IObstructionTestFilter; +template +class Grid; +struct GridUpdateInformation; /** * Obstruction manager: provides efficient spatial queries over objects in the world. Index: source/simulation2/components/ICmpRangeManager.h =================================================================== --- source/simulation2/components/ICmpRangeManager.h +++ source/simulation2/components/ICmpRangeManager.h @@ -22,7 +22,6 @@ #include "maths/FixedVector2D.h" #include "simulation2/system/Interface.h" -#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/Position.h" #include "simulation2/helpers/Player.h" @@ -43,13 +42,13 @@ VISIBLE = 2 }; -enum class LosState : u8 -{ - UNEXPLORED = 0, - EXPLORED = 1, - VISIBLE = 2, - MASK = 3 -}; +/** + * The same principle applies to CLosQuerier, but to avoid recompiling TUs (a fortiori headers) + * dependent on RangeManager but not CLosQuerier when CLosQuerier changes, + * we define it in another file. Code using LOS will then explicitly include the LOS header + * which makes sense anyways. + */ +class CLosQuerier; /** * Provides efficient range-based queries of the game world, @@ -244,93 +243,6 @@ virtual void SetEntityFlag(entity_id_t ent, const std::string& identifier, bool value) = 0; - /** - * Object providing efficient abstracted access to the LOS state. - * This depends on some implementation details of CCmpRangeManager. - * - * This *ignores* the GetLosRevealAll flag - callers should check that explicitly. - */ - class CLosQuerier - { - private: - friend class CCmpRangeManager; - friend class TestLOSTexture; - - CLosQuerier(u32 playerMask, const Grid& data, ssize_t verticesPerSide) : - m_Data(data), m_PlayerMask(playerMask), m_VerticesPerSide(verticesPerSide) - { - } - - const CLosQuerier& operator=(const CLosQuerier&); // not implemented - - public: - /** - * Returns whether the given vertex is visible (i.e. is within a unit's LOS). - */ - inline bool IsVisible(ssize_t i, ssize_t j) const - { - if (!(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide)) - return false; - - // Check high bit of each bit-pair - if ((m_Data.get(i, j) & m_PlayerMask) & 0xAAAAAAAAu) - return true; - else - return false; - } - - /** - * Returns whether the given vertex is explored (i.e. was (or still is) within a unit's LOS). - */ - inline bool IsExplored(ssize_t i, ssize_t j) const - { - if (!(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide)) - return false; - - // Check low bit of each bit-pair - if ((m_Data.get(i, j) & m_PlayerMask) & 0x55555555u) - return true; - else - return false; - } - - /** - * Returns whether the given vertex is visible (i.e. is within a unit's LOS). - * i and j must be in the range [0, verticesPerSide), else behaviour is undefined. - */ - inline bool IsVisible_UncheckedRange(ssize_t i, ssize_t j) const - { -#ifndef NDEBUG - ENSURE(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide); -#endif - // Check high bit of each bit-pair - if ((m_Data.get(i, j) & m_PlayerMask) & 0xAAAAAAAAu) - return true; - else - return false; - } - - /** - * Returns whether the given vertex is explored (i.e. was (or still is) within a unit's LOS). - * i and j must be in the range [0, verticesPerSide), else behaviour is undefined. - */ - inline bool IsExplored_UncheckedRange(ssize_t i, ssize_t j) const - { -#ifndef NDEBUG - ENSURE(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide); -#endif - // Check low bit of each bit-pair - if ((m_Data.get(i, j) & m_PlayerMask) & 0x55555555u) - return true; - else - return false; - } - - private: - u32 m_PlayerMask; - const Grid& m_Data; - ssize_t m_VerticesPerSide; - }; ////////////////////////////////////////////////////////////////// //// LOS interface below this line //// ////////////////////////////////////////////////////////////////// Index: source/simulation2/components/tests/test_HierPathfinder.h =================================================================== --- source/simulation2/components/tests/test_HierPathfinder.h +++ source/simulation2/components/tests/test_HierPathfinder.h @@ -20,6 +20,7 @@ #define TEST #include "maths/Vector2D.h" +#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/HierarchicalPathfinder.h" class TestHierarchicalPathfinder : public CxxTest::TestSuite Index: source/simulation2/components/tests/test_Pathfinder.h =================================================================== --- source/simulation2/components/tests/test_Pathfinder.h +++ source/simulation2/components/tests/test_Pathfinder.h @@ -19,6 +19,7 @@ #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/components/ICmpPathfinder.h" +#include "simulation2/helpers/Grid.h" #include "graphics/MapReader.h" #include "graphics/Terrain.h" Index: source/simulation2/helpers/HierarchicalPathfinder.cpp =================================================================== --- source/simulation2/helpers/HierarchicalPathfinder.cpp +++ source/simulation2/helpers/HierarchicalPathfinder.cpp @@ -23,6 +23,8 @@ #include "ps/Profile.h" #include "renderer/Scene.h" +#include "simulation2/helpers/Grid.h" + // Find the root ID of a region, used by InitRegions inline u16 RootID(u16 x, const std::vector& v) { Index: source/simulation2/helpers/LongPathfinder.h =================================================================== --- source/simulation2/helpers/LongPathfinder.h +++ source/simulation2/helpers/LongPathfinder.h @@ -23,6 +23,7 @@ #include "graphics/Overlay.h" #include "renderer/Scene.h" #include "renderer/TerrainOverlay.h" +#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/PriorityQueue.h" /** Index: source/simulation2/helpers/Los.h =================================================================== --- /dev/null +++ source/simulation2/helpers/Los.h @@ -0,0 +1,121 @@ +/* Copyright (C) 2020 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_LOS +#define INCLUDED_LOS + +// It doesn't seem worth moving the implementation to c++ and early-declaring Grid +// since files must include "Los.h" explicitly, and that's only done in .cpp files. +#include "Grid.h" + +enum class LosState : u8 +{ + UNEXPLORED = 0, + EXPLORED = 1, + VISIBLE = 2, + MASK = 3 +}; + +/** + * Object providing efficient abstracted access to the LOS state. + * This depends on some implementation details of CCmpRangeManager. + * + * This *ignores* the GetLosRevealAll flag - callers should check that explicitly. + */ +class CLosQuerier +{ +private: + friend class CCmpRangeManager; + friend class TestLOSTexture; + + CLosQuerier(u32 playerMask, const Grid& data, ssize_t verticesPerSide) : + m_Data(data), m_PlayerMask(playerMask), m_VerticesPerSide(verticesPerSide) + { + } + + const CLosQuerier& operator=(const CLosQuerier&); // not implemented + +public: + /** + * Returns whether the given vertex is visible (i.e. is within a unit's LOS). + */ + inline bool IsVisible(ssize_t i, ssize_t j) const + { + if (!(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide)) + return false; + + // Check high bit of each bit-pair + if ((m_Data.get(i, j) & m_PlayerMask) & 0xAAAAAAAAu) + return true; + else + return false; + } + + /** + * Returns whether the given vertex is explored (i.e. was (or still is) within a unit's LOS). + */ + inline bool IsExplored(ssize_t i, ssize_t j) const + { + if (!(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide)) + return false; + + // Check low bit of each bit-pair + if ((m_Data.get(i, j) & m_PlayerMask) & 0x55555555u) + return true; + else + return false; + } + + /** + * Returns whether the given vertex is visible (i.e. is within a unit's LOS). + * i and j must be in the range [0, verticesPerSide), else behaviour is undefined. + */ + inline bool IsVisible_UncheckedRange(ssize_t i, ssize_t j) const + { +#ifndef NDEBUG + ENSURE(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide); +#endif + // Check high bit of each bit-pair + if ((m_Data.get(i, j) & m_PlayerMask) & 0xAAAAAAAAu) + return true; + else + return false; + } + + /** + * Returns whether the given vertex is explored (i.e. was (or still is) within a unit's LOS). + * i and j must be in the range [0, verticesPerSide), else behaviour is undefined. + */ + inline bool IsExplored_UncheckedRange(ssize_t i, ssize_t j) const + { +#ifndef NDEBUG + ENSURE(i >= 0 && j >= 0 && i < m_VerticesPerSide && j < m_VerticesPerSide); +#endif + // Check low bit of each bit-pair + if ((m_Data.get(i, j) & m_PlayerMask) & 0x55555555u) + return true; + else + return false; + } + +private: + u32 m_PlayerMask; + const Grid& m_Data; + ssize_t m_VerticesPerSide; +}; + +#endif // INCLUDED_LOS Index: source/simulation2/helpers/Pathfinding.h =================================================================== --- source/simulation2/helpers/Pathfinding.h +++ source/simulation2/helpers/Pathfinding.h @@ -18,16 +18,17 @@ #ifndef INCLUDED_PATHFINDING #define INCLUDED_PATHFINDING +#include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "ps/CLogger.h" #include "simulation2/system/Entity.h" #include "simulation2/system/ParamNode.h" -#include "graphics/Terrain.h" -#include "Grid.h" #include "PathGoal.h" typedef u16 pass_class_t; +template +class Grid; struct LongPathRequest { @@ -184,99 +185,8 @@ /* * Checks that the line (x0,z0)-(x1,z1) does not intersect any impassable navcells. */ - inline bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, - pass_class_t passClass, const Grid& grid) - { - // We shouldn't allow lines between diagonally-adjacent navcells. - // It doesn't matter whether we allow lines precisely along the edge - // of an impassable navcell. - - // To rasterise the line: - // If the line is (e.g.) aiming up-right, then we start at the navcell - // containing the start point and the line must either end in that navcell - // or else exit along the top edge or the right edge (or through the top-right corner, - // which we'll arbitrary treat as the horizontal edge). - // So we jump into the adjacent navcell across that edge, and continue. - - // To handle the special case of units that are stuck on impassable cells, - // we allow them to move from an impassable to a passable cell (but not - // vice versa). - - u16 i0, j0, i1, j1; - NearestNavcell(x0, z0, i0, j0, grid.m_W, grid.m_H); - NearestNavcell(x1, z1, i1, j1, grid.m_W, grid.m_H); - - // Find which direction the line heads in - int di = (i0 < i1 ? +1 : i1 < i0 ? -1 : 0); - int dj = (j0 < j1 ? +1 : j1 < j0 ? -1 : 0); - - u16 i = i0; - u16 j = j0; - - bool currentlyOnImpassable = !IS_PASSABLE(grid.get(i0, j0), passClass); - - while (true) - { - // Make sure we are still in the limits - ENSURE( - ((di > 0 && i0 <= i && i <= i1) || (di < 0 && i1 <= i && i <= i0) || (di == 0 && i == i0)) && - ((dj > 0 && j0 <= j && j <= j1) || (dj < 0 && j1 <= j && j <= j0) || (dj == 0 && j == j0))); - - // Fail if we're moving onto an impassable navcell - bool passable = IS_PASSABLE(grid.get(i, j), passClass); - if (passable) - currentlyOnImpassable = false; - else if (!currentlyOnImpassable) - return false; - - // Succeed if we're at the target - if (i == i1 && j == j1) - return true; - - // If we can only move horizontally/vertically, then just move in that direction - // If we are reaching the limits, we can go straight to the end - if (di == 0 || i == i1) - { - j += dj; - continue; - } - else if (dj == 0 || j == j1) - { - i += di; - continue; - } - - // Otherwise we need to check which cell to move into: - - // Check whether the line intersects the horizontal (top/bottom) edge of - // the current navcell. - // Horizontal edge is (i, j + (dj>0?1:0)) .. (i + 1, j + (dj>0?1:0)) - // Since we already know the line is moving from this navcell into a different - // navcell, we simply need to test that the edge's endpoints are not both on the - // same side of the line. - - // If we are crossing exactly a vertex of the grid, we will get dota or dotb equal - // to 0. In that case we arbitrarily choose to move of dj. - // This only works because we handle the case (i == i1 || j == j1) beforehand. - // Otherwise we could go outside the j limits and never reach the final navcell. - - entity_pos_t xia = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE); - entity_pos_t xib = entity_pos_t::FromInt(i+1).Multiply(Pathfinding::NAVCELL_SIZE); - entity_pos_t zj = entity_pos_t::FromInt(j + (dj+1)/2).Multiply(Pathfinding::NAVCELL_SIZE); - - CFixedVector2D perp = CFixedVector2D(x1 - x0, z1 - z0).Perpendicular(); - entity_pos_t dota = (CFixedVector2D(xia, zj) - CFixedVector2D(x0, z0)).Dot(perp); - entity_pos_t dotb = (CFixedVector2D(xib, zj) - CFixedVector2D(x0, z0)).Dot(perp); - - // If the horizontal edge is fully on one side of the line, so the line doesn't - // intersect it, we should move across the vertical edge instead - if ((dota < entity_pos_t::Zero() && dotb < entity_pos_t::Zero()) || - (dota > entity_pos_t::Zero() && dotb > entity_pos_t::Zero())) - i += di; - else - j += dj; - } - } + bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, + pass_class_t passClass, const Grid& grid); } /* @@ -303,74 +213,7 @@ class PathfinderPassability { public: - PathfinderPassability(pass_class_t mask, const CParamNode& node) : - m_Mask(mask) - { - if (node.GetChild("MinWaterDepth").IsOk()) - m_MinDepth = node.GetChild("MinWaterDepth").ToFixed(); - else - m_MinDepth = std::numeric_limits::min(); - - if (node.GetChild("MaxWaterDepth").IsOk()) - m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed(); - else - m_MaxDepth = std::numeric_limits::max(); - - if (node.GetChild("MaxTerrainSlope").IsOk()) - m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed(); - else - m_MaxSlope = std::numeric_limits::max(); - - if (node.GetChild("MinShoreDistance").IsOk()) - m_MinShore = node.GetChild("MinShoreDistance").ToFixed(); - else - m_MinShore = std::numeric_limits::min(); - - if (node.GetChild("MaxShoreDistance").IsOk()) - m_MaxShore = node.GetChild("MaxShoreDistance").ToFixed(); - else - m_MaxShore = std::numeric_limits::max(); - - if (node.GetChild("Clearance").IsOk()) - { - m_Clearance = node.GetChild("Clearance").ToFixed(); - - /* According to Philip who designed the original doc (in docs/pathfinder.pdf), - * clearance should usually be integer to ensure consistent behavior when rasterizing - * the passability map. - * This seems doubtful to me and my pathfinder fix makes having a clearance of 0.8 quite convenient - * so I comment out this check, but leave it here for the purpose of documentation should a bug arise. - - if (!(m_Clearance % Pathfinding::NAVCELL_SIZE).IsZero()) - { - // If clearance isn't an integer number of navcells then we'll - // probably get weird behaviour when expanding the navcell grid - // by clearance, vs expanding static obstructions by clearance - LOGWARNING("Pathfinder passability class has clearance %f, should be multiple of %f", - m_Clearance.ToFloat(), Pathfinding::NAVCELL_SIZE.ToFloat()); - }*/ - } - else - m_Clearance = fixed::Zero(); - - if (node.GetChild("Obstructions").IsOk()) - { - std::wstring obstructions = node.GetChild("Obstructions").ToString(); - if (obstructions == L"none") - m_Obstructions = NONE; - else if (obstructions == L"pathfinding") - m_Obstructions = PATHFINDING; - else if (obstructions == L"foundation") - m_Obstructions = FOUNDATION; - else - { - LOGERROR("Invalid value for Obstructions in pathfinder.xml for pass class %d", mask); - m_Obstructions = NONE; - } - } - else - m_Obstructions = NONE; - } + PathfinderPassability(pass_class_t mask, const CParamNode& node); bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) const { Index: source/simulation2/helpers/Pathfinding.cpp =================================================================== --- /dev/null +++ source/simulation2/helpers/Pathfinding.cpp @@ -0,0 +1,188 @@ +/* Copyright (C) 2018 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 "Pathfinding.h" + +#include "graphics/Terrain.h" +#include "Grid.h" + +namespace Pathfinding +{ + bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, + pass_class_t passClass, const Grid& grid) + { + // We shouldn't allow lines between diagonally-adjacent navcells. + // It doesn't matter whether we allow lines precisely along the edge + // of an impassable navcell. + + // To rasterise the line: + // If the line is (e.g.) aiming up-right, then we start at the navcell + // containing the start point and the line must either end in that navcell + // or else exit along the top edge or the right edge (or through the top-right corner, + // which we'll arbitrary treat as the horizontal edge). + // So we jump into the adjacent navcell across that edge, and continue. + + // To handle the special case of units that are stuck on impassable cells, + // we allow them to move from an impassable to a passable cell (but not + // vice versa). + + u16 i0, j0, i1, j1; + NearestNavcell(x0, z0, i0, j0, grid.m_W, grid.m_H); + NearestNavcell(x1, z1, i1, j1, grid.m_W, grid.m_H); + + // Find which direction the line heads in + int di = (i0 < i1 ? +1 : i1 < i0 ? -1 : 0); + int dj = (j0 < j1 ? +1 : j1 < j0 ? -1 : 0); + + u16 i = i0; + u16 j = j0; + + bool currentlyOnImpassable = !IS_PASSABLE(grid.get(i0, j0), passClass); + + while (true) + { + // Make sure we are still in the limits + ENSURE( + ((di > 0 && i0 <= i && i <= i1) || (di < 0 && i1 <= i && i <= i0) || (di == 0 && i == i0)) && + ((dj > 0 && j0 <= j && j <= j1) || (dj < 0 && j1 <= j && j <= j0) || (dj == 0 && j == j0))); + + // Fail if we're moving onto an impassable navcell + bool passable = IS_PASSABLE(grid.get(i, j), passClass); + if (passable) + currentlyOnImpassable = false; + else if (!currentlyOnImpassable) + return false; + + // Succeed if we're at the target + if (i == i1 && j == j1) + return true; + + // If we can only move horizontally/vertically, then just move in that direction + // If we are reaching the limits, we can go straight to the end + if (di == 0 || i == i1) + { + j += dj; + continue; + } + else if (dj == 0 || j == j1) + { + i += di; + continue; + } + + // Otherwise we need to check which cell to move into: + + // Check whether the line intersects the horizontal (top/bottom) edge of + // the current navcell. + // Horizontal edge is (i, j + (dj>0?1:0)) .. (i + 1, j + (dj>0?1:0)) + // Since we already know the line is moving from this navcell into a different + // navcell, we simply need to test that the edge's endpoints are not both on the + // same side of the line. + + // If we are crossing exactly a vertex of the grid, we will get dota or dotb equal + // to 0. In that case we arbitrarily choose to move of dj. + // This only works because we handle the case (i == i1 || j == j1) beforehand. + // Otherwise we could go outside the j limits and never reach the final navcell. + + entity_pos_t xia = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE); + entity_pos_t xib = entity_pos_t::FromInt(i+1).Multiply(Pathfinding::NAVCELL_SIZE); + entity_pos_t zj = entity_pos_t::FromInt(j + (dj+1)/2).Multiply(Pathfinding::NAVCELL_SIZE); + + CFixedVector2D perp = CFixedVector2D(x1 - x0, z1 - z0).Perpendicular(); + entity_pos_t dota = (CFixedVector2D(xia, zj) - CFixedVector2D(x0, z0)).Dot(perp); + entity_pos_t dotb = (CFixedVector2D(xib, zj) - CFixedVector2D(x0, z0)).Dot(perp); + + // If the horizontal edge is fully on one side of the line, so the line doesn't + // intersect it, we should move across the vertical edge instead + if ((dota < entity_pos_t::Zero() && dotb < entity_pos_t::Zero()) || + (dota > entity_pos_t::Zero() && dotb > entity_pos_t::Zero())) + i += di; + else + j += dj; + } + } +} + +PathfinderPassability::PathfinderPassability(pass_class_t mask, const CParamNode& node) : m_Mask(mask) +{ + if (node.GetChild("MinWaterDepth").IsOk()) + m_MinDepth = node.GetChild("MinWaterDepth").ToFixed(); + else + m_MinDepth = std::numeric_limits::min(); + + if (node.GetChild("MaxWaterDepth").IsOk()) + m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed(); + else + m_MaxDepth = std::numeric_limits::max(); + + if (node.GetChild("MaxTerrainSlope").IsOk()) + m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed(); + else + m_MaxSlope = std::numeric_limits::max(); + + if (node.GetChild("MinShoreDistance").IsOk()) + m_MinShore = node.GetChild("MinShoreDistance").ToFixed(); + else + m_MinShore = std::numeric_limits::min(); + + if (node.GetChild("MaxShoreDistance").IsOk()) + m_MaxShore = node.GetChild("MaxShoreDistance").ToFixed(); + else + m_MaxShore = std::numeric_limits::max(); + + if (node.GetChild("Clearance").IsOk()) + { + m_Clearance = node.GetChild("Clearance").ToFixed(); + + /* According to Philip who designed the original doc (in docs/pathfinder.pdf), + * clearance should usually be integer to ensure consistent behavior when rasterizing + * the passability map. + * This seems doubtful to me and my pathfinder fix makes having a clearance of 0.8 quite convenient + * so I comment out this check, but leave it here for the purpose of documentation should a bug arise. + + if (!(m_Clearance % Pathfinding::NAVCELL_SIZE).IsZero()) + { + // If clearance isn't an integer number of navcells then we'll + // probably get weird behaviour when expanding the navcell grid + // by clearance, vs expanding static obstructions by clearance + LOGWARNING("Pathfinder passability class has clearance %f, should be multiple of %f", + m_Clearance.ToFloat(), Pathfinding::NAVCELL_SIZE.ToFloat()); + }*/ + } + else + m_Clearance = fixed::Zero(); + + if (node.GetChild("Obstructions").IsOk()) + { + std::wstring obstructions = node.GetChild("Obstructions").ToString(); + if (obstructions == L"none") + m_Obstructions = NONE; + else if (obstructions == L"pathfinding") + m_Obstructions = PATHFINDING; + else if (obstructions == L"foundation") + m_Obstructions = FOUNDATION; + else + { + LOGERROR("Invalid value for Obstructions in pathfinder.xml for pass class %d", mask); + m_Obstructions = NONE; + } + } + else + m_Obstructions = NONE; +} Index: source/simulation2/helpers/VertexPathfinder.cpp =================================================================== --- source/simulation2/helpers/VertexPathfinder.cpp +++ source/simulation2/helpers/VertexPathfinder.cpp @@ -38,6 +38,7 @@ #include "ps/Profile.h" #include "renderer/Scene.h" #include "simulation2/components/ICmpObstructionManager.h" +#include "simulation2/helpers/Grid.h" #include "simulation2/helpers/PriorityQueue.h" #include "simulation2/helpers/Render.h" #include "simulation2/system/SimContext.h"