Main Class Hierarchy Classes Compound List Files Compound Members File Members Pages

PathFind::AStar< MARKER, CLOSED > Class Template Reference

#include <astar.h>

Inheritance diagram for PathFind::AStar< MARKER, CLOSED >:

[legend]Collaboration diagram for PathFind::AStar< MARKER, CLOSED >:

[legend]List of all members.

Detailed Description

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>
class PathFind::AStar< MARKER, CLOSED >

A* search engine.

Pseudo algorithm for basic A* algorithm:

        priorityqueue Open
        list Closed

        AStarSearch
            s.g = 0 // s is the start node
            s.h = GoalDistEstimate(s)
            s.f = s.g + s.h
            s.parent = null
            push s on Open
            while Open is not empty
                pop node n from Open // n has the lowest f
                if n is a goal node
                    construct path
                    return success
                for each successor n' of n
                    newg = n.g + cost(n,n')
                    if n' is in Open or Closed
                       if n'.g <= newg skip
                       remove n' from Open or Closed
                    n'.parent = n
                    n'.g = newg
                    n'.h = GoalDistEstimate(n')
                    n'.f = n'.g + n'.h
                    push n' on Open
                push n onto Closed
            return failure // if no path found

This class is implemented as a template class taking the following template parameters:

MARKER Marker class to use (see Marker Classes)
CLOSED Closed list class to use

Statistics (see Search::createStatistics and Search::getStatistics):

"cpu_time"
"path_cost"
"path_length"
"nodes_expanded"
"nodes_visited"
"branching_factor"

Definition at line 202 of file astar.h.

Public Member Functions

AStar ()

StatisticsCollection createStatistics ()

Create a StatisticsCollection.

bool findPath (const Environment &env, int start, int target)

Find a path.

const vector< int > & getPath () const

const StatisticsCollection & getStatistics () const

Get statistics of last search.

const vector< char > & getVisitedNodes () const

Get a vector with 'x' char labels for each visited node.

void setNodesLimit (long long int nodesLimit)

Set nodes limit for search engine.

int getPathCost () const

long long int getNodesLimit () const

Public Attributes

long long int m_nodesLimit

Private Member Functions

const AStarNode * findNode (int nodeId)

Find a node in open or closed lists.

void findPathAStar (int start)

void finishSearch (int start, const AStarNode &node)

Construct path and set statistics after target node was found.

AStarNode getBestNodeFromOpen ()

Private Attributes

int m_pathCost

int m_target

const Environment * m_env

long long int m_nodesExpanded

long long int m_nodesVisited

CLOSED m_closed

vector< char > m_visitedNodes

vector< int > m_path

AStarOpen< MARKER > m_open

StatisticsCollection m_statistics

Statistics & m_branchingFactor

Constructor & Destructor Documentation

template<class MARKER, class CLOSED>

PathFind::AStar< MARKER, CLOSED >::AStar ( )

Definition at line 279 of file astar.h.

Member Function Documentation

template<class MARKER, class CLOSED>

StatisticsCollection PathFind::AStar< MARKER, CLOSED >::createStatistics ( ) [virtual]

Create a StatisticsCollection.
Contains Statistics instances for all values tracked. Useful for keeping accumulated statistics by creating the collection and merging the statistics of a search as returned by getStatistics().
Implements PathFind::Search.
Definition at line 286 of file astar.h.
References PathFind::StatisticsCollection::create().

template<class MARKER, class CLOSED>

const AStarNode * PathFind::AStar< MARKER, CLOSED >::findNode ( int nodeId ) [private]

Find a node in open or closed lists.

Definition at line 299 of file astar.h.
References PathFind::AStar< MARKER, CLOSED >::m_closed, and PathFind::AStar< MARKER, CLOSED >::m_open.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPathAStar().

template<class MARKER, class CLOSED>

bool PathFind::AStar< MARKER, CLOSED >::findPath ( const Environment & env,

int start,

int target

) [virtual]

Find a path.

Returns:
false, if search was aborted due to node limit.

