gwnavruntime/queries/utils/breadthfirstsearchtraversal.h Source File

breadthfirstsearchtraversal.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 #pragma once
8 
15 
16 namespace Kaim
17 {
18 
19 class NavMeshElementBlob;
20 
21 
28 template <class Visitor>
30 {
31  KY_DEFINE_NEW_DELETE_OPERATORS(MemStat_Query)
32 
33 public:
35  QueryUtils& queryUtils, const CellBox& cellBox, Visitor& visitor) :
36  m_activeData(queryUtils.m_database->GetActiveData()),
37  m_visitor(&visitor),
38  m_openNodes(queryUtils.GetWorkingMemory()),
39  m_triangleStatus(queryUtils.GetWorkingMemory(), cellBox),
40  m_visitedNodes(nullptr) {}
41 
42  KY_INLINE void Clear()
43  {
44  m_openNodes.MakeEmpty();
45  m_triangleStatus.MakeEmpty();
46  }
47 
48  KY_INLINE bool IsInitialized() const { return m_openNodes.IsInitialized() && m_triangleStatus.IsInitialized(); }
49 
50  // the navTag of the startTriangle is not tested
51  inline TraversalResult SetStartTriangle(const NavTriangleRawPtr& triangleRawPtr);
52 
53  TraversalResult AddTriangleIfNeverEncountered(const NavTriangleRawPtr& triangleRawPtr);
54 
55  TraversalResult Search();
56 
57  KY_INLINE void SetVisitedNodeContainer(WorkingMemArray<NavTriangleRawPtr>* visitedNodes) { m_visitedNodes = visitedNodes; }
58 
59 public:
60  ActiveData* m_activeData;
61 
62  Visitor* m_visitor; //< the visitor (= the "node analyser")
63 
64  WorkingMemDeque<NavTriangleRawPtr> m_openNodes; //< open nodes = nodes that are about to be analysed
65 
66  TriangleStatusInGrid m_triangleStatus; //< closed nodes = nodes that have been analysed
67  WorkingMemArray<NavTriangleRawPtr>* m_visitedNodes; //< nodes that have been visited
68 };
69 
70 template <class Visitor>
72 {
73  if (m_visitor->ShouldVisitTriangle(triangleRawPtr) == false)
74  return TraversalResult_DONE;
75 
76  if (m_openNodes.PushBack(triangleRawPtr) == KY_ERROR)
77  return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
78 
79  bool unused;
80  if (m_triangleStatus.IsInitialized() == false)
81  return TraversalResult_LACK_OF_MEMORY_FOR_CLOSED_NODES;
82 
83  return m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, unused);
84 }
85 
86 template <class Visitor>
87 TraversalResult BreadthFirstSearchTraversal<Visitor>::Search()
88 {
89  bool doesStoreVisited = m_visitedNodes != nullptr;
90 
91  NavTriangleRawPtr currentTrianglerRawPtr;
92 
93  while (!m_openNodes.IsEmpty())
94  {
95  m_openNodes.Front(currentTrianglerRawPtr);
96  m_openNodes.PopFront();
97 
98  m_visitor->Visit(currentTrianglerRawPtr, m_triangleStatus);
99 
100  if (doesStoreVisited)
101  {
102  if (m_visitedNodes->PushBack(currentTrianglerRawPtr) == KY_ERROR)
103  return TraversalResult_LACK_OF_MEMORY_FOR_VISITED_NODES;
104  }
105 
106  if (m_visitor->IsSearchFinished())
107  return TraversalResult_DONE;
108 
109  if (m_visitor->ShouldVisitNeighborTriangle(currentTrianglerRawPtr, 0))
110  {
111  const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentTrianglerRawPtr, 0));
112  if (rc != TraversalResult_DONE)
113  return rc;
114  }
115 
116  if (m_visitor->ShouldVisitNeighborTriangle(currentTrianglerRawPtr, 1))
117  {
118  const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentTrianglerRawPtr, 1));
119  if (rc != TraversalResult_DONE)
120  return rc;
121  }
122 
123  if (m_visitor->ShouldVisitNeighborTriangle(currentTrianglerRawPtr, 2))
124  {
125  const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentTrianglerRawPtr, 2));
126  if (rc != TraversalResult_DONE)
127  return rc;
128  }
129  }
130 
131  return TraversalResult_DONE;
132 }
133 
134 template <class Visitor>
135 TraversalResult BreadthFirstSearchTraversal<Visitor>::AddTriangleIfNeverEncountered(const NavTriangleRawPtr& triangleRawPtr)
136 {
137  bool nodeIsNew;
138  TraversalResult result = m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, nodeIsNew);
139  if (result != TraversalResult_DONE)
140  return result;
141 
142  if (nodeIsNew && m_openNodes.PushBack(triangleRawPtr) == KY_ERROR)
143  return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
144 
145  return TraversalResult_DONE;
146 }
147 
148 }
149 
150 
2d axis aligned box of 32bits integers. Very Important: CountX() returns m_max.x - m_min...
Definition: box2i.h:17
This class gathers all the navigation data that are currently active in a Database.
Definition: activedata.h:22
The template parameter Visitor must have following methods: void Visit(const NavTrianglePtr& triangle...
Definition: breadthfirstsearchtraversal.h:29
Database * m_database
The Database taken into account by queries made through this object. Do not modify.
Definition: queryutils.h:94
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
#define KY_ERROR
use result == KY_ERROR to test for error
Definition: types.h:132
Identifies a single NavTriangle in a NavFloor.
Definition: navtrianglerawptr.h:21
This class is an helper used internally by the Queries to factorize Code that is used in many Queries...
Definition: queryutils.h:28