Index: ps/trunk/binaries/data/mods/public/gui/credits/texts/programming.json =================================================================== --- ps/trunk/binaries/data/mods/public/gui/credits/texts/programming.json (revision 25656) +++ ps/trunk/binaries/data/mods/public/gui/credits/texts/programming.json (revision 25657) @@ -1,292 +1,293 @@ { "Title": "Programming", "Content": [ { "Title": "Programming managers", "List": [ { "nick": "Acumen", "name": "Stuart Walpole" }, { "nick": "Dak Lozar", "name": "Dave Loeser" }, { "nick": "h20", "name": "Daniel Wilhelm" }, { "nick": "Janwas", "name": "Jan Wassenberg" }, { "nick": "Raj", "name": "Raj Sharma" } ] }, { "Subtitle": "Special thanks to", "List": [ { "nick": "leper", "name": "Georg Kilzer" }, { "nick": "Ykkrosh", "name": "Philip Taylor" } ] }, { "List": [ { "nick": "01d55" }, { "nick": "aBothe", "name": "Alexander Bothe" }, { "nick": "Acumen", "name": "Stuart Walpole" }, { "nick": "adrian", "name": "Adrian Boguszewszki" }, { "name": "Adrian Fatol" }, { "nick": "AI-Amsterdam" }, { "nick": "Alan", "name": "Alan Kemp" }, { "nick": "Alex", "name": "Alexander Yakobovich" }, { "nick": "alpha123", "name": "Peter P. Cannici" }, { "nick": "Ampaex", "name": "Antonio Vazquez" }, { "name": "André Puel" }, { "nick": "andy5995", "name": "Andy Alt" }, { "nick": "Angen" }, { "nick": "Arfrever", "name": "Arfrever Frehtes Taifersar Arahesis" }, { "nick": "ArnH", "name": "Arno Hemelhof" }, { "nick": "Aurium", "name": "Aurélio Heckert" }, { "nick": "azayrahmad", "name": "Aziz Rahmad" }, { "nick": "badmadblacksad", "name": "Martin F" }, { "nick": "badosu", "name": "Amadeus Folego" }, { "nick": "bb", "name": "Bouke Jansen" }, { "nick": "Bellaz89", "name": "Andrea Bellandi" }, { "nick": "Ben", "name": "Ben Vinegar" }, { "nick": "Bird" }, { "nick": "Blue", "name": "Richard Welsh" }, { "nick": "bmwiedemann" }, { "nick": "boeseRaupe", "name": "Michael Kluge" }, { "nick": "bog_dan_ro", "name": "BogDan Vatra" }, { "nick": "Bonk", "name": "Christopher Ebbert" }, { "nick": "Boudica" }, { "nick": "Caius", "name": "Lars Kemmann" }, { "nick": "Calefaction", "name": "Matt Holmes" }, { "nick": "Calvinh", "name": "Carl-Johan Höiby" }, { "nick": "causative", "name": "Bart Parkis" }, { "name": "Cédric Houbart" }, { "nick": "Chakakhan", "name": "Kenny Long" }, { "nick": "Clockwork-Muse", "name": "Stephen A. Imhoff" }, { "nick": "cpc", "name": "Clément Pit-Claudel" }, { "nick": "Cracker78", "name": "Chad Heim" }, { "nick": "Crynux", "name": "Stephen J. Fewer" }, { "nick": "cwprogger" }, { "nick": "cygal", "name": "Quentin Pradet" }, { "nick": "Dak Lozar", "name": "Dave Loeser" }, { "nick": "dalerank", "name": "Sergey Kushnirenko" }, { "nick": "dan", "name": "Dan Strandberg" }, { "nick": "DanCar", "name": "Daniel Cardenas" }, { "nick": "danger89", "name": "Melroy van den Berg" }, { "name": "Daniel Trevitz" }, { "nick": "Dariost", "name": "Dario Ostuni" }, { "nick": "Dave", "name": "David Protasowski" }, { "name": "David Marshall" }, { "nick": "dax", "name": "Dacian Fiordean" }, { "nick": "deebee", "name": "Deepak Anthony" }, { "nick": "Deiz" }, { "nick": "Dietger", "name": "Dietger van Antwerpen" }, { "nick": "DigitalSeraphim", "name": "Nick Owens" }, { "nick": "dp304" }, { "nick": "dpiquet", "name": "Damien Piquet" }, { "nick": "dumbo" }, { "nick": "Dunedan", "name": "Daniel Roschka" }, { "nick": "dvangennip", "name": "Doménique" }, { "nick": "DynamoFox" }, { "nick": "Echelon9", "name": "Rhys Kidd" }, { "nick": "echotangoecho" }, { "nick": "eihrul", "name": "Lee Salzman" }, { "nick": "elexis", "name": "Alexander Heinsius" }, { "nick": "EmjeR", "name": "Matthijs de Rijk" }, { "nick": "EMontana" }, { "nick": "ericb" }, { "nick": "evanssthomas", "name": "Evans Thomas" }, { "nick": "Evulant", "name": "Alexander S." }, { "nick": "fabio", "name": "Fabio Pedretti" }, { "nick": "falsevision", "name": "Mahdi Khodadadifard" }, { "nick": "fatherbushido", "name": "Nicolas Tisserand" }, { "nick": "fcxSanya", "name": "Alexander Olkhovskiy" }, { "nick": "FeXoR", "name": "Florian Finke" }, { "nick": "Fire Giant", "name": "Malte Schwarzkopf" }, { "name": "Fork AD" }, { "nick": "fpre", "name": "Frederick Stallmeyer" }, { "nick": "Freagarach" }, { "nick": "freenity", "name": "Anton Galitch" }, { "nick": "Gallaecio", "name": "Adrián Chaves" }, { "nick": "gbish (aka Iny)", "name": "Grant Bishop" }, { "nick": "Gee", "name": "Gustav Larsson" }, { "nick": "Gentz", "name": "Hal Gentz" }, { "nick": "gerbilOFdoom" }, { "nick": "godlikeldh" }, { "nick": "greybeard", "name": "Joe Cocovich" }, { "nick": "grillaz" }, { "nick": "Grugnas", "name": "Giuseppe Tranchese" }, { "nick": "gudo" }, { "nick": "Guuts", "name": "Matthew Guttag" }, { "nick": "h20", "name": "Daniel Wilhelm" }, { "nick": "Hannibal_Barca", "name": "Clive Juhász S." }, { "nick": "Haommin" }, { "nick": "happyconcepts", "name": "Ben Bird" }, { "nick": "historic_bruno", "name": "Ben Brian" }, { "nick": "idanwin" }, { "nick": "Imarok", "name": "J. S." }, { "nick": "Inari" }, { "nick": "infyquest", "name": "Vijay Kiran Kamuju" }, { "nick": "irishninja", "name": "Brian Broll" }, { "nick": "IronNerd", "name": "Matthew McMullan" }, { "nick": "Itms", "name": "Nicolas Auvray" }, { "nick": "Jaison", "name": "Marco tom Suden" }, { "nick": "jammus", "name": "James Scott" }, { "nick": "Janwas", "name": "Jan Wassenberg" }, { "nick": "javiergodas", "name": "Javier Godas Vieitez" }, { "nick": "JCWasmx86" }, { "nick": "Jgwman" }, { "nick": "JonBaer", "name": "Jon Baer" }, { "nick": "Josh", "name": "Joshua J. Bakita" }, { "nick": "joskar", "name": "Johnny Oskarsson" }, { "nick": "jP_wanN", "name": "Jonas Platte" }, { "nick": "Jubalbarca", "name": "James Baillie" }, { "nick": "JubJub", "name": "Sebastian Vetter" }, { "nick": "jurgemaister" }, { "nick": "kabzerek", "name": "Grzegorz Kabza" }, { "nick": "Kai", "name": "Kai Chen" }, { "name": "Kareem Ergawy" }, { "nick": "kevmo", "name": "Kevin Caffrey" }, { "nick": "kezz", "name": "Graeme Kerry" }, { "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": "Langbart" }, { "nick": "LeanderH", "name": "Leander Hemelhof" }, { "nick": "leper", "name": "Georg Kilzer" }, { "nick": "Link Mauve", "name": "Emmanuel Gil Peyrot" }, { "nick": "LittleDev" }, { "nick": "livingaftermidnight", "name": "Will Dull" }, { "nick": "lonehawk", "name": "Vignesh Krishnan" }, { "nick": "Louhike" }, { "nick": "lsdh" }, { "nick": "Ludovic", "name": "Ludovic Rousseau" }, { "nick": "luiko", "name": "Luis Carlos Garcia Barajas" }, { "nick": "m0l0t0ph", "name": "Christoph Gielisch" }, { "nick": "madmax", "name": "Abhijit Nandy" }, { "nick": "madpilot", "name": "Guido Falsi" }, { "nick": "mammadori", "name": "Marco Amadori" }, { "nick": "marder", "name": "Stefan R. F." }, { "nick": "markcho" }, { "nick": "MarkT", "name": "Mark Thompson" }, { "nick": "Markus" }, { "nick": "Mate-86", "name": "Mate Kovacs" }, { "nick": "Matei", "name": "Matei Zaharia" }, { "nick": "MattDoerksen", "name": "Matt Doerksen" }, { "nick": "mattlott", "name": "Matt Lott" }, { "nick": "maveric", "name": "Anton Protko" }, { "nick": "Micnasty", "name": "Travis Gorkin" }, { "name": "Mikołaj \"Bajter\" Korcz" }, { "nick": "mimo" }, { "nick": "mk12", "name": "Mitchell Kember" }, { "nick": "mmayfield45", "name": "Michael Mayfield" }, { "nick": "mmoanis", "name": "Mohamed Moanis" }, { "nick": "Molotov", "name": "Dario Alvarez" }, { "nick": "mpmoreti", "name": "Marcos Paulo Moreti" }, { "nick": "mreiland", "name": "Michael Reiland" }, { "nick": "myconid" }, { "nick": "n1xc0d3r", "name": "Luis Guerrero" }, { "nick": "nani", "name": "S. N." }, { "nick": "nd3c3nt", "name": "Gavin Fowler" }, { "nick": "nephele" }, { "nick": "Nescio" }, { "nick": "niektb", "name": "Niek ten Brinke" }, { "nick": "nikagra", "name": "Mikita Hradovich" }, { "nick": "njm" }, { "nick": "NoMonkey", "name": "John Mena" }, { "nick": "norsnor" }, { "nick": "notpete", "name": "Rich Cross" }, { "nick": "nwtour" }, { "nick": "odoaker", "name": "Ágoston Sipos" }, { "nick": "Offensive ePeen", "name": "Jared Ryan Bills" }, { "nick": "Ols", "name": "Oliver Whiteman" }, { "nick": "olsner", "name": "Simon Brenner" }, { "nick": "OptimusShepard", "name": "Pirmin Stanglmeier" }, { "nick": "otero" }, { "nick": "Palaxin", "name": "David A. Freitag" }, { "name": "Paul Withers" }, { "nick": "paulobezerr", "name": "Paulo George Gomes Bezerra" }, { "nick": "pcpa", "name": "Paulo Andrade" }, { "nick": "Pendingchaos" }, { "nick": "PeteVasi", "name": "Pete Vasiliauskas" }, { "nick": "pilino1234" }, { "nick": "PingvinBetyar", "name": "Schronk Tamás" }, { "nick": "plugwash", "name": "Peter Michael Green" }, { "nick": "Polakrity" }, { "nick": "Poya", "name": "Poya Manouchehri" }, { "nick": "prefect", "name": "Nicolai Hähnle" }, { "nick": "Prodigal Son" }, { "nick": "pstumpf", "name": "Pascal Stumpf" }, { "nick": "pyrolink", "name": "Andrew Decker" }, { "nick": "quantumstate", "name": "Jonathan Waller" }, { "nick": "QuickShot", "name": "Walter Krawec" }, { "nick": "quonter" }, { "nick": "qwertz" }, { "nick": "Radagast" }, { "nick": "Raj", "name": "Raj Sharma" }, { "nick": "ramtzok1", "name": "Ram" }, { "nick": "rapidelectron", "name": "Christian Weihsbach" }, { "nick": "r-a-sattarov", "name": "Ramil Sattarov" }, { "nick": "RedFox", "name": "Jorma Rebane" }, { "nick": "RefinedCode" }, { "nick": "Riemer" }, { "name": "Rolf Sievers" }, { "nick": "s0600204", "name": "Matthew Norwood" }, { "nick": "sacha_vrand", "name": "Sacha Vrand" }, { "nick": "SafaAlfulaij" }, { "name": "Samuel Guarnieri" }, { "nick": "Samulis", "name": "Sam Gossner" }, { "nick": "Sandarac" }, { "nick": "sanderd17", "name": "Sander Deryckere" }, { "nick": "sathyam", "name": "Sathyam Vellal" }, { "nick": "sbirmi", "name": "Sharad Birmiwal" }, { "nick": "sbte", "name": "Sven Baars" }, { "nick": "scroogie", "name": "André Gemünd" }, { "nick": "scythetwirler", "name": "Casey X." }, { "nick": "serveurix" }, { "nick": "Shane", "name": "Shane Grant" }, { "nick": "shh" }, { "nick": "Silk", "name": "Josh Godsiff" }, { "nick": "silure" }, { "nick": "Simikolon", "name": "Yannick & Simon" }, { "nick": "smiley", "name": "M. L." }, { "nick": "Spahbod", "name": "Omid Davoodi" }, { "nick": "Stan", "name": "Stanislas Dolcini" }, { "nick": "Stefan" }, { "nick": "StefanBruens", "name": "Stefan Brüns" }, { "nick": "stilz", "name": "Sławomir Zborowski" }, { "nick": "stwf", "name": "Steven Fuchs" }, { "nick": "svott", "name": "Sven Ott" }, { "nick": "t4nk004" }, { "nick": "tau" }, { "nick": "tbm", "name": "Martin Michlmayr" }, { "nick": "Teiresias" }, { "nick": "temple" }, { "nick": "texane" }, { "nick": "thamlett", "name": "Timothy Hamlett" }, { "nick": "thedrunkyak", "name": "Dan Fuhr" }, { "nick": "Tobbi" }, { "nick": "Toonijn", "name": "Toon Baeyens" }, { "nick": "TrinityDeath", "name": "Jethro Lu" }, { "nick": "triumvir", "name": "Corin Schedler" }, { "nick": "trompetin17", "name": "Juan Guillermo" }, { "nick": "tpearson", "name": "Timothy Pearson" }, { "nick": "user1", "name": "A. C." }, { "nick": "usey11" }, { "nick": "vincent_c", "name": "Vincent Cheng" }, { "nick": "vinhig", "name": "Vincent Higginson" }, { "nick": "vladislavbelov", "name": "Vladislav Belov" }, { "nick": "voroskoi" }, { "nick": "vts", "name": "Jeroen DR" }, { "nick": "wacko", "name": "Andrew Spiering" }, { "nick": "WhiteTreePaladin", "name": "Brian Ashley" }, { "nick": "wraitii", "name": "Lancelot de Ferrière le Vayer" }, { "nick": "Xentelian", "name": "Mark Strawson" }, { "nick": "Xienen", "name": "Dayle Flowers" }, { "nick": "xtizer", "name": "Matt Green" }, { "nick": "yashi", "name": "Yasushi Shoji" }, { "nick": "Ykkrosh", "name": "Philip Taylor" }, { "nick": "Yves" }, { "nick": "Zeusthor", "name": "Jeffrey Tavares" }, { "nick": "zoot" }, { "nick": "zsol", "name": "Zsolt Dollenstein" }, { "nick": "ztamas", "name": "Tamas Zolnai" }, { "nick": "Zyi", "name": "Charles De Meulenaer" } ] } ] } Index: ps/trunk/binaries/data/mods/public/simulation/data/pathfinder.xml =================================================================== --- ps/trunk/binaries/data/mods/public/simulation/data/pathfinder.xml (revision 25656) +++ ps/trunk/binaries/data/mods/public/simulation/data/pathfinder.xml (revision 25657) @@ -1,81 +1,81 @@ - 64 + 20 1.6 pathfinding 2 1.0 0.8 pathfinding 2 1.0 3.0 pathfinding 1 10.0 pathfinding 1 3.0 foundation 0 4.0 1.0 foundation 8.0 1.25 none none 2 1.0 none 1 Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 25656) +++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 25657) @@ -1,924 +1,954 @@ /* 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_GridSize = 0; m_Grid = NULL; m_TerrainOnlyGrid = NULL; FlushAIPathfinderDirtinessInformation(); m_NextAsyncTicket = 1; m_AtlasOverlay = NULL; - m_VertexPathfinder = std::make_unique(m_GridSize, m_TerrainOnlyGrid); + size_t workerThreads = Threading::TaskManager::Instance().GetNumberOfWorkers(); + // Store one vertex pathfinder for each thread (including the main thread). + while (m_VertexPathfinders.size() < workerThreads + 1) + m_VertexPathfinders.emplace_back(m_GridSize, m_TerrainOnlyGrid); m_LongPathfinder = std::make_unique(); m_PathfinderHier = std::make_unique(); + // Set up one future for each worker thread. + m_Futures.resize(workerThreads); + // 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"); // Paths are computed: // - Before MT_Update // - Before MT_MotionUnitFormation - // - 'in-between' turns (effectively at the start until threading is implemented). + // - asynchronously between turn end and turn start. // 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). + // to avoid spending too much time there (since the latter are threaded and thus much 'cheaper'). // 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; } } CCmpPathfinder::~CCmpPathfinder() {}; void CCmpPathfinder::Deinit() { SetDebugOverlay(false); // cleans up memory + + // Wait on all pathfinding tasks. + for (Future& future : m_Futures) + future.Cancel(); + m_Futures.clear(); + 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.m_Requests); Serializer(serialize, "short requests", m_ShortPathRequests.m_Requests); serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket); serialize.NumberU16_Unbounded("grid size", m_GridSize); } 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.m_Requests.empty() || !m_LongPathRequests.m_Requests.empty()) { ENSURE(CmpPtr(GetSystemEntity())); StartProcessingMoves(false); } break; } } void CCmpPathfinder::RenderSubmit(SceneCollector& collector) { g_VertexPathfinderDebugOverlay.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) { g_VertexPathfinderDebugOverlay.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; u16 shoreGridSize = terrain.GetTilesPerSide(); // First pass - find underwater tiles Grid waterGrid(shoreGridSize, shoreGridSize); for (u16 j = 0; j < shoreGridSize; ++j) { for (u16 i = 0; i < shoreGridSize; ++i) { fixed x, z; Pathfinding::TerrainTileCenter(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(shoreGridSize, shoreGridSize); for (u16 j = 0; j < shoreGridSize; ++j) { for (u16 i = 0; i < shoreGridSize; ++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 < shoreGridSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1)) || (i < shoreGridSize-1 && waterGrid.get(i+1, j)) || (i < shoreGridSize-1 && j < shoreGridSize-1 && waterGrid.get(i+1, j+1)) || (i < shoreGridSize-1 && j > 0 && waterGrid.get(i+1, j-1)) || (j > 0 && waterGrid.get(i, j-1)) || (j < shoreGridSize-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 < shoreGridSize; ++y) { u16 min = shoreMax; for (u16 x = 0; x < shoreGridSize; ++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 = shoreGridSize; 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 < shoreGridSize; ++x) { u16 min = shoreMax; for (u16 y = 0; y < shoreGridSize; ++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 = shoreGridSize; 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 gridSize = cmpTerrain->GetMapSize() / Pathfinding::NAVCELL_SIZE_INT; if (gridSize == 0) return; // If the terrain was resized then delete the old grid data if (m_Grid && m_GridSize != gridSize) { SAFE_DELETE(m_Grid); SAFE_DELETE(m_TerrainOnlyGrid); } // Initialise the terrain data when first needed if (!m_Grid) { m_GridSize = gridSize; m_Grid = new Grid(m_GridSize, m_GridSize); SAFE_DELETE(m_TerrainOnlyGrid); m_TerrainOnlyGrid = new Grid(m_GridSize, m_GridSize); m_DirtinessInformation = { true, true, Grid(m_GridSize, m_GridSize) }; 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_GridSize, m_GridSize)); #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 gridSize = cmpTerrain->GetMapSize() / Pathfinding::NAVCELL_SIZE_INT; if (gridSize == 0) return; const bool needsNewTerrainGrid = !m_TerrainOnlyGrid || m_GridSize != gridSize; if (needsNewTerrainGrid) { m_GridSize = gridSize; SAFE_DELETE(m_TerrainOnlyGrid); m_TerrainOnlyGrid = new Grid(m_GridSize, m_GridSize); // 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_GridSize, m_GridSize); m_DirtinessInformation = { true, true, Grid(m_GridSize, m_GridSize) }; 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_GridSize; int jstart = 0, jend = m_GridSize; 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, m_GridSize); iend = Clamp(itile1 + 1, 0, m_GridSize); jstart = Clamp(jtile0 - 1, 0, m_GridSize); jend = Clamp(jtile1 + 1, 0, m_GridSize); } // 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_TERRAIN_TILE; int jtile = j / Pathfinding::NAVCELLS_PER_TERRAIN_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_TERRAIN_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); } } ////////////////////////////////////////////////////////// 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.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.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())); + return m_VertexPathfinders.front().ComputeShortPath(request, CmpPtr(GetSystemEntity())); } template template void CCmpPathfinder::PathRequests::Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder) { 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); } void CCmpPathfinder::SendRequestedPaths() { PROFILE2("SendRequestedPaths"); if (!m_LongPathRequests.m_ComputeDone || !m_ShortPathRequests.m_ComputeDone) { - m_ShortPathRequests.Compute(*this, *m_VertexPathfinder); + // Also start computing on the main thread to finish faster. + m_ShortPathRequests.Compute(*this, m_VertexPathfinders.front()); m_LongPathRequests.Compute(*this, *m_LongPathfinder); } + // We're done, clear futures. + // Use CancelOrWait instead of just Cancel to ensure determinism. + for (Future& future : m_Futures) + future.CancelOrWait(); { PROFILE2("PostMessages"); for (PathResult& path : m_ShortPathRequests.m_Results) { CMessagePathResult msg(path.ticket, path.path); GetSimContext().GetComponentManager().PostMessage(path.notify, msg); } for (PathResult& path : m_LongPathRequests.m_Results) { CMessagePathResult msg(path.ticket, path.path); GetSimContext().GetComponentManager().PostMessage(path.notify, msg); } } m_ShortPathRequests.ClearComputed(); m_LongPathRequests.ClearComputed(); } void CCmpPathfinder::StartProcessingMoves(bool useMax) { m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0); m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0); + + Threading::TaskManager& taskManager = Threading::TaskManager::Instance(); + for (size_t i = 0; i < m_Futures.size(); ++i) + { + ENSURE(!m_Futures[i].Valid()); + // Pass the i+1th vertex pathfinder to keep the first for the main thread, + // each thread get its own instance to avoid conflicts in cached data. + m_Futures[i] = taskManager.PushTask([&pathfinder=*this, &vertexPfr=m_VertexPathfinders[i + 1]]() { + PROFILE2("Async pathfinding"); + pathfinder.m_ShortPathRequests.Compute(pathfinder, vertexPfr); + pathfinder.m_LongPathRequests.Compute(pathfinder, *pathfinder.m_LongPathfinder); + }); + } } + ////////////////////////////////////////////////////////// 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_GridSize, m_GridSize); 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_GridSize, m_GridSize); 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 25656) +++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 25657) @@ -1,294 +1,298 @@ /* 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 "ps/TaskManager.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 { 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: // Lazily-constructed dynamic state (not serialized): u16 m_GridSize; // Navcells per side of the map. 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::vector m_VertexPathfinders; std::unique_ptr m_PathfinderHier; std::unique_ptr m_LongPathfinder; + // One per live asynchronous path computing task. + std::vector> m_Futures; + 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; + std::atomic m_NextPathToCompute = 0; // This is false until all scheduled paths have been computed. - bool m_ComputeDone = true; + std::atomic 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 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_TERRAIN_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/helpers/VertexPathfinder.h =================================================================== --- ps/trunk/source/simulation2/helpers/VertexPathfinder.h (revision 25656) +++ ps/trunk/source/simulation2/helpers/VertexPathfinder.h (revision 25657) @@ -1,141 +1,141 @@ /* 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_VERTEXPATHFINDER #define INCLUDED_VERTEXPATHFINDER #include "graphics/Overlay.h" #include "simulation2/helpers/Pathfinding.h" #include "simulation2/system/CmpPtr.h" #include #include // A vertex around the corners of an obstruction // (paths will be sequences of these vertexes) struct Vertex { enum { UNEXPLORED, OPEN, CLOSED, }; CFixedVector2D p; fixed g, h; u16 pred; u8 status; u8 quadInward : 4; // the quadrant which is inside the shape (or NONE) u8 quadOutward : 4; // the quadrants of the next point on the path which this vertex must be in, given 'pred' }; // Obstruction edges (paths will not cross any of these). // Defines the two points of the edge. struct Edge { CFixedVector2D p0, p1; }; // Axis-aligned obstruction squares (paths will not cross any of these). // Defines the opposing corners of an axis-aligned square // (from which four individual edges can be trivially computed), requiring p0 <= p1 struct Square { CFixedVector2D p0, p1; }; // Axis-aligned obstruction edges. // p0 defines one end; c1 is either the X or Y coordinate of the other end, // depending on the context in which this is used. struct EdgeAA { CFixedVector2D p0; fixed c1; }; class ICmpObstructionManager; class CSimContext; class SceneCollector; class VertexPathfinder { public: VertexPathfinder(const u16& gridSize, Grid* const & terrainOnlyGrid) : m_GridSize(gridSize), m_TerrainOnlyGrid(terrainOnlyGrid) {}; VertexPathfinder(const VertexPathfinder&) = delete; VertexPathfinder(VertexPathfinder&& o) : m_GridSize(o.m_GridSize), m_TerrainOnlyGrid(o.m_TerrainOnlyGrid) {} /** * Compute a precise path from the given point to the goal, and return the set of waypoints. * The path is based on the full set of obstructions that pass the filter, such that * a unit of clearance 'clearance' will be able to follow the path with no collisions. * The path is restricted to a box of radius 'range' from the starting point. * Defined in CCmpPathfinder_Vertex.cpp */ WaypointPath ComputeShortPath(const ShortPathRequest& request, CmpPtr cmpObstructionManager) const; private: // References to the Pathfinder for convenience. const u16& m_GridSize; Grid* const & m_TerrainOnlyGrid; // 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; // 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; // 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. }; /** - * If there are several vertex pathfinders running asynchronously, their debug output might conflict. - * To remain thread-safe, this single class will handle the debug data. + * There are several vertex pathfinders running asynchronously, so their debug output + * might conflict. To remain thread-safe, this single class will handle the debug data. * NB: though threadsafe, the way things are setup means you can have a few * more graphs and edges than you'd expect showing up in the rendered graph. */ class VertexPathfinderDebugOverlay { friend class VertexPathfinder; public: void SetDebugOverlay(bool enabled) { m_DebugOverlay = enabled; } void RenderSubmit(SceneCollector& collector); protected: void DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal); void DebugRenderGraph(const CSimContext& simContext, const std::vector& vertexes, const std::vector& edges, const std::vector& edgeSquares); void DebugRenderEdges(const CSimContext& simContext, bool visible, CFixedVector2D curr, CFixedVector2D npos); std::atomic m_DebugOverlay = false; // The data is double buffered: the first is the 'work-in-progress' state, the second the last RenderSubmit state. std::vector m_DebugOverlayShortPathLines; std::vector m_DebugOverlayShortPathLinesSubmitted; }; extern VertexPathfinderDebugOverlay g_VertexPathfinderDebugOverlay; #endif // INCLUDED_VERTEXPATHFINDER