X-Git-Url: http://git.salome-platform.org/gitweb/?a=blobdiff_plain;f=src%2Fgenericgui%2FLinkAStar.hxx;h=02ce5f91835f03319a1f06bcf9b9e17fa55dadf9;hb=a23297fae67e406c4b7f4a3361877346e15b9263;hp=cbd2bf1176a1df8ed7666e823c39bf347c031f72;hpb=f4c10bf1781a76534bb1fa293aef541aef56148b;p=modules%2Fyacs.git

diff --git a/src/genericgui/LinkAStar.hxx b/src/genericgui/LinkAStar.hxx
index cbd2bf117..02ce5f918 100644
--- a/src/genericgui/LinkAStar.hxx
+++ b/src/genericgui/LinkAStar.hxx
@@ -1,28 +1,32 @@
-//  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
 {
@@ -50,6 +54,17 @@ 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:
@@ -62,13 +77,17 @@ namespace YACS
       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;
     };
 
   }