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