JumpPointCache Class Reference

Jump point cache. More...

Classes
struct	RowRaw
	Simple space-inefficient row storage. More...
struct	RowTree

Public Member Functions
void	ComputeRows (std::vector< Row > &rows, const Grid< NavcellData > &terrain, pass_class_t passClass, bool transpose, bool mirror)
	Compute the cached obstruction/jump points for each cell, in a single direction. More...
void	reset (const Grid< NavcellData > *terrain, pass_class_t passClass)
size_t	GetMemoryUsage () const
int	GetJumpPointRight (int i, int j, const PathGoal &goal) const
	Returns the next jump point (or goal point) to explore, at (ip, j) where i < ip. More...
int	GetJumpPointLeft (int i, int j, const PathGoal &goal) const
int	GetJumpPointUp (int i, int j, const PathGoal &goal) const
int	GetJumpPointDown (int i, int j, const PathGoal &goal) const

Public Attributes
int	m_Width
int	m_Height
std::vector< Row >	m_JumpPointsRight
std::vector< Row >	m_JumpPointsLeft
std::vector< Row >	m_JumpPointsUp
std::vector< Row >	m_JumpPointsDown

Private Types
typedef RowRaw	Row

Detailed Description

Jump point cache.

The JPS algorithm wants to efficiently either find the first jump point in some direction from some cell (not counting the cell itself), if it is reachable without crossing any impassable cells; or know that there is no such reachable jump point. The jump point is always on a passable cell. We cache that data to allow fast lookups, which helps performance significantly (especially on sparse maps). Recalculation might be expensive but the underlying passability data changes relatively rarely.

To allow the algorithm to detect goal cells, we want to treat them as jump points too. (That means the algorithm will push those cells onto its open queue, and will eventually pop a goal cell and realise it's done.) (Goals might be circles/squares/etc, not just a single cell.) But the goal generally changes for every path request, so we can't cache it like the normal jump points. Instead, if there's no jump point from some cell then we'll cache the first impassable cell as an 'obstruction jump point' (with a flag to distinguish from a real jump point), and then the caller can test whether the goal includes a cell that's closer than the first (obstruction or real) jump point, and treat the goal cell as a jump point in that case.

We only ever need to find the jump point relative to a passable cell; the cache is allowed to return bogus values for impassable cells.

Member Typedef Documentation

Row

typedef RowRaw JumpPointCache::Row

private

Member Function Documentation

ComputeRows()

void JumpPointCache::ComputeRows ( std::vector< Row > &  rows, const Grid< NavcellData > &  terrain, pass_class_t  passClass, bool  transpose, bool  mirror  )

inline

Compute the cached obstruction/jump points for each cell, in a single direction.

By default the code assumes the rightwards (+i) direction; set 'transpose' to switch to upwards (+j), and/or set 'mirror' to reverse the direction.

GetJumpPointDown()

int JumpPointCache::GetJumpPointDown ( int  i, int  j, const PathGoal &  goal  ) const

inline

GetJumpPointLeft()

int JumpPointCache::GetJumpPointLeft ( int  i, int  j, const PathGoal &  goal  ) const

inline

GetJumpPointRight()

int JumpPointCache::GetJumpPointRight ( int  i, int  j, const PathGoal &  goal  ) const

inline

Returns the next jump point (or goal point) to explore, at (ip, j) where i < ip.

Returns i if there is no such point.

GetJumpPointUp()

int JumpPointCache::GetJumpPointUp ( int  i, int  j, const PathGoal &  goal  ) const

inline

GetMemoryUsage()

size_t JumpPointCache::GetMemoryUsage ( ) const

inline

reset()

void JumpPointCache::reset ( const Grid< NavcellData > *  terrain, pass_class_t  passClass  )

inline

Member Data Documentation

m_Height

int JumpPointCache::m_Height

m_JumpPointsDown

std::vector<Row> JumpPointCache::m_JumpPointsDown

m_JumpPointsLeft

std::vector<Row> JumpPointCache::m_JumpPointsLeft

m_JumpPointsRight

std::vector<Row> JumpPointCache::m_JumpPointsRight

m_JumpPointsUp

std::vector<Row> JumpPointCache::m_JumpPointsUp

m_Width

int JumpPointCache::m_Width

---

The documentation for this class was generated from the following file:

• /home/docker/jenkins/workspace/technical-docs/source/simulation2/helpers/LongPathfinder.cpp