12 #ifndef Navigation_BestFirstSearch2dBorderCollector_H
13 #define Navigation_BestFirstSearch2dBorderCollector_H
32 template<
class TraverseLogic,
class EdgeIntersector>
33 class BestFirstSearch2dBorderCollector
38 BestFirstSearch2dBorderCollector(
void* traverseLogicUserData, EdgeIntersector& edgeIntersector);
40 bool IsSearchFinished();
42 bool ShouldVisitNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr,
KyUInt32 indexOfNeighborTriangle);
43 bool ShouldVisitTriangle(const NavTriangleRawPtr& triangleRawPtr);
44 void ComputeTriangleCost(const NavTriangleRawPtr& triangleRawPtr,
KyFloat32& cost);
46 NavTriangleRawPtr GetNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr,
KyUInt32 indexOfNeighborTriangle);
48 void Visit(const NavTriangleRawPtr& triangleRawPtr,
KyFloat32 cost, const TriangleStatusInGrid& triangleStatus);
51 EdgeIntersector* m_edgeIntersector;
52 void* m_traverseLogicUserData;
53 bool m_collisionFound;
57 NavHalfEdgeRawPtr m_intersectedHalfEdgeRawPtr;
60 bool m_shouldVisitNeighborTriangle[3];
61 NavTriangleRawPtr m_neighborTriangle[3];
64 template<class TraverseLogic, class EdgeIntersector>
65 KY_INLINE BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::BestFirstSearch2dBorderCollector(
void* traverseLogicUserData, EdgeIntersector& edgeIntersector) :
66 m_edgeIntersector(&edgeIntersector), m_traverseLogicUserData(traverseLogicUserData), m_collisionFound(false),
69 m_shouldVisitNeighborTriangle[0] =
true;
70 m_shouldVisitNeighborTriangle[1] =
true;
71 m_shouldVisitNeighborTriangle[2] =
true;
74 template<
class TraverseLogic,
class EdgeIntersector>
75 KY_INLINE
bool BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::IsSearchFinished() {
return false; }
77 template<
class TraverseLogic,
class EdgeIntersector>
78 KY_INLINE
bool BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::ShouldVisitNeighborTriangle(
const NavTriangleRawPtr& ,
KyUInt32 indexOfNeighborTriangle)
80 return m_shouldVisitNeighborTriangle[indexOfNeighborTriangle];
83 template<
class TraverseLogic,
class EdgeIntersector>
84 KY_INLINE
bool BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::ShouldVisitTriangle(
const NavTriangleRawPtr& ) {
return true; }
86 template<
class TraverseLogic,
class EdgeIntersector>
87 KY_INLINE NavTriangleRawPtr BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::GetNeighborTriangle(
const NavTriangleRawPtr& ,
KyUInt32 indexOfNeighborTriangle)
89 return m_neighborTriangle[indexOfNeighborTriangle];
92 template<
class TraverseLogic,
class EdgeIntersector>
93 void BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::ComputeTriangleCost(
const NavTriangleRawPtr& triangleRawPtr,
KyFloat32& cost)
96 triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
97 m_edgeIntersector->ComputeTriangleCost(v0, v1, v2, cost);
100 template<
class TraverseLogic,
class EdgeIntersector>
101 void BestFirstSearch2dBorderCollector<TraverseLogic, EdgeIntersector>::Visit(
const NavTriangleRawPtr& triangleRawPtr,
const KyFloat32 ,
102 const TriangleStatusInGrid& triangleStatus)
105 CoordPos64* vertex[4] = { &v0, &v1, &v2, &v0};
106 NavHalfEdgeRawPtr halfEdgeRawPtr[3];
107 NavHalfEdge halfEdge[3];
108 bool isACrossableEdges[3];
109 bool isVisibleEdges[3];
110 bool neighborTriangleAlreadyVisited[3];
113 NavFloor* navFloor = triangleRawPtr.GetNavFloor();
116 halfEdgeRawPtr[i].Set(navFloor, firstNavHalfEdgeIdx + i);
118 triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
120 const NavFloorBlob& navFloorBlob = *navFloor->GetNavFloorBlob();
121 const NavHalfEdge* m_navHalfEdges = navFloorBlob.m_navHalfEdges.GetValues();
124 halfEdge[i] = m_navHalfEdges[firstNavHalfEdgeIdx + i];
126 NavHalfEdgeRawPtr pairHalfEdgeRawPtr;
129 isACrossableEdges[i] = halfEdgeRawPtr[i].IsHalfEdgeCrossable<TraverseLogic>(m_traverseLogicUserData, halfEdge[i], &navFloorBlob, pairHalfEdgeRawPtr);
130 if (isACrossableEdges[i])
136 neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen_Unsafe(m_neighborTriangle[i]);
138 neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen(m_neighborTriangle[i]);
142 neighborTriangleAlreadyVisited[i] =
false;
147 isVisibleEdges[i] = neighborTriangleAlreadyVisited[i] || m_edgeIntersector->IsEdgeVisible(*vertex[i], *vertex[i+1], halfEdgeRawPtr[i], isACrossableEdges[i]);
151 m_shouldVisitNeighborTriangle[i] = neighborTriangleAlreadyVisited[i]==
false && isVisibleEdges[i] && isACrossableEdges[i];
158 #endif //Navigation_BestFirstSearch2dBorderCollector_H
#define KyFloat32MAXVAL
The maximum value that can be stored in the KyFloat32 variable type.
Definition: types.h:227
KyUInt32 NavHalfEdgeIdx
An index that uniquely identifies a single edge of a triangle within the set of edges owned by a NavF...
Definition: navmeshtypes.h:87
Indicates that another NavHalfEdge in the same NavFloor but in different Connex lies adjacent to the ...
Definition: navmeshtypes.h:60
static NavHalfEdgeIdx NavTriangleIdxToFirstNavHalfEdgeIdx(NavTriangleIdx idx)
Retrieves the first NavHalfEdgeIdx of NavTriangle specified by the input NavTriangleIdx.
Definition: navfloorblob.inl:26
Vec2LL CoordPos64
A type that represents the position of a point within the 2D integer grid.
Definition: navmeshtypes.h:19
Definition: gamekitcrowddispersion.h:20
static NavTriangleIdx NavHalfEdgeIdxToTriangleIdx(NavHalfEdgeIdx idx)
Retrieves the index of the triangle that contains the edge specified the input NavHalfEdgeIdx.
Definition: navfloorblob.inl:25
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
Indicates that another NavHalfEdge in the same Connex lies adjacent to the NavHalfEdge.
Definition: navmeshtypes.h:61
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36
float KyFloat32
Type used internally to represent a 32-bit floating-point number.
Definition: types.h:43