Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp	(revision 23361)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp	(revision 23362)
@@ -1,972 +1,972 @@
 /* Copyright (C) 2020 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation, either version 2 of the License, or
  * (at your option) any later version.
  *
  * 0 A.D. is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 /**
  * @file
  * Common code and setup code for CCmpPathfinder.
  */
 
 #include "precompiled.h"
 
 #include "CCmpPathfinder_Common.h"
 
 #include "ps/CLogger.h"
 #include "ps/CStr.h"
 #include "ps/Profile.h"
 #include "ps/XML/Xeromyces.h"
 #include "renderer/Scene.h"
 #include "simulation2/MessageTypes.h"
 #include "simulation2/components/ICmpObstruction.h"
 #include "simulation2/components/ICmpObstructionManager.h"
 #include "simulation2/components/ICmpTerrain.h"
 #include "simulation2/components/ICmpWaterManager.h"
 #include "simulation2/helpers/HierarchicalPathfinder.h"
 #include "simulation2/helpers/LongPathfinder.h"
 #include "simulation2/helpers/MapEdgeTiles.h"
 #include "simulation2/helpers/Rasterize.h"
 #include "simulation2/helpers/VertexPathfinder.h"
 #include "simulation2/serialization/SerializeTemplates.h"
 
 REGISTER_COMPONENT_TYPE(Pathfinder)
 
 void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
 {
 	m_MapSize = 0;
 	m_Grid = NULL;
 	m_TerrainOnlyGrid = NULL;
 
 	FlushAIPathfinderDirtinessInformation();
 
 	m_NextAsyncTicket = 1;
 
 	m_AtlasOverlay = NULL;
 
 	m_VertexPathfinder = std::unique_ptr<VertexPathfinder>(new VertexPathfinder(m_MapSize, m_TerrainOnlyGrid));
 	m_LongPathfinder = std::unique_ptr<LongPathfinder>(new LongPathfinder());
 	m_PathfinderHier = std::unique_ptr<HierarchicalPathfinder>(new HierarchicalPathfinder());
 
 	// Register Relax NG validator
 	CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
 
 	// 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),
 	// so load the data from a special XML file.
 	CParamNode externalParamNode;
 	CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
 
     // 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");
 	m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
 
 
 	const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
 	for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
 	{
 		std::string name = it->first;
 		ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS);
 		pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size());
 		m_PassClasses.push_back(PathfinderPassability(mask, it->second));
 		m_PassClassMasks[name] = mask;
 	}
 
 	m_Workers.emplace_back(PathfinderWorker{});
 }
 
 CCmpPathfinder::~CCmpPathfinder() {};
 
 void CCmpPathfinder::Deinit()
 {
 	m_Workers.clear();
 
 	SetDebugOverlay(false); // cleans up memory
 	SAFE_DELETE(m_AtlasOverlay);
 
 	SAFE_DELETE(m_Grid);
 	SAFE_DELETE(m_TerrainOnlyGrid);
 }
 
 struct SerializeLongRequest
 {
 	template<typename S>
 	void operator()(S& serialize, const char* UNUSED(name), LongPathRequest& value)
 	{
 		serialize.NumberU32_Unbounded("ticket", value.ticket);
 		serialize.NumberFixed_Unbounded("x0", value.x0);
 		serialize.NumberFixed_Unbounded("z0", value.z0);
 		SerializeGoal()(serialize, "goal", value.goal);
 		serialize.NumberU16_Unbounded("pass class", value.passClass);
 		serialize.NumberU32_Unbounded("notify", value.notify);
 	}
 };
 
 struct SerializeShortRequest
 {
 	template<typename S>
 	void operator()(S& serialize, const char* UNUSED(name), ShortPathRequest& value)
 	{
 		serialize.NumberU32_Unbounded("ticket", value.ticket);
 		serialize.NumberFixed_Unbounded("x0", value.x0);
 		serialize.NumberFixed_Unbounded("z0", value.z0);
 		serialize.NumberFixed_Unbounded("clearance", value.clearance);
 		serialize.NumberFixed_Unbounded("range", value.range);
 		SerializeGoal()(serialize, "goal", value.goal);
 		serialize.NumberU16_Unbounded("pass class", value.passClass);
 		serialize.Bool("avoid moving units", value.avoidMovingUnits);
 		serialize.NumberU32_Unbounded("group", value.group);
 		serialize.NumberU32_Unbounded("notify", value.notify);
 	}
 };
 
 template<typename S>
 void CCmpPathfinder::SerializeCommon(S& serialize)
 {
 	SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_LongPathRequests);
 	SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_ShortPathRequests);
 	serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
 	serialize.NumberU16_Unbounded("map size", m_MapSize);
 }
 
 void CCmpPathfinder::Serialize(ISerializer& serialize)
 {
 	SerializeCommon(serialize);
 }
 
 void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
 {
 	Init(paramNode);
 
 	SerializeCommon(deserialize);
 }
 
 void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
 {
 	switch (msg.GetType())
 	{
 	case MT_RenderSubmit:
 	{
 		const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
 		RenderSubmit(msgData.collector);
 		break;
 	}
 	case MT_TerrainChanged:
 	{
 		const CMessageTerrainChanged& msgData = static_cast<const CMessageTerrainChanged&>(msg);
 		m_TerrainDirty = true;
 		MinimalTerrainUpdate(msgData.i0, msgData.j0, msgData.i1, msgData.j1);
 		break;
 	}
 	case MT_WaterChanged:
 	case MT_ObstructionMapShapeChanged:
 		m_TerrainDirty = true;
 		UpdateGrid();
 		break;
 	case MT_Deserialized:
 		UpdateGrid();
 		// In case we were serialised with requests pending, we need to process them.
 		if (!m_ShortPathRequests.empty() || !m_LongPathRequests.empty())
 		{
 			ENSURE(CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
 			StartProcessingMoves(false);
 		}
 		break;
 	}
 }
 
 void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
 {
 	m_VertexPathfinder->RenderSubmit(collector);
 	m_PathfinderHier->RenderSubmit(collector);
 }
 
 void CCmpPathfinder::SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
 {
 	m_LongPathfinder->SetDebugPath(*m_PathfinderHier, x0, z0, goal, passClass);
 }
 
 void CCmpPathfinder::SetDebugOverlay(bool enabled)
 {
 	m_VertexPathfinder->SetDebugOverlay(enabled);
 	m_LongPathfinder->SetDebugOverlay(enabled);
 }
 
 void CCmpPathfinder::SetHierDebugOverlay(bool enabled)
 {
 	m_PathfinderHier->SetDebugOverlay(enabled, &GetSimContext());
 }
 
 void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid<u8>& grid) const
 {
 	m_LongPathfinder->GetDebugData(steps, time, grid);
 }
 
 void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
 {
 	if (enable)
 	{
 		if (!m_AtlasOverlay)
 			m_AtlasOverlay = new AtlasOverlay(this, passClass);
 		m_AtlasOverlay->m_PassClass = passClass;
 	}
 	else
 		SAFE_DELETE(m_AtlasOverlay);
 }
 
 pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
 {
 	std::map<std::string, pass_class_t>::const_iterator it = m_PassClassMasks.find(name);
 	if (it == m_PassClassMasks.end())
 	{
 		LOGERROR("Invalid passability class name '%s'", name.c_str());
 		return 0;
 	}
 
 	return it->second;
 }
 
 void CCmpPathfinder::GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const
 {
 	passClasses = m_PassClassMasks;
 }
 
 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)
 	{
 		if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
 			pathfindingPassClasses[pair.first] = pair.second;
 		else
 			nonPathfindingPassClasses[pair.first] = pair.second;
 	}
 }
 
 const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
 {
 	for (const PathfinderPassability& passability : m_PassClasses)
 	{
 		if (passability.m_Mask == passClass)
 			return &passability;
 	}
 
 	return NULL;
 }
 
 const Grid<NavcellData>& CCmpPathfinder::GetPassabilityGrid()
 {
 	if (!m_Grid)
 		UpdateGrid();
 
 	return *m_Grid;
 }
 
 /**
  * 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
  * it is <=clearance navcells away from an impassable navcell in the original grid.
  * The results are ORed onto the original grid.
  *
  * This is used for adding clearance onto terrain-based navcell passability.
  *
  * TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
  * Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
  * This would only really be a problem for big clearances.
  */
 static void ExpandImpassableCells(Grid<NavcellData>& grid, u16 clearance, pass_class_t mask)
 {
 	PROFILE3("ExpandImpassableCells");
 
 	u16 w = grid.m_W;
 	u16 h = grid.m_H;
 
 	// First expand impassable cells horizontally into a temporary 1-bit grid
 	Grid<u8> tempGrid(w, h);
 	for (u16 j = 0; j < h; ++j)
 	{
 		// 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
 		u16 numBlocked = 0;
 		for (u16 i = 0; i <= clearance && i < w; ++i)
 			if (!IS_PASSABLE(grid.get(i, j), mask))
 				++numBlocked;
 
 		for (u16 i = 0; i < w; ++i)
 		{
 			// Store a flag if blocked by at least one nearby cell
 			if (numBlocked)
 				tempGrid.set(i, j, 1);
 
 			// Slide the numBlocked window along:
 			// remove the old i-clearance value, add the new (i+1)+clearance
 			// (avoiding overflowing the grid)
 			if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))
 				--numBlocked;
 			if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))
 				++numBlocked;
 		}
 	}
 
 	for (u16 i = 0; i < w; ++i)
 	{
 		// 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
 		u16 numBlocked = 0;
 		for (u16 j = 0; j <= clearance && j < h; ++j)
 			if (tempGrid.get(i, j))
 				++numBlocked;
 
 		for (u16 j = 0; j < h; ++j)
 		{
 			// Add the mask if blocked by at least one nearby cell
 			if (numBlocked)
 				grid.set(i, j, grid.get(i, j) | mask);
 
 			// Slide the numBlocked window along:
 			// remove the old j-clearance value, add the new (j+1)+clearance
 			// (avoiding overflowing the grid)
 			if (j >= clearance && tempGrid.get(i, j-clearance))
 				--numBlocked;
 			if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))
 				++numBlocked;
 		}
 	}
 }
 
 Grid<u16> CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
 {
 	PROFILE3("ComputeShoreGrid");
 
 	CmpPtr<ICmpWaterManager> cmpWaterManager(GetSystemEntity());
 
 	// TODO: these bits should come from ICmpTerrain
 	CTerrain& terrain = GetSimContext().GetTerrain();
 
 	// avoid integer overflow in intermediate calculation
 	const u16 shoreMax = 32767;
 
 	// First pass - find underwater tiles
 	Grid<u8> waterGrid(m_MapSize, m_MapSize);
 	for (u16 j = 0; j < m_MapSize; ++j)
 	{
 		for (u16 i = 0; i < m_MapSize; ++i)
 		{
 			fixed x, z;
 			Pathfinding::TileCenter(i, j, x, z);
 
 			bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
 			waterGrid.set(i, j, underWater ? 1 : 0);
 		}
 	}
 
 	// Second pass - find shore tiles
 	Grid<u16> shoreGrid(m_MapSize, m_MapSize);
 	for (u16 j = 0; j < m_MapSize; ++j)
 	{
 		for (u16 i = 0; i < m_MapSize; ++i)
 		{
 			// Find a land tile
 			if (!waterGrid.get(i, j))
 			{
 				// 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))
 					|| (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))
 					)
 					shoreGrid.set(i, j, 0);
 				else
 					shoreGrid.set(i, j, shoreMax);
 			}
 			// If we want to expand on water, we want water tiles not to be shore tiles
 			else if (expandOnWater)
 				shoreGrid.set(i, j, shoreMax);
 		}
 	}
 
 	// Expand influences on land to find shore distance
 	for (u16 y = 0; y < m_MapSize; ++y)
 	{
 		u16 min = shoreMax;
 		for (u16 x = 0; x < m_MapSize; ++x)
 		{
 			if (!waterGrid.get(x, y) || expandOnWater)
 			{
 				u16 g = shoreGrid.get(x, y);
 				if (g > min)
 					shoreGrid.set(x, y, min);
 				else if (g < min)
 					min = g;
 
 				++min;
 			}
 		}
 		for (u16 x = m_MapSize; x > 0; --x)
 		{
 			if (!waterGrid.get(x-1, y) || expandOnWater)
 			{
 				u16 g = shoreGrid.get(x-1, y);
 				if (g > min)
 					shoreGrid.set(x-1, y, min);
 				else if (g < min)
 					min = g;
 
 				++min;
 			}
 		}
 	}
 	for (u16 x = 0; x < m_MapSize; ++x)
 	{
 		u16 min = shoreMax;
 		for (u16 y = 0; y < m_MapSize; ++y)
 		{
 			if (!waterGrid.get(x, y) || expandOnWater)
 			{
 				u16 g = shoreGrid.get(x, y);
 				if (g > min)
 					shoreGrid.set(x, y, min);
 				else if (g < min)
 					min = g;
 
 				++min;
 			}
 		}
 		for (u16 y = m_MapSize; y > 0; --y)
 		{
 			if (!waterGrid.get(x, y-1) || expandOnWater)
 			{
 				u16 g = shoreGrid.get(x, y-1);
 				if (g > min)
 					shoreGrid.set(x, y-1, min);
 				else if (g < min)
 					min = g;
 
 				++min;
 			}
 		}
 	}
 
 	return shoreGrid;
 }
 
 void CCmpPathfinder::UpdateGrid()
 {
 	PROFILE3("UpdateGrid");
 
 	CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
 	if (!cmpTerrain)
 		return; // error
 
 	u16 terrainSize = cmpTerrain->GetTilesPerSide();
 	if (terrainSize == 0)
 		return;
 
 	// If the terrain was resized then delete the old grid data
 	if (m_Grid && m_MapSize != terrainSize)
 	{
 		SAFE_DELETE(m_Grid);
 		SAFE_DELETE(m_TerrainOnlyGrid);
 	}
 
 	// Initialise the terrain data when first needed
 	if (!m_Grid)
 	{
 		m_MapSize = terrainSize;
 		m_Grid = new Grid<NavcellData>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
 		SAFE_DELETE(m_TerrainOnlyGrid);
 		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_AIPathfinderDirtinessInformation = m_DirtinessInformation;
 
 		m_TerrainDirty = true;
 	}
 
 	// The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
 #ifdef NDEBUG
 	ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
 #else
 	ENSURE(m_DirtinessInformation.dirtinessGrid == Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));
 #endif
 
 	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
 	cmpObstructionManager->UpdateInformations(m_DirtinessInformation);
 
 	if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
 		return;
 
 	// If the terrain has changed, recompute m_Grid
 	// Else, use data from m_TerrainOnlyGrid and add obstructions
 	if (m_TerrainDirty)
 	{
 		TerrainUpdateHelper();
 
 		*m_Grid = *m_TerrainOnlyGrid;
 
 		m_TerrainDirty = false;
 		m_DirtinessInformation.globallyDirty = true;
 	}
 	else if (m_DirtinessInformation.globallyDirty)
 	{
 		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));
 	}
 	else
 	{
 		ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
 
 		for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
 			for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
 				if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
 					m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
 	}
 
 	// Add obstructions onto the grid
 	cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);
 
 	// Update the long-range and hierarchical pathfinders.
 	if (m_DirtinessInformation.globallyDirty)
 	{
 		std::map<std::string, pass_class_t> nonPathfindingPassClasses, pathfindingPassClasses;
 		GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
 		m_LongPathfinder->Reload(m_Grid);
 		m_PathfinderHier->Recompute(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
 	}
 	else
 	{
 		m_LongPathfinder->Update(m_Grid);
 		m_PathfinderHier->Update(m_Grid, m_DirtinessInformation.dirtinessGrid);
 	}
 
 	// Remember the necessary updates that the AI pathfinder will have to perform as well
 	m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation);
 }
 
 void CCmpPathfinder::MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1)
 {
 	TerrainUpdateHelper(false, itile0, jtile0, itile1, jtile1);
 }
 
 void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability, int itile0, int jtile0, int itile1, int jtile1)
 {
 	PROFILE3("TerrainUpdateHelper");
 
 	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
 	CmpPtr<ICmpWaterManager> cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
 	CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
 	CTerrain& terrain = GetSimContext().GetTerrain();
 
 	if (!cmpTerrain || !cmpObstructionManager)
 		return;
 
 	u16 terrainSize = cmpTerrain->GetTilesPerSide();
 	if (terrainSize == 0)
 		return;
 
 	const bool needsNewTerrainGrid = !m_TerrainOnlyGrid || m_MapSize != terrainSize;
 	if (needsNewTerrainGrid)
 	{
 		m_MapSize = terrainSize;
 
 		SAFE_DELETE(m_TerrainOnlyGrid);
 		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 (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
 		{
 			SAFE_DELETE(m_Grid);
 			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_AIPathfinderDirtinessInformation = m_DirtinessInformation;
 		}
 	}
 
 	Grid<u16> shoreGrid = ComputeShoreGrid();
 
 	const bool partialTerrainGridUpdate =
 		!expandPassability && !needsNewTerrainGrid &&
 		itile0 != -1 && jtile0 != -1 && itile1 != -1 && jtile1 != -1;
 	int istart = 0, iend = m_MapSize * Pathfinding::NAVCELLS_PER_TILE;
 	int jstart = 0, jend = m_MapSize * Pathfinding::NAVCELLS_PER_TILE;
 	if (partialTerrainGridUpdate)
 	{
 		// We need to extend the boundaries by 1 tile, because slope and ground
 		// level are calculated by multiple neighboring tiles.
 		// TODO: add CTerrain constant instead of 1.
 		istart = Clamp(itile0 - 1, 0, static_cast<int>(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE;
 		iend = Clamp(itile1 + 1, 0, static_cast<int>(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE;
 		jstart = Clamp(jtile0 - 1, 0, static_cast<int>(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE;
 		jend = Clamp(jtile1 + 1, 0, static_cast<int>(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE;
 	}
 
 	// Compute initial terrain-dependent passability
 	for (int j = jstart; j < jend; ++j)
 	{
 		for (int i = istart; i < iend; ++i)
 		{
 			// World-space coordinates for this navcell
 			fixed x, z;
 			Pathfinding::NavcellCenter(i, j, x, z);
 
 			// Terrain-tile coordinates for this navcell
 			int itile = i / Pathfinding::NAVCELLS_PER_TILE;
 			int jtile = j / Pathfinding::NAVCELLS_PER_TILE;
 
 			// Gather all the data potentially needed to determine passability:
 
 			fixed height = terrain.GetExactGroundLevelFixed(x, z);
 
 			fixed water;
 			if (cmpWaterManager)
 				water = cmpWaterManager->GetWaterLevel(x, z);
 
 			fixed depth = water - height;
 
 			// Exact slopes give kind of weird output, so just use rough tile-based slopes
 			fixed slope = terrain.GetSlopeFixed(itile, jtile);
 
 			// Get world-space coordinates from shoreGrid (which uses terrain tiles)
 			fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);
 
 			// Compute the passability for every class for this cell
 			NavcellData t = 0;
-			for (PathfinderPassability& passability : m_PassClasses)
+			for (const PathfinderPassability& passability : m_PassClasses)
 				if (!passability.IsPassable(depth, slope, shoredist))
 					t |= passability.m_Mask;
 
 			m_TerrainOnlyGrid->set(i, j, t);
 		}
 	}
 
 	// Compute off-world passability
 	const int edgeSize = MAP_EDGE_TILES * Pathfinding::NAVCELLS_PER_TILE;
 
 	NavcellData edgeMask = 0;
-	for (PathfinderPassability& passability : m_PassClasses)
+	for (const PathfinderPassability& passability : m_PassClasses)
 		edgeMask |= passability.m_Mask;
 
 	int w = m_TerrainOnlyGrid->m_W;
 	int h = m_TerrainOnlyGrid->m_H;
 
 	if (cmpObstructionManager->GetPassabilityCircular())
 	{
 		for (int j = jstart; j < jend; ++j)
 		{
 			for (int i = istart; i < iend; ++i)
 			{
 				// Based on CCmpRangeManager::LosIsOffWorld
 				// but tweaked since it's tile-based instead.
 				// (We double all the values so we can handle half-tile coordinates.)
 				// This needs to be slightly tighter than the LOS circle,
 				// else units might get themselves lost in the SoD around the edge.
 
 				int dist2 = (i*2 + 1 - w)*(i*2 + 1 - w)
 					+ (j*2 + 1 - h)*(j*2 + 1 - h);
 
 				if (dist2 >= (w - 2*edgeSize) * (h - 2*edgeSize))
 					m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
 			}
 		}
 	}
 	else
 	{
 		for (u16 j = 0; j < h; ++j)
 			for (u16 i = 0; i < edgeSize; ++i)
 				m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
 		for (u16 j = 0; j < h; ++j)
 			for (u16 i = w-edgeSize+1; i < w; ++i)
 				m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
 		for (u16 j = 0; j < edgeSize; ++j)
 			for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
 				m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
 		for (u16 j = h-edgeSize+1; j < h; ++j)
 			for (u16 i = edgeSize; i < w-edgeSize+1; ++i)
 				m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask);
 	}
 
 	if (!expandPassability)
 		return;
 
 	// Expand the impassability grid, for any class with non-zero clearance,
 	// 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
 	// with the same clearance, because the impassable cells are not necessarily the
 	// same for all these passabilities.
 	for (PathfinderPassability& passability : m_PassClasses)
 	{
 		if (passability.m_Clearance == fixed::Zero())
 			continue;
 
 		int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity();
 		ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask);
 	}
 }
 
 //////////////////////////////////////////////////////////
 
 // Async pathfinder workers
 
 CCmpPathfinder::PathfinderWorker::PathfinderWorker() {}
 
 template<typename T>
 void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<T>&, ssize_t)
 {
 	static_assert(sizeof(T) == 0, "Only specializations can be used");
 }
 
 template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<LongPathRequest>& from, ssize_t amount)
 {
 	m_LongRequests.insert(m_LongRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end()));
 }
 
 template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<ShortPathRequest>& from, ssize_t amount)
 {
 	m_ShortRequests.insert(m_ShortRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end()));
 }
 
 void CCmpPathfinder::PathfinderWorker::Work(const CCmpPathfinder& pathfinder)
 {
 	while (!m_LongRequests.empty())
 	{
 		const LongPathRequest& req = m_LongRequests.back();
 		WaypointPath path;
 		pathfinder.m_LongPathfinder->ComputePath(*pathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, path);
 		m_Results.emplace_back(req.ticket, req.notify, path);
 
 		m_LongRequests.pop_back();
 	}
 
 	while (!m_ShortRequests.empty())
 	{
 		const ShortPathRequest& req = m_ShortRequests.back();
 		WaypointPath path = pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(pathfinder.GetSystemEntity()));
 		m_Results.emplace_back(req.ticket, req.notify, path);
 
 		m_ShortRequests.pop_back();
 	}
 }
 
 u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
 {
 	LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
 	m_LongPathRequests.push_back(req);
 	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)
 {
 	ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
 	m_ShortPathRequests.push_back(req);
 	return req.ticket;
 }
 
 void CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const
 {
 	m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret);
 }
 
 WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const
 {
 	return m_VertexPathfinder->ComputeShortPath(request, CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
 }
 
 void CCmpPathfinder::FetchAsyncResultsAndSendMessages()
 {
 	PROFILE2("FetchAsyncResults");
 
 	// We may now clear existing requests.
 	m_ShortPathRequests.clear();
 	m_LongPathRequests.clear();
 
 	// WARNING: the order in which moves are pulled must be consistent when using 1 or n workers.
 	// We fetch in the same order we inserted in, but we push moves backwards, so this works.
 	std::vector<PathResult> results;
 	for (PathfinderWorker& worker : m_Workers)
 	{
 		results.insert(results.end(), std::make_move_iterator(worker.m_Results.begin()), std::make_move_iterator(worker.m_Results.end()));
 		worker.m_Results.clear();
 	}
 
 	{
 		PROFILE2("PostMessages");
 		for (PathResult& path : results)
 		{
 			CMessagePathResult msg(path.ticket, path.path);
 			GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
 		}
 	}
 }
 
 void CCmpPathfinder::StartProcessingMoves(bool useMax)
 {
 	std::vector<LongPathRequest> longRequests = GetMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves);
 	std::vector<ShortPathRequest> shortRequests = GetMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size());
 
 	PushRequestsToWorkers(longRequests);
 	PushRequestsToWorkers(shortRequests);
 
 	for (PathfinderWorker& worker : m_Workers)
 		worker.Work(*this);
 }
 
 template <typename T>
 std::vector<T> CCmpPathfinder::GetMovesToProcess(std::vector<T>& requests, bool useMax, size_t maxMoves)
 {
 	// Keep the original requests in which we need to serialize.
 	std::vector<T> copiedRequests;
 	if (useMax)
 	{
 		size_t amount = std::min(requests.size(), maxMoves);
 		if (amount > 0)
 			copiedRequests.insert(copiedRequests.begin(), requests.end() - amount, requests.end());
 	}
 	else
 		copiedRequests = requests;
 
 	return copiedRequests;
 }
 
 template <typename T>
 void CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from)
 {
 	if (from.empty())
 		return;
 
 	// Trivial load-balancing, / rounds towards zero so add 1 to ensure we do push all requests.
 	size_t amount = from.size() / m_Workers.size() + 1;
 
 	// WARNING: the order in which moves are pushed must be consistent when using 1 or n workers.
 	// In this instance, work is distributed in a strict LIFO order, effectively reversing tickets.
 	for (PathfinderWorker& worker : m_Workers)
 	{
 		amount = std::min(amount, from.size()); // Since we are rounding up before, ensure we aren't pushing beyond the end.
 		worker.PushRequests(from, amount);
 		from.erase(from.end() - amount, from.end());
 	}
 }
 
 //////////////////////////////////////////////////////////
 
 bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,
 	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
 {
 	PROFILE2_IFSPIKE("Check Movement", 0.001);
 
 	// Test against obstructions first. filter may discard pathfinding-blocking obstructions.
 	// Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
 	// This makes movement smoother and more natural for units, overall.
 	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
 	if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
 		return false;
 
 	// Then test against the terrain grid. This should not be necessary
 	// But in case we allow terrain to change it will become so.
 	return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
 }
 
 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
 {
 	// Check unit obstruction
 	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
 	if (!cmpObstructionManager)
 		return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
 
 	if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
 		return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
 
 	// Test against terrain and static obstructions:
 
 	u16 i, j;
 	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))
 		return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
 
 	// (Static obstructions will be redundantly tested against in both the
 	// obstruction-shape test and navcell-passability test, which is slightly
 	// inefficient but shouldn't affect behaviour)
 
 	return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
 }
 
 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 h, entity_id_t id, pass_class_t passClass) const
 {
 	return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
 }
 
 
 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 h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
 {
 	// Check unit obstruction
 	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
 	if (!cmpObstructionManager)
 		return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
 
 	if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
 		return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
 
 	// Test against terrain:
 
 	ICmpObstructionManager::ObstructionSquare square;
 	CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), id);
 	if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square))
 		return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;
 
 	entity_pos_t expand;
 	const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
 	if (passability)
 		expand = passability->m_Clearance;
 
 	SimRasterize::Spans spans;
 	SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
 	for (const SimRasterize::Span& span : spans)
 	{
 		i16 i0 = span.i0;
 		i16 i1 = span.i1;
 		i16 j = span.j;
 
 		// Fail if any span extends outside the grid
 		if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H)
 			return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
 
 		// Fail if any span includes an impassable tile
 		for (i16 i = i0; i < i1; ++i)
 			if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
 				return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
 	}
 
 	return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
 }
