Differential D1918 Diff 8147 source/simulation2/components/CCmpPathfinder.cpp

Changeset View

Standalone View

source/simulation2/components/CCmpPathfinder.cpp

Show First 20 Lines • Show All 48 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_Worker = std::unique_ptr<PathfinderWorker>(new PathfinderWorker(*this));
		StanUnsubmitted Not Done Inline Actions could it be a shared_pointer ? @vladislavbelov said we should avoid raw pointers but I'm not sure when we should use those. Stan: could it be a shared_pointer ? @vladislavbelov said we should avoid raw pointers but I'm not…
		theotherhivekingUnsubmitted Not Done Inline Actions Here is what Herb Sutter has to say about it: Guideline: Don’t pass a smart pointer as a function parameter unless you want to use or manipulate the smart pointer itself, such as to share or transfer ownership. Source: https://herbsutter.com/2013/06/05/gotw-91-solution-smart-pointer-parameters/ theotherhiveking: Here is what Herb Sutter has to say about it: >Guideline: Don’t pass a smart pointer as a…
		wraitiiAuthorUnsubmitted Done Inline Actions Here I'm just initialising the unique pointer, so using new is legitimate. wraitii: Here I'm just initialising the unique pointer, so using new is legitimate.
		elexisUnsubmitted Not Done Inline Actions The magic of emplace is that it forwards the arguments to the constructor. So if you pass it a finished type, it will call the move constructor or copy constructor if it wouldn't use copy elision. If you dont pass anything, you'll end up calling the default constructor in place: `m_Workers.emplace_back(PathfinderWorker{});` -> `m_Workers.emplace_back();` elexis: The magic of emplace is that it forwards the arguments to the constructor. So if you pass it a…
}		}

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

