Index: binaries/data/config/default.cfg
===================================================================
--- binaries/data/config/default.cfg
+++ binaries/data/config/default.cfg
@@ -403,6 +403,10 @@
 zoom.in = 5
 zoom.out = 4
 
+[pathfinder]
+usenumthreads = false;
+numthreads = 0;
+
 [chat]
 timestamp = true                    ; Show at which time chat messages have been sent
 
Index: binaries/data/mods/public/gui/credits/texts/programming.json
===================================================================
--- binaries/data/mods/public/gui/credits/texts/programming.json
+++ binaries/data/mods/public/gui/credits/texts/programming.json
@@ -121,6 +121,7 @@
 			{"nick": "kabzerek", "name": "Grzegorz Kabza"},
 			{"nick": "Kai", "name": "Kai Chen"},
 			{"name": "Kareem Ergawy"},
+			{"nick": "Kuba386", "name":"Jakub Kośmicki"},
 			{"nick": "kevmo", "name": "Kevin Caffrey"},
 			{"nick": "kezz", "name": "Graeme Kerry"},
 			{"nick": "kingadami", "name": "Adam Winsor"},
Index: binaries/data/mods/public/gui/options/options.json
===================================================================
--- binaries/data/mods/public/gui/options/options.json
+++ binaries/data/mods/public/gui/options/options.json
@@ -81,7 +81,23 @@
 				"label": "Chat Timestamp",
 				"tooltip": "Show time that messages are posted in the lobby, gamesetup and ingame chat.",
 				"config": "chat.timestamp"
+			},
+			{
+				"type": "boolean",
+				"label": "Use non-standerd pathfinder thread count",
+				"tooltip":"Use default thread count or choose your own.",
+				"config": "pathfinder.usenumthreads"
+			},
+			{
+				"type": "number",
+				"label": "Number of pathfinder threads",
+				"tooltip": "Number of pathfinder worker threads. Mostly for debugging purposes. 0 to disable threading.",
+				"config": "pathfinder.numthreads",
+				"dependencies":["pathfinder.usenumthreads"],
+				"min": 0,
+				"max": 64
 			}
+
 		]
 	},
 	{
Index: binaries/data/mods/public/simulation/data/pathfinder.xml
===================================================================
--- binaries/data/mods/public/simulation/data/pathfinder.xml
+++ binaries/data/mods/public/simulation/data/pathfinder.xml
@@ -1,8 +1,7 @@
 <?xml version="1.0" encoding="utf-8"?>
 <Pathfinder>
   <!-- Sets limit on the number of same turns moves we will process -->
-  <!-- Setting the value to 0 disable this functionality -->
-  <MaxSameTurnMoves>64</MaxSameTurnMoves>
+  <MaxSameTurnMoves>6</MaxSameTurnMoves>
 
   <PassabilityClasses>
 
Index: source/ps/Profile.h
===================================================================
--- source/ps/Profile.h
+++ source/ps/Profile.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2013 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -178,15 +178,16 @@
 		if (CProfileManager::IsInitialised())
 		{
 			// The profiler is only safe to use on the main thread
-			ENSURE(ThreadUtil::IsMainThread());
 
-			g_Profiler.Start(name);
+			if(ThreadUtil::IsMainThread())
+				g_Profiler.Start(name);
 		}
 	}
 	~CProfileSample()
 	{
 		if (CProfileManager::IsInitialised())
-			g_Profiler.Stop();
+			if(ThreadUtil::IsMainThread())
+				g_Profiler.Stop();
 	}
 };
 
Index: source/simulation2/Simulation2.cpp
===================================================================
--- source/simulation2/Simulation2.cpp
+++ source/simulation2/Simulation2.cpp
@@ -540,8 +540,8 @@
 	CmpPtr<ICmpPathfinder> cmpPathfinder(simContext, SYSTEM_ENTITY);
 	if (cmpPathfinder)
 	{
+		cmpPathfinder->FetchAsyncResultsAndSendMessages();
 		cmpPathfinder->UpdateGrid();
-		cmpPathfinder->FinishAsyncRequests();
 	}
 
 	// Push AI commands onto the queue before we use them
@@ -555,23 +555,22 @@
 
 	// Process newly generated move commands so the UI feels snappy
 	if (cmpPathfinder)
-		cmpPathfinder->ProcessSameTurnMoves();
-
+	{
+		cmpPathfinder->StartProcessingMoves(true);
+		cmpPathfinder->FetchAsyncResultsAndSendMessages();
+	}
 	// Send all the update phases
 	{
 		PROFILE2("Sim - Update");
 		CMessageUpdate msgUpdate(turnLengthFixed);
 		componentManager.BroadcastMessage(msgUpdate);
 	}
+
 	{
 		CMessageUpdate_MotionFormation msgUpdate(turnLengthFixed);
 		componentManager.BroadcastMessage(msgUpdate);
 	}
 
-	// Process move commands for formations (group proxy)
-	if (cmpPathfinder)
-		cmpPathfinder->ProcessSameTurnMoves();
-
 	{
 		PROFILE2("Sim - Motion Unit");
 		CMessageUpdate_MotionUnit msgUpdate(turnLengthFixed);
@@ -583,12 +582,12 @@
 		componentManager.BroadcastMessage(msgUpdate);
 	}
 
-	// Process moves resulting from group proxy movement (unit needs to catch up or realign) and any others
-	if (cmpPathfinder)
-		cmpPathfinder->ProcessSameTurnMoves();
-
 	// Clean up any entities destroyed during the simulation update
 	componentManager.FlushDestroyedComponents();
+
+	// Process all remaining moves
+	if (cmpPathfinder)
+		cmpPathfinder->StartProcessingMoves();
 }
 
 void CSimulation2Impl::Interpolate(float simFrameLength, float frameOffset, float realFrameLength)
Index: source/simulation2/components/CCmpAIManager.cpp
===================================================================
--- source/simulation2/components/CCmpAIManager.cpp
+++ source/simulation2/components/CCmpAIManager.cpp
@@ -15,6 +15,7 @@
  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include <lib/allocators/shared_ptr.h>
 #include "precompiled.h"
 
 #include "simulation2/system/Component.h"
@@ -245,6 +246,8 @@
 	~CAIWorker()
 	{
 		JS_RemoveExtraGCRootsTracer(m_ScriptInterface->GetJSRuntime(), Trace, this);
+		m_ScriptInterface.reset();
+		m_SerializablePrototypes.reset();
 	}
 
 	bool HasLoadedEntityTemplates() const { return m_HasLoadedEntityTemplates; }
@@ -714,6 +717,10 @@
 	void Deserialize(std::istream& stream, u32 numAis)
 	{
 		m_PlayerMetadata.clear();
+		for(auto i : m_Players)
+        {
+		    i.reset();
+        }
 		m_Players.clear();
 
 		if (numAis == 0)
Index: source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- source/simulation2/components/CCmpPathfinder.cpp
+++ source/simulation2/components/CCmpPathfinder.cpp
@@ -28,6 +28,7 @@
 #include "ps/CStr.h"
 #include "ps/Profile.h"
 #include "ps/XML/Xeromyces.h"
+#include "ps/ConfigDB.h"
 #include "renderer/Scene.h"
 #include "simulation2/MessageTypes.h"
 #include "simulation2/components/ICmpObstruction.h"
@@ -37,6 +38,8 @@
 #include "simulation2/helpers/Rasterize.h"
 #include "simulation2/serialization/SerializeTemplates.h"
 
+#include "tools/atlas/GameInterface/GameLoop.h"
+
 REGISTER_COMPONENT_TYPE(Pathfinder)
 
 void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
@@ -52,8 +55,6 @@
 	m_DebugOverlay = false;
 	m_AtlasOverlay = NULL;
 
-	m_SameTurnMovesCount = 0;
-
 	// Register Relax NG validator
 	CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
 
@@ -63,38 +64,86 @@
 	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();
+	m_MaxSameTurnMoves = (u16) pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
 
-
-	const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren();
+	const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild(
+			"PassabilityClasses").GetChildren();
 	for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it)
 	{
 		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());
 		m_PassClasses.push_back(PathfinderPassability(mask, it->second));
 		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);
