19 class NavMeshElementBlob;
28 template <
class Visitor>
36 m_activeData(queryUtils.
m_database->GetActiveData()),
38 m_openNodes(queryUtils.GetWorkingMemory()),
39 m_triangleStatus(queryUtils.GetWorkingMemory(), cellBox),
40 m_visitedNodes(
nullptr) {}
42 KY_INLINE
void Clear()
44 m_openNodes.MakeEmpty();
45 m_triangleStatus.MakeEmpty();
48 KY_INLINE
bool IsInitialized()
const {
return m_openNodes.IsInitialized() && m_triangleStatus.IsInitialized(); }
53 TraversalResult AddTriangleIfNeverEncountered(
const NavTriangleRawPtr& triangleRawPtr);
55 TraversalResult Search();
57 KY_INLINE
void SetVisitedNodeContainer(WorkingMemArray<NavTriangleRawPtr>* visitedNodes) { m_visitedNodes = visitedNodes; }
64 WorkingMemDeque<NavTriangleRawPtr> m_openNodes;
66 TriangleStatusInGrid m_triangleStatus;
67 WorkingMemArray<NavTriangleRawPtr>* m_visitedNodes;
70 template <
class Visitor>
73 if (m_visitor->ShouldVisitTriangle(triangleRawPtr) ==
false)
74 return TraversalResult_DONE;
76 if (m_openNodes.PushBack(triangleRawPtr) ==
KY_ERROR)
77 return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
80 if (m_triangleStatus.IsInitialized() ==
false)
81 return TraversalResult_LACK_OF_MEMORY_FOR_CLOSED_NODES;
83 return m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, unused);
86 template <
class Visitor>
87 TraversalResult BreadthFirstSearchTraversal<Visitor>::Search()
89 bool doesStoreVisited = m_visitedNodes !=
nullptr;
91 NavTriangleRawPtr currentTrianglerRawPtr;
93 while (!m_openNodes.IsEmpty())
95 m_openNodes.Front(currentTrianglerRawPtr);
96 m_openNodes.PopFront();
98 m_visitor->Visit(currentTrianglerRawPtr, m_triangleStatus);
100 if (doesStoreVisited)
102 if (m_visitedNodes->PushBack(currentTrianglerRawPtr) ==
KY_ERROR)
103 return TraversalResult_LACK_OF_MEMORY_FOR_VISITED_NODES;
106 if (m_visitor->IsSearchFinished())
107 return TraversalResult_DONE;
109 if (m_visitor->ShouldVisitNeighborTriangle(currentTrianglerRawPtr, 0))
111 const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentTrianglerRawPtr, 0));
112 if (rc != TraversalResult_DONE)
116 if (m_visitor->ShouldVisitNeighborTriangle(currentTrianglerRawPtr, 1))
118 const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentTrianglerRawPtr, 1));
119 if (rc != TraversalResult_DONE)
123 if (m_visitor->ShouldVisitNeighborTriangle(currentTrianglerRawPtr, 2))
125 const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentTrianglerRawPtr, 2));
126 if (rc != TraversalResult_DONE)
131 return TraversalResult_DONE;
134 template <
class Visitor>
135 TraversalResult BreadthFirstSearchTraversal<Visitor>::AddTriangleIfNeverEncountered(
const NavTriangleRawPtr& triangleRawPtr)
138 TraversalResult result = m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, nodeIsNew);
139 if (result != TraversalResult_DONE)
142 if (nodeIsNew && m_openNodes.PushBack(triangleRawPtr) ==
KY_ERROR)
143 return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
145 return TraversalResult_DONE;
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