Index: binaries/data/config/default.cfg
===================================================================
--- binaries/data/config/default.cfg
+++ binaries/data/config/default.cfg
@@ -417,6 +417,9 @@
 zoom.in = 5
 zoom.out = 4
 
+[multithreading]
+pathfinder = 0                      ; How many threads to use for pathfinding. Special values: 0 chooses automatically, 1 de-activates threading entirely.
+
 [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
@@ -138,6 +138,7 @@
 				{ "nick": "kingadami", "name": "Adam Winsor" },
 				{ "nick": "kingbasil", "name": "Giannis Fafalios" },
 				{ "nick": "Krinkle", "name": "Timo Tijhof" },
+				{ "nick": "Kuba386", "name": "Jakub Kośmicki" },
 				{ "nick": "lafferjm", "name": "Justin Lafferty" },
 				{ "nick": "LeanderH", "name": "Leander Hemelhof" },
 				{ "nick": "leper", "name": "Georg Kilzer" },
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,16 @@
 				"label": "Chat timestamp",
 				"tooltip": "Show time that messages are posted in the lobby, gamesetup and ingame chat.",
 				"config": "chat.timestamp"
+			},
+			{
+				"type": "number",
+				"label": "Number of pathfinder threads",
+				"tooltip": "Number of pathfinder worker threads. Use 0 to choose automatically and 1 to disable threading altogether.",
+				"config": "multithreading.pathfinder",
+				"min": 0,
+				"max": 64
 			}
+
 		]
 	},
 	{
Index: source/ps/ThreadFrontier.h
===================================================================
--- /dev/null
+++ source/ps/ThreadFrontier.h
@@ -0,0 +1,73 @@
+/* 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/>.
+ */
+
+#ifndef INCLUDED_THREADFRONTIER
+#define INCLUDED_THREADFRONTIER
+
+#include <condition_variable>
+#include <mutex>
+
+/*
+ * A ThreadFrontier is similar to a Barrier in that it synchronizes n threads.
+ * A frontier has one thread waiting for n other threads to go through the Frontier.
+ */
+class ThreadFrontier
+{
+private:
+	std::mutex m_Mutex;
+	std::condition_variable m_ConditionVariable;
+	int m_Expecting;
+	int m_Count;
+public:
+	ThreadFrontier() : m_Expecting(0), m_Count(0) {};
+
+	void Setup(int expect)
+	{
+		ENSURE(m_Expecting == 0 && m_Count == 0);
+		std::lock_guard<std::mutex> lock(m_Mutex);
+		m_Expecting = expect;
+		// The frontier is open, call Reset() to close it.
+		m_Count = m_Expecting;
+	}
+
+	void Reset()
+	{
+		m_Count = 0;
+	}
+
+	void Watch()
+	{
+		std::unique_lock<std::mutex> lock(m_Mutex);
+		// If all threads have already gone through the frontier, we can stop watching right away.
+		if (m_Count == m_Expecting)
+			return;
+		m_ConditionVariable.wait(lock, [this] { return m_Count == m_Expecting; });
+	}
+
+	void GoThrough()
+	{
+		// Acquire the lock: we must be sure that the watching thread is either not yet in Watch()
+		// or is fully in the waiting state. Without this mutex lock, we could notify when the watching thread
+		// is in wait() but not yet in the waiting state, thus deadlocking.
+		std::lock_guard<std::mutex> lock(m_Mutex);
+		// Notify the watching thread if we are the last to go through.
+		if (++m_Count == m_Expecting)
+			m_ConditionVariable.notify_one();
+	}
+};
+
+#endif // INCLUDED_THREADFRONTIER
Index: source/ps/ThreadUtil.h
===================================================================
--- source/ps/ThreadUtil.h
+++ source/ps/ThreadUtil.h
@@ -33,6 +33,11 @@
  */
 void SetMainThread();
 
+/**
+ * Returns the number of threads we want for the pathfinder.
+ */
+u32 GetNumberOfPathfindingThreads();
+
 }
 
 #endif // INCLUDED_THREADUTIL
Index: source/ps/ThreadUtil.cpp
===================================================================
--- source/ps/ThreadUtil.cpp
+++ source/ps/ThreadUtil.cpp
@@ -20,6 +20,7 @@
 #include <thread>
 
 #include "ThreadUtil.h"