+
+		if (threadcount < 1 || (g_AtlasGameLoop && g_AtlasGameLoop->running) || threadcount > 64)
+		{
+			useCustomThreadCount = false;
+		}
+		else
+		{
+			#ifndef NDEBUG
+			std::cerr << "Using " << threadcount << " pathfinder threads" << "\n";
+			#endif
+			for (u8 i = 0; i < (u8) threadcount; ++i)
+				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
+		}
+	}
+	if (!useCustomThreadCount)
+	{
+		// 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))
+		{
+			#ifndef NDEBUG
+			std::cerr << "Using 0 pathfinder threads" << "\n";
+			#endif
+			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)
+			// this way we'll benefit from hardware load-balancing a little.
+			if (std::thread::hardware_concurrency() == 2)
+			{
+				#ifndef NDEBUG
+				std::cerr << "Using 1 pathfinder thread" << "\n";
+				#endif
+				m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
+			}
+			else
+			{
+				#ifndef NDEBUG
+				std::cerr << "Using " << (std::thread::hardware_concurrency() - 1) * 2 << " pathfinder threads" << "\n";
+				#endif
+				for (size_t i = 0; i < (std::thread::hardware_concurrency() - 1) * 2; ++i)
+					m_WorkerThreads.push_back(new AsyncPathfinderWorkerThread(*this));
+			}
+		}
+	}
 }
 
 void CCmpPathfinder::Deinit()
 {
+	for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
+		worker->PrepareToKill();
+	m_MainThreadSignal.notify_all();
+	for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
+		delete worker;
+
+	m_WorkerThreads.clear();
 	SetDebugOverlay(false); // cleans up memory
 	SAFE_DELETE(m_AtlasOverlay);
 
@@ -140,7 +189,6 @@
 	SerializeVector<SerializeLongRequest>()(serialize, "long requests", m_AsyncLongPathRequests);
 	SerializeVector<SerializeShortRequest>()(serialize, "short requests", m_AsyncShortPathRequests);
 	serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
-	serialize.NumberU16_Unbounded("same turn moves count", m_SameTurnMovesCount);
 	serialize.NumberU16_Unbounded("map size", m_MapSize);
 }
 
@@ -160,24 +208,21 @@
 {
 	switch (msg.GetType())
 	{
-	case MT_RenderSubmit:
-	{
-		const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
-		RenderSubmit(msgData.collector);
-		break;
-	}
-	case MT_TerrainChanged:
-		m_TerrainDirty = true;
-		MinimalTerrainUpdate();
-		break;
-	case MT_WaterChanged:
-	case MT_ObstructionMapShapeChanged:
-		m_TerrainDirty = true;
-		UpdateGrid();
-		break;
-	case MT_TurnStart:
-		m_SameTurnMovesCount = 0;
-		break;
+		case MT_RenderSubmit:
+		{
+			const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
+			RenderSubmit(msgData.collector);
+			break;
+		}
+		case MT_TerrainChanged:
+			m_TerrainDirty = true;
+			MinimalTerrainUpdate();
+			break;
+		case MT_WaterChanged:
+		case MT_ObstructionMapShapeChanged:
+			m_TerrainDirty = true;
+			UpdateGrid();
+			break;
 	}
 }
 
@@ -237,7 +282,7 @@
 			return &passability;
 	}
 
-	return NULL;
+	return nullptr;
 }
 
 const Grid<NavcellData>& CCmpPathfinder::GetPassabilityGrid()
@@ -357,10 +402,11 @@
 			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))
+				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);
@@ -460,10 +506,12 @@
 	{
 		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_DirtinessInformation = {true, true, Grid<u8>(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE)};
 		m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
 
 		m_TerrainDirty = true;
@@ -557,9 +605,10 @@
 		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_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;
 		}
 	}
@@ -629,7 +678,7 @@
 				// 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);
+							+ (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);
@@ -672,123 +721,260 @@
 
 //////////////////////////////////////////////////////////
 
-// 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 };
-	m_AsyncLongPathRequests.push_back(req);
-	return req.ticket;
+	if (m_Pathfinder.m_UseThreading)
+		m_Thread = new std::thread(&CCmpPathfinder::AsyncPathfinderWorkerThread::InitThread, this,
+								   m_Pathfinder.m_WorkerThreads.size());
 }
 
-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 };
-	m_AsyncShortPathRequests.push_back(req);
-	return req.ticket;
+	if (m_Thread != nullptr)
+	{
+		if (m_Thread->joinable())
+			m_Thread->join();
+		delete m_Thread;
+	}
 }
 
-void CCmpPathfinder::FinishAsyncRequests()
+void CCmpPathfinder::AsyncPathfinderWorkerThread::InitThread(size_t index)
 {
-	PROFILE2("Finish Async Requests");
-	// Save the request queue in case it gets modified while iterating
-	std::vector<AsyncLongPathRequest> longRequests;
-	m_AsyncLongPathRequests.swap(longRequests);
-
-	std::vector<AsyncShortPathRequest> shortRequests;
-	m_AsyncShortPathRequests.swap(shortRequests);
+	g_Profiler2.RegisterCurrentThread("Pathfinder thread " + std::to_string(index));
+	WaitForWork();
+}
 
-	// TODO: we should only compute one path per entity per turn
+void CCmpPathfinder::AsyncPathfinderWorkerThread::PrepareToKill()
+{
+	m_Kill = true;
+}
 
-	// TODO: this computation should be done incrementally, spread
-	// across multiple frames (or even multiple turns)
+void CCmpPathfinder::AsyncPathfinderWorkerThread::WaitForWork()
+{
+	while (!m_Kill)
+	{
+		// wait until we're woken up
+		std::unique_lock<std::mutex> lock(m_Pathfinder.m_MainThreadMutex);
+		m_Pathfinder.m_MainThreadSignal.wait(lock);
+		lock.unlock();
 
-	ProcessLongRequests(longRequests);
-	ProcessShortRequests(shortRequests);
+		Work();
+	}
 }
 
-void CCmpPathfinder::ProcessLongRequests(const std::vector<AsyncLongPathRequest>& longRequests)
+void CCmpPathfinder::AsyncPathfinderWorkerThread::Work()
 {
-	PROFILE2("Process Long Requests");
-	for (size_t i = 0; i < longRequests.size(); ++i)
+	m_Computing = true;
+
+	// start by going through our long requests.
+	while (!m_LongRequests.empty())
 	{
-		const AsyncLongPathRequest& req = longRequests[i];
+		std::unique_lock<std::mutex> lock(m_Pause);
+		if (!m_Pathfinder.m_MayComputePaths)
+			return;
+
+		const AsyncLongPathRequest& req = m_LongRequests.back();
 		WaypointPath path;
 		ComputePath(req.x0, req.z0, req.goal, req.passClass, path);
-		CMessagePathResult msg(req.ticket, path);
-		GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
-	}
-}
+		m_Results.push_back({req.ticket, req.notify, path});
 
-void CCmpPathfinder::ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests)
-{
-	PROFILE2("Process Short Requests");
-	for (size_t i = 0; i < shortRequests.size(); ++i)
+		m_LongRequests.pop_back();
+		lock.unlock();
+	}
+	// then the short requests
+	while (!m_ShortRequests.empty())
 	{
-		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;
 		ControlGroupMovementObstructionFilter filter(req.avoidMovingUnits, req.group);
 		ComputeShortPath(filter, req.x0, req.z0, req.clearance, req.range, req.goal, req.passClass, path);
-		CMessagePathResult msg(req.ticket, path);
-		GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
+		m_Results.push_back({req.ticket, req.notify, path});
+
+		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,
+									 entity_id_t notify)
 {
-	if (!m_AsyncLongPathRequests.empty())
-	{
-		// Figure out how many moves we can do this time
-		i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
+	AsyncLongPathRequest req = {m_NextAsyncTicket++, x0, z0, goal, passClass, notify};
+	m_AsyncLongPathRequests.push_back(req);
+	return req.ticket;
+}
 
-		if (moveCount <= 0)
-			return;
+void
+CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass,
+									 WaypointPath& ret) const
+{
+	m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
+}
 
-		// Copy the long request elements we are going to process into a new array
-		std::vector<AsyncLongPathRequest> longRequests;
-		if ((i32)m_AsyncLongPathRequests.size() <= moveCount)
-		{
-			m_AsyncLongPathRequests.swap(longRequests);
-			moveCount = (i32)longRequests.size();
-		}
-		else
+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)
+{
+	AsyncShortPathRequest req = {m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits,
+								 group, notify};
+	m_AsyncShortPathRequests.push_back(req);
+	return req.ticket;
+}
+
+void CCmpPathfinder::FetchAsyncResultsAndSendMessages()
+{
+	// wait until all threads have stopped computing
+	// collect messages
+	// send them
+	PROFILE2("FetchAsyncResults");
+
+	while (true)
+	{
+		bool stop = true;
+		for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
+			if (worker->m_Computing)
+				stop = false;
+		if (stop)
+			break;
+	}
+
+	std::vector<PathResult> results;
+	for (AsyncPathfinderWorkerThread* worker : m_WorkerThreads)
+	{
+		results.insert(results.end(), std::make_move_iterator(worker->m_Results.begin()),
+					   std::make_move_iterator(worker->m_Results.end()));
+		worker->m_Results.clear();
+	}
+	// post messages
+	{
+		PROFILE2("PostMessages");
+		for (PathResult& path : results)
 		{
-			longRequests.resize(moveCount);
-			copy(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount, longRequests.begin());
-			m_AsyncLongPathRequests.erase(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount);
+			CMessagePathResult msg(path.ticket, path.path);
+			GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
 		}
+	}
+}
 
