Index: ps/trunk/source/simulation2/Simulation2.cpp =================================================================== --- ps/trunk/source/simulation2/Simulation2.cpp +++ ps/trunk/source/simulation2/Simulation2.cpp @@ -540,8 +540,8 @@ CmpPtr cmpPathfinder(simContext, SYSTEM_ENTITY); if (cmpPathfinder) { + cmpPathfinder->FetchAsyncResultsAndSendMessages(); cmpPathfinder->UpdateGrid(); - cmpPathfinder->FinishAsyncRequests(); } // Push AI commands onto the queue before we use them @@ -555,14 +555,17 @@ // Process newly generated move commands so the UI feels snappy if (cmpPathfinder) - cmpPathfinder->ProcessSameTurnMoves(); - + { + cmpPathfinder->StartProcessingMoves(true); + cmpPathfinder->FetchAsyncResultsAndSendMessages(); + } // Send all the update phases { PROFILE2("Sim - Update"); CMessageUpdate msgUpdate(turnLengthFixed); componentManager.BroadcastMessage(msgUpdate); } + { CMessageUpdate_MotionFormation msgUpdate(turnLengthFixed); componentManager.BroadcastMessage(msgUpdate); @@ -570,7 +573,10 @@ // Process move commands for formations (group proxy) if (cmpPathfinder) - cmpPathfinder->ProcessSameTurnMoves(); + { + cmpPathfinder->StartProcessingMoves(true); + cmpPathfinder->FetchAsyncResultsAndSendMessages(); + } { PROFILE2("Sim - Motion Unit"); @@ -583,12 +589,12 @@ componentManager.BroadcastMessage(msgUpdate); } - // Process moves resulting from group proxy movement (unit needs to catch up or realign) and any others - if (cmpPathfinder) - cmpPathfinder->ProcessSameTurnMoves(); - // Clean up any entities destroyed during the simulation update componentManager.FlushDestroyedComponents(); + + // Process all remaining moves + if (cmpPathfinder) + cmpPathfinder->StartProcessingMoves(false); } void CSimulation2Impl::Interpolate(float simFrameLength, float frameOffset, float realFrameLength) Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp +++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp @@ -55,8 +55,6 @@ m_AtlasOverlay = NULL; - 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()); @@ -98,12 +96,16 @@ m_PassClasses.push_back(PathfinderPassability(mask, it->second)); m_PassClassMasks[name] = mask; } + + m_Workers.emplace_back(PathfinderWorker{}); } CCmpPathfinder::~CCmpPathfinder() {}; void CCmpPathfinder::Deinit() { + m_Workers.clear(); + SetDebugOverlay(false); // cleans up memory SAFE_DELETE(m_AtlasOverlay); @@ -149,7 +151,6 @@ SerializeVector()(serialize, "long requests", m_LongPathRequests); SerializeVector()(serialize, "short requests", m_ShortPathRequests); serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket); - serialize.NumberU16_Unbounded("same turn moves count", m_SameTurnMovesCount); serialize.NumberU16_Unbounded("map size", m_MapSize); } @@ -184,9 +185,6 @@ m_TerrainDirty = true; UpdateGrid(); break; - case MT_TurnStart: - m_SameTurnMovesCount = 0; - break; } } @@ -703,10 +701,46 @@ ////////////////////////////////////////////////////////// +// Async pathfinder workers -void CCmpPathfinder::ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const +CCmpPathfinder::PathfinderWorker::PathfinderWorker() {} + +template +void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector&, ssize_t) { - m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret); + static_assert(sizeof(T) == 0, "Only specializations can be used"); +} + +template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector& from, ssize_t amount) +{ + m_LongRequests.insert(m_LongRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end())); +} + +template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector& from, ssize_t amount) +{ + m_ShortRequests.insert(m_ShortRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end())); +} + +void CCmpPathfinder::PathfinderWorker::Work(const CCmpPathfinder& pathfinder) +{ + while (!m_LongRequests.empty()) + { + const LongPathRequest& req = m_LongRequests.back(); + WaypointPath path; + pathfinder.m_LongPathfinder->ComputePath(*pathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, path); + m_Results.emplace_back(req.ticket, req.notify, path); + + m_LongRequests.pop_back(); + } + + while (!m_ShortRequests.empty()) + { + const ShortPathRequest& req = m_ShortRequests.back(); + WaypointPath path = pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr(pathfinder.GetSystemEntity())); + m_Results.emplace_back(req.ticket, req.notify, path); + + m_ShortRequests.pop_back(); + } } u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify) @@ -716,118 +750,98 @@ return req.ticket; } -u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify) +u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, + const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, + entity_id_t group, entity_id_t notify) { ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify }; m_ShortPathRequests.push_back(req); return req.ticket; } -WaypointPath CCmpPathfinder::ComputeShortPath(const ShortPathRequest& request) const +void CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const { - return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity())); + m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret); } -// Async processing: - -void CCmpPathfinder::FinishAsyncRequests() +WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const { - PROFILE2("Finish Async Requests"); - // Save the request queue in case it gets modified while iterating - std::vector longRequests; - m_LongPathRequests.swap(longRequests); - - std::vector shortRequests; - m_ShortPathRequests.swap(shortRequests); - - // TODO: we should only compute one path per entity per turn - - // TODO: this computation should be done incrementally, spread - // across multiple frames (or even multiple turns) - - ProcessLongRequests(longRequests); - ProcessShortRequests(shortRequests); + return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity())); } -void CCmpPathfinder::ProcessLongRequests(const std::vector& longRequests) +void CCmpPathfinder::FetchAsyncResultsAndSendMessages() { - PROFILE2("Process Long Requests"); - for (size_t i = 0; i < longRequests.size(); ++i) + PROFILE2("FetchAsyncResults"); + + // WARNING: the order in which moves are pulled must be consistent when using 1 or n workers. + // We fetch in the same order we inserted in, but we push moves backwards, so this works. + std::vector results; + for (PathfinderWorker& worker : m_Workers) { - const LongPathRequest& req = longRequests[i]; - WaypointPath path; - ComputePath(req.x0, req.z0, req.goal, req.passClass, path); - CMessagePathResult msg(req.ticket, path); - GetSimContext().GetComponentManager().PostMessage(req.notify, msg); + results.insert(results.end(), std::make_move_iterator(worker.m_Results.begin()), std::make_move_iterator(worker.m_Results.end())); + worker.m_Results.clear(); } -} -void CCmpPathfinder::ProcessShortRequests(const std::vector& shortRequests) -{ - PROFILE2("Process Short Requests"); - for (size_t i = 0; i < shortRequests.size(); ++i) { - const ShortPathRequest& req = shortRequests[i]; - WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr(GetSystemEntity())); - CMessagePathResult msg(req.ticket, path); - GetSimContext().GetComponentManager().PostMessage(req.notify, msg); + PROFILE2("PostMessages"); + for (PathResult& path : results) + { + CMessagePathResult msg(path.ticket, path.path); + GetSimContext().GetComponentManager().PostMessage(path.notify, msg); + } } } -void CCmpPathfinder::ProcessSameTurnMoves() +void CCmpPathfinder::StartProcessingMoves(bool useMax) { - if (!m_LongPathRequests.empty()) - { - // Figure out how many moves we can do this time - i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount; + std::vector longRequests = PopMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves); + std::vector shortRequests = PopMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size()); - if (moveCount <= 0) - return; + PushRequestsToWorkers(longRequests); + PushRequestsToWorkers(shortRequests); - // Copy the long request elements we are going to process into a new array - std::vector longRequests; - if ((i32)m_LongPathRequests.size() <= moveCount) - { - m_LongPathRequests.swap(longRequests); - moveCount = (i32)longRequests.size(); - } - else + for (PathfinderWorker& worker : m_Workers) + worker.Work(*this); +} + +template +std::vector CCmpPathfinder::PopMovesToProcess(std::vector& requests, bool useMax, size_t maxMoves) +{ + std::vector poppedRequests; + if (useMax) + { + size_t amount = std::min(requests.size(), maxMoves); + if (amount > 0) { - longRequests.resize(moveCount); - copy(m_LongPathRequests.begin(), m_LongPathRequests.begin() + moveCount, longRequests.begin()); - m_LongPathRequests.erase(m_LongPathRequests.begin(), m_LongPathRequests.begin() + moveCount); + poppedRequests.insert(poppedRequests.begin(), std::make_move_iterator(requests.end() - amount), std::make_move_iterator(requests.end())); + requests.erase(requests.end() - amount, requests.end()); } - - ProcessLongRequests(longRequests); - - m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount); } - - if (!m_ShortPathRequests.empty()) + else { - // Figure out how many moves we can do now - i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount; + poppedRequests.swap(requests); + requests.clear(); + } - if (moveCount <= 0) - return; + return poppedRequests; +} - // Copy the short request elements we are going to process into a new array - std::vector shortRequests; - if ((i32)m_ShortPathRequests.size() <= moveCount) - { - m_ShortPathRequests.swap(shortRequests); - moveCount = (i32)shortRequests.size(); - } - else - { - shortRequests.resize(moveCount); - copy(m_ShortPathRequests.begin(), m_ShortPathRequests.begin() + moveCount, shortRequests.begin()); - m_ShortPathRequests.erase(m_ShortPathRequests.begin(), m_ShortPathRequests.begin() + moveCount); - } +template +void CCmpPathfinder::PushRequestsToWorkers(std::vector& from) +{ + if (from.empty()) + return; - ProcessShortRequests(shortRequests); + // Trivial load-balancing, / rounds towards zero so add 1 to ensure we do push all requests. + size_t amount = from.size() / m_Workers.size() + 1; - m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount); + // WARNING: the order in which moves are pushed must be consistent when using 1 or n workers. + // In this instance, work is distributed in a strict LIFO order, effectively reversing tickets. + for (PathfinderWorker& worker : m_Workers) + { + amount = std::min(amount, from.size()); // Since we are rounding up before, ensure we aren't pushing beyond the end. + worker.PushRequests(from, amount); + from.erase(from.end() - amount, from.end()); } } 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 @@ -57,6 +57,33 @@ */ class CCmpPathfinder final : public ICmpPathfinder { +protected: + + class PathfinderWorker + { + friend CCmpPathfinder; + public: + PathfinderWorker(); + + // Process path requests, checking if we should stop before each new one. + void Work(const CCmpPathfinder& pathfinder); + + private: + // Insert requests in m_[Long/Short]Requests depending on from. + // This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers + template + void PushRequests(std::vector& from, ssize_t amount); + + // Stores our results, the main thread will fetch this. + std::vector m_Results; + + std::vector m_LongRequests; + std::vector m_ShortRequests; + }; + + // Allow the workers to access our private variables + friend class PathfinderWorker; + public: static void ClassInit(CComponentManager& componentManager) { @@ -81,8 +108,8 @@ std::vector m_LongPathRequests; std::vector m_ShortPathRequests; - u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests - u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn + u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests. + u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves. // Lazily-constructed dynamic state (not serialized): @@ -101,9 +128,8 @@ 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 - - u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn + // Workers process pathing requests. + std::vector m_Workers; AtlasOverlay* m_AtlasOverlay; @@ -168,11 +194,11 @@ 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) const; + virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const; virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify); - virtual WaypointPath ComputeShortPath(const ShortPathRequest& request) const; + virtual WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const; virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify); @@ -194,13 +220,15 @@ virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool onlyCenterPoint) const; - virtual void FinishAsyncRequests(); + virtual void FetchAsyncResultsAndSendMessages(); - void ProcessLongRequests(const std::vector& longRequests); + virtual void StartProcessingMoves(bool useMax); - void ProcessShortRequests(const std::vector& shortRequests); + template + std::vector PopMovesToProcess(std::vector& requests, bool useMax = false, size_t maxMoves = 0); - virtual void ProcessSameTurnMoves(); + template + void PushRequestsToWorkers(std::vector& from); /** * Regenerates the grid based on the current obstruction list, if necessary Index: ps/trunk/source/simulation2/components/CCmpRallyPointRenderer.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpRallyPointRenderer.cpp +++ ps/trunk/source/simulation2/components/CCmpRallyPointRenderer.cpp @@ -686,7 +686,7 @@ start.X = m_RallyPoints[index-1].X; start.Y = m_RallyPoints[index-1].Y; } - cmpPathfinder->ComputePath(start.X, start.Y, goal, cmpPathfinder->GetPassabilityClass(m_LinePassabilityClass), path); + cmpPathfinder->ComputePathImmediate(start.X, start.Y, goal, cmpPathfinder->GetPassabilityClass(m_LinePassabilityClass), path); // Check if we got a path back; if not we probably have two markers less than one tile apart. if (path.m_Waypoints.size() < 2) Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpPathfinder.h +++ ps/trunk/source/simulation2/components/ICmpPathfinder.h @@ -33,6 +33,19 @@ template class Grid; +// Returned by asynchronous workers, used to send messages in the main thread. +struct WaypointPath; + +struct PathResult +{ + PathResult() = default; + PathResult(u32 t, entity_id_t n, WaypointPath p) : ticket(t), notify(n), path(p) {}; + + u32 ticket; + entity_id_t notify; + WaypointPath path; +}; + /** * Pathfinder algorithms. * @@ -89,40 +102,36 @@ virtual Grid ComputeShoreGrid(bool expandOnWater = false) = 0; /** - * Compute a tile-based path from the given point to the goal, and return the set of waypoints. - * 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) const = 0; - - /** * Asynchronous version of ComputePath. + * Request a long path computation, asynchronously. * The result will be sent as CMessagePathResult to 'notify'. * Returns a unique non-zero number, which will match the 'ticket' in the result, * so callers can recognise each individual request they make. */ virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify) = 0; - /** - * If the debug overlay is enabled, render the path that will computed by ComputePath. + /* + * Request a long-path computation immediately */ - virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) = 0; + virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const = 0; /** - * Compute a precise path from the given point to the goal, and return the set of waypoints. - * The path is based on the full set of obstructions that pass the filter, such that - * a unit of clearance 'clearance' will be able to follow the path with no collisions. - * The path is restricted to a box of radius 'range' from the starting point. - */ - virtual WaypointPath ComputeShortPath(const ShortPathRequest& request) const = 0; - - /** - * Asynchronous version of ComputeShortPath (using ControlGroupObstructionFilter). + * Request a short path computation, asynchronously. * The result will be sent as CMessagePathResult to 'notify'. * Returns a unique non-zero number, which will match the 'ticket' in the result, * so callers can recognise each individual request they make. */ - virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify) = 0; + virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t controller, entity_id_t notify) = 0; + + /* + * Request a short-path computation immediately. + */ + virtual WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const = 0; + + /** + * If the debug overlay is enabled, render the path that will computed by ComputePath. + */ + virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) = 0; /** * Check whether the given movement line is valid and doesn't hit any obstructions @@ -171,12 +180,12 @@ /** * Finish computing asynchronous path requests and send the CMessagePathResult messages. */ - virtual void FinishAsyncRequests() = 0; + virtual void FetchAsyncResultsAndSendMessages() = 0; /** - * Process moves during the same turn they were created in to improve responsiveness. + * Tell asynchronous pathfinder threads that they can begin computing paths. */ - virtual void ProcessSameTurnMoves() = 0; + virtual void StartProcessingMoves(bool useMax) = 0; /** * Regenerates the grid based on the current obstruction list, if necessary 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 @@ -183,7 +183,7 @@ PathGoal goal = { PathGoal::POINT, x1, z1 }; WaypointPath path; - cmp->ComputePath(x0, z0, goal, cmp->GetPassabilityClass("default"), path); + cmp->ComputePathImmediate(x0, z0, goal, cmp->GetPassabilityClass("default"), path); } t = timer_Time() - t; @@ -214,7 +214,7 @@ } PathGoal goal = { PathGoal::POINT, range, range }; - WaypointPath path = cmpPathfinder->ComputeShortPath(ShortPathRequest{ 0, range/3, range/3, fixed::FromInt(2), range, goal, 0, false, 0, 0 }); + WaypointPath path = cmpPathfinder->ComputeShortPathImmediate(ShortPathRequest{ 0, range/3, range/3, fixed::FromInt(2), range, goal, 0, false, 0, 0 }); for (size_t i = 0; i < path.m_Waypoints.size(); ++i) printf("# %d: %f %f\n", (int)i, path.m_Waypoints[i].x.ToFloat(), path.m_Waypoints[i].z.ToFloat()); } @@ -369,7 +369,7 @@ PathGoal goal = { PathGoal::POINT, x1, z1 }; WaypointPath path; - cmpPathfinder->ComputePath(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path); + cmpPathfinder->ComputePathImmediate(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path); u32 debugSteps; double debugTime; @@ -418,7 +418,7 @@ for (int i = 0; i < n; ++i) { WaypointPath path; - cmpPathfinder->ComputePath(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path); + cmpPathfinder->ComputePathImmediate(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path); } t = timer_Time() - t; debug_printf("### RepeatPath %fms each (%fs total)\n", 1000*t / n, t);