gwnavruntime/queries/utils/astartraversal.h Source File

astartraversal.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 
8 #pragma once
9 
12 
16 
18 
20 
22 
23 namespace Kaim
24 {
25 
26 class TraversalVisitNodeContext
27 {
28 public:
29  TraversalVisitNodeContext() {}
30  void Clear();
31 
32 public:
33  NavGraphVertexRawPtr m_visitedGraphVertexRawPtr;
34  AStarNodeIndex m_visitedNodeIndex;
35 };
36 
37 template<class TraversalCustomzier>
38 class AStarTraversal
39 {
40  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
41 public:
42  typedef typename TraversalCustomzier::TLogic TraverseLogic;
43 
44  // Constructs a new instance of this class.
45  AStarTraversal() : m_traversalCustomizer(), m_astarContext(nullptr), m_traversalParams(nullptr) {}
46  AStarTraversal(const TraversalCustomzier& customizer) : m_traversalCustomizer(customizer), m_astarContext(nullptr), m_traversalParams(nullptr) {}
47 
48  KyResult InitializeContextAndStartNode(QueryUtils& queryUtils, const Vec3f& startPos3f, const NavTrianglePtr& startTrianglePtr);
49  KyResult InitializeContextAndStartNode(QueryUtils& queryUtils, const Vec3f& startPos3f, const NavGraphEdgePtr& startNavGraphEdgePtr);
50  KyResult InitializeContextAndStartNode(QueryUtils& queryUtils, const Vec3f& startPos3f, const NavGraphVertexPtr& startNavGraphVertexPtr);
51 
52  // must be called after the StartNode initialisation
53  KyResult InitializeDestNode(const Vec3f& destPos, const NavTrianglePtr& destTrianglePtr);
54  KyResult InitializeDestNode(const Vec3f& destPos, const NavGraphEdgePtr& destNavGraphEdgePtr);
55  KyResult InitializeDestNode(const NavGraphVertexPtr& destNavGraphVertexPtr);
56 
57  KyResult ExploreAllNodesInTriangle(ActiveData* activeData, const NavTriangleRawPtr& triangleRawPtr, AStarNodeIndex currentNodeIndex);
58  // used only when we start the traversal from a NavGraphEdge
59  KyResult ExploreAllNodesInNavGraphEdge(ActiveData* activeData, const Vec3f& posOnEdge, const NavGraphEdgeRawPtr& navGraphEdgeRawPtr, AStarNodeIndex currentNodeIndex, NavGraphEdgeDirection m_navGraphEdgePathfindMode);
60 
61  KY_INLINE bool IsThereNodeToVisit() { return m_astarContext->m_traversalBinHeap.IsEmpty() == false; }
62 
63  // Performs a single iteration of the AStar Algorithm.
64  KyResult VisitNode(QueryUtils& queryUtils, TraversalVisitNodeContext& visitNodeContext);
65  KyResult UpdateOpenedOrClosedNode(AStarNodeIndex neighborNodeIndex, AStarNodeIndex currentNodeIndex,
66  KyFloat32 costFromCurrentNode, KyFloat32 costMultiplierFromCurrent);
67 
68 private:
69  KyResult ExploreNeighborsOfHalfEdgeNode(ActiveData* activeData, AStarNodeIndex indexOfOpenWithLowerCost, const NavHalfEdgeRawPtr& currentEdgeRawPtr,
70  const NavHalfEdgeRawPtr& pairHalfEdgeRawPtr, const Vec3f& nodePosition, const LogicDoNotUseCanEnterNavTag&);
71  KyResult ExploreNeighborsOfHalfEdgeNode(ActiveData* activeData, AStarNodeIndex indexOfOpenWithLowerCost, const NavHalfEdgeRawPtr& currentEdgeRawPtr,
72  const NavHalfEdgeRawPtr& pairHalfEdgeRawPtr, const Vec3f& nodePosition, const LogicDoUseCanEnterNavTag&);
73 
74  KyResult ExploreNeighborsOfHalfEdgeNode(ActiveData* activeData, AStarNodeIndex indexOfOpenWithLowerCost, const NavHalfEdgeRawPtr& halfEdgeRawPtr);
75  KyResult ExploreNeighborsOfGraphVertexNode(ActiveData* activeData, AStarNodeIndex indexOfOpenWithLowerCost, NavGraphVertexRawPtr& visitedGraphVertexRawPtr);
76  KyResult ExploreNeighborsOfAbstractGraphNode(AStarNodeIndex currentCostNodeIndex, const AbstractGraphNodeRawPtr& currentAbstractNodeRawPtr);
77 
78  KyResult ExploreHalfEdgesOfTriangle(ActiveData* activeData, const NavTriangleRawPtr& triangleRawPtr, AStarNodeIndex currentNodeIndex);
79  KyResult ExploreGraphVerticesInTriangle(const NavTriangleRawPtr& triangleRawPtr, AStarNodeIndex currentNodeIndex);
80  KyResult ExploreAbstractGraphNodesInTriangle(const NavTriangleRawPtr& triangleRawPtr, AStarNodeIndex currentNodeIndex);
81 
82  KyResult ExploreAbstractGraphNodesOnNavHalEdgeRawPtr(const NavHalfEdgeRawPtr& navHalfEdgeRawPtr, AStarNodeIndex currentNodeIndex);
83 
84  KyResult CreateNewHalfEdgeNode(ActiveData* activeData, const NavHalfEdgeRawPtr& HalfEdge, const NavHalfEdgeRawPtr& pairHalfEdge,
85  const Vec3f& startPosOfEdge, const Vec3f& endPosOfEdge, AStarNodeIndex predecessorIndex);
86 
87  KyResult CreateNewGraphVertexNode(const NavGraphVertexRawPtr& navGraphVertexRawPtr, AStarNodeIndex predecessorIndex,
88  KyFloat32 costFromCurrentNode, KyFloat32 costMultiplier);
89  KyResult CreateNewAbstractGraphNode(const AbstractGraphNodeRawPtr& abstractGraphNodeRawPtr, const AbstractGraphNodeRawPtr& pairedAbstractGraphNodeRawPtr,
90  AStarNodeIndex predecessorNodeIndex, KyFloat32 costFromCurrentNode);
91 
92  KyResult OpenOrUpdateGraphVertex(const NavGraphVertexRawPtr& navGraphVertexRawPtr, AStarNodeIndex vertexNodeIndex, AStarNodeIndex currentNodeIndex,
93  KyFloat32 costFromCurrentNode, KyFloat32 costMultiplier);
94 
95  KyResult OpenOrUpdateHalfEdge(ActiveData* activeData, const NavHalfEdgeRawPtr& halfEdge, AStarNodeIndex halfEdgeNodeIndex,
96  const Vec3f& startPosOfEdge, const Vec3f& endPosOfEdge, AStarNodeIndex currentNodeIndex);
97 
98  KyResult OpenOrUpdateAbstractGraphNode(const AbstractGraphNodeRawPtr& neighborAbstractNodeRawPtr,
99  AStarNodeIndex neighborAstarNodeIndex, AStarNodeIndex currentNodeIndex, KyFloat32 costFromCurrentNode);
100 
101  bool ShouldOpenHalfEdgeNode(const NavHalfEdgeRawPtr& halfEdge, NavHalfEdgeRawPtr& pairHalfEdgeOfNewNode);
102  bool ShouldOpenGraphVertexNode(const NavGraphVertexRawPtr& navGraphVertexRawPtr);
103  bool ShouldOpenAbstractGraphNode(const AbstractGraphNodeRawPtr& abstractGraphNodeRawPtr, AbstractGraphNodeRawPtr& pairedAbstractGraphNodeRawPtr);
104 
105  bool CanTraverseNavTriangle(const NavTriangleRawPtr& triangle);
106  bool CanTraverseNavTriangleAndGetCost(const NavTriangleRawPtr& triangle, const Vec3f& A, const Vec3f& B, KyFloat32& cost, KyFloat32& costMultiplier);
107  bool CanTraverseGraphEdgeAndGetCost(const NavGraphEdgeRawPtr& edge, const Vec3f& A, const Vec3f& B, KyFloat32& cost, KyFloat32& costMultiplier);
108 
109  KyFloat32 EvaluateCostToDest(const Vec3f& nodePosition);
110 
111 public: // internal
112  KyResult InitializeInvalidDestNode();
113 
114 public:
115  TraversalCustomzier m_traversalCustomizer;
116 public:
117  AStarTraversalContext* m_astarContext;
118  TraversalParameters* m_traversalParams;
119 };
120 
121 }
122 
124 
125 
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
Navigation return code class.
Definition: types.h:108
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
float KyFloat32
float
Definition: types.h:32