Pyrogenesis  trunk
Functions | Variables
Pathfinding Namespace Reference

Functions

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 TileCenter (u16 i, u16 j, entity_pos_t &x, entity_pos_t &z)
 Returns the position of the center of the given tile. More...
 
void NavcellCenter (u16 i, u16 j, entity_pos_t &x, entity_pos_t &z)
 
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)
 

Variables

const int NAVCELLS_PER_TILE = 4
 The long-range pathfinder operates primarily over a navigation grid (a uniform-cost 2D passability grid, with horizontal/vertical (not diagonal) connectivity). More...
 
const fixed NAVCELL_SIZE = fixed::FromInt((int)TERRAIN_TILE_SIZE) / Pathfinding::NAVCELLS_PER_TILE
 Size of a navcell in metres ( = TERRAIN_TILE_SIZE / NAVCELLS_PER_TILE) More...
 
const int NAVCELL_SIZE_INT = 1
 
const int NAVCELL_SIZE_LOG2 = 0
 
const entity_pos_t GOAL_DELTA = NAVCELL_SIZE/8
 For extending the goal outwards/inwards a little bit NOTE: keep next to the definition of NAVCELL_SIZE to avoid init order problems between translation units. More...
 
const 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

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 
)
inline
void Pathfinding::NavcellCenter ( u16  i,
u16  j,
entity_pos_t x,
entity_pos_t z 
)
inline
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

void Pathfinding::TileCenter ( u16  i,
u16  j,
entity_pos_t x,
entity_pos_t z 
)
inline

Returns the position of the center of the given tile.

Variable Documentation

const entity_pos_t Pathfinding::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.

So we extend the clearance radius by 1.

const entity_pos_t Pathfinding::GOAL_DELTA = NAVCELL_SIZE/8

For extending the goal outwards/inwards a little bit NOTE: keep next to the definition of NAVCELL_SIZE to avoid init order problems between translation units.

TODO: figure out whether this is actually needed. It was added back in r8751 (in 2010) for unclear reasons and it does not seem to really improve behavior today

const fixed Pathfinding::NAVCELL_SIZE = fixed::FromInt((int)TERRAIN_TILE_SIZE) / Pathfinding::NAVCELLS_PER_TILE

Size of a navcell in metres ( = TERRAIN_TILE_SIZE / NAVCELLS_PER_TILE)

const int Pathfinding::NAVCELL_SIZE_INT = 1
const int Pathfinding::NAVCELL_SIZE_LOG2 = 0
const int Pathfinding::NAVCELLS_PER_TILE = 4

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 terrain tile into NxN "nav cells" (for some integer N, preferably a power of two).