-		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)
+	{
+		size_t amount = std::min(m_AsyncLongPathRequests.size(), (size_t) m_MaxSameTurnMoves);
+		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
 	{
-		// Figure out how many moves we can do now
-		i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
+		longRequests.swap(m_AsyncLongPathRequests);
+		m_AsyncLongPathRequests.clear();
+	}
 
-		if (moveCount <= 0)
-			return;
+	done += longRequests.size();
 
-		// Copy the short request elements we are going to process into a new array
-		std::vector<AsyncShortPathRequest> shortRequests;
-		if ((i32)m_AsyncShortPathRequests.size() <= moveCount)
+	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)
 		{
-			m_AsyncShortPathRequests.swap(shortRequests);
-			moveCount = (i32)shortRequests.size();
+			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());
 		}
-		else
+		// 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();
+	}
+
+	std::vector<AsyncShortPathRequest> shortRequests;
+	if (useMax)
+	{
+		size_t amount = std::min(m_AsyncShortPathRequests.size(), (size_t) m_MaxSameTurnMoves - done);
+		if (amount > 0)
 		{
-			shortRequests.resize(moveCount);
-			copy(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount, shortRequests.begin());
-			m_AsyncShortPathRequests.erase(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount);
+			shortRequests.insert(shortRequests.begin(),
+								 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
+	{
+		shortRequests.swap(m_AsyncShortPathRequests);
+		m_AsyncShortPathRequests.clear();
+	}
 
-		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 (AsyncPathfinderWorkerThread* 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();
 }
 
 //////////////////////////////////////////////////////////
@@ -812,7 +998,7 @@
 }
 
 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
 	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
Index: source/simulation2/components/CCmpPathfinder_Common.h
===================================================================
--- source/simulation2/components/CCmpPathfinder_Common.h
+++ source/simulation2/components/CCmpPathfinder_Common.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -38,7 +38,12 @@
 #include "simulation2/components/ICmpObstructionManager.h"
 #include "simulation2/helpers/LongPathfinder.h"
 
+#include <thread>
+#include <mutex>
+#include <condition_variable>
+
 class SceneCollector;
+
 class AtlasOverlay;
 
 #ifdef NDEBUG
@@ -47,7 +52,6 @@
 #define PATHFIND_DEBUG 1
 #endif
 
-
 struct AsyncLongPathRequest
 {
 	u32 ticket;
@@ -120,6 +124,98 @@
  */
 class CCmpPathfinder : public ICmpPathfinder
 {
+protected:
+
+	class AsyncPathfinderWorkerThread
+	{
+		friend CCmpPathfinder;
+	private:
+		// takes care of what needs to be called to initialise the thread before calling WaitForWork();
+		void InitThread(size_t index);
+
+	public:
+		AsyncPathfinderWorkerThread(const CCmpPathfinder& pathfinder);
+
+		~AsyncPathfinderWorkerThread();
+
+		void PrepareToKill();
+
+		// Will loop until a conditional_variable notifies us, and call Work().
+		void WaitForWork();
+
+		// Process path requests, checking if we should stop before each new one. Sets m_Computing to false on return.
+		void Work();
+
+		/**
+		 * Compute a tile-based path from the given point to the goal, and return the set of waypoints.
+		 * The waypoints correspond to the centers of horizontally/vertically adjacent tiles
+		 * along the path.
+		 */
+		void
+		ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret)
+		{
+			m_Pathfinder.m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
+		}
+
+		/**
+		 * Compute a precise path from the given point to the goal, and return the set of waypoints.
+		 * The path is based on the full set of obstructions that pass the filter, such that
+		 * a unit of clearance 'clearance' will be able to follow the path with no collisions.
+		 * The path is restricted to a box of radius 'range' from the starting point.
+		 * Defined in CCmpPathfinder_Vertex.cpp
+		 */
+		void
+		ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance,
+						 entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret);
+
+	private:
+		/*
+		 * General state
+		 */
+
+		// read-only pathfinder, for getting required information (grids,…)
+		const CCmpPathfinder& m_Pathfinder;
+
+		// store our results, the main thread will fetch this
+		std::vector<PathResult> m_Results;
+
+		std::thread* m_Thread = nullptr;
+
+		bool m_Kill = false;
+
+		/*
+		 * Thread synchronisation
+		 */
+
+		bool m_Computing = false;
+		// using deque: for simplicity the worker thread will pop_back, the main thread will push_front
+		std::deque<AsyncLongPathRequest> m_LongRequests;
+		std::deque<AsyncShortPathRequest> m_ShortRequests;
+		// the main thread may push new requests even when we are computing existing ones, so lock.
+		std::mutex m_Pause;
+
+		/*
+		 * Memory optimisations: avoid recreating these vectors
+		 */
+
+		std::vector<Edge> edgesUnaligned;
+		std::vector<EdgeAA> edgesLeft;
+		std::vector<EdgeAA> edgesRight;
+		std::vector<EdgeAA> edgesBottom;
+		std::vector<EdgeAA> edgesTop;
+
+		// List of obstruction vertexes (plus start/end points); we'll try to find paths through
+		// the graph defined by these vertexes
+		std::vector<Vertex> vertexes;
+		// List of collision edges - paths must never cross these.
+		// (Edges are one-sided so intersections are fine in one direction, but not the other direction.)
+		std::vector<Edge> edges;
+		std::vector<Square> edgeSquares; // axis-aligned squares; equivalent to 4 edges};
+	};
+
+// Allow the workers to access our private variables
+	friend class AsyncPathfinderWorkerThread;
+
 public:
 	static void ClassInit(CComponentManager& componentManager)
 	{
@@ -143,7 +239,7 @@
 	std::vector<AsyncLongPathRequest> m_AsyncLongPathRequests;
 	std::vector<AsyncShortPathRequest> m_AsyncShortPathRequests;
 	u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests
-	u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn
+	u16 m_MaxSameTurnMoves; // How many moves to immediately compute.
 
 	// Lazily-constructed dynamic state (not serialized):
 
@@ -159,29 +255,25 @@
 	bool m_TerrainDirty;
 
 	// Interface to the long-range pathfinder.
-	LongPathfinder m_LongPathfinder;
-
-	// For responsiveness we will process some moves in the same turn they were generated in
-
-	u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn
+	mutable LongPathfinder m_LongPathfinder;
 
-	// memory optimizations: those vectors are created once, reused for all calculations;
-	std::vector<Edge> edgesUnaligned;
-	std::vector<EdgeAA> edgesLeft;
-	std::vector<EdgeAA> edgesRight;
-	std::vector<EdgeAA> edgesBottom;
-	std::vector<EdgeAA> edgesTop;
-
-	// List of obstruction vertexes (plus start/end points); we'll try to find paths through
-	// the graph defined by these vertexes
-	std::vector<Vertex> vertexes;
-	// List of collision edges - paths must never cross these.
-	// (Edges are one-sided so intersections are fine in one direction, but not the other direction.)
-	std::vector<Edge> edges;
-	std::vector<Square> edgeSquares; // axis-aligned squares; equivalent to 4 edges
+	// we Process paths in an asynchronous way, making sure to do it at times where it is safe.
+	std::vector<AsyncPathfinderWorkerThread*> m_WorkerThreads;
+	bool m_UseThreading = true;
+
+	// this variable will be set by the main thread. When going from true to false,
+	// the threads will define their own m_Computing to false. The main thread must wait until
+	// all threads' m_Computing are false to proceed.
+	bool m_MayComputePaths = false;
+
+	// we use a condition variable to wake the pathfinder threads when relevant
+	mutable std::condition_variable m_MainThreadSignal;
+	mutable std::mutex m_MainThreadMutex;
 
+	// HACK: the pathfinder is threaded but we will want to debug, so use mutexes and mutable to modify this.
 	bool m_DebugOverlay;
-	std::vector<SOverlayLine> m_DebugOverlayShortPathLines;
+	mutable std::vector<SOverlayLine> m_DebugOverlayShortPathLines;
+	mutable std::mutex m_DebugMutex;
 	AtlasOverlay* m_AtlasOverlay;
 
 	static std::string GetSchema()
@@ -205,9 +297,10 @@
 	virtual pass_class_t GetPassabilityClass(const std::string& name) const;
 
 	virtual void GetPassabilityClasses(std::map<std::string, pass_class_t>& passClasses) const;
+
 	virtual void GetPassabilityClasses(
-		std::map<std::string, pass_class_t>& nonPathfindingPassClasses,
-		std::map<std::string, pass_class_t>& pathfindingPassClasses) const;
+			std::map<std::string, pass_class_t>& nonPathfindingPassClasses,
+			std::map<std::string, pass_class_t>& pathfindingPassClasses) const;
 
 	const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const;
 
@@ -245,16 +338,15 @@
 
 	virtual Grid<u16> ComputeShoreGrid(bool expandOnWater = false);
 
-	virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret)
-	{
-		m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
-	}
-
-	virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify);
+	virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass,
+								 entity_id_t notify);
 
