AStarSearch< UserState > Class Template Reference

#include <AStarSearch.h>

Collaboration diagram for AStarSearch< UserState >:

[legend]List of all members.

Public Types
	SS_NOT_STARTED
	SS_RUNNING
	SS_PATH_NOT_FOUND
	SS_PATH_FOUND
enum	SearchState { SS_NOT_STARTED, SS_RUNNING, SS_PATH_NOT_FOUND, SS_PATH_FOUND }
Public Member Functions
	AStarSearch (void)
	~AStarSearch (void)
void	_releaseSolution ()
void	setStartState (UserState *startState, UserState *endState)
SearchState	getSearchState ()
bool	isRunnable ()
	Returns true if the search can be advanced at least one more step.
bool	isSolved ()
	Returns true iff the search produced a valid result.
bool	isUnsolvable ()
	Returns true iff the search cannot find a valid result.
bool	advanceSearch ()
	Advances to the next best node.
const WaypointList< UserState > *	getSolutionPath ()
Private Member Functions
AStarNode *	_findBestOpenNode ()
	Retrieves the node on the Open List with the smallest total cost to reach the goal node.
AStarNode *	_getFromClosed (AStarNode *node)
AStarNode *	_getFromOpen (AStarNode *node)
bool	_isNodeClosed (AStarNode *node)
bool	_isNodeOpen (AStarNode *node)
void	_removeFromClosed (AStarNode *node)
void	_removeFromOpen (AStarNode *node)
void	_addToOpen (AStarNode *node)
void	_addToClosed (AStarNode *node)
void	_constructionWaypointList (AStarNode *endNode)
	Builds a WaypointList from UserStates.
void	_releaseNodes ()
Private Attributes
SearchState	mCurState
AStarNode *	mStartNode
UserState *	mEndState
AStarNode *	mGoalNode
vector< AStarNode * >	mOpenList
vector< AStarNode * >	mClosedList
WaypointList< UserState > *	mSolutionList
Classes
class	AStarNode
class	HeapCompare

---

Detailed Description

template<class UserState>
class AStarSearch< UserState >

Definition at line 51 of file AStarSearch.h.

---

Member Enumeration Documentation

template<class UserState>

enum AStarSearch::SearchState

Enumerator:

SS_NOT_STARTED
SS_RUNNING
SS_PATH_NOT_FOUND
SS_PATH_FOUND

Definition at line 192 of file AStarSearch.h.

        {
                SS_NOT_STARTED,
                SS_RUNNING,
                SS_PATH_NOT_FOUND,
                SS_PATH_FOUND
        };

---

Constructor & Destructor Documentation

template<class UserState>

AStarSearch< UserState >::AStarSearch

(

void

)

[inline]

Definition at line 233 of file AStarSearch.h.

References AStarSearch< UserState >::mClosedList, AStarSearch< UserState >::mCurState, AStarSearch< UserState >::mGoalNode, AStarSearch< UserState >::mOpenList, AStarSearch< UserState >::mSolutionList, AStarSearch< UserState >::mStartNode, and AStarSearch< UserState >::SS_NOT_STARTED.

        {
                mCurState = SS_NOT_STARTED;

                mGoalNode = NULL;
                mStartNode = NULL;

                mSolutionList = NULL;

                mOpenList.clear ();
                mClosedList.clear ();
        }

template<class UserState>

AStarSearch< UserState >::~AStarSearch

(

void

)

[inline]

Definition at line 247 of file AStarSearch.h.

References AStarSearch< UserState >::_releaseNodes(), and AStarSearch< UserState >::_releaseSolution().

        {
                _releaseNodes ();
                _releaseSolution ();
        }

---

Member Function Documentation

template<class UserState>

void AStarSearch< UserState >::_addToClosed

(

AStarNode *

node

)

[inline, private]

Definition at line 599 of file AStarSearch.h.

References AStarSearch< UserState >::mClosedList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                mClosedList.push_back ( node );
        }

template<class UserState>

void AStarSearch< UserState >::_addToOpen

(

AStarNode *

node

)

[inline, private]

Definition at line 590 of file AStarSearch.h.

References AStarSearch< UserState >::mOpenList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                mOpenList.push_back ( node );
#ifdef _USE_HEAP_
                push_heap ( mOpenList.begin(), mOpenList.end(), HeapCompare() );
