A templated version of A*, based on HOG genericAStar. More...

#include <EPEAStar.h>

Inheritance diagram for EPEAStar< state, action, environment >:

Collaboration diagram for EPEAStar< state, action, environment >:

Public Member Functions
	EPEAStar ()

virtual	~EPEAStar ()

void	GetPath (environment *env, const state &from, const state &to, std::vector< state > &thePath)
	Perform an A* search between two states. More...

void	GetPath (environment *, const state &, const state &, std::vector< action > &)

bool	InitializeSearch (environment *env, const state &from, const state &to, std::vector< state > &thePath)
	Initialize the A* search. More...

bool	DoSingleSearchStep (std::vector< state > &thePath)
	Expand a single node. More...

void	AddAdditionalStartState (state &newState)
	Add additional start state to the search. More...

void	AddAdditionalStartState (state &newState, double cost)
	Add additional start state to the search. More...

state	CheckNextNode ()
	Returns the next state on the open list (but doesn't pop it off the queue). More...

void	ExtractPathToStart (state &node, std::vector< state > &thePath)

void	ExtractPathToStartFromID (uint64_t node, std::vector< state > &thePath)
	Get the path from a goal state to the start state. More...

virtual const char *	GetName ()
	Return the name of the algorithm. More...

void	PrintStats ()
	A function that prints the number of states in the closed list and open queue. More...

uint64_t	GetUniqueNodesExpanded ()

void	ResetNodeCount ()

int	GetMemoryUsage ()
	Return the amount of memory used by PEAStar. More...

bool	GetClosedListGCost (const state &val, double &gCost) const
	Get state from the closed list. More...

unsigned int	GetNumOpenItems ()

const EPEAOpenClosedData< state > &	GetOpenItem (unsigned int which)

const int	GetNumItems ()

const EPEAOpenClosedData< state > &	GetItem (unsigned int which)

bool	HaveExpandedState (const state &val)

void	SetReopenNodes (bool re)

bool	GetReopenNodes ()

void	SetHeuristic (Heuristic< state > *h)

uint64_t	GetNodesExpanded () const

uint64_t	GetNodesTouched () const

void	LogFinalStats (StatCollection *)

void	SetStopAfterGoal (bool val)

bool	GetStopAfterGoal ()

void	OpenGLDraw () const
	Draw the open/closed list. More...

void	SetWeight (double w)

Public Member Functions inherited from GenericSearchAlgorithm< state, action, environment >
	GenericSearchAlgorithm ()

virtual	~GenericSearchAlgorithm ()

virtual void	OpenGLDraw (const environment *env) const

Public Attributes
AStarOpenClosed< state, EPEAStarCompare< state >, EPEAOpenClosedData< xyLoc > >	openClosedList

state	goal

state	start

Private Attributes
uint64_t	nodesTouched

uint64_t	nodesExpanded

environment *	env

bool	stopAfterGoal

double	weight

bool	reopenNodes

uint64_t	uniqueNodesExpanded

Heuristic< state > *	theHeuristic

Detailed Description

template<class state, class action, class environment>
class EPEAStar< state, action, environment >

A templated version of A*, based on HOG genericAStar.

Definition at line 82 of file EPEAStar.h.

Constructor & Destructor Documentation

◆ EPEAStar()

template<class state , class action , class environment >

EPEAStar< state, action, environment >::EPEAStar ( )

inline

Definition at line 84 of file EPEAStar.h.

References EPEAStar< state, action, environment >::env, EPEAStar< state, action, environment >::reopenNodes, EPEAStar< state, action, environment >::ResetNodeCount(), EPEAStar< state, action, environment >::stopAfterGoal, and EPEAStar< state, action, environment >::weight.

◆ ~EPEAStar()

template<class state , class action , class environment >

virtual EPEAStar< state, action, environment >::~EPEAStar ( )

inlinevirtual

Definition at line 85 of file EPEAStar.h.

Member Function Documentation

◆ AddAdditionalStartState() [1/2]

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::AddAdditionalStartState ( state & newState )

Add additional start state to the search.

This should only be called after Initialize Search and before DoSingleSearchStep.

Author: Nathan Sturtevant

Date: 01/06/08

Definition at line 235 of file EPEAStar.h.

◆ AddAdditionalStartState() [2/2]

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::AddAdditionalStartState	(	state &	newState,
		double	cost
	)

Add additional start state to the search.

This should only be called after Initialize Search

Author: Nathan Sturtevant

Date: 09/25/10

Definition at line 246 of file EPEAStar.h.

◆ CheckNextNode()

template<class state , class action , class environment >

state EPEAStar< state, action, environment >::CheckNextNode

Returns the next state on the open list (but doesn't pop it off the queue).

Author: Nathan Sturtevant

Date: 03/22/06

Returns: The first state in the open list.

Definition at line 349 of file EPEAStar.h.

◆ DoSingleSearchStep()

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::DoSingleSearchStep ( std::vector< state > & thePath )

virtual

Expand a single node.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

thePath will contain an optimal path from start to goal if the function returns TRUE

Returns: TRUE if there is no path or if we have found the goal, FALSE otherwise

Reimplemented from GenericSearchAlgorithm< state, action, environment >.

Definition at line 262 of file EPEAStar.h.

References fless(), kClosedList, kNotFound, and kOpenList.

◆ ExtractPathToStart()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::ExtractPathToStart	(	state &	node,
		std::vector< state > &	thePath
	)

inline

Definition at line 100 of file EPEAStar.h.

References EPEAStar< state, action, environment >::env, EPEAStar< state, action, environment >::ExtractPathToStartFromID(), AStarOpenClosed< state, CmpKey, dataStructure >::Lookup(), and EPEAStar< state, action, environment >::openClosedList.

◆ ExtractPathToStartFromID()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::ExtractPathToStartFromID	(	uint64_t	node,
		std::vector< state > &	thePath
	)

Get the path from a goal state to the start state.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

goalNode	the goal state
thePath	will contain the path from goalNode to the start state

Definition at line 367 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::ExtractPathToStart().

◆ GetClosedListGCost()

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::GetClosedListGCost	(	const state &	val,
		double &	gCost
	)		const

Get state from the closed list.

Author: Nathan Sturtevant

Date: 10/09/07

Parameters

val	The state to lookup in the closed list @gCost The g-cost of the node in the closed list

Returns: success Whether we found the value or not more states

Definition at line 414 of file EPEAStar.h.

References kClosedList.

◆ GetItem()

template<class state , class action , class environment >

const EPEAOpenClosedData<state>& EPEAStar< state, action, environment >::GetItem ( unsigned int which )

inline

Definition at line 118 of file EPEAStar.h.

References AStarOpenClosed< state, CmpKey, dataStructure >::Lookat(), and EPEAStar< state, action, environment >::openClosedList.

◆ GetMemoryUsage()

template<class state , class action , class environment >

int EPEAStar< state, action, environment >::GetMemoryUsage

Return the amount of memory used by PEAStar.

Author: Nathan Sturtevant

Date: 03/22/06

Returns: The combined number of elements in the closed list and open queue

Definition at line 398 of file EPEAStar.h.

◆ GetName()

template<class state , class action , class environment >

const char * EPEAStar< state, action, environment >::GetName

virtual

Return the name of the algorithm.

Author: Nathan Sturtevant

Date: 03/22/06

Returns: The name of the algorithm

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 161 of file EPEAStar.h.

◆ GetNodesExpanded()

template<class state , class action , class environment >

uint64_t EPEAStar< state, action, environment >::GetNodesExpanded ( ) const

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 127 of file EPEAStar.h.

References EPEAStar< state, action, environment >::nodesExpanded.

◆ GetNodesTouched()

template<class state , class action , class environment >

uint64_t EPEAStar< state, action, environment >::GetNodesTouched ( ) const

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 128 of file EPEAStar.h.

References EPEAStar< state, action, environment >::nodesTouched.

◆ GetNumItems()

template<class state , class action , class environment >

const int EPEAStar< state, action, environment >::GetNumItems ( )

inline

Definition at line 117 of file EPEAStar.h.

References EPEAStar< state, action, environment >::openClosedList, and AStarOpenClosed< state, CmpKey, dataStructure >::size().

◆ GetNumOpenItems()

template<class state , class action , class environment >

unsigned int EPEAStar< state, action, environment >::GetNumOpenItems ( )

inline

Definition at line 115 of file EPEAStar.h.

References EPEAStar< state, action, environment >::openClosedList, and AStarOpenClosed< state, CmpKey, dataStructure >::OpenSize().

◆ GetOpenItem()

template<class state , class action , class environment >

const EPEAOpenClosedData<state>& EPEAStar< state, action, environment >::GetOpenItem ( unsigned int which )

inline

Definition at line 116 of file EPEAStar.h.

References AStarOpenClosed< state, CmpKey, dataStructure >::GetOpenItem(), AStarOpenClosed< state, CmpKey, dataStructure >::Lookat(), and EPEAStar< state, action, environment >::openClosedList.

◆ GetPath() [1/2]

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::GetPath	(	environment *	,
		const state &	,
		const state &	,
		std::vector< action > &
	)

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 88 of file EPEAStar.h.

◆ GetPath() [2/2]

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::GetPath	(	environment *	_env,
		const state &	from,
		const state &	to,
		std::vector< state > &	thePath
	)

virtual

Perform an A* search between two states.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

_env	The search environment
from	The start state
to	The goal state
thePath	A vector of states which will contain an optimal path between from and to when the function returns, if one exists.

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 180 of file EPEAStar.h.

◆ GetReopenNodes()

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::GetReopenNodes ( )

inline

Definition at line 123 of file EPEAStar.h.

References EPEAStar< state, action, environment >::reopenNodes.

◆ GetStopAfterGoal()

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::GetStopAfterGoal ( )

inline

Definition at line 133 of file EPEAStar.h.

References EPEAStar< state, action, environment >::stopAfterGoal.

◆ GetUniqueNodesExpanded()

template<class state , class action , class environment >

uint64_t EPEAStar< state, action, environment >::GetUniqueNodesExpanded ( )

inline

Definition at line 106 of file EPEAStar.h.

References EPEAStar< state, action, environment >::uniqueNodesExpanded.

◆ HaveExpandedState()

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::HaveExpandedState ( const state & val )

inline

Definition at line 119 of file EPEAStar.h.

References EPEAStar< state, action, environment >::env, kNotFound, AStarOpenClosed< state, CmpKey, dataStructure >::Lookup(), and EPEAStar< state, action, environment >::openClosedList.

◆ InitializeSearch()

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::InitializeSearch	(	environment *	_env,
		const state &	from,
		const state &	to,
		std::vector< state > &	thePath
	)

virtual

Initialize the A* search.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

_env	The search environment
from	The start state
to	The goal state

Returns: TRUE if initialization was successful, FALSE otherwise

Reimplemented from GenericSearchAlgorithm< state, action, environment >.

Definition at line 201 of file EPEAStar.h.

◆ LogFinalStats()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::LogFinalStats ( StatCollection * )

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 130 of file EPEAStar.h.

◆ OpenGLDraw()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::OpenGLDraw

virtual

Draw the open/closed list.

Author: Nathan Sturtevant

Date: 03/12/09

Reimplemented from GenericSearchAlgorithm< state, action, environment >.

Definition at line 433 of file EPEAStar.h.

References EPEAOpenClosedData< state >::data, kClosedList, kOpenList, EPEAOpenClosedData< state >::reopened, and EPEAOpenClosedData< state >::where.

◆ PrintStats()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::PrintStats

A function that prints the number of states in the closed list and open queue.

Author: Nathan Sturtevant

Date: 03/22/06

Definition at line 384 of file EPEAStar.h.

◆ ResetNodeCount()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::ResetNodeCount ( )

inline

Definition at line 107 of file EPEAStar.h.

References EPEAStar< state, action, environment >::nodesExpanded, EPEAStar< state, action, environment >::nodesTouched, and EPEAStar< state, action, environment >::uniqueNodesExpanded.

Referenced by EPEAStar< state, action, environment >::EPEAStar().

◆ SetHeuristic()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::SetHeuristic ( Heuristic< state > * h )

inline

Definition at line 125 of file EPEAStar.h.

References EPEAStar< state, action, environment >::theHeuristic.

◆ SetReopenNodes()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::SetReopenNodes ( bool re )

inline

Definition at line 122 of file EPEAStar.h.

References EPEAStar< state, action, environment >::reopenNodes.

◆ SetStopAfterGoal()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::SetStopAfterGoal ( bool val )

inline

Definition at line 132 of file EPEAStar.h.

References EPEAStar< state, action, environment >::stopAfterGoal.

◆ SetWeight()

template<class state , class action , class environment >

void EPEAStar< state, action, environment >::SetWeight ( double w )

inline

Definition at line 137 of file EPEAStar.h.

References EPEAStar< state, action, environment >::weight.

Member Data Documentation

◆ env

template<class state , class action , class environment >

environment* EPEAStar< state, action, environment >::env

private

Definition at line 140 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::EPEAStar(), EPEAStar< state, action, environment >::ExtractPathToStart(), and EPEAStar< state, action, environment >::HaveExpandedState().

◆ goal

template<class state , class action , class environment >

state EPEAStar< state, action, environment >::goal

Definition at line 92 of file EPEAStar.h.

◆ nodesExpanded

template<class state , class action , class environment >

uint64_t EPEAStar< state, action, environment >::nodesExpanded

private

Definition at line 139 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::GetNodesExpanded(), and EPEAStar< state, action, environment >::ResetNodeCount().

◆ nodesTouched

template<class state , class action , class environment >

uint64_t EPEAStar< state, action, environment >::nodesTouched

private

Definition at line 139 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::GetNodesTouched(), and EPEAStar< state, action, environment >::ResetNodeCount().

◆ openClosedList

template<class state , class action , class environment >

AStarOpenClosed<state, EPEAStarCompare<state>, EPEAOpenClosedData<xyLoc> > EPEAStar< state, action, environment >::openClosedList

Definition at line 88 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::ExtractPathToStart(), EPEAStar< state, action, environment >::GetItem(), EPEAStar< state, action, environment >::GetNumItems(), EPEAStar< state, action, environment >::GetNumOpenItems(), EPEAStar< state, action, environment >::GetOpenItem(), and EPEAStar< state, action, environment >::HaveExpandedState().

◆ reopenNodes

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::reopenNodes

private

Definition at line 145 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::EPEAStar(), EPEAStar< state, action, environment >::GetReopenNodes(), and EPEAStar< state, action, environment >::SetReopenNodes().

◆ start

template<class state , class action , class environment >

state EPEAStar< state, action, environment >::start

Definition at line 92 of file EPEAStar.h.

◆ stopAfterGoal

template<class state , class action , class environment >

bool EPEAStar< state, action, environment >::stopAfterGoal

private

Definition at line 141 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::EPEAStar(), EPEAStar< state, action, environment >::GetStopAfterGoal(), and EPEAStar< state, action, environment >::SetStopAfterGoal().

◆ theHeuristic

template<class state , class action , class environment >

Heuristic<state>* EPEAStar< state, action, environment >::theHeuristic

private

Definition at line 147 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::SetHeuristic().

◆ uniqueNodesExpanded

template<class state , class action , class environment >

uint64_t EPEAStar< state, action, environment >::uniqueNodesExpanded

private

Definition at line 146 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::GetUniqueNodesExpanded(), and EPEAStar< state, action, environment >::ResetNodeCount().

◆ weight

template<class state , class action , class environment >

double EPEAStar< state, action, environment >::weight

private

Definition at line 143 of file EPEAStar.h.

Referenced by EPEAStar< state, action, environment >::EPEAStar(), and EPEAStar< state, action, environment >::SetWeight().

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

/home/sturtevant/nightly/hog2/generic/EPEAStar.h

Public Member Functions

Public Attributes

Private Attributes

Detailed Description

template<class state, class action, class environment> class EPEAStar< state, action, environment >

Constructor & Destructor Documentation

◆ EPEAStar()

◆ ~EPEAStar()

Member Function Documentation

◆ AddAdditionalStartState() [1/2]

◆ AddAdditionalStartState() [2/2]

◆ CheckNextNode()

◆ DoSingleSearchStep()

◆ ExtractPathToStart()

◆ ExtractPathToStartFromID()

◆ GetClosedListGCost()

◆ GetItem()

◆ GetMemoryUsage()

◆ GetName()

◆ GetNodesExpanded()

◆ GetNodesTouched()

◆ GetNumItems()

◆ GetNumOpenItems()

◆ GetOpenItem()

◆ GetPath() [1/2]

◆ GetPath() [2/2]

◆ GetReopenNodes()

◆ GetStopAfterGoal()

◆ GetUniqueNodesExpanded()

◆ HaveExpandedState()

◆ InitializeSearch()

◆ LogFinalStats()

◆ OpenGLDraw()

◆ PrintStats()

◆ ResetNodeCount()

◆ SetHeuristic()

◆ SetReopenNodes()

◆ SetStopAfterGoal()

◆ SetWeight()

Member Data Documentation

◆ env

◆ goal

◆ nodesExpanded

◆ nodesTouched

◆ openClosedList

◆ reopenNodes

◆ start

◆ stopAfterGoal

◆ theHeuristic

◆ uniqueNodesExpanded

◆ weight

template<class state, class action, class environment>
class EPEAStar< state, action, environment >