-	virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret);
+	virtual u32 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 controller, entity_id_t notify);
 
-	virtual u32 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 controller, entity_id_t notify);
+	virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass,
+									  WaypointPath& ret) const;
 
 	virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
 	{
@@ -279,21 +371,25 @@
 
 	virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0);
 
-	virtual bool 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;
-
-	virtual ICmpObstruction::EFoundationCheck CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool onlyCenterPoint) const;
-
-	virtual ICmpObstruction::EFoundationCheck 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;
+	virtual bool 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;
 
-	virtual ICmpObstruction::EFoundationCheck 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 onlyCenterPoint) const;
+	virtual ICmpObstruction::EFoundationCheck
+	CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r,
+					   pass_class_t passClass, bool onlyCenterPoint) const;
 
-	virtual void FinishAsyncRequests();
+	virtual ICmpObstruction::EFoundationCheck
+	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;
 
-	void ProcessLongRequests(const std::vector<AsyncLongPathRequest>& longRequests);
+	virtual ICmpObstruction::EFoundationCheck
+	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 onlyCenterPoint) const;
 
-	void ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests);
+	virtual void FetchAsyncResultsAndSendMessages();
 
-	virtual void ProcessSameTurnMoves();
+	virtual void StartProcessingMoves(bool useMax);
 
 	/**
 	 * Regenerates the grid based on the current obstruction list, if necessary
@@ -322,7 +418,7 @@
 	pass_class_t m_PassClass;
 
 	AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) :
-		TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
+			TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
 	{
 	}
 
@@ -335,7 +431,7 @@
 			for (size_t i = 0; i < w; ++i)
 			{
 				SColor4ub color(0, 0, 0, 0);
-				if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
+				if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int) i, (int) j), m_PassClass))
 					color = SColor4ub(255, 0, 0, 127);
 
 				*p++ = color.R;
Index: source/simulation2/components/CCmpPathfinder_Vertex.cpp
===================================================================
--- source/simulation2/components/CCmpPathfinder_Vertex.cpp
+++ source/simulation2/components/CCmpPathfinder_Vertex.cpp
@@ -1,4 +1,4 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -257,7 +257,7 @@
 	int i0, int j0, int i1, int j1,
 	pass_class_t passClass, const Grid<NavcellData>& grid)
 {
-	PROFILE("AddTerrainEdges");
+	//PROFILE2("AddTerrainEdges");
 
 	// Clamp the coordinates so we won't attempt to sample outside of the grid.
 	// (This assumes the outermost ring of navcells (which are always impassable)
@@ -509,39 +509,42 @@
 	}
 };
 
-void CCmpPathfinder::ComputeShortPath(const IObstructionTestFilter& filter,
+void CCmpPathfinder::AsyncPathfinderWorkerThread::ComputeShortPath(const IObstructionTestFilter& filter,
 	entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance,
 	entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& path)
 {
-	PROFILE("ComputeShortPath");
-	m_DebugOverlayShortPathLines.clear();
+	//PROFILE2("ComputeShortPath");
 
-	if (m_DebugOverlay)
+	if (m_Pathfinder.m_DebugOverlay)
 	{
+		std::unique_lock<std::mutex> lock(m_Pathfinder.m_DebugMutex);
+		m_Pathfinder.m_DebugOverlayShortPathLines.clear();
+
 		// Render the goal shape
-		m_DebugOverlayShortPathLines.push_back(SOverlayLine());
-		m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 0, 0, 1);
+		m_Pathfinder.m_DebugOverlayShortPathLines.push_back(SOverlayLine());
+		m_Pathfinder.m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 0, 0, 1);
 		switch (goal.type)
 		{
 		case PathGoal::POINT:
 		{
-			SimRender::ConstructCircleOnGround(GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), 0.2f, m_DebugOverlayShortPathLines.back(), true);
+			SimRender::ConstructCircleOnGround(m_Pathfinder.GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), 0.2f, m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 			break;
 		}
 		case PathGoal::CIRCLE:
 		case PathGoal::INVERTED_CIRCLE:
 		{
-			SimRender::ConstructCircleOnGround(GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat(), m_DebugOverlayShortPathLines.back(), true);
+			SimRender::ConstructCircleOnGround(m_Pathfinder.GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat(), m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 			break;
 		}
 		case PathGoal::SQUARE:
 		case PathGoal::INVERTED_SQUARE:
 		{
 			float a = atan2f(goal.v.X.ToFloat(), goal.v.Y.ToFloat());
-			SimRender::ConstructSquareOnGround(GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat()*2, goal.hh.ToFloat()*2, a, m_DebugOverlayShortPathLines.back(), true);
+			SimRender::ConstructSquareOnGround(m_Pathfinder.GetSimContext(), goal.x.ToFloat(), goal.z.ToFloat(), goal.hw.ToFloat()*2, goal.hh.ToFloat()*2, a, m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 			break;
 		}
 		}
+		lock.unlock();
 	}
 
 	// List of collision edges - paths must never cross these.
@@ -578,7 +581,7 @@
 	const size_t GOAL_VERTEX_ID = 1;
 
 	// Find all the obstruction squares that might affect us
-	CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
+	CmpPtr<ICmpObstructionManager> cmpObstructionManager(m_Pathfinder.GetSystemEntity());
 	std::vector<ICmpObstructionManager::ObstructionSquare> squares;
 	size_t staticShapesNb = 0;
 	cmpObstructionManager->GetStaticObstructionsInRange(filter, rangeXMin - clearance, rangeZMin - clearance, rangeXMax + clearance, rangeZMax + clearance, squares);
@@ -661,9 +664,9 @@
 	// Add terrain obstructions
 	{
 		u16 i0, j0, i1, j1;
-		Pathfinding::NearestNavcell(rangeXMin, rangeZMin, i0, j0, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
-		Pathfinding::NearestNavcell(rangeXMax, rangeZMax, i1, j1, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
-		AddTerrainEdges(edges, vertexes, i0, j0, i1, j1, passClass, *m_TerrainOnlyGrid);
+		Pathfinding::NearestNavcell(rangeXMin, rangeZMin, i0, j0, m_Pathfinder.m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_Pathfinder.m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
+		Pathfinding::NearestNavcell(rangeXMax, rangeZMax, i1, j1, m_Pathfinder.m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_Pathfinder.m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
+		AddTerrainEdges(edges, vertexes, i0, j0, i1, j1, passClass, *m_Pathfinder.m_TerrainOnlyGrid);
 	}
 
 	// Clip out vertices that are inside an edgeSquare (i.e. trivially unreachable)
@@ -689,14 +692,15 @@
 	ENSURE(vertexes.size() < 65536); // we store array indexes as u16
 
 	// Render the debug overlay
-	if (m_DebugOverlay)
+	if (m_Pathfinder.m_DebugOverlay)
 	{
+		std::unique_lock<std::mutex> lock(m_Pathfinder.m_DebugMutex);
 #define PUSH_POINT(p) STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat()))
 		// Render the vertexes as little Pac-Man shapes to indicate quadrant direction
 		for (size_t i = 0; i < vertexes.size(); ++i)
 		{
-			m_DebugOverlayShortPathLines.emplace_back();
-			m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 1, 0, 1);
+			m_Pathfinder.m_DebugOverlayShortPathLines.emplace_back();
+			m_Pathfinder.m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 1, 0, 1);
 
 			float x = vertexes[i].p.X.ToFloat();
 			float z = vertexes[i].p.Y.ToFloat();
@@ -709,19 +713,19 @@
 			else if (vertexes[i].quadInward == QUADRANT_BR) { a0 =  0.00f; a1 = 0.75f; }
 
 			if (a0 == a1)
-				SimRender::ConstructCircleOnGround(GetSimContext(), x, z, 0.5f,
-					m_DebugOverlayShortPathLines.back(), true);
+				SimRender::ConstructCircleOnGround(m_Pathfinder.GetSimContext(), x, z, 0.5f,
+					m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 			else
-				SimRender::ConstructClosedArcOnGround(GetSimContext(), x, z, 0.5f,
+				SimRender::ConstructClosedArcOnGround(m_Pathfinder.GetSimContext(), x, z, 0.5f,
 					a0 * ((float)M_PI*2.0f), a1 * ((float)M_PI*2.0f),
-					m_DebugOverlayShortPathLines.back(), true);
+					m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 		}
 
 		// Render the edges
 		for (size_t i = 0; i < edges.size(); ++i)
 		{
-			m_DebugOverlayShortPathLines.emplace_back();
-			m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1);
+			m_Pathfinder.m_DebugOverlayShortPathLines.emplace_back();
+			m_Pathfinder.m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1);
 			std::vector<float> xz;
 			PUSH_POINT(edges[i].p0);
 			PUSH_POINT(edges[i].p1);
@@ -736,15 +740,15 @@
 			PUSH_POINT(p4);
 			PUSH_POINT(edges[i].p1);
 
-			SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), true);
+			SimRender::ConstructLineOnGround(m_Pathfinder.GetSimContext(), xz, m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 		}
 #undef PUSH_POINT
 
 		// Render the axis-aligned squares
 		for (size_t i = 0; i < edgeSquares.size(); ++i)
 		{
-			m_DebugOverlayShortPathLines.push_back(SOverlayLine());
-			m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1);
+			m_Pathfinder.m_DebugOverlayShortPathLines.push_back(SOverlayLine());
+			m_Pathfinder.m_DebugOverlayShortPathLines.back().m_Color = CColor(0, 1, 1, 1);
 			std::vector<float> xz;
 			Square s = edgeSquares[i];
 			xz.push_back(s.p0.X.ToFloat());
@@ -757,8 +761,9 @@
 			xz.push_back(s.p0.Y.ToFloat());
 			xz.push_back(s.p0.X.ToFloat());
 			xz.push_back(s.p0.Y.ToFloat());
-			SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), true);
+			SimRender::ConstructLineOnGround(m_Pathfinder.GetSimContext(), xz, m_Pathfinder.m_DebugOverlayShortPathLines.back(), true);
 		}
+		lock.unlock();
 	}
 
 	// Do an A* search over the vertex/visibility graph:
@@ -772,7 +777,7 @@
 	// we can't reach. Since the algorithm can only reach a vertex once (and then it'll be marked
 	// as closed), we won't be doing any redundant visibility computations.
 
-	PROFILE_START("Short pathfinding - A*");
+	//PROFILE_START("Short pathfinding - A*");
 
 	VertexPriorityQueue open;
 	VertexPriorityQueue::Item qiStart = { START_VERTEX_ID, start.h, start.h };
@@ -853,16 +858,21 @@
 				CheckVisibility(vertexes[curr.id].p, npos, edgesUnaligned);
 
 			/*
-			// Render the edges that we examine
-			m_DebugOverlayShortPathLines.push_back(SOverlayLine());
-			m_DebugOverlayShortPathLines.back().m_Color = visible ? CColor(0, 1, 0, 0.5) : CColor(1, 0, 0, 0.5);
-			std::vector<float> xz;
-			xz.push_back(vertexes[curr.id].p.X.ToFloat());
-			xz.push_back(vertexes[curr.id].p.Y.ToFloat());
-			xz.push_back(npos.X.ToFloat());
-			xz.push_back(npos.Y.ToFloat());
-			SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), false);
-			*/
+ 			// Render the edges that we examine
+-			m_DebugOverlayShortPathLines.push_back(SOverlayLine());
+-			m_DebugOverlayShortPathLines.back().m_Color = visible ? CColor(0, 1, 0, 0.5) : CColor(1, 0, 0, 0.5);
++			std::unique_lock<std::mutex> lock(m_Pathfinder.m_DebugMutex);
++			m_Pathfinder.m_DebugOverlayShortPathLines.push_back(SOverlayLine());
++			m_Pathfinder.m_DebugOverlayShortPathLines.back().m_Color = visible ? CColor(0, 1, 0, 0.5) : CColor(1, 0, 0, 0.5);
+ 			std::vector<float> xz;
+ 			xz.push_back(vertexes[curr.id].p.X.ToFloat());
+ 			xz.push_back(vertexes[curr.id].p.Y.ToFloat());
+ 			xz.push_back(npos.X.ToFloat());
+ 			xz.push_back(npos.Y.ToFloat());
+-			SimRender::ConstructLineOnGround(GetSimContext(), xz, m_DebugOverlayShortPathLines.back(), false);
++			SimRender::ConstructLineOnGround(m_Pathfinder.GetSimContext(), xz, m_Pathfinder.m_DebugOverlayShortPathLines.back(), false);
++			 lock.unlock();
+ 			//*/
 
 			if (visible)
 			{
@@ -927,5 +937,16 @@
 	for (u16 id = idBest; id != START_VERTEX_ID; id = vertexes[id].pred)
 		path.m_Waypoints.emplace_back(Waypoint{ vertexes[id].p.X, vertexes[id].p.Y });
 
-	PROFILE_END("Short pathfinding - A*");
+
+	edges.clear();
+	edgeSquares.clear();
+	vertexes.clear();
+
+	edgesUnaligned.clear();
+	edgesLeft.clear();
+	edgesRight.clear();
+	edgesBottom.clear();
+	edgesTop.clear();
+
+	//PROFILE_END("Short pathfinding - A*");
 }
