{
if(nodes.size() != waypoints.size())
{
+ std::ostringstream oss;
+ oss << "expect indexs : [";
+ for(const auto& index : nodes)
+ {
+ oss << index << ", ";
+ }
+ oss << "]\n";
+ oss << "your indexs : [";
+ for(const auto& waypoint : waypoints)
+ {
+ oss << waypoint.GetNavigationMeshFaceIndex() << ", ";
+ }
+ oss << "]\n";
+ tet_printf("%s\n",oss.str().c_str());
return false;
}
for(auto i = 0u; i < nodes.size(); ++i )
{
if(nodes[i] != waypoints[i].GetNavigationMeshFaceIndex())
{
+ std::ostringstream oss;
+ oss << "expect indexs : [";
+ for(const auto& index : nodes)
+ {
+ oss << index << ", ";
+ }
+ oss << "]\n";
+ oss << "your indexs : [";
+ for(const auto& waypoint : waypoints)
+ {
+ oss << waypoint.GetNavigationMeshFaceIndex() << ", ";
+ }
+ oss << "]\n";
+ tet_printf("%s\n",oss.str().c_str());
return false;
}
}
tet_printf( "]");
}
-int UtcDaliPathFinderDjikstraFindPath0(void)
+int UtcDaliPathFinderFindShortestPath0(void)
{
auto navmesh = NavigationMeshFactory::CreateFromFile( "resources/navmesh-test.bin");
- auto pathfinder = PathFinder::New( *navmesh, PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH );
-
- DALI_TEST_CHECK(navmesh);
- DALI_TEST_CHECK(pathfinder);
+ std::vector<PathFinderAlgorithm> testAlgorithms = {
+ PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH,
+ PathFinderAlgorithm::SPFA,
+ };
+ for(const auto& algorithm : testAlgorithms)
{
- auto waypoints = pathfinder->FindPath(18, 139);
- DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION);
+ tet_printf("Test algorithm type : %d\n", static_cast<int>(algorithm));
+ auto pathfinder = PathFinder::New( *navmesh, algorithm );
- // Results are verified in the Blender
- std::vector<uint32_t> expectedResults =
- {18, 97, 106, 82, 50, 139};
+ DALI_TEST_CHECK(navmesh);
+ DALI_TEST_CHECK(pathfinder);
- DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION);
- }
- //printWaypointForPython(waypoints);
-
- {
- // Top floor middle to the tree
+ {
+ auto waypoints = pathfinder->FindPath(18, 139);
+ DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION);
- auto waypoints = pathfinder->FindPath(18, 157);
- DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION);
+ // Results are verified in the Blender
+ std::vector<uint32_t> expectedResults =
+ {18, 97, 106, 82, 50, 139};
+ DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION);
+ }
//printWaypointForPython(waypoints);
- // Results are verified in the Blender
- std::vector<uint32_t> expectedResults =
- {18, 97, 106, 82, 50, 6, 89, 33, 157};
+ {
+ // Top floor middle to the tree
+
+ auto waypoints = pathfinder->FindPath(18, 157);
+ DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION);
+
+ //printWaypointForPython(waypoints);
- DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION);
+ // Results are verified in the Blender
+ std::vector<uint32_t> expectedResults =
+ {18, 97, 106, 82, 50, 6, 89, 33, 157};
+ DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION);
+
+ }
}
END_TEST;
}
-int UtcDaliPathFinderDjikstraFindPath1(void)
+int UtcDaliPathFinderFindShortestPath1(void)
{
auto navmesh = NavigationMeshFactory::CreateFromFile( "resources/navmesh-test.bin");
// All coordinates in navmesh local space
navmesh->SetSceneTransform( Matrix(Matrix::IDENTITY));
- auto pathfinder = PathFinder::New( *navmesh, PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH );
-
- DALI_TEST_CHECK(navmesh);
- DALI_TEST_CHECK(pathfinder);
+ std::vector<PathFinderAlgorithm> testAlgorithms = {
+ PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH,
+ PathFinderAlgorithm::SPFA,
+ PathFinderAlgorithm::SPFA_DOUBLE_WAY, /* Note : Even this algorithm doesn't found shortest path, UTC will pass. */
+ };
+ for(const auto& algorithm : testAlgorithms)
{
- Vector3 from(-6.0767, -1.7268, 0.1438); // ground floor
- Vector3 to(-6.0767, -1.7268, 4.287); // first floor
-
- auto waypoints = pathfinder->FindPath(from, to);
- DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION);
-
- // Results are verified in the Blender
- std::vector<uint32_t> expectedResults =
- {154, 58, 85, 106, 128, 132, 137};
+ tet_printf("Test algorithm type : %d\n", static_cast<int>(algorithm));
+ auto pathfinder = PathFinder::New( *navmesh, algorithm );
- DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION);
+ DALI_TEST_CHECK(navmesh);
+ DALI_TEST_CHECK(pathfinder);
- // Verify last and first points by finding floor points
{
- Vector3 verifyPos = Vector3::ZERO;
- uint32_t verifyIndex = NavigationMesh::NULL_FACE;
- auto result = navmesh->FindFloor(from, verifyPos, verifyIndex);
-
- DALI_TEST_EQUALS(result, true, TEST_LOCATION);
- DALI_TEST_EQUALS(verifyPos, waypoints[0].GetScenePosition(), TEST_LOCATION);
- DALI_TEST_EQUALS(verifyIndex, waypoints[0].GetNavigationMeshFaceIndex(), TEST_LOCATION);
-
- // Verified with Blender
- Vector2 local(1.064201f, -0.273200f);
- DALI_TEST_EQUALS(local, waypoints[0].GetFaceLocalSpacePosition(), TEST_LOCATION);
- }
-
- {
- Vector3 verifyPos = Vector3::ZERO;
- uint32_t verifyIndex = NavigationMesh::NULL_FACE;
- auto result = navmesh->FindFloor(to, verifyPos, verifyIndex);
-
- DALI_TEST_EQUALS(result, true, TEST_LOCATION);
- DALI_TEST_EQUALS(verifyPos, waypoints.back().GetScenePosition(), TEST_LOCATION);
- DALI_TEST_EQUALS(verifyIndex, waypoints.back().GetNavigationMeshFaceIndex(), TEST_LOCATION);
-
- // Verified with Blender
- Vector2 local(0.165907f, 0.142597f);
- DALI_TEST_EQUALS(local, waypoints.back().GetFaceLocalSpacePosition(), TEST_LOCATION);
+ Vector3 from(-6.0767, -1.7268, 0.1438); // ground floor
+ Vector3 to(-6.0767, -1.7268, 4.287); // first floor
+
+ auto waypoints = pathfinder->FindPath(from, to);
+ DALI_TEST_NOT_EQUALS(int(waypoints.size()), 0, 0, TEST_LOCATION);
+
+ // Results are verified in the Blender
+ std::vector<uint32_t> expectedResults =
+ {154, 58, 85, 106, 128, 132, 137};
+
+ DALI_TEST_EQUALS(CompareResults(expectedResults, waypoints), true, TEST_LOCATION);
+
+ // Verify last and first points by finding floor points
+ {
+ Vector3 verifyPos = Vector3::ZERO;
+ uint32_t verifyIndex = NavigationMesh::NULL_FACE;
+ auto result = navmesh->FindFloor(from, verifyPos, verifyIndex);
+
+ DALI_TEST_EQUALS(result, true, TEST_LOCATION);
+ DALI_TEST_EQUALS(verifyPos, waypoints[0].GetScenePosition(), TEST_LOCATION);
+ DALI_TEST_EQUALS(verifyIndex, waypoints[0].GetNavigationMeshFaceIndex(), TEST_LOCATION);
+
+ // Verified with Blender
+ Vector2 local(1.064201f, -0.273200f);
+ DALI_TEST_EQUALS(local, waypoints[0].GetFaceLocalSpacePosition(), TEST_LOCATION);
+ }
+
+ {
+ Vector3 verifyPos = Vector3::ZERO;
+ uint32_t verifyIndex = NavigationMesh::NULL_FACE;
+ auto result = navmesh->FindFloor(to, verifyPos, verifyIndex);
+
+ DALI_TEST_EQUALS(result, true, TEST_LOCATION);
+ DALI_TEST_EQUALS(verifyPos, waypoints.back().GetScenePosition(), TEST_LOCATION);
+ DALI_TEST_EQUALS(verifyIndex, waypoints.back().GetNavigationMeshFaceIndex(), TEST_LOCATION);
+
+ // Verified with Blender
+ Vector2 local(0.165907f, 0.142597f);
+ DALI_TEST_EQUALS(local, waypoints.back().GetFaceLocalSpacePosition(), TEST_LOCATION);
+ }
}
}
--- /dev/null
+/*
+ * Copyright (c) 2023 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// INTERNAL INCLUDES
+#include <dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h>
+#include <dali-scene3d/internal/algorithm/path-finder-waypoint-data.h>
+#include <dali-scene3d/public-api/algorithm/path-finder-waypoint.h>
+
+// EXTERNAL INCLUDES
+#include <limits>
+#include <unordered_set>
+#include <vector>
+
+using WayPointList = Dali::Scene3D::Algorithm::WayPointList;
+
+namespace
+{
+constexpr float PRIORITY_SCALE_FACTOR = 0.7f; ///< The value of heuristic factor that how much will you consider
+ /// direction of source --> target. If 0.0f, we will use only dist.
+
+/**
+ * @brief Get the Component Id object
+ *
+ * @param[in,out] components Container of components id stored.
+ * @param[in] index index what we want to get components's id.
+ * @return uint32_t top-value of this components.
+ */
+uint32_t GetComponentId(std::vector<uint32_t>& components, uint32_t index)
+{
+ if(components[index] == index)
+ {
+ return index;
+ }
+ // Get my parent's components id, and update myself.
+ uint32_t ret = GetComponentId(components, components[index]);
+ return components[index] = ret;
+}
+
+/**
+ * @brief Combine two elements by Union-Find algorithm.
+ *
+ * @param[in,out] components Container of components id stored.
+ * @param[in,out] componentsLevel Container of components level stored.
+ * @param[in] index0 index of components what we want to be combined.
+ * @param[in] index1 index of components what we want to be combined.
+ */
+void ComponentsCombine(std::vector<uint32_t>& components, std::vector<uint32_t>& componentsLevel, uint32_t index0, uint32_t index1)
+{
+ uint32_t p0 = GetComponentId(components, index0);
+ uint32_t p1 = GetComponentId(components, index1);
+ if(p0 == p1)
+ {
+ return;
+ }
+
+ if(componentsLevel[p0] < componentsLevel[p1])
+ {
+ components[p0] = p1;
+ }
+ else
+ {
+ components[p1] = p0;
+ if(componentsLevel[p0] == componentsLevel[p1])
+ {
+ ++componentsLevel[p0];
+ }
+ }
+}
+} // namespace
+
+namespace Dali::Scene3D::Internal::Algorithm
+{
+PathFinderAlgorithmSPFADoubleWay::PathFinderAlgorithmSPFADoubleWay(Dali::Scene3D::Algorithm::NavigationMesh& navMesh)
+: mNavigationMesh(&GetImplementation(navMesh))
+{
+ PrepareData();
+}
+
+PathFinderAlgorithmSPFADoubleWay::~PathFinderAlgorithmSPFADoubleWay() = default;
+
+float PathFinderAlgorithmSPFADoubleWay::DistancePanaltyCalculate(uint32_t index) const noexcept
+{
+ return dist[index] - priority[index] * PRIORITY_SCALE_FACTOR;
+}
+
+Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFADoubleWay::FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo)
+{
+ Dali::Vector3 outPosFrom;
+ uint32_t polyIndexFrom;
+ auto result = mNavigationMesh->FindFloor(positionFrom, outPosFrom, polyIndexFrom);
+
+ Scene3D::Algorithm::WayPointList waypoints;
+
+ if(result)
+ {
+ Dali::Vector3 outPosTo;
+ uint32_t polyIndexTo;
+ result = mNavigationMesh->FindFloor(positionTo, outPosTo, polyIndexTo);
+
+ if(result)
+ {
+ // Get waypoints
+ waypoints = FindPath(polyIndexFrom, polyIndexTo);
+
+ // replace first and last waypoint
+ auto& wpFrom = static_cast<WayPointData&>(waypoints[0]);
+ auto& wpTo = static_cast<WayPointData&>(waypoints.back());
+
+ Vector2 fromCenter(wpFrom.point3d.x, wpFrom.point3d.y);
+ wpFrom.point3d = outPosFrom;
+ wpFrom.point2d = fromCenter - Vector2(outPosFrom.x, outPosFrom.y);
+
+ Vector2 toCenter(wpTo.point3d.x, wpTo.point3d.y);
+ wpTo.point3d = outPosTo;
+ wpTo.point2d = toCenter - Vector2(outPosTo.x, outPosTo.y);
+ wpTo.point3d = outPosTo;
+ }
+ }
+
+ // Returns waypoints with non-zero size of empty vector in case of failure (no path to be found)
+ return waypoints;
+}
+
+Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFADoubleWay::FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex)
+{
+ // Fast return if source and target index is same.
+ if(sourcePolyIndex == targetPolyIndex)
+ {
+ WayPointList waypoints;
+ waypoints.resize(1);
+
+ auto& wp = static_cast<WayPointData&>(waypoints[0]);
+ wp.face = mNavigationMesh->GetFace(sourcePolyIndex);
+ wp.nodeIndex = sourcePolyIndex;
+ wp.edge = nullptr;
+
+ return OptimizeWaypoints(waypoints);
+ }
+
+ // Fast return if source and target index is not in same components.
+ // That mean, there is no path. Return empty list.
+ if(GetComponentId(componentIds, sourcePolyIndex) != GetComponentId(componentIds, targetPolyIndex))
+ {
+ return WayPointList();
+ }
+
+ // pair<navimesh FaceIndex, is backward direction>
+ using queueItem = std::pair<uint32_t, uint8_t>;
+
+ std::list<queueItem> nodeQueue;
+
+ std::unordered_set<uint32_t> usedPolyIndexs[2];
+
+ // Set distance of source and target
+ dist[sourcePolyIndex] = 0.0f;
+ dist[targetPolyIndex] = 0.0f;
+ priority[sourcePolyIndex] = 0.0f;
+ priority[targetPolyIndex] = 0.0f;
+ queued[sourcePolyIndex] = true;
+ queued[targetPolyIndex] = true;
+ nodeQueue.push_back(std::make_pair(sourcePolyIndex, 0));
+ nodeQueue.push_back(std::make_pair(targetPolyIndex, 1));
+ usedPolyIndexs[0].insert(sourcePolyIndex);
+ usedPolyIndexs[1].insert(targetPolyIndex);
+
+ bool foundPath = false;
+ uint32_t forwardEndIndex = Scene3D::Algorithm::NavigationMesh::NULL_FACE;
+ uint32_t backwardStartIndex = Scene3D::Algorithm::NavigationMesh::NULL_FACE;
+
+ const auto sourcePos = Dali::Vector3(Face(sourcePolyIndex)->center);
+ const auto targetPos = Dali::Vector3(Face(targetPolyIndex)->center);
+ Vector3 direction = targetPos - sourcePos;
+ direction.Normalize();
+
+ // Note : we always success to found path since source and target is in same components.
+ while(!foundPath)
+ {
+ // find minimum distance
+ auto minDistIndex = nodeQueue.front().first;
+ auto isBackward = nodeQueue.front().second;
+ nodeQueue.pop_front();
+ queued[minDistIndex] = false;
+
+ // check the neighbours
+ for(auto i = 0u; i < 3 && !foundPath; ++i)
+ {
+ auto nIndex = mNodes[minDistIndex].faces[i];
+ if(nIndex != Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ if(usedPolyIndexs[!isBackward].count(nIndex))
+ {
+ // We found path!
+ foundPath = true;
+ if(isBackward)
+ {
+ forwardEndIndex = nIndex;
+ backwardStartIndex = minDistIndex;
+ }
+ else
+ {
+ forwardEndIndex = minDistIndex;
+ backwardStartIndex = nIndex;
+ }
+ break;
+ }
+
+ usedPolyIndexs[isBackward].insert(nIndex);
+
+ auto alt = dist[minDistIndex] + mNodes[minDistIndex].weight[i];
+ if(alt < dist[nIndex])
+ {
+ dist[nIndex] = alt;
+
+ if(isBackward)
+ {
+ prevBackward[nIndex] = minDistIndex;
+ if(priority[nIndex] < 0.0f)
+ {
+ const auto currentPos = Dali::Vector3(Face(nIndex)->center);
+ Vector3 diff = currentPos - targetPos;
+ priority[nIndex] = std::max(0.0f, -direction.Dot(diff));
+ }
+ }
+ else
+ {
+ prevForward[nIndex] = minDistIndex;
+ if(priority[nIndex] < 0.0f)
+ {
+ const auto currentPos = Dali::Vector3(Face(nIndex)->center);
+ Vector3 diff = currentPos - sourcePos;
+ priority[nIndex] = std::max(0.0f, direction.Dot(diff));
+ }
+ }
+
+ if(!queued[nIndex])
+ {
+ queued[nIndex] = true;
+ if(!nodeQueue.empty() && DistancePanaltyCalculate(nIndex) < DistancePanaltyCalculate(nodeQueue.front().first))
+ {
+ nodeQueue.push_front(std::make_pair(nIndex, isBackward));
+ }
+ else
+ {
+ nodeQueue.push_back(std::make_pair(nIndex, isBackward));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ // Build path of face index
+ std::list<uint32_t> q;
+ {
+ uint32_t u = forwardEndIndex;
+ while(u != Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ q.push_front(u);
+ u = prevForward[u];
+ }
+ }
+ {
+ uint32_t u = backwardStartIndex;
+ while(u != Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ q.push_back(u);
+ u = prevBackward[u];
+ }
+ }
+
+ WayPointList waypoints;
+ waypoints.resize(q.size());
+
+ auto index = 0u;
+ auto prevN = 0u;
+ for(auto n : q)
+ {
+ auto& wp = static_cast<WayPointData&>(waypoints[index]);
+ wp.face = mNavigationMesh->GetFace(n);
+ wp.nodeIndex = n;
+
+ wp.edge = nullptr;
+ // set the common edge with previous node
+ if(index > 0)
+ {
+ const auto& node = mNodes[prevN];
+ for(auto i = 0u; i < 3; ++i)
+ {
+ if(node.faces[i] == wp.nodeIndex)
+ {
+ wp.edge = mNavigationMesh->GetEdge(node.edges[i]);
+ break;
+ }
+ }
+ }
+
+ prevN = n;
+ index++;
+ }
+
+ // Reset informations what we used.
+ // Forward indexes
+ for(const auto& i : usedPolyIndexs[0])
+ {
+ dist[i] = std::numeric_limits<float>::infinity();
+ priority[i] = -1.0f; // Initialize by negative value, that we didn't calculate yet.
+ prevForward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ prevBackward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ queued[i] = false;
+ }
+ // Backward indexes
+ for(const auto& i : usedPolyIndexs[1])
+ {
+ dist[i] = std::numeric_limits<float>::infinity();
+ priority[i] = -1.0f; // Initialize by negative value, that we didn't calculate yet.
+ prevForward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ prevBackward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ queued[i] = false;
+ }
+
+ return OptimizeWaypoints(waypoints);
+}
+
+void PathFinderAlgorithmSPFADoubleWay::PrepareData()
+{
+ // Build the list structure connecting the nodes
+ auto faceCount = mNavigationMesh->GetFaceCount();
+
+ mNodes.resize(faceCount);
+ dist.resize(faceCount);
+ priority.resize(faceCount);
+ prevForward.resize(faceCount);
+ prevBackward.resize(faceCount);
+ componentIds.resize(faceCount);
+ queued.resize(faceCount);
+
+ // Temperal container for components level. It will be used for Union-Find algorithm.
+ std::vector<uint32_t> componentLevels(faceCount);
+
+ // Initialize path informations.
+ for(auto i = 0u; i < faceCount; ++i)
+ {
+ dist[i] = std::numeric_limits<float>::infinity();
+ priority[i] = -1.0f; // Initialize by negative value, that we didn't calculate yet.
+ prevForward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ prevBackward[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ queued[i] = false;
+
+ componentIds[i] = i; // Components id should be initialized by itself.
+ componentLevels[i] = 0u;
+ }
+
+ // for each face build the list
+ for(auto i = 0u; i < faceCount; ++i)
+ {
+ auto& node = mNodes[i];
+ const auto* face = mNavigationMesh->GetFace(i);
+ auto c0 = Dali::Vector3(face->center);
+
+ // for each edge add neighbouring face and compute distance to set the weight of node
+ for(auto edgeIndex = 0u; edgeIndex < 3; ++edgeIndex)
+ {
+ const auto* edge = mNavigationMesh->GetEdge(face->edge[edgeIndex]);
+ auto p1 = edge->face[0];
+ auto p2 = edge->face[1];
+
+ // One of faces is current face so ignore it
+ auto p = ((p1 != i) ? p1 : p2);
+ node.faces[edgeIndex] = p;
+ if(p != ::Dali::Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ node.edges[edgeIndex] = face->edge[edgeIndex];
+ auto c1 = Dali::Vector3(mNavigationMesh->GetFace(p)->center);
+ node.weight[edgeIndex] = (c1 - c0).Length();
+
+ // Connect two components
+ ComponentsCombine(componentIds, componentLevels, i, p);
+ }
+ }
+ }
+}
+
+[[maybe_unused]] static float ccw(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C)
+{
+ return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x);
+}
+
+[[maybe_unused]] static bool intersect(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C, const Dali::Vector2& D)
+{
+ return ccw(A, C, D) != ccw(B, C, D) && ccw(A, B, C) != ccw(A, B, D);
+}
+
+Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFADoubleWay::OptimizeWaypoints(WayPointList& waypoints) const
+{
+ WayPointList optimizedWaypoints;
+ optimizedWaypoints.emplace_back(waypoints[0]);
+ optimizedWaypoints.reserve(waypoints.size());
+
+ auto startIndex = 1u;
+
+ bool finished = false;
+ for(auto j = 0; !finished; ++j)
+ {
+ auto& startWaypoint = optimizedWaypoints.back();
+ const auto& startWaypointData = static_cast<const WayPointData&>(startWaypoint);
+
+ // add new-last waypoint which will be overriden as long as intersection takes place
+ optimizedWaypoints.emplace_back();
+ for(auto wpIndex = startIndex; wpIndex < waypoints.size(); ++wpIndex)
+ {
+ if(wpIndex == waypoints.size() - 1)
+ {
+ optimizedWaypoints.back() = waypoints.back();
+ finished = true;
+ continue;
+ }
+ // Points between centres of faces
+
+ const auto& wpData = static_cast<const WayPointData&>(waypoints[wpIndex]);
+
+ auto Pa0 = Dali::Vector2(startWaypointData.face->center[0], startWaypointData.face->center[1]);
+ auto Pa1 = Dali::Vector2(wpData.face->center[0], wpData.face->center[1]);
+
+ bool doesIntersect = true;
+ for(auto i = startIndex; i < wpIndex; ++i)
+ {
+ const auto& wp = static_cast<WayPointData&>(waypoints[i]);
+ // Skip starting waypoint
+ if(wp.face == startWaypointData.face)
+ {
+ continue;
+ }
+ auto Pb0 = mNavigationMesh->GetVertex(wp.edge->vertex[0]);
+ auto Pb1 = mNavigationMesh->GetVertex(wp.edge->vertex[1]);
+ auto vPb0 = Dali::Vector2(Pb0->x, Pb0->y);
+ auto vPb1 = Dali::Vector2(Pb1->x, Pb1->y);
+
+ doesIntersect = intersect(Pa0, Pa1, vPb0, vPb1);
+ if(!doesIntersect)
+ {
+ break;
+ }
+ }
+
+ if(!doesIntersect)
+ {
+ optimizedWaypoints.back() = waypoints[wpIndex - 1];
+ startIndex = wpIndex - 1;
+ break;
+ }
+ }
+ }
+
+ for(auto& wp : optimizedWaypoints)
+ {
+ auto& wpData = static_cast<WayPointData&>(wp);
+ wpData.point3d = mNavigationMesh->PointLocalToScene(Dali::Vector3(wpData.face->center));
+ wpData.point2d = Vector2::ZERO;
+ }
+
+ return optimizedWaypoints;
+}
+} // namespace Dali::Scene3D::Internal::Algorithm
--- /dev/null
+#ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H
+#define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H
+
+/*
+ * Copyright (c) 2023 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// INTERNAL INCLUDES
+#include <dali-scene3d/internal/algorithm/navigation-mesh-impl.h>
+#include <dali-scene3d/public-api/algorithm/path-finder.h>
+
+namespace Dali::Scene3D::Internal::Algorithm
+{
+class PathFinderAlgorithmSPFADoubleWay : public Dali::Scene3D::Algorithm::PathFinderBase
+{
+public:
+ /**
+ * @brief Constructor
+ *
+ * @param[in] navMesh Navigation mesh to associate with the algorithm
+ */
+ explicit PathFinderAlgorithmSPFADoubleWay(Dali::Scene3D::Algorithm::NavigationMesh& navMesh);
+
+ /**
+ * @brief Destructor
+ */
+ ~PathFinderAlgorithmSPFADoubleWay() override;
+
+ /**
+ * @brief Looks for a path from point A to point B.
+ *
+ * @param[in] positionFrom source position in NavigationMesh parent space
+ * @param[in] positionTo target position in NavigationMesh parent space
+ * @return List of waypoints for path
+ */
+ Scene3D::Algorithm::WayPointList FindPath(const Dali::Vector3& PositionFrom, const Dali::Vector3& PositionTo) override;
+
+ /**
+ * @brief Finds path between NavigationMesh faces
+ *
+ * @param[in] polyIndexFrom Index of start polygon
+ * @param[in] polyIndexTo Index of end polygon
+ * @return List of waypoints for path
+ */
+ Scene3D::Algorithm::WayPointList FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) override;
+
+ [[nodiscard]] inline const NavigationMesh::Face* Face(uint32_t i) const
+ {
+ return mNavigationMesh->GetFace(i);
+ }
+
+ /**
+ * Build the graph of nodes
+ * distance between nodes is weight of node
+ */
+ void PrepareData();
+
+ Scene3D::Algorithm::WayPointList OptimizeWaypoints(Scene3D::Algorithm::WayPointList& waypoints) const;
+
+ /**
+ * @brief Calculate the panalty of node index. Low panalty "might" be calculated earlier.
+ * @pre dist and priority should be calculated.
+ *
+ * @param[in] index index of node what we want to calculate panantly.
+ */
+ float DistancePanaltyCalculate(uint32_t index) const noexcept;
+
+ /**
+ * Structure describes single node of pathfinding algorithm
+ */
+ struct FaceNode
+ {
+ uint32_t faceIndex; ///< Index of face which is associated with node
+
+ // neighbours
+ uint32_t faces[3]; ///< List of neighbouring faces (max 3 for a triangle)
+ uint32_t edges[3]; ///< List of edges (max 3 for a triangle)
+ float weight[3]; ///< List of weights (by distance) to each neighbour
+ };
+
+ NavigationMesh* mNavigationMesh; ///< Pointer to a valid NavigationMesh
+ std::vector<FaceNode> mNodes; ///< List of nodes
+
+private:
+ std::vector<float> dist;
+ std::vector<float> priority; ///< Cached priority value. It will be calculated by source & target poly index per every queries.
+ std::vector<uint32_t> prevForward;
+ std::vector<uint32_t> prevBackward;
+ std::vector<uint32_t> componentIds; ///< Id of connected components per each nodes. It should be one of node's index.
+ std::vector<bool> queued;
+};
+} // namespace Dali::Scene3D::Internal::Algorithm
+#endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_DOUBLE_WAY_H
--- /dev/null
+/*
+ * Copyright (c) 2023 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// INTERNAL INCLUDES
+#include <dali-scene3d/internal/algorithm/path-finder-spfa.h>
+#include <dali-scene3d/internal/algorithm/path-finder-waypoint-data.h>
+#include <dali-scene3d/public-api/algorithm/path-finder-waypoint.h>
+
+// EXTERNAL INCLUDES
+#include <limits>
+#include <vector>
+
+using WayPointList = Dali::Scene3D::Algorithm::WayPointList;
+
+namespace Dali::Scene3D::Internal::Algorithm
+{
+PathFinderAlgorithmSPFA::PathFinderAlgorithmSPFA(Dali::Scene3D::Algorithm::NavigationMesh& navMesh)
+: mNavigationMesh(&GetImplementation(navMesh))
+{
+ PrepareData();
+}
+
+PathFinderAlgorithmSPFA::~PathFinderAlgorithmSPFA() = default;
+
+Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFA::FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo)
+{
+ Dali::Vector3 outPosFrom;
+ uint32_t polyIndexFrom;
+ auto result = mNavigationMesh->FindFloor(positionFrom, outPosFrom, polyIndexFrom);
+
+ Scene3D::Algorithm::WayPointList waypoints;
+
+ if(result)
+ {
+ Dali::Vector3 outPosTo;
+ uint32_t polyIndexTo;
+ result = mNavigationMesh->FindFloor(positionTo, outPosTo, polyIndexTo);
+
+ if(result)
+ {
+ // Get waypoints
+ waypoints = FindPath(polyIndexFrom, polyIndexTo);
+
+ // replace first and last waypoint
+ auto& wpFrom = static_cast<WayPointData&>(waypoints[0]);
+ auto& wpTo = static_cast<WayPointData&>(waypoints.back());
+
+ Vector2 fromCenter(wpFrom.point3d.x, wpFrom.point3d.y);
+ wpFrom.point3d = outPosFrom;
+ wpFrom.point2d = fromCenter - Vector2(outPosFrom.x, outPosFrom.y);
+
+ Vector2 toCenter(wpTo.point3d.x, wpTo.point3d.y);
+ wpTo.point3d = outPosTo;
+ wpTo.point2d = toCenter - Vector2(outPosTo.x, outPosTo.y);
+ wpTo.point3d = outPosTo;
+ }
+ }
+
+ // Returns waypoints with non-zero size of empty vector in case of failure (no path to be found)
+ return waypoints;
+}
+
+Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFA::FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex)
+{
+ auto nodeCount = uint32_t(mNodes.size());
+ std::vector<float> dist;
+ std::vector<uint32_t> prev;
+ std::vector<bool> queued;
+
+ dist.resize(mNodes.size());
+ prev.resize(mNodes.size());
+ queued.resize(mNodes.size());
+
+ std::list<uint32_t> nodeQueue;
+
+ [[maybe_unused]] auto sourcePos = Dali::Vector3(Face(sourcePolyIndex)->center);
+
+ for(auto i = 0u; i < nodeCount; ++i)
+ {
+ dist[i] = std::numeric_limits<float>::infinity();
+ prev[i] = Scene3D::Algorithm::NavigationMesh::NULL_FACE; // set prev to null polygon
+ queued[i] = false;
+ }
+
+ // Set distance of source
+ dist[sourcePolyIndex] = 0.0f;
+ queued[sourcePolyIndex] = true;
+ nodeQueue.push_back(sourcePolyIndex);
+
+ while(!nodeQueue.empty())
+ {
+ // find minimum distance
+ auto minDistIndex = nodeQueue.front();
+ nodeQueue.pop_front();
+ queued[minDistIndex] = false;
+
+ // Skip operator when minDistIndex is target
+ if(minDistIndex == targetPolyIndex)
+ {
+ continue;
+ }
+
+ // check the neighbours
+ for(auto i = 0u; i < 3; ++i)
+ {
+ auto nIndex = mNodes[minDistIndex].faces[i];
+ if(nIndex != Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ auto alt = dist[minDistIndex] + mNodes[minDistIndex].weight[i];
+ if(alt < dist[nIndex])
+ {
+ dist[nIndex] = alt;
+ prev[nIndex] = minDistIndex;
+
+ if(!queued[nIndex])
+ {
+ queued[nIndex] = true;
+ if(!nodeQueue.empty() && dist[nIndex] < dist[nodeQueue.front()])
+ {
+ nodeQueue.push_front(nIndex);
+ }
+ else
+ {
+ nodeQueue.push_back(nIndex);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ // Compute distances for each node back to the source
+ auto u = targetPolyIndex;
+ std::list<uint32_t> q;
+ if(prev[u] != Scene3D::Algorithm::NavigationMesh::NULL_FACE || u == sourcePolyIndex)
+ {
+ while(u != Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ q.push_front(u);
+ u = prev[u];
+ }
+ }
+
+ WayPointList waypoints;
+ waypoints.resize(q.size());
+
+ if(q.size() == 0)
+ {
+ // Fail to found path. Return empty list.
+ return waypoints;
+ }
+
+ auto index = 0u;
+ auto prevN = 0u;
+ for(auto n : q)
+ {
+ auto& wp = static_cast<WayPointData&>(waypoints[index]);
+ wp.face = mNavigationMesh->GetFace(n);
+ wp.nodeIndex = n;
+
+ wp.edge = nullptr;
+ // set the common edge with previous node
+ if(index > 0)
+ {
+ const auto& node = mNodes[prevN];
+ for(auto i = 0u; i < 3; ++i)
+ {
+ if(node.faces[i] == wp.nodeIndex)
+ {
+ wp.edge = mNavigationMesh->GetEdge(node.edges[i]);
+ break;
+ }
+ }
+ }
+
+ prevN = n;
+ index++;
+ }
+
+ return OptimizeWaypoints(waypoints);
+}
+
+void PathFinderAlgorithmSPFA::PrepareData()
+{
+ // Build the list structure connecting the nodes
+ auto faceCount = mNavigationMesh->GetFaceCount();
+
+ mNodes.resize(faceCount);
+
+ // for each face build the list
+ for(auto i = 0u; i < faceCount; ++i)
+ {
+ auto& node = mNodes[i];
+ const auto* face = mNavigationMesh->GetFace(i);
+ auto c0 = Dali::Vector3(face->center);
+
+ // for each edge add neighbouring face and compute distance to set the weight of node
+ for(auto edgeIndex = 0u; edgeIndex < 3; ++edgeIndex)
+ {
+ const auto* edge = mNavigationMesh->GetEdge(face->edge[edgeIndex]);
+ auto p1 = edge->face[0];
+ auto p2 = edge->face[1];
+
+ // One of faces is current face so ignore it
+ auto p = ((p1 != i) ? p1 : p2);
+ node.faces[edgeIndex] = p;
+ if(p != ::Dali::Scene3D::Algorithm::NavigationMesh::NULL_FACE)
+ {
+ node.edges[edgeIndex] = face->edge[edgeIndex];
+ auto c1 = Dali::Vector3(mNavigationMesh->GetFace(p)->center);
+ node.weight[edgeIndex] = (c1 - c0).Length();
+ }
+ }
+ }
+}
+
+[[maybe_unused]] static float ccw(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C)
+{
+ return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x);
+}
+
+[[maybe_unused]] static bool intersect(const Dali::Vector2& A, const Dali::Vector2& B, const Dali::Vector2& C, const Dali::Vector2& D)
+{
+ return ccw(A, C, D) != ccw(B, C, D) && ccw(A, B, C) != ccw(A, B, D);
+}
+
+Scene3D::Algorithm::WayPointList PathFinderAlgorithmSPFA::OptimizeWaypoints(WayPointList& waypoints) const
+{
+ WayPointList optimizedWaypoints;
+ optimizedWaypoints.emplace_back(waypoints[0]);
+ optimizedWaypoints.reserve(waypoints.size());
+
+ auto startIndex = 1u;
+
+ bool finished = false;
+ for(auto j = 0; !finished; ++j)
+ {
+ auto& startWaypoint = optimizedWaypoints.back();
+ const auto& startWaypointData = static_cast<const WayPointData&>(startWaypoint);
+
+ // add new-last waypoint which will be overriden as long as intersection takes place
+ optimizedWaypoints.emplace_back();
+ for(auto wpIndex = startIndex; wpIndex < waypoints.size(); ++wpIndex)
+ {
+ if(wpIndex == waypoints.size() - 1)
+ {
+ optimizedWaypoints.back() = waypoints.back();
+ finished = true;
+ continue;
+ }
+ // Points between centres of faces
+
+ const auto& wpData = static_cast<const WayPointData&>(waypoints[wpIndex]);
+
+ auto Pa0 = Dali::Vector2(startWaypointData.face->center[0], startWaypointData.face->center[1]);
+ auto Pa1 = Dali::Vector2(wpData.face->center[0], wpData.face->center[1]);
+
+ bool doesIntersect = true;
+ for(auto i = startIndex; i < wpIndex; ++i)
+ {
+ const auto& wp = static_cast<WayPointData&>(waypoints[i]);
+ // Skip starting waypoint
+ if(wp.face == startWaypointData.face)
+ {
+ continue;
+ }
+ auto Pb0 = mNavigationMesh->GetVertex(wp.edge->vertex[0]);
+ auto Pb1 = mNavigationMesh->GetVertex(wp.edge->vertex[1]);
+ auto vPb0 = Dali::Vector2(Pb0->x, Pb0->y);
+ auto vPb1 = Dali::Vector2(Pb1->x, Pb1->y);
+
+ doesIntersect = intersect(Pa0, Pa1, vPb0, vPb1);
+ if(!doesIntersect)
+ {
+ break;
+ }
+ }
+
+ if(!doesIntersect)
+ {
+ optimizedWaypoints.back() = waypoints[wpIndex - 1];
+ startIndex = wpIndex - 1;
+ break;
+ }
+ }
+ }
+
+ for(auto& wp : optimizedWaypoints)
+ {
+ auto& wpData = static_cast<WayPointData&>(wp);
+ wpData.point3d = mNavigationMesh->PointLocalToScene(Dali::Vector3(wpData.face->center));
+ wpData.point2d = Vector2::ZERO;
+ }
+
+ return optimizedWaypoints;
+}
+} // namespace Dali::Scene3D::Internal::Algorithm
--- /dev/null
+#ifndef DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H
+#define DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H
+
+/*
+ * Copyright (c) 2023 Samsung Electronics Co., Ltd.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// INTERNAL INCLUDES
+#include <dali-scene3d/internal/algorithm/navigation-mesh-impl.h>
+#include <dali-scene3d/public-api/algorithm/path-finder.h>
+
+namespace Dali::Scene3D::Internal::Algorithm
+{
+class PathFinderAlgorithmSPFA : public Dali::Scene3D::Algorithm::PathFinderBase
+{
+public:
+ /**
+ * @brief Constructor
+ *
+ * @param[in] navMesh Navigation mesh to associate with the algorithm
+ */
+ explicit PathFinderAlgorithmSPFA(Dali::Scene3D::Algorithm::NavigationMesh& navMesh);
+
+ /**
+ * @brief Destructor
+ */
+ ~PathFinderAlgorithmSPFA() override;
+
+ /**
+ * @brief Looks for a path from point A to point B.
+ *
+ * @param[in] positionFrom source position in NavigationMesh parent space
+ * @param[in] positionTo target position in NavigationMesh parent space
+ * @return List of waypoints for path
+ */
+ Scene3D::Algorithm::WayPointList FindPath(const Dali::Vector3& PositionFrom, const Dali::Vector3& PositionTo) override;
+
+ /**
+ * @brief Finds path between NavigationMesh faces
+ *
+ * @param[in] polyIndexFrom Index of start polygon
+ * @param[in] polyIndexTo Index of end polygon
+ * @return List of waypoints for path
+ */
+ Scene3D::Algorithm::WayPointList FindPath(uint32_t sourcePolyIndex, uint32_t targetPolyIndex) override;
+
+ [[nodiscard]] inline const NavigationMesh::Face* Face(uint32_t i) const
+ {
+ return mNavigationMesh->GetFace(i);
+ }
+
+ /**
+ * Build the graph of nodes
+ * distance between nodes is weight of node
+ */
+ void PrepareData();
+
+ Scene3D::Algorithm::WayPointList OptimizeWaypoints(Scene3D::Algorithm::WayPointList& waypoints) const;
+
+ /**
+ * Structure describes single node of pathfinding algorithm
+ */
+ struct FaceNode
+ {
+ uint32_t faceIndex; ///< Index of face which is associated with node
+
+ // neighbours
+ uint32_t faces[3]; ///< List of neighbouring faces (max 3 for a triangle)
+ uint32_t edges[3]; ///< List of edges (max 3 for a triangle)
+ float weight[3]; ///< List of weights (by distance) to each neighbour
+ };
+
+ NavigationMesh* mNavigationMesh; ///< Pointer to a valid NavigationMesh
+ std::vector<FaceNode> mNodes; ///< List of nodes
+};
+} // namespace Dali::Scene3D::Internal::Algorithm
+#endif // DALI_SCENE3D_INTERNAL_PATH_FINDER_SPFA_H
set(scene3d_src_files ${scene3d_src_files}
${scene3d_internal_dir}/algorithm/navigation-mesh-impl.cpp
${scene3d_internal_dir}/algorithm/path-finder-djikstra.cpp
+ ${scene3d_internal_dir}/algorithm/path-finder-spfa.cpp
+ ${scene3d_internal_dir}/algorithm/path-finder-spfa-double-way.cpp
${scene3d_internal_dir}/common/environment-map-load-task.cpp
${scene3d_internal_dir}/common/model-load-task.cpp
${scene3d_internal_dir}/controls/model/model-impl.cpp
// default algorithm
#include <dali-scene3d/internal/algorithm/path-finder-djikstra.h>
+#include <dali-scene3d/internal/algorithm/path-finder-spfa-double-way.h>
+#include <dali-scene3d/internal/algorithm/path-finder-spfa.h>
namespace Dali::Scene3D::Algorithm
{
{
PathFinderBase* impl = nullptr;
- if(algorithm == PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH)
+ switch(algorithm)
{
- impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmDjikstra(navigationMesh);
+ case PathFinderAlgorithm::DJIKSTRA_SHORTEST_PATH:
+ {
+ impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmDjikstra(navigationMesh);
+ break;
+ }
+ case PathFinderAlgorithm::SPFA:
+ {
+ impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmSPFA(navigationMesh);
+ break;
+ }
+ case PathFinderAlgorithm::SPFA_DOUBLE_WAY:
+ {
+ impl = new Dali::Scene3D::Internal::Algorithm::PathFinderAlgorithmSPFADoubleWay(navigationMesh);
+ break;
+ }
}
if(!impl)
WayPointList PathFinder::FindPath(const Dali::Vector3& positionFrom, const Dali::Vector3& positionTo)
{
- return mImpl->FindPath( positionFrom, positionTo );
+ return mImpl->FindPath(positionFrom, positionTo);
}
WayPointList PathFinder::FindPath(uint32_t polyIndexFrom, uint32_t polyIndexTo)
{
- return mImpl->FindPath( polyIndexFrom, polyIndexTo );
+ return mImpl->FindPath(polyIndexFrom, polyIndexTo);
}
-
PathFinder::PathFinder(std::unique_ptr<PathFinderBase>&& baseImpl)
{
mImpl = std::move(baseImpl);
}
-
} // namespace Dali::Scene3D::Algorithm
*/
// INTERNAL INCLUDES
-#include <dali-scene3d/public-api/api.h>
#include <dali-scene3d/public-api/algorithm/navigation-mesh.h>
#include <dali-scene3d/public-api/algorithm/path-finder-waypoint.h>
+#include <dali-scene3d/public-api/api.h>
namespace Dali::Scene3D::Algorithm
{
-
using WayPointList = std::vector<Scene3D::Algorithm::WayPoint>;
/**
enum class PathFinderAlgorithm
{
DJIKSTRA_SHORTEST_PATH, ///< Using A* variant (Djikstra) finding a shortest path
+ SPFA, ///< Using SPFA-SLF (Shortest Path Fast Algorithm with Short Label First) finding a shortest path.
+ SPFA_DOUBLE_WAY, ///< Using SPFA-SLF double way. It might not find shortest, but will use less memory.
+
DEFAULT = DJIKSTRA_SHORTEST_PATH, ///< Default algorithm to use
};
class DALI_SCENE3D_API PathFinderBase
{
public:
-
/**
* @brief Destructor
*/
class DALI_SCENE3D_API PathFinder
{
public:
-
/**
* @brief Creates new instance of path finder
* @param[in] navigationMesh Navigation mesh to associate with
* @param[in] algorithm algorithm to use
* @return Valid pointer to PathFinder object or nullptr
*/
- static std::unique_ptr<PathFinder> New( NavigationMesh& navigationMesh, PathFinderAlgorithm algorithm );
+ static std::unique_ptr<PathFinder> New(NavigationMesh& navigationMesh, PathFinderAlgorithm algorithm);
/**
* @brief Looks for a path from point A to point B.
WayPointList FindPath(uint32_t faceIndexFrom, uint32_t faceIndexTo);
private:
-
PathFinder() = delete;
DALI_INTERNAL explicit PathFinder(std::unique_ptr<PathFinderBase>&& baseImpl);
std::unique_ptr<PathFinderBase> mImpl;
};
-}
+} // namespace Dali::Scene3D::Algorithm
#endif // DALI_SCENE3D_PATH_FINDER_H