---

AStar Class Reference

This is an implementation of the A* methodology. More...

#include <astar.h>

Inheritance diagram for AStar:

Public Member Functions
	AStar (OGrid *grid)
	Initialize with occupancy grid.
bool	search (motion_chain &path, motion start, motion goal)
uint8	cost (int i, int j)
	return cost of location x,y
int	cost (int x, int y, CELL_STATE ctype, node_chain *shadow_nodes=NULL)
void	update_nodes (node_chain &changed_nodes)
Node *	node (uint8 x, uint8 y)
void	InitStar (void)
void	path_flag (motion_chain &path)
	Mark all segments in motion chain as within path.
Protected Member Functions
	AStar (void)
void	GetChildren (Node *n, Node *child[EDGES+1])
void	mark (int x, int y)
Protected Attributes
Node	_field [MAX_STAR_NODES]
OGrid *	_ogrid

---

Detailed Description

This is an implementation of the A* methodology.

The A* is a search strategy of the form F = G + H where G is actual cost from start to current node, and H is a heuristic cost from current node to goal. The two most common heuristics used are:

• Euclidean distance (this is used here): straight line distance.
• Manhattan distance : distance counting nodes up and across.

The Manhanttan distance is purported to be better in a lot of cases to the Euclidean distance.

---

Constructor & Destructor Documentation

AStar (  OGrid *  grid  )

Initialize with occupancy grid.

AStar (  void   )  [protected]

---

Member Function Documentation

int cost (  int  x, int  y, CELL_STATE  ctype, node_chain *  shadow_nodes = NULL )  [inherited]

set cost of node location x,y. incrementally updates all nodes whose cost has changed.

uint8 cost (  int  i, int  j )  [inherited]

return cost of location x,y

void GetChildren (  Node *  n, Node *  child[EDGES+1] )  [protected, inherited]

void InitStar (  void   )  [inherited]

cost has range 0..255; 0 is clear, and 255 is "absolute" obstacle (whatever that means). Can recommend areas not to take by setting cell to a value less than the MINIMUM_OBSTACLE value. Once the value exceeds MINIMUM_OBSTACLE, then the cell will not be evaluated in the A* algorithm.

void mark (  int  x, int  y )  [protected, inherited]

Node* node (  uint8  x, uint8  y )  [inherited]

Return Node at location x,y. (I forget why I needed this). Fills in a node with Terrain type specified.

void path_flag (  motion_chain &  path  )  [inherited]

Mark all segments in motion chain as within path.

bool search (  motion_chain &  path, motion  start, motion  goal )

Perform search and generate path from start to goal. The returned path has only position information, all _face values are 0, due to the nature of the algorithm. Parameters: path  The variable to return the generated path. start  The starting position of the entity. goal  The goal position of the entity. Returns: True if a successful path was found.

void update_nodes (  node_chain &  changed_nodes  )  [inherited]

this is done this way because the node_chain is only so big, so this allows nodes to be updated incrementally. Reimplemented in DStar.

---

Field Documentation

Node _field[MAX_STAR_NODES] [protected, inherited]

OGrid* _ogrid [protected, inherited]

---