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

#include <OldTemplateAStar.h>

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

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

Public Types
typedef OpenClosedList< OldOldTemplateAStarUtil::SearchNode< state >, OldOldTemplateAStarUtil::SearchNodeHash< state >, OldOldTemplateAStarUtil::SearchNodeEqual< state >, OldOldTemplateAStarUtil::SearchNodeCompare< state > >	PQueue

typedef std::unordered_map< uint64_t, OldOldTemplateAStarUtil::SearchNode< state >, Hash64 >	NodeLookupTable

typedef NodeLookupTable::const_iterator	closedList_iterator

Public Member Functions
	OldTemplateAStar ()

virtual	~OldTemplateAStar ()

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

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

bool	InitializeSearch (environment *env, state &from, 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...

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

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

void	DoAbstractSearch ()

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

void	ResetNodeCount ()

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

void	GetClosedListIter (closedList_iterator)
	Get an iterator for the closed list. More...

bool	ClosedListIterNext (closedList_iterator &it, state &next) const
	Get the next state in the closed list. More...

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

void	SetUseBPMX (bool use)

bool	GetUsingBPMX ()

uint64_t	GetNodesExpanded ()

uint64_t	GetNodesTouched ()

void	LogFinalStats (StatCollection *)

void	SetRadius (double rad)

double	GetRadius ()

void	SetRadiusEnvironment (environment *e)

void	SetStopAfterGoal (bool val)

bool	GetStopAfterGoal ()

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

void	SetWeight (double w)
	Use weighted A* and set the weight. More...

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

virtual	~GenericSearchAlgorithm ()

virtual void	GetPath (environment *env, const state &from, const state &to, std::vector< state > &path)=0

virtual void	GetPath (environment *env, const state &from, const state &to, std::vector< action > &path)=0

virtual bool	InitializeSearch (environment *env, const state &from, const state &to, std::vector< state > &thePath)

virtual uint64_t	GetNodesExpanded () const =0

virtual uint64_t	GetNodesTouched () const =0

virtual void	OpenGLDraw (const environment *env) const

Public Attributes
PQueue	openQueue

NodeLookupTable	closedList

state	goal

state	start

Private Member Functions
bool	GetNextNode (state &next)
	Removes the top node from the open list More...

void	UpdateClosedNode (environment *env, state &currOpenNode, state &neighbor)
	Check and update the weight of a closed node. More...

void	UpdateWeight (environment *env, state &currOpenNode, state &neighbor)
	Update the weight of a node. More...

void	AddToOpenList (environment *env, state &currOpenNode, state &neighbor)
	Add a node to the open list. More...

Private Attributes
uint64_t	nodesTouched

uint64_t	nodesExpanded

std::vector< state >	neighbors

environment *	env

bool	stopAfterGoal

double	radius

double	weight

bool	useOccupancyInfo

bool	useRadius

bool	firstRound

bool	useBPMX

environment *	radEnv

Detailed Description

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

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

Definition at line 106 of file OldTemplateAStar.h.

Member Typedef Documentation

◆ closedList_iterator

template<class state , class action , class environment >

typedef NodeLookupTable::const_iterator OldTemplateAStar< state, action, environment >::closedList_iterator

Definition at line 123 of file OldTemplateAStar.h.

◆ NodeLookupTable

template<class state , class action , class environment >

typedef std::unordered_map<uint64_t, OldOldTemplateAStarUtil::SearchNode<state>, Hash64 > OldTemplateAStar< state, action, environment >::NodeLookupTable

Definition at line 117 of file OldTemplateAStar.h.

◆ PQueue

template<class state , class action , class environment >

typedef OpenClosedList<OldOldTemplateAStarUtil::SearchNode<state>, OldOldTemplateAStarUtil::SearchNodeHash<state>, OldOldTemplateAStarUtil::SearchNodeEqual<state>, OldOldTemplateAStarUtil::SearchNodeCompare<state> > OldTemplateAStar< state, action, environment >::PQueue

Definition at line 112 of file OldTemplateAStar.h.

Constructor & Destructor Documentation

◆ OldTemplateAStar()

template<class state , class action , class environment >

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

inline

Definition at line 108 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::env, OldTemplateAStar< state, action, environment >::radEnv, OldTemplateAStar< state, action, environment >::radius, OldTemplateAStar< state, action, environment >::stopAfterGoal, OldTemplateAStar< state, action, environment >::useBPMX, OldTemplateAStar< state, action, environment >::useOccupancyInfo, OldTemplateAStar< state, action, environment >::useRadius, and OldTemplateAStar< state, action, environment >::weight.

◆ ~OldTemplateAStar()

template<class state , class action , class environment >

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

inlinevirtual

Definition at line 109 of file OldTemplateAStar.h.

Member Function Documentation

◆ AddAdditionalStartState()

template<class state , class action , class environment >

void OldTemplateAStar< 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 280 of file OldTemplateAStar.h.

◆ AddToOpenList()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::AddToOpenList	(	environment *	e,
		state &	currOpenNode,
		state &	neighbor
	)

private

Add a node to the open list.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

currOpenNode	the state that's currently being expanded
neighbor	the state to be added to the open list

Definition at line 496 of file OldTemplateAStar.h.

References fgreater().

◆ CheckNextNode()

template<class state , class action , class environment >

state OldTemplateAStar< 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 390 of file OldTemplateAStar.h.

◆ ClosedListIterNext()

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::ClosedListIterNext	(	closedList_iterator &	it,
		state &	next
	)		const

Get the next state in the closed list.

Author: Nathan Sturtevant

Date: 06/13/07

Parameters

it	A closedList_iterator pointing at the current state in the closed list

Returns: The next state in the closed list. Returns UINT_MAX if there's no more states

Definition at line 607 of file OldTemplateAStar.h.

◆ DoAbstractSearch()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::DoAbstractSearch ( )

inline

Definition at line 131 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::useOccupancyInfo, and OldTemplateAStar< state, action, environment >::useRadius.

◆ DoSingleSearchStep()

template<class state , class action , class environment >

bool OldTemplateAStar< 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 297 of file OldTemplateAStar.h.

References OldOldTemplateAStarUtil::SearchNode< state >::fCost, fgreater(), and OldOldTemplateAStarUtil::SearchNode< state >::gCost.

◆ ExtractPathToStart()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::ExtractPathToStart	(	state &	goalNode,
		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 530 of file OldTemplateAStar.h.

References OldOldTemplateAStarUtil::SearchNode< state >::currNode, and OldOldTemplateAStarUtil::SearchNode< state >::prevNode.

◆ GetClosedListGCost()

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::GetClosedListGCost	(	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 627 of file OldTemplateAStar.h.

◆ GetClosedListIter()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::GetClosedListIter ( closedList_iterator )

Get an iterator for the closed list.

Author: Nathan Sturtevant

Date: 06/13/07

Returns: An iterator pointing to the first node in the closed list

Definition at line 591 of file OldTemplateAStar.h.

◆ GetMemoryUsage()

template<class state , class action , class environment >

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

Return the amount of memory used by OldTemplateAStar.

Author: Nathan Sturtevant

Date: 03/22/06

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

Definition at line 577 of file OldTemplateAStar.h.

◆ GetName()

template<class state , class action , class environment >

const char * OldTemplateAStar< 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 205 of file OldTemplateAStar.h.

◆ GetNextNode()

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::GetNextNode ( state & next )

private

Removes the top node from the open list

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

state will contain the next state in the open list

Returns: TRUE if next contains a valid state, FALSE if there is no more states in the open queue

Definition at line 405 of file OldTemplateAStar.h.

References OldOldTemplateAStarUtil::SearchNode< state >::currNode.

◆ GetNodesExpanded()

template<class state , class action , class environment >

uint64_t OldTemplateAStar< state, action, environment >::GetNodesExpanded ( )

inline

Definition at line 149 of file OldTemplateAStar.h.

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

◆ GetNodesTouched()

template<class state , class action , class environment >

uint64_t OldTemplateAStar< state, action, environment >::GetNodesTouched ( )

inline

Definition at line 150 of file OldTemplateAStar.h.

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

◆ GetPath() [1/2]

template<class state , class action , class environment >

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

inline

Definition at line 112 of file OldTemplateAStar.h.

◆ GetPath() [2/2]

template<class state , class action , class environment >

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

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.

Definition at line 224 of file OldTemplateAStar.h.

◆ GetRadius()

template<class state , class action , class environment >

double OldTemplateAStar< state, action, environment >::GetRadius ( )

inline

Definition at line 155 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::radius.

◆ GetStopAfterGoal()

template<class state , class action , class environment >

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

inline

Definition at line 160 of file OldTemplateAStar.h.

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

◆ GetUsingBPMX()

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::GetUsingBPMX ( )

inline

Definition at line 146 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::useBPMX.

◆ InitializeSearch()

template<class state , class action , class environment >

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

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

Definition at line 245 of file OldTemplateAStar.h.

◆ LogFinalStats()

template<class state , class action , class environment >

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

inlinevirtual

Implements GenericSearchAlgorithm< state, action, environment >.

Definition at line 152 of file OldTemplateAStar.h.

◆ OpenGLDraw()

template<class state , class action , class environment >

void OldTemplateAStar< 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 644 of file OldTemplateAStar.h.

◆ PrintStats()

template<class state , class action , class environment >

void OldTemplateAStar< 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 563 of file OldTemplateAStar.h.

◆ ResetNodeCount()

template<class state , class action , class environment >

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

inline

Definition at line 137 of file OldTemplateAStar.h.

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

◆ SetRadius()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::SetRadius ( double rad )

inline

Definition at line 154 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::radius.

◆ SetRadiusEnvironment()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::SetRadiusEnvironment ( environment * e )

inline

Definition at line 157 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::radEnv.

◆ SetStopAfterGoal()

template<class state , class action , class environment >

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

inline

Definition at line 159 of file OldTemplateAStar.h.

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

◆ SetUseBPMX()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::SetUseBPMX ( bool use )

inline

Definition at line 145 of file OldTemplateAStar.h.

References OldTemplateAStar< state, action, environment >::useBPMX.

◆ SetWeight()

template<class state , class action , class environment >

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

inline

Use weighted A* and set the weight.

Use f = g + weight * h during search

Author: Renee Jansen

Date: 10/23/2007

Definition at line 171 of file OldTemplateAStar.h.

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

◆ UpdateClosedNode()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::UpdateClosedNode	(	environment *	e,
		state &	currOpenNode,
		state &	neighbor
	)

private

Check and update the weight of a closed node.

Author: Nathan Sturtevant

Date: 11/10/08

Parameters

currOpenNode	The node that's currently being expanded
neighbor	The node whose weight will be updated

Definition at line 433 of file OldTemplateAStar.h.

References OldOldTemplateAStarUtil::SearchNode< state >::currNode, OldOldTemplateAStarUtil::SearchNode< state >::fCost, fgreater(), OldOldTemplateAStarUtil::SearchNode< state >::gCost, and OldOldTemplateAStarUtil::SearchNode< state >::prevNode.

◆ UpdateWeight()

template<class state , class action , class environment >

void OldTemplateAStar< state, action, environment >::UpdateWeight	(	environment *	e,
		state &	currOpenNode,
		state &	neighbor
	)

private

Update the weight of a node.

Author: Nathan Sturtevant

Date: 03/22/06

Parameters

currOpenNode	The node that's currently being expanded
neighbor	The node whose weight will be updated

Definition at line 466 of file OldTemplateAStar.h.

References OldOldTemplateAStarUtil::SearchNode< state >::currNode, OldOldTemplateAStarUtil::SearchNode< state >::fCost, fgreater(), OldOldTemplateAStarUtil::SearchNode< state >::gCost, and OldOldTemplateAStarUtil::SearchNode< state >::prevNode.

Member Data Documentation

◆ closedList

template<class state , class action , class environment >

NodeLookupTable OldTemplateAStar< state, action, environment >::closedList

Definition at line 120 of file OldTemplateAStar.h.

◆ env

template<class state , class action , class environment >

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

private

Definition at line 181 of file OldTemplateAStar.h.

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

◆ firstRound

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::firstRound

private

Definition at line 189 of file OldTemplateAStar.h.

◆ goal

template<class state , class action , class environment >

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

Definition at line 121 of file OldTemplateAStar.h.

◆ neighbors

template<class state , class action , class environment >

std::vector<state> OldTemplateAStar< state, action, environment >::neighbors

private

Definition at line 180 of file OldTemplateAStar.h.

◆ nodesExpanded

template<class state , class action , class environment >

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

private

Definition at line 173 of file OldTemplateAStar.h.

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

◆ nodesTouched

template<class state , class action , class environment >

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

private

Definition at line 173 of file OldTemplateAStar.h.

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

◆ openQueue

template<class state , class action , class environment >

PQueue OldTemplateAStar< state, action, environment >::openQueue

Definition at line 119 of file OldTemplateAStar.h.

◆ radEnv

template<class state , class action , class environment >

environment* OldTemplateAStar< state, action, environment >::radEnv

private

Definition at line 191 of file OldTemplateAStar.h.

Referenced by OldTemplateAStar< state, action, environment >::OldTemplateAStar(), and OldTemplateAStar< state, action, environment >::SetRadiusEnvironment().

◆ radius

template<class state , class action , class environment >

double OldTemplateAStar< state, action, environment >::radius

private

Definition at line 184 of file OldTemplateAStar.h.

Referenced by OldTemplateAStar< state, action, environment >::GetRadius(), OldTemplateAStar< state, action, environment >::OldTemplateAStar(), and OldTemplateAStar< state, action, environment >::SetRadius().

◆ start

template<class state , class action , class environment >

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

Definition at line 121 of file OldTemplateAStar.h.

◆ stopAfterGoal

template<class state , class action , class environment >

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

private

Definition at line 182 of file OldTemplateAStar.h.

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

◆ useBPMX

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::useBPMX

private

Definition at line 190 of file OldTemplateAStar.h.

Referenced by OldTemplateAStar< state, action, environment >::GetUsingBPMX(), OldTemplateAStar< state, action, environment >::OldTemplateAStar(), and OldTemplateAStar< state, action, environment >::SetUseBPMX().

◆ useOccupancyInfo

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::useOccupancyInfo

private

Definition at line 187 of file OldTemplateAStar.h.

Referenced by OldTemplateAStar< state, action, environment >::DoAbstractSearch(), and OldTemplateAStar< state, action, environment >::OldTemplateAStar().

◆ useRadius

template<class state , class action , class environment >

bool OldTemplateAStar< state, action, environment >::useRadius

private

Definition at line 188 of file OldTemplateAStar.h.

Referenced by OldTemplateAStar< state, action, environment >::DoAbstractSearch(), and OldTemplateAStar< state, action, environment >::OldTemplateAStar().

◆ weight

template<class state , class action , class environment >

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

private

Definition at line 185 of file OldTemplateAStar.h.

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

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

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

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

◆ closedList_iterator

◆ NodeLookupTable

◆ PQueue

Constructor & Destructor Documentation

◆ OldTemplateAStar()

◆ ~OldTemplateAStar()

Member Function Documentation

◆ AddAdditionalStartState()

◆ AddToOpenList()

◆ CheckNextNode()

◆ ClosedListIterNext()

◆ DoAbstractSearch()

◆ DoSingleSearchStep()

◆ ExtractPathToStart()

◆ GetClosedListGCost()

◆ GetClosedListIter()

◆ GetMemoryUsage()

◆ GetName()

◆ GetNextNode()

◆ GetNodesExpanded()

◆ GetNodesTouched()

◆ GetPath() [1/2]

◆ GetPath() [2/2]

◆ GetRadius()

◆ GetStopAfterGoal()

◆ GetUsingBPMX()

◆ InitializeSearch()

◆ LogFinalStats()

◆ OpenGLDraw()

◆ PrintStats()

◆ ResetNodeCount()

◆ SetRadius()

◆ SetRadiusEnvironment()

◆ SetStopAfterGoal()

◆ SetUseBPMX()

◆ SetWeight()

◆ UpdateClosedNode()

◆ UpdateWeight()

Member Data Documentation

◆ closedList

◆ env

◆ firstRound

◆ goal

◆ neighbors

◆ nodesExpanded

◆ nodesTouched

◆ openQueue

◆ radEnv

◆ radius

◆ start

◆ stopAfterGoal

◆ useBPMX

◆ useOccupancyInfo

◆ useRadius

◆ weight

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