tcod-haskell-0.1.0.0: libtcod/src/fov_restrictive.c
/*
* libtcod 1.6.3
* Copyright (c) 2008,2009,2010,2012,2013,2016,2017 Jice & Mingos & rmtew
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * The name of Jice or Mingos may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY JICE, MINGOS AND RMTEW ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL JICE, MINGOS OR RMTEW BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/*
* Mingos' Restrictive Precise Angle Shadowcasting (MRPAS) v1.2
*/
#include <fov.h>
#include <stdlib.h> /* for NULL in VS */
#include <libtcod_int.h>
#include <libtcod_utility.h>
/* angle ranges */
double * start_angle = NULL;
double * end_angle = NULL;
/* number of allocated angle pairs */
int allocated = 0;
void TCOD_map_compute_fov_restrictive_shadowcasting_quadrant (map_t *m, int player_x, int player_y, int max_radius, bool light_walls, int dx, int dy) {
/* octant: vertical edge */
{
int iteration = 1; /* iteration of the algo for this octant */
bool done = false;
int total_obstacles = 0;
int obstacles_in_last_line = 0;
double min_angle = 0.0;
int x;
int y;
/* do while there are unblocked slopes left and the algo is within the map's boundaries
scan progressive lines/columns from the PC outwards */
y = player_y+dy; /* the outer slope's coordinates (first processed line) */
if (y < 0 || y >= m->height) {
done = true;
}
while (!done) {
/* process cells in the line */
double slopes_per_cell = 1.0 / (double)(iteration);
double half_slopes = slopes_per_cell * 0.5;
int processed_cell = (int)((min_angle + half_slopes) / slopes_per_cell);
int minx = MAX(0, player_x - iteration);
int maxx = MIN(m->width - 1, player_x + iteration);
done = true;
for (x = player_x + (processed_cell * dx); x >= minx && x <= maxx; x+=dx) {
int c = x + (y * m->width);
/* calculate slopes per cell */
bool visible = true;
bool extended = false;
double centre_slope = (double)processed_cell * slopes_per_cell;
double start_slope = centre_slope - half_slopes;
double end_slope = centre_slope + half_slopes;
if (obstacles_in_last_line > 0) {
if (
!(
m->cells[c-(m->width * dy)].fov &&
m->cells[c-(m->width * dy)].transparent
) &&
!(
m->cells[c-(m->width * dy) - dx].fov &&
m->cells[c-(m->width * dy) - dx].transparent
)
) {
visible = false;
} else {
int idx;
for (idx = 0; idx < obstacles_in_last_line && visible; ++idx) {
if (
start_slope <= end_angle[idx] &&
end_slope >= start_angle[idx]
) {
if (m->cells[c].transparent) {
if (
centre_slope > start_angle[idx] &&
centre_slope < end_angle[idx]
) {
visible = false;
}
} else {
if (
start_slope >= start_angle[idx] &&
end_slope <= end_angle[idx]
) {
visible = false;
} else {
start_angle[idx] = MIN(start_angle[idx], start_slope);
end_angle[idx] = MAX(end_angle[idx], end_slope);
extended = true;
}
}
}
}
}
}
if (visible) {
done = false;
m->cells[c].fov = true;
/* if the cell is opaque, block the adjacent slopes */
if (!m->cells[c].transparent) {
if (min_angle >= start_slope) {
min_angle = end_slope;
/* if min_angle is applied to the last cell in line, nothing more
needs to be checked. */
if (processed_cell == iteration) {
done = true;
}
} else if (!extended) {
start_angle[total_obstacles] = start_slope;
end_angle[total_obstacles++] = end_slope;
}
if (!light_walls) {
m->cells[c].fov = false;
}
}
}
processed_cell++;
}
if (iteration == max_radius) {
done = true;
}
iteration++;
obstacles_in_last_line = total_obstacles;
y += dy;
if (y < 0 || y >= m->height) {
done = true;
}
}
}
/* octant: horizontal edge */
{
int iteration = 1; /* iteration of the algo for this octant */
bool done = false;
int total_obstacles = 0;
int obstacles_in_last_line = 0;
double min_angle = 0.0;
int x;
int y;
/* do while there are unblocked slopes left and the algo is within the map's boundaries
scan progressive lines/columns from the PC outwards */
x = player_x+dx; /*the outer slope's coordinates (first processed line) */
if (x < 0 || x >= m->width) {
done = true;
}
while (!done) {
/* process cells in the line */
double slopes_per_cell = 1.0 / (double)(iteration);
double half_slopes = slopes_per_cell * 0.5;
int processed_cell = (int)((min_angle + half_slopes) / slopes_per_cell);
int miny = MAX(0, player_y - iteration);
int maxy = MIN(m->height - 1, player_y + iteration);
done = true;
for (y = player_y + (processed_cell * dy); y >= miny && y <= maxy; y += dy) {
int c = x + (y * m->width);
/* calculate slopes per cell */
bool visible = true;
bool extended = false;
double centre_slope = (double)processed_cell * slopes_per_cell;
double start_slope = centre_slope - half_slopes;
double end_slope = centre_slope + half_slopes;
if (obstacles_in_last_line > 0) {
if (
!(
m->cells[c-dx].fov &&
m->cells[c-dx].transparent
) &&
!(
m->cells[c-(m->width * dy) - dx].fov &&
m->cells[c-(m->width * dy) - dx].transparent
)
) {
visible = false;
} else {
int idx;
for (idx = 0; idx < obstacles_in_last_line && visible; ++idx) {
if (
start_slope <= end_angle[idx] &&
end_slope >= start_angle[idx]
) {
if (m->cells[c].transparent) {
if (
centre_slope > start_angle[idx] &&
centre_slope < end_angle[idx]
) {
visible = false;
}
} else {
if (
start_slope >= start_angle[idx] &&
end_slope <= end_angle[idx]
) {
visible = false;
} else {
start_angle[idx] = MIN(start_angle[idx], start_slope);
end_angle[idx] = MAX(end_angle[idx], end_slope);
extended = true;
}
}
++idx;
}
}
}
}
if (visible) {
done = false;
m->cells[c].fov = true;
/* if the cell is opaque, block the adjacent slopes */
if (!m->cells[c].transparent) {
if (min_angle >= start_slope) {
min_angle = end_slope;
/* if min_angle is applied to the last cell in line, nothing more
needs to be checked. */
if (processed_cell == iteration) {
done = true;
}
} else if (!extended) {
start_angle[total_obstacles] = start_slope;
end_angle[total_obstacles++] = end_slope;
}
if (!light_walls) {
m->cells[c].fov = false;
}
}
}
processed_cell++;
}
if (iteration == max_radius) {
done = true;
}
iteration++;
obstacles_in_last_line = total_obstacles;
x += dx;
if (x < 0 || x >= m->width) {
done = true;
}
}
}
}
void TCOD_map_compute_fov_restrictive_shadowcasting(TCOD_map_t map, int player_x, int player_y, int max_radius, bool light_walls) {
map_t *m = (map_t *)map;
int max_obstacles;
int c;
/* first, zero the FOV map */
for(c = m->nbcells - 1; c >= 0; c--) {
m->cells[c].fov = false;
}
/* calculate an approximated (excessive, just in case) maximum number of obstacles per octant */
max_obstacles = m->nbcells / 7;
/* check memory for angles */
if (max_obstacles > allocated) {
allocated = max_obstacles;
if (start_angle != NULL) free(start_angle);
if (end_angle != NULL) free(end_angle);
start_angle = (double*)calloc(max_obstacles, sizeof(double));
end_angle = (double*)calloc(max_obstacles, sizeof(double));
}
/* set PC's position as visible */
m->cells[player_x+(player_y*m->width)].fov = true;
/* compute the 4 quadrants of the map */
TCOD_map_compute_fov_restrictive_shadowcasting_quadrant (m, player_x, player_y, max_radius, light_walls, 1, 1);
TCOD_map_compute_fov_restrictive_shadowcasting_quadrant (m, player_x, player_y, max_radius, light_walls, 1, -1);
TCOD_map_compute_fov_restrictive_shadowcasting_quadrant (m, player_x, player_y, max_radius, light_walls, -1, 1);
TCOD_map_compute_fov_restrictive_shadowcasting_quadrant (m, player_x, player_y, max_radius, light_walls, -1, -1);
}