Changeset View
Changeset View
Standalone View
Standalone View
source/simulation2/helpers/HierarchicalPathfinder.h
Show All 21 Lines | |||||
#include "renderer/TerrainOverlay.h" | #include "renderer/TerrainOverlay.h" | ||||
#include "Render.h" | #include "Render.h" | ||||
#include "graphics/SColor.h" | #include "graphics/SColor.h" | ||||
/** | /** | ||||
* Hierarchical pathfinder. | * Hierarchical pathfinder. | ||||
* | * | ||||
* It doesn't find shortest paths, but deals with connectivity. | * Deals with connectivity (can point A reach point B?). | ||||
temple: . | |||||
* | * | ||||
* The navcell-grid representation of the map is split into fixed-size chunks. | * The navcell-grid representation of the map is split into fixed-size chunks. | ||||
* Within a chunk, each maximal set of adjacently-connected passable navcells | * Within a chunk, each maximal set of adjacently-connected passable navcells | ||||
* is defined as a region. | * is defined as a region. | ||||
* Each region is a vertex in the hierarchical pathfinder's graph. | * Each region is a vertex in the hierarchical pathfinder's graph. | ||||
* When two regions in adjacent chunks are connected by passable navcells, | * When two regions in adjacent chunks are connected by passable navcells, | ||||
* the graph contains an edge between the corresponding two vertexes. | * the graph contains an edge between the corresponding two vertexes. | ||||
* (There will never be an edge between two regions in the same chunk.) | * By design, there can never be an edge between two regions in the same chunk. | ||||
* | |||||
* Those fixed-size chunks are used to efficiently compute "global regions" by effectively flood-filling. | |||||
* Those can then be used to immediately determine if two reachables points are connected. | |||||
Done Inline Actions. temple: . | |||||
* | |||||
* The main use of this class is to convert an arbitrary PathGoal to a reachable navcell. | |||||
Done Inline Actions. temple: . | |||||
* This happens in MakeGoalReachable. | |||||
Done Inline ActionsB temple: B | |||||
* | * | ||||
* Since regions are typically fairly large, it is possible to determine | |||||
* connectivity between any two navcells by mapping them onto their appropriate | |||||
* region and then doing a relatively small graph search. | |||||
*/ | */ | ||||
#ifdef TEST | |||||
class TestCmpPathfinder; | |||||
#endif | |||||
class HierarchicalOverlay; | class HierarchicalOverlay; | ||||
class HierarchicalPathfinder | class HierarchicalPathfinder | ||||
{ | { | ||||
#ifdef TEST | |||||
friend class TestCmpPathfinder; | |||||
#endif | |||||
public: | public: | ||||
typedef u32 GlobalRegionID; | |||||
struct RegionID | struct RegionID | ||||
{ | { | ||||
u8 ci, cj; // chunk ID | u8 ci, cj; // chunk ID | ||||
u16 r; // unique-per-chunk local region ID | u16 r; // unique-per-chunk local region ID | ||||
RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { } | RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { } | ||||
bool operator<(RegionID b) const | bool operator<(const RegionID& b) const | ||||
{ | { | ||||
// Sort by chunk ID, then by per-chunk region ID | // Sort by chunk ID, then by per-chunk region ID | ||||
if (ci < b.ci) | if (ci < b.ci) | ||||
return true; | return true; | ||||
if (b.ci < ci) | if (b.ci < ci) | ||||
return false; | return false; | ||||
if (cj < b.cj) | if (cj < b.cj) | ||||
return true; | return true; | ||||
if (b.cj < cj) | if (b.cj < cj) | ||||
return false; | return false; | ||||
return r < b.r; | return r < b.r; | ||||
} | } | ||||
bool operator==(RegionID b) const | bool operator==(const RegionID& b) const | ||||
{ | { | ||||
return ((ci == b.ci) && (cj == b.cj) && (r == b.r)); | return ((ci == b.ci) && (cj == b.cj) && (r == b.r)); | ||||
} | } | ||||
}; | }; | ||||
HierarchicalPathfinder(); | HierarchicalPathfinder(); | ||||
~HierarchicalPathfinder(); | ~HierarchicalPathfinder(); | ||||
void SetDebugOverlay(bool enabled, const CSimContext* simContext); | void SetDebugOverlay(bool enabled, const CSimContext* simContext); | ||||
// Non-pathfinding grids will never be recomputed on calling HierarchicalPathfinder::Update | // Non-pathfinding grids will never be recomputed on calling HierarchicalPathfinder::Update | ||||
void Recompute(Grid<NavcellData>* passabilityGrid, | void Recompute(Grid<NavcellData>* passabilityGrid, | ||||
const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks, | const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks, | ||||
const std::map<std::string, pass_class_t>& pathfindingPassClassMasks); | const std::map<std::string, pass_class_t>& pathfindingPassClassMasks); | ||||
void Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid); | void Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid); | ||||
RegionID Get(u16 i, u16 j, pass_class_t passClass); | RegionID Get(u16 i, u16 j, pass_class_t passClass); | ||||
GlobalRegionID GetGlobalRegion(u16 i, u16 j, pass_class_t passClass); | |||||
/** | /** | ||||
* Updates @p goal so that it's guaranteed to be reachable from the navcell | * Updates @p goal to a point goal guaranteed to be reachable from the original navcell | ||||
* @p i0, @p j0 (which is assumed to be on a passable navcell). | * @p i0, @p j0 (which is assumed to be on a passable navcell). | ||||
* | * | ||||
* If the goal is not reachable, it is replaced with a point goal nearest to | * If the goal is not reachable, it is replaced with an acceptable point goal | ||||
* the goal center. | * This function does not necessarily return the closest navcell to the goal | ||||
* but the one with the lowest f score of the A* algorithm. | |||||
* This means it is usually a tradeoff between walking time and distance to the goal. | |||||
* | * | ||||
* In the case of a non-point reachable goal, it is replaced with a point goal | * In the case of a non-point reachable goal, it is replaced with a point goal | ||||
* at the reachable navcell of the goal which is nearest to the starting navcell. | * at the reachable navcell of the goal which is nearest to the starting navcell. | ||||
* TODO: since A* is used, it could return the reachable navcell nearest to the penultimate region visited. | |||||
Done Inline ActionsThis comment isn't accurate, I need to change it. wraitii: This comment isn't accurate, I need to change it. | |||||
* which is probably better (imagine a path that must bend around). | |||||
* | |||||
* @returns true if the goal was reachable, false otherwise. | |||||
*/ | */ | ||||
Not Done Inline Actionsno A* temple: no A* | |||||
void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass); | bool MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass); | ||||
/** | /** | ||||
* Updates @p i, @p j (which is assumed to be an impassable navcell) | * Updates @p i, @p j to the nearest passable navcell. | ||||
* to the nearest passable navcell. | * @param limited: only search a few tiles around (i, j) | ||||
*/ | */ | ||||
void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass); | void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass, bool limited = false); | ||||
/** | /** | ||||
* Generates the connectivity grid associated with the given pass_class | * Generates the connectivity grid associated with the given pass_class | ||||
*/ | */ | ||||
Grid<u16> GetConnectivityGrid(pass_class_t passClass); | Grid<u16> GetConnectivityGrid(pass_class_t passClass); | ||||
pass_class_t GetPassabilityClass(const std::string& name) const | pass_class_t GetPassabilityClass(const std::string& name) const | ||||
{ | { | ||||
auto it = m_PassClassMasks.find(name); | auto it = m_PassClassMasks.find(name); | ||||
if (it != m_PassClassMasks.end()) | if (it != m_PassClassMasks.end()) | ||||
return it->second; | return it->second; | ||||
LOGERROR("Invalid passability class name '%s'", name.c_str()); | LOGERROR("Invalid passability class name '%s'", name.c_str()); | ||||
return 0; | return 0; | ||||
} | } | ||||
private: | private: | ||||
static const u8 CHUNK_SIZE = 96; // number of navcells per side | static const u8 CHUNK_SIZE = 96; // number of navcells per side | ||||
// TODO PATHFINDER: figure out best number. Probably 64 < n < 128 | // TODO: figure out best number. Probably 64 < n < 128 | ||||
struct Chunk | struct Chunk | ||||
{ | { | ||||
u8 m_ChunkI, m_ChunkJ; // chunk ID | u8 m_ChunkI, m_ChunkJ; // chunk ID | ||||
u16 m_NumRegions; // number of local region IDs (starting from 1) | std::vector<u16> m_RegionsID; // IDs of local region, without 0 | ||||
Done Inline ActionsChanged to a vector to use ranged-for loops. wraitii: Changed to a vector to use ranged-for loops. | |||||
u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell | u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell | ||||
cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_NumRegions with a checkerboard pattern | cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_RegionsID with a checkerboard pattern | ||||
void InitRegions(int ci, int cj, Grid<NavcellData>* grid, pass_class_t passClass); | void InitRegions(int ci, int cj, Grid<NavcellData>* grid, pass_class_t passClass); | ||||
RegionID Get(int i, int j) const; | RegionID Get(int i, int j) const; | ||||
void RegionCenter(u16 r, int& i, int& j) const; | void RegionCenter(u16 r, int& i, int& j) const; | ||||
void NearestNavcell(int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const; | |||||
void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const; | void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const; | ||||
bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const; | bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const; | ||||
#ifdef TEST | |||||
bool operator==(const Chunk& b) const | |||||
{ | |||||
return (m_ChunkI == b.m_ChunkI && m_ChunkJ == b.m_ChunkJ && m_RegionsID == b.m_RegionsID && memcmp(&m_Regions, &b.m_Regions, sizeof(u16) * CHUNK_SIZE * CHUNK_SIZE) == 0); | |||||
} | |||||
#endif | |||||
}; | }; | ||||
typedef std::map<RegionID, std::set<RegionID> > EdgesMap; | typedef std::map<RegionID, std::set<RegionID> > EdgesMap; | ||||
void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges); | void RecomputeAllEdges(pass_class_t passClass, EdgesMap& edges); | ||||
void UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges); | |||||
void FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass); | void UpdateGlobalRegions(const std::map<pass_class_t, std::vector<RegionID>>& needNewGlobalRegionMap); | ||||
void FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass); | template <typename Ordering> | ||||
void FindReachableRegions(RegionID from, std::set<RegionID, Ordering>& reachable, pass_class_t passClass); | |||||
void FindGoalRegions(u16 gi, u16 gj, const PathGoal& goal, std::set<RegionID>& regions, pass_class_t passClass); | |||||
Done Inline ActionsA lot of this stuff is unneeded now. temple: A lot of this stuff is unneeded now. | |||||
/** | /** | ||||
* Updates @p iGoal and @p jGoal to the navcell that is the nearest to the | * Updates @p iGoal and @p jGoal to the navcell that is the nearest to the | ||||
* initial goal coordinates, in one of the given @p regions. | * initial goal coordinates, in one of the given @p regions. | ||||
* (Assumes @p regions is non-empty.) | * (Assumes @p regions is non-empty.) | ||||
*/ | */ | ||||
void FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass); | void FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass); | ||||
Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) | Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) | ||||
{ | { | ||||
return m_Chunks[passClass].at(cj * m_ChunksW + ci); | return m_Chunks[passClass].at(cj * m_ChunksW + ci); | ||||
} | } | ||||
void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid); | void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid); | ||||
u16 m_W, m_H; | u16 m_W, m_H; | ||||
u16 m_ChunksW, m_ChunksH; | u8 m_ChunksW, m_ChunksH; | ||||
std::map<pass_class_t, std::vector<Chunk> > m_Chunks; | std::map<pass_class_t, std::vector<Chunk> > m_Chunks; | ||||
std::map<pass_class_t, EdgesMap> m_Edges; | std::map<pass_class_t, EdgesMap> m_Edges; | ||||
std::map<pass_class_t, std::map<RegionID, GlobalRegionID>> m_GlobalRegions; | |||||
GlobalRegionID m_NextGlobalRegionID; | |||||
Done Inline ActionsIs this a concern, that we could run out of numbers? Otherwise we wouldn't need a vector? temple: Is this a concern, that we could run out of numbers? Otherwise we wouldn't need a vector? | |||||
Done Inline ActionsI think the concern wasn't that we could run out of region IDs but rather that the vector will get sparse and performance will suffer. wraitii: I think the concern wasn't that we could run out of region IDs but rather that the vector will… | |||||
Done Inline ActionsChanged to a simple "always increment" pattern because of the Update fix, as I'll need to re-flood-fill once per turn at least in general. wraitii: Changed to a simple "always increment" pattern because of the Update fix, as I'll need to re… | |||||
// Passability classes for which grids will be updated when calling Update | // Passability classes for which grids will be updated when calling Update | ||||
std::map<std::string, pass_class_t> m_PassClassMasks; | std::map<std::string, pass_class_t> m_PassClassMasks; | ||||
void AddDebugEdges(pass_class_t passClass); | void AddDebugEdges(pass_class_t passClass); | ||||
HierarchicalOverlay* m_DebugOverlay; | HierarchicalOverlay* m_DebugOverlay; | ||||
const CSimContext* m_SimContext; // Used for drawing the debug lines | const CSimContext* m_SimContext; // Used for drawing the debug lines | ||||
public: | public: | ||||
▲ Show 20 Lines • Show All 42 Lines • Show Last 20 Lines |
Wildfire Games · Phabricator
.