18 #ifndef INCLUDED_LONGPATHFINDER 19 #define INCLUDED_LONGPATHFINDER 28 #define ACCEPT_DIAGONAL_GAPS 0 69 STATUS_UNEXPLORED = 0,
74 bool IsUnexplored()
const {
return GetStatus() == STATUS_UNEXPLORED; }
75 bool IsOpen()
const {
return GetStatus() == STATUS_OPEN; }
76 bool IsClosed()
const {
return GetStatus() == STATUS_CLOSED; }
81 inline int GetPredI(
int i)
const {
return i + GetPredDI(); }
82 inline int GetPredJ(
int j)
const {
return j + GetPredDJ(); }
106 return (
i32)data >> 17;
111 return ((
i32)data << 15) >> 17;
119 ASSERT(-16384 <= di && di < 16384);
120 ASSERT(-16384 <= dj && dj < 16384);
122 data |= (((
u32)di & 0x7FFF) << 17) | (((
u32)dj & 0x7FFF) << 2);
167 void SetDebugOverlay(
bool enabled);
171 m_PathfinderHier.SetDebugOverlay(enabled, simContext);
182 ComputePath(x0, z0, goal, passClass, *m_DebugPath);
183 m_DebugPassClass = passClass;
187 const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks,
188 const std::map<std::string, pass_class_t>& pathfindingPassClassMasks)
190 m_Grid = passabilityGrid;
192 m_GridSize = passabilityGrid->
m_W;
194 m_JumpPointCache.clear();
196 m_PathfinderHier.Recompute(passabilityGrid, nonPathfindingPassClassMasks, pathfindingPassClassMasks);
201 m_Grid = passabilityGrid;
203 ASSERT(m_GridSize == passabilityGrid->
m_H);
205 m_JumpPointCache.clear();
207 m_PathfinderHier.Update(passabilityGrid, dirtinessGrid);
212 for (
size_t i = 0;
i < m_PathfinderHier.m_DebugOverlayLines.size(); ++
i)
213 collector.
Submit(&m_PathfinderHier.m_DebugOverlayLines[
i]);
226 LOGERROR(
"The pathfinder grid hasn't been setup yet, aborting ComputePath");
230 ComputeJPSPath(x0, z0, origGoal, passClass, path);
244 return m_PathfinderHier.GetConnectivityGrid(passClass);
249 GetDebugDataJPS(steps, time, grid);
265 PathCost CalculateHeuristic(
int i,
int j,
int iGoal,
int jGoal);
283 void GetDebugDataJPS(
u32& steps,
double& time,
Grid<u8>& grid)
const;
301 void GenerateSpecialMap(
pass_class_t passClass, std::vector<CircularRegion> excludedRegions);
333 for (
size_t j = 0;
j < h; ++
j)
335 for (
size_t i = 0;
i < w; ++
i)
341 if (debugGrid.
m_W && debugGrid.
m_H)
343 u8 n = debugGrid.
get((
int)i, (
int)j);
366 for (
size_t k = 0; k < waypoints.size(); ++k)
377 bool firstCell =
true;
380 if (data[(jp*w + ip)*4+3] == 0)
382 data[(jp*w + ip)*4+0] = 0xFF;
383 data[(jp*w + ip)*4+1] = 0xFF;
384 data[(jp*w + ip)*4+2] = 0xFF;
385 data[(jp*w + ip)*4+3] = firstCell ? 0xA0 : 0x60;
387 ip = ip < i ? ip+1 : ip > i ? ip-1 : ip;
388 jp = jp < j ? jp+1 : jp > j ? jp-1 : jp;
391 while (ip != i || jp != j);
398 #endif // INCLUDED_LONGPATHFINDER Represents the 2D coordinates of a tile.
Definition: LongPathfinder.h:37
A simple fixed-point number class.
Definition: Fixed.h:115
CircularRegion(entity_pos_t x, entity_pos_t z, entity_pos_t r)
Definition: LongPathfinder.h:128
u8 G
Definition: SColor.h:33
bool operator==(const TileID &b) const
Definition: LongPathfinder.h:43
#define LOGERROR(...)
Definition: CLogger.h:36
Similar to Grid, except optimised for sparse usage (the grid is subdivided into buckets whose content...
Definition: Grid.h:136
Grid< u16 > GetConnectivityGrid(pass_class_t passClass)
Definition: LongPathfinder.h:242
void SetDebugPath(entity_pos_t x0, entity_pos_t z0, const PathGoal &goal, pass_class_t passClass)
Definition: LongPathfinder.h:174
u16 pass_class_t
Definition: Pathfinding.h:29
bool m_UseJPSCache
Definition: LongPathfinder.h:303
Definition: Pathfinding.h:105
void GetDebugData(u32 &steps, double &time, Grid< u8 > &grid) const
Definition: LongPathfinder.h:247
Returned path.
Definition: Pathfinding.h:40
u32 data
Definition: LongPathfinder.h:89
u32 m_DebugSteps
Definition: LongPathfinder.h:258
uint16_t u16
Definition: types.h:38
pass_class_t m_DebugPassClass
Definition: LongPathfinder.h:262
u32 data
Definition: LongPathfinder.h:58
int GetPredDJ() const
Definition: LongPathfinder.h:109
u16 m_H
Definition: Grid.h:125
#define IS_PASSABLE(item, classmask)
Definition: Pathfinding.h:101
bool IsClosed() const
Definition: LongPathfinder.h:76
std::vector< Waypoint > m_Waypoints
Definition: Pathfinding.h:42
u16 jBest
Definition: LongPathfinder.h:154
void Update(Grid< NavcellData > *passabilityGrid, const Grid< u8 > &dirtinessGrid)
Definition: LongPathfinder.h:199
void ComputePath(entity_pos_t x0, entity_pos_t z0, const PathGoal &origGoal, pass_class_t passClass, WaypointPath &path)
Compute a tile-based path from the given point to the goal, and return the set of waypoints...
Definition: LongPathfinder.h:221
PathCost hBest
Definition: LongPathfinder.h:153
Pathfinder goal.
Definition: PathGoal.h:32
#define ASSERT(expr)
same as ENSURE in debug mode, does nothing in release mode.
Definition: debug.h:315
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
bool NavcellContainsGoal(int i, int j) const
Returns true if the given navcell contains a part of the goal area.
Definition: PathGoal.cpp:95
uint8_t u8
Definition: types.h:37
void HierarchicalRenderSubmit(SceneCollector &collector)
Definition: LongPathfinder.h:210
u32 steps
Definition: LongPathfinder.h:139
This interface accepts renderable objects.
Definition: Scene.h:83
u8 A
Definition: SColor.h:35
Jump point cache.
Definition: LongPathfinder.cpp:56
Definition: LongPathfinder.h:161
PathGoal m_DebugGoal
Definition: LongPathfinder.h:260
LongOverlay * m_DebugOverlay
Definition: LongPathfinder.h:256
int GetPredI(int i) const
Definition: LongPathfinder.h:81
uint32_t u32
Definition: types.h:39
const int NAVCELLS_PER_TILE
The long-range pathfinder operates primarily over a navigation grid (a uniform-cost 2D passability gr...
Definition: Pathfinding.h:117
Definition: HierarchicalPathfinder.h:47
void SetStatusOpen()
Definition: LongPathfinder.h:77
double m_DebugTime
Definition: LongPathfinder.h:259
PathCost g
Definition: LongPathfinder.h:88
void SetHierDebugOverlay(bool enabled, const CSimContext *simContext)
Definition: LongPathfinder.h:169
int GetPredDI() const
Definition: LongPathfinder.h:104
PathCost GetCost() const
Definition: LongPathfinder.h:84
Definition: LongPathfinder.h:137
virtual void BuildTextureRGBA(u8 *data, size_t w, size_t h)
Called each frame to generate the texture to render on the terrain.
Definition: LongPathfinder.h:323
TileID()
Definition: LongPathfinder.h:39
void SetStatus(u8 s)
Definition: LongPathfinder.h:97
int GetPredJ(int j) const
Definition: LongPathfinder.h:82
WaypointPath * m_DebugPath
Definition: LongPathfinder.h:261
u8 GetStatus() const
Definition: LongPathfinder.h:92
TileID(u16 i, u16 j)
Definition: LongPathfinder.h:41
#define SAFE_DELETE(p)
delete memory ensuing from new and set the pointer to zero (thus making double-frees safe / a no-op) ...
Definition: code_generation.h:111
pass_class_t passClass
Definition: LongPathfinder.h:145
Tile data for A* computation.
Definition: LongPathfinder.h:65
u8 R
Definition: SColor.h:32
u16 i() const
Definition: LongPathfinder.h:54
bool operator<(const TileID &b) const
Returns lexicographic order over (i,j)
Definition: LongPathfinder.h:49
Terrain overlay for pathfinder debugging.
Definition: LongPathfinder.h:313
int32_t i32
Definition: types.h:34
u16 m_GridSize
Definition: LongPathfinder.h:253
SparseGrid< PathfindTile > PathfindTileGrid
Definition: LongPathfinder.h:133
PathfindTileGrid * tiles
Definition: LongPathfinder.h:150
JumpPointCache * jpc
Definition: LongPathfinder.h:156
PathGoal goal
Definition: LongPathfinder.h:141
void Reload(Grid< NavcellData > *passabilityGrid, const std::map< std::string, pass_class_t > &nonPathfindingPassClassMasks, const std::map< std::string, pass_class_t > &pathfindingPassClassMasks)
Definition: LongPathfinder.h:186
void SetStatusClosed()
Definition: LongPathfinder.h:78
HierarchicalPathfinder m_PathfinderHier
Definition: LongPathfinder.h:306
Grid< NavcellData > * m_Grid
Definition: LongPathfinder.h:252
T & get(int i, int j) const
Definition: Grid.h:117
Base class for texture-based terrain overlays, with an arbitrary number of texels per terrain tile...
Definition: TerrainOverlay.h:174
bool IsUnexplored() const
Definition: LongPathfinder.h:74
Definition: LongPathfinder.h:126
void NearestNavcell(entity_pos_t x, entity_pos_t z, u16 &i, u16 &j, u16 w, u16 h)
Compute the navcell indexes on the grid nearest to a given point w, h are the grid dimensions...
Definition: Pathfinding.h:145
PriorityQueue open
Definition: LongPathfinder.h:147
std::map< pass_class_t, shared_ptr< JumpPointCache > > m_JumpPointCache
Definition: LongPathfinder.h:304
u16 m_W
Definition: Grid.h:125
bool IsOpen() const
Definition: LongPathfinder.h:75
void SetCost(PathCost cost)
Definition: LongPathfinder.h:85
LongPathfinder & m_Pathfinder
Definition: LongPathfinder.h:316
Represents the cost of a path consisting of horizontal/vertical and diagonal movements over a uniform...
Definition: Pathfinding.h:50
PathfindTileGrid * m_DebugGrid
Definition: LongPathfinder.h:257
u16 j() const
Definition: LongPathfinder.h:55
virtual void Submit(CPatch *patch)=0
Submit a terrain patch that is part of the scene.
LongOverlay(LongPathfinder &pathfinder)
Definition: LongPathfinder.h:318
Grid< NavcellData > * terrain
Definition: LongPathfinder.h:151
u16 jGoal
Definition: LongPathfinder.h:143
void SetPred(int pi, int pj, int i, int j)
Definition: LongPathfinder.h:115
entity_pos_t z
Definition: LongPathfinder.h:129
PriorityQueueHeap< TileID, PathCost, PathCost > PriorityQueue
Definition: LongPathfinder.h:132