Differential D14 Diff 7121 source/simulation2/components/CCmpPathfinder.cpp

Changeset View

Standalone View

source/simulation2/components/CCmpPathfinder.cpp

	Show All 22 Lines
	#include "precompiled.h"			#include "precompiled.h"

	#include "CCmpPathfinder_Common.h"			#include "CCmpPathfinder_Common.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 "ps/ConfigDB.h"
	#include "renderer/Scene.h"			#include "renderer/Scene.h"
	#include "simulation2/MessageTypes.h"			#include "simulation2/MessageTypes.h"
	#include "simulation2/components/ICmpObstruction.h"			#include "simulation2/components/ICmpObstruction.h"
	#include "simulation2/components/ICmpObstructionManager.h"			#include "simulation2/components/ICmpObstructionManager.h"
	#include "simulation2/components/ICmpTerrain.h"			#include "simulation2/components/ICmpTerrain.h"
	#include "simulation2/components/ICmpWaterManager.h"			#include "simulation2/components/ICmpWaterManager.h"
	#include "simulation2/helpers/Rasterize.h"			#include "simulation2/helpers/Rasterize.h"
	#include "simulation2/serialization/SerializeTemplates.h"			#include "simulation2/serialization/SerializeTemplates.h"

				#include "tools/atlas/GameInterface/GameLoop.h"

	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;
				StanUnsubmitted Not Done Inline Actions If you want to change this line replace the c style cast by a c++ cast :) Stan: If you want to change this line replace the c style cast by a c++ cast :)
				Kuba386Unsubmitted Done Inline Actions Done in next diff. Kuba386: Done in next diff.
				StanUnsubmitted Not Done Inline Actions Do we have a conversion to unsigned int ? Stan: Do we have a conversion to unsigned int ?
				StanUnsubmitted Not Done Inline Actions Same here If you want to change this line replace the c style cast by a c++ cast :) Stan: Same here If you want to change this line replace the c style cast by a c++ cast :)
				Kuba386Unsubmitted Done Inline Actions Done in next diff. Same for others. :) Kuba386: Done in next diff. Same for others. :)
	m_Grid = NULL;			m_Grid = NULL;
	m_TerrainOnlyGrid = NULL;			m_TerrainOnlyGrid = NULL;

	FlushAIPathfinderDirtinessInformation();			FlushAIPathfinderDirtinessInformation();

	m_NextAsyncTicket = 1;			m_NextAsyncTicket = 1;

	m_DebugOverlay = false;			m_DebugOverlay = false;
	m_AtlasOverlay = NULL;			m_AtlasOverlay = NULL;

	m_SameTurnMovesCount = 0;

	// 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),
	// 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");
				wraitiiAuthorUnsubmitted Done Inline Actions LOGINFO wraitii: LOGINFO

	// Previously all move commands during a turn were
	// queued up and processed asynchronously at the start
	// of the next turn. Now we are processing queued up
	// events several times duing the turn. This improves
	// responsiveness and units move more smoothly especially.
	// when in formation. There is still a call at the
	// beginning of a turn to process all outstanding moves -
	// 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");
				StanUnsubmitted Not Done Inline Actions cpp cast here as well. Stan: cpp cast here as well.
				StanUnsubmitted Not Done Inline Actions Though it might be better to use an u8 everywhere ? Stan: Though it might be better to use an u8 everywhere ?
				StanUnsubmitted Not Done Inline Actions Why 64 and not 255 ? Stan: Why 64 and not 255 ?
				Kuba386Unsubmitted Done Inline Actions 64 is max value in UI, and so should be there. Why not 255? This case is intended to protect players from setting invalid values. values <0 are handled like 0 is, and I've assumed that user probably wouldn't want to run more than 64 threads. I don't know anyone who has 32-core CPU. We can however raise this limit a bit. 255 seems reasonable value. Kuba386: 64 is max value in UI, and so should be there. Why not 255? This case is intended to protect…
	m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();			m_MaxSameTurnMoves = (u16) pathingSettings.GetChild("MaxSameTurnMoves").ToInt();

				const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild(
	const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();			"PassabilityClasses").GetChildren();
				wraitiiAuthorUnsubmitted Done Inline Actions else wraitii: else
	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;
	}			}

				// check if user wants to use custom thread count.

				bool useCustomThreadCount = false;
				CFG_GET_VAL("pathfinder.usenumthreads", useCustomThreadCount);
				if (useCustomThreadCount)
				{
				int threadcount;
				CFG_GET_VAL("pathfinder.numthreads", threadcount);

				std::cerr << "Using " << threadcount << "pathfinder threads" << "\n";

				if (threadcount < 1 \|\| (g_AtlasGameLoop && g_AtlasGameLoop->running) \|\| threadcount > 64)
				{
				m_UseThreading = false;
				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
				}
				else
				{
				for (size_t i = 0; i < threadcount; ++i)
				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
				}
				}
				else
				wraitiiAuthorUnsubmitted Done Inline Actions In general here: I don't like the NDEBUG stuff, either it's worth having as LOGINFO or it's not and then delete. This is also indented a lot but that might be the debug noise. wraitii: In general here: I don't like the NDEBUG stuff, either it's worth having as LOGINFO or it's not…
				Kuba386Unsubmitted Not Done Inline Actions I've just removed these since count of pathfinder threads is not likely to be different from desired one because of a bug. Kuba386: I've just removed these since count of pathfinder threads is not likely to be different from…
				{
				// do not use threads if we are single-core (obviously) or are in atlas (as we might modify state in-between turns).
				// the worker thread will only call std::thread if we're using threading, so if not it'll be synchronous and single-thread.
				if (std::thread::hardware_concurrency() <= 1 \|\| (g_AtlasGameLoop && g_AtlasGameLoop->running))
				{
				m_UseThreading = false;
				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
				}
				else
				{
				// create one thread if we have two cores, otherwise 2*(number of cores-1)
				StanUnsubmitted Not Done Inline Actions Comments start with Capitals. Stan: Comments start with Capitals.
				// this way we'll benefit from hardware load-balancing a little.
				if (std::thread::hardware_concurrency() == 2)
				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
				else
				for (size_t i = 0; i < (std::thread::hardware_concurrency() - 1) * 2; ++i)
				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
				}
				}
	}			}

	void CCmpPathfinder::Deinit()			void CCmpPathfinder::Deinit()
				StanUnsubmitted Not Done Inline Actions Is it useful? Stan: Is it useful?
	{			{
				for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
				worker->PrepareToKill();
				m_MainThreadSignal.notify_all();
				for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
				StanUnsubmitted Not Done Inline Actions We don't use auto as a general rule of thumb. Stan: We don't use auto as a general rule of thumb.
				delete worker;

				m_WorkerThreads.clear();
	SetDebugOverlay(false); // cleans up memory			SetDebugOverlay(false); // cleans up memory
	SAFE_DELETE(m_AtlasOverlay);			SAFE_DELETE(m_AtlasOverlay);
				StanUnsubmitted Not Done Inline Actions We don't use auto as a general rule of thumb. Stan: We don't use auto as a general rule of thumb.
				vladislavbelovUnsubmitted Done Inline Actions It's not good to access atlas stuff from simulation. You need to use a common source, like a thread manager. The same for the number of threads. vladislavbelov: It's not good to access atlas stuff from simulation. You need to use a common source, like a…
				wraitiiAuthorUnsubmitted Done Inline Actions Sorry, I don't understand what you mean here. You're saying we should implement a "Thread Manager" class at a 'top-level' global that tells us how many threads we want for pathfinding? I'm not clear how that's much better for now. Also I somewhat intend to remove this as if we had proper mutex protection it wouldn't be needed. wraitii: Sorry, I don't understand what you mean here. You're saying we should implement a "Thread…
				SilierUnsubmitted Done Inline Actions well, in this part of code threads are going to be created, they do not exists at this point so no concurency here. wantedThreads is local (in scope of function) variable - > no problem even with threads as every would have its own unique variable with no option to see or change the one from another thread g_Atlas & & g_Atlas->running is only reading, as far as I know you can safely read from variable with as many threads as you wish and it is safe but again this function is running in main thread only Silier: well, in this part of code threads are going to be created, they do not exists at this point so…
				vladislavbelovUnsubmitted Done Inline Actions Sorry, I don't understand what you mean here. You're saying we should implement a "Thread Manager" class at a 'top-level' global that tells us how many threads we want for pathfinding? I mean that the component shouldn't decide about the number of threads and shouldn't communicate with the Atlas directly. We may use ThreadUtil to calculate right number of threads. Because we might have separate threads for other purposes, and we need to manage them somehow. g_Atlas & & g_Atlas->running is only reading, as far as I know you can safely read from variable with as many threads as you wish and it is safe but again this function is running in main thread only It's not the syntax error but the semantic for me. vladislavbelov: > Sorry, I don't understand what you mean here. You're saying we should implement a "Thread…
				wraitiiAuthorUnsubmitted Done Inline Actions OK, makes sense for ThreadUtil. wraitii: OK, makes sense for ThreadUtil.

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

	struct SerializeLongRequest			struct SerializeLongRequest
	{			{
	template<typename S>			template<typename S>
	void operator()(S& serialize, const char* UNUSED(name), AsyncLongPathRequest& value)			void operator()(S& serialize, const char* UNUSED(name), AsyncLongPathRequest& value)
				vladislavbelovUnsubmitted Done Inline Actions Use `std::unique_ptr` instead, raw pointers are dangerous. vladislavbelov: Use `std::unique_ptr` instead, raw pointers are dangerous.
				wraitiiAuthorUnsubmitted Done Inline Actions Indeed. wraitii: Indeed.
	{			{
	serialize.NumberU32_Unbounded("ticket", value.ticket);			serialize.NumberU32_Unbounded("ticket", value.ticket);
	serialize.NumberFixed_Unbounded("x0", value.x0);			serialize.NumberFixed_Unbounded("x0", value.x0);
	serialize.NumberFixed_Unbounded("z0", value.z0);			serialize.NumberFixed_Unbounded("z0", value.z0);
	SerializeGoal()(serialize, "goal", value.goal);			SerializeGoal()(serialize, "goal", value.goal);
	serialize.NumberU16_Unbounded("pass class", value.passClass);			serialize.NumberU16_Unbounded("pass class", value.passClass);
	serialize.NumberU32_Unbounded("notify", value.notify);			serialize.NumberU32_Unbounded("notify", value.notify);
	}			}
	};			};

	struct SerializeShortRequest			struct SerializeShortRequest
	{			{
	template<typename S>			template<typename S>
				wraitiiAuthorUnsubmitted Done Inline Actions Also missed these two. wraitii: Also missed these two.
	void operator()(S& serialize, const char* UNUSED(name), AsyncShortPathRequest& value)			void operator()(S& serialize, const char* UNUSED(name), AsyncShortPathRequest& value)
	{			{
	serialize.NumberU32_Unbounded("ticket", value.ticket);			serialize.NumberU32_Unbounded("ticket", value.ticket);
	serialize.NumberFixed_Unbounded("x0", value.x0);			serialize.NumberFixed_Unbounded("x0", value.x0);
	serialize.NumberFixed_Unbounded("z0", value.z0);			serialize.NumberFixed_Unbounded("z0", value.z0);
	serialize.NumberFixed_Unbounded("clearance", value.clearance);			serialize.NumberFixed_Unbounded("clearance", value.clearance);
	serialize.NumberFixed_Unbounded("range", value.range);			serialize.NumberFixed_Unbounded("range", value.range);
	SerializeGoal()(serialize, "goal", value.goal);			SerializeGoal()(serialize, "goal", value.goal);
	serialize.NumberU16_Unbounded("pass class", value.passClass);			serialize.NumberU16_Unbounded("pass class", value.passClass);
	serialize.Bool("avoid moving units", value.avoidMovingUnits);			serialize.Bool("avoid moving units", value.avoidMovingUnits);
	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)
	{			{
	SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_AsyncLongPathRequests);			SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_AsyncLongPathRequests);
	SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_AsyncShortPathRequests);			SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_AsyncShortPathRequests);
	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);
	}			}

	void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)			void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
	{			{
	Init(paramNode);			Init(paramNode);

	SerializeCommon(deserialize);			SerializeCommon(deserialize);
	}			}

	void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))			void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
	{			{
	switch (msg.GetType())			switch (msg.GetType())
				StanUnsubmitted Not Done Inline Actions Maybe all the cases should have curly braces. No strong feeling. Stan: Maybe all the cases should have curly braces. No strong feeling.
				wraitiiAuthorUnsubmitted Done Inline Actions Will need to be untapped as that's how we do switch cases (don't ask me why). wraitii: Will need to be untapped as that's how we do switch cases (don't ask me why).
	{			{
	case MT_RenderSubmit:			case MT_RenderSubmit:
	{			{
	const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);			const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
	RenderSubmit(msgData.collector);			RenderSubmit(msgData.collector);
	break;			break;
	}			}
	case MT_TerrainChanged:			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)
	{			{
	for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)			for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)
	collector.Submit(&m_DebugOverlayShortPathLines[i]);			collector.Submit(&m_DebugOverlayShortPathLines[i]);

	m_LongPathfinder.HierarchicalRenderSubmit(collector);			m_LongPathfinder.HierarchicalRenderSubmit(collector);
	}			}

	void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)			void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
	{			{
	if (enable)			if (enable)
	{			{
	if (!m_AtlasOverlay)			if (!m_AtlasOverlay)
	m_AtlasOverlay = new AtlasOverlay(this, passClass);			m_AtlasOverlay = new AtlasOverlay(this, passClass);
	m_AtlasOverlay->m_PassClass = passClass;			m_AtlasOverlay->m_PassClass = passClass;
	}			}
	else			else
	SAFE_DELETE(m_AtlasOverlay);			SAFE_DELETE(m_AtlasOverlay);
	}			}

	pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const			pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
	{			{
	std::map<std::string, pass_class_t>::const_iterator it = m_PassClassMasks.find(name);			std::map<std::string, pass_class_t>::const_iterator it = m_PassClassMasks.find(name);
	if (it == m_PassClassMasks.end())			if (it == m_PassClassMasks.end())
	{			{
	LOGERROR("Invalid passability class name '%s'", name.c_str());			LOGERROR("Invalid passability class name '%s'", name.c_str());
	return 0;			return 0;
	}			}

	return it->second;			return it->second;
	}			}

	void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const			void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const
	{			{
	passClasses = m_PassClassMasks;			passClasses = m_PassClassMasks;
	}			}

	void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& nonPathfindingPassClasses, std::map<std::string, pass_class_t>& pathfindingPassClasses) const			void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& nonPathfindingPassClasses,
				std::map<std::string, pass_class_t>& pathfindingPassClasses) const
	{			{
	for (const std::pair<std::string, pass_class_t>& pair : m_PassClassMasks)			for (const std::pair<std::string, pass_class_t>& pair : m_PassClassMasks)
	{			{
	if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))			if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
	pathfindingPassClasses[pair.first] = pair.second;			pathfindingPassClasses[pair.first] = pair.second;
	else			else
	nonPathfindingPassClasses[pair.first] = pair.second;			nonPathfindingPassClasses[pair.first] = pair.second;
	}			}
	}			}

	const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const			const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
	{			{
	for (const PathfinderPassability& passability : m_PassClasses)			for (const PathfinderPassability& passability : m_PassClasses)
	{			{
	if (passability.m_Mask == passClass)			if (passability.m_Mask == passClass)
	return &passability;			return &passability;
	}			}

	return NULL;			return NULL;
	}			}

	const Grid<NavcellData>& CCmpPathfinder::GetPassabilityGrid()			const Grid<NavcellData>& CCmpPathfinder::GetPassabilityGrid()
	{			{
	if (!m_Grid)			if (!m_Grid)
	UpdateGrid();			UpdateGrid();

	return *m_Grid;			return *m_Grid;
	}			}

	/**			/**
	* Given a grid of passable/impassable navcells (based on some passability mask),			* Given a grid of passable/impassable navcells (based on some passability mask),
	* computes a new grid where a navcell is impassable (per that mask) if			* computes a new grid where a navcell is impassable (per that mask) if
	* it is <=clearance navcells away from an impassable navcell in the original grid.			* it is <=clearance navcells away from an impassable navcell in the original grid.
	* The results are ORed onto the original grid.			* The results are ORed onto the original grid.
	*			*
	* This is used for adding clearance onto terrain-based navcell passability.			* This is used for adding clearance onto terrain-based navcell passability.
	*			*
	* TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as			* TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
	* Euclidean distances; currently it effectively does dist=max(dx,dy) instead.			* Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
	* This would only really be a problem for big clearances.			* This would only really be a problem for big clearances.
	*/			*/
	static void ExpandImpassableCells(Grid<NavcellData>& grid, u16 clearance, pass_class_t mask)			static void ExpandImpassableCells(Grid<NavcellData>& grid, u16 clearance, pass_class_t mask)
	{			{
	PROFILE3("ExpandImpassableCells");			//PROFILE3("ExpandImpassableCells");

	u16 w = grid.m_W;			u16 w = grid.m_W;
	u16 h = grid.m_H;			u16 h = grid.m_H;

	// First expand impassable cells horizontally into a temporary 1-bit grid			// First expand impassable cells horizontally into a temporary 1-bit grid
	Grid<u8> tempGrid(w, h);			Grid<u8> tempGrid(w, h);
	for (u16 j = 0; j < h; ++j)			for (u16 j = 0; j < h; ++j)
	{			{
	// New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance			// New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance

	// Count the number of blocked cells around i=0			// Count the number of blocked cells around i=0
	u16 numBlocked = 0;			u16 numBlocked = 0;
	for (u16 i = 0; i <= clearance && i < w; ++i)			for (u16 i = 0; i <= clearance && i < w; ++i)
	if (!IS_PASSABLE(grid.get(i, j), mask))			if (!IS_PASSABLE(grid.get(i, j), mask))
	++numBlocked;			++numBlocked;

	for (u16 i = 0; i < w; ++i)			for (u16 i = 0; i < w; ++i)
	{			{
	// Store a flag if blocked by at least one nearby cell			// Store a flag if blocked by at least one nearby cell
	if (numBlocked)			if (numBlocked)
	tempGrid.set(i, j, 1);			tempGrid.set(i, j, 1);

	// Slide the numBlocked window along:			// Slide the numBlocked window along:
	// remove the old i-clearance value, add the new (i+1)+clearance			// remove the old i-clearance value, add the new (i+1)+clearance
	// (avoiding overflowing the grid)			// (avoiding overflowing the grid)
	if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))			if (i >= clearance && !IS_PASSABLE(grid.get(i - clearance, j), mask))
	--numBlocked;			--numBlocked;
	if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))			if (i + 1 + clearance < w && !IS_PASSABLE(grid.get(i + 1 + clearance, j), mask))
	++numBlocked;			++numBlocked;
	}			}
	}			}

	for (u16 i = 0; i < w; ++i)			for (u16 i = 0; i < w; ++i)
	{			{
	// New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance			// New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance
	// Count the number of blocked cells around j=0			// Count the number of blocked cells around j=0
	u16 numBlocked = 0;			u16 numBlocked = 0;
	for (u16 j = 0; j <= clearance && j < h; ++j)			for (u16 j = 0; j <= clearance && j < h; ++j)
	if (tempGrid.get(i, j))			if (tempGrid.get(i, j))
	++numBlocked;			++numBlocked;

	for (u16 j = 0; j < h; ++j)			for (u16 j = 0; j < h; ++j)
	{			{
	// Add the mask if blocked by at least one nearby cell			// Add the mask if blocked by at least one nearby cell
	if (numBlocked)			if (numBlocked)
	grid.set(i, j, grid.get(i, j) \| mask);			grid.set(i, j, grid.get(i, j) \| mask);

	// Slide the numBlocked window along:			// Slide the numBlocked window along:
	// remove the old j-clearance value, add the new (j+1)+clearance			// remove the old j-clearance value, add the new (j+1)+clearance
	// (avoiding overflowing the grid)			// (avoiding overflowing the grid)
	if (j >= clearance && tempGrid.get(i, j-clearance))			if (j >= clearance && tempGrid.get(i, j - clearance))
	--numBlocked;			--numBlocked;
	if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))			if (j + 1 + clearance < h && tempGrid.get(i, j + 1 + clearance))
	++numBlocked;			++numBlocked;
	}			}
	}			}
	}			}

	Grid<u16> CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)			Grid<u16> CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
	{			{
	PROFILE3("ComputeShoreGrid");			//PROFILE3("ComputeShoreGrid");

	CmpPtr<ICmpWaterManager> cmpWaterManager(GetSystemEntity());			CmpPtr<ICmpWaterManager> cmpWaterManager(GetSystemEntity());

	// TODO: these bits should come from ICmpTerrain			// TODO: these bits should come from ICmpTerrain
	CTerrain& terrain = GetSimContext().GetTerrain();			CTerrain& terrain = GetSimContext().GetTerrain();

	// avoid integer overflow in intermediate calculation			// avoid integer overflow in intermediate calculation
	const u16 shoreMax = 32767;			const u16 shoreMax = 32767;

	// First pass - find underwater tiles			// First pass - find underwater tiles
	Grid<u8> waterGrid(m_MapSize, m_MapSize);			Grid<u8> waterGrid(m_MapSize, m_MapSize);
	for (u16 j = 0; j < m_MapSize; ++j)			for (u16 j = 0; j < m_MapSize; ++j)
	{			{
	for (u16 i = 0; i < m_MapSize; ++i)			for (u16 i = 0; i < m_MapSize; ++i)
	{			{
	fixed x, z;			fixed x, z;
	Pathfinding::TileCenter(i, j, x, z);			Pathfinding::TileCenter(i, j, x, z);

	bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));			bool underWater =
				cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
	waterGrid.set(i, j, underWater ? 1 : 0);			waterGrid.set(i, j, underWater ? 1 : 0);
	}			}
	}			}

	// Second pass - find shore tiles			// Second pass - find shore tiles
	Grid<u16> shoreGrid(m_MapSize, m_MapSize);			Grid<u16> shoreGrid(m_MapSize, m_MapSize);
	for (u16 j = 0; j < m_MapSize; ++j)			for (u16 j = 0; j < m_MapSize; ++j)
	{			{
	for (u16 i = 0; i < m_MapSize; ++i)			for (u16 i = 0; i < m_MapSize; ++i)
	{			{
	// Find a land tile			// Find a land tile
	if (!waterGrid.get(i, j))			if (!waterGrid.get(i, j))
	{			{
	// If it's bordered by water, it's a shore tile			// If it's bordered by water, it's a shore tile
	if ((i > 0 && waterGrid.get(i-1, j)) \|\| (i > 0 && j < m_MapSize-1 && waterGrid.get(i-1, j+1)) \|\| (i > 0 && j > 0 && waterGrid.get(i-1, j-1))			if ((i > 0 && waterGrid.get(i - 1, j)) \|\| (i > 0 && j < m_MapSize - 1 && waterGrid.get(i - 1, j + 1)) \|\|
	\|\| (i < m_MapSize-1 && waterGrid.get(i+1, j)) \|\| (i < m_MapSize-1 && j < m_MapSize-1 && waterGrid.get(i+1, j+1)) \|\| (i < m_MapSize-1 && j > 0 && waterGrid.get(i+1, j-1))			(i > 0 && j > 0 && waterGrid.get(i - 1, j - 1))
				\|\| (i < m_MapSize - 1 && waterGrid.get(i + 1, j)) \|\|
				(i < m_MapSize - 1 && j < m_MapSize - 1 && waterGrid.get(i + 1, j + 1)) \|\|
				(i < m_MapSize - 1 && j > 0 && waterGrid.get(i + 1, j - 1))
	\|\| (j > 0 && waterGrid.get(i, j-1)) \|\| (j < m_MapSize-1 && waterGrid.get(i, j+1))			\|\| (j > 0 && waterGrid.get(i, j - 1)) \|\| (j < m_MapSize - 1 && waterGrid.get(i, j + 1))
	)			)
	shoreGrid.set(i, j, 0);			shoreGrid.set(i, j, 0);
	else			else
	shoreGrid.set(i, j, shoreMax);			shoreGrid.set(i, j, shoreMax);
	}			}
	// If we want to expand on water, we want water tiles not to be shore tiles			// If we want to expand on water, we want water tiles not to be shore tiles
	else if (expandOnWater)			else if (expandOnWater)
	shoreGrid.set(i, j, shoreMax);			shoreGrid.set(i, j, shoreMax);
	}			}
	}			}

	// Expand influences on land to find shore distance			// Expand influences on land to find shore distance
	for (u16 y = 0; y < m_MapSize; ++y)			for (u16 y = 0; y < m_MapSize; ++y)
	{			{
	u16 min = shoreMax;			u16 min = shoreMax;
	for (u16 x = 0; x < m_MapSize; ++x)			for (u16 x = 0; x < m_MapSize; ++x)
	{			{
	if (!waterGrid.get(x, y) \|\| expandOnWater)			if (!waterGrid.get(x, y) \|\| expandOnWater)
	{			{
	u16 g = shoreGrid.get(x, y);			u16 g = shoreGrid.get(x, y);
	if (g > min)			if (g > min)
	shoreGrid.set(x, y, min);			shoreGrid.set(x, y, min);
	else if (g < min)			else if (g < min)
	min = g;			min = g;

	++min;			++min;
	}			}
	}			}
	for (u16 x = m_MapSize; x > 0; --x)			for (u16 x = m_MapSize; x > 0; --x)
	{			{
	if (!waterGrid.get(x-1, y) \|\| expandOnWater)			if (!waterGrid.get(x - 1, y) \|\| expandOnWater)
	{			{
	u16 g = shoreGrid.get(x-1, y);			u16 g = shoreGrid.get(x - 1, y);
	if (g > min)			if (g > min)
	shoreGrid.set(x-1, y, min);			shoreGrid.set(x - 1, y, min);
	else if (g < min)			else if (g < min)
	min = g;			min = g;

	++min;			++min;
	}			}
	}			}
	}			}
	for (u16 x = 0; x < m_MapSize; ++x)			for (u16 x = 0; x < m_MapSize; ++x)
	{			{
	u16 min = shoreMax;			u16 min = shoreMax;
	for (u16 y = 0; y < m_MapSize; ++y)			for (u16 y = 0; y < m_MapSize; ++y)
	{			{
	if (!waterGrid.get(x, y) \|\| expandOnWater)			if (!waterGrid.get(x, y) \|\| expandOnWater)
	{			{
	u16 g = shoreGrid.get(x, y);			u16 g = shoreGrid.get(x, y);
	if (g > min)			if (g > min)
	shoreGrid.set(x, y, min);			shoreGrid.set(x, y, min);
	else if (g < min)			else if (g < min)
	min = g;			min = g;

	++min;			++min;
	}			}
	}			}
	for (u16 y = m_MapSize; y > 0; --y)			for (u16 y = m_MapSize; y > 0; --y)
	{			{
	if (!waterGrid.get(x, y-1) \|\| expandOnWater)			if (!waterGrid.get(x, y - 1) \|\| expandOnWater)
	{			{
	u16 g = shoreGrid.get(x, y-1);			u16 g = shoreGrid.get(x, y - 1);
	if (g > min)			if (g > min)
	shoreGrid.set(x, y-1, min);			shoreGrid.set(x, y - 1, min);
	else if (g < min)			else if (g < min)
	min = g;			min = g;

	++min;			++min;
	}			}
	}			}
	}			}

	return shoreGrid;			return shoreGrid;
	}			}

	void CCmpPathfinder::UpdateGrid()			void CCmpPathfinder::UpdateGrid()
	{			{
	PROFILE3("UpdateGrid");			//PROFILE3("UpdateGrid");

	CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);			CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
	if (!cmpTerrain)			if (!cmpTerrain)
	return; // error			return; // error

	u16 terrainSize = cmpTerrain->GetTilesPerSide();			u16 terrainSize = cmpTerrain->GetTilesPerSide();
	if (terrainSize == 0)			if (terrainSize == 0)
	return;			return;

	// If the terrain was resized then delete the old grid data			// If the terrain was resized then delete the old grid data
	if (m_Grid && m_MapSize != terrainSize)			if (m_Grid && m_MapSize != terrainSize)
	{			{
	SAFE_DELETE(m_Grid);			SAFE_DELETE(m_Grid);
	SAFE_DELETE(m_TerrainOnlyGrid);			SAFE_DELETE(m_TerrainOnlyGrid);
	}			}

	// Initialise the terrain data when first needed			// Initialise the terrain data when first needed
	if (!m_Grid)			if (!m_Grid)
	{			{
	m_MapSize = terrainSize;			m_MapSize = terrainSize;
	m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);			m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE);

	SAFE_DELETE(m_TerrainOnlyGrid);			SAFE_DELETE(m_TerrainOnlyGrid);
	m_TerrainOnlyGrid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);			m_TerrainOnlyGrid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE);


	m_DirtinessInformation = { true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };			m_DirtinessInformation = {true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE)};
	m_AIPathfinderDirtinessInformation = m_DirtinessInformation;			m_AIPathfinderDirtinessInformation = m_DirtinessInformation;

	m_TerrainDirty = true;			m_TerrainDirty = true;
	}			}

	// The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.			// The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
	#ifdef NDEBUG			#ifdef NDEBUG
	ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));			ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
	#else			#else
	ENSURE(m_DirtinessInformation.dirtinessGrid == Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));			ENSURE(m_DirtinessInformation.dirtinessGrid ==
				Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));
	#endif			#endif

	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);			CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
	cmpObstructionManager->UpdateInformations(m_DirtinessInformation);			cmpObstructionManager->UpdateInformations(m_DirtinessInformation);

	if (!m_DirtinessInformation.dirty && !m_TerrainDirty)			if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
	return;			return;

	// If the terrain has changed, recompute m_Grid			// If the terrain has changed, recompute m_Grid
	// Else, use data from m_TerrainOnlyGrid and add obstructions			// Else, use data from m_TerrainOnlyGrid and add obstructions
	if (m_TerrainDirty)			if (m_TerrainDirty)
	{			{
	TerrainUpdateHelper();			TerrainUpdateHelper();

	m_Grid = m_TerrainOnlyGrid;			m_Grid = m_TerrainOnlyGrid;

	m_TerrainDirty = false;			m_TerrainDirty = false;
	m_DirtinessInformation.globallyDirty = true;			m_DirtinessInformation.globallyDirty = true;
	}			}
	else if (m_DirtinessInformation.globallyDirty)			else if (m_DirtinessInformation.globallyDirty)
	{			{
	ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));			ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
	memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)(m_Grid->m_H)sizeof(NavcellData));			memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W) * (m_Grid->m_H) * sizeof(NavcellData));
	}			}
	else			else
	{			{
	ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));			ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));

	for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)			for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
	for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)			for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
	if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)			if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
	m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));			m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
	}			}

	// Add obstructions onto the grid			// Add obstructions onto the grid
	cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);			cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);

	// Update the long-range pathfinder			// Update the long-range pathfinder
	if (m_DirtinessInformation.globallyDirty)			if (m_DirtinessInformation.globallyDirty)
	{			{
	std::map<std::string, pass_class_t> nonPathfindingPassClasses, pathfindingPassClasses;			std::map<std::string, pass_class_t> nonPathfindingPassClasses, pathfindingPassClasses;
	GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);			GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
	m_LongPathfinder.Reload(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);			m_LongPathfinder.Reload(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
	}			}
	else			else
	m_LongPathfinder.Update(m_Grid, m_DirtinessInformation.dirtinessGrid);			m_LongPathfinder.Update(m_Grid, m_DirtinessInformation.dirtinessGrid);

	// Remember the necessary updates that the AI pathfinder will have to perform as well			// Remember the necessary updates that the AI pathfinder will have to perform as well
	m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);			m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);
	}			}

	void CCmpPathfinder::MinimalTerrainUpdate()			void CCmpPathfinder::MinimalTerrainUpdate()
	{			{
	TerrainUpdateHelper(false);			TerrainUpdateHelper(false);
	}			}

	void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability/* = true */)			void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability/* = true */)
	{			{
	PROFILE3("TerrainUpdateHelper");			//PROFILE3("TerrainUpdateHelper");

	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);			CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
	CmpPtr<ICmpWaterManager> cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);			CmpPtr<ICmpWaterManager> cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
	CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);			CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
	CTerrain& terrain = GetSimContext().GetTerrain();			CTerrain& terrain = GetSimContext().GetTerrain();

	if (!cmpTerrain \|\| !cmpObstructionManager)			if (!cmpTerrain \|\| !cmpObstructionManager)
	return;			return;

	u16 terrainSize = cmpTerrain->GetTilesPerSide();			u16 terrainSize = cmpTerrain->GetTilesPerSide();
	if (terrainSize == 0)			if (terrainSize == 0)
	return;			return;

	if (!m_TerrainOnlyGrid \|\| m_MapSize != terrainSize)			if (!m_TerrainOnlyGrid \|\| m_MapSize != terrainSize)
	{			{
	m_MapSize = terrainSize;			m_MapSize = terrainSize;

	SAFE_DELETE(m_TerrainOnlyGrid);			SAFE_DELETE(m_TerrainOnlyGrid);
	m_TerrainOnlyGrid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);			m_TerrainOnlyGrid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE);

	// If this update comes from a map resizing, we must reinitialize the other grids as well			// If this update comes from a map resizing, we must reinitialize the other grids as well
	if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))			if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
	{			{
	SAFE_DELETE(m_Grid);			SAFE_DELETE(m_Grid);
	m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);			m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE);

	m_DirtinessInformation = { true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };			m_DirtinessInformation = {true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE)};
	m_AIPathfinderDirtinessInformation = m_DirtinessInformation;			m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
	}			}
	}			}

	Grid<u16> shoreGrid = ComputeShoreGrid();			Grid<u16> shoreGrid = ComputeShoreGrid();

	// Compute initial terrain-dependent passability			// Compute initial terrain-dependent passability
	for (int j = 0; j < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++j)			for (int j = 0; j < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++j)
	{			{
	for (int i = 0; i < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++i)			for (int i = 0; i < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++i)
	{			{
	// World-space coordinates for this navcell			// World-space coordinates for this navcell
	fixed x, z;			fixed x, z;
	Pathfinding::NavcellCenter(i, j, x, z);			Pathfinding::NavcellCenter(i, j, x, z);

	// Terrain-tile coordinates for this navcell			// Terrain-tile coordinates for this navcell
	int itile = i / Pathfinding::NAVCELLS_PER_TILE;			int itile = i / Pathfinding::NAVCELLS_PER_TILE;
	int jtile = j / Pathfinding::NAVCELLS_PER_TILE;			int jtile = j / Pathfinding::NAVCELLS_PER_TILE;

	// Gather all the data potentially needed to determine passability:			// Gather all the data potentially needed to determine passability:

	fixed height = terrain.GetExactGroundLevelFixed(x, z);			fixed height = terrain.GetExactGroundLevelFixed(x, z);

	fixed water;			fixed water;
	if (cmpWaterManager)			if (cmpWaterManager)
	water = cmpWaterManager->GetWaterLevel(x, z);			water = cmpWaterManager->GetWaterLevel(x, z);

	fixed depth = water - height;			fixed depth = water - height;

	// Exact slopes give kind of weird output, so just use rough tile-based slopes			// Exact slopes give kind of weird output, so just use rough tile-based slopes
	fixed slope = terrain.GetSlopeFixed(itile, jtile);			fixed slope = terrain.GetSlopeFixed(itile, jtile);

	// Get world-space coordinates from shoreGrid (which uses terrain tiles)			// Get world-space coordinates from shoreGrid (which uses terrain tiles)
	fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);			fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);

	// Compute the passability for every class for this cell			// Compute the passability for every class for this cell
	NavcellData t = 0;			NavcellData t = 0;
	for (PathfinderPassability& passability : m_PassClasses)			for (PathfinderPassability& passability : m_PassClasses)
	if (!passability.IsPassable(depth, slope, shoredist))			if (!passability.IsPassable(depth, slope, shoredist))
	t \|= passability.m_Mask;			t \|= passability.m_Mask;

	m_TerrainOnlyGrid->set(i, j, t);			m_TerrainOnlyGrid->set(i, j, t);
	}			}
	}			}

	// Compute off-world passability			// Compute off-world passability
	// WARNING: CCmpRangeManager::LosIsOffWorld needs to be kept in sync with this			// WARNING: CCmpRangeManager::LosIsOffWorld needs to be kept in sync with this
	const int edgeSize = 3 * Pathfinding::NAVCELLS_PER_TILE; // number of tiles around the edge that will be off-world			const int edgeSize = 3 * Pathfinding::NAVCELLS_PER_TILE; // number of tiles around the edge that will be off-world

	NavcellData edgeMask = 0;			NavcellData edgeMask = 0;
	for (PathfinderPassability& passability : m_PassClasses)			for (PathfinderPassability& passability : m_PassClasses)
	edgeMask \|= passability.m_Mask;			edgeMask \|= passability.m_Mask;

	int w = m_TerrainOnlyGrid->m_W;			int w = m_TerrainOnlyGrid->m_W;
	int h = m_TerrainOnlyGrid->m_H;			int h = m_TerrainOnlyGrid->m_H;

	if (cmpObstructionManager->GetPassabilityCircular())			if (cmpObstructionManager->GetPassabilityCircular())
	{			{
	for (int j = 0; j < h; ++j)			for (int j = 0; j < h; ++j)
	{			{
	for (int i = 0; i < w; ++i)			for (int i = 0; i < w; ++i)
	{			{
	// Based on CCmpRangeManager::LosIsOffWorld			// Based on CCmpRangeManager::LosIsOffWorld
	// but tweaked since it's tile-based instead.			// but tweaked since it's tile-based instead.
	// (We double all the values so we can handle half-tile coordinates.)			// (We double all the values so we can handle half-tile coordinates.)
	// This needs to be slightly tighter than the LOS circle,			// This needs to be slightly tighter than the LOS circle,
	// else units might get themselves lost in the SoD around the edge.			// else units might get themselves lost in the SoD around the edge.

	int dist2 = (i2 + 1 - w)(i*2 + 1 - w)			int dist2 = (i * 2 + 1 - w) * (i * 2 + 1 - w)
	+ (j2 + 1 - h)(j*2 + 1 - h);			+ (j * 2 + 1 - h) * (j * 2 + 1 - h);

	if (dist2 >= (w - 2edgeSize) (h - 2*edgeSize))			if (dist2 >= (w - 2 * edgeSize) * (h - 2 * edgeSize))
	m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);			m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);
	}			}
	}			}
	}			}
	else			else
	{			{
	for (u16 j = 0; j < h; ++j)			for (u16 j = 0; j < h; ++j)
	for (u16 i = 0; i < edgeSize; ++i)			for (u16 i = 0; i < edgeSize; ++i)
	m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);			m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);
	for (u16 j = 0; j < h; ++j)			for (u16 j = 0; j < h; ++j)
	for (u16 i = w-edgeSize+1; i < w; ++i)			for (u16 i = w - edgeSize + 1; i < w; ++i)
	m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);			m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);
	for (u16 j = 0; j < edgeSize; ++j)			for (u16 j = 0; j < edgeSize; ++j)
	for (u16 i = edgeSize; i < w-edgeSize+1; ++i)			for (u16 i = edgeSize; i < w - edgeSize + 1; ++i)
	m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);			m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);
	for (u16 j = h-edgeSize+1; j < h; ++j)			for (u16 j = h - edgeSize + 1; j < h; ++j)
	for (u16 i = edgeSize; i < w-edgeSize+1; ++i)			for (u16 i = edgeSize; i < w - edgeSize + 1; ++i)
	m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);			m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) \| edgeMask);
	}			}

	if (!expandPassability)			if (!expandPassability)
	return;			return;

	// Expand the impassability grid, for any class with non-zero clearance,			// Expand the impassability grid, for any class with non-zero clearance,
	// so that we can stop units getting too close to impassable navcells.			// so that we can stop units getting too close to impassable navcells.
	// Note: It's not possible to perform this expansion once for all passabilities			// Note: It's not possible to perform this expansion once for all passabilities
	// with the same clearance, because the impassable cells are not necessarily the			// with the same clearance, because the impassable cells are not necessarily the
	// same for all these passabilities.			// same for all these passabilities.
	for (PathfinderPassability& passability : m_PassClasses)			for (PathfinderPassability& passability : m_PassClasses)
	{			{
	if (passability.m_Clearance == fixed::Zero())			if (passability.m_Clearance == fixed::Zero())
	continue;			continue;

	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 path requests:			// Async pathfinder workers

	u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)			CCmpPathfinder::AsyncPathfinderWorkerThread::AsyncPathfinderWorkerThread(const CCmpPathfinder& pathfinder)
				: m_Pathfinder(pathfinder)
	{			{
	AsyncLongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };			if (m_Pathfinder.m_UseThreading)
	m_AsyncLongPathRequests.push_back(req);			m_Thread = new std::thread(&CCmpPathfinder::AsyncPathfinderWorkerThread::InitThread, this,
	return req.ticket;			m_Pathfinder.m_WorkerThreads.size());
				vladislavbelovUnsubmitted Done Inline Actions Use `std::unique_ptr`. vladislavbelov: Use `std::unique_ptr`.
	}			}

	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)			CCmpPathfinder::AsyncPathfinderWorkerThread::~AsyncPathfinderWorkerThread()
	{			{
	AsyncShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };			if (m_Thread != nullptr)
	m_AsyncShortPathRequests.push_back(req);			{
				StanUnsubmitted Not Done Inline Actions Merge loops ? Stan: Merge loops ?
	return req.ticket;			if (m_Thread->joinable())
				m_Thread->join();
				delete m_Thread;
				}
				StanUnsubmitted Not Done Inline Actions + debug_SetThreadName("Pathfinder thread " + std::to_string(index)); Stan: + debug_SetThreadName("Pathfinder thread " + std::to_string(index));
				Kuba386Unsubmitted Done Inline Actions Fine, didn't know about that. Kuba386: Fine, didn't know about that.
				StanUnsubmitted Done Inline Actions It didn't work on linux until very recently thanks to @linkmauve Stan: It didn't work on linux until very recently thanks to @linkmauve
	}			}

	void CCmpPathfinder::FinishAsyncRequests()			void CCmpPathfinder::AsyncPathfinderWorkerThread::InitThread(size_t index)
	{			{
	PROFILE2("Finish Async Requests");			g_Profiler2.RegisterCurrentThread("Pathfinder thread " + std::to_string(index));
	// Save the request queue in case it gets modified while iterating			WaitForWork();
	std::vector<AsyncLongPathRequest> longRequests;			}
	m_AsyncLongPathRequests.swap(longRequests);

	std::vector<AsyncShortPathRequest> shortRequests;
	m_AsyncShortPathRequests.swap(shortRequests);

				vladislavbelovUnsubmitted Done Inline Actions I don't think that the busy waiting is good here, why not to use `std::condition_variable`? vladislavbelov: I don't think that the busy waiting is good here, why not to use `std::condition_variable`?
				wraitiiAuthorUnsubmitted Done Inline Actions You can't use a `condition_variable` alone to wait on multiple threads. Adding the proper synchronisation would require more code, which has a higher chance of mistakes now and down the line. I agree that this spins at 100% which is a bit of a waste. What I hope is that using `std::this_thread::yield()` fixes this issue with an acceptable latency. wraitii: You can't use a `condition_variable` alone to [[ https://stackoverflow.
				vladislavbelovUnsubmitted Done Inline Actions Yes, in a direct way, but you can wrap it. Like https://stackoverflow.com/questions/24465533/implementing-boostbarrier-in-c11/24465624#24465624. Or use something like boost::barrier. Adding the proper synchronisation would require more code, which has a higher chance of mistakes now and down the line. It's not much more code and it's relatively simple. I'd prefer user's comfort instead of not saving few lines of code. In fact you may freeze the user machine (if it's not so good to predict busy-waiting). Also it may slow down other threads, I mean like renderer one, if it'd exist. std::this_thread::yield It's useful but it doesn't guarantee a good stable work. It may wake up every tick or sleep for a long time. Could you measure how many percents it and threads do busy waiting? vladislavbelov: Yes, in a direct way, but you can wrap it. Like https://stackoverflow.
				wraitiiAuthorUnsubmitted Done Inline Actions I've ran some benchmarks: Yield() isn't useful on OS X, and when spin looping hard we are consuming 100% CPU which seems wasteful. condition variables and barriers seem almost faster than spinlocking. Overall I'll switch to using condition_variable. I think it's a complicated construct, but at the end of the day we can't occupy 100% of a process spin locking. wraitii: I've ran some benchmarks: - Yield() isn't useful on OS X, and when spin looping hard we are…
	// TODO: we should only compute one path per entity per turn			void CCmpPathfinder::AsyncPathfinderWorkerThread::PrepareToKill()
				{
				StanUnsubmitted Not Done Inline Actions I guess one cannot check for m_kill there? Stan: I guess one cannot check for m_kill there?
				m_Kill = true;
				StanUnsubmitted Not Done Inline Actions Is it hard to do ? Stan: Is it hard to do ?
				wraitiiAuthorUnsubmitted Done Inline Actions It's trickier, but it's also a micro-improvement that needs further testing. wraitii: It's trickier, but it's also a micro-improvement that needs further testing.
				}
				StanUnsubmitted Done Inline Actions What does this function do ? Name seems misleading. Stan: What does this function do ? Name seems misleading.
				wraitiiAuthorUnsubmitted Done Inline Actions It's just there to be specialised, and it pushes requests so I don't think so? wraitii: It's just there to be specialised, and it pushes requests so I don't think so?
				StanUnsubmitted Done Inline Actions That line doesn't pushes request does it ? Stan: That line doesn't pushes request does it ?
				wraitiiAuthorUnsubmitted Done Inline Actions It inserts them at the end (by moving), so that's similar to pushing. wraitii: It inserts them at the end (by moving), so that's similar to pushing.
				StanUnsubmitted Done Inline Actions static_assert(sizeof(T) == 0, "Only specializations can be used"); What part of that statement does that ? Oo There is only one line in that function Stan: static_assert(sizeof(T) == 0, "Only specializations can be used"); What part of that statement…
				wraitiiAuthorUnsubmitted Done Inline Actions As said above, this is just the template function which gets specialised by L709/714. This base template cannot be used (it's not implemented but there's no clean way to write that because of issues in XCode/VS, see https://stackoverflow.com/a/37593094). wraitii: As said above, this is just the template function which gets specialised by L709/714. This base…
				StanUnsubmitted Not Done Inline Actions Ah thanks for the explanation :) Stan: Ah thanks for the explanation :)

	// TODO: this computation should be done incrementally, spread			void CCmpPathfinder::AsyncPathfinderWorkerThread::WaitForWork()
	// across multiple frames (or even multiple turns)			{
				while (!m_Kill)
				SilierUnsubmitted Not Done Inline Actions and here as well Silier: and here as well
				{
				// wait until we're woken up
				StanUnsubmitted Not Done Inline Actions break? Stan: break?
				wraitiiAuthorUnsubmitted Done Inline Actions Might as well return. wraitii: Might as well return.
				std::unique_lock<std::mutex> lock(m_Pathfinder.m_MainThreadMutex);
				m_Pathfinder.m_MainThreadSignal.wait(lock);
				lock.unlock();
				SilierUnsubmitted Not Done Inline Actions I think you are missing unlock here, or consider std::lock_guard Silier: I think you are missing unlock here, or consider std::lock_guard
				SilierUnsubmitted Not Done Inline Actions well, ok it is unique lock and it unlocks itself when goes out of scope so it is fine I am just thinking that some unlocks could be removed as they are not needed for unique locks? Silier: well, ok it is unique lock and it unlocks itself when goes out of scope so it is fine I am…

	ProcessLongRequests(longRequests);			Work();
	ProcessShortRequests(shortRequests);			}
	}			}

	void CCmpPathfinder::ProcessLongRequests(const std::vector<AsyncLongPathRequest>& longRequests)			void CCmpPathfinder::AsyncPathfinderWorkerThread::Work()
	{			{
	PROFILE2("Process Long Requests");			m_Computing = true;
	for (size_t i = 0; i < longRequests.size(); ++i)
				// start by going through our long requests.
				SilierUnsubmitted Done Inline Actions we could lock/unlock only when using multithreads, branch is already here so ... Silier: we could lock/unlock only when using multithreads, branch is already here so ...
				while (!m_LongRequests.empty())
				wraitiiAuthorUnsubmitted Done Inline Actions Realised last night that I need to make sure the results are ordered consistently for threaded/non-threaded/different # of threads here. I think they are by accident right now, but and "ENSURE (is_sorted)" is probably worth adding. wraitii: Realised last night that I need to make sure the results are ordered consistently for…
	{			{
	const AsyncLongPathRequest& req = longRequests[i];			std::unique_lock<std::mutex> lock(m_Pause);
				StanUnsubmitted Not Done Inline Actions Why the scope ? Stan: Why the scope ?
				wraitiiAuthorUnsubmitted Done Inline Actions lock gets release automatically at the end of the scope. wraitii: lock gets release automatically at the end of the scope.
				StanUnsubmitted Not Done Inline Actions How hard is it to do? + Profile? Stan: How hard is it to do? + Profile?
				wraitiiAuthorUnsubmitted Done Inline Actions It's hard enough. There's a high chance of dumb bugs, and this whole diff is already stupidly faster than svn. wraitii: It's hard enough. There's a high chance of dumb bugs, and this whole diff is already stupidly…
				if (!m_Pathfinder.m_MayComputePaths)
				return;

				const AsyncLongPathRequest& req = m_LongRequests.back();
	WaypointPath path;			WaypointPath path;
	ComputePath(req.x0, req.z0, req.goal, req.passClass, path);			ComputePath(req.x0, req.z0, req.goal, req.passClass, path);
	CMessagePathResult msg(req.ticket, path);			m_Results.push_back({req.ticket, req.notify, path});
	GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
	}
	}

				StanUnsubmitted Not Done Inline Actions Invert, early return? Stan: Invert, early return?
	void CCmpPathfinder::ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests)			m_LongRequests.pop_back();
	{			lock.unlock();
	PROFILE2("Process Short Requests");			}
	for (size_t i = 0; i < shortRequests.size(); ++i)			// then the short requests
				while (!m_ShortRequests.empty())
				StanUnsubmitted Not Done Inline Actions Can't you just move that out of the loop and check for !stop ? Stan: Can't you just move that out of the loop and check for !stop ?
				wraitiiAuthorUnsubmitted Done Inline Actions This is another spin-lock: we continue looping until all threads are done computing, so it needs to be reset at the beginning of the loop anyways. Putting it outside the loop isn't much neater imo, but the whole thing might be rewritten in a slightly more functional way I think. wraitii: This is another spin-lock: we continue looping until all threads are done computing, so it…
	{			{
	const AsyncShortPathRequest& req = shortRequests[i];			std::unique_lock<std::mutex> lock(m_Pause);
				if (!m_Pathfinder.m_MayComputePaths)
				return;

				const AsyncShortPathRequest& req = m_ShortRequests.back();
	WaypointPath path;			WaypointPath path;
	ControlGroupMovementObstructionFilter filter(req.avoidMovingUnits, req.group);			ControlGroupMovementObstructionFilter filter(req.avoidMovingUnits, req.group);
	ComputeShortPath(filter, req.x0, req.z0, req.clearance, req.range, req.goal, req.passClass, path);			ComputeShortPath(filter, req.x0, req.z0, req.clearance, req.range, req.goal, req.passClass, path);
	CMessagePathResult msg(req.ticket, path);			m_Results.push_back({req.ticket, req.notify, path});
	GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
				m_ShortRequests.pop_back();
				lock.unlock();
	}			}
				std::unique_lock<std::mutex> lock(m_Pause);
				m_Computing = false;
				lock.unlock();
	}			}

	void CCmpPathfinder::ProcessSameTurnMoves()			// Async path requests:

				u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass,
				wraitiiAuthorUnsubmitted Done Inline Actions This is a bit of a weird syntax in C++, but it's basically `worker[into].insert()` in JS. The alternative in C++ would be a macro or an explicit IF, but I think that's fine to use. wraitii: This is a bit of a weird syntax in C++, but it's basically `worker[into].insert()` in JS. The…
				vladislavbelovUnsubmitted Done Inline Actions Too unsafe for me. I'd replace the function by: template <typename T, typename U> void CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from, std::deque<U>& into) With probably a type validation like `std::is_same<U, AsyncPathRequest>::value`. vladislavbelov:* Too unsafe for me. I'd replace the function by: ```lang=cpp template <typename T, typename U>…
				wraitiiAuthorUnsubmitted Done Inline Actions One can't actually, because I need to call either the longRequest or the shortRequest of the worker in the inner loop. This is basically rewritable as CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from, bool toLongRequests) [...] if (toLongRequests) worker->m_LongRequests.insert([...]) else worker->m_ShortRequests.insert([...]) If I pass the worker, I lose the whole point of the function as the for-loop has to be outside the function. wraitii: One can't actually, because I need to call either the longRequest or the shortRequest of the…
				vladislavbelovUnsubmitted Done Inline Actions If you wanna leave the function loop, I'd prefer to add more code but with an explicit access. Like: template<typename T> CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from) { // ... worker->AddRequests<T>( std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end()) ); // ... } template<typename T> void AsyncPathfinderWorkerThread::AddRequests(... it_begin, ... it_end) { auto& container = RequestsContainer<T>(); container.insert(container.begin(), std::make_move_iterator(it_begin), std::make_move_iterator(it_end)); } template<typename T> void AsyncPathfinderWorkerThread::RequestsContainer(); template<> std::deque<AsyncShortPathRequest>& RequestsContainer() { return m_ShortRequests; } // ... It'd be the same by performance, but safer I think. As you can't pass an arbitrary container member. vladislavbelov: If you wanna leave the function loop, I'd prefer to add more code but with an explicit access.
				wraitiiAuthorUnsubmitted Done Inline Actions I suppose ultimately this would be if-constexpr-ed. I'll go with your way as it does seem more readable and I didn't think of it. wraitii: I suppose ultimately this would be if-constexpr-ed. I'll go with your way as it does seem more…
				wraitiiAuthorUnsubmitted Done Inline Actions Done in a slightly simpler manner. wraitii: Done in a slightly simpler manner.
				entity_id_t notify)
				SilierUnsubmitted Not Done Inline Actions should not this comment be elsewhere ? Silier: should not this comment be elsewhere ?
				wraitiiAuthorUnsubmitted Not Done Inline Actions My intention was that if people did something stupid, they would trigger the assert, and then that comment would tell them why this was a bad idea. wraitii: My intention was that if people did something stupid, they would trigger the assert, and then…
	{			{
				StanUnsubmitted Not Done Inline Actions range loop ? Stan: range loop ?
				Kuba386Unsubmitted Done Inline Actions sure :) Kuba386: sure :)
				SilierUnsubmitted Not Done Inline Actions do we want to just prevent pushing or really fail if some worker is computing ? Is computing worker here broken state? Silier: do we want to just prevent pushing or really fail if some worker is computing ? Is computing…
				Kuba386Unsubmitted Not Done Inline Actions At this point, we are about to start computing pathes for new turn. Fact that we are starting new turn implies that previous turn finished, and fact that previous turn finished implies that computation for previous turn finished. Nothing should put pathfinder threads into working state between end of a turn and start of next turn. Kuba386: At this point, we are about to start computing pathes for new turn. Fact that we are starting…
				Kuba386Unsubmitted Done Inline Actions Well, not exaclty 'for new turn', because StartProcessingRequests is called three times during single turn. I must check whether it's just remaining of non-threaded version, or if it's still needed... Anyway, it's not gonna happen unless there's a bug. Kuba386: Well, not exaclty 'for new turn', because StartProcessingRequests is called three times during…
	if (!m_AsyncLongPathRequests.empty())			AsyncLongPathRequest req = {m_NextAsyncTicket++, x0, z0, goal, passClass, notify};
				m_AsyncLongPathRequests.push_back(req);
				return req.ticket;
				}

				SilierUnsubmitted Not Done Inline Actions Could not be here used atomic variable instead locking this? Silier: Could not be here used atomic variable instead locking this?
				void
				CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass,
				WaypointPath& ret) const
	{			{
	// Figure out how many moves we can do this time			m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
	i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;			}

	if (moveCount <= 0)			u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range,
	return;			const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits,
				entity_id_t group, entity_id_t notify)
				{
				AsyncShortPathRequest req = {m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits,
				group, notify};
				m_AsyncShortPathRequests.push_back(req);
				return req.ticket;
				}

	// Copy the long request elements we are going to process into a new array			void CCmpPathfinder::FetchAsyncResultsAndSendMessages()
	std::vector<AsyncLongPathRequest> longRequests;			{
	if ((i32)m_AsyncLongPathRequests.size() <= moveCount)			// wait until all threads have stopped computing
				// collect messages
				// send them
				PROFILE2("FetchAsyncResults");

				while (true)
				{
				bool stop = true;
				lyvUnsubmitted Not Done Inline Actions ? lyv: ?
				wraitiiAuthorUnsubmitted Done Inline Actions mutex spin-lock wraitii: mutex spin-lock
				for (auto worker : m_WorkerThreads)
				if (worker->m_Computing)
				stop = false;
				if (stop)
				break;
				}

				std::vector<PathResult> results;
				for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
				lyvUnsubmitted Not Done Inline Actions This would throw a compiler warning. `for (;;)` is the usual standard for infinite loops. It isn’t inheretly bad though. Do what the CC says. lyv: This would throw a compiler warning. `for (;;)` is the usual standard for infinite loops. It…
	{			{
	m_AsyncLongPathRequests.swap(longRequests);			results.insert(results.end(), std::make_move_iterator(worker->m_Results.begin()),
	moveCount = (i32)longRequests.size();			std::make_move_iterator(worker->m_Results.end()));
				elexisUnsubmitted Not Done Inline Actions (we use the actual type instead of auto, so that the reader doesn't have to guess) elexis: (we use the actual type instead of auto, so that the reader doesn't have to guess)
				worker->m_Results.clear();
	}			}
	else			// post messages
				{
				PROFILE2("PostMessages");
				for (PathResult& path : results)
	{			{
	longRequests.resize(moveCount);			CMessagePathResult msg(path.ticket, path.path);
	copy(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount, longRequests.begin());			GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
	m_AsyncLongPathRequests.erase(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount);			}
				}
	}			}

	ProcessLongRequests(longRequests);			void CCmpPathfinder::StartProcessingMoves(bool useMax)
				{
				// We will send new path requests to worker threads
				// trying to balance the workload
				// and then notify them they can start working.
				// since it's entirely possible that they are still currently computing paths
				// we will lock on the m_Pause mutex of each thread to pause them temporarily

	m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);			size_t done = 0;
	}

	if (!m_AsyncShortPathRequests.empty())			std::vector<AsyncLongPathRequest> longRequests;
				if (useMax)
	{			{
	// Figure out how many moves we can do now			size_t amount = std::min(m_AsyncLongPathRequests.size(), (size_t) m_MaxSameTurnMoves);
	i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;			if (amount > 0)
				{
				longRequests.insert(longRequests.begin(),
				std::make_move_iterator(m_AsyncLongPathRequests.end() - amount),
				std::make_move_iterator(m_AsyncLongPathRequests.end()));
				m_AsyncLongPathRequests.erase(m_AsyncLongPathRequests.end() - amount, m_AsyncLongPathRequests.end());
				}
				}
				else
				{
				longRequests.swap(m_AsyncLongPathRequests);
				m_AsyncLongPathRequests.clear();
				}

	if (moveCount <= 0)			done += longRequests.size();
	return;
				if (!longRequests.empty())
				{
				size_t amount = longRequests.size() / m_WorkerThreads.size();
				// try and divide equally among threads.
				for (size_t i = 0; i < m_WorkerThreads.size() - 1; ++i)
				{
				std::unique_lock<std::mutex> lock(m_WorkerThreads[i]->m_Pause);
				// move-insert
				m_WorkerThreads[i]->m_LongRequests.insert(m_WorkerThreads[i]->m_LongRequests.begin(),
				std::make_move_iterator(longRequests.end() - amount),
				std::make_move_iterator(longRequests.end()));
				lock.unlock();
				longRequests.erase(longRequests.end() - amount, longRequests.end());
				}
				// move the whole thing for the last, to make sure we don't forget one through rounding.
				std::unique_lock<std::mutex> lock(m_WorkerThreads.back()->m_Pause);
				m_WorkerThreads.back()->m_LongRequests.insert(m_WorkerThreads.back()->m_LongRequests.begin(),
				std::make_move_iterator(longRequests.begin()),
				std::make_move_iterator(longRequests.end()));
				lock.unlock();
				}

	// Copy the short request elements we are going to process into a new array
	std::vector<AsyncShortPathRequest> shortRequests;			std::vector<AsyncShortPathRequest> shortRequests;
	if ((i32)m_AsyncShortPathRequests.size() <= moveCount)			if (useMax)
				{
				size_t amount = std::min(m_AsyncShortPathRequests.size(), (size_t) m_MaxSameTurnMoves - done);
				if (amount > 0)
	{			{
	m_AsyncShortPathRequests.swap(shortRequests);			shortRequests.insert(shortRequests.begin(),
	moveCount = (i32)shortRequests.size();			std::make_move_iterator(m_AsyncShortPathRequests.end() - amount),
				std::make_move_iterator(m_AsyncShortPathRequests.end()));
				m_AsyncShortPathRequests.erase(m_AsyncShortPathRequests.end() - amount, m_AsyncShortPathRequests.end());
				}
	}			}
	else			else
	{			{
	shortRequests.resize(moveCount);			shortRequests.swap(m_AsyncShortPathRequests);
	copy(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount, shortRequests.begin());			m_AsyncShortPathRequests.clear();
	m_AsyncShortPathRequests.erase(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount);
	}			}

	ProcessShortRequests(shortRequests);			if (!shortRequests.empty())
				{
				size_t amount = shortRequests.size() / m_WorkerThreads.size();
				// try and divide equally among threads.
				for (size_t i = 0; i < m_WorkerThreads.size() - 1; ++i)
				{
				std::unique_lock<std::mutex> lock(m_WorkerThreads[i]->m_Pause);
				// move-insert
				m_WorkerThreads[i]->m_ShortRequests.insert(m_WorkerThreads[i]->m_ShortRequests.begin(),
				std::make_move_iterator(shortRequests.end() - amount),
				std::make_move_iterator(shortRequests.end()));
				lock.unlock();
				shortRequests.erase(shortRequests.end() - amount, shortRequests.end());
				}
				// move the whole thing for the last, to make sure we don't forget one through rounding.
				std::unique_lock<std::mutex> lock(m_WorkerThreads.back()->m_Pause);
				m_WorkerThreads.back()->m_ShortRequests.insert(m_WorkerThreads.back()->m_ShortRequests.begin(),
				std::make_move_iterator(shortRequests.begin()),
				std::make_move_iterator(shortRequests.end()));
				lock.unlock();
				}

	m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);			// we may now notify them.
				m_MayComputePaths = true;
				if (m_UseThreading)
				{
				// immediately mark them as computing
				for (auto worker : m_WorkerThreads)
				{
				std::unique_lock<std::mutex> lock(worker->m_Pause);
				worker->m_Computing = true;
				lock.unlock();
	}			}
				std::lock_guard<std::mutex> lock(m_MainThreadMutex);
				m_MainThreadSignal.notify_all();
				}
				else
				m_WorkerThreads.back()->Work();
	}			}

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

	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
	{			{
	PROFILE2_IFSPIKE("Check Movement", 0.001);			//PROFILE2_IFSPIKE("Check Movement", 0.001);

	// Test against obstructions first. filter may discard pathfinding-blocking obstructions.			// Test against obstructions first. filter may discard pathfinding-blocking obstructions.
	// Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.			// Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
	// This makes movement smoother and more natural for units, overall.			// This makes movement smoother and more natural for units, overall.
	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());			CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
	if (!cmpObstructionManager \|\| cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))			if (!cmpObstructionManager \|\| cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
	return false;			return false;

	// Then test against the terrain grid. This should not be necessary			// Then test against the terrain grid. This should not be necessary
	// But in case we allow terrain to change it will become so.			// But in case we allow terrain to change it will become so.
	return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);			return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
	}			}

	ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,			ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,
	entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const			entity_pos_t x, entity_pos_t z, entity_pos_t r,
				pass_class_t passClass,
				bool UNUSED(onlyCenterPoint)) const
	{			{
	// Check unit obstruction			// Check unit obstruction
	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());			CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
	if (!cmpObstructionManager)			if (!cmpObstructionManager)
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;

	if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))			if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;

	// Test against terrain and static obstructions:			// Test against terrain and static obstructions:

	u16 i, j;			u16 i, j;
	Pathfinding::NearestNavcell(x, z, i, j, m_MapSizePathfinding::NAVCELLS_PER_TILE, m_MapSizePathfinding::NAVCELLS_PER_TILE);			Pathfinding::NearestNavcell(x, z, i, j, m_MapSize * Pathfinding::NAVCELLS_PER_TILE,
				m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
	if (!IS_PASSABLE(m_Grid->get(i, j), passClass))			if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;

	// (Static obstructions will be redundantly tested against in both the			// (Static obstructions will be redundantly tested against in both the
	// obstruction-shape test and navcell-passability test, which is slightly			// obstruction-shape test and navcell-passability test, which is slightly
	// inefficient but shouldn't affect behaviour)			// inefficient but shouldn't affect behaviour)

	return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;			return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
	}			}

	ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,			ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
	entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,			entity_pos_t x, entity_pos_t z, entity_pos_t a,
	entity_pos_t h, entity_id_t id, pass_class_t passClass) const			entity_pos_t w,
				entity_pos_t h, entity_id_t id,
				pass_class_t passClass) const
	{			{
	return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);			return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
	}			}


	ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,			ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
	entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,			entity_pos_t x, entity_pos_t z, entity_pos_t a,
	entity_pos_t h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const			entity_pos_t w,
				entity_pos_t h, entity_id_t id,
				pass_class_t passClass,
				bool UNUSED(onlyCenterPoint)) const
	{			{
	// Check unit obstruction			// Check unit obstruction
	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());			CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
	if (!cmpObstructionManager)			if (!cmpObstructionManager)
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;

	if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))			if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;

	// Test against terrain:			// Test against terrain:

	ICmpObstructionManager::ObstructionSquare square;			ICmpObstructionManager::ObstructionSquare square;
	CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), id);			CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), id);
	if (!cmpObstruction \|\| !cmpObstruction->GetObstructionSquare(square))			if (!cmpObstruction \|\| !cmpObstruction->GetObstructionSquare(square))
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;

	entity_pos_t expand;			entity_pos_t expand;
	const PathfinderPassability* passability = GetPassabilityFromMask(passClass);			const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
	if (passability)			if (passability)
	expand = passability->m_Clearance;			expand = passability->m_Clearance;

	SimRasterize::Spans spans;			SimRasterize::Spans spans;
	SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);			SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
	for (const SimRasterize::Span& span : spans)			for (const SimRasterize::Span& span : spans)
	{			{
	i16 i0 = span.i0;			i16 i0 = span.i0;
	i16 i1 = span.i1;			i16 i1 = span.i1;
	i16 j = span.j;			i16 j = span.j;

	// Fail if any span extends outside the grid			// Fail if any span extends outside the grid
	if (i0 < 0 \|\| i1 > m_TerrainOnlyGrid->m_W \|\| j < 0 \|\| j > m_TerrainOnlyGrid->m_H)			if (i0 < 0 \|\| i1 > m_TerrainOnlyGrid->m_W \|\| j < 0 \|\| j > m_TerrainOnlyGrid->m_H)
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;

	// Fail if any span includes an impassable tile			// Fail if any span includes an impassable tile
	for (i16 i = i0; i < i1; ++i)			for (i16 i = i0; i < i1; ++i)
	if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))			if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
	return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;			return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
	}			}

	return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;			return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
	}			}