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)
	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)
int	GetJumpPointUp (int i, int j, const PathGoal &goal)
int	GetJumpPointDown (int i, int j, const PathGoal &goal)

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

typedef RowRaw JumpPointCache::Row

private

Member Function Documentation

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.

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

inline

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

inline

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

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.

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

inline

size_t JumpPointCache::GetMemoryUsage ( ) const

inline

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

inline

Member Data Documentation

int JumpPointCache::m_Height

std::vector<Row> JumpPointCache::m_JumpPointsDown

std::vector<Row> JumpPointCache::m_JumpPointsLeft

std::vector<Row> JumpPointCache::m_JumpPointsRight

std::vector<Row> JumpPointCache::m_JumpPointsUp

int JumpPointCache::m_Width

---

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

• /var/svn/checkout/source/simulation2/helpers/LongPathfinder.cpp