1//
2// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
3//
4// This software is provided 'as-is', without any express or implied
5// warranty. In no event will the authors be held liable for any damages
6// arising from the use of this software.
7// Permission is granted to anyone to use this software for any purpose,
8// including commercial applications, and to alter it and redistribute it
9// freely, subject to the following restrictions:
10// 1. The origin of this software must not be misrepresented; you must not
11// claim that you wrote the original software. If you use this software
12// in a product, an acknowledgment in the product documentation would be
13// appreciated but is not required.
14// 2. Altered source versions must be plainly marked as such, and must not be
15// misrepresented as being the original software.
16// 3. This notice may not be removed or altered from any source distribution.
17//
18
19#include "Recast.h"
20#include "RecastAssert.h"
21
22#include <stdlib.h>
23
24void rcFilterLowHangingWalkableObstacles(rcContext* context, const int walkableClimb, rcHeightfield& heightfield)
25{
26 rcAssert(context);
27
28 rcScopedTimer timer(context, RC_TIMER_FILTER_LOW_OBSTACLES);
29
30 const int xSize = heightfield.width;
31 const int zSize = heightfield.height;
32
33 for (int z = 0; z < zSize; ++z)
34 {
35 for (int x = 0; x < xSize; ++x)
36 {
37 rcSpan* previousSpan = NULL;
38 bool previousWasWalkable = false;
39 unsigned char previousArea = RC_NULL_AREA;
40
41 for (rcSpan* span = heightfield.spans[x + z * xSize]; span != NULL; previousSpan = span, span = span->next)
42 {
43 const bool walkable = span->area != RC_NULL_AREA;
44 // If current span is not walkable, but there is walkable
45 // span just below it, mark the span above it walkable too.
46 if (!walkable && previousWasWalkable)
47 {
48 if (rcAbs((int)span->smax - (int)previousSpan->smax) <= walkableClimb)
49 {
50 span->area = previousArea;
51 }
52 }
53 // Copy walkable flag so that it cannot propagate
54 // past multiple non-walkable objects.
55 previousWasWalkable = walkable;
56 previousArea = span->area;
57 }
58 }
59 }
60}
61
62void rcFilterLedgeSpans(rcContext* context, const int walkableHeight, const int walkableClimb,
63 rcHeightfield& heightfield)
64{
65 rcAssert(context);
66
67 rcScopedTimer timer(context, RC_TIMER_FILTER_BORDER);
68
69 const int xSize = heightfield.width;
70 const int zSize = heightfield.height;
71 const int MAX_HEIGHT = 0xffff; // TODO (graham): Move this to a more visible constant and update usages.
72
73 // Mark border spans.
74 for (int z = 0; z < zSize; ++z)
75 {
76 for (int x = 0; x < xSize; ++x)
77 {
78 for (rcSpan* span = heightfield.spans[x + z * xSize]; span; span = span->next)
79 {
80 // Skip non walkable spans.
81 if (span->area == RC_NULL_AREA)
82 {
83 continue;
84 }
85
86 const int bot = (int)(span->smax);
87 const int top = span->next ? (int)(span->next->smin) : MAX_HEIGHT;
88
89 // Find neighbours minimum height.
90 int minNeighborHeight = MAX_HEIGHT;
91
92 // Min and max height of accessible neighbours.
93 int accessibleNeighborMinHeight = span->smax;
94 int accessibleNeighborMaxHeight = span->smax;
95
96 for (int direction = 0; direction < 4; ++direction)
97 {
98 int dx = x + rcGetDirOffsetX(direction);
99 int dy = z + rcGetDirOffsetY(direction);
100 // Skip neighbours which are out of bounds.
101 if (dx < 0 || dy < 0 || dx >= xSize || dy >= zSize)
102 {
103 minNeighborHeight = rcMin(minNeighborHeight, -walkableClimb - bot);
104 continue;
105 }
106
107 // From minus infinity to the first span.
108 const rcSpan* neighborSpan = heightfield.spans[dx + dy * xSize];
109 int neighborBot = -walkableClimb;
110 int neighborTop = neighborSpan ? (int)neighborSpan->smin : MAX_HEIGHT;
111
112 // Skip neighbour if the gap between the spans is too small.
113 if (rcMin(top, neighborTop) - rcMax(bot, neighborBot) > walkableHeight)
114 {
115 minNeighborHeight = rcMin(minNeighborHeight, neighborBot - bot);
116 }
117
118 // Rest of the spans.
119 for (neighborSpan = heightfield.spans[dx + dy * xSize]; neighborSpan; neighborSpan = neighborSpan->next)
120 {
121 neighborBot = (int)neighborSpan->smax;
122 neighborTop = neighborSpan->next ? (int)neighborSpan->next->smin : MAX_HEIGHT;
123
124 // Skip neighbour if the gap between the spans is too small.
125 if (rcMin(top, neighborTop) - rcMax(bot, neighborBot) > walkableHeight)
126 {
127 minNeighborHeight = rcMin(minNeighborHeight, neighborBot - bot);
128
129 // Find min/max accessible neighbour height.
130 if (rcAbs(neighborBot - bot) <= walkableClimb)
131 {
132 if (neighborBot < accessibleNeighborMinHeight) accessibleNeighborMinHeight = neighborBot;
133 if (neighborBot > accessibleNeighborMaxHeight) accessibleNeighborMaxHeight = neighborBot;
134 }
135
136 }
137 }
138 }
139
140 // The current span is close to a ledge if the drop to any
141 // neighbour span is less than the walkableClimb.
142 if (minNeighborHeight < -walkableClimb)
143 {
144 span->area = RC_NULL_AREA;
145 }
146 // If the difference between all neighbours is too large,
147 // we are at steep slope, mark the span as ledge.
148 else if ((accessibleNeighborMaxHeight - accessibleNeighborMinHeight) > walkableClimb)
149 {
150 span->area = RC_NULL_AREA;
151 }
152 }
153 }
154 }
155}
156
157void rcFilterWalkableLowHeightSpans(rcContext* context, const int walkableHeight, rcHeightfield& heightfield)
158{
159 rcAssert(context);
160
161 rcScopedTimer timer(context, RC_TIMER_FILTER_WALKABLE);
162
163 const int xSize = heightfield.width;
164 const int zSize = heightfield.height;
165 const int MAX_HEIGHT = 0xffff;
166
167 // Remove walkable flag from spans which do not have enough
168 // space above them for the agent to stand there.
169 for (int z = 0; z < zSize; ++z)
170 {
171 for (int x = 0; x < xSize; ++x)
172 {
173 for (rcSpan* span = heightfield.spans[x + z*xSize]; span; span = span->next)
174 {
175 const int bot = (int)(span->smax);
176 const int top = span->next ? (int)(span->next->smin) : MAX_HEIGHT;
177 if ((top - bot) < walkableHeight)
178 {
179 span->area = RC_NULL_AREA;
180 }
181 }
182 }
183 }
184}
185