Skip to content

Instantly share code, notes, and snippets.

@tommyettinger
Created September 12, 2019 05:59
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save tommyettinger/3909bbfc3b7ff14a6c1dab2ad7836d59 to your computer and use it in GitHub Desktop.
Stripped-down version of Jagd's Field of View class
import java.util.Arrays;
/**
* This class provides methods for calculating Field of View in grids. Field of
* View (FOV) algorithms determine how much area surrounding a point can be
* seen. They return a two dimensional array of doubles, representing the amount
* of view (almost always sight) which the origin has of each cell.
* <br>
* The input resistanceMap is considered the percent of opacity. This resistance
* is on top of the resistance applied from the light spreading out. You can
* obtain a resistance map by looping over all the x,y positions in your
* grid-based map and running a switch statement on each cell, assigning a double
* to the same x,y position in a double[][]. The value should be between 0.0
* (unblocked) for things light passes through, 1.0 (blocked) for things light
* can't pass at all, and possibly other values for translucent obstacles.
* <br>
* The returned light map is considered the percent of light in the cells.
* <br>
* Currently, all implementations provide percentage levels of light from 0.0
* (unlit) to 1.0 (fully lit).
* <br>
* All solvers perform bounds checking so solid borders in the map are not
* required.
*
* @author Eben Howard - http://squidpony.com - howard@squidpony.com
* @author Tommy Ettinger
*/
public class FOV {
/**
* Unneeded.
*/
protected FOV() {
}
/**
* Fills a 2D double array with the given value.
* @param array a 2D double array that will be modified
* @param value the value to fill {@code array} with
*/
public static void fill(double[][] array, double value)
{
for (int i = 0; i < array.length; i++) {
Arrays.fill(array[i], value);
}
}
public static double radius (double x, double y) {
return Math.sqrt(x * x + y * y);
}
/**
* Calculates the Field Of View for the provided map from the given x, y
* coordinates. Assigns to, and returns, a light map where the values
* represent a percentage of fully lit. Always uses shadowcasting FOV,
* which allows this method to be static since it doesn't need to keep any
* state around, and can reuse the state the user gives it via the
* {@code light} parameter. The values in light are always cleared before
* this is run, because prior state can make this give incorrect results.
* <br>
* The starting point for the calculation is considered to be at the center
* of the origin cell. The light will be treated as having infinite possible
* radius, so all lit cells will be given 1.0 for their value.
*
* @param resistanceMap the grid of cells to calculate on; 1.0 resists all light, 0.0 does not resist
* @param light a non-null 2D double array that will have its contents overwritten, modified, and returned
* @param startx the horizontal component of the starting location
* @param starty the vertical component of the starting location
* @return the computed light grid (the same as {@code light})
*/
public static double[][] reuseFOV(double[][] resistanceMap, double[][] light, int startx, int starty) {
return reuseFOV(resistanceMap, light, startx, starty, Double.POSITIVE_INFINITY);
}
/**
* Calculates the Field Of View for the provided map from the given x, y
* coordinates. Assigns to, and returns, a light map where the values
* represent a percentage of fully lit. Always uses shadowcasting FOV,
* which allows this method to be static since it doesn't need to keep any
* state around, and can reuse the state the user gives it via the
* {@code light} parameter. The values in light are always cleared before
* this is run, because prior state can make this give incorrect results.
* <br>
* The starting point for the calculation is considered to be at the center
* of the origin cell. Radius determinations based on Euclidean
* calculations. Values in {@code light} will be 1.0 at the light source
* and will decrease steadily as they get further away.
*
* @param resistanceMap the grid of cells to calculate on; 1.0 resists all light, 0.0 does not resist
* @param startX the horizontal component of the starting location
* @param startY the vertical component of the starting location
* @param radius the distance the light will extend to
* @return the computed light grid
*/
public static double[][] reuseFOV(double[][] resistanceMap, double[][] light, int startX, int startY, double radius)
{
double decay = 1.0 / radius;
fill(light, 0);
light[startX][startY] = Math.min(1.0, radius);//make the starting space full power unless radius is tiny
final int width = light.length, height = light[0].length;
shadowCast(1, 1.0, 0.0, 0, 1, 1, 0, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, 1, 0, 0, 1, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, 0, 1, -1, 0, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, 1, 0, 0, -1, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, 0, -1, -1, 0, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, -1, 0, 0, -1, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, 0, -1, 1, 0, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
shadowCast(1, 1.0, 0.0, -1, 0, 0, 1, radius, startX, startY, decay, light, resistanceMap, 0, 0, width, height);
return light;
}
private static void shadowCast(int row, double start, double end, int xx, int xy, int yx, int yy,
double radius, int startx, int starty, double decay, double[][] lightMap,
double[][] map, int minX, int minY, int maxX, int maxY) {
double newStart = 0;
if (start < end) {
return;
}
boolean blocked = false;
for (int distance = row; distance <= radius && distance < maxX - minX + maxY - minY && !blocked; distance++) {
int deltaY = -distance;
for (int deltaX = -distance; deltaX <= 0; deltaX++) {
int currentX = startx + deltaX * xx + deltaY * xy;
int currentY = starty + deltaX * yx + deltaY * yy;
double leftSlope = (deltaX - 0.5f) / (deltaY + 0.5f);
double rightSlope = (deltaX + 0.5f) / (deltaY - 0.5f);
if (!(currentX >= minX && currentY >= minY && currentX < maxX && currentY < maxY) || start < rightSlope) {
continue;
} else if (end > leftSlope) {
break;
}
double deltaRadius = radius(deltaX, deltaY);
//check if it's within the lightable area and light if needed
if (deltaRadius <= radius) {
lightMap[currentX][currentY] = 1.0 - decay * deltaRadius;
}
if (blocked) { //previous cell was a blocking one
if (map[currentX][currentY] >= 1) {//hit a wall
newStart = rightSlope;
} else {
blocked = false;
start = newStart;
}
} else {
if (map[currentX][currentY] >= 1 && distance < radius) {//hit a wall within sight line
blocked = true;
shadowCast(distance + 1, start, leftSlope, xx, xy, yx, yy, radius, startx, starty, decay,
lightMap, map, minX, minY, maxX, maxY); // recurse with different initial settings
newStart = rightSlope;
}
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment