1 // Copyright (C) 2006-2016 CEA/DEN, EDF R&D
3 // This library is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU Lesser General Public
5 // License as published by the Free Software Foundation; either
6 // version 2.1 of the License, or (at your option) any later version.
8 // This library is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 // Lesser General Public License for more details.
13 // You should have received a copy of the GNU Lesser General Public
14 // License along with this library; if not, write to the Free Software
15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
20 #ifndef _LINKASTAR_HXX_
21 #define _LINKASTAR_HXX_
23 #include "LinkMatrix.hxx"
40 LCostNode(std::pair<int,int> parent);
41 virtual ~LCostNode() {};
42 inline void setParent(std::pair<int,int> parent) { _parent = parent; };
43 std::pair<int,int> getParent() const {return _parent; };
44 inline void setGCost(double c) { _gCost = c; };
45 inline void setHCost(double c) { _hCost = c; };
46 inline void setFCost(double c) { _fCost = c; };
47 inline double getGCost() const { return _gCost; };
48 inline double getHCost() const { return _hCost; };
49 inline double getFCost() const { return _fCost; };
51 double _gCost, _hCost, _fCost;
52 std::pair<int,int> _parent;
55 typedef std::map<std::pair<int,int>, LCostNode> LNodeMap;
59 Cost(double f,std::pair<int,int> p):F(f),pos(p) {};
61 std::pair<int,int> pos;
62 bool operator<(const Cost& a) const
71 LinkAStar(const LinkMatrix& linkMatrix);
74 bool computePath(LNode from, LNode to);
76 bool isAlreadyInList(std::pair<int,int> n, const LNodeMap& aList);
77 void addNeighbours(std::pair<int,int> n);
78 std::pair<int,int> bestNode(const LNodeMap& aList);
79 void moveToClosedList(std::pair<int,int> n);
80 //inline double distance(int i1, int j1, int i2, int j2) { return std::sqrt(double((i1-i2)*(i1-i2) + (j1-j2)*(j1-j2)));};
81 //inline double distance(int i1, int j1, int i2, int j2) { return double((i1-i2)*(i1-i2) + (j1-j2)*(j1-j2));};
82 //manhattan distance is better for 4 connected cells
83 inline double distance(int i1, int j1, int i2, int j2) { return abs(i1-i2)+abs(j1-j2);};
85 const LinkMatrix &_linkMatrix;
90 std::priority_queue<Cost> _pq;