Implements PathFind::Search.
Definition at line 310 of file astar.h.
References PathFind::Statistics::add(), PathFind::StatisticsCollection::clear(), PathFind::AStar< MARKER, CLOSED >::findPathAStar(), PathFind::StatisticsCollection::get(), PathFind::Environment::isValidNodeId(), PathFind::AStar< MARKER, CLOSED >::m_env, PathFind::AStar< MARKER, CLOSED >::m_nodesExpanded, PathFind::AStar< MARKER, CLOSED >::m_nodesVisited, PathFind::AStar< MARKER, CLOSED >::m_path, PathFind::AStar< MARKER, CLOSED >::m_statistics, PathFind::AStar< MARKER, CLOSED >::m_target, and PathFind::AStar< MARKER, CLOSED >::m_visitedNodes.

template<class MARKER, class CLOSED>

void PathFind::AStar< MARKER, CLOSED >::finishSearch ( int start,

const AStarNode & node

) [private]

Construct path and set statistics after target node was found.

Definition at line 382 of file astar.h.
References PathFind::Statistics::add(), PathFind::StatisticsCollection::get(), PathFind::AStar< MARKER, CLOSED >::m_closed, PathFind::AStarNode::m_f, PathFind::AStar< MARKER, CLOSED >::m_path, PathFind::AStar< MARKER, CLOSED >::m_pathCost, PathFind::AStar< MARKER, CLOSED >::m_statistics, and PathFind::AStar< MARKER, CLOSED >::m_target.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPathAStar().

template<class MARKER, class CLOSED>

AStarNode PathFind::AStar< MARKER, CLOSED >::getBestNodeFromOpen ( ) [private]

Definition at line 391 of file astar.h.
References PathFind::AStarNode::m_nodeId, PathFind::AStar< MARKER, CLOSED >::m_nodesVisited, PathFind::AStar< MARKER, CLOSED >::m_open, and PathFind::AStar< MARKER, CLOSED >::m_visitedNodes.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPathAStar().

long long int PathFind::Search::getNodesLimit ( ) const [inline, inherited]

Definition at line 48 of file search.h.
References PathFind::Search::m_nodesLimit.

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

const vector<int>& PathFind::AStar< MARKER, CLOSED >::getPath ( ) const [inline, virtual]

Implements PathFind::Search.
Definition at line 212 of file astar.h.
References PathFind::AStar< MARKER, CLOSED >::m_path.

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

int PathFind::AStar< MARKER, CLOSED >::getPathCost ( ) const [inline]

Definition at line 230 of file astar.h.
References PathFind::AStar< MARKER, CLOSED >::m_pathCost.

template<class MARKER, class CLOSED>

const StatisticsCollection & PathFind::AStar< MARKER, CLOSED >::getStatistics ( ) const [virtual]

Get statistics of last search.

Implements PathFind::Search.
Definition at line 403 of file astar.h.
References PathFind::AStar< MARKER, CLOSED >::m_statistics.

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

const vector<char>& PathFind::AStar< MARKER, CLOSED >::getVisitedNodes ( ) const [inline, virtual]

Get a vector with 'x' char labels for each visited node.

Implements PathFind::Search.
Definition at line 220 of file astar.h.
References PathFind::AStar< MARKER, CLOSED >::m_visitedNodes.

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

void PathFind::AStar< MARKER, CLOSED >::setNodesLimit ( long long int nodesLimit ) [inline]

Set nodes limit for search engine.
The default is -1 and means unlimited search. The nodes limit is a hint only, the search engine may ignore it.
Reimplemented from PathFind::Search.
Definition at line 225 of file astar.h.
References PathFind::Search::m_nodesLimit.

Member Data Documentation

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

Statistics& PathFind::AStar< MARKER, CLOSED >::m_branchingFactor [private]

Definition at line 256 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPathAStar().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

CLOSED PathFind::AStar< MARKER, CLOSED >::m_closed [private]

Definition at line 246 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findNode(), PathFind::AStar< MARKER, CLOSED >::findPathAStar(), and PathFind::AStar< MARKER, CLOSED >::finishSearch().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

const Environment* PathFind::AStar< MARKER, CLOSED >::m_env [private]

Definition at line 240 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), and PathFind::AStar< MARKER, CLOSED >::findPathAStar().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

