Index: binaries/data/mods/public/gui/credits/texts/programming.json =================================================================== --- binaries/data/mods/public/gui/credits/texts/programming.json +++ binaries/data/mods/public/gui/credits/texts/programming.json @@ -141,6 +141,7 @@ { "nick": "kingadami", "name": "Adam Winsor" }, { "nick": "kingbasil", "name": "Giannis Fafalios" }, { "nick": "Krinkle", "name": "Timo Tijhof" }, + { "nick": "Kuba386", "name": "Jakub Kośmicki" }, { "nick": "lafferjm", "name": "Justin Lafferty" }, { "nick": "LeanderH", "name": "Leander Hemelhof" }, { "nick": "leper", "name": "Georg Kilzer" }, Index: source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- source/simulation2/components/CCmpPathfinder.cpp +++ source/simulation2/components/CCmpPathfinder.cpp @@ -59,7 +59,9 @@ m_AtlasOverlay = NULL; - m_VertexPathfinder = std::make_unique(m_MapSize, m_TerrainOnlyGrid); + // Store one vertex pathfinder for each thread (including the main thread). + while (m_VertexPathfinders.size() < g_ThreadPool.GetNbOfThreads() + 1) + m_VertexPathfinders.emplace_back(m_MapSize, m_TerrainOnlyGrid); m_LongPathfinder = std::make_unique(); m_PathfinderHier = std::make_unique(); @@ -75,9 +77,9 @@ // Paths are computed: // - Before MT_Update // - Before MT_MotionUnitFormation - // - 'in-between' turns (effectively at the start until threading is implemented). + // - asynchronously between turn end and turn start. // The latter of these must compute all outstanding requests, but the former two are capped - // to avoid spending too much time there (since the latter are designed to be threaded and thus not block the GUI). + // to avoid spending too much time there (since the latter are threaded and thus much 'cheaper'). // This loads that maximum number (note that it's per computation call, not per turn for now). const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder"); m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt(); @@ -99,6 +101,12 @@ void CCmpPathfinder::Deinit() { SetDebugOverlay(false); // cleans up memory + + // Wait on all pathfinding tasks. + for (CancellableFuture& future : m_Futures) + future.Cancel(); + m_Futures.clear(); + SAFE_DELETE(m_AtlasOverlay); SAFE_DELETE(m_Grid); @@ -196,7 +204,7 @@ void CCmpPathfinder::RenderSubmit(SceneCollector& collector) { - m_VertexPathfinder->RenderSubmit(collector); + g_VertexPathfinderDebugOverlay.RenderSubmit(collector); m_PathfinderHier->RenderSubmit(collector); } @@ -207,7 +215,7 @@ void CCmpPathfinder::SetDebugOverlay(bool enabled) { - m_VertexPathfinder->SetDebugOverlay(enabled); + g_VertexPathfinderDebugOverlay.SetDebugOverlay(enabled); m_LongPathfinder->SetDebugOverlay(enabled); } @@ -747,7 +755,7 @@ WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const { - return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity())); + return m_VertexPathfinders.front().ComputeShortPath(request, CmpPtr(GetSystemEntity())); } template @@ -783,8 +791,19 @@ if (!m_LongPathRequests.m_ComputeDone || !m_ShortPathRequests.m_ComputeDone) { - m_ShortPathRequests.Compute(*this, *m_VertexPathfinder); + // Also start computing on the main thread to finish faster. + m_ShortPathRequests.Compute(*this, m_VertexPathfinders.front()); m_LongPathRequests.Compute(*this, *m_LongPathfinder); + + std::unique_lock lock(m_PathfinderMutex); + m_PathfinderConditionVariable.wait(lock, [this] { return m_LongPathRequests.m_ComputeDone && m_ShortPathRequests.m_ComputeDone; }); + } + + { + // Mark all computation tasks as done, even if they weren't started. + for (CancellableFuture& future : m_Futures) + future.Cancel(); + m_Futures.clear(); } { @@ -809,8 +828,29 @@ { m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0); m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0); + + // Resize futures to each parallel thread. + m_Futures.resize(g_ThreadPool.GetNbOfThreads()); + + size_t i = 0; + for (ThreadPool::ThreadExecutor& executor : g_ThreadPool.GetAllWorkers()) + { + // Pass the i+1th vertex pathfinder to keep the first for the main thread, + // while avoiding issues because of cached data. + m_Futures[i] = executor.Submit([&pathfinder=*this, &vertexPfr=m_VertexPathfinders[i + 1]]() { + PROFILE2("Async pathfinding"); + pathfinder.m_ShortPathRequests.Compute(pathfinder, vertexPfr); + pathfinder.m_LongPathRequests.Compute(pathfinder, *pathfinder.m_LongPathfinder); + { + std::unique_lock lock(pathfinder.m_PathfinderMutex); + pathfinder.m_PathfinderConditionVariable.notify_all(); + } + }); + ++i; + } } + ////////////////////////////////////////////////////////// bool CCmpPathfinder::IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) Index: source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- source/simulation2/components/CCmpPathfinder_Common.h +++ source/simulation2/components/CCmpPathfinder_Common.h @@ -35,6 +35,7 @@ #include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "ps/CLogger.h" +#include "ps/ThreadPool.h" #include "renderer/TerrainOverlay.h" #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/helpers/Grid.h" @@ -94,19 +95,24 @@ GridUpdateInformation m_AIPathfinderDirtinessInformation; bool m_TerrainDirty; - std::unique_ptr m_VertexPathfinder; + std::vector m_VertexPathfinders; std::unique_ptr m_PathfinderHier; std::unique_ptr m_LongPathfinder; + mutable std::mutex m_PathfinderMutex; + mutable std::condition_variable m_PathfinderConditionVariable; + // One per live asynchronous path computing task. + std::vector m_Futures; + template class PathRequests { public: std::vector m_Requests; std::vector m_Results; // This is the array index of the next path to compute. - size_t m_NextPathToCompute = 0; + std::atomic m_NextPathToCompute = 0; // This is false until all scheduled paths have been computed. - bool m_ComputeDone = true; + std::atomic m_ComputeDone = true; void ClearComputed() { Index: source/simulation2/helpers/LongPathfinder.h =================================================================== --- source/simulation2/helpers/LongPathfinder.h +++ source/simulation2/helpers/LongPathfinder.h @@ -154,7 +154,7 @@ PathCost hBest; // heuristic of closest discovered tile to goal u16 iBest, jBest; // closest tile - JumpPointCache* jpc; + const JumpPointCache* jpc; }; class LongOverlay; @@ -171,14 +171,14 @@ void SetDebugPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) { - if (!m_DebugOverlay) + if (!m_Debug.Overlay) return; - SAFE_DELETE(m_DebugGrid); - delete m_DebugPath; - m_DebugPath = new WaypointPath(); - ComputePath(hierPath, x0, z0, goal, passClass, *m_DebugPath); - m_DebugPassClass = passClass; + SAFE_DELETE(m_Debug.Grid); + delete m_Debug.Path; + m_Debug.Path = new WaypointPath(); + ComputePath(hierPath, x0, z0, goal, passClass, *m_Debug.Path); + m_Debug.PassClass = passClass; } void Reload(Grid* passabilityGrid) @@ -225,15 +225,20 @@ u16 m_GridSize; // Debugging - output from last pathfind operation. - // mutable as making these const would require a lot of boilerplate code - // and they do not change the behavioural const-ness of the pathfinder. - mutable LongOverlay* m_DebugOverlay; - mutable PathfindTileGrid* m_DebugGrid; - mutable u32 m_DebugSteps; - mutable double m_DebugTime; - mutable PathGoal m_DebugGoal; - mutable WaypointPath* m_DebugPath; - mutable pass_class_t m_DebugPassClass; + struct Debug + { + // Atomic - used to toggle debugging. + std::atomic Overlay = nullptr; + // Mutable - set by ComputeJPSPath (thus possibly from different threads). + // Synchronized via mutex if necessary. + mutable PathfindTileGrid* Grid = nullptr; + mutable u32 Steps; + mutable double Time; + mutable PathGoal Goal; + + WaypointPath* Path = nullptr; + pass_class_t PassClass; + } m_Debug; private: PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const; @@ -280,93 +285,4 @@ mutable std::map > m_JumpPointCache; }; -/** - * Terrain overlay for pathfinder debugging. - * Renders a representation of the most recent pathfinding operation. - */ -class LongOverlay : public TerrainTextureOverlay -{ -public: - LongPathfinder& m_Pathfinder; - - LongOverlay(LongPathfinder& pathfinder) : - TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder) - { - } - - virtual void BuildTextureRGBA(u8* data, size_t w, size_t h) - { - // Grab the debug data for the most recently generated path - u32 steps; - double time; - Grid debugGrid; - m_Pathfinder.GetDebugData(steps, time, debugGrid); - - // Render navcell passability - u8* p = data; - for (size_t j = 0; j < h; ++j) - { - for (size_t i = 0; i < w; ++i) - { - SColor4ub color(0, 0, 0, 0); - if (!IS_PASSABLE(m_Pathfinder.m_Grid->get((int)i, (int)j), m_Pathfinder.m_DebugPassClass)) - color = SColor4ub(255, 0, 0, 127); - - if (debugGrid.m_W && debugGrid.m_H) - { - u8 n = debugGrid.get((int)i, (int)j); - - if (n == 1) - color = SColor4ub(255, 255, 0, 127); - else if (n == 2) - color = SColor4ub(0, 255, 0, 127); - - if (m_Pathfinder.m_DebugGoal.NavcellContainsGoal(i, j)) - color = SColor4ub(0, 0, 255, 127); - } - - *p++ = color.R; - *p++ = color.G; - *p++ = color.B; - *p++ = color.A; - } - } - - // Render the most recently generated path - if (m_Pathfinder.m_DebugPath && !m_Pathfinder.m_DebugPath->m_Waypoints.empty()) - { - std::vector& waypoints = m_Pathfinder.m_DebugPath->m_Waypoints; - u16 ip = 0, jp = 0; - for (size_t k = 0; k < waypoints.size(); ++k) - { - u16 i, j; - Pathfinding::NearestNavcell(waypoints[k].x, waypoints[k].z, i, j, m_Pathfinder.m_GridSize, m_Pathfinder.m_GridSize); - if (k == 0) - { - ip = i; - jp = j; - } - else - { - bool firstCell = true; - do - { - if (data[(jp*w + ip)*4+3] == 0) - { - data[(jp*w + ip)*4+0] = 0xFF; - data[(jp*w + ip)*4+1] = 0xFF; - data[(jp*w + ip)*4+2] = 0xFF; - data[(jp*w + ip)*4+3] = firstCell ? 0xA0 : 0x60; - } - ip = ip < i ? ip+1 : ip > i ? ip-1 : ip; - jp = jp < j ? jp+1 : jp > j ? jp-1 : jp; - firstCell = false; - } - while (ip != i || jp != j); - } - } - } - } -}; - #endif // INCLUDED_LONGPATHFINDER Index: source/simulation2/helpers/LongPathfinder.cpp =================================================================== --- source/simulation2/helpers/LongPathfinder.cpp +++ source/simulation2/helpers/LongPathfinder.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 @@ -25,6 +25,13 @@ #include "Geometry.h" #include "HierarchicalPathfinder.h" +#include + +namespace +{ +static std::mutex g_DebugMutex; +} + /** * Jump point cache. * @@ -87,7 +94,7 @@ * Returns the coordinate of the next jump point xp (where x < xp), * and whether it's an obstruction point or jump point. */ - void Get(int x, int& xp, bool& obstruction) + void Get(int x, int& xp, bool& obstruction) const { ENSURE(0 <= x && x < (int)data.size()); xp = data[x] >> 1; @@ -178,7 +185,7 @@ data.swap(tree); } - void Get(int x, int& xp, bool& obstruction) + void Get(int x, int& xp, bool& obstruction) const { // Search the binary tree for an interval which contains x int i = 0; @@ -323,7 +330,7 @@ * at (ip, j) where i < ip. * Returns i if there is no such point. */ - int GetJumpPointRight(int i, int j, const PathGoal& goal) + int GetJumpPointRight(int i, int j, const PathGoal& goal) const { int ip; bool obstruction; @@ -336,7 +343,7 @@ return i; } - int GetJumpPointLeft(int i, int j, const PathGoal& goal) + int GetJumpPointLeft(int i, int j, const PathGoal& goal) const { int mip; // mirrored value, because m_JumpPointsLeft is generated from a mirrored map bool obstruction; @@ -347,7 +354,7 @@ return i; } - int GetJumpPointUp(int i, int j, const PathGoal& goal) + int GetJumpPointUp(int i, int j, const PathGoal& goal) const { int jp; bool obstruction; @@ -357,7 +364,7 @@ return j; } - int GetJumpPointDown(int i, int j, const PathGoal& goal) + int GetJumpPointDown(int i, int j, const PathGoal& goal) const { int mjp; // mirrored value bool obstruction; @@ -373,18 +380,10 @@ LongPathfinder::LongPathfinder() : m_UseJPSCache(false), - m_Grid(NULL), m_GridSize(0), - m_DebugOverlay(NULL), m_DebugGrid(NULL), m_DebugPath(NULL) + m_Grid(NULL), m_GridSize(0) { } -LongPathfinder::~LongPathfinder() -{ - SAFE_DELETE(m_DebugOverlay); - SAFE_DELETE(m_DebugGrid); - SAFE_DELETE(m_DebugPath); -} - #define PASSABLE(i, j) IS_PASSABLE(state.terrain->get(i, j), state.passClass) // Calculate heuristic cost from tile i,j to goal @@ -715,20 +714,25 @@ 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); + PROFILE2("ComputePathJPS"); PathfinderState state = { 0 }; - std::map >::const_iterator it = m_JumpPointCache.find(passClass); - if (it != m_JumpPointCache.end()) - state.jpc = it->second.get(); - - if (m_UseJPSCache && !state.jpc) + if (m_UseJPSCache) { - state.jpc = new JumpPointCache; - state.jpc->reset(m_Grid, passClass); - debug_printf("PATHFINDER: JPC memory: %d kB\n", (int)state.jpc->GetMemoryUsage() / 1024); - m_JumpPointCache[passClass] = shared_ptr(state.jpc); + // Needs to lock for construction, or several threads might try doing that at the same time. + static std::mutex JPCMutex; + std::unique_lock lock(JPCMutex); + std::map >::const_iterator it = m_JumpPointCache.find(passClass); + if (it != m_JumpPointCache.end()) + state.jpc = it->second.get(); + + if (!state.jpc) + { + m_JumpPointCache[passClass] = std::make_shared(); + m_JumpPointCache[passClass]->reset(m_Grid, passClass); + debug_printf("PATHFINDER: JPC memory: %d kB\n", (int)state.jpc->GetMemoryUsage() / 1024); + state.jpc = m_JumpPointCache[passClass].get(); + } } // Convert the start coordinates to tile indexes @@ -901,10 +905,16 @@ ImprovePathWaypoints(path, passClass, origGoal.maxdist, x0, z0); // Save this grid for debug display - delete m_DebugGrid; - m_DebugGrid = state.tiles; - m_DebugSteps = state.steps; - m_DebugGoal = state.goal; + if (m_Debug.Overlay) + { + std::lock_guard lock(g_DebugMutex); + delete m_Debug.Grid; + m_Debug.Grid = state.tiles; + m_Debug.Steps = state.steps; + m_Debug.Goal = state.goal; + } + else + SAFE_DELETE(state.tiles); } #undef PASSABLE @@ -963,36 +973,30 @@ void LongPathfinder::GetDebugDataJPS(u32& steps, double& time, Grid& grid) const { - steps = m_DebugSteps; - time = m_DebugTime; + steps = m_Debug.Steps; + time = m_Debug.Time; - if (!m_DebugGrid) + if (!m_Debug.Grid) return; + std::lock_guard lock(g_DebugMutex); + u16 iGoal, jGoal; - Pathfinding::NearestNavcell(m_DebugGoal.x, m_DebugGoal.z, iGoal, jGoal, m_GridSize, m_GridSize); + Pathfinding::NearestNavcell(m_Debug.Goal.x, m_Debug.Goal.z, iGoal, jGoal, m_GridSize, m_GridSize); - grid = Grid(m_DebugGrid->m_W, m_DebugGrid->m_H); + grid = Grid(m_Debug.Grid->m_W, m_Debug.Grid->m_H); for (u16 j = 0; j < grid.m_H; ++j) { for (u16 i = 0; i < grid.m_W; ++i) { if (i == iGoal && j == jGoal) continue; - PathfindTile t = m_DebugGrid->get(i, j); + PathfindTile t = m_Debug.Grid->get(i, j); grid.set(i, j, (t.IsOpen() ? 1 : 0) | (t.IsClosed() ? 2 : 0)); } } } -void LongPathfinder::SetDebugOverlay(bool enabled) -{ - if (enabled && !m_DebugOverlay) - m_DebugOverlay = new LongOverlay(*this); - else if (!enabled && m_DebugOverlay) - SAFE_DELETE(m_DebugOverlay); -} - void LongPathfinder::ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const { @@ -1045,3 +1049,109 @@ } } } + + +/** + * Terrain overlay for pathfinder debugging. + * Renders a representation of the most recent pathfinding operation. + */ +class LongOverlay : public TerrainTextureOverlay +{ +public: + LongPathfinder& m_Pathfinder; + + LongOverlay(LongPathfinder& pathfinder) : + TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder) + { + } + + virtual void BuildTextureRGBA(u8* data, size_t w, size_t h) + { + // Grab the debug data for the most recently generated path + u32 steps; + double time; + Grid debugGrid; + m_Pathfinder.GetDebugData(steps, time, debugGrid); + + // Render navcell passability + u8* p = data; + for (size_t j = 0; j < h; ++j) + { + for (size_t i = 0; i < w; ++i) + { + SColor4ub color(0, 0, 0, 0); + if (!IS_PASSABLE(m_Pathfinder.m_Grid->get((int)i, (int)j), m_Pathfinder.m_Debug.PassClass)) + color = SColor4ub(255, 0, 0, 127); + + if (debugGrid.m_W && debugGrid.m_H) + { + u8 n = debugGrid.get((int)i, (int)j); + + if (n == 1) + color = SColor4ub(255, 255, 0, 127); + else if (n == 2) + color = SColor4ub(0, 255, 0, 127); + + if (m_Pathfinder.m_Debug.Goal.NavcellContainsGoal(i, j)) + color = SColor4ub(0, 0, 255, 127); + } + + *p++ = color.R; + *p++ = color.G; + *p++ = color.B; + *p++ = color.A; + } + } + + // Render the most recently generated path + if (m_Pathfinder.m_Debug.Path && !m_Pathfinder.m_Debug.Path->m_Waypoints.empty()) + { + std::vector& waypoints = m_Pathfinder.m_Debug.Path->m_Waypoints; + u16 ip = 0, jp = 0; + for (size_t k = 0; k < waypoints.size(); ++k) + { + u16 i, j; + Pathfinding::NearestNavcell(waypoints[k].x, waypoints[k].z, i, j, m_Pathfinder.m_GridSize, m_Pathfinder.m_GridSize); + if (k == 0) + { + ip = i; + jp = j; + } + else + { + bool firstCell = true; + do + { + if (data[(jp*w + ip)*4+3] == 0) + { + data[(jp*w + ip)*4+0] = 0xFF; + data[(jp*w + ip)*4+1] = 0xFF; + data[(jp*w + ip)*4+2] = 0xFF; + data[(jp*w + ip)*4+3] = firstCell ? 0xA0 : 0x60; + } + ip = ip < i ? ip+1 : ip > i ? ip-1 : ip; + jp = jp < j ? jp+1 : jp > j ? jp-1 : jp; + firstCell = false; + } + while (ip != i || jp != j); + } + } + } + } +}; + +// These two functions must come below LongOverlay's definition. +void LongPathfinder::SetDebugOverlay(bool enabled) +{ + if (enabled && !m_Debug.Overlay) + m_Debug.Overlay = new LongOverlay(*this); + else if (!enabled && m_Debug.Overlay) + SAFE_DELETE(m_Debug.Overlay); +} + +LongPathfinder::~LongPathfinder() +{ + SAFE_DELETE(m_Debug.Overlay); + SAFE_DELETE(m_Debug.Grid); + SAFE_DELETE(m_Debug.Path); +} Index: source/simulation2/helpers/VertexPathfinder.h =================================================================== --- source/simulation2/helpers/VertexPathfinder.h +++ 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,9 @@ class VertexPathfinder { public: - VertexPathfinder(const u16& mapSize, Grid* const & terrainOnlyGrid) : m_MapSize(mapSize), m_TerrainOnlyGrid(terrainOnlyGrid), m_DebugOverlay(false) {}; + VertexPathfinder(const u16& mapSize, Grid* const & terrainOnlyGrid) : m_MapSize(mapSize), m_TerrainOnlyGrid(terrainOnlyGrid) {}; + VertexPathfinder(const VertexPathfinder&) = delete; + VertexPathfinder(VertexPathfinder&& o) : m_MapSize(o.m_MapSize), m_TerrainOnlyGrid(o.m_TerrainOnlyGrid) {} /** * Compute a precise path from the given point to the goal, and return the set of waypoints. @@ -86,22 +88,12 @@ */ WaypointPath ComputeShortPath(const ShortPathRequest& request, CmpPtr cmpObstructionManager) const; - void SetDebugOverlay(bool enabled) { m_DebugOverlay = enabled; } - void RenderSubmit(SceneCollector& collector); - private: - void DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal) const; - void DebugRenderGraph(const CSimContext& simContext, const std::vector& vertexes, const std::vector& edges, const std::vector& edgeSquares) const; - void DebugRenderEdges(const CSimContext& simContext, bool visible, CFixedVector2D curr, CFixedVector2D npos) const; - // References to the Pathfinder for convenience. const u16& m_MapSize; Grid* const & m_TerrainOnlyGrid; - std::atomic m_DebugOverlay; - mutable std::vector m_DebugOverlayShortPathLines; - // These vectors are expensive to recreate on every call, so we cache them here. // They are made mutable to allow using them in the otherwise const ComputeShortPath. @@ -120,4 +112,30 @@ mutable std::vector m_EdgeSquares; // Axis-aligned squares; equivalent to 4 edges. }; +/** + * There are several vertex pathfinders running asynchronously, so their debug output + * might conflict. To remain thread-safe, this single class will handle the debug data. + * NB: though threadsafe, the way things are setup means you can have a few + * more graphs and edges than you'd expect showing up in the rendered graph. + */ +class VertexPathfinderDebugOverlay +{ + friend class VertexPathfinder; +public: + void SetDebugOverlay(bool enabled) { m_DebugOverlay = enabled; } + void RenderSubmit(SceneCollector& collector); +protected: + + void DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal); + void DebugRenderGraph(const CSimContext& simContext, const std::vector& vertexes, const std::vector& edges, const std::vector& edgeSquares); + void DebugRenderEdges(const CSimContext& simContext, bool visible, CFixedVector2D curr, CFixedVector2D npos); + + std::atomic m_DebugOverlay = false; + // The data is double buffered: the first is the 'work-in-progress' state, the second the last RenderSubmit state. + std::vector m_DebugOverlayShortPathLines; + std::vector m_DebugOverlayShortPathLinesSubmitted; +}; + +extern VertexPathfinderDebugOverlay g_VertexPathfinderDebugOverlay; + #endif // INCLUDED_VERTEXPATHFINDER Index: source/simulation2/helpers/VertexPathfinder.cpp =================================================================== --- source/simulation2/helpers/VertexPathfinder.cpp +++ 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 @@ -43,6 +43,15 @@ #include "simulation2/helpers/Render.h" #include "simulation2/system/SimContext.h" +#include + +namespace +{ +static std::mutex g_DebugMutex; +} + +VertexPathfinderDebugOverlay g_VertexPathfinderDebugOverlay; + /* Quadrant optimisation: * (loosely based on GPG2 "Optimizing Points-of-Visibility Pathfinding") * @@ -515,7 +524,7 @@ { PROFILE2("ComputeShortPath"); - DebugRenderGoal(cmpObstructionManager->GetSimContext(), request.goal); + g_VertexPathfinderDebugOverlay.DebugRenderGoal(cmpObstructionManager->GetSimContext(), request.goal); // Create impassable edges at the max-range boundary, so we can't escape the region // where we're meant to be searching @@ -694,7 +703,7 @@ ENSURE(m_Vertexes.size() < 65536); // We store array indexes as u16. - DebugRenderGraph(cmpObstructionManager->GetSimContext(), m_Vertexes, m_Edges, m_EdgeSquares); + g_VertexPathfinderDebugOverlay.DebugRenderGraph(cmpObstructionManager->GetSimContext(), m_Vertexes, m_Edges, m_EdgeSquares); // Do an A* search over the vertex/visibility graph: @@ -786,7 +795,7 @@ CheckVisibility(m_Vertexes[curr.id].p, npos, m_EdgesUnaligned); // Render the edges that we examine. - DebugRenderEdges(cmpObstructionManager->GetSimContext(), visible, m_Vertexes[curr.id].p, npos); + g_VertexPathfinderDebugOverlay.DebugRenderEdges(cmpObstructionManager->GetSimContext(), visible, m_Vertexes[curr.id].p, npos); if (visible) { @@ -854,12 +863,14 @@ return path; } -void VertexPathfinder::DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal) const +void VertexPathfinderDebugOverlay::DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal) { if (!m_DebugOverlay) return; - m_DebugOverlayShortPathLines.clear(); + std::lock_guard lock(g_DebugMutex); + + g_VertexPathfinderDebugOverlay.m_DebugOverlayShortPathLines.clear(); // Render the goal shape m_DebugOverlayShortPathLines.push_back(SOverlayLine()); @@ -887,11 +898,13 @@ } } -void VertexPathfinder::DebugRenderGraph(const CSimContext& simContext, const std::vector& vertexes, const std::vector& edges, const std::vector& edgeSquares) const +void VertexPathfinderDebugOverlay::DebugRenderGraph(const CSimContext& simContext, const std::vector& vertexes, const std::vector& edges, const std::vector& edgeSquares) { if (!m_DebugOverlay) return; + std::lock_guard lock(g_DebugMutex); + #define PUSH_POINT(p) STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat())) // Render the vertexes as little Pac-Man shapes to indicate quadrant direction for (size_t i = 0; i < vertexes.size(); ++i) @@ -962,11 +975,13 @@ } } -void VertexPathfinder::DebugRenderEdges(const CSimContext& UNUSED(simContext), bool UNUSED(visible), CFixedVector2D UNUSED(curr), CFixedVector2D UNUSED(npos)) const +void VertexPathfinderDebugOverlay::DebugRenderEdges(const CSimContext& UNUSED(simContext), bool UNUSED(visible), CFixedVector2D UNUSED(curr), CFixedVector2D UNUSED(npos)) { if (!m_DebugOverlay) return; + std::lock_guard lock(g_DebugMutex); + // Disabled by default. /* m_DebugOverlayShortPathLines.push_back(SOverlayLine()); @@ -983,11 +998,13 @@ */ } -void VertexPathfinder::RenderSubmit(SceneCollector& collector) +void VertexPathfinderDebugOverlay::RenderSubmit(SceneCollector& collector) { if (!m_DebugOverlay) return; - for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i) - collector.Submit(&m_DebugOverlayShortPathLines[i]); + std::lock_guard lock(g_DebugMutex); + m_DebugOverlayShortPathLines.swap(m_DebugOverlayShortPathLinesSubmitted); + for (size_t i = 0; i < m_DebugOverlayShortPathLinesSubmitted.size(); ++i) + collector.Submit(&m_DebugOverlayShortPathLinesSubmitted[i]); }