+#include "ConfigDB.h"
 
 static bool g_MainThreadSet;
 static std::thread::id g_MainThread;
@@ -39,3 +40,17 @@
 	g_MainThread = std::this_thread::get_id();
 	g_MainThreadSet = true;
 }
+
+u32 ThreadUtil::GetNumberOfPathfindingThreads()
+{
+	u32 wantedThreads = 0;
+
+	if (CConfigDB::IsInitialised())
+		CFG_GET_VAL("multithreading.pathfinder", wantedThreads);
+
+	// By default use (# of cores - 1) cores
+	if (wantedThreads == 0)
+		return std::thread::hardware_concurrency() - 1;
+
+	return wantedThreads;
+}
Index: source/simulation2/Simulation2.cpp
===================================================================
--- source/simulation2/Simulation2.cpp
+++ source/simulation2/Simulation2.cpp
@@ -26,6 +26,7 @@
 #include "simulation2/system/ComponentManager.h"
 #include "simulation2/system/ParamNode.h"
 #include "simulation2/system/SimContext.h"
+#include "simulation2/system/SimSynchronization.h"
 #include "simulation2/components/ICmpAIManager.h"
 #include "simulation2/components/ICmpCommandQueue.h"
 #include "simulation2/components/ICmpTemplateManager.h"
@@ -55,6 +56,7 @@
 		m_SecondaryTerrain(nullptr), m_SecondaryContext(nullptr), m_SecondaryComponentManager(nullptr), m_SecondaryLoadedScripts(nullptr),
 		m_MapSettings(cx->GetGeneralJSContext()), m_InitAttributes(cx->GetGeneralJSContext())
 	{
+		m_SimContext.m_SynchronizationData = &m_SynchronizationData;
 		m_SimContext.m_UnitManager = unitManager;
 		m_SimContext.m_Terrain = terrain;
 		m_ComponentManager.LoadComponentTypes();
@@ -125,6 +127,8 @@
 	double m_DeltaTime;
 	float m_LastFrameOffset;
 
+	SSimSynchronization m_SynchronizationData;
+
 	std::string m_StartupScript;
 	JS::PersistentRootedValue m_InitAttributes;
 	JS::PersistentRootedValue m_MapSettings;
@@ -895,6 +899,7 @@
 
 bool CSimulation2::DeserializeState(std::istream& stream)
 {
+	m->m_SynchronizationData.Reset();
 	// TODO: need to make sure the required SYSTEM_ENTITY components get constructed
 	return m->m_ComponentManager.DeserializeState(stream);
 }
Index: source/simulation2/TypeList.h
===================================================================
--- source/simulation2/TypeList.h
+++ source/simulation2/TypeList.h
@@ -123,6 +123,7 @@
 INTERFACE(Obstruction)
 COMPONENT(Obstruction)
 
+// Must come before Pathfinder.
 INTERFACE(ObstructionManager)
 COMPONENT(ObstructionManager)
 
@@ -135,6 +136,7 @@
 INTERFACE(ParticleManager)
 COMPONENT(ParticleManager)
 
+// Must come after ObstructionManager.
 INTERFACE(Pathfinder)
 COMPONENT(Pathfinder)
 
Index: source/simulation2/components/CCmpObstructionManager.cpp
===================================================================
--- source/simulation2/components/CCmpObstructionManager.cpp
+++ source/simulation2/components/CCmpObstructionManager.cpp
@@ -30,13 +30,14 @@
 #include "simulation2/helpers/Render.h"
 #include "simulation2/helpers/Spatial.h"
 #include "simulation2/serialization/SerializeTemplates.h"
+#include "simulation2/system/SimSynchronization.h"
 
 #include "graphics/Overlay.h"
 #include "graphics/Terrain.h"
 #include "maths/MathUtil.h"
 #include "ps/Profile.h"
-#include "renderer/Scene.h"
 #include "ps/CLogger.h"
+#include "renderer/Scene.h"
 
 // Externally, tags are opaque non-zero positive integers.
 // Internally, they are tagged (by shape) indexes into shape lists.
@@ -233,6 +234,8 @@
 	// So anything that happens here should be safely serialized.
 	virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+
 		m_WorldX0 = x0;
 		m_WorldZ0 = z0;
 		m_WorldX1 = x1;
@@ -257,6 +260,8 @@
 
 	void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+
 		// Use 8x8 tile subdivisions
 		// (TODO: find the optimal number instead of blindly guessing)
 		m_UnitSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE));