long long int PathFind::AStar< MARKER, CLOSED >::m_nodesExpanded [private]

Definition at line 242 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), and PathFind::AStar< MARKER, CLOSED >::findPathAStar().

long long int PathFind::Search::m_nodesLimit [inherited]

Definition at line 78 of file search.h.
Referenced by PathFind::Search::getNodesLimit(), PathFind::Search::Search(), PathFind::IDAStar::searchPathIdaStar(), PathFind::Search::setNodesLimit(), and PathFind::AStar< MARKER, CLOSED >::setNodesLimit().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

long long int PathFind::AStar< MARKER, CLOSED >::m_nodesVisited [private]

Definition at line 244 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), and PathFind::AStar< MARKER, CLOSED >::getBestNodeFromOpen().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

AStarOpen<MARKER> PathFind::AStar< MARKER, CLOSED >::m_open [private]

Definition at line 252 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findNode(), PathFind::AStar< MARKER, CLOSED >::findPathAStar(), and PathFind::AStar< MARKER, CLOSED >::getBestNodeFromOpen().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

vector<int> PathFind::AStar< MARKER, CLOSED >::m_path [private]

Definition at line 250 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), PathFind::AStar< MARKER, CLOSED >::finishSearch(), and PathFind::AStar< MARKER, CLOSED >::getPath().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

int PathFind::AStar< MARKER, CLOSED >::m_pathCost [private]

Definition at line 236 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPathAStar(), PathFind::AStar< MARKER, CLOSED >::finishSearch(), and PathFind::AStar< MARKER, CLOSED >::getPathCost().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

StatisticsCollection PathFind::AStar< MARKER, CLOSED >::m_statistics [private]

Definition at line 254 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), PathFind::AStar< MARKER, CLOSED >::finishSearch(), and PathFind::AStar< MARKER, CLOSED >::getStatistics().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

int PathFind::AStar< MARKER, CLOSED >::m_target [private]

Definition at line 238 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), PathFind::AStar< MARKER, CLOSED >::findPathAStar(), and PathFind::AStar< MARKER, CLOSED >::finishSearch().

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>

vector<char> PathFind::AStar< MARKER, CLOSED >::m_visitedNodes [private]

Definition at line 248 of file astar.h.
Referenced by PathFind::AStar< MARKER, CLOSED >::findPath(), PathFind::AStar< MARKER, CLOSED >::getBestNodeFromOpen(), and PathFind::AStar< MARKER, CLOSED >::getVisitedNodes().

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

astar.h

Generated on Thu Aug 7 13:05:20 2003 by Doxygen1.3.1


Public Member Functions
	AStar ()
StatisticsCollection	createStatistics ()
	Create a StatisticsCollection.
bool	findPath (const Environment &env, int start, int target)
	Find a path.
const vector< int > &	getPath () const
const StatisticsCollection &	getStatistics () const
	Get statistics of last search.
const vector< char > &	getVisitedNodes () const
	Get a vector with 'x' char labels for each visited node.
void	setNodesLimit (long long int nodesLimit)
	Set nodes limit for search engine.
int	getPathCost () const
long long int	getNodesLimit () const
Public Attributes
long long int	m_nodesLimit
Private Member Functions
const AStarNode *	findNode (int nodeId)
	Find a node in open or closed lists.
void	findPathAStar (int start)
void	finishSearch (int start, const AStarNode &node)
	Construct path and set statistics after target node was found.
AStarNode	getBestNodeFromOpen ()
Private Attributes
int	m_pathCost
int	m_target
const Environment *	m_env
long long int	m_nodesExpanded
long long int	m_nodesVisited
CLOSED	m_closed
vector< char >	m_visitedNodes
vector< int >	m_path
AStarOpen< MARKER >	m_open
StatisticsCollection	m_statistics
Statistics &	m_branchingFactor

PathFind::AStar< MARKER, CLOSED > Class Template Reference

Detailed Description

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>> class PathFind::AStar< MARKER, CLOSED >

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class MARKER = MarkerFastClear, class CLOSED = AStarClosedLookup<MARKER>>
class PathFind::AStar< MARKER, CLOSED >