/* * Copyright (C) 2006, Greg McIntyre * All rights reserved. See the file named COPYING in the distribution * for more details. */ #include #include #include #define __USE_ISOC99 1 #include #include #include #include "fov.h" /* +---++---++---++---+ | || || || | | || || || | | || || || | +---++---++---++---+ 2 +---++---++---+##### | || || |##### | || || |##### | || || |##### +---++---++---+#####X 1 <-- y +---++---++---++---+ | || || || | | @ || || || | <-- srcy centre -> dy = 0.5 = y - 0.5 | || || || | +---++---++---++---+ 0 0 1 2 3 4 ^ ^ | | srcx x -> dx = 3.5 = x + 0.5 centre Slope from @ to X. +---++---++---++---+ | || || || | | || || || | | || || || | +---++---++---++---+ 2 +---++---++---++---+ | || || || | | || || || | | || || || | +---++---++---+X---+ 1 <-- y +---++---++---+##### | || || |##### | @ || || |##### <-- srcy centre -> dy = 0.5 = y - 0.5 | || || |##### +---++---++---+##### 0 0 1 2 3 ^ ^ | | srcx x -> dx = 2.5 = x - 0.5 centre Slope from @ to X */ /* Types ---------------------------------------------------------- */ typedef struct { /*@observer@*/ fov_settings_type *settings; /*@observer@*/ void *map; /*@observer@*/ void *source; int source_x; int source_y; unsigned radius; } fov_private_data_type; /* Options -------------------------------------------------------- */ void fov_settings_init(fov_settings_type *settings) { settings->shape = FOV_SHAPE_CIRCLE_PRECALCULATE; settings->corner_peek = FOV_CORNER_NOPEEK; settings->opaque_apply = FOV_OPAQUE_APPLY; settings->opaque = NULL; settings->apply = NULL; settings->numheights = 0; } fov_settings_type *new_fov_settings() { fov_settings_type *s = malloc(sizeof(fov_settings_type)); fov_settings_init(s); return s; } void fov_settings_set_shape(fov_settings_type *settings, fov_shape_type value) { settings->shape = value; } void fov_settings_set_corner_peek(fov_settings_type *settings, fov_corner_peek_type value) { settings->corner_peek = value; } void fov_settings_set_opaque_apply(fov_settings_type *settings, fov_opaque_apply_type value) { settings->opaque_apply = value; } void fov_settings_set_opacity_test_function(fov_settings_type *settings, bool (*f)(void *map, int x, int y)) { settings->opaque = f; } void fov_settings_set_apply_lighting_function(fov_settings_type *settings, void (*f)(void *map, int x, int y, int dx, int dy, void *src)) { settings->apply = f; } /* Circular FOV --------------------------------------------------- */ /*@null@*/ static unsigned *precalculate_heights(unsigned maxdist) { unsigned i; unsigned *result = (unsigned *)malloc((maxdist+2)*sizeof(unsigned)); if (result) { for (i = 0; i <= maxdist; ++i) { result[i] = (unsigned)sqrtf((float)(maxdist*maxdist - i*i)); } result[maxdist+1] = 0; } return result; } static unsigned height(fov_settings_type *settings, int x, unsigned maxdist) { unsigned **newheights; if (maxdist > settings->numheights) { newheights = (unsigned **)calloc((size_t)maxdist, sizeof(unsigned*)); if (newheights != NULL) { if (settings->heights != NULL && settings->numheights > 0) { /* Copy the pointers to the heights arrays we've already * calculated. Once copied out, we can free the old * array of pointers. */ memcpy(newheights, settings->heights, settings->numheights*sizeof(unsigned*)); free(settings->heights); } settings->heights = newheights; settings->numheights = maxdist; } } if (settings->heights) { if (settings->heights[maxdist-1] == NULL) { settings->heights[maxdist-1] = precalculate_heights(maxdist); } if (settings->heights[maxdist-1] != NULL) { return settings->heights[maxdist-1][abs(x)]; } } return 0; } void fov_settings_free(fov_settings_type *settings) { unsigned i; if (settings != NULL) { if (settings->heights != NULL && settings->numheights > 0) { /*@+forloopexec@*/ for (i = 0; i < settings->numheights; ++i) { unsigned *h = settings->heights[i]; if (h != NULL) { free(h); } settings->heights[i] = NULL; } /*@=forloopexec@*/ free(settings->heights); settings->heights = NULL; settings->numheights = 0; } } } /* Slope ---------------------------------------------------------- */ static float fov_slope(float dx, float dy) { if (dx <= -FLT_EPSILON || dx >= FLT_EPSILON) { return dy/dx; } else { return 0.0; } } /* Octants -------------------------------------------------------- */ #define FOV_DEFINE_OCTANT(signx, signy, rx, ry, nx, ny, nf, apply_edge, apply_diag) \ static void fov_octant_##nx##ny##nf( \ fov_private_data_type *data, \ int dx, \ float start_slope, \ float end_slope) { \ int x, y, dy, dy0, dy1; \ unsigned h; \ int prev_blocked = -1; \ float end_slope_next; \ fov_settings_type *settings = data->settings; \ \ if (dx == 0) { \ fov_octant_##nx##ny##nf(data, dx+1, start_slope, end_slope); \ return; \ } else if ((unsigned)dx > data->radius) { \ return; \ } \ \ dy0 = (int)(0.5f + ((float)dx)*start_slope); \ dy1 = (int)(0.5f + ((float)dx)*end_slope); \ \ rx = data->source_##rx signx dx; \ ry = data->source_##ry signy dy0; \ \ if (!apply_diag && dy1 == dx) { \ /* We do diagonal lines on every second octant, so they don't get done twice. */ \ --dy1; \ } \ \ switch (settings->shape) { \ case FOV_SHAPE_CIRCLE_PRECALCULATE: \ h = height(settings, dx, data->radius); \ break; \ case FOV_SHAPE_CIRCLE: \ h = (unsigned)sqrtf((float)(data->radius*data->radius - dx*dx)); \ break; \ case FOV_SHAPE_OCTAGON: \ h = (data->radius - dx)<<1; \ break; \ default: \ h = data->radius; \ break; \ }; \ if ((unsigned)dy1 > h) { \ if (h == 0) { \ return; \ } \ dy1 = (int)h; \ } \ \ /*fprintf(stderr, "(%2d) = [%2d .. %2d] (%f .. %f), h=%d,edge=%d\n", \ dx, dy0, dy1, ((float)dx)*start_slope, \ 0.5f + ((float)dx)*end_slope, h, apply_edge);*/ \ \ for (dy = dy0; dy <= dy1; ++dy) { \ ry = data->source_##ry signy dy; \ \ if (settings->opaque(data->map, x, y)) { \ if (settings->opaque_apply == FOV_OPAQUE_APPLY && (apply_edge || dy > 0)) { \ settings->apply(data->map, x, y, dx, dy, data->source); \ } \ if (prev_blocked == 0) { \ end_slope_next = fov_slope((float)dx + 0.5f, (float)dy - 0.5f); \ fov_octant_##nx##ny##nf(data, dx+1, start_slope, end_slope_next); \ } \ prev_blocked = 1; \ } else { \ if (apply_edge || dy > 0) { \ settings->apply(data->map, x, y, dx, dy, data->source); \ } \ if (prev_blocked == 1) { \ start_slope = fov_slope((float)dx - 0.5f, (float)dy - 0.5f); \ } \ prev_blocked = 0; \ } \ } \ \ if (prev_blocked == 0) { \ fov_octant_##nx##ny##nf(data, dx+1, start_slope, end_slope); \ } \ } FOV_DEFINE_OCTANT(+,+,x,y,p,p,n,true,true) FOV_DEFINE_OCTANT(+,+,y,x,p,p,y,true,false) FOV_DEFINE_OCTANT(+,-,x,y,p,m,n,false,true) FOV_DEFINE_OCTANT(+,-,y,x,p,m,y,false,false) FOV_DEFINE_OCTANT(-,+,x,y,m,p,n,true,true) FOV_DEFINE_OCTANT(-,+,y,x,m,p,y,true,false) FOV_DEFINE_OCTANT(-,-,x,y,m,m,n,false,true) FOV_DEFINE_OCTANT(-,-,y,x,m,m,y,false,false) /* Circle --------------------------------------------------------- */ static void _fov_circle(fov_private_data_type *data) { /* * Octants are defined by (x,y,r) where: * x = [p]ositive or [n]egative x increment * y = [p]ositive or [n]egative y increment * r = [y]es or [n]o for reflecting on axis x = y * * \pmy|ppy/ * \ | / * \ | / * mpn\|/ppn * ----@---- * mmn/|\pmn * / | \ * / | \ * /mmy|mpy\ */ fov_octant_ppn(data, 1, (float)0.0f, (float)1.0f); fov_octant_ppy(data, 1, (float)0.0f, (float)1.0f); fov_octant_pmn(data, 1, (float)0.0f, (float)1.0f); fov_octant_pmy(data, 1, (float)0.0f, (float)1.0f); fov_octant_mpn(data, 1, (float)0.0f, (float)1.0f); fov_octant_mpy(data, 1, (float)0.0f, (float)1.0f); fov_octant_mmn(data, 1, (float)0.0f, (float)1.0f); fov_octant_mmy(data, 1, (float)0.0f, (float)1.0f); } void fov_circle(fov_settings_type *settings, void *map, void *source, int source_x, int source_y, unsigned radius) { fov_private_data_type data; data.settings = settings; data.map = map; data.source = source; data.source_x = source_x; data.source_y = source_y; data.radius = radius; _fov_circle(&data); } /** * Limit x to the range [a, b]. */ static float betweenf(float x, float a, float b) { if (x - a < FLT_EPSILON) { /* x < a */ return a; } else if (x - b > FLT_EPSILON) { /* x > b */ return b; } else { return x; } } #define BEAM_DIRECTION(d, p1, p2, p3, p4, p5, p6, p7, p8) \ if (direction == d) { \ end_slope = betweenf(a, 0.0f, 1.0f); \ fov_octant_##p1(&data, 1, 0.0f, end_slope); \ fov_octant_##p2(&data, 1, 0.0f, end_slope); \ if (a - 1.0f > FLT_EPSILON) { /* a > 1.0f */ \ start_slope = betweenf(2.0f - a, 0.0f, 1.0f); \ fov_octant_##p3(&data, 1, start_slope, 1.0f); \ fov_octant_##p4(&data, 1, start_slope, 1.0f); \ } \ if (a - 2.0f > FLT_EPSILON) { /* a > 2.0f */ \ end_slope = betweenf(a - 2.0f, 0.0f, 1.0f); \ fov_octant_##p5(&data, 1, 0.0f, end_slope); \ fov_octant_##p6(&data, 1, 0.0f, end_slope); \ } \ if (a - 3.0f > FLT_EPSILON) { /* a > 3.0f */ \ start_slope = betweenf(4.0f - a, 0.0f, 1.0f); \ fov_octant_##p7(&data, 1, start_slope, 1.0f); \ fov_octant_##p8(&data, 1, start_slope, 1.0f); \ } \ } #define BEAM_DIRECTION_DIAG(d, p1, p2, p3, p4, p5, p6, p7, p8) \ if (direction == d) { \ start_slope = betweenf(1.0f - a, 0.0f, 1.0f); \ fov_octant_##p1(&data, 1, start_slope, 1.0f); \ fov_octant_##p2(&data, 1, start_slope, 1.0f); \ if (a - 1.0f > FLT_EPSILON) { /* a > 1.0f */ \ end_slope = betweenf(a - 1.0f, 0.0f, 1.0f); \ fov_octant_##p3(&data, 1, 0.0f, end_slope); \ fov_octant_##p4(&data, 1, 0.0f, end_slope); \ } \ if (a - 2.0f > FLT_EPSILON) { /* a > 2.0f */ \ start_slope = betweenf(3.0f - a, 0.0f, 1.0f); \ fov_octant_##p5(&data, 1, start_slope, 1.0f); \ fov_octant_##p6(&data, 1, start_slope, 1.0f); \ } \ if (a - 3.0f > FLT_EPSILON) { /* a > 3.0f */ \ end_slope = betweenf(a - 3.0f, 0.0f, 1.0f); \ fov_octant_##p7(&data, 1, 0.0f, end_slope); \ fov_octant_##p8(&data, 1, 0.0f, end_slope); \ } \ } void fov_beam(fov_settings_type *settings, void *map, void *source, int source_x, int source_y, unsigned radius, fov_direction_type direction, float angle) { fov_private_data_type data; float start_slope, end_slope, a; data.settings = settings; data.map = map; data.source = source; data.source_x = source_x; data.source_y = source_y; data.radius = radius; if (angle <= 0.0f) { return; } else if (angle >= 360.0f) { _fov_circle(&data); } /* Calculate the angle as a percentage of 45 degrees, halved (for * each side of the centre of the beam). e.g. angle = 180.0f means * half the beam is 90.0 which is 2x45, so the result is 2.0. */ a = angle/90.0f; BEAM_DIRECTION(FOV_EAST, ppn, pmn, ppy, mpy, pmy, mmy, mpn, mmn); BEAM_DIRECTION(FOV_WEST, mpn, mmn, pmy, mmy, ppy, mpy, ppn, pmn); BEAM_DIRECTION(FOV_NORTH, mpy, mmy, mmn, pmn, mpn, ppn, pmy, ppy); BEAM_DIRECTION(FOV_SOUTH, pmy, ppy, mpn, ppn, mmn, pmn, mmy, mpy); BEAM_DIRECTION_DIAG(FOV_NORTHEAST, pmn, mpy, mmy, ppn, mmn, ppy, mpn, pmy); BEAM_DIRECTION_DIAG(FOV_NORTHWEST, mmn, mmy, mpn, mpy, pmy, pmn, ppy, ppn); BEAM_DIRECTION_DIAG(FOV_SOUTHEAST, ppn, ppy, pmy, pmn, mpn, mpy, mmn, mmy); BEAM_DIRECTION_DIAG(FOV_SOUTHWEST, pmy, mpn, ppy, mmn, ppn, mmy, pmn, mpy); }