@@ -279,6 +284,8 @@
 
 	virtual tag_t AddUnitShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, flags_t flags, entity_id_t group)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+
 		UnitShape shape = { ent, x, z, clearance, flags, group };
 		u32 id = m_UnitShapeNext++;
 		m_UnitShapes[id] = shape;
@@ -292,6 +299,8 @@
 
 	virtual tag_t AddStaticShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h, flags_t flags, entity_id_t group, entity_id_t group2 /* = INVALID_ENTITY */)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+
 		fixed s, c;
 		sincos_approx(a, s, c);
 		CFixedVector2D u(c, -s);
@@ -331,6 +340,7 @@
 
 	virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
 		ENSURE(TAG_IS_VALID(tag));
 
 		if (TAG_IS_UNIT(tag))
@@ -380,6 +390,7 @@
 
 	virtual void SetUnitMovingFlag(tag_t tag, bool moving)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
 		ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag));
 
 		if (TAG_IS_UNIT(tag))
@@ -396,6 +407,7 @@
 
 	virtual void SetUnitControlGroup(tag_t tag, entity_id_t group)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
 		ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag));
 
 		if (TAG_IS_UNIT(tag))
@@ -407,6 +419,7 @@
 
 	virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
 		ENSURE(TAG_IS_VALID(tag) && TAG_IS_STATIC(tag));
 
 		if (TAG_IS_STATIC(tag))
@@ -419,6 +432,7 @@
 
 	virtual void RemoveShape(tag_t tag)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
 		ENSURE(TAG_IS_VALID(tag));
 
 		if (TAG_IS_UNIT(tag))
@@ -491,6 +505,8 @@
 
 	virtual void SetPassabilityCircular(bool enabled)
 	{
+		ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+
 		m_PassabilityCircular = enabled;
 		MakeDirtyAll();
 
Index: source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- source/simulation2/components/CCmpPathfinder.cpp
+++ source/simulation2/components/CCmpPathfinder.cpp
@@ -27,6 +27,7 @@
 #include "ps/CLogger.h"
 #include "ps/CStr.h"
 #include "ps/Profile.h"
+#include "ps/ThreadUtil.h"
 #include "ps/XML/Xeromyces.h"
 #include "renderer/Scene.h"
 #include "simulation2/MessageTypes.h"
@@ -40,6 +41,7 @@
 #include "simulation2/helpers/Rasterize.h"
 #include "simulation2/helpers/VertexPathfinder.h"
 #include "simulation2/serialization/SerializeTemplates.h"
+#include "simulation2/system/SimSynchronization.h"
 
 REGISTER_COMPONENT_TYPE(Pathfinder)
 
@@ -68,21 +70,6 @@
 	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();
 
@@ -97,13 +84,37 @@
 		m_PassClassMasks[name] = mask;
 	}
 