Index: ps/trunk/source/simulation2/helpers/Pathfinding.h
===================================================================
--- ps/trunk/source/simulation2/helpers/Pathfinding.h	(revision 23361)
+++ ps/trunk/source/simulation2/helpers/Pathfinding.h	(revision 23362)
@@ -1,400 +1,400 @@
 /* Copyright (C) 2019 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation, either version 2 of the License, or
  * (at your option) any later version.
  *
  * 0 A.D. is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #ifndef INCLUDED_PATHFINDING
 #define INCLUDED_PATHFINDING
 
 #include "maths/MathUtil.h"
 #include "ps/CLogger.h"
 
 #include "simulation2/system/Entity.h"
 #include "simulation2/system/ParamNode.h"
 #include "graphics/Terrain.h"
 #include "Grid.h"
 #include "PathGoal.h"
 
 typedef u16 pass_class_t;
 
 struct LongPathRequest
 {
 	u32 ticket;
 	entity_pos_t x0;
 	entity_pos_t z0;
 	PathGoal goal;
 	pass_class_t passClass;
 	entity_id_t notify;
 };
 
 struct ShortPathRequest
 {
 	u32 ticket;
 	entity_pos_t x0;
 	entity_pos_t z0;
 	entity_pos_t clearance;
 	entity_pos_t range;
 	PathGoal goal;
 	pass_class_t passClass;
 	bool avoidMovingUnits;
 	entity_id_t group;
 	entity_id_t notify;
 };
 
 struct Waypoint
 {
 	entity_pos_t x, z;
 };
 
 /**
  * Returned path.
  * Waypoints are in *reverse* order (the earliest is at the back of the list)
  */
 struct WaypointPath
 {
 	std::vector<Waypoint> m_Waypoints;
 };
 
 /**
  * Represents the cost of a path consisting of horizontal/vertical and
  * diagonal movements over a uniform-cost grid.
  * Maximum path length before overflow is about 45K steps.
  */
 struct PathCost
 {
 	PathCost() : data(0) { }
 
 	/// Construct from a number of horizontal/vertical and diagonal steps
 	PathCost(u16 hv, u16 d)
 		: data(hv * 65536 + d * 92682) // 2^16 * sqrt(2) == 92681.9
 	{
 	}
 
 	/// Construct for horizontal/vertical movement of given number of steps
 	static PathCost horizvert(u16 n)
 	{
 		return PathCost(n, 0);
 	}
 
 	/// Construct for diagonal movement of given number of steps
 	static PathCost diag(u16 n)
 	{
 		return PathCost(0, n);
 	}
 
 	PathCost operator+(const PathCost& a) const
 	{
 		PathCost c;
 		c.data = data + a.data;
 		return c;
 	}
 
 	PathCost& operator+=(const PathCost& a)
 	{
 		data += a.data;
 		return *this;
 	}
 
 	bool operator<=(const PathCost& b) const { return data <= b.data; }
 	bool operator< (const PathCost& b) const { return data <  b.data; }
 	bool operator>=(const PathCost& b) const { return data >= b.data; }
 	bool operator>(const PathCost& b) const { return data >  b.data; }
 
 	u32 ToInt()
 	{
 		return data;
 	}
 
 private:
 	u32 data;
 };
 
 static const int PASS_CLASS_BITS = 16;
 typedef u16 NavcellData; // 1 bit per passability class (up to PASS_CLASS_BITS)
 #define IS_PASSABLE(item, classmask) (((item) & (classmask)) == 0)
 #define PASS_CLASS_MASK_FROM_INDEX(id) ((pass_class_t)(1u << id))
 #define SPECIAL_PASS_CLASS PASS_CLASS_MASK_FROM_INDEX((PASS_CLASS_BITS-1)) // 16th bit, used for special in-place computations
 
 namespace Pathfinding
 {
 	/**
 	 * The long-range pathfinder operates primarily over a navigation grid (a uniform-cost
 	 * 2D passability grid, with horizontal/vertical (not diagonal) connectivity).
 	 * This is based on the terrain tile passability, plus the rasterized shapes of
 	 * obstructions, all expanded outwards by the radius of the units.
 	 * Since units are much smaller than terrain tiles, the nav grid should be
 	 * higher resolution than the tiles.
 	 * We therefore split each terrain tile into NxN "nav cells" (for some integer N,
 	 * preferably a power of two).
 	 */
 	const int NAVCELLS_PER_TILE = 4;
 
 	/**
 	 * Size of a navcell in metres ( = TERRAIN_TILE_SIZE / NAVCELLS_PER_TILE)
 	 */
 	const fixed NAVCELL_SIZE = fixed::FromInt((int)TERRAIN_TILE_SIZE) / Pathfinding::NAVCELLS_PER_TILE;
 	const int NAVCELL_SIZE_INT = 1;
 	const int NAVCELL_SIZE_LOG2 = 0;
 
 	/**
 	 * To make sure the long-range pathfinder is more strict than the short-range one,
 	 * we need to slightly over-rasterize. So we extend the clearance radius by 1.
 	 */
 	const entity_pos_t CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1);
 
 	/**
 	 * Compute the navcell indexes on the grid nearest to a given point
 	 * w, h are the grid dimensions, i.e. the number of navcells per side
 	 */
 	inline void NearestNavcell(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h)
 	{
 		// Use NAVCELL_SIZE_INT to save the cost of dividing by a fixed
 		i = static_cast<u16>(Clamp((x / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, w - 1));
 		j = static_cast<u16>(Clamp((z / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, h - 1));
 	}
 
 	/**
 	 * Returns the position of the center of the given tile
 	 */
 	inline void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
 	{
 		cassert(TERRAIN_TILE_SIZE % 2 == 0);
 		x = entity_pos_t::FromInt(i*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2);
 		z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2);
 	}
 
 	inline void NavcellCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
 	{
 		x = entity_pos_t::FromInt(i * 2 + 1).Multiply(NAVCELL_SIZE / 2);
 		z = entity_pos_t::FromInt(j * 2 + 1).Multiply(NAVCELL_SIZE / 2);
 	}
 
 	/*
 	 * Checks that the line (x0,z0)-(x1,z1) does not intersect any impassable navcells.
 	 */
 	inline bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1,
 		pass_class_t passClass, const Grid<NavcellData>& grid)
 	{
 		// We shouldn't allow lines between diagonally-adjacent navcells.
 		// It doesn't matter whether we allow lines precisely along the edge
 		// of an impassable navcell.
 
 		// To rasterise the line:
 		// If the line is (e.g.) aiming up-right, then we start at the navcell
 		// containing the start point and the line must either end in that navcell
 		// or else exit along the top edge or the right edge (or through the top-right corner,
 		// which we'll arbitrary treat as the horizontal edge).
 		// So we jump into the adjacent navcell across that edge, and continue.
 
 		// To handle the special case of units that are stuck on impassable cells,
 		// we allow them to move from an impassable to a passable cell (but not
 		// vice versa).
 
 		u16 i0, j0, i1, j1;
 		NearestNavcell(x0, z0, i0, j0, grid.m_W, grid.m_H);
 		NearestNavcell(x1, z1, i1, j1, grid.m_W, grid.m_H);
 
 		// Find which direction the line heads in
 		int di = (i0 < i1 ? +1 : i1 < i0 ? -1 : 0);
 		int dj = (j0 < j1 ? +1 : j1 < j0 ? -1 : 0);
 
 		u16 i = i0;
 		u16 j = j0;
 
 		bool currentlyOnImpassable = !IS_PASSABLE(grid.get(i0, j0), passClass);
 
 		while (true)
 		{
 			// Make sure we are still in the limits
 			ENSURE(
 				((di > 0 && i0 <= i && i <= i1) || (di < 0 && i1 <= i && i <= i0) || (di == 0 && i == i0)) &&
 				((dj > 0 && j0 <= j && j <= j1) || (dj < 0 && j1 <= j && j <= j0) || (dj == 0 && j == j0)));
 
 			// Fail if we're moving onto an impassable navcell
 			bool passable = IS_PASSABLE(grid.get(i, j), passClass);
 			if (passable)
 				currentlyOnImpassable = false;
 			else if (!currentlyOnImpassable)
 				return false;
 
 			// Succeed if we're at the target
 			if (i == i1 && j == j1)
 				return true;
 
 			// If we can only move horizontally/vertically, then just move in that direction
 			// If we are reaching the limits, we can go straight to the end
 			if (di == 0 || i == i1)
 			{
 				j += dj;
 				continue;
 			}
 			else if (dj == 0 || j == j1)
 			{
 				i += di;
 				continue;
 			}
 
 			// Otherwise we need to check which cell to move into:
 
 			// Check whether the line intersects the horizontal (top/bottom) edge of
 			// the current navcell.
 			// Horizontal edge is (i, j + (dj>0?1:0)) .. (i + 1, j + (dj>0?1:0))
 			// Since we already know the line is moving from this navcell into a different
 			// navcell, we simply need to test that the edge's endpoints are not both on the
 			// same side of the line.
 
 			// If we are crossing exactly a vertex of the grid, we will get dota or dotb equal
 			// to 0. In that case we arbitrarily choose to move of dj.
 			// This only works because we handle the case (i == i1 || j == j1) beforehand.
 			// Otherwise we could go outside the j limits and never reach the final navcell.
 
 			entity_pos_t xia = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE);
 			entity_pos_t xib = entity_pos_t::FromInt(i+1).Multiply(Pathfinding::NAVCELL_SIZE);
 			entity_pos_t zj = entity_pos_t::FromInt(j + (dj+1)/2).Multiply(Pathfinding::NAVCELL_SIZE);
 
 			CFixedVector2D perp = CFixedVector2D(x1 - x0, z1 - z0).Perpendicular();
 			entity_pos_t dota = (CFixedVector2D(xia, zj) - CFixedVector2D(x0, z0)).Dot(perp);
 			entity_pos_t dotb = (CFixedVector2D(xib, zj) - CFixedVector2D(x0, z0)).Dot(perp);
 
 			// If the horizontal edge is fully on one side of the line, so the line doesn't
 			// intersect it, we should move across the vertical edge instead
 			if ((dota < entity_pos_t::Zero() && dotb < entity_pos_t::Zero()) ||
 				(dota > entity_pos_t::Zero() && dotb > entity_pos_t::Zero()))
 				i += di;
 			else
 				j += dj;
 		}
 	}
 }
 
 /*
  * For efficient pathfinding we want to try hard to minimise the per-tile search cost,
  * so we precompute the tile passability flags and movement costs for the various different
  * types of unit.
  * We also want to minimise memory usage (there can easily be 100K tiles so we don't want
  * to store many bytes for each).
  *
  * To handle passability efficiently, we have a small number of passability classes
  * (e.g. "infantry", "ship"). Each unit belongs to a single passability class, and
  * uses that for all its pathfinding.
  * Passability is determined by water depth, terrain slope, forestness, buildingness.
  * We need at least one bit per class per tile to represent passability.
  *
  * Not all pass classes are used for actual pathfinding. The pathfinder calls
  * CCmpObstructionManager's Rasterize() to add shapes onto the passability grid.
  * Which shapes are rasterized depend on the value of the m_Obstructions of each passability
  * class.
  *
  * Passabilities not used for unit pathfinding should not use the Clearance attribute, and
  * will get a zero clearance value.
  */
 class PathfinderPassability
 {
 public:
 	PathfinderPassability(pass_class_t mask, const CParamNode& node) :
 		m_Mask(mask)
 	{
 		if (node.GetChild("MinWaterDepth").IsOk())
 			m_MinDepth = node.GetChild("MinWaterDepth").ToFixed();
 		else
 			m_MinDepth = std::numeric_limits<fixed>::min();
 
 		if (node.GetChild("MaxWaterDepth").IsOk())
 			m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed();
 		else
 			m_MaxDepth = std::numeric_limits<fixed>::max();
 
 		if (node.GetChild("MaxTerrainSlope").IsOk())
 			m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed();
 		else
 			m_MaxSlope = std::numeric_limits<fixed>::max();
 
 		if (node.GetChild("MinShoreDistance").IsOk())
 			m_MinShore = node.GetChild("MinShoreDistance").ToFixed();
 		else
 			m_MinShore = std::numeric_limits<fixed>::min();
 
 		if (node.GetChild("MaxShoreDistance").IsOk())
 			m_MaxShore = node.GetChild("MaxShoreDistance").ToFixed();
 		else
 			m_MaxShore = std::numeric_limits<fixed>::max();
 
 		if (node.GetChild("Clearance").IsOk())
 		{
 			m_Clearance = node.GetChild("Clearance").ToFixed();
 
 			/* According to Philip who designed the original doc (in docs/pathfinder.pdf),
 			 * clearance should usually be integer to ensure consistent behavior when rasterizing
 			 * the passability map.
 			 * This seems doubtful to me and my pathfinder fix makes having a clearance of 0.8 quite convenient
 			 * so I comment out this check, but leave it here for the purpose of documentation should a bug arise.
 
 			if (!(m_Clearance % Pathfinding::NAVCELL_SIZE).IsZero())
 			{
 				// If clearance isn't an integer number of navcells then we'll
 				// probably get weird behaviour when expanding the navcell grid
 				// by clearance, vs expanding static obstructions by clearance
 				LOGWARNING("Pathfinder passability class has clearance %f, should be multiple of %f",
 					m_Clearance.ToFloat(), Pathfinding::NAVCELL_SIZE.ToFloat());
 			}*/
 		}
 		else
 			m_Clearance = fixed::Zero();
 
 		if (node.GetChild("Obstructions").IsOk())
 		{
 			std::wstring obstructions = node.GetChild("Obstructions").ToString();
 			if (obstructions == L"none")
 				m_Obstructions = NONE;
 			else if (obstructions == L"pathfinding")
 				m_Obstructions = PATHFINDING;
 			else if (obstructions == L"foundation")
 				m_Obstructions = FOUNDATION;
 			else
 			{
 				LOGERROR("Invalid value for Obstructions in pathfinder.xml for pass class %d", mask);
 				m_Obstructions = NONE;
 			}
 		}
 		else
 			m_Obstructions = NONE;
 	}
 
-	bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist)
+	bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) const
 	{
 		return ((m_MinDepth <= waterdepth && waterdepth <= m_MaxDepth) && (steepness < m_MaxSlope) && (m_MinShore <= shoredist && shoredist <= m_MaxShore));
 	}
 
 	pass_class_t m_Mask;
 
 	fixed m_Clearance; // min distance from static obstructions
 
 	enum ObstructionHandling
 	{
 		NONE,
 		PATHFINDING,
 		FOUNDATION
 	};
 	ObstructionHandling m_Obstructions;
 
 private:
 	fixed m_MinDepth;
 	fixed m_MaxDepth;
 	fixed m_MaxSlope;
 	fixed m_MinShore;
 	fixed m_MaxShore;
 };
 
 #endif // INCLUDED_PATHFINDING