Index: ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 9664)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h (revision 9665)
@@ -1,273 +1,286 @@
/* Copyright (C) 2011 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, whose implementation is split into multiple source files,
* and provides common code needed for more than one of those files.
* CCmpPathfinder includes two pathfinding algorithms (one tile-based, one vertex-based)
* with some shared state and functionality, so the code is split into
* CCmpPathfinder_Vertex.cpp, CCmpPathfinder_Tile.cpp and CCmpPathfinder.cpp
*/
#include "simulation2/system/Component.h"
#include "ICmpPathfinder.h"
#include "graphics/Overlay.h"
#include "graphics/Terrain.h"
#include "maths/MathUtil.h"
#include "simulation2/helpers/Geometry.h"
#include "simulation2/helpers/Grid.h"
class PathfinderOverlay;
class SceneCollector;
struct PathfindTile;
#ifdef NDEBUG
#define PATHFIND_DEBUG 0
#else
#define PATHFIND_DEBUG 1
#endif
/*
* For efficient pathfinding we want to try hard to minimise the per-tile search cost,
* so we precompute the tile passability flags and movement costs for the various different
* types of unit.
* We also want to minimise memory usage (there can easily be 100K tiles so we don't want
* to store many bytes for each).
*
* To handle passability efficiently, we have a small number of passability classes
* (e.g. "infantry", "ship"). Each unit belongs to a single passability class, and
* uses that for all its pathfinding.
* Passability is determined by water depth, terrain slope, forestness, buildingness.
* We need at least one bit per class per tile to represent passability.
*
* We use a separate bit to indicate building obstructions (instead of folding it into
* the class passabilities) so that it can be ignored when doing the accurate short paths.
* We use another bit to indicate tiles near obstructions that block construction,
* for the AI to plan safe building spots.
*
* To handle movement costs, we have an arbitrary number of unit cost classes (e.g. "infantry", "camel"),
* and a small number of terrain cost classes (e.g. "grass", "steep grass", "road", "sand"),
* and a cost mapping table between the classes (e.g. camels are fast on sand).
* We need log2(|terrain cost classes|) bits per tile to represent costs.
*
* We could have one passability bitmap per class, and another array for cost classes,
* but instead (for no particular reason) we'll pack them all into a single u16 array.
*
* We handle dynamic updates currently by recomputing the entire array, which is stupid;
* it should only bother updating the region that has changed.
*/
class PathfinderPassability
{
public:
PathfinderPassability(ICmpPathfinder::pass_class_t mask, const CParamNode& node) :
m_Mask(mask)
{
if (node.GetChild("MinWaterDepth").IsOk())
m_MinDepth = node.GetChild("MinWaterDepth").ToFixed();
else
m_MinDepth = std::numeric_limits::min();
if (node.GetChild("MaxWaterDepth").IsOk())
m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed();
else
m_MaxDepth = std::numeric_limits::max();
if (node.GetChild("MaxTerrainSlope").IsOk())
m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed();
else
m_MaxSlope = std::numeric_limits::max();
}
bool IsPassable(fixed waterdepth, fixed steepness)
{
return ((m_MinDepth <= waterdepth && waterdepth <= m_MaxDepth) && (steepness < m_MaxSlope));
}
ICmpPathfinder::pass_class_t m_Mask;
private:
fixed m_MinDepth;
fixed m_MaxDepth;
fixed m_MaxSlope;
};
typedef u16 TerrainTile;
// 1 bit for pathfinding obstructions,
// 1 bit for construction obstructions (used by AI),
// PASS_CLASS_BITS for terrain passability (allowing PASS_CLASS_BITS classes),
// COST_CLASS_BITS for movement costs (allowing 2^COST_CLASS_BITS classes)
const int PASS_CLASS_BITS = 10;
const int COST_CLASS_BITS = 16 - (PASS_CLASS_BITS + 2);
#define IS_TERRAIN_PASSABLE(item, classmask) (((item) & (classmask)) == 0)
#define IS_PASSABLE(item, classmask) (((item) & ((classmask) | 1)) == 0)
#define GET_COST_CLASS(item) ((item) >> (PASS_CLASS_BITS + 2))
#define COST_CLASS_MASK(id) ( (TerrainTile) ((id) << (PASS_CLASS_BITS + 2)) )
typedef SparseGrid PathfindTileGrid;
struct AsyncLongPathRequest
{
u32 ticket;
entity_pos_t x0;
entity_pos_t z0;
ICmpPathfinder::Goal goal;
ICmpPathfinder::pass_class_t passClass;
ICmpPathfinder::cost_class_t costClass;
entity_id_t notify;
};
struct AsyncShortPathRequest
{
u32 ticket;
entity_pos_t x0;
entity_pos_t z0;
entity_pos_t r;
entity_pos_t range;
ICmpPathfinder::Goal goal;
ICmpPathfinder::pass_class_t passClass;
bool avoidMovingUnits;
entity_id_t group;
entity_id_t notify;
};
/**
* Implementation of ICmpPathfinder
*/
class CCmpPathfinder : 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_TurnStart);
}
DEFAULT_COMPONENT_ALLOCATOR(Pathfinder)
// Template state:
std::map m_PassClassMasks;
std::vector m_PassClasses;
std::map m_TerrainCostClassTags;
std::map m_UnitCostClassTags;
std::vector > m_MoveCosts; // costs[unitClass][terrainClass]
std::vector > m_MoveSpeeds; // speeds[unitClass][terrainClass]
// Dynamic state:
std::vector m_AsyncLongPathRequests;
std::vector m_AsyncShortPathRequests;
u32 m_NextAsyncTicket; // unique IDs for asynchronous path requests
// Lazily-constructed dynamic state (not serialized):
u16 m_MapSize; // tiles per side
Grid* m_Grid; // terrain/passability information
Grid* m_ObstructionGrid; // cached obstruction information (TODO: we shouldn't bother storing this, it's redundant with LSBs of m_Grid)
bool m_TerrainDirty; // indicates if m_Grid has been updated since terrain changed
+
+ // For responsiveness we will procees 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
+ u16 m_SameTurnMovesCount; // current number of same turn moves we have processed this turn
// Debugging - output from last pathfind operation:
+
PathfindTileGrid* m_DebugGrid;
u32 m_DebugSteps;
Path* m_DebugPath;
PathfinderOverlay* m_DebugOverlay;
pass_class_t m_DebugPassClass;
std::vector m_DebugOverlayShortPathLines;
static std::string GetSchema()
{
return "";
}
virtual void Init(const CParamNode& paramNode);
virtual void Deinit();
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);
virtual std::map GetPassabilityClasses();
virtual cost_class_t GetCostClass(const std::string& name);
virtual const Grid& GetPassabilityGrid();
virtual void ComputePath(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, Path& ret);
virtual u32 ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, entity_id_t notify);
virtual void ComputeShortPath(const IObstructionTestFilter& filter, entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, pass_class_t passClass, Path& ret);
virtual u32 ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& 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 Goal& goal, pass_class_t passClass, cost_class_t costClass);
virtual void ResetDebugPath();
virtual void SetDebugOverlay(bool enabled);
virtual fixed GetMovementSpeed(entity_pos_t x0, entity_pos_t z0, cost_class_t costClass);
virtual CFixedVector2D GetNearestPointOnGoal(CFixedVector2D pos, const Goal& goal);
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);
virtual void FinishAsyncRequests();
+ virtual void ProcessLongRequests(const std::vector& longRequests);
+
+ virtual void ProcessShortRequests(const std::vector& shortRequests);
+
+ virtual void ProcessSameTurnMoves();
+
/**
* Returns the tile containing the given position
*/
void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j)
{
i = clamp((x / (int)CELL_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1);
j = clamp((z / (int)CELL_SIZE).ToInt_RoundToZero(), 0, m_MapSize-1);
}
/**
* Returns the position of the center of the given tile
*/
static void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
{
x = entity_pos_t::FromInt(i*(int)CELL_SIZE + CELL_SIZE/2);
z = entity_pos_t::FromInt(j*(int)CELL_SIZE + CELL_SIZE/2);
}
static fixed DistanceToGoal(CFixedVector2D pos, const CCmpPathfinder::Goal& goal);
/**
* Regenerates the grid based on the current obstruction list, if necessary
*/
void UpdateGrid();
void RenderSubmit(SceneCollector& collector);
};
#endif // INCLUDED_CCMPPATHFINDER_COMMON
Index: ps/trunk/source/simulation2/components/CCmpPathfinder.cpp
===================================================================
--- ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 9664)
+++ ps/trunk/source/simulation2/components/CCmpPathfinder.cpp (revision 9665)
@@ -1,456 +1,533 @@
/* Copyright (C) 2011 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 "renderer/Scene.h"
#include "simulation2/MessageTypes.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/components/ICmpWaterManager.h"
#include "simulation2/serialization/SerializeTemplates.h"
// Default cost to move a single tile is a fairly arbitrary number, which should be big
// enough to be precise when multiplied/divided and small enough to never overflow when
// summing the cost of a whole path.
const int DEFAULT_MOVE_COST = 256;
REGISTER_COMPONENT_TYPE(Pathfinder)
void CCmpPathfinder::Init(const CParamNode& UNUSED(paramNode))
{
m_MapSize = 0;
m_Grid = NULL;
m_ObstructionGrid = NULL;
m_TerrainDirty = true;
m_NextAsyncTicket = 1;
m_DebugOverlay = NULL;
m_DebugGrid = NULL;
m_DebugPath = NULL;
// 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");
+ const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
+ m_MaxSameTurnMoves = 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_t)(1u << (m_PassClasses.size() + 2));
m_PassClasses.push_back(PathfinderPassability(mask, it->second));
m_PassClassMasks[name] = mask;
}
const CParamNode::ChildrenMap& moveClasses = externalParamNode.GetChild("Pathfinder").GetChild("MovementClasses").GetChildren();
// First find the set of unit classes used by any terrain classes,
// and assign unique tags to terrain classes
std::set unitClassNames;
unitClassNames.insert("default"); // must always have costs for default
{
size_t i = 0;
for (CParamNode::ChildrenMap::const_iterator it = moveClasses.begin(); it != moveClasses.end(); ++it)
{
std::string terrainClassName = it->first;
m_TerrainCostClassTags[terrainClassName] = (cost_class_t)i;
++i;
const CParamNode::ChildrenMap& unitClasses = it->second.GetChild("UnitClasses").GetChildren();
for (CParamNode::ChildrenMap::const_iterator uit = unitClasses.begin(); uit != unitClasses.end(); ++uit)
unitClassNames.insert(uit->first);
}
}
// For each terrain class, set the costs for every unit class,
// and assign unique tags to unit classes
{
size_t i = 0;
for (std::set::const_iterator nit = unitClassNames.begin(); nit != unitClassNames.end(); ++nit)
{
m_UnitCostClassTags[*nit] = (cost_class_t)i;
++i;
std::vector costs;
std::vector speeds;
for (CParamNode::ChildrenMap::const_iterator it = moveClasses.begin(); it != moveClasses.end(); ++it)
{
// Default to the general costs for this terrain class
fixed cost = it->second.GetChild("@Cost").ToFixed();
fixed speed = it->second.GetChild("@Speed").ToFixed();
// Check for specific cost overrides for this unit class
const CParamNode& unitClass = it->second.GetChild("UnitClasses").GetChild(nit->c_str());
if (unitClass.IsOk())
{
cost = unitClass.GetChild("@Cost").ToFixed();
speed = unitClass.GetChild("@Speed").ToFixed();
}
costs.push_back((cost * DEFAULT_MOVE_COST).ToInt_RoundToZero());
speeds.push_back(speed);
}
m_MoveCosts.push_back(costs);
m_MoveSpeeds.push_back(speeds);
}
}
}
void CCmpPathfinder::Deinit()
{
SetDebugOverlay(false); // cleans up memory
ResetDebugPath();
delete m_Grid;
delete m_ObstructionGrid;
}
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.NumberU8_Unbounded("cost class", value.costClass);
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("r", value.r);
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);
}
};
void CCmpPathfinder::Serialize(ISerializer& serialize)
{
SerializeVector()(serialize, "long requests", m_AsyncLongPathRequests);
SerializeVector()(serialize, "short requests", m_AsyncShortPathRequests);
serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
}
void CCmpPathfinder::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
{
Init(paramNode);
SerializeVector()(deserialize, "long requests", m_AsyncLongPathRequests);
SerializeVector()(deserialize, "short requests", m_AsyncShortPathRequests);
deserialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
}
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:
{
// TODO: we ought to only bother updating the dirtied region
m_TerrainDirty = true;
break;
}
+ case MT_TurnStart:
+ {
+ m_SameTurnMovesCount = 0;
+ break;
+ }
}
}
void CCmpPathfinder::RenderSubmit(SceneCollector& collector)
{
for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)
collector.Submit(&m_DebugOverlayShortPathLines[i]);
}
fixed CCmpPathfinder::GetMovementSpeed(entity_pos_t x0, entity_pos_t z0, u8 costClass)
{
UpdateGrid();
u16 i, j;
NearestTile(x0, z0, i, j);
TerrainTile tileTag = m_Grid->get(i, j);
return m_MoveSpeeds.at(costClass).at(GET_COST_CLASS(tileTag));
}
ICmpPathfinder::pass_class_t CCmpPathfinder::GetPassabilityClass(const std::string& name)
{
if (m_PassClassMasks.find(name) == m_PassClassMasks.end())
{
LOGERROR(L"Invalid passability class name '%hs'", name.c_str());
return 0;
}
return m_PassClassMasks[name];
}
std::map CCmpPathfinder::GetPassabilityClasses()
{
return m_PassClassMasks;
}
ICmpPathfinder::cost_class_t CCmpPathfinder::GetCostClass(const std::string& name)
{
if (m_UnitCostClassTags.find(name) == m_UnitCostClassTags.end())
{
LOGERROR(L"Invalid unit cost class name '%hs'", name.c_str());
return m_UnitCostClassTags["default"];
}
return m_UnitCostClassTags[name];
}
fixed CCmpPathfinder::DistanceToGoal(CFixedVector2D pos, const CCmpPathfinder::Goal& goal)
{
switch (goal.type)
{
case CCmpPathfinder::Goal::POINT:
return (pos - CFixedVector2D(goal.x, goal.z)).Length();
case CCmpPathfinder::Goal::CIRCLE:
return ((pos - CFixedVector2D(goal.x, goal.z)).Length() - goal.hw).Absolute();
case CCmpPathfinder::Goal::SQUARE:
{
CFixedVector2D halfSize(goal.hw, goal.hh);
CFixedVector2D d(pos.X - goal.x, pos.Y - goal.z);
return Geometry::DistanceToSquare(d, goal.u, goal.v, halfSize);
}
default:
debug_warn(L"invalid type");
return fixed::Zero();
}
}
const Grid& CCmpPathfinder::GetPassabilityGrid()
{
UpdateGrid();
return *m_Grid;
}
void CCmpPathfinder::UpdateGrid()
{
// If the terrain was resized then delete the old grid data
if (m_Grid && m_MapSize != GetSimContext().GetTerrain().GetTilesPerSide())
{
SAFE_DELETE(m_Grid);
SAFE_DELETE(m_ObstructionGrid);
m_TerrainDirty = true;
}
// Initialise the terrain data when first needed
if (!m_Grid)
{
// TOOD: these bits should come from ICmpTerrain
ssize_t size = GetSimContext().GetTerrain().GetTilesPerSide();
ENSURE(size >= 1 && size <= 0xffff); // must fit in 16 bits
m_MapSize = size;
m_Grid = new Grid(m_MapSize, m_MapSize);
m_ObstructionGrid = new Grid(m_MapSize, m_MapSize);
}
CmpPtr cmpObstructionManager(GetSimContext(), SYSTEM_ENTITY);
bool obstructionsDirty = cmpObstructionManager->Rasterise(*m_ObstructionGrid);
if (obstructionsDirty && !m_TerrainDirty)
{
PROFILE("UpdateGrid obstructions");
// Obstructions changed - we need to recompute passability
// Since terrain hasn't changed we only need to update the obstruction bits
// and can skip the rest of the data
// TODO: if ObstructionManager::SetPassabilityCircular was called at runtime
// (which should probably never happen, but that's not guaranteed),
// then TILE_OUTOFBOUNDS will change and we can't use this fast path, but
// currently it'll just set obstructionsDirty and we won't notice
for (u16 j = 0; j < m_MapSize; ++j)
{
for (u16 i = 0; i < m_MapSize; ++i)
{
TerrainTile& t = m_Grid->get(i, j);
u8 obstruct = m_ObstructionGrid->get(i, j);
if (obstruct & ICmpObstructionManager::TILE_OBSTRUCTED_PATHFINDING)
t |= 1;
else
t &= ~1;
if (obstruct & ICmpObstructionManager::TILE_OBSTRUCTED_FOUNDATION)
t |= 2;
else
t &= ~2;
}
}
++m_Grid->m_DirtyID;
}
else if (obstructionsDirty || m_TerrainDirty)
{
PROFILE("UpdateGrid full");
// Obstructions or terrain changed - we need to recompute passability
// TODO: only bother recomputing the region that has actually changed
CmpPtr cmpWaterMan(GetSimContext(), SYSTEM_ENTITY);
CTerrain& terrain = GetSimContext().GetTerrain();
for (u16 j = 0; j < m_MapSize; ++j)
{
for (u16 i = 0; i < m_MapSize; ++i)
{
fixed x, z;
TileCenter(i, j, x, z);
TerrainTile t = 0;
u8 obstruct = m_ObstructionGrid->get(i, j);
fixed height = terrain.GetVertexGroundLevelFixed(i, j); // TODO: should use tile centre
fixed water;
if (!cmpWaterMan.null())
water = cmpWaterMan->GetWaterLevel(x, z);
fixed depth = water - height;
fixed slope = terrain.GetSlopeFixed(i, j);
if (obstruct & ICmpObstructionManager::TILE_OBSTRUCTED_PATHFINDING)
t |= 1;
if (obstruct & ICmpObstructionManager::TILE_OBSTRUCTED_FOUNDATION)
t |= 2;
if (obstruct & ICmpObstructionManager::TILE_OUTOFBOUNDS)
{
// If out of bounds, nobody is allowed to pass
for (size_t n = 0; n < m_PassClasses.size(); ++n)
t |= m_PassClasses[n].m_Mask;
}
else
{
for (size_t n = 0; n < m_PassClasses.size(); ++n)
{
if (!m_PassClasses[n].IsPassable(depth, slope))
t |= m_PassClasses[n].m_Mask;
}
}
std::string moveClass = terrain.GetMovementClass(i, j);
if (m_TerrainCostClassTags.find(moveClass) != m_TerrainCostClassTags.end())
t |= COST_CLASS_MASK(m_TerrainCostClassTags[moveClass]);
m_Grid->set(i, j, t);
}
}
m_TerrainDirty = false;
++m_Grid->m_DirtyID;
}
}
//////////////////////////////////////////////////////////
// Async path requests:
u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const Goal& goal, pass_class_t passClass, cost_class_t costClass, entity_id_t notify)
{
AsyncLongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, costClass, notify };
m_AsyncLongPathRequests.push_back(req);
return req.ticket;
}
u32 CCmpPathfinder::ComputeShortPathAsync(entity_pos_t x0, entity_pos_t z0, entity_pos_t r, entity_pos_t range, const Goal& goal, pass_class_t passClass, bool avoidMovingUnits, entity_id_t group, entity_id_t notify)
{
AsyncShortPathRequest req = { m_NextAsyncTicket++, x0, z0, r, range, goal, passClass, avoidMovingUnits, group, notify };
m_AsyncShortPathRequests.push_back(req);
return req.ticket;
}
void CCmpPathfinder::FinishAsyncRequests()
{
// 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)
+{
for (size_t i = 0; i < longRequests.size(); ++i)
{
const AsyncLongPathRequest& req = longRequests[i];
Path path;
ComputePath(req.x0, req.z0, req.goal, req.passClass, req.costClass, path);
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
+}
+void CCmpPathfinder::ProcessShortRequests(const std::vector& shortRequests)
+{
for (size_t i = 0; i < shortRequests.size(); ++i)
{
const AsyncShortPathRequest& req = shortRequests[i];
Path path;
ControlGroupMovementObstructionFilter filter(req.avoidMovingUnits, req.group);
ComputeShortPath(filter, req.x0, req.z0, req.r, req.range, req.goal, req.passClass, path);
CMessagePathResult msg(req.ticket, path);
GetSimContext().GetComponentManager().PostMessage(req.notify, msg);
}
}
+
+void CCmpPathfinder::ProcessSameTurnMoves()
+{
+ u32 moveCount;
+
+ if (m_AsyncLongPathRequests.size() > 0)
+ {
+ // Figure out how many moves we can do this time
+ 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 (m_AsyncLongPathRequests.size() <= moveCount)
+ {
+ m_AsyncLongPathRequests.swap(longRequests);
+ moveCount = 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 += moveCount;
+ }
+
+ if (m_AsyncShortPathRequests.size() > 0)
+ {
+ // Figure out how many moves we can do now
+ 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 (m_AsyncShortPathRequests.size() <= moveCount)
+ {
+ m_AsyncShortPathRequests.swap(shortRequests);
+ moveCount = 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 += moveCount;
+ }
+}
+
Index: ps/trunk/source/simulation2/components/ICmpPathfinder.h
===================================================================
--- ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 9664)
+++ ps/trunk/source/simulation2/components/ICmpPathfinder.h (revision 9665)
@@ -1,165 +1,170 @@
/* Copyright (C) 2011 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/helpers/Position.h"
#include "maths/FixedVector2D.h"
#include