void CCmpPathfinder::Deinit()		void CCmpPathfinder::Deinit()
{		{
SetDebugOverlay(false); // cleans up memory		SetDebugOverlay(false); // cleans up memory
SAFE_DELETE(m_AtlasOverlay);		SAFE_DELETE(m_AtlasOverlay);
Show All 35 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 501 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(const CCmpPathfinder& pathfinder) : m_Pathfinder(pathfinder) {}

void CCmpPathfinder::ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const		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");
		}
		elexisUnsubmitted Not Done Inline Actions Should yield linker errors if the specialization is not implemented, so no need to make this a runtime error then? elexis: Should yield linker errors if the specialization is not implemented, so no need to make this a…
		wraitiiAuthorUnsubmitted Not Done Inline Actions ??? wraitii: ???
		wraitiiAuthorUnsubmitted Done Inline Actions I think an explicit static error is better than a random linker error. wraitii: I think an explicit static error is better than a random linker error.
		elexisUnsubmitted Not Done Inline Actions I didn't know that command yet, it's at compile time, so that's indeed even better than later at linking! elexis: I didn't know that command yet, it's at compile time, so that's indeed even better than later…
		wraitiiAuthorUnsubmitted Done Inline Actions Oh yeah indeed I guess that's why I was confused, this is compile-time. wraitii: Oh yeah indeed I guess that's why I was confused, this is compile-time.

		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()
		{
		while (!m_LongRequests.empty())
		{
		const LongPathRequest& req = m_LongRequests.back();
		WaypointPath path;
		m_Pathfinder.m_LongPathfinder->ComputePath(*m_Pathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, path);
		m_Results.push_back({req.ticket, req.notify, path});
		elexisUnsubmitted Not Done Inline Actions `m_Results.push_back({req.ticket, req.notify, path});` -> `m_Results.emplace_back(req.ticket, req.notify, path);` I think it's equivalent code flow, but the first one relies on copy elision, the second one is ensured to construct in place without copy or move assignment / constructor. elexis: `m_Results.push_back({req.ticket, req.notify, path});` -> `m_Results.emplace_back(req.ticket…

		m_LongRequests.pop_back();
		elexisUnsubmitted Not Done Inline Actions (perhaps one can avoid back() pop_back() with an erase idiom, but that sounds perverse) elexis: (perhaps one can avoid back() pop_back() with an erase idiom, but that sounds perverse)
		}

		while (!m_ShortRequests.empty())
		{
		const ShortPathRequest& req = m_ShortRequests.back();
		WaypointPath path = m_Pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(m_Pathfinder.GetSystemEntity()));
		m_Results.push_back({req.ticket, req.notify, path});
		elexisUnsubmitted Not Done Inline Actions (same) elexis: (same)

		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)
{		{
		elexisUnsubmitted Not Done Inline Actions ComputeShortPathAsync(\n \t... \t...) { ? elexis: ``` ComputeShortPathAsync(\n \t... \t...) { ``` ?
		wraitiiAuthorUnsubmitted Done Inline Actions not sure how we indent in such cases. It's aligned on the parenthesis here. wraitii: not sure how we indent in such cases. It's aligned on the parenthesis here.
		wraitiiAuthorUnsubmitted Done Inline Actions I've tried both, I find aligning on the parenthesis much more readable. wraitii: I've tried both, I find aligning on the parenthesis much more readable.
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);
}		}
		elexisUnsubmitted Not Done Inline Actions (wondering whether its faster to pass a point with 2 components by ref or those two numbers, probably the latter) elexis: (wondering whether its faster to pass a point with 2 components by ref or those two numbers…
		wraitiiAuthorUnsubmitted Done Inline Actions Yeah we could use some interface streamlining here, but that ought to come later. wraitii: Yeah we could use some interface streamlining here, but that ought to come later.

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

void CCmpPathfinder::FinishAsyncRequests()
{		{
PROFILE2("Finish Async Requests");		return m_VertexPathfinder->ComputeShortPath(request, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
		elexisUnsubmitted Not Done Inline Actions Should check with clang that these proxies are inlined: CC="clang -Rpass=inline" CXX="clang++ -Rpass=inline" make -j3 (Gotta save the log and grep for function name or file + line nr) elexis: Should check with clang that these proxies are inlined: > CC="clang -Rpass=inline"…
		wraitiiAuthorUnsubmitted Done Inline Actions Definitely completely irrelevant, performance wise, either way, but if one wants to, sure. wraitii: Definitely completely irrelevant, performance wise, either way, but if one wants to, sure.
// Save the request queue in case it gets modified while iterating		}
std::vector<LongPathRequest> longRequests;
m_LongPathRequests.swap(longRequests);

std::vector<ShortPathRequest> shortRequests;		void CCmpPathfinder::FetchAsyncResultsAndSendMessages()
m_ShortPathRequests.swap(shortRequests);		{
		PROFILE2("FetchAsyncResults");

// TODO: we should only compute one path per entity per turn		std::vector<PathResult> results;

// TODO: this computation should be done incrementally, spread		results.insert(results.end(), std::make_move_iterator(m_Worker->m_Results.begin()), std::make_move_iterator(m_Worker->m_Results.end()));
// across multiple frames (or even multiple turns)		m_Worker->m_Results.clear();

ProcessLongRequests(longRequests);
ProcessShortRequests(shortRequests);
}

void CCmpPathfinder::ProcessLongRequests(const std::vector<LongPathRequest>& longRequests)
{		{
PROFILE2("Process Long Requests");		PROFILE2("PostMessages");
for (size_t i = 0; i < longRequests.size(); ++i)		for (PathResult& path : results)
{		{
const LongPathRequest& req = longRequests[i];		CMessagePathResult msg(path.ticket, path.path);
WaypointPath path;		GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
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)		void CCmpPathfinder::StartProcessingMoves(bool useMax)
{		{
PROFILE2("Process Short Requests");		std::vector<LongPathRequest> longRequests = PopMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves);
for (size_t i = 0; i < shortRequests.size(); ++i)		std::vector<ShortPathRequest> shortRequests = PopMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size());
{
const ShortPathRequest& req = shortRequests[i];		PushRequestsToWorker(longRequests);
WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));		PushRequestsToWorker(shortRequests);
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);		m_Worker->Work();
}
}		}

void CCmpPathfinder::ProcessSameTurnMoves()		template <typename T>
		std::vector<T> CCmpPathfinder::PopMovesToProcess(std::vector<T>& requests, bool useMax, size_t maxMoves)
{		{
if (!m_LongPathRequests.empty())		std::vector<T> poppedRequests;
		if (useMax)
{		{
// Figure out how many moves we can do this time		size_t amount = std::min(poppedRequests.size(), maxMoves);
		elexisUnsubmitted Not Done Inline Actions (copy elision should hold, may verify with clang) elexis: (copy elision should hold, may verify with clang)
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;		if (amount > 0)

if (moveCount <= 0)
return;

// Copy the long request elements we are going to process into a new array
std::vector<LongPathRequest> longRequests;
if ((i32)m_LongPathRequests.size() <= moveCount)
{		{
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::PushRequestsToWorker(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		m_Worker->PushRequests(from, from.size());
std::vector<ShortPathRequest> shortRequests;		from.erase(from.begin(), from.end());
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);
}
}		}

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

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 91 Lines • Show Last 20 Lines