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

   1 #ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H
   2 #define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_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 PathFinderAlgorithmSPFA : 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 PathFinderAlgorithmSPFA(Dali::Scene3D::Algorithm::NavigationMesh& navMesh);
  35
  36   /**
  37    * @brief Destructor
  38    */
  39   ~PathFinderAlgorithmSPFA() 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    * Structure describes single node of pathfinding algorithm
  74    */
  75   struct FaceNode
  76   {
  77     uint32_t faceIndex; ///< Index of face which is associated with node
  78
  79     // neighbours
  80     uint32_t faces[3];  ///< List of neighbouring faces (max 3 for a triangle)
  81     uint32_t edges[3];  ///< List of edges (max 3 for a triangle)
  82     float    weight[3]; ///< List of weights (by distance) to each neighbour
  83   };
  84
  85   NavigationMesh*       mNavigationMesh; ///< Pointer to a valid NavigationMesh
  86   std::vector<FaceNode> mNodes;          ///< List of nodes
  87 };
  88 } // namespace Dali::Scene3D::Internal::Algorithm
  89 #endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H