-// Copyright (C) 2006-2008 CEA/DEN, EDF R&D
+// Copyright (C) 2006-2020 CEA/DEN, EDF R&D
//
-// This library is free software; you can redistribute it and/or
-// modify it under the terms of the GNU Lesser General Public
-// License as published by the Free Software Foundation; either
-// version 2.1 of the License.
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
//
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-// Lesser General Public License for more details.
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
//
-// You should have received a copy of the GNU Lesser General Public
-// License along with this library; if not, write to the Free Software
-// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+// You should have received a copy of the GNU Lesser General Public
+// License along with this library; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
-// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
+// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
//
+
#ifndef _LINKASTAR_HXX_
#define _LINKASTAR_HXX_
#include "LinkMatrix.hxx"
#include <map>
+#include <queue>
#include <list>
+#include <cmath>
+#include <stdlib.h>
namespace YACS
{
typedef std::map<std::pair<int,int>, LCostNode> LNodeMap;
+ struct Cost
+ {
+ Cost(double f,std::pair<int,int> p):F(f),pos(p) {};
+ double F;
+ std::pair<int,int> pos;
+ bool operator<(const Cost& a) const
+ {
+ return (a.F < F);
+ }
+ };
+
class LinkAStar
{
public:
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);
+ //inline double distance(int i1, int j1, int i2, int j2) { return std::sqrt(double((i1-i2)*(i1-i2) + (j1-j2)*(j1-j2)));};
+ //inline double distance(int i1, int j1, int i2, int j2) { return double((i1-i2)*(i1-i2) + (j1-j2)*(j1-j2));};
+ //manhattan distance is better for 4 connected cells
+ inline double distance(int i1, int j1, int i2, int j2) { return abs(i1-i2)+abs(j1-j2);};
protected:
const LinkMatrix &_linkMatrix;
LNodeMap _closedList;
LNodeMap _openList;
LNode _from;
LNode _to;
+ std::priority_queue<Cost> _pq;
};
}