Index: source/simulation2/components/CCmpRallyPointRenderer.cpp
===================================================================
--- source/simulation2/components/CCmpRallyPointRenderer.cpp
+++ source/simulation2/components/CCmpRallyPointRenderer.cpp
@@ -681,7 +681,7 @@
 		start.X = m_RallyPoints[index-1].X;
 		start.Y = m_RallyPoints[index-1].Y;
 	}
-	cmpPathfinder->ComputePath(start.X, start.Y, goal, cmpPathfinder->GetPassabilityClass(m_LinePassabilityClass), path);
+	cmpPathfinder->ComputePathImmediate(start.X, start.Y, goal, cmpPathfinder->GetPassabilityClass(m_LinePassabilityClass), path);
 
 	// Check if we got a path back; if not we probably have two markers less than one tile apart.
 	if (path.m_Waypoints.size() < 2)
Index: source/simulation2/components/CCmpVisualActor.cpp
===================================================================
--- source/simulation2/components/CCmpVisualActor.cpp
+++ source/simulation2/components/CCmpVisualActor.cpp
@@ -68,8 +68,6 @@
 private:
 	std::wstring m_BaseActorName, m_ActorName;
 	bool m_IsFoundationActor;
-
-	// Not initialized in non-visual mode
 	CUnit* m_Unit;
 
 	fixed m_R, m_G, m_B; // shading color
@@ -452,13 +450,13 @@
 
 		SetVariant("animation", m_AnimName);
 
-		CmpPtr<ICmpSound> cmpSound(GetEntityHandle());
-		if (cmpSound)
-			m_SoundGroup = cmpSound->GetSoundGroup(wstring_from_utf8(m_AnimName));
-
 		if (!m_Unit || !m_Unit->GetAnimation() || !m_Unit->GetID())
 			return;
 
+		CmpPtr<ICmpSound> cmpSound(GetSimContext(), m_Unit->GetID());
+		if (cmpSound)
+			m_SoundGroup = cmpSound->GetSoundGroup(wstring_from_utf8(m_AnimName));
+
 		m_Unit->GetAnimation()->SetAnimationState(m_AnimName, m_AnimOnce, m_AnimSpeed.ToFloat(), m_AnimDesync.ToFloat(), m_SoundGroup.c_str());	
 	}
 
Index: source/simulation2/components/ICmpPathfinder.h
===================================================================
--- source/simulation2/components/ICmpPathfinder.h
+++ source/simulation2/components/ICmpPathfinder.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -33,6 +33,16 @@
 
 template<typename T> class Grid;
 
+// returned by asynchronous workers, used to send messages in the main thread.
+struct WaypointPath;
+
+struct PathResult
+{
+	u32 ticket;
+	entity_id_t notify;
+	WaypointPath path;
+};
+
 /**
  * Pathfinder algorithms.
  *
@@ -89,35 +99,25 @@
 	virtual Grid<u16> ComputeShoreGrid(bool expandOnWater = false) = 0;
 
 	/**
-	 * Compute a tile-based path from the given point to the goal, and return the set of waypoints.
-	 * The waypoints correspond to the centers of horizontally/vertically adjacent tiles
-	 * along the path.
-	 */
-	virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) = 0;
-
-	/**
-	 * Asynchronous version of ComputePath.
+	 * Request a long path computation, asynchronously.
 	 * The result will be sent as CMessagePathResult to 'notify'.
 	 * Returns a unique non-zero number, which will match the 'ticket' in the result,
 	 * so callers can recognise each individual request they make.
 	 */
 	virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify) = 0;
 
