#include <LinkAStar.hxx>

Collaboration diagram for YACS::HMI::LinkAStar:

Public Member Functions
	LinkAStar (const LinkMatrix &linkMatrix)

	~LinkAStar ()

bool	computePath (LNode from, LNode to)

LNodePath	givePath ()

bool	isAlreadyInList (std::pair< int, int > n, const LNodeMap &aList)

void	addNeighbours (std::pair< int, int > n)

std::pair< int, int >	bestNode (const LNodeMap &aList)

void	moveToClosedList (std::pair< int, int > n)

double	distance (int i1, int j1, int i2, int j2)

Protected Attributes
const LinkMatrix &	_linkMatrix

LNodeMap	_closedList

LNodeMap	_openList

LNode	_from

LNode	_to

std::priority_queue< Cost >	_pq

Detailed Description

Definition at line 68 of file LinkAStar.hxx.

Constructor & Destructor Documentation

LinkAStar::LinkAStar ( const LinkMatrix & linkMatrix )

Definition at line 47 of file LinkAStar.cxx.

References _closedList, _openList, and _pq.

                                                  : _linkMatrix(linkMatrix), _from(0,0), _to(0,0)
 {
   _closedList.clear();
   _openList.clear();
   _pq=std::priority_queue<Cost>();
 }

LinkAStar::~LinkAStar ( )

Definition at line 54 of file LinkAStar.cxx.

55 {

56 }

Member Function Documentation

void LinkAStar::addNeighbours ( std::pair< int, int > n )

Definition at line 118 of file LinkAStar.cxx.

References _closedList, _linkMatrix, _openList, _pq, _to, YACS::HMI::LinkMatrix::cost(), distance(), YACS::HMI::LCostNode::getFCost(), YACS::HMI::LCostNode::getGCost(), YACS::HMI::LCostNode::getHCost(), YACS::HMI::LNode::getX(), YACS::HMI::LNode::getY(), CORBAEngineTest::i, YACS::HMI::LinkMatrix::imax(), isAlreadyInList(), YACS::HMI::LinkMatrix::jmax(), YACS::HMI::LCostNode::setFCost(), YACS::HMI::LCostNode::setGCost(), and YACS::HMI::LCostNode::setHCost().

Referenced by computePath().

 {
   LCostNode tmp(currentNode);
   int x = currentNode.first;
   int y = currentNode.second;
   for (int i = x-1; i <= x+1; i++)
     {
       if ((i<0) || (i >= _linkMatrix.imax()))
         continue;   // --- skip: outside matrix
       for (int j = y-1; j <= y+1; j++)
         {
           if ((j<0) || (j >= _linkMatrix.jmax()))
             continue; // --- skip: outside matrix
           
           if ((i == x) && (j == y))
             continue; // --- skip: current node
 
           if ((i != x) && (j != y))
             continue; // --- skip: diagonals (move only vertical or horizontal)
           
           int cost = _linkMatrix.cost(i,j);
           if (! cost)
             continue; // --- skip: blocked
           
           pair<int,int> pos(i,j);
           if (isAlreadyInList(pos, _closedList))
             continue; // --- skip: already in closed list
           
           tmp.setGCost(_closedList[currentNode].getGCost() + cost*distance(x, y, i, j));
           tmp.setHCost(distance(i, j, _to.getX(), _to.getY()));
           tmp.setFCost(tmp.getGCost() + tmp.getHCost());
           if (isAlreadyInList(pos, _openList))
             {
               if (tmp.getFCost() < _openList[pos].getFCost())
                 {
                   _openList[pos] = tmp; // --- new path better, update node
                   _pq.push(Cost(tmp.getFCost(),pos));
                 }
             }
           else
             {
               _openList[pos] = tmp; // --- add node
               _pq.push(Cost(tmp.getFCost(),pos));
             }
         }
     }
 }

std::pair< int, int > LinkAStar::bestNode ( const LNodeMap & aList )

Definition at line 166 of file LinkAStar.cxx.

References _pq.

Referenced by computePath().

 {
   std::pair<int, int> pos;
   do
     {
       pos=_pq.top().pos;
       _pq.pop();
     }
   while(aList.count(pos)==0);
   return pos;
 }

bool LinkAStar::computePath	(	LNode	from,
		LNode	to
	)

Definition at line 58 of file LinkAStar.cxx.

