Index: ps/trunk/source/simulation2/components/CCmpAIManager.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpAIManager.cpp (revision 22277)
+++ ps/trunk/source/simulation2/components/CCmpAIManager.cpp (revision 22278)
@@ -1,1189 +1,1199 @@
/* Copyright (C) 2018 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
#include "precompiled.h"
#include "simulation2/system/Component.h"
#include "ICmpAIManager.h"
#include "simulation2/MessageTypes.h"
#include "graphics/Terrain.h"
#include "lib/timer.h"
#include "lib/tex/tex.h"
#include "lib/allocators/shared_ptr.h"
#include "ps/CLogger.h"
#include "ps/Filesystem.h"
#include "ps/Profile.h"
#include "ps/scripting/JSInterface_VFS.h"
#include "ps/TemplateLoader.h"
#include "ps/Util.h"
#include "simulation2/components/ICmpAIInterface.h"
#include "simulation2/components/ICmpCommandQueue.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/components/ICmpRangeManager.h"
#include "simulation2/components/ICmpTemplateManager.h"
#include "simulation2/components/ICmpTerritoryManager.h"
+#include "simulation2/helpers/HierarchicalPathfinder.h"
#include "simulation2/helpers/LongPathfinder.h"
#include "simulation2/serialization/DebugSerializer.h"
#include "simulation2/serialization/StdDeserializer.h"
#include "simulation2/serialization/StdSerializer.h"
#include "simulation2/serialization/SerializeTemplates.h"
extern void QuitEngine();
/**
* @file
* Player AI interface.
* AI is primarily scripted, and the CCmpAIManager component defined here
* takes care of managing all the scripts.
*
* To avoid slow AI scripts causing jerky rendering, they are run in a background
* thread (maintained by CAIWorker) so that it's okay if they take a whole simulation
* turn before returning their results (though preferably they shouldn't use nearly
* that much CPU).
*
* CCmpAIManager grabs the world state after each turn (making use of AIInterface.js
* and AIProxy.js to decide what data to include) then passes it to CAIWorker.
* The AI scripts will then run asynchronously and return a list of commands to execute.
* Any attempts to read the command list (including indirectly via serialization)
* will block until it's actually completed, so the rest of the engine should avoid
* reading it for as long as possible.
*
* JS::Values are passed between the game and AI threads using ScriptInterface::StructuredClone.
*
* TODO: actually the thread isn't implemented yet, because performance hasn't been
* sufficiently problematic to justify the complexity yet, but the CAIWorker interface
* is designed to hopefully support threading when we want it.
*/
/**
* Implements worker thread for CCmpAIManager.
*/
class CAIWorker
{
private:
class CAIPlayer
{
NONCOPYABLE(CAIPlayer);
public:
CAIPlayer(CAIWorker& worker, const std::wstring& aiName, player_id_t player, u8 difficulty, const std::wstring& behavior,
shared_ptr scriptInterface) :
m_Worker(worker), m_AIName(aiName), m_Player(player), m_Difficulty(difficulty), m_Behavior(behavior),
m_ScriptInterface(scriptInterface), m_Obj(scriptInterface->GetJSRuntime())
{
}
bool Initialise()
{
// LoadScripts will only load each script once even though we call it for each player
if (!m_Worker.LoadScripts(m_AIName))
return false;
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
OsPath path = L"simulation/ai/" + m_AIName + L"/data.json";
JS::RootedValue metadata(cx);
m_Worker.LoadMetadata(path, &metadata);
if (metadata.isUndefined())
{
LOGERROR("Failed to create AI player: can't find %s", path.string8());
return false;
}
// Get the constructor name from the metadata
std::string moduleName;
std::string constructor;
JS::RootedValue objectWithConstructor(cx); // object that should contain the constructor function
JS::RootedValue global(cx, m_ScriptInterface->GetGlobalObject());
JS::RootedValue ctor(cx);
if (!m_ScriptInterface->HasProperty(metadata, "moduleName"))
{
LOGERROR("Failed to create AI player: %s: missing 'moduleName'", path.string8());
return false;
}
m_ScriptInterface->GetProperty(metadata, "moduleName", moduleName);
if (!m_ScriptInterface->GetProperty(global, moduleName.c_str(), &objectWithConstructor)
|| objectWithConstructor.isUndefined())
{
LOGERROR("Failed to create AI player: %s: can't find the module that should contain the constructor: '%s'", path.string8(), moduleName);
return false;
}
if (!m_ScriptInterface->GetProperty(metadata, "constructor", constructor))
{
LOGERROR("Failed to create AI player: %s: missing 'constructor'", path.string8());
return false;
}
// Get the constructor function from the loaded scripts
if (!m_ScriptInterface->GetProperty(objectWithConstructor, constructor.c_str(), &ctor)
|| ctor.isNull())
{
LOGERROR("Failed to create AI player: %s: can't find constructor '%s'", path.string8(), constructor);
return false;
}
m_ScriptInterface->GetProperty(metadata, "useShared", m_UseSharedComponent);
// Set up the data to pass as the constructor argument
JS::RootedValue settings(cx);
m_ScriptInterface->Eval(L"({})", &settings);
m_ScriptInterface->SetProperty(settings, "player", m_Player, false);
m_ScriptInterface->SetProperty(settings, "difficulty", m_Difficulty, false);
m_ScriptInterface->SetProperty(settings, "behavior", m_Behavior, false);
if (!m_UseSharedComponent)
{
ENSURE(m_Worker.m_HasLoadedEntityTemplates);
m_ScriptInterface->SetProperty(settings, "templates", m_Worker.m_EntityTemplates, false);
}
JS::AutoValueVector argv(cx);
argv.append(settings.get());
m_ScriptInterface->CallConstructor(ctor, argv, &m_Obj);
if (m_Obj.get().isNull())
{
LOGERROR("Failed to create AI player: %s: error calling constructor '%s'", path.string8(), constructor);
return false;
}
return true;
}
void Run(JS::HandleValue state, int playerID)
{
m_Commands.clear();
m_ScriptInterface->CallFunctionVoid(m_Obj, "HandleMessage", state, playerID);
}
// overloaded with a sharedAI part.
// javascript can handle both natively on the same function.
void Run(JS::HandleValue state, int playerID, JS::HandleValue SharedAI)
{
m_Commands.clear();
m_ScriptInterface->CallFunctionVoid(m_Obj, "HandleMessage", state, playerID, SharedAI);
}
void InitAI(JS::HandleValue state, JS::HandleValue SharedAI)
{
m_Commands.clear();
m_ScriptInterface->CallFunctionVoid(m_Obj, "Init", state, m_Player, SharedAI);
}
CAIWorker& m_Worker;
std::wstring m_AIName;
player_id_t m_Player;
u8 m_Difficulty;
std::wstring m_Behavior;
bool m_UseSharedComponent;
// Take care to keep this declaration before heap rooted members. Destructors of heap rooted
// members have to be called before the runtime destructor.
shared_ptr m_ScriptInterface;
JS::PersistentRootedValue m_Obj;
std::vector > m_Commands;
};
public:
struct SCommandSets
{
player_id_t player;
std::vector > commands;
};
CAIWorker() :
m_ScriptInterface(new ScriptInterface("Engine", "AI", g_ScriptRuntime)),
m_TurnNum(0),
m_CommandsComputed(true),
m_HasLoadedEntityTemplates(false),
m_HasSharedComponent(false),
m_SerializablePrototypes(new ObjectIdCache(g_ScriptRuntime)),
m_EntityTemplates(g_ScriptRuntime->m_rt),
m_SharedAIObj(g_ScriptRuntime->m_rt),
m_PassabilityMapVal(g_ScriptRuntime->m_rt),
m_TerritoryMapVal(g_ScriptRuntime->m_rt)
{
m_ScriptInterface->ReplaceNondeterministicRNG(m_RNG);
m_ScriptInterface->SetCallbackData(static_cast (this));
m_SerializablePrototypes->init();
JS_AddExtraGCRootsTracer(m_ScriptInterface->GetJSRuntime(), Trace, this);
m_ScriptInterface->RegisterFunction("PostCommand");
m_ScriptInterface->RegisterFunction("IncludeModule");
m_ScriptInterface->RegisterFunction("Exit");
m_ScriptInterface->RegisterFunction("ComputePath");
m_ScriptInterface->RegisterFunction, u32, u32, u32, CAIWorker::DumpImage>("DumpImage");
m_ScriptInterface->RegisterFunction("GetTemplate");
JSI_VFS::RegisterScriptFunctions_Simulation(*(m_ScriptInterface.get()));
// Globalscripts may use VFS script functions
m_ScriptInterface->LoadGlobalScripts();
}
~CAIWorker()
{
JS_RemoveExtraGCRootsTracer(m_ScriptInterface->GetJSRuntime(), Trace, this);
}
bool HasLoadedEntityTemplates() const { return m_HasLoadedEntityTemplates; }
bool LoadScripts(const std::wstring& moduleName)
{
// Ignore modules that are already loaded
if (m_LoadedModules.find(moduleName) != m_LoadedModules.end())
return true;
// Mark this as loaded, to prevent it recursively loading itself
m_LoadedModules.insert(moduleName);
// Load and execute *.js
VfsPaths pathnames;
if (vfs::GetPathnames(g_VFS, L"simulation/ai/" + moduleName + L"/", L"*.js", pathnames) < 0)
{
LOGERROR("Failed to load AI scripts for module %s", utf8_from_wstring(moduleName));
return false;
}
for (const VfsPath& path : pathnames)
{
if (!m_ScriptInterface->LoadGlobalScriptFile(path))
{
LOGERROR("Failed to load script %s", path.string8());
return false;
}
}
return true;
}
static void IncludeModule(ScriptInterface::CxPrivate* pCxPrivate, const std::wstring& name)
{
ENSURE(pCxPrivate->pCBData);
CAIWorker* self = static_cast (pCxPrivate->pCBData);
self->LoadScripts(name);
}
static void PostCommand(ScriptInterface::CxPrivate* pCxPrivate, int playerid, JS::HandleValue cmd)
{
ENSURE(pCxPrivate->pCBData);
CAIWorker* self = static_cast (pCxPrivate->pCBData);
self->PostCommand(playerid, cmd);
}
void PostCommand(int playerid, JS::HandleValue cmd)
{
for (size_t i=0; im_Player == playerid)
{
m_Players[i]->m_Commands.push_back(m_ScriptInterface->WriteStructuredClone(cmd));
return;
}
}
LOGERROR("Invalid playerid in PostCommand!");
}
static JS::Value ComputePath(ScriptInterface::CxPrivate* pCxPrivate,
JS::HandleValue position, JS::HandleValue goal, pass_class_t passClass)
{
ENSURE(pCxPrivate->pCBData);
CAIWorker* self = static_cast (pCxPrivate->pCBData);
JSContext* cx(self->m_ScriptInterface->GetContext());
JSAutoRequest rq(cx);
CFixedVector2D pos, goalPos;
std::vector waypoints;
JS::RootedValue retVal(cx);
self->m_ScriptInterface->FromJSVal(cx, position, pos);
self->m_ScriptInterface->FromJSVal(cx, goal, goalPos);
self->ComputePath(pos, goalPos, passClass, waypoints);
self->m_ScriptInterface->ToJSVal >(cx, &retVal, waypoints);
return retVal;
}
void ComputePath(const CFixedVector2D& pos, const CFixedVector2D& goal, pass_class_t passClass, std::vector& waypoints)
{
WaypointPath ret;
PathGoal pathGoal = { PathGoal::POINT, goal.X, goal.Y };
- m_LongPathfinder.ComputePath(pos.X, pos.Y, pathGoal, passClass, ret);
+ m_LongPathfinder.ComputePath(m_HierarchicalPathfinder, pos.X, pos.Y, pathGoal, passClass, ret);
for (Waypoint& wp : ret.m_Waypoints)
waypoints.emplace_back(wp.x, wp.z);
}
static CParamNode GetTemplate(ScriptInterface::CxPrivate* pCxPrivate, const std::string& name)
{
ENSURE(pCxPrivate->pCBData);
CAIWorker* self = static_cast (pCxPrivate->pCBData);
return self->GetTemplate(name);
}
CParamNode GetTemplate(const std::string& name)
{
if (!m_TemplateLoader.TemplateExists(name))
return CParamNode(false);
return m_TemplateLoader.GetTemplateFileData(name).GetChild("Entity");
}
static void ExitProgram(ScriptInterface::CxPrivate* UNUSED(pCxPrivate))
{
QuitEngine();
}
/**
* Debug function for AI scripts to dump 2D array data (e.g. terrain tile weights).
*/
static void DumpImage(ScriptInterface::CxPrivate* UNUSED(pCxPrivate), const std::wstring& name, const std::vector& data, u32 w, u32 h, u32 max)
{
// TODO: this is totally not threadsafe.
VfsPath filename = L"screenshots/aidump/" + name;
if (data.size() != w*h)
{
debug_warn(L"DumpImage: data size doesn't match w*h");
return;
}
if (max == 0)
{
debug_warn(L"DumpImage: max must not be 0");
return;
}
const size_t bpp = 8;
int flags = TEX_BOTTOM_UP|TEX_GREY;
const size_t img_size = w * h * bpp/8;
const size_t hdr_size = tex_hdr_size(filename);
shared_ptr buf;
AllocateAligned(buf, hdr_size+img_size, maxSectorSize);
Tex t;
if (t.wrap(w, h, bpp, flags, buf, hdr_size) < 0)
return;
u8* img = buf.get() + hdr_size;
for (size_t i = 0; i < data.size(); ++i)
img[i] = (u8)((data[i] * 255) / max);
tex_write(&t, filename);
}
void SetRNGSeed(u32 seed)
{
m_RNG.seed(seed);
}
bool TryLoadSharedComponent()
{
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
// we don't need to load it.
if (!m_HasSharedComponent)
return false;
// reset the value so it can be used to determine if we actually initialized it.
m_HasSharedComponent = false;
if (LoadScripts(L"common-api"))
m_HasSharedComponent = true;
else
return false;
// mainly here for the error messages
OsPath path = L"simulation/ai/common-api/";
// Constructor name is SharedScript, it's in the module API3
// TODO: Hardcoding this is bad, we need a smarter way.
JS::RootedValue AIModule(cx);
JS::RootedValue global(cx, m_ScriptInterface->GetGlobalObject());
JS::RootedValue ctor(cx);
if (!m_ScriptInterface->GetProperty(global, "API3", &AIModule) || AIModule.isUndefined())
{
LOGERROR("Failed to create shared AI component: %s: can't find module '%s'", path.string8(), "API3");
return false;
}
if (!m_ScriptInterface->GetProperty(AIModule, "SharedScript", &ctor)
|| ctor.isUndefined())
{
LOGERROR("Failed to create shared AI component: %s: can't find constructor '%s'", path.string8(), "SharedScript");
return false;
}
// Set up the data to pass as the constructor argument
JS::RootedValue settings(cx);
m_ScriptInterface->Eval(L"({})", &settings);
JS::RootedValue playersID(cx);
m_ScriptInterface->Eval(L"({})", &playersID);
for (size_t i = 0; i < m_Players.size(); ++i)
{
JS::RootedValue val(cx);
m_ScriptInterface->ToJSVal(cx, &val, m_Players[i]->m_Player);
m_ScriptInterface->SetPropertyInt(playersID, i, val, true);
}
m_ScriptInterface->SetProperty(settings, "players", playersID);
ENSURE(m_HasLoadedEntityTemplates);
m_ScriptInterface->SetProperty(settings, "templates", m_EntityTemplates, false);
JS::AutoValueVector argv(cx);
argv.append(settings);
m_ScriptInterface->CallConstructor(ctor, argv, &m_SharedAIObj);
if (m_SharedAIObj.get().isNull())
{
LOGERROR("Failed to create shared AI component: %s: error calling constructor '%s'", path.string8(), "SharedScript");
return false;
}
return true;
}
bool AddPlayer(const std::wstring& aiName, player_id_t player, u8 difficulty, const std::wstring& behavior)
{
shared_ptr ai(new CAIPlayer(*this, aiName, player, difficulty, behavior, m_ScriptInterface));
if (!ai->Initialise())
return false;
// this will be set to true if we need to load the shared Component.
if (!m_HasSharedComponent)
m_HasSharedComponent = ai->m_UseSharedComponent;
m_Players.push_back(ai);
return true;
}
bool RunGamestateInit(const shared_ptr& gameState, const Grid& passabilityMap, const Grid& territoryMap,
const std::map& nonPathfindingPassClassMasks, const std::map& pathfindingPassClassMasks)
{
// this will be run last by InitGame.js, passing the full game representation.
// For now it will run for the shared Component.
// This is NOT run during deserialization.
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
JS::RootedValue state(cx);
m_ScriptInterface->ReadStructuredClone(gameState, &state);
ScriptInterface::ToJSVal(cx, &m_PassabilityMapVal, passabilityMap);
ScriptInterface::ToJSVal(cx, &m_TerritoryMapVal, territoryMap);
m_PassabilityMap = passabilityMap;
m_NonPathfindingPassClasses = nonPathfindingPassClassMasks;
m_PathfindingPassClasses = pathfindingPassClassMasks;
- m_LongPathfinder.Reload(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks);
+ m_LongPathfinder.Reload(&m_PassabilityMap);
+ m_HierarchicalPathfinder.Recompute(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks);
if (m_HasSharedComponent)
{
m_ScriptInterface->SetProperty(state, "passabilityMap", m_PassabilityMapVal, true);
m_ScriptInterface->SetProperty(state, "territoryMap", m_TerritoryMapVal, true);
m_ScriptInterface->CallFunctionVoid(m_SharedAIObj, "init", state);
for (size_t i = 0; i < m_Players.size(); ++i)
{
if (m_HasSharedComponent && m_Players[i]->m_UseSharedComponent)
m_Players[i]->InitAI(state, m_SharedAIObj);
}
}
return true;
}
void UpdateGameState(const shared_ptr& gameState)
{
ENSURE(m_CommandsComputed);
m_GameState = gameState;
}
void UpdatePathfinder(const Grid& passabilityMap, bool globallyDirty, const Grid& dirtinessGrid, bool justDeserialized,
const std::map& nonPathfindingPassClassMasks, const std::map& pathfindingPassClassMasks)
{
ENSURE(m_CommandsComputed);
bool dimensionChange = m_PassabilityMap.m_W != passabilityMap.m_W || m_PassabilityMap.m_H != passabilityMap.m_H;
m_PassabilityMap = passabilityMap;
if (globallyDirty)
- m_LongPathfinder.Reload(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks);
+ {
+ m_LongPathfinder.Reload(&m_PassabilityMap);
+ m_HierarchicalPathfinder.Recompute(&m_PassabilityMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks);
+ }
else
- m_LongPathfinder.Update(&m_PassabilityMap, dirtinessGrid);
+ {
+ m_LongPathfinder.Update(&m_PassabilityMap);
+ m_HierarchicalPathfinder.Update(&m_PassabilityMap, dirtinessGrid);
+ }
JSContext* cx = m_ScriptInterface->GetContext();
if (dimensionChange || justDeserialized)
ScriptInterface::ToJSVal(cx, &m_PassabilityMapVal, m_PassabilityMap);
else
{
// Avoid a useless memory reallocation followed by a garbage collection.
JSAutoRequest rq(cx);
JS::RootedObject mapObj(cx, &m_PassabilityMapVal.toObject());
JS::RootedValue mapData(cx);
ENSURE(JS_GetProperty(cx, mapObj, "data", &mapData));
JS::RootedObject dataObj(cx, &mapData.toObject());
u32 length = 0;
ENSURE(JS_GetArrayLength(cx, dataObj, &length));
u32 nbytes = (u32)(length * sizeof(NavcellData));
JS::AutoCheckCannotGC nogc;
memcpy((void*)JS_GetUint16ArrayData(dataObj, nogc), m_PassabilityMap.m_Data, nbytes);
}
}
void UpdateTerritoryMap(const Grid& territoryMap)
{
ENSURE(m_CommandsComputed);
bool dimensionChange = m_TerritoryMap.m_W != territoryMap.m_W || m_TerritoryMap.m_H != territoryMap.m_H;
m_TerritoryMap = territoryMap;
JSContext* cx = m_ScriptInterface->GetContext();
if (dimensionChange)
ScriptInterface::ToJSVal(cx, &m_TerritoryMapVal, m_TerritoryMap);
else
{
// Avoid a useless memory reallocation followed by a garbage collection.
JSAutoRequest rq(cx);
JS::RootedObject mapObj(cx, &m_TerritoryMapVal.toObject());
JS::RootedValue mapData(cx);
ENSURE(JS_GetProperty(cx, mapObj, "data", &mapData));
JS::RootedObject dataObj(cx, &mapData.toObject());
u32 length = 0;
ENSURE(JS_GetArrayLength(cx, dataObj, &length));
u32 nbytes = (u32)(length * sizeof(u8));
JS::AutoCheckCannotGC nogc;
memcpy((void*)JS_GetUint8ArrayData(dataObj, nogc), m_TerritoryMap.m_Data, nbytes);
}
}
void StartComputation()
{
m_CommandsComputed = false;
}
void WaitToFinishComputation()
{
if (!m_CommandsComputed)
{
PerformComputation();
m_CommandsComputed = true;
}
}
void GetCommands(std::vector& commands)
{
WaitToFinishComputation();
commands.clear();
commands.resize(m_Players.size());
for (size_t i = 0; i < m_Players.size(); ++i)
{
commands[i].player = m_Players[i]->m_Player;
commands[i].commands = m_Players[i]->m_Commands;
}
}
void LoadEntityTemplates(const std::vector >& templates)
{
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
m_HasLoadedEntityTemplates = true;
m_ScriptInterface->Eval("({})", &m_EntityTemplates);
JS::RootedValue val(cx);
for (size_t i = 0; i < templates.size(); ++i)
{
templates[i].second->ToJSVal(cx, false, &val);
m_ScriptInterface->SetProperty(m_EntityTemplates, templates[i].first.c_str(), val, true);
}
}
void Serialize(std::ostream& stream, bool isDebug)
{
WaitToFinishComputation();
if (isDebug)
{
CDebugSerializer serializer(*m_ScriptInterface, stream);
serializer.Indent(4);
SerializeState(serializer);
}
else
{
CStdSerializer serializer(*m_ScriptInterface, stream);
// TODO: see comment in Deserialize()
serializer.SetSerializablePrototypes(m_SerializablePrototypes);
SerializeState(serializer);
}
}
void SerializeState(ISerializer& serializer)
{
if (m_Players.empty())
return;
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
std::stringstream rngStream;
rngStream << m_RNG;
serializer.StringASCII("rng", rngStream.str(), 0, 32);
serializer.NumberU32_Unbounded("turn", m_TurnNum);
serializer.Bool("useSharedScript", m_HasSharedComponent);
if (m_HasSharedComponent)
{
JS::RootedValue sharedData(cx);
if (!m_ScriptInterface->CallFunction(m_SharedAIObj, "Serialize", &sharedData))
LOGERROR("AI shared script Serialize call failed");
serializer.ScriptVal("sharedData", &sharedData);
}
for (size_t i = 0; i < m_Players.size(); ++i)
{
serializer.String("name", m_Players[i]->m_AIName, 1, 256);
serializer.NumberI32_Unbounded("player", m_Players[i]->m_Player);
serializer.NumberU8_Unbounded("difficulty", m_Players[i]->m_Difficulty);
serializer.String("behavior", m_Players[i]->m_Behavior, 1, 256);
serializer.NumberU32_Unbounded("num commands", (u32)m_Players[i]->m_Commands.size());
for (size_t j = 0; j < m_Players[i]->m_Commands.size(); ++j)
{
JS::RootedValue val(cx);
m_ScriptInterface->ReadStructuredClone(m_Players[i]->m_Commands[j], &val);
serializer.ScriptVal("command", &val);
}
bool hasCustomSerialize = m_ScriptInterface->HasProperty(m_Players[i]->m_Obj, "Serialize");
if (hasCustomSerialize)
{
JS::RootedValue scriptData(cx);
if (!m_ScriptInterface->CallFunction(m_Players[i]->m_Obj, "Serialize", &scriptData))
LOGERROR("AI script Serialize call failed");
serializer.ScriptVal("data", &scriptData);
}
else
{
serializer.ScriptVal("data", &m_Players[i]->m_Obj);
}
}
// AI pathfinder
SerializeMap()(serializer, "non pathfinding pass classes", m_NonPathfindingPassClasses);
SerializeMap()(serializer, "pathfinding pass classes", m_PathfindingPassClasses);
serializer.NumberU16_Unbounded("pathfinder grid w", m_PassabilityMap.m_W);
serializer.NumberU16_Unbounded("pathfinder grid h", m_PassabilityMap.m_H);
serializer.RawBytes("pathfinder grid data", (const u8*)m_PassabilityMap.m_Data,
m_PassabilityMap.m_W*m_PassabilityMap.m_H*sizeof(NavcellData));
}
void Deserialize(std::istream& stream, u32 numAis)
{
m_PlayerMetadata.clear();
m_Players.clear();
if (numAis == 0)
return;
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
ENSURE(m_CommandsComputed); // deserializing while we're still actively computing would be bad
CStdDeserializer deserializer(*m_ScriptInterface, stream);
std::string rngString;
std::stringstream rngStream;
deserializer.StringASCII("rng", rngString, 0, 32);
rngStream << rngString;
rngStream >> m_RNG;
deserializer.NumberU32_Unbounded("turn", m_TurnNum);
deserializer.Bool("useSharedScript", m_HasSharedComponent);
if (m_HasSharedComponent)
{
TryLoadSharedComponent();
JS::RootedValue sharedData(cx);
deserializer.ScriptVal("sharedData", &sharedData);
if (!m_ScriptInterface->CallFunctionVoid(m_SharedAIObj, "Deserialize", sharedData))
LOGERROR("AI shared script Deserialize call failed");
}
for (size_t i = 0; i < numAis; ++i)
{
std::wstring name;
player_id_t player;
u8 difficulty;
std::wstring behavior;
deserializer.String("name", name, 1, 256);
deserializer.NumberI32_Unbounded("player", player);
deserializer.NumberU8_Unbounded("difficulty",difficulty);
deserializer.String("behavior", behavior, 1, 256);
if (!AddPlayer(name, player, difficulty, behavior))
throw PSERROR_Deserialize_ScriptError();
u32 numCommands;
deserializer.NumberU32_Unbounded("num commands", numCommands);
m_Players.back()->m_Commands.reserve(numCommands);
for (size_t j = 0; j < numCommands; ++j)
{
JS::RootedValue val(cx);
deserializer.ScriptVal("command", &val);
m_Players.back()->m_Commands.push_back(m_ScriptInterface->WriteStructuredClone(val));
}
// TODO: this is yucky but necessary while the AIs are sharing data between contexts;
// ideally a new (de)serializer instance would be created for each player
// so they would have a single, consistent script context to use and serializable
// prototypes could be stored in their ScriptInterface
deserializer.SetSerializablePrototypes(m_DeserializablePrototypes);
bool hasCustomDeserialize = m_ScriptInterface->HasProperty(m_Players.back()->m_Obj, "Deserialize");
if (hasCustomDeserialize)
{
JS::RootedValue scriptData(cx);
deserializer.ScriptVal("data", &scriptData);
if (m_Players[i]->m_UseSharedComponent)
{
if (!m_ScriptInterface->CallFunctionVoid(m_Players.back()->m_Obj, "Deserialize", scriptData, m_SharedAIObj))
LOGERROR("AI script Deserialize call failed");
}
else if (!m_ScriptInterface->CallFunctionVoid(m_Players.back()->m_Obj, "Deserialize", scriptData))
{
LOGERROR("AI script deserialize() call failed");
}
}
else
{
deserializer.ScriptVal("data", &m_Players.back()->m_Obj);
}
}
// AI pathfinder
SerializeMap()(deserializer, "non pathfinding pass classes", m_NonPathfindingPassClasses);
SerializeMap()(deserializer, "pathfinding pass classes", m_PathfindingPassClasses);
u16 mapW, mapH;
deserializer.NumberU16_Unbounded("pathfinder grid w", mapW);
deserializer.NumberU16_Unbounded("pathfinder grid h", mapH);
m_PassabilityMap = Grid(mapW, mapH);
deserializer.RawBytes("pathfinder grid data", (u8*)m_PassabilityMap.m_Data, mapW*mapH*sizeof(NavcellData));
- m_LongPathfinder.Reload(&m_PassabilityMap, m_NonPathfindingPassClasses, m_PathfindingPassClasses);
+ m_LongPathfinder.Reload(&m_PassabilityMap);
+ m_HierarchicalPathfinder.Recompute(&m_PassabilityMap, m_NonPathfindingPassClasses, m_PathfindingPassClasses);
}
int getPlayerSize()
{
return m_Players.size();
}
void RegisterSerializablePrototype(std::wstring name, JS::HandleValue proto)
{
// Require unique prototype and name (for reverse lookup)
// TODO: this is yucky - see comment in Deserialize()
ENSURE(proto.isObject() && "A serializable prototype has to be an object!");
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
JS::RootedObject obj(cx, &proto.toObject());
if (m_SerializablePrototypes->has(obj) || m_DeserializablePrototypes.find(name) != m_DeserializablePrototypes.end())
{
LOGERROR("RegisterSerializablePrototype called with same prototype multiple times: p=%p n='%s'", (void *)obj.get(), utf8_from_wstring(name));
return;
}
m_SerializablePrototypes->add(cx, obj, name);
m_DeserializablePrototypes[name] = JS::Heap(obj);
}
private:
static void Trace(JSTracer *trc, void *data)
{
reinterpret_cast(data)->TraceMember(trc);
}
void TraceMember(JSTracer *trc)
{
for (std::pair>& prototype : m_DeserializablePrototypes)
JS_CallObjectTracer(trc, &prototype.second, "CAIWorker::m_DeserializablePrototypes");
for (std::pair>& metadata : m_PlayerMetadata)
JS_CallValueTracer(trc, &metadata.second, "CAIWorker::m_PlayerMetadata");
}
void LoadMetadata(const VfsPath& path, JS::MutableHandleValue out)
{
if (m_PlayerMetadata.find(path) == m_PlayerMetadata.end())
{
// Load and cache the AI player metadata
m_ScriptInterface->ReadJSONFile(path, out);
m_PlayerMetadata[path] = JS::Heap(out);
return;
}
out.set(m_PlayerMetadata[path].get());
}
void PerformComputation()
{
// Deserialize the game state, to pass to the AI's HandleMessage
JSContext* cx = m_ScriptInterface->GetContext();
JSAutoRequest rq(cx);
JS::RootedValue state(cx);
{
PROFILE3("AI compute read state");
m_ScriptInterface->ReadStructuredClone(m_GameState, &state);
m_ScriptInterface->SetProperty(state, "passabilityMap", m_PassabilityMapVal, true);
m_ScriptInterface->SetProperty(state, "territoryMap", m_TerritoryMapVal, true);
}
// It would be nice to do
// m_ScriptInterface->FreezeObject(state.get(), true);
// to prevent AI scripts accidentally modifying the state and
// affecting other AI scripts they share it with. But the performance
// cost is far too high, so we won't do that.
// If there is a shared component, run it
if (m_HasSharedComponent)
{
PROFILE3("AI run shared component");
m_ScriptInterface->CallFunctionVoid(m_SharedAIObj, "onUpdate", state);
}
for (size_t i = 0; i < m_Players.size(); ++i)
{
PROFILE3("AI script");
PROFILE2_ATTR("player: %d", m_Players[i]->m_Player);
PROFILE2_ATTR("script: %ls", m_Players[i]->m_AIName.c_str());
if (m_HasSharedComponent && m_Players[i]->m_UseSharedComponent)
m_Players[i]->Run(state, m_Players[i]->m_Player, m_SharedAIObj);
else
m_Players[i]->Run(state, m_Players[i]->m_Player);
}
}
// Take care to keep this declaration before heap rooted members. Destructors of heap rooted
// members have to be called before the runtime destructor.
shared_ptr m_ScriptRuntime;
shared_ptr m_ScriptInterface;
boost::rand48 m_RNG;
u32 m_TurnNum;
JS::PersistentRootedValue m_EntityTemplates;
bool m_HasLoadedEntityTemplates;
std::map > m_PlayerMetadata;
std::vector > m_Players; // use shared_ptr just to avoid copying
bool m_HasSharedComponent;
JS::PersistentRootedValue m_SharedAIObj;
std::vector m_Commands;
std::set m_LoadedModules;
shared_ptr m_GameState;
Grid m_PassabilityMap;
JS::PersistentRootedValue m_PassabilityMapVal;
Grid m_TerritoryMap;
JS::PersistentRootedValue m_TerritoryMapVal;
std::map m_NonPathfindingPassClasses;
std::map m_PathfindingPassClasses;
+ HierarchicalPathfinder m_HierarchicalPathfinder;
LongPathfinder m_LongPathfinder;
bool m_CommandsComputed;
shared_ptr > m_SerializablePrototypes;
std::map > m_DeserializablePrototypes;
CTemplateLoader m_TemplateLoader;
};
/**
* Implementation of ICmpAIManager.
*/
class CCmpAIManager : public ICmpAIManager
{
public:
static void ClassInit(CComponentManager& UNUSED(componentManager))
{
}
DEFAULT_COMPONENT_ALLOCATOR(AIManager)
static std::string GetSchema()
{
return "";
}
virtual void Init(const CParamNode& UNUSED(paramNode))
{
m_TerritoriesDirtyID = 0;
m_TerritoriesDirtyBlinkingID = 0;
m_JustDeserialized = false;
}
virtual void Deinit()
{
}
virtual void Serialize(ISerializer& serialize)
{
serialize.NumberU32_Unbounded("num ais", m_Worker.getPlayerSize());
// Because the AI worker uses its own ScriptInterface, we can't use the
// ISerializer (which was initialised with the simulation ScriptInterface)
// directly. So we'll just grab the ISerializer's stream and write to it
// with an independent serializer.
m_Worker.Serialize(serialize.GetStream(), serialize.IsDebug());
}
virtual void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
{
Init(paramNode);
u32 numAis;
deserialize.NumberU32_Unbounded("num ais", numAis);
if (numAis > 0)
LoadUsedEntityTemplates();
m_Worker.Deserialize(deserialize.GetStream(), numAis);
m_JustDeserialized = true;
}
virtual void AddPlayer(const std::wstring& id, player_id_t player, u8 difficulty, const std::wstring& behavior)
{
LoadUsedEntityTemplates();
m_Worker.AddPlayer(id, player, difficulty, behavior);
// AI players can cheat and see through FoW/SoD, since that greatly simplifies
// their implementation.
// (TODO: maybe cleverer AIs should be able to optionally retain FoW/SoD)
CmpPtr cmpRangeManager(GetSystemEntity());
if (cmpRangeManager)
cmpRangeManager->SetLosRevealAll(player, true);
}
virtual void SetRNGSeed(u32 seed)
{
m_Worker.SetRNGSeed(seed);
}
virtual void TryLoadSharedComponent()
{
m_Worker.TryLoadSharedComponent();
}
virtual void RunGamestateInit()
{
const ScriptInterface& scriptInterface = GetSimContext().GetScriptInterface();
JSContext* cx = scriptInterface.GetContext();
JSAutoRequest rq(cx);
CmpPtr cmpAIInterface(GetSystemEntity());
ENSURE(cmpAIInterface);
// Get the game state from AIInterface
// We flush events from the initialization so we get a clean state now.
JS::RootedValue state(cx);
cmpAIInterface->GetFullRepresentation(&state, true);
// Get the passability data
Grid dummyGrid;
const Grid* passabilityMap = &dummyGrid;
CmpPtr cmpPathfinder(GetSystemEntity());
if (cmpPathfinder)
passabilityMap = &cmpPathfinder->GetPassabilityGrid();
// Get the territory data
// Since getting the territory grid can trigger a recalculation, we check NeedUpdateAI first
Grid dummyGrid2;
const Grid* territoryMap = &dummyGrid2;
CmpPtr cmpTerritoryManager(GetSystemEntity());
if (cmpTerritoryManager && cmpTerritoryManager->NeedUpdateAI(&m_TerritoriesDirtyID, &m_TerritoriesDirtyBlinkingID))
territoryMap = &cmpTerritoryManager->GetTerritoryGrid();
LoadPathfinderClasses(state);
std::map nonPathfindingPassClassMasks, pathfindingPassClassMasks;
if (cmpPathfinder)
cmpPathfinder->GetPassabilityClasses(nonPathfindingPassClassMasks, pathfindingPassClassMasks);
m_Worker.RunGamestateInit(scriptInterface.WriteStructuredClone(state), *passabilityMap, *territoryMap, nonPathfindingPassClassMasks, pathfindingPassClassMasks);
}
virtual void StartComputation()
{
PROFILE("AI setup");
const ScriptInterface& scriptInterface = GetSimContext().GetScriptInterface();
JSContext* cx = scriptInterface.GetContext();
JSAutoRequest rq(cx);
if (m_Worker.getPlayerSize() == 0)
return;
CmpPtr cmpAIInterface(GetSystemEntity());
ENSURE(cmpAIInterface);
// Get the game state from AIInterface
JS::RootedValue state(cx);
if (m_JustDeserialized)
cmpAIInterface->GetFullRepresentation(&state, false);
else
cmpAIInterface->GetRepresentation(&state);
LoadPathfinderClasses(state); // add the pathfinding classes to it
// Update the game state
m_Worker.UpdateGameState(scriptInterface.WriteStructuredClone(state));
// Update the pathfinding data
CmpPtr cmpPathfinder(GetSystemEntity());
if (cmpPathfinder)
{
const GridUpdateInformation& dirtinessInformations = cmpPathfinder->GetAIPathfinderDirtinessInformation();
if (dirtinessInformations.dirty || m_JustDeserialized)
{
const Grid& passabilityMap = cmpPathfinder->GetPassabilityGrid();
std::map nonPathfindingPassClassMasks, pathfindingPassClassMasks;
cmpPathfinder->GetPassabilityClasses(nonPathfindingPassClassMasks, pathfindingPassClassMasks);
m_Worker.UpdatePathfinder(passabilityMap,
dirtinessInformations.globallyDirty, dirtinessInformations.dirtinessGrid, m_JustDeserialized,
nonPathfindingPassClassMasks, pathfindingPassClassMasks);
}
cmpPathfinder->FlushAIPathfinderDirtinessInformation();
}
// Update the territory data
// Since getting the territory grid can trigger a recalculation, we check NeedUpdateAI first
CmpPtr cmpTerritoryManager(GetSystemEntity());
if (cmpTerritoryManager && (cmpTerritoryManager->NeedUpdateAI(&m_TerritoriesDirtyID, &m_TerritoriesDirtyBlinkingID) || m_JustDeserialized))
{
const Grid& territoryMap = cmpTerritoryManager->GetTerritoryGrid();
m_Worker.UpdateTerritoryMap(territoryMap);
}
m_Worker.StartComputation();
m_JustDeserialized = false;
}
virtual void PushCommands()
{
std::vector commands;
m_Worker.GetCommands(commands);
CmpPtr cmpCommandQueue(GetSystemEntity());
if (!cmpCommandQueue)
return;
const ScriptInterface& scriptInterface = GetSimContext().GetScriptInterface();
JSContext* cx = scriptInterface.GetContext();
JSAutoRequest rq(cx);
JS::RootedValue clonedCommandVal(cx);
for (size_t i = 0; i < commands.size(); ++i)
{
for (size_t j = 0; j < commands[i].commands.size(); ++j)
{
scriptInterface.ReadStructuredClone(commands[i].commands[j], &clonedCommandVal);
cmpCommandQueue->PushLocalCommand(commands[i].player, clonedCommandVal);
}
}
}
private:
size_t m_TerritoriesDirtyID;
size_t m_TerritoriesDirtyBlinkingID;
bool m_JustDeserialized;
/**
* Load the templates of all entities on the map (called when adding a new AI player for a new game
* or when deserializing)
*/
void LoadUsedEntityTemplates()
{
if (m_Worker.HasLoadedEntityTemplates())
return;
CmpPtr cmpTemplateManager(GetSystemEntity());
ENSURE(cmpTemplateManager);
std::vector templateNames = cmpTemplateManager->FindUsedTemplates();
std::vector > usedTemplates;
usedTemplates.reserve(templateNames.size());
for (const std::string& name : templateNames)
{
const CParamNode* node = cmpTemplateManager->GetTemplateWithoutValidation(name);
if (node)
usedTemplates.emplace_back(name, node);
}
// Send the data to the worker
m_Worker.LoadEntityTemplates(usedTemplates);
}
void LoadPathfinderClasses(JS::HandleValue state)
{
CmpPtr cmpPathfinder(GetSystemEntity());
if (!cmpPathfinder)
return;
const ScriptInterface& scriptInterface = GetSimContext().GetScriptInterface();
JSContext* cx = scriptInterface.GetContext();
JSAutoRequest rq(cx);
JS::RootedValue classesVal(cx);
scriptInterface.Eval("({})", &classesVal);
std::map classes;
cmpPathfinder->GetPassabilityClasses(classes);
for (std::map::iterator it = classes.begin(); it != classes.end(); ++it)
scriptInterface.SetProperty(classesVal, it->first.c_str(), it->second, true);
scriptInterface.SetProperty(state, "passabilityClasses", classesVal, true);
}
CAIWorker m_Worker;
};
REGISTER_COMPONENT_TYPE(AIManager)
Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 22277)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 22278)
@@ -1,916 +1,930 @@
/* Copyright (C) 2019 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 "ps/CLogger.h"
#include "ps/CStr.h"
#include "ps/Profile.h"
#include "ps/XML/Xeromyces.h"
#include "renderer/Scene.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/Rasterize.h"
#include "simulation2/helpers/VertexPathfinder.h"
#include "simulation2/serialization/SerializeTemplates.h"
REGISTER_COMPONENT_TYPE(Pathfinder)
void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
{
m_MapSize = 0;
m_Grid = NULL;
m_TerrainOnlyGrid = NULL;
FlushAIPathfinderDirtinessInformation();
m_NextAsyncTicket = 1;
m_AtlasOverlay = NULL;
m_SameTurnMovesCount = 0;
m_VertexPathfinder = std::unique_ptr(new VertexPathfinder(m_MapSize, m_TerrainOnlyGrid));
+ m_LongPathfinder = std::unique_ptr(new LongPathfinder());
+ m_PathfinderHier = std::unique_ptr(new HierarchicalPathfinder());
// Register Relax NG validator
CXeromyces::AddValidator(g_VFS, "pathfinder", "simulation/data/pathfinder.rng");
// Since this is used as a system component (not loaded from an entity template),
// we can't use the real paramNode (it won't get handled properly when deserializing),
// so load the data from a special XML file.
CParamNode externalParamNode;
CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
// Previously all move commands during a turn were
// queued up and processed asynchronously at the start
// of the next turn. Now we are processing queued up
// events several times duing the turn. This improves
// responsiveness and units move more smoothly especially.
// when in formation. There is still a call at the
// beginning of a turn to process all outstanding moves -
// this will handle any moves above the MaxSameTurnMoves
// threshold.
//
// TODO - The moves processed at the beginning of the
// turn do not count against the maximum moves per turn
// currently. The thinking is that this will eventually
// happen in another thread. Either way this probably
// will require some adjustment and rethinking.
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
SAFE_DELETE(m_AtlasOverlay);
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);
}
struct SerializeLongRequest
{
template
void operator()(S& serialize, const char* UNUSED(name), AsyncLongPathRequest& value)
{
serialize.NumberU32_Unbounded("ticket", value.ticket);
serialize.NumberFixed_Unbounded("x0", value.x0);
serialize.NumberFixed_Unbounded("z0", value.z0);
SerializeGoal()(serialize, "goal", value.goal);
serialize.NumberU16_Unbounded("pass class", value.passClass);
serialize.NumberU32_Unbounded("notify", value.notify);
}
};
struct SerializeShortRequest
{
template
void operator()(S& serialize, const char* UNUSED(name), AsyncShortPathRequest& 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);
SerializeGoal()(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)
{
SerializeVector()(serialize, "long requests", m_AsyncLongPathRequests);
SerializeVector()(serialize, "short requests", m_AsyncShortPathRequests);
serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
serialize.NumberU16_Unbounded("same turn moves count", m_SameTurnMovesCount);
serialize.NumberU16_Unbounded("map size", m_MapSize);
}
void CCmpPathfinder::Serialize(ISerializer& serialize)
{
SerializeCommon(serialize);
}
void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
{
Init(paramNode);
SerializeCommon(deserialize);
}
void CCmpPathfinder::HandleMessage(const CMessage& msg, bool UNUSED(global))
{
switch (msg.GetType())
{
case MT_RenderSubmit:
{
const CMessageRenderSubmit& msgData = static_cast (msg);
RenderSubmit(msgData.collector);
break;
}
case MT_TerrainChanged:
m_TerrainDirty = true;
MinimalTerrainUpdate();
break;
case MT_WaterChanged:
case MT_ObstructionMapShapeChanged:
m_TerrainDirty = true;
UpdateGrid();
break;
case MT_TurnStart:
m_SameTurnMovesCount = 0;
break;
}
}
void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
{
m_VertexPathfinder->RenderSubmit(collector);
- m_LongPathfinder.HierarchicalRenderSubmit(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(x0, z0, goal, passClass);
+ m_LongPathfinder->SetDebugPath(*m_PathfinderHier, x0, z0, goal, passClass);
}
void CCmpPathfinder::SetDebugOverlay(bool enabled)
{
m_VertexPathfinder->SetDebugOverlay(enabled);
- m_LongPathfinder.SetDebugOverlay(enabled);
+ m_LongPathfinder->SetDebugOverlay(enabled);
}
void CCmpPathfinder::SetHierDebugOverlay(bool enabled)
{
- m_LongPathfinder.SetHierDebugOverlay(enabled, &GetSimContext());
+ m_PathfinderHier->SetDebugOverlay(enabled, &GetSimContext());
}
void CCmpPathfinder::GetDebugData(u32& steps, double& time, Grid& grid) const
{
- m_LongPathfinder.GetDebugData(steps, time, grid);
+ m_LongPathfinder->GetDebugData(steps, time, grid);
}
void CCmpPathfinder::SetAtlasOverlay(bool enable, pass_class_t passClass)
{
if (enable)
{
if (!m_AtlasOverlay)
m_AtlasOverlay = new AtlasOverlay(this, passClass);
m_AtlasOverlay->m_PassClass = passClass;
}
else
SAFE_DELETE(m_AtlasOverlay);
}
pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name) const
{
std::map::const_iterator it = m_PassClassMasks.find(name);
if (it == m_PassClassMasks.end())
{
LOGERROR("Invalid passability class name '%s'", name.c_str());
return 0;
}
return it->second;
}
void CCmpPathfinder::GetPassabilityClasses(std::map& passClasses) const
{
passClasses = m_PassClassMasks;
}
void CCmpPathfinder::GetPassabilityClasses(std::map& nonPathfindingPassClasses, std::map& pathfindingPassClasses) const
{
for (const std::pair& pair : m_PassClassMasks)
{
if ((GetPassabilityFromMask(pair.second)->m_Obstructions == PathfinderPassability::PATHFINDING))
pathfindingPassClasses[pair.first] = pair.second;
else
nonPathfindingPassClasses[pair.first] = pair.second;
}
}
const PathfinderPassability* CCmpPathfinder::GetPassabilityFromMask(pass_class_t passClass) const
{
for (const PathfinderPassability& passability : m_PassClasses)
{
if (passability.m_Mask == passClass)
return &passability;
}
return NULL;
}
const Grid& CCmpPathfinder::GetPassabilityGrid()
{
if (!m_Grid)
UpdateGrid();
return *m_Grid;
}
/**
* Given a grid of passable/impassable navcells (based on some passability mask),
* computes a new grid where a navcell is impassable (per that mask) if
* it is <=clearance navcells away from an impassable navcell in the original grid.
* The results are ORed onto the original grid.
*
* This is used for adding clearance onto terrain-based navcell passability.
*
* TODO PATHFINDER: might be nicer to get rounded corners by measuring clearances as
* Euclidean distances; currently it effectively does dist=max(dx,dy) instead.
* This would only really be a problem for big clearances.
*/
static void ExpandImpassableCells(Grid& grid, u16 clearance, pass_class_t mask)
{
PROFILE3("ExpandImpassableCells");
u16 w = grid.m_W;
u16 h = grid.m_H;
// First expand impassable cells horizontally into a temporary 1-bit grid
Grid tempGrid(w, h);
for (u16 j = 0; j < h; ++j)
{
// New cell (i,j) is blocked if (i',j) blocked for any i-clearance <= i' <= i+clearance
// Count the number of blocked cells around i=0
u16 numBlocked = 0;
for (u16 i = 0; i <= clearance && i < w; ++i)
if (!IS_PASSABLE(grid.get(i, j), mask))
++numBlocked;
for (u16 i = 0; i < w; ++i)
{
// Store a flag if blocked by at least one nearby cell
if (numBlocked)
tempGrid.set(i, j, 1);
// Slide the numBlocked window along:
// remove the old i-clearance value, add the new (i+1)+clearance
// (avoiding overflowing the grid)
if (i >= clearance && !IS_PASSABLE(grid.get(i-clearance, j), mask))
--numBlocked;
if (i+1+clearance < w && !IS_PASSABLE(grid.get(i+1+clearance, j), mask))
++numBlocked;
}
}
for (u16 i = 0; i < w; ++i)
{
// New cell (i,j) is blocked if (i,j') blocked for any j-clearance <= j' <= j+clearance
// Count the number of blocked cells around j=0
u16 numBlocked = 0;
for (u16 j = 0; j <= clearance && j < h; ++j)
if (tempGrid.get(i, j))
++numBlocked;
for (u16 j = 0; j < h; ++j)
{
// Add the mask if blocked by at least one nearby cell
if (numBlocked)
grid.set(i, j, grid.get(i, j) | mask);
// Slide the numBlocked window along:
// remove the old j-clearance value, add the new (j+1)+clearance
// (avoiding overflowing the grid)
if (j >= clearance && tempGrid.get(i, j-clearance))
--numBlocked;
if (j+1+clearance < h && tempGrid.get(i, j+1+clearance))
++numBlocked;
}
}
}
Grid CCmpPathfinder::ComputeShoreGrid(bool expandOnWater)
{
PROFILE3("ComputeShoreGrid");
CmpPtr cmpWaterManager(GetSystemEntity());
// TODO: these bits should come from ICmpTerrain
CTerrain& terrain = GetSimContext().GetTerrain();
// avoid integer overflow in intermediate calculation
const u16 shoreMax = 32767;
// First pass - find underwater tiles
Grid waterGrid(m_MapSize, m_MapSize);
for (u16 j = 0; j < m_MapSize; ++j)
{
for (u16 i = 0; i < m_MapSize; ++i)
{
fixed x, z;
Pathfinding::TileCenter(i, j, x, z);
bool underWater = cmpWaterManager && (cmpWaterManager->GetWaterLevel(x, z) > terrain.GetExactGroundLevelFixed(x, z));
waterGrid.set(i, j, underWater ? 1 : 0);
}
}
// Second pass - find shore tiles
Grid shoreGrid(m_MapSize, m_MapSize);
for (u16 j = 0; j < m_MapSize; ++j)
{
for (u16 i = 0; i < m_MapSize; ++i)
{
// Find a land tile
if (!waterGrid.get(i, j))
{
// If it's bordered by water, it's a shore tile
if ((i > 0 && waterGrid.get(i-1, j)) || (i > 0 && j < m_MapSize-1 && waterGrid.get(i-1, j+1)) || (i > 0 && j > 0 && waterGrid.get(i-1, j-1))
|| (i < m_MapSize-1 && waterGrid.get(i+1, j)) || (i < m_MapSize-1 && j < m_MapSize-1 && waterGrid.get(i+1, j+1)) || (i < m_MapSize-1 && j > 0 && waterGrid.get(i+1, j-1))
|| (j > 0 && waterGrid.get(i, j-1)) || (j < m_MapSize-1 && waterGrid.get(i, j+1))
)
shoreGrid.set(i, j, 0);
else
shoreGrid.set(i, j, shoreMax);
}
// If we want to expand on water, we want water tiles not to be shore tiles
else if (expandOnWater)
shoreGrid.set(i, j, shoreMax);
}
}
// Expand influences on land to find shore distance
for (u16 y = 0; y < m_MapSize; ++y)
{
u16 min = shoreMax;
for (u16 x = 0; x < m_MapSize; ++x)
{
if (!waterGrid.get(x, y) || expandOnWater)
{
u16 g = shoreGrid.get(x, y);
if (g > min)
shoreGrid.set(x, y, min);
else if (g < min)
min = g;
++min;
}
}
for (u16 x = m_MapSize; x > 0; --x)
{
if (!waterGrid.get(x-1, y) || expandOnWater)
{
u16 g = shoreGrid.get(x-1, y);
if (g > min)
shoreGrid.set(x-1, y, min);
else if (g < min)
min = g;
++min;
}
}
}
for (u16 x = 0; x < m_MapSize; ++x)
{
u16 min = shoreMax;
for (u16 y = 0; y < m_MapSize; ++y)
{
if (!waterGrid.get(x, y) || expandOnWater)
{
u16 g = shoreGrid.get(x, y);
if (g > min)
shoreGrid.set(x, y, min);
else if (g < min)
min = g;
++min;
}
}
for (u16 y = m_MapSize; y > 0; --y)
{
if (!waterGrid.get(x, y-1) || expandOnWater)
{
u16 g = shoreGrid.get(x, y-1);
if (g > min)
shoreGrid.set(x, y-1, min);
else if (g < min)
min = g;
++min;
}
}
}
return shoreGrid;
}
void CCmpPathfinder::UpdateGrid()
{
PROFILE3("UpdateGrid");
CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
if (!cmpTerrain)
return; // error
u16 terrainSize = cmpTerrain->GetTilesPerSide();
if (terrainSize == 0)
return;
// If the terrain was resized then delete the old grid data
if (m_Grid && m_MapSize != terrainSize)
{
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_TerrainOnlyGrid);
}
// Initialise the terrain data when first needed
if (!m_Grid)
{
m_MapSize = terrainSize;
m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
SAFE_DELETE(m_TerrainOnlyGrid);
m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
m_TerrainDirty = true;
}
// The grid should be properly initialized and clean. Checking the latter is expensive so do it only for debugging.
#ifdef NDEBUG
ENSURE(m_DirtinessInformation.dirtinessGrid.compare_sizes(m_Grid));
#else
ENSURE(m_DirtinessInformation.dirtinessGrid == Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE));
#endif
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
cmpObstructionManager->UpdateInformations(m_DirtinessInformation);
if (!m_DirtinessInformation.dirty && !m_TerrainDirty)
return;
// If the terrain has changed, recompute m_Grid
// Else, use data from m_TerrainOnlyGrid and add obstructions
if (m_TerrainDirty)
{
TerrainUpdateHelper();
*m_Grid = *m_TerrainOnlyGrid;
m_TerrainDirty = false;
m_DirtinessInformation.globallyDirty = true;
}
else if (m_DirtinessInformation.globallyDirty)
{
ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
memcpy(m_Grid->m_Data, m_TerrainOnlyGrid->m_Data, (m_Grid->m_W)*(m_Grid->m_H)*sizeof(NavcellData));
}
else
{
ENSURE(m_Grid->compare_sizes(m_TerrainOnlyGrid));
for (u16 j = 0; j < m_DirtinessInformation.dirtinessGrid.m_H; ++j)
for (u16 i = 0; i < m_DirtinessInformation.dirtinessGrid.m_W; ++i)
if (m_DirtinessInformation.dirtinessGrid.get(i, j) == 1)
m_Grid->set(i, j, m_TerrainOnlyGrid->get(i, j));
}
// Add obstructions onto the grid
cmpObstructionManager->Rasterize(*m_Grid, m_PassClasses, m_DirtinessInformation.globallyDirty);
- // Update the long-range pathfinder
+ // Update the long-range and hierarchical pathfinders.
if (m_DirtinessInformation.globallyDirty)
{
std::map nonPathfindingPassClasses, pathfindingPassClasses;
GetPassabilityClasses(nonPathfindingPassClasses, pathfindingPassClasses);
- m_LongPathfinder.Reload(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
+ m_LongPathfinder->Reload(m_Grid);
+ m_PathfinderHier->Recompute(m_Grid, nonPathfindingPassClasses, pathfindingPassClasses);
}
else
- m_LongPathfinder.Update(m_Grid, m_DirtinessInformation.dirtinessGrid);
+ {
+ 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()
{
TerrainUpdateHelper(false);
}
void CCmpPathfinder::TerrainUpdateHelper(bool expandPassability/* = true */)
{
PROFILE3("TerrainUpdateHelper");
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
CmpPtr cmpWaterManager(GetSimContext(), SYSTEM_ENTITY);
CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
CTerrain& terrain = GetSimContext().GetTerrain();
if (!cmpTerrain || !cmpObstructionManager)
return;
u16 terrainSize = cmpTerrain->GetTilesPerSide();
if (terrainSize == 0)
return;
if (!m_TerrainOnlyGrid || m_MapSize != terrainSize)
{
m_MapSize = terrainSize;
SAFE_DELETE(m_TerrainOnlyGrid);
m_TerrainOnlyGrid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
// If this update comes from a map resizing, we must reinitialize the other grids as well
if (!m_TerrainOnlyGrid->compare_sizes(m_Grid))
{
SAFE_DELETE(m_Grid);
m_Grid = new Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE);
m_DirtinessInformation = { true, true, Grid(m_MapSize * Pathfinding::NAVCELLS_PER_TILE, m_MapSize * Pathfinding::NAVCELLS_PER_TILE) };
m_AIPathfinderDirtinessInformation = m_DirtinessInformation;
}
}
Grid shoreGrid = ComputeShoreGrid();
// Compute initial terrain-dependent passability
for (int j = 0; j < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++j)
{
for (int i = 0; i < m_MapSize * Pathfinding::NAVCELLS_PER_TILE; ++i)
{
// World-space coordinates for this navcell
fixed x, z;
Pathfinding::NavcellCenter(i, j, x, z);
// Terrain-tile coordinates for this navcell
int itile = i / Pathfinding::NAVCELLS_PER_TILE;
int jtile = j / Pathfinding::NAVCELLS_PER_TILE;
// Gather all the data potentially needed to determine passability:
fixed height = terrain.GetExactGroundLevelFixed(x, z);
fixed water;
if (cmpWaterManager)
water = cmpWaterManager->GetWaterLevel(x, z);
fixed depth = water - height;
// Exact slopes give kind of weird output, so just use rough tile-based slopes
fixed slope = terrain.GetSlopeFixed(itile, jtile);
// Get world-space coordinates from shoreGrid (which uses terrain tiles)
fixed shoredist = fixed::FromInt(shoreGrid.get(itile, jtile)).MultiplyClamp(TERRAIN_TILE_SIZE);
// Compute the passability for every class for this cell
NavcellData t = 0;
for (PathfinderPassability& passability : m_PassClasses)
if (!passability.IsPassable(depth, slope, shoredist))
t |= passability.m_Mask;
m_TerrainOnlyGrid->set(i, j, t);
}
}
// Compute off-world passability
// WARNING: CCmpRangeManager::LosIsOffWorld needs to be kept in sync with this
const int edgeSize = 3 * Pathfinding::NAVCELLS_PER_TILE; // number of tiles around the edge that will be off-world
NavcellData edgeMask = 0;
for (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 = 0; j < h; ++j)
{
for (int i = 0; i < w; ++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);
}
}
//////////////////////////////////////////////////////////
+
+void CCmpPathfinder::ComputePath(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);
+}
+
u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
{
AsyncLongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
m_AsyncLongPathRequests.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)
{
AsyncShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
m_AsyncShortPathRequests.push_back(req);
return req.ticket;
}
WaypointPath CCmpPathfinder::ComputeShortPath(const AsyncShortPathRequest& request) const
{
return m_VertexPathfinder->ComputeShortPath(request, CmpPtr(GetSystemEntity()));
}
// Async processing:
void CCmpPathfinder::FinishAsyncRequests()
{
PROFILE2("Finish Async Requests");
// Save the request queue in case it gets modified while iterating
std::vector longRequests;
m_AsyncLongPathRequests.swap(longRequests);
std::vector shortRequests;
m_AsyncShortPathRequests.swap(shortRequests);
// TODO: we should only compute one path per entity per turn
// TODO: this computation should be done incrementally, spread
// across multiple frames (or even multiple turns)
ProcessLongRequests(longRequests);
ProcessShortRequests(shortRequests);
}
void CCmpPathfinder::ProcessLongRequests(const std::vector& longRequests)
{
PROFILE2("Process Long Requests");
for (size_t i = 0; i < longRequests.size(); ++i)
{
const AsyncLongPathRequest& req = longRequests[i];
WaypointPath path;
ComputePath(req.x0, req.z0, req.goal, req.passClass, path);
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
}
void CCmpPathfinder::ProcessShortRequests(const std::vector& shortRequests)
{
PROFILE2("Process Short Requests");
for (size_t i = 0; i < shortRequests.size(); ++i)
{
const AsyncShortPathRequest& req = shortRequests[i];
WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr(GetSystemEntity()));
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
}
void CCmpPathfinder::ProcessSameTurnMoves()
{
if (!m_AsyncLongPathRequests.empty())
{
// Figure out how many moves we can do this time
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
if (moveCount <= 0)
return;
// Copy the long request elements we are going to process into a new array
std::vector longRequests;
if ((i32)m_AsyncLongPathRequests.size() <= moveCount)
{
m_AsyncLongPathRequests.swap(longRequests);
moveCount = (i32)longRequests.size();
}
else
{
longRequests.resize(moveCount);
copy(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount, longRequests.begin());
m_AsyncLongPathRequests.erase(m_AsyncLongPathRequests.begin(), m_AsyncLongPathRequests.begin() + moveCount);
}
ProcessLongRequests(longRequests);
m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
}
if (!m_AsyncShortPathRequests.empty())
{
// Figure out how many moves we can do now
i32 moveCount = m_MaxSameTurnMoves - m_SameTurnMovesCount;
if (moveCount <= 0)
return;
// Copy the short request elements we are going to process into a new array
std::vector shortRequests;
if ((i32)m_AsyncShortPathRequests.size() <= moveCount)
{
m_AsyncShortPathRequests.swap(shortRequests);
moveCount = (i32)shortRequests.size();
}
else
{
shortRequests.resize(moveCount);
copy(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount, shortRequests.begin());
m_AsyncShortPathRequests.erase(m_AsyncShortPathRequests.begin(), m_AsyncShortPathRequests.begin() + moveCount);
}
ProcessShortRequests(shortRequests);
m_SameTurnMovesCount = (u16)(m_SameTurnMovesCount + moveCount);
}
}
//////////////////////////////////////////////////////////
bool CCmpPathfinder::CheckMovement(const IObstructionTestFilter& filter,
entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, entity_pos_t r,
pass_class_t passClass) const
{
PROFILE2_IFSPIKE("Check Movement", 0.001);
// Test against obstructions first. filter may discard pathfinding-blocking obstructions.
// Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly.
// This makes movement smoother and more natural for units, overall.
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true))
return false;
// Then test against the terrain grid. This should not be necessary
// But in case we allow terrain to change it will become so.
return Pathfinding::CheckLineMovement(x0, z0, x1, z1, passClass, *m_TerrainOnlyGrid);
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckUnitPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t r, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
{
// Check unit obstruction
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
if (cmpObstructionManager->TestUnitShape(filter, x, z, r, NULL))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
// Test against terrain and static obstructions:
u16 i, j;
Pathfinding::NearestNavcell(x, z, i, j, m_MapSize*Pathfinding::NAVCELLS_PER_TILE, m_MapSize*Pathfinding::NAVCELLS_PER_TILE);
if (!IS_PASSABLE(m_Grid->get(i, j), passClass))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
// (Static obstructions will be redundantly tested against in both the
// obstruction-shape test and navcell-passability test, which is slightly
// inefficient but shouldn't affect behaviour)
return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
entity_pos_t h, entity_id_t id, pass_class_t passClass) const
{
return CCmpPathfinder::CheckBuildingPlacement(filter, x, z, a, w, h, id, passClass, false);
}
ICmpObstruction::EFoundationCheck CCmpPathfinder::CheckBuildingPlacement(const IObstructionTestFilter& filter,
entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w,
entity_pos_t h, entity_id_t id, pass_class_t passClass, bool UNUSED(onlyCenterPoint)) const
{
// Check unit obstruction
CmpPtr cmpObstructionManager(GetSystemEntity());
if (!cmpObstructionManager)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_ERROR;
if (cmpObstructionManager->TestStaticShape(filter, x, z, a, w, h, NULL))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_OBSTRUCTS_FOUNDATION;
// Test against terrain:
ICmpObstructionManager::ObstructionSquare square;
CmpPtr cmpObstruction(GetSimContext(), id);
if (!cmpObstruction || !cmpObstruction->GetObstructionSquare(square))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_NO_OBSTRUCTION;
entity_pos_t expand;
const PathfinderPassability* passability = GetPassabilityFromMask(passClass);
if (passability)
expand = passability->m_Clearance;
SimRasterize::Spans spans;
SimRasterize::RasterizeRectWithClearance(spans, square, expand, Pathfinding::NAVCELL_SIZE);
for (const SimRasterize::Span& span : spans)
{
i16 i0 = span.i0;
i16 i1 = span.i1;
i16 j = span.j;
// Fail if any span extends outside the grid
if (i0 < 0 || i1 > m_TerrainOnlyGrid->m_W || j < 0 || j > m_TerrainOnlyGrid->m_H)
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
// Fail if any span includes an impassable tile
for (i16 i = i0; i < i1; ++i)
if (!IS_PASSABLE(m_TerrainOnlyGrid->get(i, j), passClass))
return ICmpObstruction::FOUNDATION_CHECK_FAIL_TERRAIN_CLASS;
}
return ICmpObstruction::FOUNDATION_CHECK_SUCCESS;
}
Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 22277)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 22278)
@@ -1,258 +1,257 @@
/* Copyright (C) 2019 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
#ifndef INCLUDED_CCMPPATHFINDER_COMMON
#define INCLUDED_CCMPPATHFINDER_COMMON
/**
* @file
* Declares CCmpPathfinder. Its implementation is mainly done in CCmpPathfinder.cpp,
* but the short-range (vertex) pathfinding is done in CCmpPathfinder_Vertex.cpp.
* This file provides common code needed for both files.
*
* The long-range pathfinding is done by a LongPathfinder object.
*/
#include "simulation2/system/Component.h"
#include "ICmpPathfinder.h"
#include "graphics/Overlay.h"
#include "graphics/Terrain.h"
#include "maths/MathUtil.h"
#include "ps/CLogger.h"
#include "renderer/TerrainOverlay.h"
#include "simulation2/components/ICmpObstructionManager.h"
-#include "simulation2/helpers/LongPathfinder.h"
+
+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_Update);
componentManager.SubscribeToMessageType(MT_RenderSubmit); // for debug overlays
componentManager.SubscribeToMessageType(MT_TerrainChanged);
componentManager.SubscribeToMessageType(MT_WaterChanged);
componentManager.SubscribeToMessageType(MT_ObstructionMapShapeChanged);
componentManager.SubscribeToMessageType(MT_TurnStart);
}
~CCmpPathfinder();
DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)
// Template state:
std::map m_PassClassMasks;
std::vector m_PassClasses;
// Dynamic state:
std::vector m_AsyncLongPathRequests;
std::vector m_AsyncShortPathRequests;
u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests
u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn
// Lazily-constructed dynamic state (not serialized):
u16 m_MapSize; // tiles per side
Grid* m_Grid; // terrain/passability information
Grid* m_TerrainOnlyGrid; // same as m_Grid, but only with terrain, to avoid some recomputations
// Keep clever updates in memory to avoid memory fragmentation from the grid.
// This should be used only in UpdateGrid(), there is no guarantee the data is properly initialized anywhere else.
GridUpdateInformation m_DirtinessInformation;
// The data from clever updates is stored for the AI manager
GridUpdateInformation m_AIPathfinderDirtinessInformation;
bool m_TerrainDirty;
std::unique_ptr m_VertexPathfinder;
- // Interface to the long-range pathfinder.
- LongPathfinder m_LongPathfinder;
+ std::unique_ptr m_PathfinderHier;
+ std::unique_ptr m_LongPathfinder;
// For responsiveness we will process some moves in the same turn they were generated in
u16 m_MaxSameTurnMoves; // max number of moves that can be created and processed in the same turn
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 ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, WaypointPath& ret)
- {
- m_LongPathfinder.ComputePath(x0, z0, goal, passClass, ret);
- }
+ virtual void ComputePath(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 ComputeShortPath(const AsyncShortPathRequest& 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 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 FinishAsyncRequests();
void ProcessLongRequests(const std::vector& longRequests);
void ProcessShortRequests(const std::vector& shortRequests);
virtual void ProcessSameTurnMoves();
/**
* 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();
/**
* Regenerates the terrain-only grid.
* Atlas doesn't need to have passability cells expanded.
*/
void TerrainUpdateHelper(bool expandPassability = true);
void RenderSubmit(SceneCollector& collector);
};
class AtlasOverlay : public TerrainTextureOverlay
{
public:
const CCmpPathfinder* m_Pathfinder;
pass_class_t m_PassClass;
AtlasOverlay(const CCmpPathfinder* pathfinder, pass_class_t passClass) :
TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder), m_PassClass(passClass)
{
}
virtual void BuildTextureRGBA(u8* data, size_t w, size_t h)
{
// Render navcell passability, based on the terrain-only grid
u8* p = data;
for (size_t j = 0; j < h; ++j)
{
for (size_t i = 0; i < w; ++i)
{
SColor4ub color(0, 0, 0, 0);
if (!IS_PASSABLE(m_Pathfinder->m_TerrainOnlyGrid->get((int)i, (int)j), m_PassClass))
color = SColor4ub(255, 0, 0, 127);
*p++ = color.R;
*p++ = color.G;
*p++ = color.B;
*p++ = color.A;
}
}
}
};
#endif // INCLUDED_CCMPPATHFINDER_COMMON
Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h
===================================================================
--- ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 22277)
+++ ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 22278)
@@ -1,199 +1,199 @@
/* Copyright (C) 2019 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see .
*/
#ifndef INCLUDED_ICMPPATHFINDER
#define INCLUDED_ICMPPATHFINDER
#include "simulation2/system/Interface.h"
#include "simulation2/components/ICmpObstruction.h"
#include "simulation2/helpers/PathGoal.h"
#include "simulation2/helpers/Pathfinding.h"
#include "maths/FixedVector2D.h"
#include