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

#include <CRAStar.h>

Inheritance diagram for craStar:

Collaboration diagram for craStar:

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. More...

void	setSmoothType (SmoothType s)
	Set the smoothing type.Default is BEGIN. More...

void	setAbstractLevel (int level)
	set the abstract level More...

Public Member Functions inherited from SearchAlgorithm
	SearchAlgorithm ()

virtual	~SearchAlgorithm ()

uint64_t	GetNodesExpanded ()

uint64_t	GetNodesTouched ()

virtual void	LogFinalStats (StatCollection *)

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. More...

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. More...

path *	doRefinement (GraphAbstraction aMap, path absPath, std::vector< node * > &fromChain, std::vector< node * > &toChain)
	Do a quick refinement of an abstract path. More...

node *	getNextNode (GraphAbstraction aMap, node currentLow, path returnPath, path apath, Graph *g, int abstractLevel)
	Find the next node of the refined path. More...

path *	smoothPath (GraphAbstraction m, path p)
	copied from hpaStar.cpp More...

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. More...

node *	getNextNode (MapAbstraction *m, int x, int y, int dir)
	get the next node from map coordinates (x,y) in direction dir. More...

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. More...

int	backTwoNodes (int i, std::vector< node * > lookup)
	Find the index of the node two nodes back in the path. More...

void	findMinMax (path *p)
	Find the box that bounds the path for more efficient path smoothing. More...

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

Additional Inherited Members
Public Attributes inherited from SearchAlgorithm
uint32_t	nodesExpanded

uint32_t	nodesTouched

Detailed Description

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

Definition at line 23 of file CRAStar.h.

Member Enumeration Documentation

◆ Direction

enum craStar::Direction

Enumerator
NORTH
EAST
SOUTH
WEST
NE
SE
SW
NW

Definition at line 27 of file CRAStar.h.

◆ SmoothType

enum craStar::SmoothType

Enumerator
BEGIN
END
TWO_BACK

Definition at line 37 of file CRAStar.h.

Constructor & Destructor Documentation

◆ craStar()

craStar::craStar ( )

Definition at line 22 of file CRAStar.cpp.

References absLevel, algName, BEGIN, expandSearchRadius, partialLimit, smoothing, and smType.

◆ ~craStar()

virtual craStar::~craStar ( )

inlinevirtual

Definition at line 44 of file CRAStar.h.

Member Function Documentation

◆ backTwoNodes()

int craStar::backTwoNodes	(	int	i,
		std::vector< node * >	lookup
	)

protected

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

Definition at line 680 of file CRAStar.cpp.

Referenced by smoothPath().

◆ buildAbstractPath()

path * craStar::buildAbstractPath	(	GraphAbstraction *	aMap,
		std::vector< node * > &	fromChain,
		std::vector< node * > &	toChain,
		reservationProvider *	rp
	)

protected

Build an abstract path for quick refinement.

Definition at line 174 of file CRAStar.cpp.

References SearchAlgorithm::GetNodesExpanded(), SearchAlgorithm::GetNodesTouched(), aStarOld::GetPath(), SearchAlgorithm::nodesExpanded, and SearchAlgorithm::nodesTouched.

Referenced by GetPath().

◆ buildNextAbstractPath()

path * craStar::buildNextAbstractPath	(	GraphAbstraction *	aMap,
		path *	lastPath,
		std::vector< node * > &	fromChain,
		std::vector< node * > &	toChain,
		reservationProvider *	rp
	)

protected

◆ doRefinement()

path * craStar::doRefinement	(	GraphAbstraction *	aMap,
		path *	absPath,
		std::vector< node * > &	fromChain,
		std::vector< node * > &	toChain
	)

protected

Do a quick refinement of an abstract path.

Definition at line 204 of file CRAStar.cpp.

References Graph::FindEdge(), GraphAbstraction::GetAbstractGraph(), node::GetLabelL(), node::getNeighborIter(), getNextNode(), Graph::GetNode(), GraphAbstraction::GetNthParent(), node::GetNum(), node::GetNumEdges(), GraphAbstractionConstants::kAbstractionLevel, path::n, path::next, node::nodeNeighborNext(), SearchAlgorithm::nodesTouched, path, edge::setMarked(), path::tail(), and verbose.

