dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h

   1 #ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H
   2 #define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H
   3
   4 /*
   5  * Copyright (c) 2023 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 // INTERNAL INCLUDES
  21 #include <dali-scene3d/internal/algorithm/navigation-mesh-impl.h>
  22 #include <dali-scene3d/public-api/algorithm/path-finder.h>
  23
  24 namespace Dali::Scene3D::Internal::Algorithm
  25 {
  26 class PathFinderAlgorithmSPFADoubleWay : public Dali::Scene3D::Algorithm::PathFinderBase
  27 {
  28 public:
  29   /**
  30    * @brief Constructor
  31    *
  32    * @param[in] navMesh Navigation mesh to associate with the algorithm
  33    */
  34   explicit PathFinderAlgorithmSPFADoubleWay(Dali::Scene3D::Algorithm::NavigationMesh& navMesh);
  35
  36   /**
  37    * @brief Destructor
  38    */
  39   ~PathFinderAlgorithmSPFADoubleWay() override;
  40
  41   /**
  42    * @brief Looks for a path from point A to point B.
  43    *
  44    * @param[in] positionFrom source position in NavigationMesh parent space
  45    * @param[in] positionTo target position in NavigationMesh parent space
  46    * @return List of waypoints for path
  47    */
  48   Scene3D::Algorithm::WayPointList FindPath(const Dali::Vector3& PositionFrom, const Dali::Vector3& PositionTo) override;
  49
  50   /**
  51    * @brief Finds path between NavigationMesh faces
  52    *
  53    * @param[in] polyIndexFrom Index of start polygon
  54    * @param[in] polyIndexTo Index of end polygon
  55    * @return List of waypoints for path
  56    */
  57   Scene3D::Algorithm::WayPointList FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) override;
  58
  59   [[nodiscard]] inline const NavigationMesh::Face* Face(uint32_t i) const
  60   {
  61     return mNavigationMesh->GetFace(i);
  62   }
  63
  64   /**
  65    * Build the graph of nodes
  66    * distance between nodes is weight of node
  67    */
  68   void PrepareData();
  69
  70   Scene3D::Algorithm::WayPointList OptimizeWaypoints(Scene3D::Algorithm::WayPointList& waypoints) const;
  71
  72   /**
  73    * @brief Calculate the panalty of node index. Low panalty "might" be calculated earlier.
  74    * @pre dist and priority should be calculated.
  75    *
  76    * @param[in] index index of node what we want to calculate panantly.
  77    */
  78   float DistancePanaltyCalculate(uint32_t index) const noexcept;
  79
  80   /**
  81    * Structure describes single node of pathfinding algorithm
  82    */
  83   struct FaceNode
  84   {
  85     uint32_t faceIndex; ///< Index of face which is associated with node
  86
  87     // neighbours
  88     uint32_t faces[3];  ///< List of neighbouring faces (max 3 for a triangle)
  89     uint32_t edges[3];  ///< List of edges (max 3 for a triangle)
  90     float    weight[3]; ///< List of weights (by distance) to each neighbour
  91   };
  92
  93   NavigationMesh*       mNavigationMesh; ///< Pointer to a valid NavigationMesh
  94   std::vector<FaceNode> mNodes;          ///< List of nodes
  95
  96 private:
  97   std::vector<float>    dist;
  98   std::vector<float>    priority; ///< Cached priority value. It will be calculated by source & target poly index per every queries.
  99   std::vector<uint32_t> prevForward;
 100   std::vector<uint32_t> prevBackward;
 101   std::vector<uint32_t> componentIds; ///< Id of connected components per each nodes. It should be one of node's index.
 102   std::vector<bool>     queued;
 103 };
 104 } // namespace Dali::Scene3D::Internal::Algorithm
 105 #endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H