12 #ifndef Navigation_BreadthFirstSearchEdgeCollisionVisitor_H
13 #define Navigation_BreadthFirstSearchEdgeCollisionVisitor_H
27 template<
class TraverseLogic,
class EdgeIntersector>
28 class BreadthFirstSearchEdgeCollisionVisitor
33 BreadthFirstSearchEdgeCollisionVisitor(
void* traverseLogicUserData, EdgeIntersector& edgeIntersector);
35 bool IsSearchFinished();
36 bool ShouldVisitNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr,
KyUInt32 indexOfNeighborTriangle);
37 bool ShouldVisitTriangle(const NavTriangleRawPtr& triangleRawPtr);
39 NavTriangleRawPtr GetNeighborTriangle(const NavTriangleRawPtr& triangleRawPtr,
KyUInt32 indexOfNeighborTriangle);
41 void Visit(const NavTriangleRawPtr& triangleRawPtr, const TriangleStatusInGrid& triangleStatus);
44 EdgeIntersector* m_edgeIntersector;
45 void* m_traverseLogicUserData;
46 bool m_collisionFound;
49 bool m_shouldVisitNeighborTriangle[3];
50 NavTriangleRawPtr m_neighborTriangle[3];
53 template<class TraverseLogic, class EdgeIntersector>
54 KY_INLINE BreadthFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::
55 BreadthFirstSearchEdgeCollisionVisitor(
void* traverseLogicUserData, EdgeIntersector& edgeIntersector) :
56 m_edgeIntersector(&edgeIntersector),
57 m_traverseLogicUserData(traverseLogicUserData),
58 m_collisionFound(false)
60 m_shouldVisitNeighborTriangle[0] =
true;
61 m_shouldVisitNeighborTriangle[1] =
true;
62 m_shouldVisitNeighborTriangle[2] =
true;
65 template<
class TraverseLogic,
class EdgeIntersector>
66 KY_INLINE
bool BreadthFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::IsSearchFinished() {
return m_collisionFound; }
67 template<
class TraverseLogic,
class EdgeIntersector>
68 KY_INLINE
bool BreadthFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::ShouldVisitNeighborTriangle(
const NavTriangleRawPtr& ,
KyUInt32 indexOfNeighborTriangle)
70 return m_shouldVisitNeighborTriangle[indexOfNeighborTriangle];
73 template<
class TraverseLogic,
class EdgeIntersector>
74 KY_INLINE
bool BreadthFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::ShouldVisitTriangle(
const NavTriangleRawPtr& ) {
return true; }
75 template<
class TraverseLogic,
class EdgeIntersector>
76 KY_INLINE NavTriangleRawPtr BreadthFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::GetNeighborTriangle(
const NavTriangleRawPtr& ,
KyUInt32 indexOfNeighborTriangle)
78 return m_neighborTriangle[indexOfNeighborTriangle];
81 template<
class TraverseLogic,
class EdgeIntersector>
82 void BreadthFirstSearchEdgeCollisionVisitor<TraverseLogic, EdgeIntersector>::Visit(
const NavTriangleRawPtr& triangleRawPtr,
83 const TriangleStatusInGrid& triangleStatus)
87 NavHalfEdgeRawPtr halfEdgeRawPtr[3];
88 NavHalfEdge halfEdge[3];
89 bool isACrossableEdges[3];
90 bool neighborTriangleAlreadyVisited[3];
91 bool doesIntersectsEdges[3];
94 NavFloor* navFloor = triangleRawPtr.GetNavFloor();
97 halfEdgeRawPtr[i].Set(navFloor, firstNavHalfEdgeIdx + i);
99 triangleRawPtr.GetVerticesCoordPos64(v0, v1, v2);
101 const NavFloorBlob& navFloorBlob = *navFloor->GetNavFloorBlob();
102 const NavHalfEdge* m_navHalfEdges = navFloorBlob.m_navHalfEdges.GetValues();
105 halfEdge[i] = m_navHalfEdges[firstNavHalfEdgeIdx + i];
109 NavHalfEdgeRawPtr pairHalfEdgeRawPtr;
110 isACrossableEdges[i] = halfEdgeRawPtr[i].IsHalfEdgeCrossable<TraverseLogic>(m_traverseLogicUserData, halfEdge[i], &navFloorBlob, pairHalfEdgeRawPtr);
112 if (isACrossableEdges[i])
118 neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen_Unsafe(m_neighborTriangle[i]);
120 neighborTriangleAlreadyVisited[i] = triangleStatus.IsTriangleOpen(m_neighborTriangle[i]);
124 neighborTriangleAlreadyVisited[i] =
false;
129 doesIntersectsEdges[i] = neighborTriangleAlreadyVisited[i] || m_edgeIntersector->DoesIntersectEdge(*vertex[i], *vertex[i+1]);
132 (isACrossableEdges[0] ==
false && doesIntersectsEdges[0]) ||
133 (isACrossableEdges[1] ==
false && doesIntersectsEdges[1]) ||
134 (isACrossableEdges[2] ==
false && doesIntersectsEdges[2]);
137 m_shouldVisitNeighborTriangle[i] = isACrossableEdges[i] && neighborTriangleAlreadyVisited[i] ==
false && doesIntersectsEdges[i];
143 #endif //Navigation_BreadthFirstSearchEdgeCollisionVisitor_H
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