References _closedList, _from, _openList, _pq, _to, addNeighbours(), bestNode(), DEBTRACE, YACS::HMI::LNode::getPos(), YACS::HMI::LNode::getX(), YACS::HMI::LNode::getY(), and moveToClosedList().

Referenced by YACS::HMI::SceneComposedNodeItem::rebuildLinks().

 {
   _closedList.clear();
   _openList.clear();
   _pq=std::priority_queue<Cost>();
   _from = from;
   _to = to;
   bool isPath = false;
 
   //pair<int, int> curPos(0, 0);
   //LCostNode startCost(curPos);
 
   pair<int, int> curPos = _from.getPos();
   LCostNode startCost(curPos);
   _openList[curPos] = startCost;
   moveToClosedList(curPos);
   addNeighbours(curPos);
 
   while (! ((curPos.first == _to.getX()) && (curPos.second == _to.getY()))
          && (!_openList.empty()))
     {
       curPos = bestNode(_openList);
       moveToClosedList(curPos);
       DEBTRACE("curPos(" << curPos.first << "," << curPos.second << ")");
       addNeighbours(curPos);
     }
 
   if ((curPos.first == _to.getX()) && (curPos.second == _to.getY()))
     isPath = true;
 
   return isPath;
 }

double YACS::HMI::LinkAStar::distance	(	int	i1,
		int	j1,
		int	i2,
		int	j2
	)

inline

Definition at line 83 of file LinkAStar.hxx.

Referenced by addNeighbours().

83 { return abs(i1-i2)+abs(j1-j2);};

LNodePath LinkAStar::givePath ( )

Definition at line 91 of file LinkAStar.cxx.

References _closedList, _from, _to, DEBTRACE, YACS::HMI::LNode::getPos(), YACS::HMI::LNode::getX(), YACS::HMI::LNode::getY(), and YACS::HMI::LNode::isEqual().

Referenced by YACS::HMI::SceneComposedNodeItem::rebuildLinks().

 {
   LNodePath aPath;
   aPath.clear();
   aPath.push_front(_to);
 
   LNode current = _to;
   while (! current.isEqual(_from))
     {
       current = LNode(_closedList[current.getPos()].getParent());
       aPath.push_front(current);
       DEBTRACE("(" << current.getX() << "," << current.getY() << ")");
     }
 //   aPath.push_front(_from);
 //   DEBTRACE("(" << _from.getX() << "," << _from.getY() << ")");
   return aPath;
 }

bool LinkAStar::isAlreadyInList	(	std::pair< int, int >	n,
		const LNodeMap &	aList
	)

Definition at line 109 of file LinkAStar.cxx.

Referenced by addNeighbours().

 {
   LNodeMap::const_iterator it = aList.find(n);
   if (it == aList.end())
     return false;
   else
     return true;
 }

void LinkAStar::moveToClosedList ( std::pair< int, int > n )

Definition at line 178 of file LinkAStar.cxx.

References _closedList, _openList, and DEBTRACE.

Referenced by computePath().

 {
   _closedList[pos] = _openList[pos];
   if (_openList.erase(pos) == 0)
     DEBTRACE("node not in open list, can't delete");
 }

Member Data Documentation

LNodeMap YACS::HMI::LinkAStar::_closedList

protected

Definition at line 86 of file LinkAStar.hxx.

Referenced by addNeighbours(), computePath(), givePath(), LinkAStar(), and moveToClosedList().

LNode YACS::HMI::LinkAStar::_from

protected

Definition at line 88 of file LinkAStar.hxx.

Referenced by computePath(), and givePath().

const LinkMatrix& YACS::HMI::LinkAStar::_linkMatrix

protected

Definition at line 83 of file LinkAStar.hxx.

Referenced by addNeighbours().

LNodeMap YACS::HMI::LinkAStar::_openList

protected

Definition at line 87 of file LinkAStar.hxx.

Referenced by addNeighbours(), computePath(), LinkAStar(), and moveToClosedList().

std::priority_queue<Cost> YACS::HMI::LinkAStar::_pq

protected

Definition at line 90 of file LinkAStar.hxx.

Referenced by addNeighbours(), bestNode(), computePath(), and LinkAStar().

LNode YACS::HMI::LinkAStar::_to

protected

Definition at line 89 of file LinkAStar.hxx.

Referenced by addNeighbours(), computePath(), and givePath().

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

src/genericgui/LinkAStar.hxx
src/genericgui/LinkAStar.cxx

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation