HPA* algorithm as described in (Botea,Mueller,Schaeffer 2004). More...

#include <HPAStar.h>

Inheritance diagram for hpaStar:

Collaboration diagram for hpaStar:

[legend]

Public Types
enum	Direction { NORTH, EAST, SOUTH, WEST, NE, SE, SW, NW }

enum	SmoothType { BEGIN, END, TWO_BACK }

Public Member Functions
	hpaStar ()

virtual	~hpaStar ()

virtual path *	GetPath (GraphAbstraction aMap, node from, node to, reservationProvider rp=0)
	Returns the HPA* path between from and to. More...

virtual const char *	GetName ()

void	setUpSearch (node from, node to)

path *	findAbstractPath (node from, node to)

path *	findMapPath (path abPath, node from, node *to)

void	cleanUpSearch ()
	Remove the start & goal nodes from the Graph. More...

path *	smoothPath (path *p)
	from HPA* smoothwizard.cpp More...

void	setSmoothing (bool smooth)
	Set whether we want to do path smoothing. More...

void	setPartialPathLimit (int limit)

int	getPartialPathLimit ()

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

void	setAbstraction (ClusterAbstraction *_m)

Public Member Functions inherited from SearchAlgorithm
	SearchAlgorithm ()

virtual	~SearchAlgorithm ()

uint64_t	GetNodesExpanded ()

uint64_t	GetNodesTouched ()

virtual void	LogFinalStats (StatCollection *)

