1 #ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_DIJKSTRA_H
2 #define DALI_SCENE3D_INTERNAL_PATH_FINDER_DIJKSTRA_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/internal/algorithm/navigation-mesh-impl.h>
22 #include <dali-scene3d/public-api/algorithm/path-finder.h>
24 namespace Dali::Scene3D::Internal::Algorithm
26 class PathFinderAlgorithmDijkstra : public Dali::Scene3D::Algorithm::PathFinderBase
32 * @param[in] navMesh Navigation mesh to associate with the algorithm
34 explicit PathFinderAlgorithmDijkstra(Dali::Scene3D::Algorithm::NavigationMesh& navMesh);
39 ~PathFinderAlgorithmDijkstra() override;
42 * @brief Looks for a path from point A to point B.
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
48 Scene3D::Algorithm::WayPointList FindPath(const Dali::Vector3& PositionFrom, const Dali::Vector3& PositionTo) override;
51 * @brief Finds path between NavigationMesh faces
53 * @param[in] polyIndexFrom Index of start polygon
54 * @param[in] polyIndexTo Index of end polygon
55 * @return List of waypoints for path
57 Scene3D::Algorithm::WayPointList FindPath(FaceIndex sourcePolyIndex, FaceIndex targetPolyIndex) override;
59 [[nodiscard]] inline const NavigationMesh::Face* Face(FaceIndex faceIndex) const
61 return mNavigationMesh->GetFace(faceIndex);
65 * Build the graph of nodes
66 * distance between nodes is weight of node
70 Scene3D::Algorithm::WayPointList OptimizeWaypoints(Scene3D::Algorithm::WayPointList& waypoints) const;
73 * Structure describes single node of pathfinding algorithm
78 FaceIndex faces[3]; ///< List of neighbouring faces (max 3 for a triangle)
79 EdgeIndex edges[3]; ///< List of edges (max 3 for a triangle)
80 float weight[3]; ///< List of weights (by distance) to each neighbour
82 using FaceNodeIndex = FaceIndex;
84 NavigationMesh* mNavigationMesh; ///< Pointer to a valid NavigationMesh
85 std::vector<FaceNode> mNodes; ///< List of nodes
87 } // namespace Dali::Scene3D::Internal::Algorithm
88 #endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_DIJKSTRA_H