-	m_Workers.emplace_back(PathfinderWorker{});
-}
+	u32 wantedThreads = ThreadUtil::GetNumberOfPathfindingThreads();
+
+	LOGMESSAGE("Initialising %i threads for pathfinding.", wantedThreads);
+
+	// The worker thread will only call std::thread if we actually have > 1 threads, otherwise we're running in the main thread.
+	if (wantedThreads <= 1) // <= 1 as the above computations returns 0 for one core.
+	{
+		m_UseThreading = false;
+		m_Workers.emplace_back();
+	}
+	else
+	{
+		m_PathfinderFrontier.Setup(wantedThreads);
+		m_UseThreading = true;
+		// We cannot move workers or threads will run on deleted instances.
+		m_Workers.resize(wantedThreads);
+		for (size_t i = 0; i < wantedThreads; ++i)
+			m_Workers[i].Start(*this, i);
+	}
+};
 
 CCmpPathfinder::~CCmpPathfinder() {};
 
 void CCmpPathfinder::Deinit()
 {
+	for (PathfinderWorker& worker : m_Workers)
+		worker.PrepareToKill();
+
+	GetSimContext().GetSynchronizationData().m_ComputingPaths = false;
+
+	m_PathfinderConditionVariable.notify_all();
 	m_Workers.clear();
 
 	SetDebugOverlay(false); // cleans up memory
@@ -213,6 +224,9 @@
 
 void CCmpPathfinder::SetDebugOverlay(bool enabled)
 {
+	if (enabled && m_UseThreading)
+		LOGWARNING("Warning: the vertex pathfinder only shows immediate requests when using threading. "
+				   "Configure pathfinder threads to 0 to see vertex pathfinder requests");
 	m_VertexPathfinder->SetDebugOverlay(enabled);
 	m_LongPathfinder->SetDebugOverlay(enabled);
 }
@@ -478,6 +492,8 @@
 {
 	PROFILE3("UpdateGrid");
 
+	ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+
 	CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
 	if (!cmpTerrain)
 		return; // error
@@ -732,7 +748,31 @@
 
 // Async pathfinder workers
 
-CCmpPathfinder::PathfinderWorker::PathfinderWorker() {}
+CCmpPathfinder::PathfinderWorker::PathfinderWorker() : m_Computing(false), m_Kill(false)
+{
+}
+
+CCmpPathfinder::PathfinderWorker::~PathfinderWorker()
+{
+	if (m_Thread.joinable())
+		m_Thread.join();
+}
+
+void CCmpPathfinder::PathfinderWorker::Start(const CCmpPathfinder& pathfinder, size_t index)
+{
+	if (pathfinder.m_UseThreading)
+		m_Thread = std::thread(&CCmpPathfinder::PathfinderWorker::InitThread, this, std::ref(pathfinder), index);
+}
+
+void CCmpPathfinder::PathfinderWorker::InitThread(const CCmpPathfinder& pathfinder, size_t index)
+{
+	g_Profiler2.RegisterCurrentThread("Pathfinder thread " + std::to_string(index));
+	debug_SetThreadName(("Pathfinder thread " + std::to_string(index)).c_str());
+
+	m_VertexPathfinder = std::make_unique<VertexPathfinder>(pathfinder.m_MapSize, pathfinder.m_TerrainOnlyGrid);
+
+	WaitForWork(pathfinder);
+}
 
 template<typename T>
 void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<T>&, ssize_t)
@@ -750,9 +790,35 @@
 	m_ShortRequests.insert(m_ShortRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end()));
 }
 
+void CCmpPathfinder::PathfinderWorker::PrepareToKill()
+{
+	m_Kill = true;
+}
+
+void CCmpPathfinder::PathfinderWorker::WaitForWork(const CCmpPathfinder& pathfinder)
+{
+	while (true)
+	{
+		{
+			std::unique_lock<std::mutex> lock(pathfinder.m_PathfinderMutex);
+			pathfinder.m_PathfinderConditionVariable.wait(lock, [this] { return m_Computing || m_Kill; });
+		}
+
+		if (m_Kill)
+			return;
+		Work(pathfinder);
+
+		// We must be the ones setting our m_Computing to false.
+		ENSURE(m_Computing);
+		m_Computing = false;
+
+		pathfinder.m_PathfinderFrontier.GoThrough();
+	}
+}
+
 void CCmpPathfinder::PathfinderWorker::Work(const CCmpPathfinder& pathfinder)
 {
-	while (!m_LongRequests.empty())
+	while (!m_LongRequests.empty() && !m_Kill)
 	{
 		const LongPathRequest& req = m_LongRequests.back();
 		WaypointPath path;
@@ -762,10 +828,10 @@
 		m_LongRequests.pop_back();
 	}
 
-	while (!m_ShortRequests.empty())
+	while (!m_ShortRequests.empty() && !m_Kill)
 	{
 		const ShortPathRequest& req = m_ShortRequests.back();
-		WaypointPath path = pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(pathfinder.GetSystemEntity()));
+		WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(pathfinder.GetSystemEntity()));
 		m_Results.emplace_back(req.ticket, req.notify, path);
 
 		m_ShortRequests.pop_back();
