gwnavruntime/queries/utils/astartraversalcontext.h Source File

astartraversalcontext.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 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 // Primary contact: JUBA - secondary contact: NOBODY
9 #ifndef Navigation_AStarQueryContext_H
10 #define Navigation_AStarQueryContext_H
11 
14 
15 namespace Kaim
16 {
17 class QueryUtils;
18 
19 /* Class for BinaryHeap to update index in binaryHeap assuming index is T::m_indexInBinaryHeap. */
20 class AstarBinHeapIndexTracker
21 {
22 public:
23  AstarBinHeapIndexTracker() : m_astarNodes(KY_NULL) {}
24  void SetAstarNodeArray(WorkingMemArray<AStarNode>& astarNodeArray);
25 
26  void OnAdd(AStarNodeIndex& aStarNodeIndex, KyUInt32 indexInBinaryHeap);
27  void OnRemove(AStarNodeIndex& aStarNodeIndex);
28  void OnSwap(AStarNodeIndex& lhs, AStarNodeIndex& rhs);
29 
30  WorkingMemArray<AStarNode>* m_astarNodes;
31 };
32 
33 class AStarNodeComparator
34 {
35 public:
36  AStarNodeComparator() : m_astarNodes(KY_NULL) {}
37  void SetAstarNodeArray(WorkingMemArray<AStarNode>& astarNodeArray);
38 
39  bool operator () (const AStarNodeIndex lhsIdx, const AStarNodeIndex rhsIdx) const;
40 
41  WorkingMemArray<AStarNode>* m_astarNodes;
42 };
43 
44 
45 typedef WorkingMemBinaryHeap<AStarNodeIndex, AStarNodeComparator, AstarBinHeapIndexTracker> AstarTraversalBinHeap;
46 
47 
48 class AStarTraversalContext
49 {
50  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_QueryWorkingMem)
51 public:
52  AStarTraversalContext() {}
53 
54  KyResult Init(QueryUtils& queryUtils, const AStarContextConfig& astarContextconfig);
55  void ReleaseWorkingMemory();
56 
57  KyResult CheckTraversalBinaryHeapMemory();
58  KyResult CheckAstarNodeArrayMemory();
59  KyResult CheckNavHalfEdgeRawPtrArrayMemory();
60  KyResult CheckNavGraphVertexRawPtrArrayMemory();
61  KyResult CheckAbstractGraphNodeRawPtrArrayMemory();
62 
63  KyResult InsertOrUpdateInBinHeapTraversal(AStarNode& neighborNode, AStarNodeIndex neighborNodeIndex);
64 
65  AstarNodeIndexInGrid m_edgeIndexGrid;
66  AstarTraversalBinHeap m_traversalBinHeap;
67  WorkingMemArray<AStarNode> m_aStarNodes;
68  WorkingMemArray<NavHalfEdgeRawPtr> m_edgeRawPtrNodes;
69  WorkingMemArray<NavGraphVertexRawPtr> m_vertexRawPtrNodes;
70  WorkingMemArray<AbstractGraphNodeRawPtr> m_abstractRawPtrNodes;
71  AStarNodeIndex m_nodeIdx; // used when removing points in the middle of edges in the AstarQuery
72 };
73 
74 
75 
76 KY_INLINE void AstarBinHeapIndexTracker::SetAstarNodeArray(WorkingMemArray<AStarNode>& astarNodeArray) { m_astarNodes = &astarNodeArray; }
77 KY_INLINE void AstarBinHeapIndexTracker::OnAdd(AStarNodeIndex& aStarNodeIndex, KyUInt32 indexInBinaryHeap)
78 {
79  AStarNode& aStarNode = (*m_astarNodes)[aStarNodeIndex];
80  aStarNode.m_indexInBinaryHeap = (IndexInBinHeap)indexInBinaryHeap;
81 }
82 // Called before the element has been removed.
83 KY_INLINE void AstarBinHeapIndexTracker::OnRemove(AStarNodeIndex& aStarNodeIndex)
84 {
85  AStarNode& aStarNode = (*m_astarNodes)[aStarNodeIndex];
86  aStarNode.m_indexInBinaryHeap = IndexInBinHeap_Removed;
87 }
88 // Called after the elements have been swapped.
89 KY_INLINE void AstarBinHeapIndexTracker::OnSwap(AStarNodeIndex& lhs, AStarNodeIndex& rhs)
90 {
91  AStarNode& aStarNode1 = (*m_astarNodes)[lhs];
92  AStarNode& aStarNode2 = (*m_astarNodes)[rhs];
93  Alg::Swap(aStarNode1.m_indexInBinaryHeap, aStarNode2.m_indexInBinaryHeap);
94 }
95 
96 KY_INLINE void AStarNodeComparator::SetAstarNodeArray(WorkingMemArray<AStarNode>& astarNodeArray) { m_astarNodes = &astarNodeArray; }
97 KY_INLINE bool AStarNodeComparator::operator () (const AStarNodeIndex lhsIdx, const AStarNodeIndex rhsIdx) const
98 {
99  AStarNode& lhs = (*m_astarNodes)[lhsIdx];
100  AStarNode& rhs = (*m_astarNodes)[rhsIdx];
101  return lhs.m_costFromStart + lhs.m_estimatedCostToDest < rhs.m_costFromStart + rhs.m_estimatedCostToDest;
102 }
103 
104 
105 KY_INLINE KyResult AStarTraversalContext::CheckTraversalBinaryHeapMemory()
106 {
107  if (m_traversalBinHeap.IsFull() == false)
108  return KY_SUCCESS;
109 
110  KY_LOG_WARNING( ("This traversal has reached its maximum working memory size for its BinaryHeap"));
111  return KY_ERROR;
112 }
113 
114 KY_INLINE KyResult AStarTraversalContext::CheckAstarNodeArrayMemory()
115 {
116  if (m_aStarNodes.IsFull() == false)
117  return KY_SUCCESS;
118 
119  KY_LOG_WARNING(("This traversal has reached its maximum working memory size for storing astarNodes"));
120  return KY_ERROR;
121 }
122 
123 KY_INLINE KyResult AStarTraversalContext::CheckNavHalfEdgeRawPtrArrayMemory()
124 {
125  if (m_edgeRawPtrNodes.IsFull() == false)
126  return KY_SUCCESS;
127 
128  KY_LOG_WARNING(("This traversal has reached its maximum working memory size for storing astarNodes and corresponding NavHalfEdgeRawPtr"));
129  return KY_ERROR;
130 }
131 
132 KY_INLINE KyResult AStarTraversalContext::CheckNavGraphVertexRawPtrArrayMemory()
133 {
134  if (m_vertexRawPtrNodes.IsFull() == false)
135  return KY_SUCCESS;
136 
137  KY_LOG_WARNING(("This traversal has reached its maximum working memory size for storing astarNodes and corresponding NavGraphVertexRawPtr"));
138  return KY_ERROR;
139 }
140 
141 KY_INLINE KyResult AStarTraversalContext::CheckAbstractGraphNodeRawPtrArrayMemory()
142 {
143  if (m_abstractRawPtrNodes.IsFull() == false)
144  return KY_SUCCESS;
145 
146  KY_LOG_WARNING(("This traversal has reached its maximum working memory size for storing astarNodes and corresponding AbstractGraphNodeRawPtr"));
147  return KY_ERROR;
148 }
149 
150 
151 KY_INLINE KyResult AStarTraversalContext::InsertOrUpdateInBinHeapTraversal(AStarNode& neighborNode, AStarNodeIndex neighborNodeIndex)
152 {
153  if (neighborNode.m_indexInBinaryHeap < IndexInBinHeap_Removed)
154  {
155  // (the node is open, already present in the binary heap), we compute its new position in the BinaryHeap
156  m_traversalBinHeap.UpdateAt(neighborNode.m_indexInBinaryHeap);
157  }
158  else
159  {
160  // the node has been removed from the BinaryHeap, we add it again
161 
162  // check for memory to insert a newElement in the binary heap
163  KY_FORWARD_ERROR_NO_LOG(CheckTraversalBinaryHeapMemory());
164 
165  m_traversalBinHeap.Insert(neighborNodeIndex);
166  }
167 
168  return KY_SUCCESS;
169 }
170 }
171 
172 
173 #endif //Navigation_AStarTypes_H
174 
KyInt32 KyResult
Defines a type that can be returned by methods or functions in the Gameware Navigation SDK to indicat...
Definition: types.h:254
#define KY_NULL
Null value.
Definition: types.h:247
Definition: gamekitcrowddispersion.h:20
#define KY_SUCCESS
Shorthand for Kaim::Result::Success.
Definition: types.h:273
#define KY_ERROR
Shorthand for Kaim::Result::Failure.
Definition: types.h:272
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36