#endif
        }

template<class UserState>

void AStarSearch< UserState >::_constructionWaypointList

(

AStarNode *

endNode

)

[inline, private]

Builds a WaypointList from UserStates.

The last UserState in the list will be the one associated with endNode. Each successor of endNode will have it's UserState added to the beginning of the list. Therefore, this method builds a list in reverse order from endNode to some startNode who's successor is NULL.

Remarks:

Make sure that there exists a node as an ancestor of endNode who's parent is NULL in order to stop the traversal.

Definition at line 618 of file AStarSearch.h.

References AStarSearch< UserState >::mSolutionList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                mSolutionList = new WaypointList<UserState>();

                AStarNode* curNode = endNode;
                while ( curNode != NULL )
                {
                        mSolutionList->addWaypointToFront ( curNode->mUserState );
                        curNode = curNode->mSuccessor;
                }
        }

template<class UserState>

AStarNode* AStarSearch< UserState >::_findBestOpenNode

(

)

[inline, private]

Retrieves the node on the Open List with the smallest total cost to reach the goal node.

This is a combination of the entry cost as well as the estimated cost to goal.

Definition at line 443 of file AStarSearch.h.

References AStarSearch< UserState >::AStarNode::getEntryCost(), AStarSearch< UserState >::AStarNode::getEstimatedGoalCost(), AStarSearch< UserState >::AStarNode::getTotalCost(), and AStarSearch< UserState >::mOpenList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                if ( mOpenList.empty () )
                        throw exception ( "AStarSearch::_findBestOpenNode - empty open list" );

                
#ifdef _USE_HEAP_
                AStarNode* bestNode = mOpenList.front();
                pop_heap ( mOpenList.begin(), mOpenList.end(), HeapCompare() );
                mOpenList.pop_back();
#else
                // Search the list backwards until we implement a priority heap
                AStarNode* bestNode = mOpenList.front ();
                float bestCost = bestNode->getTotalCost ();

                vector<AStarNode*>::iterator bestNodeIter = mOpenList.begin();
                vector<AStarNode*>::iterator iter = mOpenList.begin ();

                while ( iter != mOpenList.end () )
                {
                        if ( (*iter)->getTotalCost() < bestCost )
                        {
                                bestNode = (*iter);
                                bestCost = bestNode->getTotalCost();
                                bestNodeIter = iter;
                        }

                        iter++;
                }

                if ( bestNodeIter != mOpenList.end() )
                {
                        mOpenList.erase ( bestNodeIter );
                }
#endif

#if _DEBUG
                //cout << "Best Open Node: (" << bestNode->mUserState->mX << ", " << bestNode->mUserState->mY << ")" << endl;
                cout << "\tEntry Cost: " << bestNode->getEntryCost () << endl;
                cout << "\tGoal Cost: " << bestNode->getEstimatedGoalCost () << endl;
#endif

                return bestNode;
        }

template<class UserState>

AStarNode* AStarSearch< UserState >::_getFromClosed

(

AStarNode *

node

)

[inline, private]

Definition at line 491 of file AStarSearch.h.

References AStarSearch< UserState >::mClosedList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                vector<AStarNode*>::iterator iter = mClosedList.begin ();
                while ( iter != mClosedList.end () )
                {
                        if ( *(*iter) == (*node) )
                                return *iter;

                        iter++;
                }

                return NULL;
        }

template<class UserState>

AStarNode* AStarSearch< UserState >::_getFromOpen

(

AStarNode *

node

)

[inline, private]

Definition at line 507 of file AStarSearch.h.

References AStarSearch< UserState >::mOpenList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                vector<AStarNode*>::iterator iter = mOpenList.begin ();
                while ( iter != mOpenList.end () )
                {
                        if ( *(*iter) == (*node) )
                                return *iter;

                        iter++;
                }

                return NULL;
        }

template<class UserState>

bool AStarSearch< UserState >::_isNodeClosed

(

AStarNode *

node

)

[inline, private]

Definition at line 523 of file AStarSearch.h.

References AStarSearch< UserState >::mClosedList.

        {
                vector<AStarNode*>::iterator iter = mClosedList.begin ();
                while ( iter != mClosedList.end () )
                {
                        if ( *(*iter) == (*node) )
                                return true;

                        iter++;
                }
                return false;
        }

template<class UserState>