Protected Member Functions
path *	nextPathNode (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 (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)

Protected Attributes
char	algName [30]

ClusterAbstraction *	m

int	partialLimit

node *	fromnum

node *	tonum

std::vector< node * >	lookup

bool	smoothing

SmoothType	smType

int	minx

int	maxx

int	miny

int	maxy

Additional Inherited Members
Public Attributes inherited from SearchAlgorithm
uint32_t	nodesExpanded

uint32_t	nodesTouched

Detailed Description

HPA* algorithm as described in (Botea,Mueller,Schaeffer 2004).

Needs a ClusterAbstraction to run - use setAbstraction before doing any pathfinding

Definition at line 21 of file HPAStar.h.

Member Enumeration Documentation

◆ Direction

enum hpaStar::Direction

Enumerator
NORTH
EAST
SOUTH
WEST
NE
SE
SW
NW

Definition at line 25 of file HPAStar.h.

◆ SmoothType

enum hpaStar::SmoothType

Enumerator
BEGIN
END
TWO_BACK

Definition at line 35 of file HPAStar.h.

Constructor & Destructor Documentation

◆ hpaStar()

hpaStar::hpaStar ( )

Definition at line 19 of file HPAStar.cpp.

◆ ~hpaStar()

virtual hpaStar::~hpaStar ( )

inlinevirtual

Definition at line 41 of file HPAStar.h.

Member Function Documentation

◆ backTwoNodes()

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

protected

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

Definition at line 434 of file HPAStar.cpp.

◆ cleanUpSearch()

void hpaStar::cleanUpSearch ( )

Remove the start & goal nodes from the Graph.

Definition at line 280 of file HPAStar.cpp.

◆ findAbstractPath()

path * hpaStar::findAbstractPath	(	node *	from,
		node *	to
	)

Definition at line 172 of file HPAStar.cpp.

References SearchAlgorithm::GetNodesExpanded(), SearchAlgorithm::GetNodesTouched(), aStarOld::GetPath(), path::Print(), and verbose.

◆ findMapPath()

path * hpaStar::findMapPath	(	path *	abPath,
		node *	from,
		node *	to
	)

Definition at line 198 of file HPAStar.cpp.

References Graph::FindEdge(), node::GetNum(), path::n, path::next, path, path::reverse(), and path::tail().

◆ findMinMax()

void hpaStar::findMinMax ( path * p )

protected

Definition at line 550 of file HPAStar.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kFirstData, MAX_INT, path::n, and path::next.

◆ GetName()

virtual const char* hpaStar::GetName ( )

inlinevirtual

Implements SearchAlgorithm.

Definition at line 45 of file HPAStar.h.

References algName.

◆ getNextNode()

node * hpaStar::getNextNode	(	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 514 of file HPAStar.cpp.

◆ getPartialPathLimit()

int hpaStar::getPartialPathLimit ( )

inline

Definition at line 54 of file HPAStar.h.

References partialLimit.

◆ GetPath()

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

virtual

Returns the HPA* path between from and to.

Before calling this function, set the abstraction with hpaStar::setAbstraction. The abstraction must be of type ClusterAbstraction.

Reservation provider isn't used

Implements SearchAlgorithm.

Definition at line 45 of file HPAStar.cpp.

References node::GetLabelF(), SearchAlgorithm::GetNodesExpanded(), SearchAlgorithm::GetNodesTouched(), aStarOld::GetPath(), GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, path::n, path::next, path, point3d, path::tail(), and verbose.

◆ nextInLookup()

bool hpaStar::nextInLookup	(	int	last,
		int	curr,
		std::vector< node * >	lookupVec
	)

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 453 of file HPAStar.cpp.

◆ nextPathNode()

path * hpaStar::nextPathNode	(	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 473 of file HPAStar.cpp.

References Graph::FindEdge(), node::GetLabelL(), node::GetNum(), GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kTemporaryLabel, and path.

◆ setAbstraction()

void hpaStar::setAbstraction ( ClusterAbstraction * _m )

inline

Definition at line 66 of file HPAStar.h.

References m.

◆ setPartialPathLimit()

void hpaStar::setPartialPathLimit ( int limit )

inline

Definition at line 52 of file HPAStar.h.

References algName, and partialLimit.

◆ setSmoothing()

void hpaStar::setSmoothing ( bool smooth )

Set whether we want to do path smoothing.

Default is true.

Definition at line 33 of file HPAStar.cpp.

◆ setSmoothType()

void hpaStar::setSmoothType ( SmoothType s )

inline

Set the smoothing type.

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 63 of file HPAStar.h.

References smType.

◆ setUpSearch()

void hpaStar::setUpSearch	(	node *	from,
		node *	to
	)

Definition at line 148 of file HPAStar.cpp.

References verbose.

◆ smoothPath()

path * hpaStar::smoothPath ( path * p )

from HPA* smoothwizard.cpp

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

Definition at line 299 of file HPAStar.cpp.

References node::GetLabelL(), GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kTemporaryLabel, path::n, path::next, path, node::SetLabelL(), path::tail(), and verbose.

Member Data Documentation

◆ algName

char hpaStar::algName[30]

protected

Definition at line 69 of file HPAStar.h.

Referenced by GetName(), and setPartialPathLimit().

◆ fromnum

node* hpaStar::fromnum

protected

Definition at line 72 of file HPAStar.h.

◆ lookup

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

protected

Definition at line 74 of file HPAStar.h.

◆ m

ClusterAbstraction* hpaStar::m

protected

Definition at line 70 of file HPAStar.h.

Referenced by setAbstraction().

◆ maxx

int hpaStar::maxx

protected

Definition at line 83 of file HPAStar.h.

◆ maxy

int hpaStar::maxy

protected

Definition at line 85 of file HPAStar.h.

◆ minx

int hpaStar::minx

protected

Definition at line 82 of file HPAStar.h.

◆ miny

int hpaStar::miny

protected

Definition at line 84 of file HPAStar.h.

◆ partialLimit

int hpaStar::partialLimit

protected

Definition at line 71 of file HPAStar.h.

Referenced by getPartialPathLimit(), and setPartialPathLimit().

◆ smoothing

bool hpaStar::smoothing

protected

Definition at line 77 of file HPAStar.h.

◆ smType

SmoothType hpaStar::smType

protected

Definition at line 78 of file HPAStar.h.

Referenced by setSmoothType().

◆ tonum

node* hpaStar::tonum

protected

Definition at line 73 of file HPAStar.h.

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

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

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ Direction

◆ SmoothType

Constructor & Destructor Documentation

◆ hpaStar()

◆ ~hpaStar()

Member Function Documentation

◆ backTwoNodes()

◆ cleanUpSearch()

◆ findAbstractPath()

◆ findMapPath()

◆ findMinMax()

◆ GetName()

◆ getNextNode()

◆ getPartialPathLimit()

◆ GetPath()

◆ nextInLookup()

◆ nextPathNode()

◆ setAbstraction()

◆ setPartialPathLimit()

◆ setSmoothing()

◆ setSmoothType()

◆ setUpSearch()

◆ smoothPath()

Member Data Documentation

◆ algName

◆ fromnum

◆ lookup

◆ m

◆ maxx

◆ maxy

◆ minx

◆ miny

◆ partialLimit

◆ smoothing

◆ smType

◆ tonum