-	/**
-	 * If the debug overlay is enabled, render the path that will computed by ComputePath.
+	/*
+	 * Request a long-path computation immediately
 	 */
-	virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) = 0;
+	virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const = 0;
 
 	/**
-	 * Compute a precise path from the given point to the goal, and return the set of waypoints.
-	 * The path is based on the full set of obstructions that pass the filter, such that
-	 * a unit of clearance 'clearance' will be able to follow the path with no collisions.
-	 * The path is restricted to a box of radius 'range' from the starting point.
+	 * If the debug overlay is enabled, render the path that will computed by ComputePath.
 	 */
-	virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) = 0;
+	virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) = 0;
 
 	/**
-	 * Asynchronous version of ComputeShortPath (using ControlGroupObstructionFilter).
+	 * Request a short path computation, asynchronously.
 	 * The result will be sent as CMessagePathResult to 'notify'.
 	 * Returns a unique non-zero number, which will match the 'ticket' in the result,
 	 * so callers can recognise each individual request they make.
@@ -171,12 +171,12 @@
 	/**
 	 * Finish computing asynchronous path requests and send the CMessagePathResult messages.
 	 */
-	virtual void FinishAsyncRequests() = 0;
+	virtual void FetchAsyncResultsAndSendMessages() = 0;
 
 	/**
-	 * Process moves during the same turn they were created in to improve responsiveness.
+	 * Tell asynchronous pathfinder threads that they can begin computing paths.
 	 */
-	virtual void ProcessSameTurnMoves() = 0;
+	virtual void StartProcessingMoves(bool useMax = false) = 0;
 
 	/**
 	 * Regenerates the grid based on the current obstruction list, if necessary
Index: source/simulation2/components/tests/test_Pathfinder.h
===================================================================
--- source/simulation2/components/tests/test_Pathfinder.h
+++ source/simulation2/components/tests/test_Pathfinder.h
@@ -158,7 +158,7 @@
 			PathGoal goal = { PathGoal::POINT, x1, z1 };
 
 			WaypointPath path;
-			cmp->ComputePath(x0, z0, goal, cmp->GetPassabilityClass("default"), path);
+			cmp->ComputePathImmediate(x0, z0, goal, cmp->GetPassabilityClass("default"), path);
 		}
 
 		t = timer_Time() - t;
@@ -191,7 +191,7 @@
 		NullObstructionFilter filter;
 		PathGoal goal = { PathGoal::POINT, range, range };
 		WaypointPath path;
-		cmpPathfinder->ComputeShortPath(filter, range/3, range/3, fixed::FromInt(2), range, goal, 0, path);
+		//cmpPathfinder->ComputeShortPath(filter, range/3, range/3, fixed::FromInt(2), range, goal, 0, path);
 		for (size_t i = 0; i < path.m_Waypoints.size(); ++i)
 			printf("# %d: %f %f\n", (int)i, path.m_Waypoints[i].x.ToFloat(), path.m_Waypoints[i].z.ToFloat());
 	}
@@ -342,7 +342,7 @@
 		PathGoal goal = { PathGoal::POINT, x1, z1 };
 
 		WaypointPath path;
-		cmpPathfinder->ComputePath(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path);
+		cmpPathfinder->ComputePathImmediate(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path);
 
 		u32 debugSteps;
 		double debugTime;
@@ -391,7 +391,7 @@
 		for (int i = 0; i < n; ++i)
 		{
 			WaypointPath path;
-			cmpPathfinder->ComputePath(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path);
+			cmpPathfinder->ComputePathImmediate(x0, z0, goal, cmpPathfinder->GetPassabilityClass("default"), path);
 		}
 		t = timer_Time() - t;
 		debug_printf("### RepeatPath %fms each (%fs total)\n", 1000*t / n, t);
Index: source/simulation2/helpers/HierarchicalPathfinder.h
===================================================================
--- source/simulation2/helpers/HierarchicalPathfinder.h
+++ source/simulation2/helpers/HierarchicalPathfinder.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2015 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -86,7 +86,7 @@
 
 	void Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid);
 
-	RegionID Get(u16 i, u16 j, pass_class_t passClass);
+	RegionID Get(u16 i, u16 j, pass_class_t passClass) const;
 
 	/**
 	 * Updates @p goal so that it's guaranteed to be reachable from the navcell
@@ -98,18 +98,18 @@
 	 * In the case of a non-point reachable goal, it is replaced with a point goal
 	 * at the reachable navcell of the goal which is nearest to the starting navcell.
 	 */
-	void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass);
+	void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass) const;
 
 	/**
 	 * Updates @p i, @p j (which is assumed to be an impassable navcell)
 	 * to the nearest passable navcell.
 	 */
-	void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass);
+	void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass) const;
 
 	/**
 	 * Generates the connectivity grid associated with the given pass_class
 	 */
-	Grid<u16> GetConnectivityGrid(pass_class_t passClass);
+	Grid<u16> GetConnectivityGrid(pass_class_t passClass) const;
 
 	pass_class_t GetPassabilityClass(const std::string& name) const
 	{
@@ -146,25 +146,25 @@
 
 	typedef std::map<RegionID, std::set<RegionID> > EdgesMap;
 
-	void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges);
+	void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges) const;
 
-	void FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass);
+	void FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass) const;
 
-	void FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass);
+	void FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass) const;
 
 	/**
 	 * Updates @p iGoal and @p jGoal to the navcell that is the nearest to the
 	 * initial goal coordinates, in one of the given @p regions.
 	 * (Assumes @p regions is non-empty.)
 	 */
-	void FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass);
+	void FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass) const;
 
-	Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass)
+	const Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) const
 	{
-		return m_Chunks[passClass].at(cj * m_ChunksW + ci);
+		return m_Chunks.at(passClass).at(cj * m_ChunksW + ci);
 	}
 
-	void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid);
+	void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid) const;
 
 	u16 m_W, m_H;
 	u16 m_ChunksW, m_ChunksH;
Index: source/simulation2/helpers/HierarchicalPathfinder.cpp
===================================================================
--- source/simulation2/helpers/HierarchicalPathfinder.cpp
+++ source/simulation2/helpers/HierarchicalPathfinder.cpp
@@ -1,4 +1,4 @@
-/* Copyright (C) 2016 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -351,7 +351,7 @@
 	const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks,
 	const std::map<std::string, pass_class_t>& pathfindingPassClassMasks)
 {
-	PROFILE3("Hierarchical Recompute");
+	//PROFILE3("Hierarchical Recompute");
 
 	m_PassClassMasks = pathfindingPassClassMasks;
 
@@ -399,7 +399,7 @@
 
 	if (m_DebugOverlay)
 	{
-		PROFILE("debug overlay");
+		//PROFILE("debug overlay");
 		m_DebugOverlayLines.clear();
 		AddDebugEdges(GetPassabilityClass("default"));
 	}
@@ -407,7 +407,7 @@
 
 void HierarchicalPathfinder::Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid)
 {
-	PROFILE3("Hierarchical Update");
+	//PROFILE3("Hierarchical Update");
 
 	for (int cj = 0; cj <  m_ChunksH; ++cj)
 	{
@@ -448,7 +448,7 @@
 
 	if (m_DebugOverlay)
 	{
-		PROFILE("debug overlay");
+		//PROFILE("debug overlay");
 		m_DebugOverlayLines.clear();
 		AddDebugEdges(GetPassabilityClass("default"));
 	}
@@ -457,11 +457,11 @@
 /**
  * Find edges between regions in this chunk and the adjacent below/left chunks.
  */
