/[anoncvs]/projects/roguelike/fov.cpp


UCC Code Repository

Contents of /projects/roguelike/fov.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.2 - (show annotations) (download)
Thu Apr 13 12:42:56 2006 UTC (15 years ago) by banana
Branch: MAIN
CVS Tags: HEAD
Changes since 1.1: +2 -2 lines
libfov cast fixes for C++

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

Managed by UCC Webmasters ViewVC Help
Powered by ViewVC 1.1.26