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