Differential D1918 Diff 9773 ps/trunk/source/simulation2/components/CCmpPathfinder.cpp

Changeset View

Standalone View

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

Show First 20 Lines • Show All 49 Lines • ▼ Show 20 Lines	void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
m_TerrainOnlyGrid = NULL;		m_TerrainOnlyGrid = NULL;

FlushAIPathfinderDirtinessInformation();		FlushAIPathfinderDirtinessInformation();

m_NextAsyncTicket = 1;		m_NextAsyncTicket = 1;

m_AtlasOverlay = NULL;		m_AtlasOverlay = NULL;

m_SameTurnMovesCount = 0;

m_VertexPathfinder = std::unique_ptr<VertexPathfinder>(new VertexPathfinder(m_MapSize, m_TerrainOnlyGrid));		m_VertexPathfinder = std::unique_ptr<VertexPathfinder>(new VertexPathfinder(m_MapSize, m_TerrainOnlyGrid));
m_LongPathfinder = std::unique_ptr<LongPathfinder>(new LongPathfinder());		m_LongPathfinder = std::unique_ptr<LongPathfinder>(new LongPathfinder());
m_PathfinderHier = std::unique_ptr<HierarchicalPathfinder>(new HierarchicalPathfinder());		m_PathfinderHier = std::unique_ptr<HierarchicalPathfinder>(new HierarchicalPathfinder());

// Register Relax NG validator		// Register Relax NG validator
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),
Show All 25 Lines	void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
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);
}		}

struct SerializeLongRequest		struct SerializeLongRequest
Show All 29 Lines
};		};

template<typename S>		template<typename S>
void CCmpPathfinder::SerializeCommon(S& serialize)		void CCmpPathfinder::SerializeCommon(S& serialize)
{		{
SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_LongPathRequests);		SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_LongPathRequests);
SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_ShortPathRequests);		SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_ShortPathRequests);
serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);		serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
serialize.NumberU16_Unbounded("same turn moves count", m_SameTurnMovesCount);
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 18 Lines	case MT_TerrainChanged:
m_TerrainDirty = true;		m_TerrainDirty = true;
MinimalTerrainUpdate();		MinimalTerrainUpdate();
break;		break;
case MT_WaterChanged:		case MT_WaterChanged:
case MT_ObstructionMapShapeChanged:		case MT_ObstructionMapShapeChanged:
m_TerrainDirty = true;		m_TerrainDirty = true;
UpdateGrid();		UpdateGrid();
break;		break;
case MT_TurnStart:
m_SameTurnMovesCount = 0;
break;
}		}
}		}

void CCmpPathfinder::RenderSubmit(SceneCollector& collector)		void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
{		{
m_VertexPathfinder->RenderSubmit(collector);		m_VertexPathfinder->RenderSubmit(collector);
m_PathfinderHier->RenderSubmit(collector);		m_PathfinderHier->RenderSubmit(collector);
}		}
▲ Show 20 Lines • Show All 500 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

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<typename T>
		void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<T>&, 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<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.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, 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 };		ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
m_ShortPathRequests.push_back(req);		m_ShortPathRequests.push_back(req);
return req.ticket;		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<ICmpObstructionManager>(GetSystemEntity()));		m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret);
}		}

// Async processing:		WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const

void CCmpPathfinder::FinishAsyncRequests()
{		{
PROFILE2("Finish Async Requests");		return m_VertexPathfinder->ComputeShortPath(request, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
// Save the request queue in case it gets modified while iterating
std::vector<LongPathRequest> longRequests;
m_LongPathRequests.swap(longRequests);

std::vector<ShortPathRequest> 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);
}		}

void CCmpPathfinder::ProcessLongRequests(const std::vector<LongPathRequest>& longRequests)		void CCmpPathfinder::FetchAsyncResultsAndSendMessages()
{		{
PROFILE2("Process Long Requests");		PROFILE2("FetchAsyncResults");
for (size_t i = 0; i < longRequests.size(); ++i)
		// 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<PathResult> results;
		for (PathfinderWorker& worker : m_Workers)
{		{
const LongPathRequest& req = longRequests[i];		results.insert(results.end(), std::make_move_iterator(worker.m_Results.begin()), std::make_move_iterator(worker.m_Results.end()));
WaypointPath path;		worker.m_Results.clear();
ComputePath(req.x0, req.z0, req.goal, req.passClass, path);
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
}		}

void CCmpPathfinder::ProcessShortRequests(const std::vector<ShortPathRequest>& shortRequests)
{		{
PROFILE2("Process Short Requests");		PROFILE2("PostMessages");
for (size_t i = 0; i < shortRequests.size(); ++i)		for (PathResult& path : results)
{		{
const ShortPathRequest& req = shortRequests[i];		CMessagePathResult msg(path.ticket, path.path);
WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));		GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
CMessagePathResult msg(req.ticket, path);		}
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}		}
}		}

void CCmpPathfinder::ProcessSameTurnMoves()		void CCmpPathfinder::StartProcessingMoves(bool useMax)
{		{
if (!m_LongPathRequests.empty())		std::vector<LongPathRequest> longRequests = PopMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves);
{		std::vector<ShortPathRequest> shortRequests = PopMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size());
// Figure out how many moves we can do this time
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;

if (moveCount <= 0)		PushRequestsToWorkers(longRequests);
return;		PushRequestsToWorkers(shortRequests);

// Copy the long request elements we are going to process into a new array		for (PathfinderWorker& worker : m_Workers)
std::vector<LongPathRequest> longRequests;		worker.Work(*this);
if ((i32)m_LongPathRequests.size() <= moveCount)		}

		template <typename T>
		std::vector<T> CCmpPathfinder::PopMovesToProcess(std::vector<T>& requests, bool useMax, size_t maxMoves)
		{
		std::vector<T> poppedRequests;
		if (useMax)
		{
		size_t amount = std::min(requests.size(), maxMoves);
		if (amount > 0)
{		{
m_LongPathRequests.swap(longRequests);		poppedRequests.insert(poppedRequests.begin(), std::make_move_iterator(requests.end() - amount), std::make_move_iterator(requests.end()));
moveCount = (i32)longRequests.size();		requests.erase(requests.end() - amount, requests.end());
		}
}		}
else		else
{		{
longRequests.resize(moveCount);		poppedRequests.swap(requests);
copy(m_LongPathRequests.begin(), m_LongPathRequests.begin() + moveCount, longRequests.begin());		requests.clear();
m_LongPathRequests.erase(m_LongPathRequests.begin(), m_LongPathRequests.begin() + moveCount);
}		}

ProcessLongRequests(longRequests);		return poppedRequests;

m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
}		}

if (!m_ShortPathRequests.empty())		template <typename T>
		void CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from)
{		{
// Figure out how many moves we can do now		if (from.empty())
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;

if (moveCount <= 0)
return;		return;

// Copy the short request elements we are going to process into a new array		// Trivial load-balancing, / rounds towards zero so add 1 to ensure we do push all requests.
std::vector<ShortPathRequest> shortRequests;		size_t amount = from.size() / m_Workers.size() + 1;
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);
}

ProcessShortRequests(shortRequests);

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

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

bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,		bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,
entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r,		entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r,
pass_class_t passClass) const		pass_class_t passClass) const
▲ Show 20 Lines • Show All 92 Lines • Show Last 20 Lines