bool AStarSearch< UserState >::_isNodeOpen

(

AStarNode *

node

)

[inline, private]

Definition at line 537 of file AStarSearch.h.

References AStarSearch< UserState >::mClosedList.

        {
                vector<AStarNode*>::iterator iter = mClosedList.begin ();
                while ( iter != mClosedList.end () )
                {
                        if ( *(*iter) == (*node) )
                                return true;

                        iter++;
                }
                return false;
        }

template<class UserState>

void AStarSearch< UserState >::_releaseNodes

(

)

[inline, private]

Definition at line 631 of file AStarSearch.h.

References AStarSearch< UserState >::mStartNode.

Referenced by AStarSearch< UserState >::advanceSearch(), AStarSearch< UserState >::setStartState(), and AStarSearch< UserState >::~AStarSearch().

        {
                // All nodes in the search are part of a connected tree with
                // mStartNode as the root
                delete mStartNode;
                mStartNode = NULL;
        }

template<class UserState>

void AStarSearch< UserState >::_releaseSolution

(

)

[inline]

Definition at line 255 of file AStarSearch.h.

References AStarSearch< UserState >::mSolutionList.

Referenced by AStarSearch< UserState >::setStartState(), and AStarSearch< UserState >::~AStarSearch().

        {
                delete mSolutionList;
                mSolutionList = NULL;
        }

template<class UserState>

void AStarSearch< UserState >::_removeFromClosed

(

AStarNode *

node

)

[inline, private]

Definition at line 551 of file AStarSearch.h.

References AStarSearch< UserState >::mClosedList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                vector<AStarNode*>::iterator iter = mClosedList.begin ();
                while ( iter != mClosedList.end () )
                {
                        if ( *(*iter) == (*node) )
                        {
                                mClosedList.erase ( iter );
                                return;
                        }

                        iter++;
                }

                throw exception ( "AStarSearch::_removeFromClosed - Node not found" );
        }

template<class UserState>

void AStarSearch< UserState >::_removeFromOpen

(

AStarNode *

node

)

[inline, private]

Definition at line 569 of file AStarSearch.h.

References AStarSearch< UserState >::mOpenList.

Referenced by AStarSearch< UserState >::advanceSearch().

        {
                vector<AStarNode*>::iterator iter = mOpenList.begin ();
                while ( iter != mOpenList.end () )
                {
                        if ( *(*iter) == (*node) )
                        {
                                mOpenList.erase ( iter );
#ifdef _USE_HEAP_
                                make_heap ( mOpenList.begin(), mOpenList.end(), HeapCompare() );
#endif
                                return;
                        }

                        iter++;
                }

                throw exception ( "AStarSearch::_removeFromOpen - Node not found" );
        }

template<class UserState>

bool AStarSearch< UserState >::advanceSearch

(

)

[inline]

Advances to the next best node.

Definition at line 326 of file AStarSearch.h.

References AStarSearch< UserState >::_addToClosed(), AStarSearch< UserState >::_addToOpen(), AStarSearch< UserState >::_constructionWaypointList(), AStarSearch< UserState >::_findBestOpenNode(), AStarSearch< UserState >::_getFromClosed(), AStarSearch< UserState >::_getFromOpen(), AStarSearch< UserState >::_releaseNodes(), AStarSearch< UserState >::_removeFromClosed(), AStarSearch< UserState >::_removeFromOpen(), AStarSearch< UserState >::AStarNode::getEntryCost(), AStarSearch< UserState >::AStarNode::getNeighbour(), AStarSearch< UserState >::mCurState, AStarSearch< UserState >::mEndState, AStarSearch< UserState >::mOpenList, AStarSearch< UserState >::AStarNode::mUserState, AStarSearch< UserState >::SS_NOT_STARTED, AStarSearch< UserState >::SS_PATH_FOUND, AStarSearch< UserState >::SS_PATH_NOT_FOUND, and AStarSearch< UserState >::SS_RUNNING.

