10 #ifndef GwNavGen_ConnectedPattern_H
11 #define GwNavGen_ConnectedPattern_H
21 static const KyUInt32 MaxVertexEdgeLinkCount = 8;
28 enum EdgeInOrOut { EDGE_IN = 0, EDGE_OUT = 1 };
30 void Init(EdgeInOrOut edgeInOrOut, BoundaryEdge* edge)
33 m_edgeInOrOut = edgeInOrOut;
34 m_vertexIdxInEdge = (edgeInOrOut == EDGE_IN) ? 1 : 0;
37 void Apply(BoundaryVertex* center)
39 m_edge->m_vertex[m_vertexIdxInEdge] = center;
40 KY_ASSERT(m_edge->m_orientation < 4);
41 if (m_edgeInOrOut == EDGE_OUT)
42 center->m_outs[m_edge->m_orientation] = m_edge;
44 center->m_ins[m_edge->m_orientation] = m_edge;
48 EdgeInOrOut m_edgeInOrOut;
59 void Setup(BoundaryPixel* boundaryPixel,
KyUInt32 pixelIdxInSquare,
bool isOutsideCellBox)
61 m_boundaryPixel = boundaryPixel;
64 m_pixelIdxInSquare = pixelIdxInSquare;
65 m_isInPattern =
false;
66 m_isOutsideCellBox = isOutsideCellBox;
84 void PushVertexEdgeLinks(VertexEdgeLink* vertexEdgeLinks,
KyUInt32& vertexEdgeLinksCount)
const
87 CardinalDir edgeOut_IdxInPixel = GetNextCardinalDir_CCW(edgeIn_IdxInPixel);
89 BoundaryEdge* edgeIn = m_boundaryPixel->m_edges[edgeIn_IdxInPixel];
92 KY_ASSERT(vertexEdgeLinksCount < MaxVertexEdgeLinkCount);
93 VertexEdgeLink& link = vertexEdgeLinks[vertexEdgeLinksCount++];
94 link.Init(VertexEdgeLink::EDGE_IN, edgeIn);
97 BoundaryEdge* edgeOut = m_boundaryPixel->m_edges[edgeOut_IdxInPixel];
100 KY_ASSERT(vertexEdgeLinksCount < MaxVertexEdgeLinkCount);
101 VertexEdgeLink& link = vertexEdgeLinks[vertexEdgeLinksCount++];
102 link.Init(VertexEdgeLink::EDGE_OUT, edgeOut);
106 BoundaryPixel* m_boundaryPixel;
107 SquarePixel* m_connected[2];
110 bool m_isOutsideCellBox;
114 class SquarePixelColumn
118 SquarePixelColumn(
KyUInt32 squarePixelsCapacityAtInit = 50)
120 if (squarePixelsCapacityAtInit == 0)
121 squarePixelsCapacityAtInit = 50;
122 m_squarePixels.Resize(squarePixelsCapacityAtInit);
125 ~SquarePixelColumn() {}
127 void Setup(
KyUInt32 idxInSquare,
const NavBoundaryPos& pos,
const BoxOfArrays<BoundaryPixel>::Column& boundaryPixelColumn,
bool isOutsideNavBox)
130 m_squarePixels.Clear();
131 m_squarePixels.Resize(boundaryPixelColumn.m_count);
132 for (NavRasterFloorIdx floorIdx = 0; floorIdx < boundaryPixelColumn.m_count; ++floorIdx)
133 m_squarePixels[floorIdx].Setup(&boundaryPixelColumn.m_values[floorIdx], idxInSquare, isOutsideNavBox);
137 KyArrayTLS_POD<SquarePixel> m_squarePixels;
141 class ConnectionSquare
145 KY_INLINE
void SetupSquarePixelColumn(
KyUInt32 idxInSquare, const NavBoundaryPos& pos, const BoxOfArrays<BoundaryPixel>::Column& boundaryPixelColumn,
bool isOutsideNavBox)
147 m_columns[idxInSquare].Setup(idxInSquare, pos, boundaryPixelColumn, isOutsideNavBox);
150 SquarePixelColumn m_columns[4];
154 class ConnectedPattern
158 enum { CCW = 0, CW = 1 };
160 ConnectedPattern() : m_count(0)
166 void Init(SquarePixel* firstSquarePixel)
169 firstSquarePixel->m_isInPattern =
true;
170 m_pixels[0] = firstSquarePixel;
176 SquarePixel* squarePixel = firstSquarePixel;
179 squarePixel = squarePixel->m_connected[i];
180 if (squarePixel ==
KY_NULL || squarePixel->m_isInPattern ==
true)
182 squarePixel->m_isInPattern =
true;
184 m_pixels[m_count] = squarePixel;
192 KY_ASSERT(m_count != 0);
193 static const KyFloat32 florCountInv[4] = { 1.f, 0.5f, 0.333333333333f, 0.25f };
196 for (
KyUInt32 i = 0; i < m_count; ++i)
198 KY_ASSERT(m_pixels[i] !=
KY_NULL);
199 altitude += m_pixels[i]->m_boundaryPixel->m_navRasterPixel->m_altitude;
201 altitude *= florCountInv[m_count-1];
205 bool IsFullyOutsideCellBox()
207 KY_ASSERT(m_count != 0);
208 for (
KyUInt32 i = 0; i < m_count; ++i)
210 if (m_pixels[i]->m_isOutsideCellBox ==
false)
218 bool isBlocked[4] = {
false,
false,
false,
false };
219 bool isDeadEnd[4] = {
false,
false,
false,
false };
220 for (
KyUInt32 pixelIdx = 0; pixelIdx < m_count; ++pixelIdx)
222 SquarePixel* squarePixel = m_pixels[pixelIdx];
223 KY_ASSERT(squarePixel !=
KY_NULL);
225 BoundaryPixel* boundaryPixel = squarePixel->m_boundaryPixel;
226 KY_ASSERT(boundaryPixel !=
KY_NULL);
232 const BoundaryEdge* edges[4] =
234 boundaryPixel->m_edges[ dir ],
235 boundaryPixel->m_edges[(dir+1)%4],
236 boundaryPixel->m_edges[(dir+2)%4],
237 boundaryPixel->m_edges[(dir+3)%4]
242 isDeadEnd[pixelIdx] =
true;
250 if (isDeadEnd[pixelIdx] ==
false)
258 if (squarePixel->m_boundaryPixel->m_edges[ dir ] !=
KY_NULL &&
274 KyUInt32 rightEdgeIdx = (squarePixel->m_pixelIdxInSquare + 2) % 4;
275 KyUInt32 upEdgeIdx = (squarePixel->m_pixelIdxInSquare + 3) % 4;
276 KyUInt32 rightVtxIdx = (squarePixel->m_pixelIdxInSquare + 3) % 4;
277 KyUInt32 upVtxIdx = (squarePixel->m_pixelIdxInSquare);
279 if (isBlocked[rightVtxIdx] ==
false && squarePixel->m_boundaryPixel->m_edges[rightEdgeIdx])
280 isBlocked[rightVtxIdx] =
true;
282 if (isBlocked[upVtxIdx] ==
false && squarePixel->m_boundaryPixel->m_edges[upEdgeIdx])
283 isBlocked[upVtxIdx] =
true;
293 if (isDeadEnd[j] && isDeadEnd[(j+1)%4])
298 for (
KyUInt32 pixelIdx = 0; pixelIdx < m_count; ++pixelIdx)
300 if (isDeadEnd[pixelIdx])
303 SquarePixel* squarePixel = m_pixels[pixelIdx];
304 KY_ASSERT(squarePixel !=
KY_NULL);
306 SquarePixel* neighborCCW = squarePixel->m_connected[CCW];
309 KyUInt32 ccwVtxIdx = (squarePixel->m_pixelIdxInSquare);
310 if (isBlocked[ccwVtxIdx] &&
311 neighborCCW->m_boundaryPixel->m_floorColor == squarePixel->m_boundaryPixel->m_floorColor &&
312 neighborCCW->m_boundaryPixel->m_connexIdx == squarePixel->m_boundaryPixel->m_connexIdx )
316 SquarePixel* neighborCW = squarePixel->m_connected[CW];
319 KyUInt32 cwVtxIdx = (squarePixel->m_pixelIdxInSquare + 3) % 4;
320 if (isBlocked[cwVtxIdx] &&
321 neighborCW->m_boundaryPixel->m_floorColor == squarePixel->m_boundaryPixel->m_floorColor &&
322 neighborCW->m_boundaryPixel->m_connexIdx == squarePixel->m_boundaryPixel->m_connexIdx )
330 SquarePixel* m_pixels[4];
CardinalDir GetOppositeCardinalDir(const CardinalDir dir)
Returns the CardinalDir that lies in the opposite direction from the specified CardinalDir.
Definition: cardinaldir.h:35
#define KY_NULL
Null value.
Definition: types.h:247
KyUInt32 CardinalDir
Defines a type that refers to one of the cardinal points on the compass:
Definition: cardinaldir.h:23
Definition: gamekitcrowddispersion.h:20
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:137
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