1 #ifndef DALI_SCENE3D_PATH_FINDER_H
2 #define DALI_SCENE3D_PATH_FINDER_H
5 * Copyright (c) 2023 Samsung Electronics Co., Ltd.
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
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>
25 namespace Dali::Scene3D::Algorithm
27 using WayPointList = std::vector<Scene3D::Algorithm::WayPoint>;
30 * List of enums to be used when not using custom implementation
33 enum class PathFinderAlgorithm
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.
39 DEFAULT = DJIKSTRA_SHORTEST_PATH, ///< Default algorithm to use
43 * @class PathFinderBase
45 * Base class for implementation of pathfinding algorithms.
47 class DALI_SCENE3D_API PathFinderBase
53 virtual ~PathFinderBase() = default;
56 * @brief Looks for a path from point A to point B.
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
62 virtual WayPointList FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo) = 0;
65 * @brief Finds path between NavigationMesh faces
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
71 virtual WayPointList FindPath(FaceIndex polyIndexFrom, FaceIndex polyIndexTo) = 0;
77 * PathFinder runs path finding algorithm on associated NavigationMesh
78 * and returns a list of waypoints.
80 class DALI_SCENE3D_API PathFinder
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
89 static std::unique_ptr<PathFinder> New(NavigationMesh& navigationMesh, PathFinderAlgorithm algorithm);
92 * @brief Looks for a path from point A to point B.
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.
98 * - Any point is outside the navigation mesh
99 * - The path doesn't exist
101 * Both points should be defined in the same space as is used by the NavigationMesh.
103 * @param[in] positionFrom Source position
104 * @param[in] positionTo Target position
105 * @return List of waypoints for path or empty list on failure
107 WayPointList FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo);
110 * @brief Looks for a path between specified NavigationMesh faces
112 * The function looks for the path between given faces (provided as indices).
115 * - index < 0 or index > NavigationMesh::GetFaceCount()
116 * - The path doesn't exist
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
122 WayPointList FindPath(FaceIndex faceIndexFrom, FaceIndex faceIndexTo);
125 PathFinder() = delete;
127 DALI_INTERNAL explicit PathFinder(std::unique_ptr<PathFinderBase>&& baseImpl);
129 std::unique_ptr<PathFinderBase> mImpl;
132 } // namespace Dali::Scene3D::Algorithm
134 #endif // DALI_SCENE3D_PATH_FINDER_H