@@ -802,6 +868,12 @@
 {
 	PROFILE2("FetchAsyncResults");
 
+	// TODO maybe: a possible improvement here would be to push results from workers whenever they are done, and not when all are done.
+
+	// Wait until all threads have finished computing.
+	m_PathfinderFrontier.Watch();
+	GetSimContext().GetSynchronizationData().m_ComputingPaths = false;
+
 	// We may now clear existing requests.
 	m_ShortPathRequests.clear();
 	m_LongPathRequests.clear();
@@ -833,8 +905,23 @@
 	PushRequestsToWorkers(longRequests);
 	PushRequestsToWorkers(shortRequests);
 
-	for (PathfinderWorker& worker : m_Workers)
-		worker.Work(*this);
+	m_PathfinderFrontier.Reset();
+
+	ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths);
+	GetSimContext().GetSynchronizationData().m_ComputingPaths = true;
+
+	if (m_UseThreading)
+	{
+		for (PathfinderWorker& worker : m_Workers)
+		{
+			// Mark as computing to unblock.
+			ENSURE(!worker.m_Computing);
+			worker.m_Computing = true;
+		}
+		m_PathfinderConditionVariable.notify_all();
+	}
+	else
+		m_Workers.back().Work(*this);
 }
 
 template <typename T>
@@ -867,6 +954,10 @@
 	// In this instance, work is distributed in a strict LIFO order, effectively reversing tickets.
 	for (PathfinderWorker& worker : m_Workers)
 	{
+		// Prevent pushing requests when the worker is computing.
+		// Call FetchAsyncResultsAndSendMessages() before pushing new requests.
+		ENSURE(!worker.m_Computing);
+
 		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());
Index: source/simulation2/components/CCmpPathfinder_Common.h
===================================================================
--- source/simulation2/components/CCmpPathfinder_Common.h
+++ source/simulation2/components/CCmpPathfinder_Common.h
@@ -35,10 +35,13 @@
 #include "graphics/Terrain.h"
 #include "maths/MathUtil.h"
 #include "ps/CLogger.h"
+#include "ps/ThreadFrontier.h"
 #include "renderer/TerrainOverlay.h"
 #include "simulation2/components/ICmpObstructionManager.h"
 #include "simulation2/helpers/Grid.h"
 
+#include <thread>
+
 
 class HierarchicalPathfinder;
 class LongPathfinder;
@@ -65,21 +68,63 @@
 		friend CCmpPathfinder;
 	public:
 		PathfinderWorker();
+		/**
+		 * Implement a noexcept move constructor for std::vector that actually does nothing.
+		 */
+		PathfinderWorker(PathfinderWorker&&) noexcept
+		{
+			ENSURE(!m_Thread.joinable());
+		}
 
-		// Process path requests, checking if we should stop before each new one.
+		~PathfinderWorker();
+
+		/**
+		 * Create the std::thread and call InitThread
+		 */
+		void Start(const CCmpPathfinder& pathfinder, size_t index);
+
+		void PrepareToKill();
+
+		/**
+		 * Will loop until a condition_variable notifies us, and call Work().
+		 */
+		void WaitForWork(const CCmpPathfinder& pathfinder);
+
+		/**
+		 * Process path requests, checking if we should stop before each new one.
+		 * Should be callable both synchronously and asynchronously.
+		 */
 		void Work(const CCmpPathfinder& pathfinder);
 
 	private:
-		// Insert requests in m_[Long/Short]Requests depending on from.
-		// This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers
+		/**
+		 * Takes care of what needs to be called to initialise the thread before calling WaitForWork().
+		 */
+		void InitThread(const CCmpPathfinder& pathfinder, size_t index);
+
+		/**
+		 * Insert requests in m_[Long/Short]Requests depending on from.
+		 * This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers
+		 */
 		template<typename T>
 		void PushRequests(std::vector<T>& from, ssize_t amount);
 
 		// Stores our results, the main thread will fetch this.
 		std::vector<PathResult> m_Results;
 
+		std::thread m_Thread;
+
+		std::atomic<bool> m_Kill;
+		std::atomic<bool> m_Computing;
+
 		std::vector<LongPathRequest> m_LongRequests;
 		std::vector<ShortPathRequest> m_ShortRequests;
+
+		// The vertex pathfinder has local caches that cannot be shared across threads
+		// Since it otherwise has no particular state, we can freely have one for each pathfinder worker.
+		// (this data could be thread_local, but the performance of that is terrible)
+		std::unique_ptr<VertexPathfinder> m_VertexPathfinder;
+		// The same is not true of the long-range pathfinder, which uses the grid, but has no particular thread-local state.
 	};
 
 	// Allow the workers to access our private variables
@@ -124,12 +169,16 @@
 	GridUpdateInformation m_AIPathfinderDirtinessInformation;
 	bool m_TerrainDirty;
 
