12 #ifndef Navigation_BestFirstSearchTraversal_H
13 #define Navigation_BestFirstSearchTraversal_H
25 class NavMeshElementBlob;
45 template <
class Visitor>
46 class BestFirstSearchTraversal
51 BestFirstSearchTraversal(QueryUtils& queryUtils, const
CellBox& cellBox, Visitor& visitor) :
52 m_activeData(queryUtils.m_database->GetActiveData()),
54 m_openNodes(queryUtils.GetWorkingMemory()),
55 m_triangleStatus(queryUtils.GetWorkingMemory(), cellBox),
58 KY_INLINE
void Clear()
61 m_triangleStatus.MakeEmpty();
64 KY_INLINE
bool IsInitialized()
const {
return m_openNodes.IsInitialized() && m_triangleStatus.IsInitialized(); }
66 TraversalResult SetStartTriangle(
const NavTriangleRawPtr& trianglePtr);
67 TraversalResult Search();
69 KY_INLINE
void SetVisitedNodeContainer(WorkingMemArray<NavTriangleRawPtr>* visitedNodes) { m_visitedNodes = visitedNodes; }
72 TraversalResult AddTriangleIfNeverEncountered(
const NavTriangleRawPtr& node);
73 PropagationNode createNode(
const NavTriangleRawPtr& node);
76 ActiveData* m_activeData;
80 WorkingMemBinaryHeap<PropagationNode> m_openNodes;
82 TriangleStatusInGrid m_triangleStatus;
83 WorkingMemArray<NavTriangleRawPtr>* m_visitedNodes;
87 template <
class Visitor>
88 TraversalResult BestFirstSearchTraversal<Visitor>::SetStartTriangle(
const NavTriangleRawPtr& triangleRawPtr)
90 if (m_visitor->ShouldVisitTriangle(triangleRawPtr) ==
false)
91 return TraversalResult_DONE;
93 if (m_openNodes.IsFull() ==
false)
95 m_openNodes.Insert(PropagationNode(triangleRawPtr));
98 if (m_triangleStatus.IsInitialized() ==
false)
99 return TraversalResult_LACK_OF_MEMORY_FOR_CLOSED_NODES;
101 return m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, unused);
104 return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
107 template <
class Visitor>
108 TraversalResult BestFirstSearchTraversal<Visitor>::Search()
110 bool doesStoreVisited = m_visitedNodes !=
KY_NULL;
114 PropagationNode currentNode;
116 while (!m_openNodes.IsEmpty())
118 m_openNodes.ExtractFirst(currentNode);
120 m_visitor->Visit(currentNode.m_triangleRawPtr, currentNode.m_cost, m_triangleStatus);
122 if (doesStoreVisited)
124 if (
KY_FAILED(m_visitedNodes->PushBack(currentNode.m_triangleRawPtr)))
125 return TraversalResult_LACK_OF_MEMORY_FOR_VISITED_NODES;
128 if (m_visitor->IsSearchFinished())
129 return TraversalResult_DONE;
131 if (m_visitor->ShouldVisitNeighborTriangle(currentNode.m_triangleRawPtr, 0))
133 const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentNode.m_triangleRawPtr, 0));
134 if (rc != TraversalResult_DONE)
138 if (m_visitor->ShouldVisitNeighborTriangle(currentNode.m_triangleRawPtr, 1))
140 const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentNode.m_triangleRawPtr, 1));
141 if (rc != TraversalResult_DONE)
145 if (m_visitor->ShouldVisitNeighborTriangle(currentNode.m_triangleRawPtr, 2))
147 const TraversalResult rc = AddTriangleIfNeverEncountered(m_visitor->GetNeighborTriangle(currentNode.m_triangleRawPtr, 2));
148 if (rc != TraversalResult_DONE)
153 return TraversalResult_DONE;
156 template <
class Visitor>
157 TraversalResult BestFirstSearchTraversal<Visitor>::AddTriangleIfNeverEncountered(
const NavTriangleRawPtr& triangleRawPtr)
160 TraversalResult result = m_triangleStatus.OpenNodeIfNew(*m_activeData, triangleRawPtr, nodeIsNew);
161 if (result != TraversalResult_DONE)
166 if (m_openNodes.IsFull())
167 return TraversalResult_LACK_OF_MEMORY_FOR_OPEN_NODES;
169 m_openNodes.Insert(createNode(triangleRawPtr));
172 return TraversalResult_DONE;
175 template <
class Visitor>
176 PropagationNode BestFirstSearchTraversal<Visitor>::createNode(
const NavTriangleRawPtr& triangleRawPtr)
178 PropagationNode node(triangleRawPtr);
179 m_visitor->ComputeTriangleCost(triangleRawPtr, node.m_cost);
187 #endif // Navigation_BestFirstSearchTraversal_H
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