1 #ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H
2 #define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_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 PathFinderAlgorithmSPFADoubleWay : public Dali::Scene3D::Algorithm::PathFinderBase
32 * @param[in] navMesh Navigation mesh to associate with the algorithm
34 explicit PathFinderAlgorithmSPFADoubleWay(Dali::Scene3D::Algorithm::NavigationMesh& navMesh);
39 ~PathFinderAlgorithmSPFADoubleWay() 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(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) override;
59 [[nodiscard]] inline const NavigationMesh::Face* Face(uint32_t i) const
61 return mNavigationMesh->GetFace(i);
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 * @brief Calculate the panalty of node index. Low panalty "might" be calculated earlier.
74 * @pre dist and priority should be calculated.
76 * @param[in] index index of node what we want to calculate panantly.
78 float DistancePanaltyCalculate(uint32_t index) const noexcept;
81 * Structure describes single node of pathfinding algorithm
85 uint32_t faceIndex; ///< Index of face which is associated with node
88 uint32_t faces[3]; ///< List of neighbouring faces (max 3 for a triangle)
89 uint32_t edges[3]; ///< List of edges (max 3 for a triangle)
90 float weight[3]; ///< List of weights (by distance) to each neighbour
93 NavigationMesh* mNavigationMesh; ///< Pointer to a valid NavigationMesh
94 std::vector<FaceNode> mNodes; ///< List of nodes
97 std::vector<float> dist;
98 std::vector<float> priority; ///< Cached priority value. It will be calculated by source & target poly index per every queries.
99 std::vector<uint32_t> prevForward;
100 std::vector<uint32_t> prevBackward;
101 std::vector<uint32_t> componentIds; ///< Id of connected components per each nodes. It should be one of node's index.
102 std::vector<bool> queued;
104 } // namespace Dali::Scene3D::Internal::Algorithm
105 #endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H