Referenced by GetPath().

◆ findGoalNode()

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.

Definition at line 106 of file CRAStar.cpp.

References GraphAbstraction::GetAbstractGraph(), node::GetLabelL(), Graph::GetNode(), GraphAbstractionConstants::kAbstractionLevel, and GraphAbstractionConstants::kFirstData.

Referenced by GetPath().

◆ findMinMax()

void craStar::findMinMax ( path * p )

protected

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

Definition at line 810 of file CRAStar.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kFirstData, MAX_INT, maxx, maxy, minx, miny, path::n, and path::next.

Referenced by smoothPath().

◆ GetName()

virtual const char* craStar::GetName ( )

inlinevirtual

Implements SearchAlgorithm.

Definition at line 46 of file CRAStar.h.

References algName.

◆ getNextNode() [1/2]

node * craStar::getNextNode	(	GraphAbstraction *	aMap,
		node *	currentLow,
		path *	returnPath,
		path *	apath,
		Graph *	g,
		int	abstractLevel
	)

protected

Find the next node of the refined path.

Definition at line 311 of file CRAStar.cpp.

References Graph::FindEdge(), node::getNeighborIter(), Graph::GetNode(), GraphAbstraction::GetNthParent(), node::GetNum(), node::GetNumEdges(), GraphAbstraction::h(), path::n, path::next, node::nodeNeighborNext(), SearchAlgorithm::nodesExpanded, SearchAlgorithm::nodesTouched, path, edge::setMarked(), and path::tail().

Referenced by doRefinement(), and nextPathNode().

◆ getNextNode() [2/2]

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.

Definition at line 771 of file CRAStar.cpp.

References EAST, maxx, maxy, minx, miny, NE, NORTH, NW, SE, SOUTH, SW, and WEST.

◆ getPartialPathLimit()

int craStar::getPartialPathLimit ( )

inline

Definition at line 50 of file CRAStar.h.

References partialLimit.

◆ GetPath()

path * craStar::GetPath	(	GraphAbstraction *	aMap,
		node *	from,
		node *	to,
		reservationProvider *	rp = `0`
	)

virtual

Implements SearchAlgorithm.

Definition at line 34 of file CRAStar.cpp.

References buildAbstractPath(), doRefinement(), Graph::FindEdge(), findGoalNode(), GraphAbstraction::GetAbstractGraph(), node::GetLabelL(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, path::n, path::next, partialLimit, path, setupSearch(), smoothing, smoothPath(), and path::tail().

◆ nextInLookup()

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.

Definition at line 703 of file CRAStar.cpp.

Referenced by smoothPath().

◆ nextPathNode()

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)

Definition at line 723 of file CRAStar.cpp.

References Graph::FindEdge(), GraphAbstraction::GetAbstractGraph(), node::GetLabelL(), getNextNode(), node::GetNum(), GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kTemporaryLabel, lookup, SearchAlgorithm::nodesTouched, and path.

Referenced by smoothPath().

◆ setAbstractLevel()

void craStar::setAbstractLevel ( int level )

inline

set the abstract level

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

Definition at line 73 of file CRAStar.h.

References absLevel.

◆ setPartialPathLimit()

void craStar::setPartialPathLimit ( int limit )

inline

Definition at line 48 of file CRAStar.h.

References algName, and partialLimit.

◆ setSmoothing()

void craStar::setSmoothing ( bool smooth )

inline

Set whether the path will be smoothed or not.

Default is TRUE.

Definition at line 55 of file CRAStar.h.

References smoothing.

◆ setSmoothType()

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

Definition at line 65 of file CRAStar.h.

References smType.

◆ setupSearch()

void craStar::setupSearch	(	GraphAbstraction *	aMap,
		std::vector< node * > &	fromChain,
		node *	from,
		std::vector< node * > &	toChain,
		node *	to
	)

protected

Definition at line 120 of file CRAStar.cpp.

References absLevel, GraphAbstraction::GetAbstractGraph(), node::GetNum(), GraphAbstraction::GetNumAbstractGraphs(), Graph::GetNumNodes(), SearchAlgorithm::nodesExpanded, SearchAlgorithm::nodesTouched, GraphAbstraction::Pathable(), and verbose.

