Index: binaries/data/config/default.cfg =================================================================== --- binaries/data/config/default.cfg +++ binaries/data/config/default.cfg @@ -413,6 +413,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 @@ -135,6 +135,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/MutexProtected.h =================================================================== --- /dev/null +++ source/ps/MutexProtected.h @@ -0,0 +1,62 @@ +/* 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 . + */ + +#ifndef INCLUDED_MUTEXPROTECTED +#define INCLUDED_MUTEXPROTECTED + +#include + +// The following is a code trick to make sure one locks the mutex before modifying the underlying data. +// One must acquire a [PROTECTED_DATA_NAME]::Lock, which locks the mutex, and use that to access the variables. +// Const-access does not require locking. + +// Usage: define PROTECTED_DATA_NAME, use the macros, undef PROTECTED_DATA_NAME. + +#define PROTECTED_DATA_CONCAT(a,b,c) PROTECTED_DATA_CONCAT_(a,b,c) +#define PROTECTED_DATA_CONCAT_(a,b,c) a ## b ## c + +#define BEGIN_PROTECTED_DATA() \ +struct PROTECTED_DATA_NAME { \ + struct Lock { \ + Lock(PROTECTED_DATA_NAME& data) : lock(data.m_LockShapesMutex) { \ + lock.lock(); \ + }; \ + ~Lock() { lock.unlock(); } \ + private: \ + std::mutex& lock; \ + }; \ + \ + /* Mutex to prevent changes to shapes and subdivisions for the threaded pathfinder. */ \ + std::mutex m_LockShapesMutex; + +// This defines a member of the protected data struct. +#define PROTECTED_DATA(type, x) \ +protected: \ +type m_##x; \ +public: \ +type& x(PROTECTED_DATA_NAME::Lock&) { return m_##x; }; \ +const type& x() const { return m_##x; }; + +// Ends the struct definition. +#define END_PROTECTED_DATA() } PROTECTED_DATA_CONCAT(m_, PROTECTED_DATA_NAME, Data); + +// This should be called in the parent class to access the protected data. +#define PROTECTED_DATA_ACCESSOR(type, x) \ +type& x(PROTECTED_DATA_NAME::Lock& key) { return PROTECTED_DATA_CONCAT(m_, PROTECTED_DATA_NAME, Data).x(key); }; \ +const type& x() const { return PROTECTED_DATA_CONCAT(m_, PROTECTED_DATA_NAME, Data).x(); }; + +#endif // INCLUDED_MUTEXPROTECTED 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 . + */ + +#ifndef INCLUDED_THREADFRONTIER +#define INCLUDED_THREADFRONTIER + +#include +#include + +/* + * 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 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 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 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 @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -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 @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -20,6 +20,7 @@ #include #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/components/CCmpObstruction.cpp =================================================================== --- source/simulation2/components/CCmpObstruction.cpp +++ source/simulation2/components/CCmpObstruction.cpp @@ -263,8 +263,8 @@ struct SerializeTag { - template - void operator()(S& serialize, const char* UNUSED(name), tag_t& value) + template + void operator()(S& serialize, const char* UNUSED(name), T& value) { serialize.NumberU32_Unbounded("tag", value.n); } Index: source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- source/simulation2/components/CCmpObstructionManager.cpp +++ source/simulation2/components/CCmpObstructionManager.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -34,9 +34,12 @@ #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/MathUtil.h" +#include "ps/CLogger.h" +#include "ps/MutexProtected.h" #include "ps/Profile.h" #include "renderer/Scene.h" -#include "ps/CLogger.h" + +#include // Externally, tags are opaque non-zero positive integers. // Internally, they are tagged (by shape) indexes into shape lists. @@ -79,7 +82,7 @@ */ struct SerializeUnitShape { - template + template void operator()(S& serialize, const char* UNUSED(name), UnitShape& value) const { serialize.NumberU32_Unbounded("entity", value.entity); @@ -96,7 +99,7 @@ */ struct SerializeStaticShape { - template + template void operator()(S& serialize, const char* UNUSED(name), StaticShape& value) const { serialize.NumberU32_Unbounded("entity", value.entity); @@ -128,12 +131,27 @@ bool m_DebugOverlayDirty; std::vector m_DebugOverlayLines; - SpatialSubdivision m_UnitSubdivision; - SpatialSubdivision m_StaticSubdivision; +#define PROTECTED_DATA_NAME MutexProtected + + using UnitShapeType = std::map; + using StaticShapeType = std::map; + + BEGIN_PROTECTED_DATA() + PROTECTED_DATA(SpatialSubdivision, UnitSubdivision); + PROTECTED_DATA(SpatialSubdivision, StaticSubdivision); + + // TODO: using std::map is a bit inefficient; is there a better way to store these? + PROTECTED_DATA(UnitShapeType, UnitShapes); + PROTECTED_DATA(StaticShapeType, StaticShapes); + END_PROTECTED_DATA(); + + PROTECTED_DATA_ACCESSOR(SpatialSubdivision, UnitSubdivision); + PROTECTED_DATA_ACCESSOR(SpatialSubdivision, StaticSubdivision); + PROTECTED_DATA_ACCESSOR(UnitShapeType, UnitShapes); + PROTECTED_DATA_ACCESSOR(StaticShapeType, StaticShapes); + +#undef PROTECTED_DATA_NAME - // TODO: using std::map is a bit inefficient; is there a better way to store these? - std::map m_UnitShapes; - std::map m_StaticShapes; u32 m_UnitShapeNext; // next allocated id u32 m_StaticShapeNext; @@ -180,13 +198,8 @@ template void SerializeCommon(S& serialize) { - SerializeSpatialSubdivision()(serialize, "unit subdiv", m_UnitSubdivision); - SerializeSpatialSubdivision()(serialize, "static subdiv", m_StaticSubdivision); - serialize.NumberFixed_Unbounded("max clearance", m_MaxClearance); - SerializeMap()(serialize, "unit shapes", m_UnitShapes); - SerializeMap()(serialize, "static shapes", m_StaticShapes); serialize.NumberU32_Unbounded("unit shape next", m_UnitShapeNext); serialize.NumberU32_Unbounded("static shape next", m_StaticShapeNext); @@ -203,6 +216,10 @@ { // TODO: this could perhaps be optimised by not storing all the obstructions, // and instead regenerating them from the other entities on Deserialize + SerializeSpatialSubdivision()(serialize, "unit subdiv", UnitSubdivision()); + SerializeSpatialSubdivision()(serialize, "static subdiv", StaticSubdivision()); + SerializeMap()(serialize, "unit shapes", UnitShapes()); + SerializeMap()(serialize, "static shapes", StaticShapes()); SerializeCommon(serialize); } @@ -211,6 +228,12 @@ { Init(paramNode); + MutexProtected::Lock lock(m_MutexProtectedData); + SerializeSpatialSubdivision()(deserialize, "unit subdiv", UnitSubdivision(lock)); + SerializeSpatialSubdivision()(deserialize, "static subdiv", StaticSubdivision(lock)); + SerializeMap()(deserialize, "unit shapes", UnitShapes(lock)); + SerializeMap()(deserialize, "static shapes", StaticShapes(lock)); + SerializeCommon(deserialize); m_UpdateInformations.dirtinessGrid = Grid(m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE, m_TerrainTiles*Pathfinding::NAVCELLS_PER_TILE); @@ -257,33 +280,36 @@ void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1) { + MutexProtected::Lock lock(m_MutexProtectedData); + // 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)); - m_StaticSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); + UnitSubdivision(lock).Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); + StaticSubdivision(lock).Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); - for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) + for (std::map::const_iterator it = UnitShapes(lock).begin(); it != UnitShapes(lock).end(); ++it) { CFixedVector2D center(it->second.x, it->second.z); CFixedVector2D halfSize(it->second.clearance, it->second.clearance); - m_UnitSubdivision.Add(it->first, center - halfSize, center + halfSize); + UnitSubdivision(lock).Add(it->first, center - halfSize, center + halfSize); } - for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) + for (std::map::const_iterator it = StaticShapes(lock).begin(); it != StaticShapes(lock).end(); ++it) { CFixedVector2D center(it->second.x, it->second.z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(it->second.u, it->second.v, CFixedVector2D(it->second.hw, it->second.hh)); - m_StaticSubdivision.Add(it->first, center - bbHalfSize, center + bbHalfSize); + StaticSubdivision(lock).Add(it->first, center - bbHalfSize, center + bbHalfSize); } } 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) { + MutexProtected::Lock lock(m_MutexProtectedData); UnitShape shape = { ent, x, z, clearance, flags, group }; u32 id = m_UnitShapeNext++; - m_UnitShapes[id] = shape; + UnitShapes(lock)[id] = shape; - m_UnitSubdivision.Add(id, CFixedVector2D(x - clearance, z - clearance), CFixedVector2D(x + clearance, z + clearance)); + UnitSubdivision(lock).Add(id, CFixedVector2D(x - clearance, z - clearance), CFixedVector2D(x + clearance, z + clearance)); MakeDirtyUnit(flags, id, shape); @@ -292,6 +318,7 @@ 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 */) { + MutexProtected::Lock lock(m_MutexProtectedData); fixed s, c; sincos_approx(a, s, c); CFixedVector2D u(c, -s); @@ -299,11 +326,11 @@ StaticShape shape = { ent, x, z, u, v, w/2, h/2, flags, group, group2 }; u32 id = m_StaticShapeNext++; - m_StaticShapes[id] = shape; + StaticShapes(lock)[id] = shape; CFixedVector2D center(x, z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(w/2, h/2)); - m_StaticSubdivision.Add(id, center - bbHalfSize, center + bbHalfSize); + StaticSubdivision(lock).Add(id, center - bbHalfSize, center + bbHalfSize); MakeDirtyStatic(flags, id, shape); @@ -331,15 +358,16 @@ virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a) { + MutexProtected::Lock lock(m_MutexProtectedData); ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = UnitShapes(lock)[TAG_TO_INDEX(tag)]; MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region - m_UnitSubdivision.Move(TAG_TO_INDEX(tag), + UnitSubdivision(lock).Move(TAG_TO_INDEX(tag), CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance), CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance), CFixedVector2D(x - shape.clearance, z - shape.clearance), @@ -357,13 +385,13 @@ CFixedVector2D u(c, -s); CFixedVector2D v(s, c); - StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + StaticShape& shape = StaticShapes(lock)[TAG_TO_INDEX(tag)]; MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region CFixedVector2D fromBbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh)); CFixedVector2D toBbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(shape.hw, shape.hh)); - m_StaticSubdivision.Move(TAG_TO_INDEX(tag), + StaticSubdivision(lock).Move(TAG_TO_INDEX(tag), CFixedVector2D(shape.x, shape.z) - fromBbHalfSize, CFixedVector2D(shape.x, shape.z) + fromBbHalfSize, CFixedVector2D(x, z) - toBbHalfSize, @@ -380,11 +408,12 @@ virtual void SetUnitMovingFlag(tag_t tag, bool moving) { + MutexProtected::Lock lock(m_MutexProtectedData); ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag)); if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = UnitShapes(lock)[TAG_TO_INDEX(tag)]; if (moving) shape.flags |= FLAG_MOVING; else @@ -396,22 +425,24 @@ virtual void SetUnitControlGroup(tag_t tag, entity_id_t group) { + MutexProtected::Lock lock(m_MutexProtectedData); ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag)); if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = UnitShapes(lock)[TAG_TO_INDEX(tag)]; shape.group = group; } } virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2) { + MutexProtected::Lock lock(m_MutexProtectedData); ENSURE(TAG_IS_VALID(tag) && TAG_IS_STATIC(tag)); if (TAG_IS_STATIC(tag)) { - StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + StaticShape& shape = StaticShapes(lock)[TAG_TO_INDEX(tag)]; shape.group = group; shape.group2 = group2; } @@ -419,30 +450,31 @@ virtual void RemoveShape(tag_t tag) { + MutexProtected::Lock lock(m_MutexProtectedData); ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; - m_UnitSubdivision.Remove(TAG_TO_INDEX(tag), + UnitShape& shape = UnitShapes(lock)[TAG_TO_INDEX(tag)]; + UnitSubdivision(lock).Remove(TAG_TO_INDEX(tag), CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance), CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance)); MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); - m_UnitShapes.erase(TAG_TO_INDEX(tag)); + UnitShapes(lock).erase(TAG_TO_INDEX(tag)); } else { - StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + StaticShape& shape = StaticShapes(lock)[TAG_TO_INDEX(tag)]; CFixedVector2D center(shape.x, shape.z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh)); - m_StaticSubdivision.Remove(TAG_TO_INDEX(tag), center - bbHalfSize, center + bbHalfSize); + StaticSubdivision(lock).Remove(TAG_TO_INDEX(tag), center - bbHalfSize, center + bbHalfSize); MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); - m_StaticShapes.erase(TAG_TO_INDEX(tag)); + StaticShapes(lock).erase(TAG_TO_INDEX(tag)); } } @@ -452,7 +484,7 @@ if (TAG_IS_UNIT(tag)) { - const UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag)); + const UnitShape& shape = UnitShapes().at(TAG_TO_INDEX(tag)); CFixedVector2D u(entity_pos_t::FromInt(1), entity_pos_t::Zero()); CFixedVector2D v(entity_pos_t::Zero(), entity_pos_t::FromInt(1)); ObstructionSquare o = { shape.x, shape.z, u, v, shape.clearance, shape.clearance }; @@ -460,7 +492,7 @@ } else { - const StaticShape& shape = m_StaticShapes.at(TAG_TO_INDEX(tag)); + const StaticShape& shape = StaticShapes().at(TAG_TO_INDEX(tag)); ObstructionSquare o = { shape.x, shape.z, shape.u, shape.v, shape.hw, shape.hh }; return o; } @@ -489,6 +521,16 @@ virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false) const; virtual void GetStaticObstructionsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter) const; + virtual void LockObstructions() + { + m_MutexProtectedData.m_LockShapesMutex.lock(); + } + + virtual void UnlockObstructions() + { + m_MutexProtectedData.m_LockShapesMutex.unlock(); + } + virtual void SetPassabilityCircular(bool enabled) { m_PassabilityCircular = enabled; @@ -594,13 +636,13 @@ CFixedVector2D expand(m_MaxClearance, m_MaxClearance); std::vector staticsNear; - m_StaticSubdivision.GetInRange(staticsNear, center - hbox - expand*2, center + hbox + expand*2); + StaticSubdivision().GetInRange(staticsNear, center - hbox - expand*2, center + hbox + expand*2); for (u32& staticId : staticsNear) if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end()) m_DirtyStaticShapes.push_back(staticId); std::vector unitsNear; - m_UnitSubdivision.GetInRange(unitsNear, center - hbox - expand*2, center + hbox + expand*2); + UnitSubdivision().GetInRange(unitsNear, center - hbox - expand*2, center + hbox + expand*2); for (u32& unitId : unitsNear) if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end()) m_DirtyUnitShapes.push_back(unitId); @@ -632,13 +674,13 @@ CFixedVector2D center(shape.x, shape.z); std::vector staticsNear; - m_StaticSubdivision.GetNear(staticsNear, center, shape.clearance + m_MaxClearance*2); + StaticSubdivision().GetNear(staticsNear, center, shape.clearance + m_MaxClearance*2); for (u32& staticId : staticsNear) if (std::find(m_DirtyStaticShapes.begin(), m_DirtyStaticShapes.end(), staticId) == m_DirtyStaticShapes.end()) m_DirtyStaticShapes.push_back(staticId); std::vector unitsNear; - m_UnitSubdivision.GetNear(unitsNear, center, shape.clearance + m_MaxClearance*2); + UnitSubdivision().GetNear(unitsNear, center, shape.clearance + m_MaxClearance*2); for (u32& unitId : unitsNear) if (std::find(m_DirtyUnitShapes.begin(), m_DirtyUnitShapes.end(), unitId) == m_DirtyUnitShapes.end()) m_DirtyUnitShapes.push_back(unitId); @@ -871,11 +913,11 @@ unitUnitRadius -= entity_pos_t::FromInt(1)/2; std::vector unitShapes; - m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); + UnitSubdivision().GetInRange(unitShapes, posMin, posMax); for (const entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); - ENSURE(it != m_UnitShapes.end()); + std::map::const_iterator it = UnitShapes().find(shape); + ENSURE(it != UnitShapes().end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; @@ -887,11 +929,11 @@ } std::vector staticShapes; - m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); + StaticSubdivision().GetInRange(staticShapes, posMin, posMax); for (const entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); - ENSURE(it != m_StaticShapes.end()); + std::map::const_iterator it = StaticShapes().find(shape); + ENSURE(it != StaticShapes().end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; @@ -939,11 +981,11 @@ CFixedVector2D posMax(x + bbHalfWidth, z + bbHalfHeight); std::vector unitShapes; - m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); + UnitSubdivision().GetInRange(unitShapes, posMin, posMax); for (entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); - ENSURE(it != m_UnitShapes.end()); + std::map::const_iterator it = UnitShapes().find(shape); + ENSURE(it != UnitShapes().end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; @@ -960,11 +1002,11 @@ } std::vector staticShapes; - m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); + StaticSubdivision().GetInRange(staticShapes, posMin, posMax); for (entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); - ENSURE(it != m_StaticShapes.end()); + std::map::const_iterator it = StaticShapes().find(shape); + ENSURE(it != StaticShapes().end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; @@ -1006,11 +1048,11 @@ CFixedVector2D posMax(x + clearance, z + clearance); std::vector unitShapes; - m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); - for (const entity_id_t& shape : unitShapes) + UnitSubdivision().GetInRange(unitShapes, posMin, posMax); + for (entity_id_t shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); - ENSURE(it != m_UnitShapes.end()); + std::map::const_iterator it = UnitShapes().find(shape); + ENSURE(it != UnitShapes().end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; @@ -1031,11 +1073,11 @@ } std::vector staticShapes; - m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); - for (const entity_id_t& shape : staticShapes) + StaticSubdivision().GetInRange(staticShapes, posMin, posMax); + for (entity_id_t shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); - ENSURE(it != m_StaticShapes.end()); + std::map::const_iterator it = StaticShapes().find(shape); + ENSURE(it != StaticShapes().end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; @@ -1103,7 +1145,7 @@ void CCmpObstructionManager::RasterizeHelper(Grid& grid, ICmpObstructionManager::flags_t requireMask, bool fullUpdate, pass_class_t appliedMask, entity_pos_t clearance) const { - for (auto& pair : m_StaticShapes) + for (const std::pair& pair : StaticShapes()) { const StaticShape& shape = pair.second; if (!(shape.flags & requireMask)) @@ -1127,7 +1169,7 @@ } } - for (auto& pair : m_UnitShapes) + for (const std::pair& pair : UnitShapes()) { if (!(pair.second.flags & requireMask)) continue; @@ -1160,11 +1202,11 @@ ENSURE(x0 <= x1 && z0 <= z1); std::vector unitShapes; - m_UnitSubdivision.GetInRange(unitShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); - for (entity_id_t& unitShape : unitShapes) + UnitSubdivision().GetInRange(unitShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); + for (entity_id_t unitShape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(unitShape); - ENSURE(it != m_UnitShapes.end()); + std::map::const_iterator it = UnitShapes().find(unitShape); + ENSURE(it != UnitShapes().end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) continue; @@ -1188,11 +1230,11 @@ ENSURE(x0 <= x1 && z0 <= z1); std::vector staticShapes; - m_StaticSubdivision.GetInRange(staticShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); - for (entity_id_t& staticShape : staticShapes) + StaticSubdivision().GetInRange(staticShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); + for (entity_id_t staticShape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(staticShape); - ENSURE(it != m_StaticShapes.end()); + std::map::const_iterator it = StaticShapes().find(staticShape); + ENSURE(it != StaticShapes().end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) continue; @@ -1222,14 +1264,14 @@ CFixedVector2D expandedBox = Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh)) + CFixedVector2D(m_MaxClearance, m_MaxClearance); - m_UnitSubdivision.GetInRange(unitShapes, center - expandedBox, center + expandedBox); + UnitSubdivision().GetInRange(unitShapes, center - expandedBox, center + expandedBox); std::map rasterizedRects; - for (const u32& unitShape : unitShapes) + for (u32 unitShape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(unitShape); - ENSURE(it != m_UnitShapes.end()); + std::map::const_iterator it = UnitShapes().find(unitShape); + ENSURE(it != UnitShapes().end()); const UnitShape& shape = it->second; @@ -1277,12 +1319,12 @@ std::vector staticShapes; CFixedVector2D center(square.x, square.z); CFixedVector2D expandedBox = Geometry::GetHalfBoundingBox(square.u, square.v, CFixedVector2D(square.hw, square.hh)); - m_StaticSubdivision.GetInRange(staticShapes, center - expandedBox, center + expandedBox); + StaticSubdivision().GetInRange(staticShapes, center - expandedBox, center + expandedBox); - for (const u32& staticShape : staticShapes) + for (u32 staticShape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(staticShape); - ENSURE(it != m_StaticShapes.end()); + std::map::const_iterator it = StaticShapes().find(staticShape); + ENSURE(it != StaticShapes().end()); const StaticShape& shape = it->second; @@ -1325,14 +1367,14 @@ (m_WorldX1-m_WorldX0).ToFloat(), (m_WorldZ1-m_WorldZ0).ToFloat(), 0, m_DebugOverlayLines.back(), true); - for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) + for (std::map::const_iterator it = UnitShapes().begin(); it != UnitShapes().end(); ++it) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = ((it->second.flags & FLAG_MOVING) ? movingColor : defaultColor); SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.clearance.ToFloat(), it->second.clearance.ToFloat(), 0, m_DebugOverlayLines.back(), true); } - for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) + for (std::map::const_iterator it = StaticShapes().begin(); it != StaticShapes().end(); ++it) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = defaultColor; 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" @@ -68,21 +69,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 +83,35 @@ 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(); + + m_PathfinderConditionVariable.notify_all(); m_Workers.clear(); SetDebugOverlay(false); // cleans up memory @@ -115,7 +123,7 @@ struct SerializeLongRequest { - template + template void operator()(S& serialize, const char* UNUSED(name), LongPathRequest& value) { serialize.NumberU32_Unbounded("ticket", value.ticket); @@ -129,7 +137,7 @@ struct SerializeShortRequest { - template + template void operator()(S& serialize, const char* UNUSED(name), ShortPathRequest& value) { serialize.NumberU32_Unbounded("ticket", value.ticket); @@ -732,7 +740,28 @@ // 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()); + WaitForWork(pathfinder); +} template void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector&, ssize_t) @@ -750,6 +779,32 @@ 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 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()) @@ -806,6 +861,16 @@ m_ShortPathRequests.clear(); m_LongPathRequests.clear(); + // We may now clear existing requests. + m_ProcessingMoves = false; + m_ShortPathRequests.clear(); + m_LongPathRequests.clear(); + + // 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(); + // WARNING: the order in which moves are pulled must be consistent when using 1 or n workers. // We fetch in the same order we inserted in, but we push moves backwards, so this works. std::vector results; @@ -815,6 +880,13 @@ worker.m_Results.clear(); } + // Unlock obstructions before sending messages. + if(m_UseThreading) + { + CmpPtr cmpObstructionManager(GetSystemEntity()); + cmpObstructionManager->UnlockObstructions(); + } + { PROFILE2("PostMessages"); for (PathResult& path : results) @@ -833,8 +905,23 @@ PushRequestsToWorkers(longRequests); PushRequestsToWorkers(shortRequests); - for (PathfinderWorker& worker : m_Workers) - worker.Work(*this); + m_PathfinderFrontier.Reset(); + + if (m_UseThreading) + { + CmpPtr cmpObstructionManager(GetSystemEntity()); + cmpObstructionManager->LockObstructions(); + + 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 @@ -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 + class HierarchicalPathfinder; class LongPathfinder; @@ -65,19 +68,55 @@ 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 void PushRequests(std::vector& from, ssize_t amount); // Stores our results, the main thread will fetch this. std::vector m_Results; + std::thread m_Thread; + + std::atomic m_Kill; + std::atomic m_Computing; + std::vector m_LongRequests; std::vector m_ShortRequests; }; @@ -130,8 +169,15 @@ std::unique_ptr m_PathfinderHier; std::unique_ptr m_LongPathfinder; - // Workers process pathing requests. + // Worker process pathing requests. std::vector m_Workers; + bool m_UseThreading = false; + mutable std::mutex m_PathfinderMutex; + mutable std::condition_variable m_PathfinderConditionVariable; + mutable ThreadFrontier m_PathfinderFrontier; + // For now, we cannot push new requests while processing moves. + // If this is ever useful, a double-buffered queue system might be needed to still preserve serialization capabilities. + bool m_ProcessingMoves = false; AtlasOverlay* m_AtlasOverlay; Index: source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- source/simulation2/components/CCmpRangeManager.cpp +++ source/simulation2/components/CCmpRangeManager.cpp @@ -240,8 +240,8 @@ */ struct SerializeQuery { - template - void Common(S& serialize, const char* UNUSED(name), Query& value) + template + void Common(S& serialize, const char* UNUSED(name), T& value) { serialize.Bool("enabled", value.enabled); serialize.Bool("parabolic",value.parabolic); @@ -254,7 +254,7 @@ serialize.NumberU8_Unbounded("flagsMask", value.flagsMask); } - void operator()(ISerializer& serialize, const char* name, Query& value, const CSimContext& UNUSED(context)) + void operator()(ISerializer& serialize, const char* name, const Query& value, const CSimContext& UNUSED(context)) { Common(serialize, name, value); Index: source/simulation2/components/ICmpObstructionManager.h =================================================================== --- source/simulation2/components/ICmpObstructionManager.h +++ source/simulation2/components/ICmpObstructionManager.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -310,6 +310,13 @@ */ virtual void GetUnitsOnObstruction(const ObstructionSquare& square, std::vector& out, const IObstructionTestFilter& filter, bool strict = false) const = 0; + /** + * Prevent changes to the shapes - calls to GetObstructions will return the same results. + * (used for garanteeing that the simulation isn't changed when computing paths asynchronously). + */ + virtual void LockObstructions() = 0; + virtual void UnlockObstructions() = 0; + /** * Get the obstruction square representing the given shape. * @param tag tag of shape (must be valid) 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 #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 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 > m_JumpPointCache; + + static thread_local std::map > m_JumpPointCache; }; /** Index: source/simulation2/helpers/LongPathfinder.cpp =================================================================== --- source/simulation2/helpers/LongPathfinder.cpp +++ source/simulation2/helpers/LongPathfinder.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -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 > 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/helpers/Spatial.h =================================================================== --- source/simulation2/helpers/Spatial.h +++ source/simulation2/helpers/Spatial.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016 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 @@ -318,7 +318,7 @@ */ struct SerializeSpatialSubdivision { - void operator()(ISerializer& serialize, const char* UNUSED(name), SpatialSubdivision& value) + void operator()(ISerializer& serialize, const char* UNUSED(name), const SpatialSubdivision& value) { serialize.NumberFixed_Unbounded("div size", value.m_DivisionSize); serialize.NumberU32_Unbounded("divs w", value.m_DivisionsW); Index: source/simulation2/helpers/VertexPathfinder.h =================================================================== --- source/simulation2/helpers/VertexPathfinder.h +++ source/simulation2/helpers/VertexPathfinder.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -96,25 +96,25 @@ const u16& m_MapSize; Grid* const & m_TerrainOnlyGrid; - std::atomic m_DebugOverlay; - mutable std::vector m_DebugOverlayShortPathLines; + bool m_DebugOverlay; + static thread_local std::vector m_DebugOverlayShortPathLines; + static thread_local std::mutex m_DebugMutex; // These vectors are expensive to recreate on every call, so we cache them here. - // They are made mutable to allow using them in the otherwise const ComputeShortPath. - mutable std::vector m_EdgesUnaligned; - mutable std::vector m_EdgesLeft; - mutable std::vector m_EdgesRight; - mutable std::vector m_EdgesBottom; - mutable std::vector m_EdgesTop; + static thread_local std::vector m_EdgesUnaligned; + static thread_local std::vector m_EdgesLeft; + static thread_local std::vector m_EdgesRight; + static thread_local std::vector m_EdgesBottom; + static thread_local std::vector m_EdgesTop; // List of obstruction vertexes (plus start/end points); we'll try to find paths through // the graph defined by these vertexes. - mutable std::vector m_Vertexes; + static thread_local std::vector m_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.) - mutable std::vector m_Edges; - mutable std::vector m_EdgeSquares; // Axis-aligned squares; equivalent to 4 edges. + static thread_local std::vector m_Edges; + static thread_local std::vector m_EdgeSquares; // Axis-aligned squares; equivalent to 4 edges. }; #endif // INCLUDED_VERTEXPATHFINDER Index: source/simulation2/helpers/VertexPathfinder.cpp =================================================================== --- source/simulation2/helpers/VertexPathfinder.cpp +++ source/simulation2/helpers/VertexPathfinder.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 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 @@ -43,6 +43,18 @@ #include "simulation2/helpers/Render.h" #include "simulation2/system/SimContext.h" + +thread_local std::vector VertexPathfinder::m_DebugOverlayShortPathLines; +thread_local std::mutex VertexPathfinder::m_DebugMutex; +thread_local std::vector VertexPathfinder::m_EdgesUnaligned; +thread_local std::vector VertexPathfinder::m_EdgesLeft; +thread_local std::vector VertexPathfinder::m_EdgesRight; +thread_local std::vector VertexPathfinder::m_EdgesBottom; +thread_local std::vector VertexPathfinder::m_EdgesTop; +thread_local std::vector VertexPathfinder::m_Vertexes; +thread_local std::vector VertexPathfinder::m_Edges; +thread_local std::vector VertexPathfinder::m_EdgeSquares; + /* Quadrant optimisation: * (loosely based on GPG2 "Optimizing Points-of-Visibility Pathfinding") * @@ -853,6 +865,7 @@ { if (!m_DebugOverlay) return; + std::lock_guard lock(m_DebugMutex); m_DebugOverlayShortPathLines.clear(); @@ -886,6 +899,7 @@ { if (!m_DebugOverlay) return; + std::lock_guard lock(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 @@ -983,6 +997,7 @@ if (!m_DebugOverlay) return; + std::lock_guard lock(m_DebugMutex); for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i) collector.Submit(&m_DebugOverlayShortPathLines[i]); } Index: source/simulation2/serialization/SerializeTemplates.h =================================================================== --- source/simulation2/serialization/SerializeTemplates.h +++ source/simulation2/serialization/SerializeTemplates.h @@ -52,7 +52,7 @@ struct SerializeVector { template - void operator()(ISerializer& serialize, const char* name, std::vector& value) + void operator()(ISerializer& serialize, const char* name, const std::vector& value) { size_t len = value.size(); serialize.NumberU32_Unbounded("length", (u32)len); @@ -106,11 +106,11 @@ struct SerializeMap { template - void operator()(ISerializer& serialize, const char* UNUSED(name), std::map& value) + void operator()(ISerializer& serialize, const char* UNUSED(name), const std::map& value) { size_t len = value.size(); serialize.NumberU32_Unbounded("length", (u32)len); - for (typename std::map::iterator it = value.begin(); it != value.end(); ++it) + for (typename std::map::const_iterator it = value.begin(); it != value.end(); ++it) { KS()(serialize, "key", it->first); VS()(serialize, "value", it->second); @@ -118,11 +118,11 @@ } template - void operator()(ISerializer& serialize, const char* UNUSED(name), std::map& value, C& context) + void operator()(ISerializer& serialize, const char* UNUSED(name), const std::map& value, C& context) { size_t len = value.size(); serialize.NumberU32_Unbounded("length", (u32)len); - for (typename std::map::iterator it = value.begin(); it != value.end(); ++it) + for (typename std::map::const_iterator it = value.begin(); it != value.end(); ++it) { KS()(serialize, "key", it->first); VS()(serialize, "value", it->second, context); @@ -295,10 +295,10 @@ struct SerializeGoal { - template + template void operator()(S& serialize, const char* UNUSED(name), PathGoal& value) { - SerializeU8_Enum()(serialize, "type", value.type); + SerializeU8_Enum()(serialize, "type", value.type); serialize.NumberFixed_Unbounded("goal x", value.x); serialize.NumberFixed_Unbounded("goal z", value.z); serialize.NumberFixed_Unbounded("goal u x", value.u.X);