-	std::unique_ptr<VertexPathfinder> m_VertexPathfinder;
+	std::unique_ptr<VertexPathfinder> m_VertexPathfinder; // If threading is used, this will only be used for synchronous callse
 	std::unique_ptr<HierarchicalPathfinder> m_PathfinderHier;
 	std::unique_ptr<LongPathfinder> m_LongPathfinder;
 
-	// Workers process pathing requests.
+	// Worker process pathing requests.
 	std::vector<PathfinderWorker> m_Workers;
+	bool m_UseThreading = false;
+	mutable std::mutex m_PathfinderMutex;
+	mutable std::condition_variable m_PathfinderConditionVariable;
+	mutable ThreadFrontier m_PathfinderFrontier;
 
 	AtlasOverlay* m_AtlasOverlay;
 
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) 2020 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 "graphics/Overlay.h"
@@ -223,15 +224,14 @@
 	u16 m_GridSize;
 
 	// Debugging - output from last pathfind operation.
-	// mutable as making these const would require a lot of boilerplate code
-	// and they do not change the behavioural const-ness of the pathfinder.
-	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;
+	// Static and thread-local - we don't support threading debug code.
+	static thread_local LongOverlay* m_DebugOverlay;
+	static thread_local PathfindTileGrid* m_DebugGrid;
+	static thread_local u32 m_DebugSteps;
+	static thread_local double m_DebugTime;
+	static thread_local PathGoal m_DebugGoal;
+	static thread_local WaypointPath* m_DebugPath;
+	static thread_local pass_class_t m_DebugPassClass;
 
 private:
 	PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const;
@@ -273,11 +273,8 @@
 	void GenerateSpecialMap(pass_class_t passClass, std::vector<CircularRegion> excludedRegions);
 
 	bool m_UseJPSCache;