Referenced by AStarSearchManager< ASR::Level::LevelNode >::_advanceSearch().

        {
                if ( mCurState == SS_NOT_STARTED )
                        mCurState = SS_RUNNING;

                if ( mCurState != SS_RUNNING )
                        throw exception ( "AStarSearch::singleStep - Search not in a runnable state" );

                // We couldn't find a path
                if ( mOpenList.empty () )
                {
                        mCurState = SS_PATH_NOT_FOUND;
                }


                // Grab a node from the Open list
                AStarNode* curNode = _findBestOpenNode ();

                // We've reached the goal node so build our path
                if ( curNode->mUserState->isNode ( *mEndState ) )
                {
                        mCurState = SS_PATH_FOUND;
                        _constructionWaypointList ( curNode );
                        _releaseNodes ();
                        return true;
                }

                // Check all the neighbours for better matches and update any we find
                for ( int i = 0; i < curNode->mUserState->getNumNeighbours(); i++ )
                {
                        AStarNode* neighbour = curNode->getNeighbour ( i );
                        if ( neighbour == NULL )
                                continue;

                        // This neighbour is inpassable
                        if ( fabs( neighbour->getTraversalCost () + 1.0f ) < 0.01f )
                                continue;

                        // Determine if the node is on the closed list
                        AStarNode* closedNode = _getFromClosed ( neighbour );
                        if ( closedNode )
                        {
                                // If a node was already on the closed list, then it has been
                                // explored and has had it's neighbours explored. We may
                                // have a better way "in to" the node so consider it again
                                // with the new information
                                float newEntryCost = curNode->getEntryCost() + neighbour->getTraversalCost();
                                if ( newEntryCost < closedNode->getEntryCost() )
                                {
                                        // Update the neighbour to use the current node as the entry point
                                        neighbour->setSuccessor ( curNode );
                                        neighbour->setEntryCost ( newEntryCost );

                                        // We need to re-examine this node
                                        _removeFromClosed ( closedNode );
                                        _addToOpen ( neighbour );
                                }
                                continue;
                        }

                        // The node was set to be explored but we have found a better way in
                        // so consider this way into the node
                        AStarNode* openNode = _getFromOpen ( neighbour );
                        if ( openNode )
                        {
                                // If a node was already on the open list, it's estimated cost
                                // to the goal has already been set

                                float newEntryCost = curNode->getEntryCost() + neighbour->getTraversalCost();
                                if ( newEntryCost < neighbour->getEntryCost() )
                                {
                                        // Update the neighbour to use the current node as the entry point
                                        neighbour->setSuccessor ( curNode );
                                        neighbour->setEntryCost ( newEntryCost );
                                        
                                        _removeFromOpen ( openNode );
                                        _addToOpen ( neighbour );
                                }
                                continue;
                        }

                        // The neighbour state hasn't been considered before
                        // so set it up and add it to the open list for consideration
                        else
                        {
                                neighbour->setSuccessor ( curNode );
                                neighbour->setEntryCost ( curNode->getEntryCost() + neighbour->getTraversalCost () );
                                neighbour->setEstimatedGoalCost( neighbour->mUserState->getEstimatedCostToState( *mEndState ));
                                neighbour->createNeighbourNodes ();
                                _addToOpen ( neighbour );
                        }
                }

                _addToClosed ( curNode );

                return false;
        }

template<class UserState>

SearchState AStarSearch< UserState >::getSearchState

(

)

[inline]

Definition at line 292 of file AStarSearch.h.

References AStarSearch< UserState >::mCurState.

        {
                return mCurState;
        }

template<class UserState>

const WaypointList<UserState>* AStarSearch< UserState >::getSolutionPath

(

)

[inline]

Definition at line 425 of file AStarSearch.h.

References AStarSearch< UserState >::mSolutionList.

        {
                if ( !mSolutionList )
                        throw exception ( "AStarSearch::getSolutionPath - No solution exists" );

                return mSolutionList;
        }

template<class UserState>

bool AStarSearch< UserState >::isRunnable

(

)

[inline]

Returns true if the search can be advanced at least one more step.

Definition at line 300 of file AStarSearch.h.

References AStarSearch< UserState >::mCurState, AStarSearch< UserState >::SS_NOT_STARTED, and AStarSearch< UserState >::SS_RUNNING.

Referenced by AStarSearchManager< ASR::Level::LevelNode >::_advanceSearch().

        {
                return (mCurState == SS_RUNNING || mCurState == SS_NOT_STARTED );
        }

template<class UserState>

bool AStarSearch< UserState >::isSolved

(

)

[inline]

Returns true iff the search produced a valid result.

Definition at line 308 of file AStarSearch.h.

