YACS::HMI::LinkAStar Class Reference

#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::LinkAStar

(

const LinkMatrix &

linkMatrix

)

Definition at line 47 of file LinkAStar.cxx.

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

References _closedList, _openList, and _pq.

~LinkAStar()

LinkAStar::~LinkAStar

(

)

Definition at line 54 of file LinkAStar.cxx.

{
}

Member Function Documentation

addNeighbours()

void LinkAStar::addNeighbours

(

std::pair< int, int >

n

)

Definition at line 118 of file LinkAStar.cxx.

{
  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));
            }
        }
    }
}

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(), yacsorb.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().

bestNode()

std::pair< int, int > LinkAStar::bestNode

(

const LNodeMap &

aList

)

Definition at line 166 of file LinkAStar.cxx.

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

References _pq.

Referenced by computePath().

computePath()

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

Definition at line 58 of file LinkAStar.cxx.

{
  _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;
}

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

distance()

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

inline

Definition at line 83 of file LinkAStar.hxx.

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

References testCppPluginInvokation::i1.

Referenced by addNeighbours().

givePath()

LNodePath LinkAStar::givePath

(

)

Definition at line 91 of file LinkAStar.cxx.

{
  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;
}

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

isAlreadyInList()

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

Definition at line 109 of file LinkAStar.cxx.

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

References gui.Appli::n.

Referenced by addNeighbours().

moveToClosedList()

void LinkAStar::moveToClosedList

(

std::pair< int, int >

n

)

Definition at line 178 of file LinkAStar.cxx.

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

References _closedList, _openList, and DEBTRACE.

Referenced by computePath().

Member Data Documentation

_closedList

LNodeMap YACS::HMI::LinkAStar::_closedList

protected

Definition at line 86 of file LinkAStar.hxx.

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

_from

LNode YACS::HMI::LinkAStar::_from

protected

Definition at line 88 of file LinkAStar.hxx.

Referenced by computePath(), and givePath().

_linkMatrix

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

protected

Definition at line 85 of file LinkAStar.hxx.

Referenced by addNeighbours().

_openList

LNodeMap YACS::HMI::LinkAStar::_openList

protected

Definition at line 87 of file LinkAStar.hxx.

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

_pq

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

protected

Definition at line 90 of file LinkAStar.hxx.

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

_to

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