-	// Mutable may be used here as caching does not change the external const-ness of the Long Range pathfinder.
-	// This is thread-safe as it is order independent (no change in the output of the function for a given set of params).
-	// Obviously, this means that the cache should actually be a cache and not return different results
-	// from what would happen if things hadn't been cached.
-	mutable std::map<pass_class_t, shared_ptr<JumpPointCache> > m_JumpPointCache;
+
+	static thread_local std::map<pass_class_t, shared_ptr<JumpPointCache> > m_JumpPointCache;
 };
 
 /**
Index: source/simulation2/helpers/LongPathfinder.cpp
===================================================================
--- source/simulation2/helpers/LongPathfinder.cpp
+++ source/simulation2/helpers/LongPathfinder.cpp
@@ -25,6 +25,15 @@
 #include "Geometry.h"
 #include "HierarchicalPathfinder.h"
 
+thread_local LongOverlay* LongPathfinder::m_DebugOverlay;
+thread_local PathfindTileGrid* LongPathfinder::m_DebugGrid;
+thread_local u32 LongPathfinder::m_DebugSteps;
+thread_local double LongPathfinder::m_DebugTime;
+thread_local PathGoal LongPathfinder::m_DebugGoal;
+thread_local WaypointPath* LongPathfinder::m_DebugPath;
+thread_local pass_class_t LongPathfinder::m_DebugPassClass;
+thread_local std::map<pass_class_t, shared_ptr<JumpPointCache> > LongPathfinder::m_JumpPointCache;
+
 /**
  * Jump point cache.
  *
@@ -371,11 +380,11 @@
 
 //////////////////////////////////////////////////////////
 
-LongPathfinder::LongPathfinder() :
-	m_UseJPSCache(false),
-	m_Grid(NULL), m_GridSize(0),
-	m_DebugOverlay(NULL), m_DebugGrid(NULL), m_DebugPath(NULL)
+LongPathfinder::LongPathfinder() : m_UseJPSCache(false), m_Grid(nullptr), m_GridSize(0)
 {
+	m_DebugOverlay = nullptr;
+	m_DebugGrid = nullptr;
+	m_DebugPath = nullptr;
 }
 
 LongPathfinder::~LongPathfinder()
Index: source/simulation2/system/ComponentManager.cpp
===================================================================
--- source/simulation2/system/ComponentManager.cpp
+++ source/simulation2/system/ComponentManager.cpp
@@ -502,9 +502,9 @@
 	m_DynamicMessageSubscriptionsNonsync.clear();
 	m_DynamicMessageSubscriptionsNonsyncByComponent.clear();
 
-	// Delete all IComponents
-	std::map<ComponentTypeId, std::map<entity_id_t, IComponent*> >::iterator iit = m_ComponentsByTypeId.begin();
-	for (; iit != m_ComponentsByTypeId.end(); ++iit)
+	// Delete all IComponents in reverse order of creation.
+	std::map<ComponentTypeId, std::map<entity_id_t, IComponent*> >::reverse_iterator iit = m_ComponentsByTypeId.rbegin();
+	for (; iit != m_ComponentsByTypeId.rend(); ++iit)
 	{
 		std::map<entity_id_t, IComponent*>::iterator eit = iit->second.begin();
 		for (; eit != iit->second.end(); ++eit)
Index: source/simulation2/system/SimContext.h
===================================================================
--- source/simulation2/system/SimContext.h
+++ source/simulation2/system/SimContext.h
@@ -24,6 +24,7 @@
 class CUnitManager;
 class CTerrain;
 class ScriptInterface;
+struct SSimSynchronization;
 
 /**
  * Contains pointers to various 'global' objects that are needed by the simulation code,
@@ -45,6 +46,8 @@
 
 	ScriptInterface& GetScriptInterface() const;
 
+	SSimSynchronization& GetSynchronizationData() const;
+
 	void SetSystemEntity(CEntityHandle ent) { m_SystemEntity = ent; }
 	CEntityHandle GetSystemEntity() const { ASSERT(m_SystemEntity.GetId() == SYSTEM_ENTITY); return m_SystemEntity; }
 
@@ -55,9 +58,10 @@
 	int GetCurrentDisplayedPlayer() const;
 
 private:
-	CComponentManager* m_ComponentManager;
-	CUnitManager* m_UnitManager;
-	CTerrain* m_Terrain;
+	CComponentManager* m_ComponentManager = nullptr;
+	CUnitManager* m_UnitManager = nullptr;
+	CTerrain* m_Terrain = nullptr;
+	SSimSynchronization* m_SynchronizationData = nullptr;
 
 	CEntityHandle m_SystemEntity;
 
Index: source/simulation2/system/SimContext.cpp
===================================================================
--- source/simulation2/system/SimContext.cpp
+++ source/simulation2/system/SimContext.cpp
@@ -23,8 +23,7 @@
 
 #include "ps/Game.h"
 
-CSimContext::CSimContext() :
-	m_ComponentManager(NULL), m_UnitManager(NULL), m_Terrain(NULL)
+CSimContext::CSimContext()
 {
 }
 
@@ -65,6 +64,11 @@
 	return GetComponentManager().GetScriptInterface();
 }
 
+SSimSynchronization& CSimContext::GetSynchronizationData() const
+{
+	return *m_SynchronizationData;
+}
+
 int CSimContext::GetCurrentDisplayedPlayer() const
 {
 	return g_Game ? g_Game->GetViewedPlayerID() : -1;
Index: source/simulation2/system/SimSynchronization.h
===================================================================
--- /dev/null
+++ source/simulation2/system/SimSynchronization.h
@@ -0,0 +1,49 @@
+/* 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/>.
+ */
+
+#ifndef INCLUDED_SIM_SYNCHRONIZATION
+#define INCLUDED_SIM_SYNCHRONIZATION
+
+/**
+ * Some simulation operations are threaded.
+ * To avoid logical errors, this holds the status of all relevant operations,
+ * so that components can ENSURE() they're only doing operations in the correct state(s).
+ * This is intended to reveal programming errors, not to actually be a synchronization mechanism.
+ *
+ * Though data in this class is really intended to be written to from the main thread,
+ * variables are atomic to ensure that operations are not reordered in a confusing way.
+ */
+struct SSimSynchronization
+{
+	NONCOPYABLE(SSimSynchronization);
+
+	SSimSynchronization() : m_ComputingPaths(false) {};
+
+	void Reset() {
+		m_ComputingPaths = false;
+	}
+
+	/**
+	 * When this is true, the pathfinders are computing paths. In practice:
+	 *  - Nothing can change the pathfinder grid.
+	 *  - Nothing can change obstruction state (neither the obstructions nor the manager's).
+	 * This means no entities can be moved, killed, created, etc.
+	 */
+	std::atomic<bool> m_ComputingPaths;
+};
+
+#endif // INCLUDED_SIM_SYNCHRONIZATION