Differential D3849 Diff 17077 ps/trunk/source/simulation2/components/CCmpPathfinder.cpp

Changeset View

Standalone View

ps/trunk/source/simulation2/components/CCmpPathfinder.cpp

Show All 37 Lines
#include "simulation2/serialization/SerializedTypes.h"		#include "simulation2/serialization/SerializedTypes.h"

#include "ps/CLogger.h"		#include "ps/CLogger.h"
#include "ps/CStr.h"		#include "ps/CStr.h"
#include "ps/Profile.h"		#include "ps/Profile.h"
#include "ps/XML/Xeromyces.h"		#include "ps/XML/Xeromyces.h"
#include "renderer/Scene.h"		#include "renderer/Scene.h"

		#include <type_traits>

REGISTER_COMPONENT_TYPE(Pathfinder)		REGISTER_COMPONENT_TYPE(Pathfinder)

void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))		void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
{		{
m_MapSize = 0;		m_MapSize = 0;
m_Grid = NULL;		m_Grid = NULL;
m_TerrainOnlyGrid = NULL;		m_TerrainOnlyGrid = NULL;

Show All 11 Lines	void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");		CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");

// Since this is used as a system component (not loaded from an entity template),		// Since this is used as a system component (not loaded from an entity template),
// we can't use the real paramNode (it won't get handled properly when deserializing),		// we can't use the real paramNode (it won't get handled properly when deserializing),
// so load the data from a special XML file.		// so load the data from a special XML file.
CParamNode externalParamNode;		CParamNode externalParamNode;
CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");		CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");

// Previously all move commands during a turn were		// Paths are computed:
// queued up and processed asynchronously at the start		// - Before MT_Update
// of the next turn. Now we are processing queued up		// - Before MT_MotionUnitFormation
// events several times duing the turn. This improves		// - 'in-between' turns (effectively at the start until threading is implemented).
// responsiveness and units move more smoothly especially.		// The latter of these must compute all outstanding requests, but the former two are capped
// when in formation. There is still a call at the		// to avoid spending too much time there (since the latter are designed to be threaded and thus not block the GUI).
// beginning of a turn to process all outstanding moves -		// This loads that maximum number (note that it's per computation call, not per turn for now).
// this will handle any moves above the MaxSameTurnMoves
// threshold.
//
// TODO - The moves processed at the beginning of the
// turn do not count against the maximum moves per turn
// currently. The thinking is that this will eventually
// happen in another thread. Either way this probably
// will require some adjustment and rethinking.
const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");		const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();		m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();


const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();		const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)		for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
{		{
std::string name = it->first;		std::string name = it->first;
ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);		ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);
pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());		pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());
m_PassClasses.push_back(PathfinderPassability(mask, it->second));		m_PassClasses.push_back(PathfinderPassability(mask, it->second));
m_PassClassMasks[name] = mask;		m_PassClassMasks[name] = mask;
}		}

m_Workers.emplace_back(PathfinderWorker{});
}		}

CCmpPathfinder::~CCmpPathfinder() {};		CCmpPathfinder::~CCmpPathfinder() {};

void CCmpPathfinder::Deinit()		void CCmpPathfinder::Deinit()
{		{
m_Workers.clear();

SetDebugOverlay(false); // cleans up memory		SetDebugOverlay(false); // cleans up memory
SAFE_DELETE(m_AtlasOverlay);		SAFE_DELETE(m_AtlasOverlay);

SAFE_DELETE(m_Grid);		SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);		SAFE_DELETE(m_TerrainOnlyGrid);
}		}

template<>		template<>
Show All 28 Lines	void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify<S, ShortPathRequest> value)
serialize.NumberU32_Unbounded("group", value.group);		serialize.NumberU32_Unbounded("group", value.group);
serialize.NumberU32_Unbounded("notify", value.notify);		serialize.NumberU32_Unbounded("notify", value.notify);
}		}
};		};

template<typename S>		template<typename S>
void CCmpPathfinder::SerializeCommon(S& serialize)		void CCmpPathfinder::SerializeCommon(S& serialize)
{		{
Serializer(serialize, "long requests", m_LongPathRequests);		Serializer(serialize, "long requests", m_LongPathRequests.m_Requests);
Serializer(serialize, "short requests", m_ShortPathRequests);		Serializer(serialize, "short requests", m_ShortPathRequests.m_Requests);
serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);		serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
serialize.NumberU16_Unbounded("map size", m_MapSize);		serialize.NumberU16_Unbounded("map size", m_MapSize);
}		}

void CCmpPathfinder::Serialize(ISerializer& serialize)		void CCmpPathfinder::Serialize(ISerializer& serialize)
{		{
SerializeCommon(serialize);		SerializeCommon(serialize);
}		}
Show All 25 Lines	void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
case MT_WaterChanged:		case MT_WaterChanged:
case MT_ObstructionMapShapeChanged:		case MT_ObstructionMapShapeChanged:
m_TerrainDirty = true;		m_TerrainDirty = true;
UpdateGrid();		UpdateGrid();
break;		break;
case MT_Deserialized:		case MT_Deserialized:
UpdateGrid();		UpdateGrid();
// In case we were serialised with requests pending, we need to process them.		// In case we were serialised with requests pending, we need to process them.
if (!m_ShortPathRequests.empty() \|\| !m_LongPathRequests.empty())		if (!m_ShortPathRequests.m_Requests.empty() \|\| !m_LongPathRequests.m_Requests.empty())
{		{
ENSURE(CmpPtr<ICmpObstructionManager>(GetSystemEntity()));		ENSURE(CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
StartProcessingMoves(false);		StartProcessingMoves(false);
}		}
break;		break;
}		}
}		}

