craStar Class Reference

The pra* search algorithm which does partial pathfinding using abstraction. More...

#include <craStar.h>

Inheritance diagram for craStar:

[legend]Collaboration diagram for craStar:

[legend]List of all members.


Public Types
enum	Direction { NORTH, EAST, SOUTH, WEST, NE, SE, SW, NW }
enum	SmoothType { BEGIN, END, TWO_BACK }
Public Member Functions
	craStar ()
virtual	~craStar ()
virtual path *	getPath (graphAbstraction aMap, node from, node to, reservationProvider rp=0)
virtual const char *	getName ()
void	setPartialPathLimit (int limit)
int	getPartialPathLimit ()
void	setSmoothing (bool smooth)
	Set whether the path will be smoothed or not.
void	setSmoothType (SmoothType s)
	Set the smoothing type.Default is BEGIN.
void	setAbstractLevel (int level)
	set the abstract level
Protected Member Functions
void	setupSearch (graphAbstraction aMap, std::vector< node > &fromChain, node from, std::vector< node > &toChain, node *to)
void	findGoalNode (graphAbstraction aMap, node n, std::vector< node * > &toChain)
	GIven an abstract level parent node n, find a new goal that is a 0-level child of n as well as the parent chain linking them.
path *	buildNextAbstractPath (graphAbstraction , path lastPath, std::vector< node * > &fromChain, std::vector< node * > &toChain, reservationProvider *)
path *	trimPath (path lastPath, node origDest)
path *	buildAbstractPath (graphAbstraction aMap, std::vector< node > &fromChain, std::vector< node * > &toChain, reservationProvider *rp)
	Build an abstract path for quick refinement.
path *	doRefinement (graphAbstraction aMap, path absPath, std::vector< node * > &fromChain, std::vector< node * > &toChain)
	Do a quick refinement of an abstract path.
node *	getNextNode (graphAbstraction aMap, node currentLow, path returnPath, path apath, graph *g, int abstractLevel)
	Find the next node of the refined path.
path *	smoothPath (graphAbstraction m, path p)
	copied from hpaStar.cpp
path *	nextPathNode (graphAbstraction m, node n, int dir)
	shoot a ray in direction dir and see if you hit the path Return the better path if you find it; 0 if you hit a wall or obstacle (ie.
node *	getNextNode (mapAbstraction *m, int x, int y, int dir)
	get the next node from map coordinates (x,y) in direction dir.
bool	nextInLookup (int last, int curr, std::vector< node * > lookup)
	find out whether last is the next 'real' index in the lookup table after curr.
int	backTwoNodes (int i, std::vector< node * > lookup)
	Find the index of the node two nodes back in the path.
void	findMinMax (path *p)
	Find the box that bounds the path for more efficient path smoothing.
Protected Attributes
int	partialLimit
bool	expandSearchRadius
corridorAStar	cAStar
char	algName [30]
std::vector< node * >	lookup
SmoothType	smType
bool	smoothing
int	absLevel
int	minx
int	maxx
int	miny
int	maxy

Detailed Description

The pra* search algorithm which does partial pathfinding using abstraction.

Member Enumeration Documentation

enum craStar::Direction

Enumeration values:

NORTH

EAST

SOUTH

WEST

NE

SE

SW

NW

enum craStar::SmoothType

Enumeration values:

BEGIN

END

TWO_BACK

Constructor & Destructor Documentation

craStar::craStar ( )

virtual craStar::~craStar ( ) [inline, virtual]

Member Function Documentation

int craStar::backTwoNodes ( int i,

std::vector< node * > lookupVal

) [protected]

Find the index of the node two nodes back in the path.

path * craStar::buildAbstractPath ( graphAbstraction * aMap,

std::vector< node * > & fromChain,

std::vector< node * > & toChain,

reservationProvider * rp

) [protected]

Build an abstract path for quick refinement.

path * craStar::buildNextAbstractPath ( graphAbstraction * ,

path * lastPath,

std::vector< node * > & fromChain,

std::vector< node * > & toChain,

reservationProvider *

) [protected]

path * craStar::doRefinement ( graphAbstraction * aMap,

path * absPath,

std::vector< node * > & fromChain,

std::vector< node * > & toChain

) [protected]

Do a quick refinement of an abstract path.

void craStar::findGoalNode ( graphAbstraction * aMap,

node * n,

std::vector< node * > & toChain

) [protected]

GIven an abstract level parent node n, find a new goal that is a 0-level child of n as well as the parent chain linking them.
The parent chain will be stores in toChain.

void craStar::findMinMax ( path * p ) [protected]

Find the box that bounds the path for more efficient path smoothing.

virtual const char* craStar::getName ( ) [inline, virtual]

Implements searchAlgorithm.

node * craStar::getNextNode ( mapAbstraction * m,

int x,

int y,

int dir

) [protected]

get the next node from map coordinates (x,y) in direction dir.
Will return 0 if there's no node here.

node * craStar::getNextNode ( graphAbstraction * aMap,

node * currentLow,

path * returnPath,

path * apath,

graph * g,

int abstractLevel

) [protected]

Find the next node of the refined path.

int craStar::getPartialPathLimit ( ) [inline]

path * craStar::getPath ( graphAbstraction * aMap,

node * from,

node * to,

reservationProvider * rp = 0

) [virtual]

Implements searchAlgorithm.

bool craStar::nextInLookup ( int last,

int curr,

std::vector< node * > lookupVal

) [protected]

find out whether last is the next 'real' index in the lookup table after curr.
This is to make sure we don't keep replacing little paths due to null's in the lookup table.

path * craStar::nextPathNode ( graphAbstraction * m,

node * n,

int dir

) [protected]

shoot a ray in direction dir and see if you hit the path Return the better path if you find it; 0 if you hit a wall or obstacle (ie.
if you won't find the path)

void craStar::setAbstractLevel ( int level ) [inline]

set the abstract level
if the level is smaller than 1, the abstract level is chosen dynamically.

void craStar::setPartialPathLimit ( int limit ) [inline]

void craStar::setSmoothing ( bool smooth ) [inline]

Set whether the path will be smoothed or not.
Default is TRUE.

void craStar::setSmoothType ( SmoothType s ) [inline]

Set the smoothing type.Default is BEGIN.
Whenever we update the path with a better subpath, if s = BEGIN, smoothing is restarted from the beginning of this subpath if s = END, smoothing is restarted from the end of the new subpath if s = TWO_BACK, we go back two from the end of the new subpath

void craStar::setupSearch ( graphAbstraction * aMap,

std::vector< node * > & fromChain,

node * from,

std::vector< node * > & toChain,

node * to

) [protected]

path * craStar::smoothPath ( graphAbstraction * m,

path * p

) [protected]

copied from hpaStar.cpp
smoothen the path by replacing parts of the path by straight lines.