-void HierarchicalPathfinder::FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges)
+void HierarchicalPathfinder::FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges) const
 {
-	std::vector<Chunk>& chunks = m_Chunks[passClass];
+	const std::vector<Chunk>& chunks = m_Chunks.at(passClass);
 
-	Chunk& a = chunks.at(cj*m_ChunksW + ci);
+	const Chunk& a = chunks.at(cj*m_ChunksW + ci);
 
 	// For each edge between chunks, we loop over every adjacent pair of
 	// navcells in the two chunks. If they are both in valid regions
@@ -473,7 +473,7 @@
 
 	if (ci > 0)
 	{
-		Chunk& b = chunks.at(cj*m_ChunksW + (ci-1));
+		const Chunk& b = chunks.at(cj*m_ChunksW + (ci-1));
 		RegionID raPrev(0,0,0);
 		RegionID rbPrev(0,0,0);
 		for (int j = 0; j < CHUNK_SIZE; ++j)
@@ -494,7 +494,7 @@
 
 	if (cj > 0)
 	{
-		Chunk& b = chunks.at((cj-1)*m_ChunksW + ci);
+		const Chunk& b = chunks.at((cj-1)*m_ChunksW + ci);
 		RegionID raPrev(0,0,0);
 		RegionID rbPrev(0,0,0);
 		for (int i = 0; i < CHUNK_SIZE; ++i)
@@ -556,17 +556,17 @@
 	}
 }
 
-HierarchicalPathfinder::RegionID HierarchicalPathfinder::Get(u16 i, u16 j, pass_class_t passClass)
+HierarchicalPathfinder::RegionID HierarchicalPathfinder::Get(u16 i, u16 j, pass_class_t passClass) const
 {
 	int ci = i / CHUNK_SIZE;
 	int cj = j / CHUNK_SIZE;
 	ENSURE(ci < m_ChunksW && cj < m_ChunksH);
-	return m_Chunks[passClass][cj*m_ChunksW + ci].Get(i % CHUNK_SIZE, j % CHUNK_SIZE);
+	return m_Chunks.at(passClass)[cj*m_ChunksW + ci].Get(i % CHUNK_SIZE, j % CHUNK_SIZE);
 }
 
-void HierarchicalPathfinder::MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass)
+void HierarchicalPathfinder::MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass) const
 {
-	PROFILE2("MakeGoalReachable");
+	//PROFILE2("MakeGoalReachable");
 	RegionID source = Get(i0, j0, passClass);
 
 	// Find everywhere that's reachable
@@ -633,14 +633,14 @@
 	goal = newGoal;
 }
 
-void HierarchicalPathfinder::FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass)
+void HierarchicalPathfinder::FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass) const
 {
 	std::set<RegionID> regions;
 	FindPassableRegions(regions, passClass);
 	FindNearestNavcellInRegions(regions, i, j, passClass);
 }
 
-void HierarchicalPathfinder::FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass)
+void HierarchicalPathfinder::FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass) const
 {
 	// Find the navcell in the given regions that's nearest to the goal navcell:
 	// * For each region, record the (squared) minimal distance to the goal point
@@ -697,7 +697,7 @@
 	jGoal = jBest;
 }
 
-void HierarchicalPathfinder::FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass)
+void HierarchicalPathfinder::FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass) const
 {
 	// Flood-fill the region graph, starting at 'from',
 	// collecting all the regions that are reachable via edges
@@ -711,7 +711,13 @@
 		RegionID curr = open.back();
 		open.pop_back();
 
-		for (const RegionID& region : m_Edges[passClass][curr])
+		// apparently the region we're from has no edges, so we'll return the empty set
+		// TODO: maybe here we should pretend we are on any other region?
+		// indeed because of rasterization issues sometimes we can end up on "unconnected" regions
+		if (m_Edges.at(passClass).find(curr) == m_Edges.at(passClass).end())
+			continue;
+
+		for (const RegionID& region : m_Edges.at(passClass).at(curr))
 			// Add to the reachable set; if this is the first time we added
 			// it then also add it to the open list
 			if (reachable.insert(region).second)
@@ -719,10 +725,10 @@
 	}
 }
 
-void HierarchicalPathfinder::FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass)
+void HierarchicalPathfinder::FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass) const
 {
 	// Construct a set of all regions of all chunks for this pass class
-	for (const Chunk& chunk : m_Chunks[passClass])
+	for (const Chunk& chunk : m_Chunks.at(passClass))
 	{
 		// region 0 is impassable tiles
 		for (int r = 1; r <= chunk.m_NumRegions; ++r)
@@ -730,14 +736,14 @@
 	}
 }
 
-void HierarchicalPathfinder::FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid)
+void HierarchicalPathfinder::FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid) const
 {
 	ENSURE(grid.m_W == m_W && grid.m_H == m_H);
 
 	int i0 = region.ci * CHUNK_SIZE;
 	int j0 = region.cj * CHUNK_SIZE;
 
-	const Chunk& c = m_Chunks[passClass][region.cj * m_ChunksW + region.ci];
+	const Chunk& c = m_Chunks.at(passClass)[region.cj * m_ChunksW + region.ci];
 
 	for (int j = 0; j < CHUNK_SIZE; ++j)
 		for (int i = 0; i < CHUNK_SIZE; ++i)
@@ -745,7 +751,7 @@
 				grid.set(i0 + i, j0 + j, value);
 }
 
-Grid<u16> HierarchicalPathfinder::GetConnectivityGrid(pass_class_t passClass)
+Grid<u16> HierarchicalPathfinder::GetConnectivityGrid(pass_class_t passClass) const
 {
 	Grid<u16> connectivityGrid(m_W, m_H);
 	connectivityGrid.reset();
Index: source/simulation2/helpers/LongPathfinder.h
===================================================================
--- source/simulation2/helpers/LongPathfinder.h
+++ source/simulation2/helpers/LongPathfinder.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -18,6 +18,7 @@
 #ifndef INCLUDED_LONGPATHFINDER
 #define INCLUDED_LONGPATHFINDER
 
+#include <mutex>
 #include "Pathfinding.h"
 #include "HierarchicalPathfinder.h"
 
@@ -217,7 +218,7 @@
 	 * along the path.
 	 */
 	void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
-		pass_class_t passClass, WaypointPath& path)
+		pass_class_t passClass, WaypointPath& path) const
 	{
 		if (!m_Grid)
 		{
@@ -251,33 +252,37 @@
 	u16 m_GridSize;
 
 	// Debugging - output from last pathfind operation:
-	LongOverlay* m_DebugOverlay;
-	PathfindTileGrid* m_DebugGrid;
-	u32 m_DebugSteps;
-	double m_DebugTime;
-	PathGoal m_DebugGoal;
-	WaypointPath* m_DebugPath;
-	pass_class_t m_DebugPassClass;
+	// HACK: computeJPSpath is const to ensure it's read-only but we want to be able to debug
+	// so mark those as mutable and use a mutex to lock.
+	mutable LongOverlay* m_DebugOverlay;
+	mutable PathfindTileGrid* m_DebugGrid;
+	mutable u32 m_DebugSteps;
+	mutable double m_DebugTime;
+	mutable PathGoal m_DebugGoal;
+	mutable WaypointPath* m_DebugPath;
+	mutable pass_class_t m_DebugPassClass;
+
+	mutable std::mutex m_Mutex;
 
 private:
-	PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal);
-	void ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state);
+	PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const;
+	void ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state) const;
 
 	/**
 	 * JPS algorithm helper functions
 	 * @param detectGoal is not used if m_UseJPSCache is true
 	 */
-	void AddJumpedHoriz(int i, int j, int di, PathCost g, PathfinderState& state, bool detectGoal);
-	int HasJumpedHoriz(int i, int j, int di, PathfinderState& state, bool detectGoal);
-	void AddJumpedVert(int i, int j, int dj, PathCost g, PathfinderState& state, bool detectGoal);
-	int HasJumpedVert(int i, int j, int dj, PathfinderState& state, bool detectGoal);
-	void AddJumpedDiag(int i, int j, int di, int dj, PathCost g, PathfinderState& state);
+	void AddJumpedHoriz(int i, int j, int di, PathCost g, PathfinderState& state, bool detectGoal) const;
+	int HasJumpedHoriz(int i, int j, int di, PathfinderState& state, bool detectGoal) const;
+	void AddJumpedVert(int i, int j, int dj, PathCost g, PathfinderState& state, bool detectGoal) const;
+	int HasJumpedVert(int i, int j, int dj, PathfinderState& state, bool detectGoal) const;
+	void AddJumpedDiag(int i, int j, int di, int dj, PathCost g, PathfinderState& state) const;
 
 	/**
 	 * See LongPathfinder.cpp for implementation details
 	 * TODO: cleanup documentation
 	 */
-	void ComputeJPSPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path);
+	void ComputeJPSPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path)const ;
 	void GetDebugDataJPS(u32& steps, double& time, Grid<u8>& grid) const;
 
 	// Helper functions for ComputePath
@@ -290,7 +295,7 @@
 	 * If @param maxDist is non-zero, path waypoints will be espaced by at most @param maxDist.
 	 * In that case the distance between (x0, z0) and the first waypoint will also be made less than maxDist.
 	 */
