src/genericgui/LinkAStar.hxx

   1 // Copyright (C) 2006-2015  CEA/DEN, EDF R&D
   2 //
   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.
   7 //
   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.
  12 //
  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
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 #ifndef _LINKASTAR_HXX_
  21 #define _LINKASTAR_HXX_
  22
  23 #include "LinkMatrix.hxx"
  24
  25 #include <map>
  26 #include <queue>
  27 #include <list>
  28 #include <cmath>
  29 #include <stdlib.h>
  30
  31 namespace YACS
  32 {
  33   namespace HMI
  34   {
  35
  36     class LCostNode
  37     {
  38     public:
  39       LCostNode();
  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; };
  50     protected:
  51       double _gCost, _hCost, _fCost;
  52       std::pair<int,int> _parent;
  53     };
  54
  55     typedef std::map<std::pair<int,int>, LCostNode> LNodeMap;
  56
  57     struct Cost
  58       {
  59         Cost(double f,std::pair<int,int> p):F(f),pos(p) {};
  60         double F;
  61         std::pair<int,int> pos;
  62         bool operator<(const Cost& a) const
  63           {
  64             return (a.F <= F);
  65           }
  66       };
  67
  68     class LinkAStar
  69     {
  70     public:
  71       LinkAStar(const LinkMatrix& linkMatrix);
  72       ~LinkAStar();
  73
  74       bool computePath(LNode from, LNode to);
  75       LNodePath givePath();
  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);};
  84     protected:
  85       const LinkMatrix &_linkMatrix;
  86       LNodeMap _closedList;
  87       LNodeMap _openList;
  88       LNode _from;
  89       LNode _to;
  90       std::priority_queue<Cost> _pq;
  91     };
  92
  93   }
  94 }
  95 #endif