References AStarSearch< UserState >::mCurState, and AStarSearch< UserState >::SS_PATH_FOUND.

        {
                return (mCurState == SS_PATH_FOUND );
        }

template<class UserState>

bool AStarSearch< UserState >::isUnsolvable

(

)

[inline]

Returns true iff the search cannot find a valid result.

Definition at line 317 of file AStarSearch.h.

References AStarSearch< UserState >::mCurState, and AStarSearch< UserState >::SS_PATH_NOT_FOUND.

        {
                return (mCurState == SS_PATH_NOT_FOUND );
        }

template<class UserState>

void AStarSearch< UserState >::setStartState	(	UserState *	startState,
		UserState *	endState
	)			[inline]

Definition at line 265 of file AStarSearch.h.

References AStarSearch< UserState >::_releaseNodes(), AStarSearch< UserState >::_releaseSolution(), AStarSearch< UserState >::AStarNode::createNeighbourNodes(), AStarSearch< UserState >::mCurState, AStarSearch< UserState >::mEndState, AStarSearch< UserState >::mOpenList, AStarSearch< UserState >::mStartNode, AStarSearch< UserState >::AStarNode::mUserState, AStarSearch< UserState >::AStarNode::setEstimatedGoalCost(), and AStarSearch< UserState >::SS_PATH_NOT_FOUND.

Referenced by AStarSearchManager< ASR::Level::LevelNode >::createSearch().

        {
                _releaseNodes ();
                _releaseSolution ();

                mStartNode = NULL;
                mEndState = NULL;

                if ( fabs(endState->getTraversalCost() + 1.0f) < 0.01f )
                {
                        mCurState = SS_PATH_NOT_FOUND;
                        return;
                }

                mStartNode = new AStarNode ( startState );
                mStartNode->createNeighbourNodes ();
                mStartNode->setEstimatedGoalCost ( mStartNode->mUserState->getEstimatedCostToState ( *endState ) );

                mEndState = endState;

                mOpenList.push_back ( mStartNode );
        }

---

Member Data Documentation

template<class UserState>

vector<AStarNode*> AStarSearch< UserState >::mClosedList [private]

Definition at line 208 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::_addToClosed(), AStarSearch< UserState >::_getFromClosed(), AStarSearch< UserState >::_isNodeClosed(), AStarSearch< UserState >::_isNodeOpen(), AStarSearch< UserState >::_removeFromClosed(), and AStarSearch< UserState >::AStarSearch().

template<class UserState>

SearchState AStarSearch< UserState >::mCurState [private]

Definition at line 201 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::advanceSearch(), AStarSearch< UserState >::AStarSearch(), AStarSearch< UserState >::getSearchState(), AStarSearch< UserState >::isRunnable(), AStarSearch< UserState >::isSolved(), AStarSearch< UserState >::isUnsolvable(), and AStarSearch< UserState >::setStartState().

template<class UserState>

UserState* AStarSearch< UserState >::mEndState [private]

Definition at line 203 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::advanceSearch(), and AStarSearch< UserState >::setStartState().

template<class UserState>

AStarNode* AStarSearch< UserState >::mGoalNode [private]

Definition at line 205 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::AStarSearch().

template<class UserState>

vector<AStarNode*> AStarSearch< UserState >::mOpenList [private]

Definition at line 207 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::_addToOpen(), AStarSearch< UserState >::_findBestOpenNode(), AStarSearch< UserState >::_getFromOpen(), AStarSearch< UserState >::_removeFromOpen(), AStarSearch< UserState >::advanceSearch(), AStarSearch< UserState >::AStarSearch(), and AStarSearch< UserState >::setStartState().

template<class UserState>

WaypointList<UserState>* AStarSearch< UserState >::mSolutionList [private]

Definition at line 210 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::_constructionWaypointList(), AStarSearch< UserState >::_releaseSolution(), AStarSearch< UserState >::AStarSearch(), and AStarSearch< UserState >::getSolutionPath().

template<class UserState>

AStarNode* AStarSearch< UserState >::mStartNode [private]

Definition at line 202 of file AStarSearch.h.

Referenced by AStarSearch< UserState >::_releaseNodes(), AStarSearch< UserState >::AStarSearch(), and AStarSearch< UserState >::setStartState().

---

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

• D:/simple_rts/include/AStarSearch.h

---