Pathfinding Namespace Reference

Functions
bool	CheckLineMovement (entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1, pass_class_t passClass, const Grid< NavcellData > &grid)
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, i.e. More...
void	TerrainTileCenter (u16 i, u16 j, entity_pos_t &x, entity_pos_t &z)
	Returns the position of the center of the given terrain tile. More...
void	NavcellCenter (u16 i, u16 j, entity_pos_t &x, entity_pos_t &z)

Variables
constexpr fixed	NAVCELL_SIZE = fixed::FromInt(1)
	The long-range pathfinder operates primarily over a navigation grid (a uniform-cost 2D passability grid, with horizontal/vertical (not diagonal) connectivity). More...
constexpr int	NAVCELL_SIZE_INT = 1
constexpr int	NAVCELL_SIZE_LOG2 = 0
constexpr int	NAVCELLS_PER_TERRAIN_TILE = TERRAIN_TILE_SIZE / NAVCELL_SIZE_INT
	The terrain grid is coarser, and it is often convenient to convert from one to the other. More...
constexpr entity_pos_t	CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1)
	To make sure the long-range pathfinder is more strict than the short-range one, we need to slightly over-rasterize. More...

Function Documentation

CheckLineMovement()

bool Pathfinding::CheckLineMovement	(	entity_pos_t	x0,
		entity_pos_t	z0,
		entity_pos_t	x1,
		entity_pos_t	z1,
		pass_class_t	passClass,
		const Grid< NavcellData > &	grid
	)

NavcellCenter()

void Pathfinding::NavcellCenter ( u16  i, u16  j, entity_pos_t &  x, entity_pos_t &  z  )

inline

NearestNavcell()

void Pathfinding::NearestNavcell ( entity_pos_t  x, entity_pos_t  z, u16 &  i, u16 &  j, u16  w, u16  h  )

inline

Compute the navcell indexes on the grid nearest to a given point w, h are the grid dimensions, i.e.

the number of navcells per side

TerrainTileCenter()

void Pathfinding::TerrainTileCenter ( u16  i, u16  j, entity_pos_t &  x, entity_pos_t &  z  )

inline

Returns the position of the center of the given terrain tile.

Variable Documentation

CLEARANCE_EXTENSION_RADIUS

constexpr entity_pos_t Pathfinding::CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1)

inlineconstexpr

To make sure the long-range pathfinder is more strict than the short-range one, we need to slightly over-rasterize.

So we extend the clearance radius by 1.

NAVCELL_SIZE

constexpr fixed Pathfinding::NAVCELL_SIZE = fixed::FromInt(1)

inlineconstexpr

The long-range pathfinder operates primarily over a navigation grid (a uniform-cost 2D passability grid, with horizontal/vertical (not diagonal) connectivity).

This is based on the terrain tile passability, plus the rasterized shapes of obstructions, all expanded outwards by the radius of the units. Since units are much smaller than terrain tiles, the nav grid should be higher resolution than the tiles. We therefore split each the world into NxN "nav cells" (for some integer N, preferably a power of two).

NAVCELL_SIZE_INT

constexpr int Pathfinding::NAVCELL_SIZE_INT = 1

inlineconstexpr

NAVCELL_SIZE_LOG2

constexpr int Pathfinding::NAVCELL_SIZE_LOG2 = 0

inlineconstexpr

NAVCELLS_PER_TERRAIN_TILE

constexpr int Pathfinding::NAVCELLS_PER_TERRAIN_TILE = TERRAIN_TILE_SIZE / NAVCELL_SIZE_INT

inlineconstexpr

The terrain grid is coarser, and it is often convenient to convert from one to the other.