▲ Show 20 Lines • Show All 522 Lines • ▼ Show 20 Lines	for (PathfinderPassability& passability : m_PassClasses)

int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();		int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();
ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);		ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);
}		}
}		}

//////////////////////////////////////////////////////////		//////////////////////////////////////////////////////////

// Async pathfinder workers

CCmpPathfinder::PathfinderWorker::PathfinderWorker() {}

template<typename T>
void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<T>&, ssize_t)
{
static_assert(sizeof(T) == 0, "Only specializations can be used");
}

template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<LongPathRequest>& 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<ShortPathRequest>& 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<ICmpObstructionManager>(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)		u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
{		{
LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };		LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
m_LongPathRequests.push_back(req);		m_LongPathRequests.m_Requests.push_back(req);
return req.ticket;		return req.ticket;
}		}

u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range,		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,		const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits,
entity_id_t group, entity_id_t notify)		entity_id_t group, entity_id_t notify)
{		{
ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };		ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
m_ShortPathRequests.push_back(req);		m_ShortPathRequests.m_Requests.push_back(req);
return req.ticket;		return req.ticket;
}		}

void CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const		void CCmpPathfinder::ComputePathImmediate(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);		m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret);
}		}

WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const		WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const
{		{
return m_VertexPathfinder->ComputeShortPath(request, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));		return m_VertexPathfinder->ComputeShortPath(request, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
}		}

void CCmpPathfinder::FetchAsyncResultsAndSendMessages()		template<typename T>
		template<typename U>
		void CCmpPathfinder::PathRequests<T>::Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder)
		{
		static_assert((std::is_same_v<T, LongPathRequest> && std::is_same_v<U, LongPathfinder>) \|\|
		(std::is_same_v<T, ShortPathRequest> && std::is_same_v<U, VertexPathfinder>));
		size_t maxN = m_Results.size();
		size_t startIndex = m_Requests.size() - m_Results.size();
		do
{		{
PROFILE2("FetchAsyncResults");		size_t workIndex = m_NextPathToCompute++;
		if (workIndex >= maxN)
		break;
		const T& req = m_Requests[startIndex + workIndex];
		PathResult& result = m_Results[workIndex];
		result.ticket = req.ticket;
		result.notify = req.notify;
		if constexpr (std::is_same_v<T, LongPathRequest>)
		pathfinder.ComputePath(*cmpPathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, result.path);
		else
		result.path = pathfinder.ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(cmpPathfinder.GetSystemEntity()));
		if (workIndex == maxN - 1)
		m_ComputeDone = true;
		}
		while (true);
		}

// We may now clear existing requests.		void CCmpPathfinder::SendRequestedPaths()
m_ShortPathRequests.clear();		{
m_LongPathRequests.clear();		PROFILE2("SendRequestedPaths");

// WARNING: the order in which moves are pulled must be consistent when using 1 or n workers.		if (!m_LongPathRequests.m_ComputeDone \|\| !m_ShortPathRequests.m_ComputeDone)
// We fetch in the same order we inserted in, but we push moves backwards, so this works.
std::vector<PathResult> results;
for (PathfinderWorker& worker : m_Workers)
{		{
results.insert(results.end(), std::make_move_iterator(worker.m_Results.begin()), std::make_move_iterator(worker.m_Results.end()));		m_ShortPathRequests.Compute(this, m_VertexPathfinder);
worker.m_Results.clear();		m_LongPathRequests.Compute(this, m_LongPathfinder);
}		}

{		{
PROFILE2("PostMessages");		PROFILE2("PostMessages");
for (PathResult& path : results)		for (PathResult& path : m_ShortPathRequests.m_Results)
{		{
CMessagePathResult msg(path.ticket, path.path);		CMessagePathResult msg(path.ticket, path.path);
GetSimContext().GetComponentManager().PostMessage(path.notify, msg);		GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
}		}
}
}

void CCmpPathfinder::StartProcessingMoves(bool useMax)		for (PathResult& path : m_LongPathRequests.m_Results)
{		{
std::vector<LongPathRequest> longRequests = GetMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves);		CMessagePathResult msg(path.ticket, path.path);
std::vector<ShortPathRequest> shortRequests = GetMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size());		GetSimContext().GetComponentManager().PostMessage(path.notify, msg);

PushRequestsToWorkers(longRequests);
PushRequestsToWorkers(shortRequests);

for (PathfinderWorker& worker : m_Workers)
worker.Work(*this);
}		}

template <typename T>
std::vector<T> CCmpPathfinder::GetMovesToProcess(std::vector<T>& requests, bool useMax, size_t maxMoves)
{
// Keep the original requests in which we need to serialize.
std::vector<T> copiedRequests;
if (useMax)
{
size_t amount = std::min(requests.size(), maxMoves);
if (amount > 0)
copiedRequests.insert(copiedRequests.begin(), requests.end() - amount, requests.end());
}		}
else		m_ShortPathRequests.ClearComputed();
copiedRequests = requests;		m_LongPathRequests.ClearComputed();

return copiedRequests;
}		}

template <typename T>		void CCmpPathfinder::StartProcessingMoves(bool useMax)
void CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from)
{		{
if (from.empty())		m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
return;		m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);

// 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;

// 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());
}
}		}

//////////////////////////////////////////////////////////		//////////////////////////////////////////////////////////

bool CCmpPathfinder::IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)		bool CCmpPathfinder::IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
{		{
PROFILE2("IsGoalReachable");		PROFILE2("IsGoalReachable");

▲ Show 20 Lines • Show All 103 Lines • Show Last 20 Lines