dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer > Class Template Reference

A generic implementation of the standard A* algorithm. More...

#include <astar.h>

List of all members.

Public Types
enum	AStarResult { NO_PATH = 0, PATH_FOUND, PARTIAL_PATH }
typedef _NodeType	node_type
typedef _NodeType::cost_type	cost_type
typedef _NodeType::data_type	data_type
typedef std::vector< node_type * >	AStarContainer
typedef AStarContainer::iterator	AStarIterator
typedef _CostFunc	cost_function
typedef _Container	container_type
typedef AStarConfig< data_type, cost_type, container_type >	config_type
typedef AStar< node_type, cost_function, container_type, _Timer >	MyType
Public Member Functions
	AStar ()
	Default constructor creates a default config file with no constraints, and no path to goto.
	AStar (const config_type &pConfig)
	Takes a config as an arg and copies it, use this constructor to setup constraints or configured with two path points to path between.
virtual	~AStar ()
void	Reset (const config_type &pConfig)
	Resets the internal memory and copies the config class for use on the next call to FindPath().
void	Reset (data_type pFrom, data_type pTo)
	Resets the internal memory and keeps the same config params.
void	Reset (const std::vector< data_type > &pFrom, const std::vector< data_type > &pTo)
AStarResult	FindPath ()
	Runs the AStar algorithm, using the either the current config or the the default config settings if none have been set can check for return of false if no path is found.
container_type &	GetPath ()
	Call this after calling FindPath() to get.
const config_type &	GetConfig () const
	Use this to get the config data to change constraints or get the statistics from the last run of GetPath(), also holds a container of the last found path.
config_type &	GetConfig ()
cost_function &	GetCostFunction ()
const cost_function &	GetCostFunction () const
Protected Member Functions
	AStar (const AStar &)
AStar &	operator= (const AStar &)
void	FreeMem ()
void	AddNodeLink (node_type *pParent, data_type pData)
	Internal helper functions, pulled out of main loop to be optimized at a later date.
std::vector< _NodeType * > ::iterator	Contains (AStarContainer &pCont, data_type pNode)
void	Remove (AStarContainer &pCont, typename AStarContainer::iterator iterToErase)
node_type *	FindLowestCost (AStarContainer &pCont)
void	Insert (AStarContainer &pCont, node_type *pNode)
Protected Attributes
config_type	mConfig
AStarContainer	mOpen
AStarContainer	mClosed
cost_function	mCostFunc
_Timer	mTimer

---

Detailed Description

template<class _NodeType, class _CostFunc, class _Container, class _Timer>
class dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >

A generic implementation of the standard A* algorithm.

This class can be used as a generic graph searching tool, to do this you will need several template parameters an example can be found in AStarWaypointUtils.h, but I will break down the basics below.

NodeType: This class is used as the nodes in the graph we are searching, it should be derived from AStarNode and most importantly implement begin() and end() which will support our graph searching mechanism.