-	void ImprovePathWaypoints(WaypointPath& path, pass_class_t passClass, entity_pos_t maxDist, entity_pos_t x0, entity_pos_t z0);
+	void ImprovePathWaypoints(WaypointPath& path, pass_class_t passClass, entity_pos_t maxDist, entity_pos_t x0, entity_pos_t z0) const;
 
 	/**
 	 * Generate a passability map, stored in the 16th bit of navcells, based on passClass,
Index: source/simulation2/helpers/LongPathfinder.cpp
===================================================================
--- source/simulation2/helpers/LongPathfinder.cpp
+++ source/simulation2/helpers/LongPathfinder.cpp
@@ -1,4 +1,4 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -289,7 +289,7 @@
 
 	void reset(const Grid<NavcellData>* terrain, pass_class_t passClass)
 	{
-		PROFILE3("JumpPointCache reset");
+		//PROFILE3("JumpPointCache reset");
 		TIMER(L"JumpPointCache reset");
 
 		m_Width = terrain->m_W;
@@ -388,7 +388,7 @@
 
 // Calculate heuristic cost from tile i,j to goal
 // (This ought to be an underestimate for correctness)
-PathCost LongPathfinder::CalculateHeuristic(int i, int j, int iGoal, int jGoal)
+PathCost LongPathfinder::CalculateHeuristic(int i, int j, int iGoal, int jGoal) const
 {
 	int di = abs(i - iGoal);
 	int dj = abs(j - jGoal);
@@ -397,7 +397,7 @@
 }
 
 // Do the A* processing for a neighbour tile i,j.
-void LongPathfinder::ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state)
+void LongPathfinder::ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state) const
 {
 	// Reject impassable tiles
 	if (!PASSABLE(i, j))
@@ -501,7 +501,7 @@
 }
 
 
-void LongPathfinder::AddJumpedHoriz(int i, int j, int di, PathCost g, PathfinderState& state, bool detectGoal)
+void LongPathfinder::AddJumpedHoriz(int i, int j, int di, PathCost g, PathfinderState& state, bool detectGoal) const
 {
 	if (m_UseJPSCache)
 	{
@@ -543,7 +543,7 @@
 }
 
 // Returns the i-coordinate of the jump point if it exists, else returns i
-int LongPathfinder::HasJumpedHoriz(int i, int j, int di, PathfinderState& state, bool detectGoal)
+int LongPathfinder::HasJumpedHoriz(int i, int j, int di, PathfinderState& state, bool detectGoal) const
 {
 	if (m_UseJPSCache)
 	{
@@ -579,7 +579,7 @@
 	}
 }
 
-void LongPathfinder::AddJumpedVert(int i, int j, int dj, PathCost g, PathfinderState& state, bool detectGoal)
+void LongPathfinder::AddJumpedVert(int i, int j, int dj, PathCost g, PathfinderState& state, bool detectGoal) const
 {
 	if (m_UseJPSCache)
 	{
@@ -621,7 +621,7 @@
 }
 
 // Returns the j-coordinate of the jump point if it exists, else returns j
-int LongPathfinder::HasJumpedVert(int i, int j, int dj, PathfinderState& state, bool detectGoal)
+int LongPathfinder::HasJumpedVert(int i, int j, int dj, PathfinderState& state, bool detectGoal) const
 {
 	if (m_UseJPSCache)
 	{
@@ -661,7 +661,7 @@
  * We never cache diagonal jump points - they're usually so frequent that
  * a linear search is about as cheap and avoids the setup cost and memory cost.
  */
-void LongPathfinder::AddJumpedDiag(int i, int j, int di, int dj, PathCost g, PathfinderState& state)
+void LongPathfinder::AddJumpedDiag(int i, int j, int di, int dj, PathCost g, PathfinderState& state) const
 {
 	// 	ProcessNeighbour(i, j, i + di, j + dj, g, state);
 	// 	return;
@@ -712,13 +712,15 @@
 	}
 }
 
-void LongPathfinder::ComputeJPSPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path)
+void LongPathfinder::ComputeJPSPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const
 {
-	PROFILE("ComputePathJPS");
-	PROFILE2_IFSPIKE("ComputePathJPS", 0.0002);
+	//PROFILE("ComputePathJPS");
+	//PROFILE2("ComputePathJPS");
 	PathfinderState state = { 0 };
 
-	state.jpc = m_JumpPointCache[passClass].get();
+	ENSURE(!m_UseJPSCache && "Jump Point Cache currently not supported as it must handle threading properly.");
+	/*
+	state.jpc = m_JumpPointCache.at(passClass).get();
 	if (m_UseJPSCache && !state.jpc)
 	{
 		state.jpc = new JumpPointCache;
@@ -726,7 +728,7 @@
 		debug_printf("PATHFINDER: JPC memory: %d kB\n", (int)state.jpc->GetMemoryUsage() / 1024);
 		m_JumpPointCache[passClass] = shared_ptr<JumpPointCache>(state.jpc);
 	}
-
+	 */
 	// Convert the start coordinates to tile indexes
 	u16 i0, j0;
 	Pathfinding::NearestNavcell(x0, z0, i0, j0, m_GridSize, m_GridSize);
@@ -896,16 +898,18 @@
 
 	ImprovePathWaypoints(path, passClass, origGoal.maxdist, x0, z0);
 
+	SAFE_DELETE(state.tiles);
+
 	// Save this grid for debug display
 	delete m_DebugGrid;
-	m_DebugGrid = state.tiles;
-	m_DebugSteps = state.steps;
-	m_DebugGoal = state.goal;
+	//m_DebugGrid = state.tiles;
+	//m_DebugSteps = state.steps;
+	//m_DebugGoal = state.goal;
 }
 
 #undef PASSABLE
 
-void LongPathfinder::ImprovePathWaypoints(WaypointPath& path, pass_class_t passClass, entity_pos_t maxDist, entity_pos_t x0, entity_pos_t z0)
+void LongPathfinder::ImprovePathWaypoints(WaypointPath& path, pass_class_t passClass, entity_pos_t maxDist, entity_pos_t x0, entity_pos_t z0) const
 {
 	if (path.m_Waypoints.empty())
 		return;
@@ -959,6 +963,7 @@
 
 void LongPathfinder::GetDebugDataJPS(u32& steps, double& time, Grid<u8>& grid) const
 {
+	std::unique_lock<std::mutex> lock(m_Mutex);
 	steps = m_DebugSteps;
 	time = m_DebugTime;
 
@@ -979,14 +984,17 @@
 			grid.set(i, j, (t.IsOpen() ? 1 : 0) | (t.IsClosed() ? 2 : 0));
 		}
 	}
+	lock.unlock();
 }
 
 void LongPathfinder::SetDebugOverlay(bool enabled)
 {
+	std::unique_lock<std::mutex> lock(m_Mutex);
 	if (enabled && !m_DebugOverlay)
 		m_DebugOverlay = new LongOverlay(*this);
 	else if (!enabled && m_DebugOverlay)
 		SAFE_DELETE(m_DebugOverlay);
+	lock.unlock();
 }
 
 void LongPathfinder::ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
Index: source/simulation2/helpers/Render.cpp
===================================================================
--- source/simulation2/helpers/Render.cpp
+++ source/simulation2/helpers/Render.cpp
@@ -35,8 +35,6 @@
 void SimRender::ConstructLineOnGround(const CSimContext& context, const std::vector<float>& xz,
 		SOverlayLine& overlay, bool floating, float heightOffset)
 {
-	PROFILE("ConstructLineOnGround");
-
 	overlay.m_Coords.clear();
 
 	CmpPtr<ICmpTerrain> cmpTerrain(context, SYSTEM_ENTITY);
Index: source/simulation2/tests/test_Simulation2.h
===================================================================
--- source/simulation2/tests/test_Simulation2.h
+++ source/simulation2/tests/test_Simulation2.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2017 Wildfire Games.
+/* Copyright (C) 2018 Wildfire Games.
  * This file is part of 0 A.D.
  *
  * 0 A.D. is free software: you can redistribute it and/or modify
@@ -15,6 +15,7 @@
  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include "ps/ConfigDB.h"
 #include "lib/self_test.h"
 
 #include "scriptinterface/ScriptInterface.h"
@@ -43,6 +44,10 @@
 	void setUp()
 	{
 		g_VFS = CreateVfs();
+		if(!CConfigDB::IsInitialised())
+		{
+			new CConfigDB;
+		}
 		TS_ASSERT_OK(g_VFS->Mount(L"", DataDir()/"mods"/"_test.sim", VFS_MOUNT_MUST_EXIST));
 		TS_ASSERT_OK(g_VFS->Mount(L"cache", DataDir()/"_testcache"));
 		CXeromyces::Startup();