18 #ifndef INCLUDED_HIERPATHFINDER 19 #define INCLUDED_HIERPATHFINDER 53 class TestCmpPathfinder;
54 class TestHierarchicalPathfinder;
63 friend class TestCmpPathfinder;
64 friend class TestHierarchicalPathfinder;
92 return ((ci == b.
ci) && (cj == b.
cj) && (r == b.
r));
111 const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks,
112 const std::map<std::string, pass_class_t>& pathfindingPassClassMasks);
158 LOGERROR(
"Invalid passability class name '%s'", name.c_str());
174 cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536);
180 void RegionCenter(
u16 r,
int& i,
int& j)
const;
182 void RegionNavcellNearest(
u16 r,
int iGoal,
int jGoal,
int& iBest,
int& jBest,
u32& dist2Best)
const;
199 typedef std::map<RegionID, std::set<RegionID> >
EdgesMap;
210 template<
typename Ordering>
215 reachable.insert(from);
217 const EdgesMap& edgeMap =
m_Edges.at(passClass);
218 if (edgeMap.find(from) == edgeMap.end())
221 std::vector<RegionID> open;
223 open.push_back(from);
225 while (!open.empty())
230 for (
const RegionID& region : edgeMap.at(curr))
233 if (reachable.insert(region).second)
234 open.push_back(region);
282 std::map<pass_class_t, std::vector<Chunk> >
m_Chunks;
312 ENSURE(h <= std::numeric_limits<u16>::max() && w <= std::numeric_limits<u16>::max());
313 u16 height =
static_cast<u16>(h);
314 u16 width =
static_cast<u16>(w);
317 for (
u16 j = 0; j < height; ++j)
319 for (
u16 i = 0; i < width; ++i)
326 else if (rid.
r == 0xFFFF)
329 color = GetColor(rid.
r + rid.
ci*5 + rid.
cj*7, 127);
341 #endif // INCLUDED_HIERPATHFINDER Definition: HierarchicalPathfinder.h:168
Definition: HierarchicalPathfinder.h:261
u8 G
Definition: SColor.h:33
HierarchicalOverlay * m_DebugOverlay
Definition: HierarchicalPathfinder.h:293
#define LOGERROR(...)
Definition: CLogger.h:36
u16 pass_class_t
Definition: Pathfinding.h:27
void FindGoalRegionsAndBestNavcells(u16 i0, u16 j0, u16 gi, u16 gj, const PathGoal &goal, std::set< InterestingRegion, SortByBestToPoint > ®ions, pass_class_t passClass) const
Definition: HierarchicalPathfinder.cpp:775
Definition: HierarchicalPathfinder.h:238
SortByCenterToPoint(u16 i, u16 j)
Definition: HierarchicalPathfinder.h:240
Definition: Pathfinding.cpp:27
RegionID(u8 ci, u8 cj, u16 r)
Definition: HierarchicalPathfinder.h:74
void Update(Grid< NavcellData > *grid, const Grid< u8 > &dirtinessGrid)
Definition: HierarchicalPathfinder.cpp:438
void FillRegionOnGrid(const RegionID ®ion, pass_class_t passClass, u16 value, Grid< u16 > &grid) const
Definition: HierarchicalPathfinder.cpp:808
GlobalRegionID m_NextGlobalRegionID
Definition: HierarchicalPathfinder.h:287
HierarchicalOverlay(HierarchicalPathfinder &pathfinderHier)
Definition: HierarchicalPathfinder.h:305
uint16_t u16
Definition: types.h:38
u32 DistanceTo(u16 i, u16 j) const
Definition: HierarchicalPathfinder.h:96
const Chunk & GetChunk(u8 ci, u8 cj, pass_class_t passClass) const
Definition: HierarchicalPathfinder.h:194
void RecomputeAllEdges(pass_class_t passClass, EdgesMap &edges)
Find edges between regions in all chunks, in an optimised manner (only look at top/left) ...
Definition: HierarchicalPathfinder.cpp:564
Definition: HierarchicalPathfinder.h:255
std::vector< u16 > m_RegionsID
Definition: HierarchicalPathfinder.h:171
u16 bestJ
Definition: HierarchicalPathfinder.h:258
u16 m_W
Definition: HierarchicalPathfinder.h:280
void ComputeNeighbors(EdgesMap &edges, Chunk &a, Chunk &b, bool transpose, bool opposite) const
Definition: HierarchicalPathfinder.cpp:510
u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]
Definition: HierarchicalPathfinder.h:172
Pathfinder goal.
Definition: PathGoal.h:32
u32 GlobalRegionID
Definition: HierarchicalPathfinder.h:67
bool operator()(const InterestingRegion &a, const InterestingRegion &b) const
Definition: HierarchicalPathfinder.h:264
void Recompute(Grid< NavcellData > *passabilityGrid, const std::map< std::string, pass_class_t > &nonPathfindingPassClassMasks, const std::map< std::string, pass_class_t > &pathfindingPassClassMasks)
Definition: HierarchicalPathfinder.cpp:362
u16 gj
Definition: HierarchicalPathfinder.h:249
Contains pointers to various 'global' objects that are needed by the simulation code, to allow easy access without using real (evil) global variables.
Definition: SimContext.h:32
u8 B
Definition: SColor.h:34
uint8_t u8
Definition: types.h:37
Grid< u16 > GetConnectivityGrid(pass_class_t passClass) const
Generates the connectivity grid associated with the given pass_class.
Definition: HierarchicalPathfinder.cpp:823
This interface accepts renderable objects.
Definition: Scene.h:89
u8 m_ChunkJ
Definition: HierarchicalPathfinder.h:170
u8 A
Definition: SColor.h:35
bool operator()(const HierarchicalPathfinder::RegionID &a, const HierarchicalPathfinder::RegionID &b) const
Definition: HierarchicalPathfinder.h:241
Definition: HierarchicalPathfinder.h:300
u8 cj
Definition: HierarchicalPathfinder.h:71
pass_class_t GetPassabilityClass(const std::string &name) const
Definition: HierarchicalPathfinder.h:152
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:290
u8 m_ChunksH
Definition: HierarchicalPathfinder.h:281
HierarchicalPathfinder()
Definition: HierarchicalPathfinder.cpp:327
uint32_t u32
Definition: types.h:39
RegionID region
Definition: HierarchicalPathfinder.h:256
SortByBestToPoint(u16 i, u16 j)
Definition: HierarchicalPathfinder.h:263
void FindReachableRegions(RegionID from, std::set< RegionID, Ordering > &reachable, pass_class_t passClass) const
Returns all reachable regions, optionally ordered in a specific manner.
Definition: HierarchicalPathfinder.h:211
Definition: HierarchicalPathfinder.h:60
Definition: HierarchicalPathfinder.h:69
void RenderSubmit(SceneCollector &collector)
Definition: HierarchicalPathfinder.cpp:353
void FindNearestNavcellInRegions(const std::set< RegionID, SortByCenterToPoint > ®ions, u16 &iGoal, u16 &jGoal, pass_class_t passClass) const
Definition: HierarchicalPathfinder.cpp:740
void FindNearestPassableNavcell(u16 &i, u16 &j, pass_class_t passClass) const
Updates i, j (which is assumed to be an impassable navcell) to the nearest passable navcell...
Definition: HierarchicalPathfinder.cpp:728
bool MakeGoalReachable(u16 i0, u16 j0, PathGoal &goal, pass_class_t passClass) const
Updates goal so that it's guaranteed to be reachable from the navcell i0, j0 (which is assumed to be ...
Definition: HierarchicalPathfinder.cpp:676
void UpdateGlobalRegions(const std::map< pass_class_t, std::vector< RegionID > > &needNewGlobalRegionMap)
Definition: HierarchicalPathfinder.cpp:626
~HierarchicalPathfinder()
Definition: HierarchicalPathfinder.cpp:331
HierarchicalPathfinder & m_PathfinderHier
Definition: HierarchicalPathfinder.h:303
void SetDebugOverlay(bool enabled, const CSimContext *simContext)
Definition: HierarchicalPathfinder.cpp:336
bool operator==(const RegionID &b) const
Definition: HierarchicalPathfinder.h:90
u8 R
Definition: SColor.h:32
u8 m_ChunksW
Definition: HierarchicalPathfinder.h:281
u8 ci
Definition: HierarchicalPathfinder.h:71
constexpr int NAVCELLS_PER_TERRAIN_TILE
The terrain grid is coarser, and it is often convenient to convert from one to the other...
Definition: Pathfinding.h:150
void AddDebugEdges(pass_class_t passClass)
Debug visualisation of graph edges between regions.
Definition: HierarchicalPathfinder.cpp:588
RegionID Get(u16 i, u16 j, pass_class_t passClass) const
Definition: HierarchicalPathfinder.cpp:650
GlobalRegionID GetGlobalRegion(u16 i, u16 j, pass_class_t passClass) const
Definition: HierarchicalPathfinder.cpp:658
std::map< std::string, pass_class_t > m_PassClassMasks
Definition: HierarchicalPathfinder.h:290
Base class for texture-based terrain overlays, with an arbitrary number of texels per terrain tile...
Definition: TerrainOverlay.h:197
virtual void BuildTextureRGBA(u8 *data, size_t w, size_t h)
Called each frame to generate the texture to render on the terrain.
Definition: HierarchicalPathfinder.h:310
u8 m_ChunkI
Definition: HierarchicalPathfinder.h:170
u16 m_H
Definition: HierarchicalPathfinder.h:280
u16 bestI
Definition: HierarchicalPathfinder.h:257
bool operator<(const RegionID &b) const
Definition: HierarchicalPathfinder.h:76
std::map< pass_class_t, std::vector< Chunk > > m_Chunks
Definition: HierarchicalPathfinder.h:282
#define cassert(expr)
Compile-time assertion.
Definition: code_annotation.h:207
const CSimContext * m_SimContext
Definition: HierarchicalPathfinder.h:294
std::map< RegionID, std::set< RegionID > > EdgesMap
Definition: HierarchicalPathfinder.h:199
u16 gj
Definition: HierarchicalPathfinder.h:272
static const u8 CHUNK_SIZE
Definition: HierarchicalPathfinder.h:165
bool IsGoalReachable(u16 i0, u16 j0, const PathGoal &goal, pass_class_t passClass) const
Definition: HierarchicalPathfinder.cpp:710
u16 r
Definition: HierarchicalPathfinder.h:72
std::vector< SOverlayLine > m_DebugOverlayLines
Definition: HierarchicalPathfinder.h:297
std::map< pass_class_t, EdgesMap > m_Edges
Definition: HierarchicalPathfinder.h:284
std::map< pass_class_t, std::map< RegionID, GlobalRegionID > > m_GlobalRegions
Definition: HierarchicalPathfinder.h:286
void UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap &edges)
Connect a chunk's regions to their neighbors.
Definition: HierarchicalPathfinder.cpp:542