summary refs log tree commit diff stats
path: root/vendor/fov.c
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/fov.c')
-rw-r--r--vendor/fov.c427
1 files changed, 427 insertions, 0 deletions
diff --git a/vendor/fov.c b/vendor/fov.c new file mode 100644 index 0000000..74ed5c8 --- /dev/null +++ b/vendor/fov.c
@@ -0,0 +1,427 @@
1/*
2 * Copyright (C) 2006, Greg McIntyre
3 * All rights reserved. See the file named COPYING in the distribution
4 * for more details.
5 */
6
7#include <stdlib.h>
8#include <string.h>
9#include <stdio.h>
10#define __USE_ISOC99 1
11#include <math.h>
12#include <float.h>
13#include <assert.h>
14#include "fov.h"
15
16/*
17+---++---++---++---+
18| || || || |
19| || || || |
20| || || || |
21+---++---++---++---+ 2
22+---++---++---+#####
23| || || |#####
24| || || |#####
25| || || |#####
26+---++---++---+#####X 1 <-- y
27+---++---++---++---+
28| || || || |
29| @ || || || | <-- srcy centre -> dy = 0.5 = y - 0.5
30| || || || |
31+---++---++---++---+ 0
320 1 2 3 4
33 ^ ^
34 | |
35 srcx x -> dx = 3.5 = x + 0.5
36centre
37
38Slope from @ to X.
39
40+---++---++---++---+
41| || || || |
42| || || || |
43| || || || |
44+---++---++---++---+ 2
45+---++---++---++---+
46| || || || |
47| || || || |
48| || || || |
49+---++---++---+X---+ 1 <-- y
50+---++---++---+#####
51| || || |#####
52| @ || || |##### <-- srcy centre -> dy = 0.5 = y - 0.5
53| || || |#####
54+---++---++---+##### 0
550 1 2 3
56 ^ ^
57 | |
58 srcx x -> dx = 2.5 = x - 0.5
59centre
60
61Slope from @ to X
62*/
63
64
65/* Types ---------------------------------------------------------- */
66
67/** \cond INTERNAL */
68typedef struct {
69 /*@observer@*/ fov_settings_type *settings;
70 /*@observer@*/ void *map;
71 /*@observer@*/ void *source;
72 int source_x;
73 int source_y;
74 unsigned radius;
75} fov_private_data_type;
76/** \endcond */
77
78/* Options -------------------------------------------------------- */
79
80void fov_settings_init(fov_settings_type *settings) {
81 settings->shape = FOV_SHAPE_CIRCLE_PRECALCULATE;
82 settings->corner_peek = FOV_CORNER_NOPEEK;
83 settings->opaque_apply = FOV_OPAQUE_APPLY;
84 settings->opaque = NULL;
85 settings->apply = NULL;
86 settings->heights = NULL;
87 settings->numheights = 0;
88}
89
90void fov_settings_set_shape(fov_settings_type *settings,
91 fov_shape_type value) {
92 settings->shape = value;
93}
94
95void fov_settings_set_corner_peek(fov_settings_type *settings,
96 fov_corner_peek_type value) {
97 settings->corner_peek = value;
98}
99
100void fov_settings_set_opaque_apply(fov_settings_type *settings,
101 fov_opaque_apply_type value) {
102 settings->opaque_apply = value;
103}
104
105void fov_settings_set_opacity_test_function(fov_settings_type *settings,
106 bool (*f)(void *map,
107 int x, int y)) {
108 settings->opaque = f;
109}
110
111void fov_settings_set_apply_lighting_function(fov_settings_type *settings,
112 void (*f)(void *map,
113 int x, int y,
114 int dx, int dy,
115 void *src)) {
116 settings->apply = f;
117}
118
119/* Circular FOV --------------------------------------------------- */
120
121/*@null@*/ static unsigned *precalculate_heights(unsigned maxdist) {
122 unsigned i;
123 unsigned *result = (unsigned *)malloc((maxdist+2)*sizeof(unsigned));
124 if (result) {
125 for (i = 0; i <= maxdist; ++i) {
126 result[i] = (unsigned)sqrtf((float)(maxdist*maxdist - i*i));
127 }
128 result[maxdist+1] = 0;
129 }
130 return result;
131}
132
133static unsigned height(fov_settings_type *settings, int x,
134 unsigned maxdist) {
135 unsigned **newheights;
136
137 if (maxdist > settings->numheights) {
138 newheights = (unsigned **)calloc((size_t)maxdist, sizeof(unsigned*));
139 if (newheights != NULL) {
140 if (settings->heights != NULL && settings->numheights > 0) {
141 /* Copy the pointers to the heights arrays we've already
142 * calculated. Once copied out, we can free the old
143 * array of pointers. */
144 memcpy(newheights, settings->heights,
145 settings->numheights*sizeof(unsigned*));
146 free(settings->heights);
147 }
148 settings->heights = newheights;
149 settings->numheights = maxdist;
150 }
151 }
152 if (settings->heights) {
153 if (settings->heights[maxdist-1] == NULL) {
154 settings->heights[maxdist-1] = precalculate_heights(maxdist);
155 }
156 if (settings->heights[maxdist-1] != NULL) {
157 return settings->heights[maxdist-1][abs(x)];
158 }
159 }
160 return 0;
161}
162
163void fov_settings_free(fov_settings_type *settings) {
164 unsigned i;
165 if (settings != NULL) {
166 if (settings->heights != NULL && settings->numheights > 0) {
167 /*@+forloopexec@*/
168 for (i = 0; i < settings->numheights; ++i) {
169 unsigned *h = settings->heights[i];
170 if (h != NULL) {
171 free(h);
172 }
173 settings->heights[i] = NULL;
174 }
175 /*@=forloopexec@*/
176 free(settings->heights);
177 settings->heights = NULL;
178 settings->numheights = 0;
179 }
180 }
181}
182
183/* Slope ---------------------------------------------------------- */
184
185static float fov_slope(float dx, float dy) {
186 if (dx <= -FLT_EPSILON || dx >= FLT_EPSILON) {
187 return dy/dx;
188 } else {
189 return 0.0;
190 }
191}
192
193/* Octants -------------------------------------------------------- */
194
195#define FOV_DEFINE_OCTANT(signx, signy, rx, ry, nx, ny, nf, apply_edge, apply_diag) \
196 static void fov_octant_##nx##ny##nf( \
197 fov_private_data_type *data, \
198 int dx, \
199 float start_slope, \
200 float end_slope) { \
201 int x, y, dy, dy0, dy1; \
202 unsigned h; \
203 int prev_blocked = -1; \
204 float end_slope_next; \
205 fov_settings_type *settings = data->settings; \
206 \
207 if (dx == 0) { \
208 fov_octant_##nx##ny##nf(data, dx+1, start_slope, end_slope); \
209 return; \
210 } else if ((unsigned)dx > data->radius) { \
211 return; \
212 } \
213 \
214 dy0 = (int)(0.5f + ((float)dx)*start_slope); \
215 dy1 = (int)(0.5f + ((float)dx)*end_slope); \
216 \
217 rx = data->source_##rx signx dx; \
218 ry = data->source_##ry signy dy0; \
219 \
220 if (!apply_diag && dy1 == dx) { \
221 /* We do diagonal lines on every second octant, so they don't get done twice. */ \
222 --dy1; \
223 } \
224 \
225 switch (settings->shape) { \
226 case FOV_SHAPE_CIRCLE_PRECALCULATE: \
227 h = height(settings, dx, data->radius); \
228 break; \
229 case FOV_SHAPE_CIRCLE: \
230 h = (unsigned)sqrtf((float)(data->radius*data->radius - dx*dx)); \
231 break; \
232 case FOV_SHAPE_OCTAGON: \
233 h = (data->radius - dx)<<1; \
234 break; \
235 default: \
236 h = data->radius; \
237 break; \
238 }; \
239 if ((unsigned)dy1 > h) { \
240 if (h == 0) { \
241 return; \
242 } \
243 dy1 = (int)h; \
244 } \
245 \
246 /*fprintf(stderr, "(%2d) = [%2d .. %2d] (%f .. %f), h=%d,edge=%d\n", \
247 dx, dy0, dy1, ((float)dx)*start_slope, \
248 0.5f + ((float)dx)*end_slope, h, apply_edge);*/ \
249 \
250 for (dy = dy0; dy <= dy1; ++dy) { \
251 ry = data->source_##ry signy dy; \
252 \
253 if (settings->opaque(data->map, x, y)) { \
254 if (settings->opaque_apply == FOV_OPAQUE_APPLY && (apply_edge || dy > 0)) { \
255 settings->apply(data->map, x, y, x - data->source_x, y - data->source_y, data->source); \
256 } \
257 if (prev_blocked == 0) { \
258 end_slope_next = fov_slope((float)dx + 0.5f, (float)dy - 0.5f); \
259 fov_octant_##nx##ny##nf(data, dx+1, start_slope, end_slope_next); \
260 } \
261 prev_blocked = 1; \
262 } else { \
263 if (apply_edge || dy > 0) { \
264 settings->apply(data->map, x, y, x - data->source_x, y - data->source_y, data->source); \
265 } \
266 if (prev_blocked == 1) { \
267 start_slope = fov_slope((float)dx - 0.5f, (float)dy - 0.5f); \
268 } \
269 prev_blocked = 0; \
270 } \
271 } \
272 \
273 if (prev_blocked == 0) { \
274 fov_octant_##nx##ny##nf(data, dx+1, start_slope, end_slope); \
275 } \
276 }
277
278FOV_DEFINE_OCTANT(+,+,x,y,p,p,n,true,true)
279FOV_DEFINE_OCTANT(+,+,y,x,p,p,y,true,false)
280FOV_DEFINE_OCTANT(+,-,x,y,p,m,n,false,true)
281FOV_DEFINE_OCTANT(+,-,y,x,p,m,y,false,false)
282FOV_DEFINE_OCTANT(-,+,x,y,m,p,n,true,true)
283FOV_DEFINE_OCTANT(-,+,y,x,m,p,y,true,false)
284FOV_DEFINE_OCTANT(-,-,x,y,m,m,n,false,true)
285FOV_DEFINE_OCTANT(-,-,y,x,m,m,y,false,false)
286
287
288/* Circle --------------------------------------------------------- */
289
290static void _fov_circle(fov_private_data_type *data) {
291 /*
292 * Octants are defined by (x,y,r) where:
293 * x = [p]ositive or [n]egative x increment
294 * y = [p]ositive or [n]egative y increment
295 * r = [y]es or [n]o for reflecting on axis x = y
296 *
297 * \pmy|ppy/
298 * \ | /
299 * \ | /
300 * mpn\|/ppn
301 * ----@----
302 * mmn/|\pmn
303 * / | \
304 * / | \
305 * /mmy|mpy\
306 */
307 fov_octant_ppn(data, 1, (float)0.0f, (float)1.0f);
308 fov_octant_ppy(data, 1, (float)0.0f, (float)1.0f);
309 fov_octant_pmn(data, 1, (float)0.0f, (float)1.0f);
310 fov_octant_pmy(data, 1, (float)0.0f, (float)1.0f);
311 fov_octant_mpn(data, 1, (float)0.0f, (float)1.0f);
312 fov_octant_mpy(data, 1, (float)0.0f, (float)1.0f);
313 fov_octant_mmn(data, 1, (float)0.0f, (float)1.0f);
314 fov_octant_mmy(data, 1, (float)0.0f, (float)1.0f);
315}
316
317void fov_circle(fov_settings_type *settings,
318 void *map,
319 void *source,
320 int source_x,
321 int source_y,
322 unsigned radius) {
323 fov_private_data_type data;
324
325 data.settings = settings;
326 data.map = map;
327 data.source = source;
328 data.source_x = source_x;
329 data.source_y = source_y;
330 data.radius = radius;
331
332 _fov_circle(&data);
333}
334
335/**
336 * Limit x to the range [a, b].
337 */
338static float betweenf(float x, float a, float b) {
339 if (x - a < FLT_EPSILON) { /* x < a */
340 return a;
341 } else if (x - b > FLT_EPSILON) { /* x > b */
342 return b;
343 } else {
344 return x;
345 }
346}
347
348#define BEAM_DIRECTION(d, p1, p2, p3, p4, p5, p6, p7, p8) \
349 if (direction == d) { \
350 end_slope = betweenf(a, 0.0f, 1.0f); \
351 fov_octant_##p1(&data, 1, 0.0f, end_slope); \
352 fov_octant_##p2(&data, 1, 0.0f, end_slope); \
353 if (a - 1.0f > FLT_EPSILON) { /* a > 1.0f */ \
354 start_slope = betweenf(2.0f - a, 0.0f, 1.0f); \
355 fov_octant_##p3(&data, 1, start_slope, 1.0f); \
356 fov_octant_##p4(&data, 1, start_slope, 1.0f); \
357 } \
358 if (a - 2.0f > FLT_EPSILON) { /* a > 2.0f */ \
359 end_slope = betweenf(a - 2.0f, 0.0f, 1.0f); \
360 fov_octant_##p5(&data, 1, 0.0f, end_slope); \
361 fov_octant_##p6(&data, 1, 0.0f, end_slope); \
362 } \
363 if (a - 3.0f > FLT_EPSILON) { /* a > 3.0f */ \
364 start_slope = betweenf(4.0f - a, 0.0f, 1.0f); \
365 fov_octant_##p7(&data, 1, start_slope, 1.0f); \
366 fov_octant_##p8(&data, 1, start_slope, 1.0f); \
367 } \
368 }
369
370#define BEAM_DIRECTION_DIAG(d, p1, p2, p3, p4, p5, p6, p7, p8) \
371 if (direction == d) { \
372 start_slope = betweenf(1.0f - a, 0.0f, 1.0f); \
373 fov_octant_##p1(&data, 1, start_slope, 1.0f); \
374 fov_octant_##p2(&data, 1, start_slope, 1.0f); \
375 if (a - 1.0f > FLT_EPSILON) { /* a > 1.0f */ \
376 end_slope = betweenf(a - 1.0f, 0.0f, 1.0f); \
377 fov_octant_##p3(&data, 1, 0.0f, end_slope); \
378 fov_octant_##p4(&data, 1, 0.0f, end_slope); \
379 } \
380 if (a - 2.0f > FLT_EPSILON) { /* a > 2.0f */ \
381 start_slope = betweenf(3.0f - a, 0.0f, 1.0f); \
382 fov_octant_##p5(&data, 1, start_slope, 1.0f); \
383 fov_octant_##p6(&data, 1, start_slope, 1.0f); \
384 } \
385 if (a - 3.0f > FLT_EPSILON) { /* a > 3.0f */ \
386 end_slope = betweenf(a - 3.0f, 0.0f, 1.0f); \
387 fov_octant_##p7(&data, 1, 0.0f, end_slope); \
388 fov_octant_##p8(&data, 1, 0.0f, end_slope); \
389 } \
390 }
391
392void fov_beam(fov_settings_type *settings, void *map, void *source,
393 int source_x, int source_y, unsigned radius,
394 fov_direction_type direction, float angle) {
395
396 fov_private_data_type data;
397 float start_slope, end_slope, a;
398
399 data.settings = settings;
400 data.map = map;
401 data.source = source;
402 data.source_x = source_x;
403 data.source_y = source_y;
404 data.radius = radius;
405
406 if (angle <= 0.0f) {
407 return;
408 } else if (angle >= 360.0f) {
409 _fov_circle(&data);
410 return;
411 }
412
413 /* Calculate the angle as a percentage of 45 degrees, halved (for
414 * each side of the centre of the beam). e.g. angle = 180.0f means
415 * half the beam is 90.0 which is 2x45, so the result is 2.0.
416 */
417 a = angle/90.0f;
418
419 BEAM_DIRECTION(FOV_EAST, ppn, pmn, ppy, mpy, pmy, mmy, mpn, mmn);
420 BEAM_DIRECTION(FOV_WEST, mpn, mmn, pmy, mmy, ppy, mpy, ppn, pmn);
421 BEAM_DIRECTION(FOV_NORTH, mpy, mmy, mmn, pmn, mpn, ppn, pmy, ppy);
422 BEAM_DIRECTION(FOV_SOUTH, pmy, ppy, mpn, ppn, mmn, pmn, mmy, mpy);
423 BEAM_DIRECTION_DIAG(FOV_NORTHEAST, pmn, mpy, mmy, ppn, mmn, ppy, mpn, pmy);
424 BEAM_DIRECTION_DIAG(FOV_NORTHWEST, mmn, mmy, mpn, mpy, pmy, pmn, ppy, ppn);
425 BEAM_DIRECTION_DIAG(FOV_SOUTHEAST, ppn, ppy, pmy, pmn, mpn, mpy, mmn, mmy);
426 BEAM_DIRECTION_DIAG(FOV_SOUTHWEST, pmy, mpn, ppy, mmn, ppn, mmy, pmn, mpy);
427}
generated by cgit-pink 1.4.1 (git 2.36.1) at 2024-11-21 14:27:29 +0000