gwnavruntime/queries/utils/bestfirstsearchtraversal.h Source File

bestfirstsearchtraversal.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 
9 
10 
11 // ---------- Primary contact: JUBA - secondary contact: NOBODY
12 #ifndef Navigation_BestFirstSearchTraversal_H
13 #define Navigation_BestFirstSearchTraversal_H
14 
21 
22 namespace Kaim
23 {
24 
25 class NavMeshElementBlob;
26 
27 
28 /*
29 TVisitor is a class that must have following methods :
30 
31  void ComputeTriangleCost(const NavTrianglePtr& trianglePtr, KyFloat32& cost);
32 
33  Visit(const NavTrianglePtr& trianglePtr, KyFloat32 cost, const TriangleStatusInGrid& triangleStatus)
34 
35  bool IsSearchFinished();
36 
37  bool ShouldVisitTriangle(const NavTrianglePtr& trianglePtr);
38 
39  bool ShouldVisitNeighborTriangle(const NavTrianglePtr& trianglePtr, KyUInt32 indexOfNeighborTriangle);
40 
41  NavTrianglePtr GetNeighborTriangle(const NavTrianglePtr& trianglePtr, KyUInt32 indexOfNeighborTriangle);
42 
43 */
44 
45 template <class Visitor>
46 class BestFirstSearchTraversal
47 {
48  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
49 
50 public :
51  BestFirstSearchTraversal(QueryUtils& queryUtils, const CellBox& cellBox, Visitor& visitor) :
52  m_activeData(queryUtils.m_database->GetActiveData()),
53  m_visitor(&visitor),
54  m_openNodes(queryUtils.GetWorkingMemory()),
55  m_triangleStatus(queryUtils.GetWorkingMemory(), cellBox),
56  m_visitedNodes(KY_NULL) {}
57 
58  KY_INLINE void Clear()
59  {
60  m_openNodes.Clear();
61  m_triangleStatus.MakeEmpty();
62  }
63 
64  KY_INLINE bool IsInitialized() const { return m_openNodes.IsInitialized() && m_triangleStatus.IsInitialized(); }
65 
66  TraversalResult SetStartTriangle(const NavTriangleRawPtr& trianglePtr);
67  TraversalResult Search();
68 
69  KY_INLINE void SetVisitedNodeContainer(WorkingMemArray<NavTriangleRawPtr>* visitedNodes) { m_visitedNodes = visitedNodes; }
70 
71 private:
72  TraversalResult AddTriangleIfNeverEncountered(const NavTriangleRawPtr& node);
73  PropagationNode createNode(const NavTriangleRawPtr& node);
74 
75 public :
76  ActiveData* m_activeData;
77 
78  Visitor* m_visitor; //< the visitor (= the "node analyser")
79 
80  WorkingMemBinaryHeap<PropagationNode> m_openNodes; //< open nodes = nodes that are about to be analysed
81 
82  TriangleStatusInGrid m_triangleStatus; //< closed nodes = nodes that have been analysed
83  WorkingMemArray<NavTriangleRawPtr>* m_visitedNodes; //< nodes that have been visited
84 };
85 
86 
87 template <class Visitor>
88 TraversalResult BestFirstSearchTraversal<Visitor>::SetStartTriangle(const NavTriangleRawPtr& triangleRawPtr)
89 {
90  if (m_visitor->ShouldVisitTriangle(triangleRawPtr) == false)
91  return TraversalResult_DONE;
92 
93  if (m_openNodes.IsFull() == false)
94  {
95  m_openNodes.Insert(PropagationNode(triangleRawPtr));
96 
97  bool unused;
98  if (m_triangleStatus.IsInitialized() == false)
99  return TraversalResult_LACK_OF_MEMORY_FOR_CLOSED_NODES;
100 
101  return m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, unused);
102  }
103 
104  return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
105 }
106 
107 template <class Visitor>
108 TraversalResult BestFirstSearchTraversal<Visitor>::Search()
109 {
110  bool doesStoreVisited = m_visitedNodes != KY_NULL;
111 
112  //const KyUInt32 numberOfStartsNodes = m_openNodes.m_currentSize;
113  //KyUInt32 currentNumberNode = 0;
114  PropagationNode currentNode;
115 
116  while (!m_openNodes.IsEmpty())
117  {
118  m_openNodes.ExtractFirst(currentNode);
119 
120  m_visitor->Visit(currentNode.m_triangleRawPtr, currentNode.m_cost, m_triangleStatus);
121 
122  if (doesStoreVisited)
123  {
124  if (KY_FAILED(m_visitedNodes->PushBack(currentNode.m_triangleRawPtr)))
125  return TraversalResult_LACK_OF_MEMORY_FOR_VISITED_NODES;
126  }
127 
128  if (m_visitor->IsSearchFinished())
129  return TraversalResult_DONE;
130 
131  if (m_visitor->ShouldVisitNeighborTriangle(currentNode.m_triangleRawPtr, 0))
132  {
133  const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentNode.m_triangleRawPtr, 0));
134  if (rc != TraversalResult_DONE)
135  return rc;
136  }
137 
138  if (m_visitor->ShouldVisitNeighborTriangle(currentNode.m_triangleRawPtr, 1))
139  {
140  const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentNode.m_triangleRawPtr, 1));
141  if (rc != TraversalResult_DONE)
142  return rc;
143  }
144 
145  if (m_visitor->ShouldVisitNeighborTriangle(currentNode.m_triangleRawPtr, 2))
146  {
147  const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentNode.m_triangleRawPtr, 2));
148  if (rc != TraversalResult_DONE)
149  return rc;
150  }
151  }
152 
153  return TraversalResult_DONE;
154 }
155 
156 template <class Visitor>
157 TraversalResult BestFirstSearchTraversal<Visitor>::AddTriangleIfNeverEncountered(const NavTriangleRawPtr& triangleRawPtr)
158 {
159  bool nodeIsNew;
160  TraversalResult result = m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, nodeIsNew);
161  if (result != TraversalResult_DONE)
162  return result;
163 
164  if (nodeIsNew)
165  {
166  if (m_openNodes.IsFull())
167  return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
168 
169  m_openNodes.Insert(createNode(triangleRawPtr));
170  }
171 
172  return TraversalResult_DONE;
173 }
174 
175 template <class Visitor>
176 PropagationNode BestFirstSearchTraversal<Visitor>::createNode(const NavTriangleRawPtr& triangleRawPtr)
177 {
178  PropagationNode node(triangleRawPtr);
179  m_visitor->ComputeTriangleCost(triangleRawPtr, node.m_cost);
180  return node;
181 }
182 
183 
184 
185 }
186 
187 #endif // Navigation_BestFirstSearchTraversal_H
188 
Box2i CellBox
A type that represents a bounding box around cells in a 2D grid.
Definition: navmeshtypes.h:34
#define KY_FAILED(expression)
Shorthand for Kaim::Result::Fail().
Definition: types.h:274
#define KY_NULL
Null value.
Definition: types.h:247
Definition: gamekitcrowddispersion.h:20
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137