CostFunc: This class is used to calculate the cost between two nodes it should be derived from AStarCostFunc and support the operator() which takes two DataTypes (being the DataType encapsulated by our Node.

Container: This can be any standard container templated to take type DataType that supports push_front. A todo is to change it to take push_back.

Timer: This class is used for statistics info and must support Update() and GetDT() GetDT() should give the elapsed time between two Updates(). Be aware the the granularity of time is only relevant to the user and should match the AStarConfig's MaxTime.

To find a path between two points you can call Reset() with the two points and then FindPath(). Alternatively, you can set a config type which contains the path points and holds statistical info as well as pathing constraints. If you do not pass it a config, a default one will be used. To edit the default config just call GetConfig() which passes a config by reference. If you want to set new path points don't call Reset() on the config, call Reset() on AStar, cause this will clear the internal bookeeping members on AStar. The main means for editing the config is to set constraints, the const GetConfig() can be used for getting the statistics from the last path creation. The constraints can be used for finding partial paths. When a constraint is set on a config the next call to FindPath() will use the constraints and return PARTIAL_PATH if the path could not be completed, returning the best path so far. The next call to FindPath() will find the next segment from the last point in the partial path to the goal and continue to work within the constraints. When PATH_FOUND is returned from FindPath() a path to the goal has been reached else NO_PATH will indicate there is no possible path between the two points. To obtain the path or partial path, call GetPath() or copy it off of the config from GetConfig.

Thanks to Amit and his great webpage on AStar Algorithms http://theory.stanford.edu/~amitp/GameProgramming/

Bradley Anderegg

---

Member Typedef Documentation

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef _NodeType dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::node_type

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef _NodeType::cost_type dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::cost_type

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef _NodeType::data_type dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::data_type

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef std::vector<node_type*> dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::AStarContainer

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef AStarContainer::iterator dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::AStarIterator

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef _CostFunc dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::cost_function

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef _Container dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::container_type

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef AStarConfig<data_type, cost_type, container_type> dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::config_type

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

typedef AStar<node_type, cost_function, container_type, _Timer> dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::MyType

---

Member Enumeration Documentation

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

enum dtAI::AStar::AStarResult

Enumerator:

NO_PATH
PATH_FOUND
PARTIAL_PATH

---

Constructor & Destructor Documentation

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::AStar

(

)

[inline]

Default constructor creates a default config file with no constraints, and no path to goto.

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::AStar

(

const config_type &

pConfig

)

[inline]

Takes a config as an arg and copies it, use this constructor to setup constraints or configured with two path points to path between.

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::~AStar

(

)

[inline, virtual]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::AStar

(

const AStar< _NodeType, _CostFunc, _Container, _Timer > &

)

[protected]

---

Member Function Documentation

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::Reset

(

const config_type &

pConfig

)

[inline]

Resets the internal memory and copies the config class for use on the next call to FindPath().

Parameters:

takes

an AStarConfig class

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::Reset	(	data_type	pFrom,
		data_type	pTo
	)			[inline]

Resets the internal memory and keeps the same config params.

Parameters:

	the	point to find a path from
	the	point to find a path to

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::Reset	(	const std::vector< data_type > &	pFrom,
		const std::vector< data_type > &	pTo
	)			[inline]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

AStar< _NodeType, _CostFunc, _Container, _Timer >::AStarResult dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::FindPath

(

)

[inline]

Runs the AStar algorithm, using the either the current config or the the default config settings if none have been set can check for return of false if no path is found.

Returns:

the result of this call to find path, NO_PATH, PATH_FOUND, or PARTIAL_PATH,

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

container_type& dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::GetPath

(

)

[inline]

Call this after calling FindPath() to get.

Returns:

the result of the last call to FindPath()

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

const config_type& dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::GetConfig

(

)

const [inline]

Use this to get the config data to change constraints or get the statistics from the last run of GetPath(), also holds a container of the last found path.

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

config_type& dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::GetConfig

(

)

[inline]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

cost_function& dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::GetCostFunction

(

)

[inline]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

const cost_function& dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::GetCostFunction

(

)

const [inline]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

AStar& dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::operator=

(

const AStar< _NodeType, _CostFunc, _Container, _Timer > &

)

[protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::FreeMem

(

)

[inline, protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::AddNodeLink	(	node_type *	pParent,
		data_type	pData
	)			[inline, protected]

Internal helper functions, pulled out of main loop to be optimized at a later date.

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

std::vector< _NodeType * >::iterator dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::Contains	(	AStarContainer &	pCont,
		data_type	pNode
	)			[inline, protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::Remove	(	AStarContainer &	pCont,
		typename AStarContainer::iterator	iterToErase
	)			[inline, protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

_NodeType * dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::FindLowestCost

(

AStarContainer &

pCont

)

[inline, protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

void dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::Insert	(	AStarContainer &	pCont,
		node_type *	pNode
	)			[inline, protected]

---

Member Data Documentation

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

config_type dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::mConfig [protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

AStarContainer dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::mOpen [protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

AStarContainer dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::mClosed [protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

cost_function dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::mCostFunc [protected]

template<class _NodeType, class _CostFunc, class _Container, class _Timer>

_Timer dtAI::AStar< _NodeType, _CostFunc, _Container, _Timer >::mTimer [protected]

---