dali-scene3d/public-api/algorithm/path-finder.h

   1 #ifndef DALI_SCENE3D_PATH_FINDER_H
   2 #define DALI_SCENE3D_PATH_FINDER_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/public-api/algorithm/navigation-mesh.h>
  22 #include <dali-scene3d/public-api/algorithm/path-finder-waypoint.h>
  23 #include <dali-scene3d/public-api/api.h>
  24
  25 namespace Dali::Scene3D::Algorithm
  26 {
  27 using WayPointList = std::vector<Scene3D::Algorithm::WayPoint>;
  28
  29 /**
  30  * List of enums to be used when not using custom implementation
  31  * of path finding.
  32  */
  33 enum class PathFinderAlgorithm
  34 {
  35   DIJKSTRA_SHORTEST_PATH, ///< Using A* variant (Dijkstra) finding a shortest path. @SINCE_2_2.12
  36   SPFA,                   ///< Using SPFA-SLF (Shortest Path Fast Algorithm with Short Label First) finding a shortest path. @SINCE_2_2.12
  37   SPFA_DOUBLE_WAY,        ///< Using SPFA-SLF double way. It might not find shortest, but will use less memory. @SINCE_2_2.12
  38
  39   DEFAULT = DIJKSTRA_SHORTEST_PATH, ///< Default algorithm to use
  40 };
  41
  42 /**
  43  * @class PathFinderBase
  44  *
  45  * Base class for implementation of pathfinding algorithms.
  46  * @SINCE_2_2.12
  47  */
  48 class DALI_SCENE3D_API PathFinderBase
  49 {
  50 public:
  51   /**
  52    * @brief Destructor
  53    * @SINCE_2_2.12
  54    */
  55   virtual ~PathFinderBase() = default;
  56
  57   /**
  58    * @brief Looks for a path from point A to point B.
  59    *
  60    * @SINCE_2_2.12
  61    * @param[in] positionFrom source position in NavigationMesh parent space
  62    * @param[in] positionTo target position in NavigationMesh parent space
  63    * @return List of waypoints for path or empty vector if no success
  64    */
  65   virtual WayPointList FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo) = 0;
  66
  67   /**
  68    * @brief Finds path between NavigationMesh faces
  69    *
  70    * @SINCE_2_2.12
  71    * @param[in] polyIndexFrom Index of start polygon
  72    * @param[in] polyIndexTo Index of end polygon
  73    * @return List of waypoints for path or empty vector if no success
  74    */
  75   virtual WayPointList FindPath(FaceIndex polyIndexFrom, FaceIndex polyIndexTo) = 0;
  76 };
  77
  78 /**
  79  * @class PathFinder
  80  *
  81  * PathFinder runs path finding algorithm on associated NavigationMesh
  82  * and returns a list of waypoints.
  83  * @SINCE_2_2.12
  84  */
  85 class DALI_SCENE3D_API PathFinder
  86 {
  87 public:
  88   /**
  89    * @brief Creates new instance of path finder
  90    * @SINCE_2_2.12
  91    * @param[in] navigationMesh Navigation mesh to associate with
  92    * @param[in] algorithm algorithm to use
  93    * @return Valid pointer to PathFinder object or nullptr
  94    */
  95   static std::unique_ptr<PathFinder> New(NavigationMesh& navigationMesh, PathFinderAlgorithm algorithm);
  96
  97   /**
  98    * @brief Looks for a path from point A to point B.
  99    *
 100    * The function looks for the path between point A (positionFrom) and B (positionTo). It runs
 101    * the algorithm on the associated NavigationMesh and automatically looks for the floor point.
 102    *
 103    * It will fail if:
 104    * - Any point is outside the navigation mesh
 105    * - The path doesn't exist
 106    *
 107    * Both points should be defined in the same space as is used by the NavigationMesh.
 108    *
 109    * @SINCE_2_2.12
 110    * @param[in] positionFrom Source position
 111    * @param[in] positionTo Target position
 112    * @return List of waypoints for path or empty list on failure
 113    */
 114   WayPointList FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo);
 115
 116   /**
 117    * @brief Looks for a path between specified NavigationMesh faces
 118    *
 119    * The function looks for the path between given faces (provided as indices).
 120    *
 121    * It will fail if:
 122    * - index < 0 or index > NavigationMesh::GetFaceCount()
 123    * - The path doesn't exist
 124    *
 125    * @SINCE_2_2.12
 126    * @param[in] faceIndexFrom Source face index
 127    * @param[in] faceIndexTo Target face index
 128    * @return List of waypoints for path or empty list on failure
 129    */
 130   WayPointList FindPath(FaceIndex faceIndexFrom, FaceIndex faceIndexTo);
 131
 132 private:
 133   PathFinder() = delete;
 134
 135   DALI_INTERNAL explicit PathFinder(std::unique_ptr<PathFinderBase>&& baseImpl);
 136
 137   std::unique_ptr<PathFinderBase> mImpl;
 138 };
 139
 140 } // namespace Dali::Scene3D::Algorithm
 141
 142 #endif // DALI_SCENE3D_PATH_FINDER_H