Index: ps/trunk/source/simulation2/components/CCmpAIManager.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpAIManager.cpp +++ ps/trunk/source/simulation2/components/CCmpAIManager.cpp @@ -38,6 +38,7 @@ #include "simulation2/components/ICmpRangeManager.h" #include "simulation2/components/ICmpTemplateManager.h" #include "simulation2/components/ICmpTerritoryManager.h" +#include "simulation2/helpers/HierarchicalPathfinder.h" #include "simulation2/helpers/LongPathfinder.h" #include "simulation2/serialization/DebugSerializer.h" #include "simulation2/serialization/StdDeserializer.h" @@ -331,7 +332,7 @@ { WaypointPath ret; PathGoal pathGoal = { PathGoal::POINT, goal.X, goal.Y }; - m_LongPathfinder.ComputePath(pos.X, pos.Y, pathGoal, passClass, ret); + m_LongPathfinder.ComputePath(m_HierarchicalPathfinder, pos.X, pos.Y, pathGoal, passClass, ret); for (Waypoint& wp : ret.m_Waypoints) waypoints.emplace_back(wp.x, wp.z); @@ -501,7 +502,8 @@ m_NonPathfindingPassClasses = nonPathfindingPassClassMasks; m_PathfindingPassClasses = pathfindingPassClassMasks; - m_LongPathfinder.Reload(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks); + m_LongPathfinder.Reload(&m_PassabilityMap); + m_HierarchicalPathfinder.Recompute(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks); if (m_HasSharedComponent) { @@ -533,9 +535,15 @@ m_PassabilityMap = passabilityMap; if (globallyDirty) - m_LongPathfinder.Reload(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks); + { + m_LongPathfinder.Reload(&m_PassabilityMap); + m_HierarchicalPathfinder.Recompute(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks); + } else - m_LongPathfinder.Update(&m_PassabilityMap, dirtinessGrid); + { + m_LongPathfinder.Update(&m_PassabilityMap); + m_HierarchicalPathfinder.Update(&m_PassabilityMap, dirtinessGrid); + } JSContext* cx = m_ScriptInterface->GetContext(); if (dimensionChange || justDeserialized) @@ -802,7 +810,8 @@ deserializer.NumberU16_Unbounded("pathfinder grid h", mapH); m_PassabilityMap = Grid(mapW, mapH); deserializer.RawBytes("pathfinder grid data", (u8*)m_PassabilityMap.m_Data, mapW*mapH*sizeof(NavcellData)); - m_LongPathfinder.Reload(&m_PassabilityMap, m_NonPathfindingPassClasses, m_PathfindingPassClasses); + m_LongPathfinder.Reload(&m_PassabilityMap); + m_HierarchicalPathfinder.Recompute(&m_PassabilityMap, m_NonPathfindingPassClasses, m_PathfindingPassClasses); } int getPlayerSize() @@ -922,6 +931,7 @@ std::map m_NonPathfindingPassClasses; std::map m_PathfindingPassClasses; + HierarchicalPathfinder m_HierarchicalPathfinder; LongPathfinder m_LongPathfinder; bool m_CommandsComputed; Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp +++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp @@ -34,6 +34,8 @@ #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/Rasterize.h" #include "simulation2/helpers/VertexPathfinder.h" #include "simulation2/serialization/SerializeTemplates.h" @@ -55,6 +57,8 @@ m_SameTurnMovesCount = 0; m_VertexPathfinder = std::unique_ptr(new VertexPathfinder(m_MapSize, m_TerrainOnlyGrid)); + m_LongPathfinder = std::unique_ptr(new LongPathfinder()); + m_PathfinderHier = std::unique_ptr(new HierarchicalPathfinder()); // Register Relax NG validator CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng"); @@ -188,28 +192,28 @@ void CCmpPathfinder::RenderSubmit(SceneCollector& collector) { m_VertexPathfinder->RenderSubmit(collector); - m_LongPathfinder.HierarchicalRenderSubmit(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(x0, z0, goal, passClass); + m_LongPathfinder->SetDebugPath(*m_PathfinderHier, x0, z0, goal, passClass); } void CCmpPathfinder::SetDebugOverlay(bool enabled) { m_VertexPathfinder->SetDebugOverlay(enabled); - m_LongPathfinder.SetDebugOverlay(enabled); + m_LongPathfinder->SetDebugOverlay(enabled); } void CCmpPathfinder::SetHierDebugOverlay(bool enabled) { - m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext()); + m_PathfinderHier->SetDebugOverlay(enabled, &GetSimContext()); } void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid& grid) const { - m_LongPathfinder.GetDebugData(steps, time, grid); + m_LongPathfinder->GetDebugData(steps, time, grid); } void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass) @@ -534,15 +538,19 @@ // Add obstructions onto the grid cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty); - // Update the long-range pathfinder + // Update the long-range and hierarchical pathfinders. if (m_DirtinessInformation.globallyDirty) { std::map nonPathfindingPassClasses, pathfindingPassClasses; GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses); - m_LongPathfinder.Reload(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses); + m_LongPathfinder->Reload(m_Grid); + m_PathfinderHier->Recompute(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses); } else - m_LongPathfinder.Update(m_Grid, m_DirtinessInformation.dirtinessGrid); + { + 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); @@ -695,6 +703,12 @@ ////////////////////////////////////////////////////////// + +void CCmpPathfinder::ComputePath(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); +} + u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify) { AsyncLongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify }; 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 @@ -37,8 +37,10 @@ #include "ps/CLogger.h" #include "renderer/TerrainOverlay.h" #include "simulation2/components/ICmpObstructionManager.h" -#include "simulation2/helpers/LongPathfinder.h" + +class HierarchicalPathfinder; +class LongPathfinder; class VertexPathfinder; class SceneCollector; @@ -96,8 +98,8 @@ bool m_TerrainDirty; std::unique_ptr m_VertexPathfinder; - // Interface to the long-range pathfinder. - LongPathfinder m_LongPathfinder; + std::unique_ptr m_PathfinderHier; + std::unique_ptr m_LongPathfinder; // For responsiveness we will process some moves in the same turn they were generated in @@ -166,10 +168,7 @@ virtual Grid ComputeShoreGrid(bool expandOnWater = false); - virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) - { - m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret); - } + virtual void ComputePath(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); Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpPathfinder.h +++ ps/trunk/source/simulation2/components/ICmpPathfinder.h @@ -93,7 +93,7 @@ * The waypoints correspond to the centers of horizontally/vertically adjacent tiles * along the path. */ - virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) = 0; + virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const = 0; /** * Asynchronous version of ComputePath. Index: ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h +++ ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h @@ -48,6 +48,7 @@ #endif class HierarchicalOverlay; +class SceneCollector; class HierarchicalPathfinder { @@ -130,6 +131,8 @@ return 0; } + void RenderSubmit(SceneCollector& collector); + private: static const u8 CHUNK_SIZE = 96; // number of navcells per side // TODO: figure out best number. Probably 64 < n < 128 Index: ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.cpp +++ ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.cpp @@ -21,6 +21,7 @@ #include "graphics/Overlay.h" #include "ps/Profile.h" +#include "renderer/Scene.h" // Find the root ID of a region, used by InitRegions inline u16 RootID(u16 x, const std::vector& v) @@ -347,6 +348,15 @@ } } +void HierarchicalPathfinder::RenderSubmit(SceneCollector& collector) +{ + if (!m_DebugOverlay) + return; + + for (size_t i = 0; i < m_DebugOverlayLines.size(); ++i) + collector.Submit(&m_DebugOverlayLines[i]); +} + void HierarchicalPathfinder::Recompute(Grid* grid, const std::map& nonPathfindingPassClassMasks, const std::map& pathfindingPassClassMasks) Index: ps/trunk/source/simulation2/helpers/LongPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/LongPathfinder.h +++ ps/trunk/source/simulation2/helpers/LongPathfinder.h @@ -19,11 +19,11 @@ #define INCLUDED_LONGPATHFINDER #include "Pathfinding.h" -#include "HierarchicalPathfinder.h" -#include "PriorityQueue.h" #include "graphics/Overlay.h" #include "renderer/Scene.h" +#include "renderer/TerrainOverlay.h" +#include "simulation2/helpers/PriorityQueue.h" /** * Represents the 2D coordinates of a tile. @@ -156,6 +156,8 @@ class LongOverlay; +class HierarchicalPathfinder; + class LongPathfinder { public: @@ -164,12 +166,7 @@ void SetDebugOverlay(bool enabled); - void SetHierDebugOverlay(bool enabled, const CSimContext *simContext) - { - m_PathfinderHier.SetDebugOverlay(enabled, simContext); - } - - void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) + void SetDebugPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) { if (!m_DebugOverlay) return; @@ -177,38 +174,26 @@ SAFE_DELETE(m_DebugGrid); delete m_DebugPath; m_DebugPath = new WaypointPath(); - ComputePath(x0, z0, goal, passClass, *m_DebugPath); + ComputePath(hierPath, x0, z0, goal, passClass, *m_DebugPath); m_DebugPassClass = passClass; } - void Reload(Grid* passabilityGrid, - const std::map& nonPathfindingPassClassMasks, - const std::map& pathfindingPassClassMasks) + void Reload(Grid* passabilityGrid) { m_Grid = passabilityGrid; ASSERT(passabilityGrid->m_H == passabilityGrid->m_W); m_GridSize = passabilityGrid->m_W; m_JumpPointCache.clear(); - - m_PathfinderHier.Recompute(passabilityGrid, nonPathfindingPassClassMasks, pathfindingPassClassMasks); } - void Update(Grid* passabilityGrid, const Grid& dirtinessGrid) + void Update(Grid* passabilityGrid) { m_Grid = passabilityGrid; ASSERT(passabilityGrid->m_H == passabilityGrid->m_W); ASSERT(m_GridSize == passabilityGrid->m_H); m_JumpPointCache.clear(); - - m_PathfinderHier.Update(passabilityGrid, dirtinessGrid); - } - - void HierarchicalRenderSubmit(SceneCollector& collector) - { - for (size_t i = 0; i < m_PathfinderHier.m_DebugOverlayLines.size(); ++i) - collector.Submit(&m_PathfinderHier.m_DebugOverlayLines[i]); } /** @@ -216,17 +201,8 @@ * The waypoints correspond to the centers of horizontally/vertically adjacent tiles * along the path. */ - void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, - pass_class_t passClass, WaypointPath& path) const - { - if (!m_Grid) - { - LOGERROR("The pathfinder grid hasn't been setup yet, aborting ComputePath"); - return; - } - - ComputeJPSPath(x0, z0, origGoal, passClass, path); - } + void ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, + pass_class_t passClass, WaypointPath& path) const; /** * Compute a tile-based path from the given point to the goal, excluding the regions @@ -234,14 +210,9 @@ * The waypoints correspond to the centers of horizontally/vertically adjacent tiles * along the path. */ - void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, + void ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, std::vector excludedRegions, WaypointPath& path); - Grid GetConnectivityGrid(pass_class_t passClass) - { - return m_PathfinderHier.GetConnectivityGrid(passClass); - } - void GetDebugData(u32& steps, double& time, Grid& grid) const { GetDebugDataJPS(steps, time, grid); @@ -279,7 +250,7 @@ * See LongPathfinder.cpp for implementation details * TODO: cleanup documentation */ - void ComputeJPSPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const; + void ComputeJPSPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const; void GetDebugDataJPS(u32& steps, double& time, Grid& grid) const; // Helper functions for ComputePath @@ -306,8 +277,6 @@ // Obviously, this means that the cache should actually be a cache and not return different results // from what would happen if things hadn't been cached. mutable std::map > m_JumpPointCache; - - HierarchicalPathfinder m_PathfinderHier; }; /** Index: ps/trunk/source/simulation2/helpers/LongPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/helpers/LongPathfinder.cpp +++ ps/trunk/source/simulation2/helpers/LongPathfinder.cpp @@ -23,6 +23,7 @@ #include "ps/Profile.h" #include "Geometry.h" +#include "HierarchicalPathfinder.h" /** * Jump point cache. @@ -712,7 +713,7 @@ } } -void LongPathfinder::ComputeJPSPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const +void LongPathfinder::ComputeJPSPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const { PROFILE("ComputePathJPS"); PROFILE2_IFSPIKE("ComputePathJPS", 0.0002); @@ -735,14 +736,14 @@ // The JPS pathfinder requires units to be on passable tiles // (otherwise it might crash), so handle the supposedly-invalid // state specially - m_PathfinderHier.FindNearestPassableNavcell(i0, j0, passClass); + hierPath.FindNearestPassableNavcell(i0, j0, passClass); } state.goal = origGoal; // Make the goal reachable. This includes shortening the path if the goal is in a non-passable // region, transforming non-point goals to reachable point goals, etc. - m_PathfinderHier.MakeGoalReachable(i0, j0, state.goal, passClass); + hierPath.MakeGoalReachable(i0, j0, state.goal, passClass); ENSURE(state.goal.type == PathGoal::POINT); @@ -988,11 +989,22 @@ SAFE_DELETE(m_DebugOverlay); } -void LongPathfinder::ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, +void LongPathfinder::ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, + pass_class_t passClass, WaypointPath& path) const +{ + if (!m_Grid) + { + LOGERROR("The pathfinder grid hasn't been setup yet, aborting ComputeJPSPath"); + return; + } + + ComputeJPSPath(hierPath, x0, z0, origGoal, passClass, path); +} +void LongPathfinder::ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, std::vector excludedRegions, WaypointPath& path) { GenerateSpecialMap(passClass, excludedRegions); - ComputePath(x0, z0, origGoal, SPECIAL_PASS_CLASS, path); + ComputeJPSPath(hierPath, x0, z0, origGoal, SPECIAL_PASS_CLASS, path); } inline bool InRegion(u16 i, u16 j, CircularRegion region)