Index: ps/trunk/source/simulation2/Simulation2.cpp =================================================================== --- ps/trunk/source/simulation2/Simulation2.cpp (revision 25255) +++ ps/trunk/source/simulation2/Simulation2.cpp (revision 25256) @@ -1,995 +1,995 @@ /* Copyright (C) 2021 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 . */ #include "precompiled.h" #include "Simulation2.h" #include "scriptinterface/ScriptContext.h" #include "scriptinterface/ScriptInterface.h" #include "simulation2/MessageTypes.h" #include "simulation2/system/ComponentManager.h" #include "simulation2/system/ParamNode.h" #include "simulation2/system/SimContext.h" #include "simulation2/components/ICmpAIManager.h" #include "simulation2/components/ICmpCommandQueue.h" #include "simulation2/components/ICmpTemplateManager.h" #include "graphics/MapReader.h" #include "graphics/Terrain.h" #include "lib/timer.h" #include "lib/file/vfs/vfs_util.h" #include "maths/MathUtil.h" #include "ps/CLogger.h" #include "ps/ConfigDB.h" #include "ps/Filesystem.h" #include "ps/Loader.h" #include "ps/Profile.h" #include "ps/Pyrogenesis.h" #include "ps/Util.h" #include "ps/XML/Xeromyces.h" #include #include #include class CSimulation2Impl { public: CSimulation2Impl(CUnitManager* unitManager, shared_ptr cx, CTerrain* terrain) : m_SimContext(), m_ComponentManager(m_SimContext, cx), m_EnableOOSLog(false), m_EnableSerializationTest(false), m_RejoinTestTurn(-1), m_TestingRejoin(false), m_MapSettings(cx->GetGeneralJSContext()), m_InitAttributes(cx->GetGeneralJSContext()) { m_SimContext.m_UnitManager = unitManager; m_SimContext.m_Terrain = terrain; m_ComponentManager.LoadComponentTypes(); RegisterFileReloadFunc(ReloadChangedFileCB, this); // Tests won't have config initialised if (CConfigDB::IsInitialised()) { CFG_GET_VAL("ooslog", m_EnableOOSLog); CFG_GET_VAL("serializationtest", m_EnableSerializationTest); CFG_GET_VAL("rejointest", m_RejoinTestTurn); if (m_RejoinTestTurn < 0) // Handle bogus values of the arg m_RejoinTestTurn = -1; } if (m_EnableOOSLog) { m_OOSLogPath = createDateIndexSubdirectory(psLogDir() / "oos_logs"); debug_printf("Writing ooslogs to %s\n", m_OOSLogPath.string8().c_str()); } } ~CSimulation2Impl() { UnregisterFileReloadFunc(ReloadChangedFileCB, this); } void ResetState(bool skipScriptedComponents, bool skipAI) { m_DeltaTime = 0.0; m_LastFrameOffset = 0.0f; m_TurnNumber = 0; ResetComponentState(m_ComponentManager, skipScriptedComponents, skipAI); } static void ResetComponentState(CComponentManager& componentManager, bool skipScriptedComponents, bool skipAI) { componentManager.ResetState(); componentManager.InitSystemEntity(); componentManager.AddSystemComponents(skipScriptedComponents, skipAI); } static bool LoadDefaultScripts(CComponentManager& componentManager, std::set* loadedScripts); static bool LoadScripts(CComponentManager& componentManager, std::set* loadedScripts, const VfsPath& path); static bool LoadTriggerScripts(CComponentManager& componentManager, JS::HandleValue mapSettings, std::set* loadedScripts); Status ReloadChangedFile(const VfsPath& path); static Status ReloadChangedFileCB(void* param, const VfsPath& path) { return static_cast(param)->ReloadChangedFile(path); } int ProgressiveLoad(); void Update(int turnLength, const std::vector& commands); static void UpdateComponents(CSimContext& simContext, fixed turnLengthFixed, const std::vector& commands); void Interpolate(float simFrameLength, float frameOffset, float realFrameLength); void DumpState(); CSimContext m_SimContext; CComponentManager m_ComponentManager; double m_DeltaTime; float m_LastFrameOffset; std::string m_StartupScript; JS::PersistentRootedValue m_InitAttributes; JS::PersistentRootedValue m_MapSettings; std::set m_LoadedScripts; uint32_t m_TurnNumber; bool m_EnableOOSLog; OsPath m_OOSLogPath; // Functions and data for the serialization test mode: (see Update() for relevant comments) bool m_EnableSerializationTest; int m_RejoinTestTurn; bool m_TestingRejoin; // Secondary simulation (NB: order matters for destruction). std::unique_ptr m_SecondaryComponentManager; std::unique_ptr m_SecondaryTerrain; std::unique_ptr m_SecondaryContext; std::unique_ptr> m_SecondaryLoadedScripts; struct SerializationTestState { std::stringstream state; std::stringstream debug; std::string hash; }; void DumpSerializationTestState(SerializationTestState& state, const OsPath& path, const OsPath::String& suffix); void ReportSerializationFailure( SerializationTestState* primaryStateBefore, SerializationTestState* primaryStateAfter, SerializationTestState* secondaryStateBefore, SerializationTestState* secondaryStateAfter); void InitRNGSeedSimulation(); void InitRNGSeedAI(); static std::vector CloneCommandsFromOtherCompartment(const ScriptInterface& oldScript, const ScriptInterface& newScript, const std::vector& commands) { std::vector newCommands; newCommands.reserve(commands.size()); ScriptRequest rqNew(newScript); for (const SimulationCommand& command : commands) { JS::RootedValue tmpCommand(rqNew.cx, newScript.CloneValueFromOtherCompartment(oldScript, command.data)); newScript.FreezeObject(tmpCommand, true); SimulationCommand cmd(command.player, rqNew.cx, tmpCommand); newCommands.emplace_back(std::move(cmd)); } return newCommands; } }; bool CSimulation2Impl::LoadDefaultScripts(CComponentManager& componentManager, std::set* loadedScripts) { return ( LoadScripts(componentManager, loadedScripts, L"simulation/components/interfaces/") && LoadScripts(componentManager, loadedScripts, L"simulation/helpers/") && LoadScripts(componentManager, loadedScripts, L"simulation/components/") ); } bool CSimulation2Impl::LoadScripts(CComponentManager& componentManager, std::set* loadedScripts, const VfsPath& path) { VfsPaths pathnames; if (vfs::GetPathnames(g_VFS, path, L"*.js", pathnames) < 0) return false; bool ok = true; for (const VfsPath& scriptPath : pathnames) { if (loadedScripts) loadedScripts->insert(scriptPath); LOGMESSAGE("Loading simulation script '%s'", scriptPath.string8()); if (!componentManager.LoadScript(scriptPath)) ok = false; } return ok; } bool CSimulation2Impl::LoadTriggerScripts(CComponentManager& componentManager, JS::HandleValue mapSettings, std::set* loadedScripts) { bool ok = true; if (componentManager.GetScriptInterface().HasProperty(mapSettings, "TriggerScripts")) { std::vector scriptNames; componentManager.GetScriptInterface().GetProperty(mapSettings, "TriggerScripts", scriptNames); for (const std::string& triggerScript : scriptNames) { std::string scriptName = "maps/" + triggerScript; if (loadedScripts) { if (loadedScripts->find(scriptName) != loadedScripts->end()) continue; loadedScripts->insert(scriptName); } LOGMESSAGE("Loading trigger script '%s'", scriptName.c_str()); if (!componentManager.LoadScript(scriptName.data())) ok = false; } } return ok; } Status CSimulation2Impl::ReloadChangedFile(const VfsPath& path) { // Ignore if this file wasn't loaded as a script // (TODO: Maybe we ought to load in any new .js files that are created in the right directories) if (m_LoadedScripts.find(path) == m_LoadedScripts.end()) return INFO::OK; // If the file doesn't exist (e.g. it was deleted), don't bother loading it since that'll give an error message. // (Also don't bother trying to 'unload' it from the component manager, because that's not possible) if (!VfsFileExists(path)) return INFO::OK; LOGMESSAGE("Reloading simulation script '%s'", path.string8()); if (!m_ComponentManager.LoadScript(path, true)) return ERR::FAIL; return INFO::OK; } int CSimulation2Impl::ProgressiveLoad() { // yield after this time is reached. balances increased progress bar // smoothness vs. slowing down loading. const double end_time = timer_Time() + 200e-3; int ret; do { bool progressed = false; int total = 0; int progress = 0; CMessageProgressiveLoad msg(&progressed, &total, &progress); m_ComponentManager.BroadcastMessage(msg); if (!progressed || total == 0) return 0; // we have nothing left to load ret = Clamp(100*progress / total, 1, 100); } while (timer_Time() < end_time); return ret; } void CSimulation2Impl::DumpSerializationTestState(SerializationTestState& state, const OsPath& path, const OsPath::String& suffix) { if (!state.hash.empty()) { std::ofstream file (OsString(path / (L"hash." + suffix)).c_str(), std::ofstream::out | std::ofstream::trunc); file << Hexify(state.hash); } if (!state.debug.str().empty()) { std::ofstream file (OsString(path / (L"debug." + suffix)).c_str(), std::ofstream::out | std::ofstream::trunc); file << state.debug.str(); } if (!state.state.str().empty()) { std::ofstream file (OsString(path / (L"state." + suffix)).c_str(), std::ofstream::out | std::ofstream::trunc | std::ofstream::binary); file << state.state.str(); } } void CSimulation2Impl::ReportSerializationFailure( SerializationTestState* primaryStateBefore, SerializationTestState* primaryStateAfter, SerializationTestState* secondaryStateBefore, SerializationTestState* secondaryStateAfter) { const OsPath path = createDateIndexSubdirectory(psLogDir() / "serializationtest"); debug_printf("Writing serializationtest-data to %s\n", path.string8().c_str()); // Clean up obsolete files from previous runs wunlink(path / "hash.before.a"); wunlink(path / "hash.before.b"); wunlink(path / "debug.before.a"); wunlink(path / "debug.before.b"); wunlink(path / "state.before.a"); wunlink(path / "state.before.b"); wunlink(path / "hash.after.a"); wunlink(path / "hash.after.b"); wunlink(path / "debug.after.a"); wunlink(path / "debug.after.b"); wunlink(path / "state.after.a"); wunlink(path / "state.after.b"); if (primaryStateBefore) DumpSerializationTestState(*primaryStateBefore, path, L"before.a"); if (primaryStateAfter) DumpSerializationTestState(*primaryStateAfter, path, L"after.a"); if (secondaryStateBefore) DumpSerializationTestState(*secondaryStateBefore, path, L"before.b"); if (secondaryStateAfter) DumpSerializationTestState(*secondaryStateAfter, path, L"after.b"); debug_warn(L"Serialization test failure"); } void CSimulation2Impl::InitRNGSeedSimulation() { u32 seed = 0; if (!m_ComponentManager.GetScriptInterface().HasProperty(m_MapSettings, "Seed") || !m_ComponentManager.GetScriptInterface().GetProperty(m_MapSettings, "Seed", seed)) LOGWARNING("CSimulation2Impl::InitRNGSeedSimulation: No seed value specified - using %d", seed); m_ComponentManager.SetRNGSeed(seed); } void CSimulation2Impl::InitRNGSeedAI() { u32 seed = 0; if (!m_ComponentManager.GetScriptInterface().HasProperty(m_MapSettings, "AISeed") || !m_ComponentManager.GetScriptInterface().GetProperty(m_MapSettings, "AISeed", seed)) LOGWARNING("CSimulation2Impl::InitRNGSeedAI: No seed value specified - using %d", seed); CmpPtr cmpAIManager(m_SimContext, SYSTEM_ENTITY); if (cmpAIManager) cmpAIManager->SetRNGSeed(seed); } void CSimulation2Impl::Update(int turnLength, const std::vector& commands) { PROFILE3("sim update"); PROFILE2_ATTR("turn %d", (int)m_TurnNumber); fixed turnLengthFixed = fixed::FromInt(turnLength) / 1000; /* * In serialization test mode, we save the original (primary) simulation state before each turn update. * We run the update, then load the saved state into a secondary context. * We serialize that again and compare to the original serialization (to check that * serialize->deserialize->serialize is equivalent to serialize). * Then we run the update on the secondary context, and check that its new serialized * state matches the primary context after the update (to check that the simulation doesn't depend * on anything that's not serialized). * * In rejoin test mode, the secondary simulation is initialized from serialized data at turn N, then both * simulations run independantly while comparing their states each turn. This is way faster than a * complete serialization test and allows us to reproduce OOSes on rejoin. */ const bool serializationTestDebugDump = false; // set true to save human-readable state dumps before an error is detected, for debugging (but slow) const bool serializationTestHash = true; // set true to save and compare hash of state SerializationTestState primaryStateBefore; const ScriptInterface& scriptInterface = m_ComponentManager.GetScriptInterface(); const bool startRejoinTest = (int64_t) m_RejoinTestTurn == m_TurnNumber; if (startRejoinTest) m_TestingRejoin = true; if (m_EnableSerializationTest || m_TestingRejoin) { ENSURE(m_ComponentManager.SerializeState(primaryStateBefore.state)); if (serializationTestDebugDump) ENSURE(m_ComponentManager.DumpDebugState(primaryStateBefore.debug, false)); if (serializationTestHash) ENSURE(m_ComponentManager.ComputeStateHash(primaryStateBefore.hash, false)); } UpdateComponents(m_SimContext, turnLengthFixed, commands); if (m_EnableSerializationTest || startRejoinTest) { if (startRejoinTest) debug_printf("Initializing the secondary simulation\n"); m_SecondaryTerrain = std::make_unique(); m_SecondaryContext = std::make_unique(); m_SecondaryContext->m_Terrain = m_SecondaryTerrain.get(); m_SecondaryComponentManager = std::make_unique(*m_SecondaryContext, scriptInterface.GetContext()); m_SecondaryComponentManager->LoadComponentTypes(); m_SecondaryLoadedScripts = std::make_unique>(); ENSURE(LoadDefaultScripts(*m_SecondaryComponentManager, m_SecondaryLoadedScripts.get())); ResetComponentState(*m_SecondaryComponentManager, false, false); // Load the trigger scripts after we have loaded the simulation. { ScriptRequest rq2(m_SecondaryComponentManager->GetScriptInterface()); JS::RootedValue mapSettingsCloned(rq2.cx, m_SecondaryComponentManager->GetScriptInterface().CloneValueFromOtherCompartment(scriptInterface, m_MapSettings)); ENSURE(LoadTriggerScripts(*m_SecondaryComponentManager, mapSettingsCloned, m_SecondaryLoadedScripts.get())); } // Load the map into the secondary simulation LDR_BeginRegistering(); std::unique_ptr mapReader = std::make_unique(); std::string mapType; scriptInterface.GetProperty(m_InitAttributes, "mapType", mapType); if (mapType == "random") { // TODO: support random map scripts debug_warn(L"Serialization test mode does not support random maps"); } else { std::wstring mapFile; scriptInterface.GetProperty(m_InitAttributes, "map", mapFile); VfsPath mapfilename = VfsPath(mapFile).ChangeExtension(L".pmp"); mapReader->LoadMap(mapfilename, *scriptInterface.GetContext(), JS::UndefinedHandleValue, m_SecondaryTerrain.get(), NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, m_SecondaryContext.get(), INVALID_PLAYER, true); // throws exception on failure } LDR_EndRegistering(); ENSURE(LDR_NonprogressiveLoad() == INFO::OK); ENSURE(m_SecondaryComponentManager->DeserializeState(primaryStateBefore.state)); } if (m_EnableSerializationTest || m_TestingRejoin) { SerializationTestState secondaryStateBefore; ENSURE(m_SecondaryComponentManager->SerializeState(secondaryStateBefore.state)); if (serializationTestDebugDump) ENSURE(m_SecondaryComponentManager->DumpDebugState(secondaryStateBefore.debug, false)); if (serializationTestHash) ENSURE(m_SecondaryComponentManager->ComputeStateHash(secondaryStateBefore.hash, false)); if (primaryStateBefore.state.str() != secondaryStateBefore.state.str() || primaryStateBefore.hash != secondaryStateBefore.hash) { ReportSerializationFailure(&primaryStateBefore, NULL, &secondaryStateBefore, NULL); } SerializationTestState primaryStateAfter; ENSURE(m_ComponentManager.SerializeState(primaryStateAfter.state)); if (serializationTestHash) ENSURE(m_ComponentManager.ComputeStateHash(primaryStateAfter.hash, false)); UpdateComponents(*m_SecondaryContext, turnLengthFixed, CloneCommandsFromOtherCompartment(scriptInterface, m_SecondaryComponentManager->GetScriptInterface(), commands)); SerializationTestState secondaryStateAfter; ENSURE(m_SecondaryComponentManager->SerializeState(secondaryStateAfter.state)); if (serializationTestHash) ENSURE(m_SecondaryComponentManager->ComputeStateHash(secondaryStateAfter.hash, false)); if (primaryStateAfter.state.str() != secondaryStateAfter.state.str() || primaryStateAfter.hash != secondaryStateAfter.hash) { // Only do the (slow) dumping now we know we're going to need to report it ENSURE(m_ComponentManager.DumpDebugState(primaryStateAfter.debug, false)); ENSURE(m_SecondaryComponentManager->DumpDebugState(secondaryStateAfter.debug, false)); ReportSerializationFailure(&primaryStateBefore, &primaryStateAfter, &secondaryStateBefore, &secondaryStateAfter); } } // Run the GC occasionally // No delay because a lot of garbage accumulates in one turn and in non-visual replays there are // much more turns in the same time than in normal games. // Every 500 turns we run a shrinking GC, which decommits unused memory and frees all JIT code. // Based on testing, this seems to be a good compromise between memory usage and performance. // Also check the comment about gcPreserveCode in the ScriptInterface code and this forum topic: // http://www.wildfiregames.com/forum/index.php?showtopic=18466&p=300323 // // (TODO: we ought to schedule this for a frame where we're not // running the sim update, to spread the load) if (m_TurnNumber % 500 == 0) scriptInterface.GetContext()->ShrinkingGC(); else scriptInterface.GetContext()->MaybeIncrementalGC(0.0f); if (m_EnableOOSLog) DumpState(); // Start computing AI for the next turn CmpPtr cmpAIManager(m_SimContext, SYSTEM_ENTITY); if (cmpAIManager) cmpAIManager->StartComputation(); ++m_TurnNumber; } void CSimulation2Impl::UpdateComponents(CSimContext& simContext, fixed turnLengthFixed, const std::vector& commands) { // TODO: the update process is pretty ugly, with lots of messages and dependencies // between different components. Ought to work out a nicer way to do this. CComponentManager& componentManager = simContext.GetComponentManager(); CmpPtr cmpPathfinder(simContext, SYSTEM_ENTITY); if (cmpPathfinder) - cmpPathfinder->FetchAsyncResultsAndSendMessages(); + cmpPathfinder->SendRequestedPaths(); { PROFILE2("Sim - Update Start"); CMessageTurnStart msgTurnStart; componentManager.BroadcastMessage(msgTurnStart); } // Push AI commands onto the queue before we use them CmpPtr cmpAIManager(simContext, SYSTEM_ENTITY); if (cmpAIManager) cmpAIManager->PushCommands(); CmpPtr cmpCommandQueue(simContext, SYSTEM_ENTITY); if (cmpCommandQueue) cmpCommandQueue->FlushTurn(commands); // Process newly generated move commands so the UI feels snappy if (cmpPathfinder) { cmpPathfinder->StartProcessingMoves(true); - cmpPathfinder->FetchAsyncResultsAndSendMessages(); + cmpPathfinder->SendRequestedPaths(); } // 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->StartProcessingMoves(true); - cmpPathfinder->FetchAsyncResultsAndSendMessages(); + cmpPathfinder->SendRequestedPaths(); } { PROFILE2("Sim - Motion Unit"); CMessageUpdate_MotionUnit msgUpdate(turnLengthFixed); componentManager.BroadcastMessage(msgUpdate); } { PROFILE2("Sim - Update Final"); CMessageUpdate_Final msgUpdate(turnLengthFixed); componentManager.BroadcastMessage(msgUpdate); } // Clean up any entities destroyed during the simulation update componentManager.FlushDestroyedComponents(); // Process all remaining moves if (cmpPathfinder) { cmpPathfinder->UpdateGrid(); cmpPathfinder->StartProcessingMoves(false); } } void CSimulation2Impl::Interpolate(float simFrameLength, float frameOffset, float realFrameLength) { PROFILE3("sim interpolate"); m_LastFrameOffset = frameOffset; CMessageInterpolate msg(simFrameLength, frameOffset, realFrameLength); m_ComponentManager.BroadcastMessage(msg); // Clean up any entities destroyed during interpolate (e.g. local corpses) m_ComponentManager.FlushDestroyedComponents(); } void CSimulation2Impl::DumpState() { PROFILE("DumpState"); std::stringstream name;\ name << std::setw(5) << std::setfill('0') << m_TurnNumber << ".txt"; const OsPath path = m_OOSLogPath / name.str(); std::ofstream file (OsString(path).c_str(), std::ofstream::out | std::ofstream::trunc); if (!DirectoryExists(m_OOSLogPath)) { LOGWARNING("OOS-log directory %s was deleted, creating it again.", m_OOSLogPath.string8().c_str()); CreateDirectories(m_OOSLogPath, 0700); } file << "State hash: " << std::hex; std::string hashRaw; m_ComponentManager.ComputeStateHash(hashRaw, false); for (size_t i = 0; i < hashRaw.size(); ++i) file << std::setfill('0') << std::setw(2) << (int)(unsigned char)hashRaw[i]; file << std::dec << "\n"; file << "\n"; m_ComponentManager.DumpDebugState(file, true); std::ofstream binfile (OsString(path.ChangeExtension(L".dat")).c_str(), std::ofstream::out | std::ofstream::trunc | std::ofstream::binary); m_ComponentManager.SerializeState(binfile); } //////////////////////////////////////////////////////////////// CSimulation2::CSimulation2(CUnitManager* unitManager, shared_ptr cx, CTerrain* terrain) : m(new CSimulation2Impl(unitManager, cx, terrain)) { } CSimulation2::~CSimulation2() { delete m; } // Forward all method calls to the appropriate CSimulation2Impl/CComponentManager methods: void CSimulation2::EnableSerializationTest() { m->m_EnableSerializationTest = true; } void CSimulation2::EnableRejoinTest(int rejoinTestTurn) { m->m_RejoinTestTurn = rejoinTestTurn; } void CSimulation2::EnableOOSLog() { if (m->m_EnableOOSLog) return; m->m_EnableOOSLog = true; m->m_OOSLogPath = createDateIndexSubdirectory(psLogDir() / "oos_logs"); debug_printf("Writing ooslogs to %s\n", m->m_OOSLogPath.string8().c_str()); } entity_id_t CSimulation2::AddEntity(const std::wstring& templateName) { return m->m_ComponentManager.AddEntity(templateName, m->m_ComponentManager.AllocateNewEntity()); } entity_id_t CSimulation2::AddEntity(const std::wstring& templateName, entity_id_t preferredId) { return m->m_ComponentManager.AddEntity(templateName, m->m_ComponentManager.AllocateNewEntity(preferredId)); } entity_id_t CSimulation2::AddLocalEntity(const std::wstring& templateName) { return m->m_ComponentManager.AddEntity(templateName, m->m_ComponentManager.AllocateNewLocalEntity()); } void CSimulation2::DestroyEntity(entity_id_t ent) { m->m_ComponentManager.DestroyComponentsSoon(ent); } void CSimulation2::FlushDestroyedEntities() { m->m_ComponentManager.FlushDestroyedComponents(); } IComponent* CSimulation2::QueryInterface(entity_id_t ent, int iid) const { return m->m_ComponentManager.QueryInterface(ent, iid); } void CSimulation2::PostMessage(entity_id_t ent, const CMessage& msg) const { m->m_ComponentManager.PostMessage(ent, msg); } void CSimulation2::BroadcastMessage(const CMessage& msg) const { m->m_ComponentManager.BroadcastMessage(msg); } CSimulation2::InterfaceList CSimulation2::GetEntitiesWithInterface(int iid) { return m->m_ComponentManager.GetEntitiesWithInterface(iid); } const CSimulation2::InterfaceListUnordered& CSimulation2::GetEntitiesWithInterfaceUnordered(int iid) { return m->m_ComponentManager.GetEntitiesWithInterfaceUnordered(iid); } const CSimContext& CSimulation2::GetSimContext() const { return m->m_SimContext; } ScriptInterface& CSimulation2::GetScriptInterface() const { return m->m_ComponentManager.GetScriptInterface(); } void CSimulation2::PreInitGame() { ScriptRequest rq(GetScriptInterface()); JS::RootedValue global(rq.cx, rq.globalValue()); GetScriptInterface().CallFunctionVoid(global, "PreInitGame"); } void CSimulation2::InitGame() { ScriptRequest rq(GetScriptInterface()); JS::RootedValue global(rq.cx, rq.globalValue()); JS::RootedValue settings(rq.cx); JS::RootedValue tmpInitAttributes(rq.cx, GetInitAttributes()); GetScriptInterface().GetProperty(tmpInitAttributes, "settings", &settings); GetScriptInterface().CallFunctionVoid(global, "InitGame", settings); } void CSimulation2::Update(int turnLength) { std::vector commands; m->Update(turnLength, commands); } void CSimulation2::Update(int turnLength, const std::vector& commands) { m->Update(turnLength, commands); } void CSimulation2::Interpolate(float simFrameLength, float frameOffset, float realFrameLength) { m->Interpolate(simFrameLength, frameOffset, realFrameLength); } void CSimulation2::RenderSubmit(SceneCollector& collector, const CFrustum& frustum, bool culling) { PROFILE3("sim submit"); CMessageRenderSubmit msg(collector, frustum, culling); m->m_ComponentManager.BroadcastMessage(msg); } float CSimulation2::GetLastFrameOffset() const { return m->m_LastFrameOffset; } bool CSimulation2::LoadScripts(const VfsPath& path) { return m->LoadScripts(m->m_ComponentManager, &m->m_LoadedScripts, path); } bool CSimulation2::LoadDefaultScripts() { return m->LoadDefaultScripts(m->m_ComponentManager, &m->m_LoadedScripts); } void CSimulation2::SetStartupScript(const std::string& code) { m->m_StartupScript = code; } const std::string& CSimulation2::GetStartupScript() { return m->m_StartupScript; } void CSimulation2::SetInitAttributes(JS::HandleValue attribs) { m->m_InitAttributes = attribs; } JS::Value CSimulation2::GetInitAttributes() { return m->m_InitAttributes.get(); } void CSimulation2::GetInitAttributes(JS::MutableHandleValue ret) { ret.set(m->m_InitAttributes); } void CSimulation2::SetMapSettings(const std::string& settings) { m->m_ComponentManager.GetScriptInterface().ParseJSON(settings, &m->m_MapSettings); } void CSimulation2::SetMapSettings(JS::HandleValue settings) { m->m_MapSettings = settings; m->InitRNGSeedSimulation(); m->InitRNGSeedAI(); } std::string CSimulation2::GetMapSettingsString() { return m->m_ComponentManager.GetScriptInterface().StringifyJSON(&m->m_MapSettings); } void CSimulation2::GetMapSettings(JS::MutableHandleValue ret) { ret.set(m->m_MapSettings); } void CSimulation2::LoadPlayerSettings(bool newPlayers) { ScriptRequest rq(GetScriptInterface()); JS::RootedValue global(rq.cx, rq.globalValue()); GetScriptInterface().CallFunctionVoid(global, "LoadPlayerSettings", m->m_MapSettings, newPlayers); } void CSimulation2::LoadMapSettings() { ScriptRequest rq(GetScriptInterface()); JS::RootedValue global(rq.cx, rq.globalValue()); // Initialize here instead of in Update() GetScriptInterface().CallFunctionVoid(global, "LoadMapSettings", m->m_MapSettings); GetScriptInterface().FreezeObject(m->m_InitAttributes, true); GetScriptInterface().SetGlobal("InitAttributes", m->m_InitAttributes, true, true, true); if (!m->m_StartupScript.empty()) GetScriptInterface().LoadScript(L"map startup script", m->m_StartupScript); // Load the trigger scripts after we have loaded the simulation and the map. m->LoadTriggerScripts(m->m_ComponentManager, m->m_MapSettings, &m->m_LoadedScripts); } int CSimulation2::ProgressiveLoad() { return m->ProgressiveLoad(); } Status CSimulation2::ReloadChangedFile(const VfsPath& path) { return m->ReloadChangedFile(path); } void CSimulation2::ResetState(bool skipScriptedComponents, bool skipAI) { m->ResetState(skipScriptedComponents, skipAI); } bool CSimulation2::ComputeStateHash(std::string& outHash, bool quick) { return m->m_ComponentManager.ComputeStateHash(outHash, quick); } bool CSimulation2::DumpDebugState(std::ostream& stream) { stream << "sim turn: " << m->m_TurnNumber << std::endl; return m->m_ComponentManager.DumpDebugState(stream, true); } bool CSimulation2::SerializeState(std::ostream& stream) { return m->m_ComponentManager.SerializeState(stream); } bool CSimulation2::DeserializeState(std::istream& stream) { // TODO: need to make sure the required SYSTEM_ENTITY components get constructed return m->m_ComponentManager.DeserializeState(stream); } void CSimulation2::ActivateRejoinTest(int turn) { if (m->m_RejoinTestTurn != -1) return; LOGMESSAGERENDER("Rejoin test will activate in %i turns", turn - m->m_TurnNumber); m->m_RejoinTestTurn = turn; } std::string CSimulation2::GenerateSchema() { return m->m_ComponentManager.GenerateSchema(); } static std::vector GetJSONData(const VfsPath& path) { VfsPaths pathnames; Status ret = vfs::GetPathnames(g_VFS, path, L"*.json", pathnames); if (ret != INFO::OK) { // Some error reading directory wchar_t error[200]; LOGERROR("Error reading directory '%s': %s", path.string8(), utf8_from_wstring(StatusDescription(ret, error, ARRAY_SIZE(error)))); return std::vector(); } std::vector data; for (const VfsPath& p : pathnames) { // Load JSON file CVFSFile file; PSRETURN loadStatus = file.Load(g_VFS, p); if (loadStatus != PSRETURN_OK) { LOGERROR("GetJSONData: Failed to load file '%s': %s", p.string8(), GetErrorString(loadStatus)); continue; } data.push_back(file.DecodeUTF8()); // assume it's UTF-8 } return data; } std::vector CSimulation2::GetRMSData() { return GetJSONData(L"maps/random/"); } std::vector CSimulation2::GetCivData() { return GetJSONData(L"simulation/data/civs/"); } std::vector CSimulation2::GetVictoryConditiondData() { return GetJSONData(L"simulation/data/settings/victory_conditions/"); } static std::string ReadJSON(const VfsPath& path) { if (!VfsFileExists(path)) { LOGERROR("File '%s' does not exist", path.string8()); return std::string(); } // Load JSON file CVFSFile file; PSRETURN ret = file.Load(g_VFS, path); if (ret != PSRETURN_OK) { LOGERROR("Failed to load file '%s': %s", path.string8(), GetErrorString(ret)); return std::string(); } return file.DecodeUTF8(); // assume it's UTF-8 } std::string CSimulation2::GetPlayerDefaults() { return ReadJSON(L"simulation/data/settings/player_defaults.json"); } std::string CSimulation2::GetMapSizes() { return ReadJSON(L"simulation/data/settings/map_sizes.json"); } std::string CSimulation2::GetAIData() { const ScriptInterface& scriptInterface = GetScriptInterface(); ScriptRequest rq(scriptInterface); JS::RootedValue aiData(rq.cx, ICmpAIManager::GetAIs(scriptInterface)); // Build single JSON string with array of AI data JS::RootedValue ais(rq.cx); if (!ScriptInterface::CreateObject(rq, &ais, "AIData", aiData)) return std::string(); return scriptInterface.StringifyJSON(&ais); } Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 25255) +++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 25256) @@ -1,988 +1,922 @@ /* Copyright (C) 2021 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 . */ /** * @file * Common code and setup code for CCmpPathfinder. */ #include "precompiled.h" #include "CCmpPathfinder_Common.h" #include "simulation2/MessageTypes.h" #include "simulation2/components/ICmpObstruction.h" #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/components/ICmpTerrain.h" #include "simulation2/components/ICmpWaterManager.h" #include "simulation2/helpers/HierarchicalPathfinder.h" #include "simulation2/helpers/LongPathfinder.h" #include "simulation2/helpers/MapEdgeTiles.h" #include "simulation2/helpers/Rasterize.h" #include "simulation2/helpers/VertexPathfinder.h" #include "simulation2/serialization/SerializedPathfinder.h" #include "simulation2/serialization/SerializedTypes.h" #include "ps/CLogger.h" #include "ps/CStr.h" #include "ps/Profile.h" #include "ps/XML/Xeromyces.h" #include "renderer/Scene.h" +#include + REGISTER_COMPONENT_TYPE(Pathfinder) void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode)) { m_MapSize = 0; m_Grid = NULL; m_TerrainOnlyGrid = NULL; FlushAIPathfinderDirtinessInformation(); m_NextAsyncTicket = 1; m_AtlasOverlay = NULL; m_VertexPathfinder = std::make_unique(m_MapSize, m_TerrainOnlyGrid); m_LongPathfinder = std::make_unique(); m_PathfinderHier = std::make_unique(); // Register Relax NG validator CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng"); // Since this is used as a system component (not loaded from an entity template), // we can't use the real paramNode (it won't get handled properly when deserializing), // so load the data from a special XML file. CParamNode externalParamNode; CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder"); - // Previously all move commands during a turn were - // queued up and processed asynchronously at the start - // of the next turn. Now we are processing queued up - // events several times duing the turn. This improves - // responsiveness and units move more smoothly especially. - // when in formation. There is still a call at the - // beginning of a turn to process all outstanding moves - - // this will handle any moves above the MaxSameTurnMoves - // threshold. - // - // TODO - The moves processed at the beginning of the - // turn do not count against the maximum moves per turn - // currently. The thinking is that this will eventually - // happen in another thread. Either way this probably - // will require some adjustment and rethinking. + // Paths are computed: + // - Before MT_Update + // - Before MT_MotionUnitFormation + // - 'in-between' turns (effectively at the start until threading is implemented). + // The latter of these must compute all outstanding requests, but the former two are capped + // to avoid spending too much time there (since the latter are designed to be threaded and thus not block the GUI). + // This loads that maximum number (note that it's per computation call, not per turn for now). const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder"); m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt(); const CParamNode::ChildrenMap& passClasses = externalParamNode.GetChild("Pathfinder").GetChild("PassabilityClasses").GetChildren(); for (CParamNode::ChildrenMap::const_iterator it = passClasses.begin(); it != passClasses.end(); ++it) { std::string name = it->first; ENSURE((int)m_PassClasses.size() <= PASS_CLASS_BITS); pass_class_t mask = PASS_CLASS_MASK_FROM_INDEX(m_PassClasses.size()); m_PassClasses.push_back(PathfinderPassability(mask, it->second)); m_PassClassMasks[name] = mask; } - - m_Workers.emplace_back(PathfinderWorker{}); } CCmpPathfinder::~CCmpPathfinder() {}; void CCmpPathfinder::Deinit() { - m_Workers.clear(); - SetDebugOverlay(false); // cleans up memory SAFE_DELETE(m_AtlasOverlay); SAFE_DELETE(m_Grid); SAFE_DELETE(m_TerrainOnlyGrid); } template<> struct SerializeHelper { template void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify value) { serialize.NumberU32_Unbounded("ticket", value.ticket); serialize.NumberFixed_Unbounded("x0", value.x0); serialize.NumberFixed_Unbounded("z0", value.z0); Serializer(serialize, "goal", value.goal); serialize.NumberU16_Unbounded("pass class", value.passClass); serialize.NumberU32_Unbounded("notify", value.notify); } }; template<> struct SerializeHelper { template void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify value) { serialize.NumberU32_Unbounded("ticket", value.ticket); serialize.NumberFixed_Unbounded("x0", value.x0); serialize.NumberFixed_Unbounded("z0", value.z0); serialize.NumberFixed_Unbounded("clearance", value.clearance); serialize.NumberFixed_Unbounded("range", value.range); Serializer(serialize, "goal", value.goal); serialize.NumberU16_Unbounded("pass class", value.passClass); serialize.Bool("avoid moving units", value.avoidMovingUnits); serialize.NumberU32_Unbounded("group", value.group); serialize.NumberU32_Unbounded("notify", value.notify); } }; template void CCmpPathfinder::SerializeCommon(S& serialize) { - Serializer(serialize, "long requests", m_LongPathRequests); - Serializer(serialize, "short requests", m_ShortPathRequests); + Serializer(serialize, "long requests", m_LongPathRequests.m_Requests); + Serializer(serialize, "short requests", m_ShortPathRequests.m_Requests); serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket); serialize.NumberU16_Unbounded("map size", m_MapSize); } void CCmpPathfinder::Serialize(ISerializer& serialize) { SerializeCommon(serialize); } void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) { Init(paramNode); SerializeCommon(deserialize); } void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { case MT_RenderSubmit: { const CMessageRenderSubmit& msgData = static_cast (msg); RenderSubmit(msgData.collector); break; } case MT_TerrainChanged: { const CMessageTerrainChanged& msgData = static_cast(msg); m_TerrainDirty = true; MinimalTerrainUpdate(msgData.i0, msgData.j0, msgData.i1, msgData.j1); break; } case MT_WaterChanged: case MT_ObstructionMapShapeChanged: m_TerrainDirty = true; UpdateGrid(); break; case MT_Deserialized: UpdateGrid(); // In case we were serialised with requests pending, we need to process them. - if (!m_ShortPathRequests.empty() || !m_LongPathRequests.empty()) + if (!m_ShortPathRequests.m_Requests.empty() || !m_LongPathRequests.m_Requests.empty()) { ENSURE(CmpPtr(GetSystemEntity())); StartProcessingMoves(false); } break; } } void CCmpPathfinder::RenderSubmit(SceneCollector& collector) { m_VertexPathfinder->RenderSubmit(collector); m_PathfinderHier->RenderSubmit(collector); } void CCmpPathfinder::SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) { m_LongPathfinder->SetDebugPath(*m_PathfinderHier, x0, z0, goal, passClass); } void CCmpPathfinder::SetDebugOverlay(bool enabled) { m_VertexPathfinder->SetDebugOverlay(enabled); m_LongPathfinder->SetDebugOverlay(enabled); } void CCmpPathfinder::SetHierDebugOverlay(bool enabled) { m_PathfinderHier->SetDebugOverlay(enabled, &GetSimContext()); } void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid& grid) const { m_LongPathfinder->GetDebugData(steps, time, grid); } void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass) { if (enable) { if (!m_AtlasOverlay) m_AtlasOverlay = new AtlasOverlay(this, passClass); m_AtlasOverlay->m_PassClass = passClass; } else SAFE_DELETE(m_AtlasOverlay); } pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const { std::map::const_iterator it = m_PassClassMasks.find(name); if (it == m_PassClassMasks.end()) { LOGERROR("Invalid passability class name '%s'", name.c_str()); return 0; } return it->second; } void CCmpPathfinder::GetPassabilityClasses(std::map& passClasses) const { passClasses = m_PassClassMasks; } void CCmpPathfinder::GetPassabilityClasses(std::map& nonPathfindingPassClasses, std::map& pathfindingPassClasses) const { for (const std::pair& pair : m_PassClassMasks) { if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING)) pathfindingPassClasses[pair.first] = pair.second; else nonPathfindingPassClasses[pair.first] = pair.second; } } const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const { for (const PathfinderPassability& passability : m_PassClasses) { if (passability.m_Mask == passClass) return &passability; } return NULL; } const Grid& CCmpPathfinder::GetPassabilityGrid() { if (!m_Grid) UpdateGrid(); return *m_Grid; } /** * Given a grid of passable/impassable navcells (based on some passability mask), * computes a new grid where a navcell is impassable (per that mask) if * it is <=clearance navcells away from an impassable navcell in the original grid. * The results are ORed onto the original grid. * * This is used for adding clearance onto terrain-based navcell passability. * * TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as * Euclidean distances; currently it effectively does dist=max(dx,dy) instead. * This would only really be a problem for big clearances. */ static void ExpandImpassableCells(Grid& grid, u16 clearance, pass_class_t mask) { PROFILE3("ExpandImpassableCells"); u16 w = grid.m_W; u16 h = grid.m_H; // First expand impassable cells horizontally into a temporary 1-bit grid Grid tempGrid(w, h); for (u16 j = 0; j < h; ++j) { // New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance // Count the number of blocked cells around i=0 u16 numBlocked = 0; for (u16 i = 0; i <= clearance && i < w; ++i) if (!IS_PASSABLE(grid.get(i, j), mask)) ++numBlocked; for (u16 i = 0; i < w; ++i) { // Store a flag if blocked by at least one nearby cell if (numBlocked) tempGrid.set(i, j, 1); // Slide the numBlocked window along: // remove the old i-clearance value, add the new (i+1)+clearance // (avoiding overflowing the grid) if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask)) --numBlocked; if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask)) ++numBlocked; } } for (u16 i = 0; i < w; ++i) { // New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance // Count the number of blocked cells around j=0 u16 numBlocked = 0; for (u16 j = 0; j <= clearance && j < h; ++j) if (tempGrid.get(i, j)) ++numBlocked; for (u16 j = 0; j < h; ++j) { // Add the mask if blocked by at least one nearby cell if (numBlocked) grid.set(i, j, grid.get(i, j) | mask); // Slide the numBlocked window along: // remove the old j-clearance value, add the new (j+1)+clearance // (avoiding overflowing the grid) if (j >= clearance && tempGrid.get(i, j-clearance)) --numBlocked; if (j+1+clearance < h && tempGrid.get(i, j+1+clearance)) ++numBlocked; } } } Grid CCmpPathfinder::ComputeShoreGrid(bool expandOnWater) { PROFILE3("ComputeShoreGrid"); CmpPtr cmpWaterManager(GetSystemEntity()); // TODO: these bits should come from ICmpTerrain CTerrain& terrain = GetSimContext().GetTerrain(); // avoid integer overflow in intermediate calculation const u16 shoreMax = 32767; // First pass - find underwater tiles Grid waterGrid(m_MapSize, m_MapSize); for (u16 j = 0; j < m_MapSize; ++j) { for (u16 i = 0; i < m_MapSize; ++i) { fixed x, z; Pathfinding::TileCenter(i, j, x, z); bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z)); waterGrid.set(i, j, underWater ? 1 : 0); } } // Second pass - find shore tiles Grid shoreGrid(m_MapSize, m_MapSize); for (u16 j = 0; j < m_MapSize; ++j) { for (u16 i = 0; i < m_MapSize; ++i) { // Find a land tile if (!waterGrid.get(i, j)) { // If it's bordered by water, it's a shore tile if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < m_MapSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1)) || (i < m_MapSize-1 && waterGrid.get(i+1, j)) || (i < m_MapSize-1 && j < m_MapSize-1 && waterGrid.get(i+1, j+1)) || (i < m_MapSize-1 && j > 0 && waterGrid.get(i+1, j-1)) || (j > 0 && waterGrid.get(i, j-1)) || (j < m_MapSize-1 && waterGrid.get(i, j+1)) ) shoreGrid.set(i, j, 0); else shoreGrid.set(i, j, shoreMax); } // If we want to expand on water, we want water tiles not to be shore tiles else if (expandOnWater) shoreGrid.set(i, j, shoreMax); } } // Expand influences on land to find shore distance for (u16 y = 0; y < m_MapSize; ++y) { u16 min = shoreMax; for (u16 x = 0; x < m_MapSize; ++x) { if (!waterGrid.get(x, y) || expandOnWater) { u16 g = shoreGrid.get(x, y); if (g > min) shoreGrid.set(x, y, min); else if (g < min) min = g; ++min; } } for (u16 x = m_MapSize; x > 0; --x) { if (!waterGrid.get(x-1, y) || expandOnWater) { u16 g = shoreGrid.get(x-1, y); if (g > min) shoreGrid.set(x-1, y, min); else if (g < min) min = g; ++min; } } } for (u16 x = 0; x < m_MapSize; ++x) { u16 min = shoreMax; for (u16 y = 0; y < m_MapSize; ++y) { if (!waterGrid.get(x, y) || expandOnWater) { u16 g = shoreGrid.get(x, y); if (g > min) shoreGrid.set(x, y, min); else if (g < min) min = g; ++min; } } for (u16 y = m_MapSize; y > 0; --y) { if (!waterGrid.get(x, y-1) || expandOnWater) { u16 g = shoreGrid.get(x, y-1); if (g > min) shoreGrid.set(x, y-1, min); else if (g < min) min = g; ++min; } } } return shoreGrid; } void CCmpPathfinder::UpdateGrid() { PROFILE3("UpdateGrid"); CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); if (!cmpTerrain) return; // error u16 terrainSize = cmpTerrain->GetTilesPerSide(); if (terrainSize == 0) return; // If the terrain was resized then delete the old grid data if (m_Grid && m_MapSize != terrainSize) { SAFE_DELETE(m_Grid); SAFE_DELETE(m_TerrainOnlyGrid); } // Initialise the terrain data when first needed if (!m_Grid) { m_MapSize = terrainSize; m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE); SAFE_DELETE(m_TerrainOnlyGrid); m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE); m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) }; m_AIPathfinderDirtinessInformation = m_DirtinessInformation; m_TerrainDirty = true; } // The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging. #ifdef NDEBUG ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid)); #else ENSURE(m_DirtinessInformation.dirtinessGrid == Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE)); #endif CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY); cmpObstructionManager->UpdateInformations(m_DirtinessInformation); if (!m_DirtinessInformation.dirty && !m_TerrainDirty) return; // If the terrain has changed, recompute m_Grid // Else, use data from m_TerrainOnlyGrid and add obstructions if (m_TerrainDirty) { TerrainUpdateHelper(); *m_Grid = *m_TerrainOnlyGrid; m_TerrainDirty = false; m_DirtinessInformation.globallyDirty = true; } else if (m_DirtinessInformation.globallyDirty) { ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid)); memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)*(m_Grid->m_H)*sizeof(NavcellData)); } else { ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid)); for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j) for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i) if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1) m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j)); } // Add obstructions onto the grid cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty); // Update the long-range and hierarchical pathfinders. if (m_DirtinessInformation.globallyDirty) { std::map nonPathfindingPassClasses, pathfindingPassClasses; GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses); m_LongPathfinder->Reload(m_Grid); m_PathfinderHier->Recompute(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses); } else { m_LongPathfinder->Update(m_Grid); m_PathfinderHier->Update(m_Grid, m_DirtinessInformation.dirtinessGrid); } // Remember the necessary updates that the AI pathfinder will have to perform as well m_AIPathfinderDirtinessInformation.MergeAndClear(m_DirtinessInformation); } void CCmpPathfinder::MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1) { TerrainUpdateHelper(false, itile0, jtile0, itile1, jtile1); } void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability, int itile0, int jtile0, int itile1, int jtile1) { PROFILE3("TerrainUpdateHelper"); CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY); CmpPtr cmpWaterManager(GetSimContext(), SYSTEM_ENTITY); CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); CTerrain& terrain = GetSimContext().GetTerrain(); if (!cmpTerrain || !cmpObstructionManager) return; u16 terrainSize = cmpTerrain->GetTilesPerSide(); if (terrainSize == 0) return; const bool needsNewTerrainGrid = !m_TerrainOnlyGrid || m_MapSize != terrainSize; if (needsNewTerrainGrid) { m_MapSize = terrainSize; SAFE_DELETE(m_TerrainOnlyGrid); m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE); // If this update comes from a map resizing, we must reinitialize the other grids as well if (!m_TerrainOnlyGrid->compare_sizes(m_Grid)) { SAFE_DELETE(m_Grid); m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE); m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) }; m_AIPathfinderDirtinessInformation = m_DirtinessInformation; } } Grid shoreGrid = ComputeShoreGrid(); const bool partialTerrainGridUpdate = !expandPassability && !needsNewTerrainGrid && itile0 != -1 && jtile0 != -1 && itile1 != -1 && jtile1 != -1; int istart = 0, iend = m_MapSize * Pathfinding::NAVCELLS_PER_TILE; int jstart = 0, jend = m_MapSize * Pathfinding::NAVCELLS_PER_TILE; if (partialTerrainGridUpdate) { // We need to extend the boundaries by 1 tile, because slope and ground // level are calculated by multiple neighboring tiles. // TODO: add CTerrain constant instead of 1. istart = Clamp(itile0 - 1, 0, static_cast(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE; iend = Clamp(itile1 + 1, 0, static_cast(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE; jstart = Clamp(jtile0 - 1, 0, static_cast(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE; jend = Clamp(jtile1 + 1, 0, static_cast(m_MapSize)) * Pathfinding::NAVCELLS_PER_TILE; } // Compute initial terrain-dependent passability for (int j = jstart; j < jend; ++j) { for (int i = istart; i < iend; ++i) { // World-space coordinates for this navcell fixed x, z; Pathfinding::NavcellCenter(i, j, x, z); // Terrain-tile coordinates for this navcell int itile = i / Pathfinding::NAVCELLS_PER_TILE; int jtile = j / Pathfinding::NAVCELLS_PER_TILE; // Gather all the data potentially needed to determine passability: fixed height = terrain.GetExactGroundLevelFixed(x, z); fixed water; if (cmpWaterManager) water = cmpWaterManager->GetWaterLevel(x, z); fixed depth = water - height; // Exact slopes give kind of weird output, so just use rough tile-based slopes fixed slope = terrain.GetSlopeFixed(itile, jtile); // Get world-space coordinates from shoreGrid (which uses terrain tiles) fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE); // Compute the passability for every class for this cell NavcellData t = 0; for (const PathfinderPassability& passability : m_PassClasses) if (!passability.IsPassable(depth, slope, shoredist)) t |= passability.m_Mask; m_TerrainOnlyGrid->set(i, j, t); } } // Compute off-world passability const int edgeSize = MAP_EDGE_TILES * Pathfinding::NAVCELLS_PER_TILE; NavcellData edgeMask = 0; for (const PathfinderPassability& passability : m_PassClasses) edgeMask |= passability.m_Mask; int w = m_TerrainOnlyGrid->m_W; int h = m_TerrainOnlyGrid->m_H; if (cmpObstructionManager->GetPassabilityCircular()) { for (int j = jstart; j < jend; ++j) { for (int i = istart; i < iend; ++i) { // Based on CCmpRangeManager::LosIsOffWorld // but tweaked since it's tile-based instead. // (We double all the values so we can handle half-tile coordinates.) // This needs to be slightly tighter than the LOS circle, // else units might get themselves lost in the SoD around the edge. int dist2 = (i*2 + 1 - w)*(i*2 + 1 - w) + (j*2 + 1 - h)*(j*2 + 1 - h); if (dist2 >= (w - 2*edgeSize) * (h - 2*edgeSize)) m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask); } } } else { for (u16 j = 0; j < h; ++j) for (u16 i = 0; i < edgeSize; ++i) m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask); for (u16 j = 0; j < h; ++j) for (u16 i = w-edgeSize+1; i < w; ++i) m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask); for (u16 j = 0; j < edgeSize; ++j) for (u16 i = edgeSize; i < w-edgeSize+1; ++i) m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask); for (u16 j = h-edgeSize+1; j < h; ++j) for (u16 i = edgeSize; i < w-edgeSize+1; ++i) m_TerrainOnlyGrid->set(i, j, m_TerrainOnlyGrid->get(i, j) | edgeMask); } if (!expandPassability) return; // Expand the impassability grid, for any class with non-zero clearance, // so that we can stop units getting too close to impassable navcells. // Note: It's not possible to perform this expansion once for all passabilities // with the same clearance, because the impassable cells are not necessarily the // same for all these passabilities. for (PathfinderPassability& passability : m_PassClasses) { if (passability.m_Clearance == fixed::Zero()) continue; int clearance = (passability.m_Clearance / Pathfinding::NAVCELL_SIZE).ToInt_RoundToInfinity(); ExpandImpassableCells(*m_TerrainOnlyGrid, clearance, passability.m_Mask); } } ////////////////////////////////////////////////////////// -// Async pathfinder workers - -CCmpPathfinder::PathfinderWorker::PathfinderWorker() {} - -template -void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector&, ssize_t) -{ - static_assert(sizeof(T) == 0, "Only specializations can be used"); -} - -template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector& from, ssize_t amount) -{ - m_LongRequests.insert(m_LongRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end())); -} - -template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector& from, ssize_t amount) -{ - m_ShortRequests.insert(m_ShortRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end())); -} - -void CCmpPathfinder::PathfinderWorker::Work(const CCmpPathfinder& pathfinder) -{ - while (!m_LongRequests.empty()) - { - const LongPathRequest& req = m_LongRequests.back(); - WaypointPath path; - pathfinder.m_LongPathfinder->ComputePath(*pathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, path); - m_Results.emplace_back(req.ticket, req.notify, path); - - m_LongRequests.pop_back(); - } - - while (!m_ShortRequests.empty()) - { - const ShortPathRequest& req = m_ShortRequests.back(); - WaypointPath path = pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr(pathfinder.GetSystemEntity())); - m_Results.emplace_back(req.ticket, req.notify, path); - - m_ShortRequests.pop_back(); - } -} - u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify) { LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify }; - m_LongPathRequests.push_back(req); + m_LongPathRequests.m_Requests.push_back(req); return req.ticket; } u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t clearance, entity_pos_t range, const PathGoal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify) { ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify }; - m_ShortPathRequests.push_back(req); + m_ShortPathRequests.m_Requests.push_back(req); return req.ticket; } void CCmpPathfinder::ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const { m_LongPathfinder->ComputePath(*m_PathfinderHier, x0, z0, goal, passClass, ret); } WaypointPath CCmpPathfinder::ComputeShortPathImmediate(const ShortPathRequest& request) const { return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity())); } -void CCmpPathfinder::FetchAsyncResultsAndSendMessages() +template +template +void CCmpPathfinder::PathRequests::Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder) { - PROFILE2("FetchAsyncResults"); + static_assert((std::is_same_v && std::is_same_v) || + (std::is_same_v && std::is_same_v)); + size_t maxN = m_Results.size(); + size_t startIndex = m_Requests.size() - m_Results.size(); + do + { + size_t workIndex = m_NextPathToCompute++; + if (workIndex >= maxN) + break; + const T& req = m_Requests[startIndex + workIndex]; + PathResult& result = m_Results[workIndex]; + result.ticket = req.ticket; + result.notify = req.notify; + if constexpr (std::is_same_v) + pathfinder.ComputePath(*cmpPathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, result.path); + else + result.path = pathfinder.ComputeShortPath(req, CmpPtr(cmpPathfinder.GetSystemEntity())); + if (workIndex == maxN - 1) + m_ComputeDone = true; + } + while (true); +} - // We may now clear existing requests. - m_ShortPathRequests.clear(); - m_LongPathRequests.clear(); +void CCmpPathfinder::SendRequestedPaths() +{ + PROFILE2("SendRequestedPaths"); - // 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; - for (PathfinderWorker& worker : m_Workers) + if (!m_LongPathRequests.m_ComputeDone || !m_ShortPathRequests.m_ComputeDone) { - results.insert(results.end(), std::make_move_iterator(worker.m_Results.begin()), std::make_move_iterator(worker.m_Results.end())); - worker.m_Results.clear(); + m_ShortPathRequests.Compute(*this, *m_VertexPathfinder); + m_LongPathRequests.Compute(*this, *m_LongPathfinder); } { PROFILE2("PostMessages"); - for (PathResult& path : results) + for (PathResult& path : m_ShortPathRequests.m_Results) { CMessagePathResult msg(path.ticket, path.path); GetSimContext().GetComponentManager().PostMessage(path.notify, msg); } - } -} -void CCmpPathfinder::StartProcessingMoves(bool useMax) -{ - std::vector longRequests = GetMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves); - std::vector shortRequests = GetMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size()); - - PushRequestsToWorkers(longRequests); - PushRequestsToWorkers(shortRequests); - - for (PathfinderWorker& worker : m_Workers) - worker.Work(*this); -} - -template -std::vector CCmpPathfinder::GetMovesToProcess(std::vector& requests, bool useMax, size_t maxMoves) -{ - // Keep the original requests in which we need to serialize. - std::vector copiedRequests; - if (useMax) - { - size_t amount = std::min(requests.size(), maxMoves); - if (amount > 0) - copiedRequests.insert(copiedRequests.begin(), requests.end() - amount, requests.end()); + for (PathResult& path : m_LongPathRequests.m_Results) + { + CMessagePathResult msg(path.ticket, path.path); + GetSimContext().GetComponentManager().PostMessage(path.notify, msg); + } } - else - copiedRequests = requests; - - return copiedRequests; + m_ShortPathRequests.ClearComputed(); + m_LongPathRequests.ClearComputed(); } -template -void CCmpPathfinder::PushRequestsToWorkers(std::vector& from) +void CCmpPathfinder::StartProcessingMoves(bool useMax) { - if (from.empty()) - return; - - // Trivial load-balancing, / rounds towards zero so add 1 to ensure we do push all requests. - size_t amount = from.size() / m_Workers.size() + 1; - - // WARNING: the order in which moves are pushed must be consistent when using 1 or n workers. - // In this instance, work is distributed in a strict LIFO order, effectively reversing tickets. - for (PathfinderWorker& worker : m_Workers) - { - amount = std::min(amount, from.size()); // Since we are rounding up before, ensure we aren't pushing beyond the end. - worker.PushRequests(from, amount); - from.erase(from.end() - amount, from.end()); - } + m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0); + m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0); } ////////////////////////////////////////////////////////// bool CCmpPathfinder::IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) { PROFILE2("IsGoalReachable"); u16 i, j; Pathfinding::NearestNavcell(x0, z0, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE); if (!IS_PASSABLE(m_Grid->get(i, j), passClass)) m_PathfinderHier->FindNearestPassableNavcell(i, j, passClass); return m_PathfinderHier->IsGoalReachable(i, j, goal, passClass); } bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r, pass_class_t passClass) const { PROFILE2_IFSPIKE("Check Movement", 0.001); // Test against obstructions first. filter may discard pathfinding-blocking obstructions. // Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly. // This makes movement smoother and more natural for units, overall. CmpPtr cmpObstructionManager(GetSystemEntity()); if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true)) return false; // Then test against the terrain grid. This should not be necessary // But in case we allow terrain to change it will become so. return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid); } ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const { // Check unit obstruction CmpPtr cmpObstructionManager(GetSystemEntity()); if (!cmpObstructionManager) return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR; if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL)) return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION; // Test against terrain and static obstructions: u16 i, j; Pathfinding::NearestNavcell(x, z, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE); if (!IS_PASSABLE(m_Grid->get(i, j), passClass)) return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS; // (Static obstructions will be redundantly tested against in both the // obstruction-shape test and navcell-passability test, which is slightly // inefficient but shouldn't affect behaviour) return ICmpObstruction::FOUNDATION_CHECK_SUCCESS; } ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass) const { return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false); } ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const { // Check unit obstruction CmpPtr cmpObstructionManager(GetSystemEntity()); if (!cmpObstructionManager) return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR; if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL)) return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION; // Test against terrain: ICmpObstructionManager::ObstructionSquare square; CmpPtr cmpObstruction(GetSimContext(), id); if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square)) return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION; entity_pos_t expand; const PathfinderPassability* passability = GetPassabilityFromMask(passClass); if (passability) expand = passability->m_Clearance; SimRasterize::Spans spans; SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE); for (const SimRasterize::Span& span : spans) { i16 i0 = span.i0; i16 i1 = span.i1; i16 j = span.j; // Fail if any span extends outside the grid if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H) return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS; // Fail if any span includes an impassable tile for (i16 i = i0; i < i1; ++i) if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass)) return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS; } return ICmpObstruction::FOUNDATION_CHECK_SUCCESS; } Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 25255) +++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 25256) @@ -1,287 +1,294 @@ -/* Copyright (C) 2020 Wildfire Games. +/* Copyright (C) 2021 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_CCMPPATHFINDER_COMMON #define INCLUDED_CCMPPATHFINDER_COMMON /** * @file * Declares CCmpPathfinder. Its implementation is mainly done in CCmpPathfinder.cpp, * but the short-range (vertex) pathfinding is done in CCmpPathfinder_Vertex.cpp. * This file provides common code needed for both files. * * The long-range pathfinding is done by a LongPathfinder object. */ #include "simulation2/system/Component.h" #include "ICmpPathfinder.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "ps/CLogger.h" #include "renderer/TerrainOverlay.h" #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/helpers/Grid.h" +#include class HierarchicalPathfinder; class LongPathfinder; class VertexPathfinder; class SceneCollector; class AtlasOverlay; #ifdef NDEBUG #define PATHFIND_DEBUG 0 #else #define PATHFIND_DEBUG 1 #endif /** * Implementation of ICmpPathfinder */ class CCmpPathfinder final : public ICmpPathfinder { -protected: - - class PathfinderWorker - { - friend CCmpPathfinder; - public: - PathfinderWorker(); - - // Process path requests, checking if we should stop before each new one. - 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 - template - void PushRequests(std::vector& from, ssize_t amount); - - // Stores our results, the main thread will fetch this. - std::vector m_Results; - - std::vector m_LongRequests; - std::vector m_ShortRequests; - }; - - // Allow the workers to access our private variables - friend class PathfinderWorker; - public: static void ClassInit(CComponentManager& componentManager) { componentManager.SubscribeToMessageType(MT_Deserialized); componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays componentManager.SubscribeToMessageType(MT_TerrainChanged); componentManager.SubscribeToMessageType(MT_WaterChanged); componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged); } ~CCmpPathfinder(); DEFAULT_COMPONENT_ALLOCATOR(Pathfinder) // Template state: std::map m_PassClassMasks; std::vector m_PassClasses; + u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves. // Dynamic state: - std::vector m_LongPathRequests; - std::vector m_ShortPathRequests; - u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests. - u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves. - // Lazily-constructed dynamic state (not serialized): u16 m_MapSize; // tiles per side Grid* m_Grid; // terrain/passability information Grid* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations // Keep clever updates in memory to avoid memory fragmentation from the grid. // This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else. GridUpdateInformation m_DirtinessInformation; // The data from clever updates is stored for the AI manager GridUpdateInformation m_AIPathfinderDirtinessInformation; bool m_TerrainDirty; std::unique_ptr m_VertexPathfinder; std::unique_ptr m_PathfinderHier; std::unique_ptr m_LongPathfinder; - // Workers process pathing requests. - std::vector m_Workers; + template + class PathRequests { + public: + std::vector m_Requests; + std::vector m_Results; + // This is the array index of the next path to compute. + size_t m_NextPathToCompute = 0; + // This is false until all scheduled paths have been computed. + bool m_ComputeDone = true; + + void ClearComputed() + { + if (m_Results.size() == m_Requests.size()) + m_Requests.clear(); + else + m_Requests.erase(m_Requests.end() - m_Results.size(), m_Requests.end()); + m_Results.clear(); + } + + /** + * @param max - if non-zero, how many paths to process. + */ + void PrepareForComputation(u16 max) + { + size_t n = m_Requests.size(); + if (max && n > max) + n = max; + m_NextPathToCompute = 0; + m_Results.resize(n); + m_ComputeDone = n == 0; + } + + template + void Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder); + }; + PathRequests m_LongPathRequests; + PathRequests m_ShortPathRequests; + + u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests. AtlasOverlay* m_AtlasOverlay; static std::string GetSchema() { return ""; } virtual void Init(const CParamNode& paramNode); virtual void Deinit(); template void SerializeCommon(S& serialize); virtual void Serialize(ISerializer& serialize); virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize); virtual void HandleMessage(const CMessage& msg, bool global); virtual pass_class_t GetPassabilityClass(const std::string& name) const; virtual void GetPassabilityClasses(std::map& passClasses) const; virtual void GetPassabilityClasses( std::map& nonPathfindingPassClasses, std::map& pathfindingPassClasses) const; const PathfinderPassability* GetPassabilityFromMask(pass_class_t passClass) const; virtual entity_pos_t GetClearance(pass_class_t passClass) const { const PathfinderPassability* passability = GetPassabilityFromMask(passClass); if (!passability) return fixed::Zero(); return passability->m_Clearance; } virtual entity_pos_t GetMaximumClearance() const { entity_pos_t max = fixed::Zero(); for (const PathfinderPassability& passability : m_PassClasses) if (passability.m_Clearance > max) max = passability.m_Clearance; return max + Pathfinding::CLEARANCE_EXTENSION_RADIUS; } virtual const Grid& GetPassabilityGrid(); virtual const GridUpdateInformation& GetAIPathfinderDirtinessInformation() const { return m_AIPathfinderDirtinessInformation; } virtual void FlushAIPathfinderDirtinessInformation() { m_AIPathfinderDirtinessInformation.Clean(); } virtual Grid ComputeShoreGrid(bool expandOnWater = false); virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const; virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify); virtual WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const; 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 bool IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass); virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass); virtual void SetDebugOverlay(bool enabled); virtual void SetHierDebugOverlay(bool enabled); virtual void GetDebugData(u32& steps, double& time, Grid& grid) const; 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 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 void FetchAsyncResultsAndSendMessages(); + virtual void SendRequestedPaths(); virtual void StartProcessingMoves(bool useMax); template std::vector GetMovesToProcess(std::vector& requests, bool useMax = false, size_t maxMoves = 0); template void PushRequestsToWorkers(std::vector& from); /** * Regenerates the grid based on the current obstruction list, if necessary */ virtual void UpdateGrid(); /** * Updates the terrain-only grid without updating the dirtiness informations. * Useful for fast passability updates in Atlas. */ void MinimalTerrainUpdate(int itile0, int jtile0, int itile1, int jtile1); /** * Regenerates the terrain-only grid. * Atlas doesn't need to have passability cells expanded. */ void TerrainUpdateHelper(bool expandPassability = true, int itile0 = -1, int jtile0 = -1, int itile1 = -1, int jtile1 = -1); void RenderSubmit(SceneCollector& collector); }; class AtlasOverlay : public TerrainTextureOverlay { public: const CCmpPathfinder* m_Pathfinder; pass_class_t m_PassClass; AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) : TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass) { } virtual void BuildTextureRGBA(u8* data, size_t w, size_t h) { // Render navcell passability, based on the terrain-only grid u8* p = data; for (size_t j = 0; j < h; ++j) { 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)) color = SColor4ub(255, 0, 0, 127); *p++ = color.R; *p++ = color.G; *p++ = color.B; *p++ = color.A; } } } }; #endif // INCLUDED_CCMPPATHFINDER_COMMON Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h =================================================================== --- ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 25255) +++ ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 25256) @@ -1,213 +1,213 @@ /* Copyright (C) 2021 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_ICMPPATHFINDER #define INCLUDED_ICMPPATHFINDER #include "simulation2/system/Interface.h" #include "simulation2/components/ICmpObstruction.h" #include "simulation2/helpers/Pathfinding.h" #include "maths/FixedVector2D.h" #include class IObstructionTestFilter; class PathGoal; template class Grid; // Returned by asynchronous workers, used to send messages in the main thread. struct WaypointPath; struct PathResult { PathResult() = default; PathResult(u32 t, entity_id_t n, WaypointPath p) : ticket(t), notify(n), path(p) {}; u32 ticket; entity_id_t notify; WaypointPath path; }; /** * Pathfinder algorithms. * * There are two different modes: a tile-based pathfinder that works over long distances and * accounts for terrain costs but ignore units, and a 'short' vertex-based pathfinder that * provides precise paths and avoids other units. * * Both use the same concept of a PathGoal: either a point, circle or square. * (If the starting point is inside the goal shape then the path will move outwards * to reach the shape's outline.) * * The output is a list of waypoints. */ class ICmpPathfinder : public IComponent { public: /** * Get the list of all known passability classes. */ virtual void GetPassabilityClasses(std::map& passClasses) const = 0; /** * Get the list of passability classes, separating pathfinding classes and others. */ virtual void GetPassabilityClasses( std::map& nonPathfindingPassClasses, std::map& pathfindingPassClasses) const = 0; /** * Get the tag for a given passability class name. * Logs an error and returns something acceptable if the name is unrecognised. */ virtual pass_class_t GetPassabilityClass(const std::string& name) const = 0; virtual entity_pos_t GetClearance(pass_class_t passClass) const = 0; /** * Get the larger clearance in all passability classes. */ virtual entity_pos_t GetMaximumClearance() const = 0; virtual const Grid& GetPassabilityGrid() = 0; /** * Get the accumulated dirtiness information since the last time the AI accessed and flushed it. */ virtual const GridUpdateInformation& GetAIPathfinderDirtinessInformation() const = 0; virtual void FlushAIPathfinderDirtinessInformation() = 0; /** * Get a grid representing the distance to the shore of the terrain tile. */ virtual Grid ComputeShoreGrid(bool expandOnWater = false) = 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; /* * Request a long-path computation immediately */ virtual void ComputePathImmediate(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret) const = 0; /** * 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. */ 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) = 0; /* * Request a short-path computation immediately. */ virtual WaypointPath ComputeShortPathImmediate(const ShortPathRequest& request) const = 0; /** * If the debug overlay is enabled, render the path that will computed by ComputePath. */ virtual void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) = 0; /** * @return true if the goal is reachable from (x0, z0) for the given passClass, false otherwise. * Warning: this is synchronous, somewhat expensive and not should not be called too liberally. */ virtual bool IsGoalReachable(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) = 0; /** * Check whether the given movement line is valid and doesn't hit any obstructions * or impassable terrain. * Returns true if the movement is okay. */ 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 = 0; /** * Check whether a unit placed here is valid and doesn't hit any obstructions * or impassable terrain. * When onlyCenterPoint = true, only check the center tile of the unit * @return ICmpObstruction::FOUNDATION_CHECK_SUCCESS if the placement is okay, else * a value describing the type of failure. */ 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 = false) const = 0; /** * Check whether a building placed here is valid and doesn't hit any obstructions * or impassable terrain. * @return ICmpObstruction::FOUNDATION_CHECK_SUCCESS if the placement is okay, else * a value describing the type of failure. */ 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 = 0; /** * Check whether a building placed here is valid and doesn't hit any obstructions * or impassable terrain. * when onlyCenterPoint = true, only check the center tile of the building * @return ICmpObstruction::FOUNDATION_CHECK_SUCCESS if the placement is okay, else * a value describing the type of failure. */ 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 = 0; /** * Toggle the storage and rendering of debug info. */ virtual void SetDebugOverlay(bool enabled) = 0; /** * Toggle the storage and rendering of debug info for the hierarchical pathfinder. */ virtual void SetHierDebugOverlay(bool enabled) = 0; /** * Finish computing asynchronous path requests and send the CMessagePathResult messages. */ - virtual void FetchAsyncResultsAndSendMessages() = 0; + virtual void SendRequestedPaths() = 0; /** * Tell asynchronous pathfinder threads that they can begin computing paths. */ virtual void StartProcessingMoves(bool useMax) = 0; /** * Regenerates the grid based on the current obstruction list, if necessary */ virtual void UpdateGrid() = 0; /** * Returns some stats about the last ComputePath. */ virtual void GetDebugData(u32& steps, double& time, Grid& grid) const = 0; /** * Sets up the pathfinder passability overlay in Atlas. */ virtual void SetAtlasOverlay(bool enable, pass_class_t passClass = 0) = 0; DECLARE_INTERFACE_TYPE(Pathfinder) }; #endif // INCLUDED_ICMPPATHFINDER