Referenced by GetPath().

◆ smoothPath()

path * craStar::smoothPath	(	GraphAbstraction *	m,
		path *	p
	)

protected

copied from hpaStar.cpp

smoothen the path by replacing parts of the path by straight lines.

Definition at line 532 of file CRAStar.cpp.

References backTwoNodes(), END, findMinMax(), node::GetLabelL(), GraphAbstractionConstants::kTemporaryLabel, lookup, path::n, path::next, nextInLookup(), nextPathNode(), NORTH, NW, path, node::SetLabelL(), smType, path::tail(), TWO_BACK, and verbose.

Referenced by GetPath().

◆ trimPath()

path * craStar::trimPath	(	path *	lastPath,
		node *	origDest
	)

protected

Definition at line 499 of file CRAStar.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kParent, path::n, path::next, and partialLimit.

Member Data Documentation

◆ absLevel

int craStar::absLevel

protected

Definition at line 115 of file CRAStar.h.

Referenced by craStar(), setAbstractLevel(), and setupSearch().

◆ algName

char craStar::algName[30]

protected

Definition at line 101 of file CRAStar.h.

Referenced by craStar(), GetName(), and setPartialPathLimit().

◆ cAStar

corridorAStar craStar::cAStar

protected

Definition at line 100 of file CRAStar.h.

Referenced by buildNextAbstractPath().

◆ expandSearchRadius

bool craStar::expandSearchRadius

protected

Definition at line 99 of file CRAStar.h.

Referenced by buildNextAbstractPath(), and craStar().

◆ lookup

std::vector<node*> craStar::lookup

protected

Definition at line 105 of file CRAStar.h.

Referenced by nextPathNode(), and smoothPath().

◆ maxx

int craStar::maxx

protected

Definition at line 118 of file CRAStar.h.

Referenced by findMinMax(), and getNextNode().

◆ maxy

int craStar::maxy

protected

Definition at line 120 of file CRAStar.h.

Referenced by findMinMax(), and getNextNode().

◆ minx

int craStar::minx

protected

Definition at line 117 of file CRAStar.h.

Referenced by findMinMax(), and getNextNode().

◆ miny

int craStar::miny

protected

Definition at line 119 of file CRAStar.h.

Referenced by findMinMax(), and getNextNode().

◆ partialLimit

int craStar::partialLimit

protected

Definition at line 98 of file CRAStar.h.

Referenced by buildNextAbstractPath(), craStar(), getPartialPathLimit(), GetPath(), setPartialPathLimit(), and trimPath().

◆ smoothing

bool craStar::smoothing

protected

Definition at line 114 of file CRAStar.h.

Referenced by craStar(), GetPath(), and setSmoothing().

◆ smType

SmoothType craStar::smType

protected

Definition at line 113 of file CRAStar.h.

Referenced by craStar(), setSmoothType(), and smoothPath().

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

/home/sturtevant/nightly/hog2/abstractionalgorithms/CRAStar.h
/home/sturtevant/nightly/hog2/abstractionalgorithms/CRAStar.cpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ Direction

◆ SmoothType

Constructor & Destructor Documentation

◆ craStar()

◆ ~craStar()

Member Function Documentation

◆ backTwoNodes()

◆ buildAbstractPath()

◆ buildNextAbstractPath()

◆ doRefinement()

◆ findGoalNode()

◆ findMinMax()

◆ GetName()

◆ getNextNode() [1/2]

◆ getNextNode() [2/2]

◆ getPartialPathLimit()

◆ GetPath()

◆ nextInLookup()

◆ nextPathNode()

◆ setAbstractLevel()

◆ setPartialPathLimit()

◆ setSmoothing()

◆ setSmoothType()

◆ setupSearch()

◆ smoothPath()

◆ trimPath()

Member Data Documentation

◆ absLevel

◆ algName

◆ cAStar

◆ expandSearchRadius

◆ lookup

◆ maxx

◆ maxy

◆ minx

◆ miny

◆ partialLimit

◆ smoothing

◆ smType