EDIT:
Hi there,
I've worked through the algorithm and now it functions decently. It still has a small bug where the corner in a wall isn't visible, and it could do with a little bit of tweaking. But the basics for Permissive FOV are there, so I thought I'd put it up here. If anyone happens to be interested in making a roguelike in Java, feel free to use it; I'll also add the final version with the bug fixes if anyone would need it.
Quick basics on how to use:
the class assumes you keep the level contained in a grid of squares. You add a FieldOfVision field in let's say, the player class. Call the updateFOV method during initialisation, and basically everytime the FOV needs updating. After using that method, use the getters for invisible and visible points; these will be arrays that contain the coordinates of all points that disappeared, and appeared in view respectively.
Code:
package models.creatures;
import java.awt.Point;
import java.util.ArrayList;
import models.Level;
public class FieldOfVision
{
private ArrayList<Point> visibles, invisibles; // The points that turned visible and invisible with the new calculation of the fov.
private int srcX, srcY; // Source square in the level.
private int radius; // The radius of emission in squares.
public FieldOfVision()
{
this.visibles = new ArrayList<Point>();
this.invisibles = new ArrayList<Point>();
}
public ArrayList<Point> getVisibleSquares()
{
return this.visibles;
}
public ArrayList<Point> getDisappearedSquares()
{
return this.invisibles;
}
// Updates the field of vision.
public void updateFOV(Level level, int srcX, int srcY, int radius)
{
// Copies the visible points into the invisible array...
this.invisibles.clear();
for(Point point : this.visibles)
{
this.invisibles.add(point);
}
// ...And clears it.
this.visibles.clear();
this.srcX = srcX;
this.srcY = srcY;
this.radius = radius;
// Method that calculates the new visible squares.
this.calculateLOS(level);
// Remove the points in the invisible list that are still in the visible list.
for(Point point : this.visibles)
{
while(this.invisibles.contains(point))
{
this.invisibles.remove(point);
}
}
}
// Calculates fov for each quadrant of the field.
private void calculateLOS(Level level)
{
this.visibles.add(new Point(srcX, srcY));
quadrantLOS(level, -1, -1);
quadrantLOS(level, 1, -1);
quadrantLOS(level, 1, 1);
quadrantLOS(level, -1, 1);
}
// Calculates fov for a quadrant.
private void quadrantLOS(Level level, int dx, int dy)
{
// Creates a new arc that fills the quadrant
ArcRange arcs = new ArcRange(radius);
// Iteration through points in the quadrant going outward
pointsloop:
for(int rad = 0; rad < 2 * Math.sqrt(Math.pow(radius, 2) / 2); rad++)
{
for(int i = 0; i <= rad; i++)
{
boolean blocks = level.getSquare(srcX + (rad - i) * dx, srcY + i * dy).hasWall();
// If the point is inside the visible circle and hasn't been visited yet...
if(Math.pow(rad - i, 2) + Math.pow(i, 2) <= Math.pow(radius, 2) && (!this.visibles.contains(new Point(srcX + (rad - i) * dx, srcY + i * dy)) || blocks))
{
// If it is visible within the viewing arcs...
// Note: This method also calculates the new arcs if needed.
if(arcs.isVisible(rad - i, i, blocks))
{
// Add the point to the visible list.
this.visibles.add((new Point(srcX + (rad - i) * dx, srcY + i * dy)));
}
// If there are no viewing arcs left, break the loop.
if(arcs.isEmpty())
{
break pointsloop;
}
}
}
}
}
// Class that contains the view arcs and the method isVisible to manipulate them.
private class ArcRange
{
private ArrayList<Arc> arcs;
public ArcRange(int radius)
{
this.arcs = new ArrayList<Arc>();
this.arcs.add(new Arc(new Line(new Point(0, 1), new Point(0, radius)), new Line(new Point(1, 0), new Point(radius, 0))));
}
// Arguments are the point that is being processed, and whether this point has a wall.
public boolean isVisible(int x, int y, boolean blocks)
{
// Assume the block is invisible.
boolean visible = false;
int size = arcs.size();
// For all arcs in this arc range...
for(int i = 0; i < size; i++)
{
float steepDelta = arcs.get(i).getSteepLine().hits(new Point(x, y));
float shallowDelta = arcs.get(i).getShallowLine().hits(new Point(x, y));
// If the point is within viewing range of both lines...
if(steepDelta > -1 && shallowDelta < 1)
{
// Set it visible.
visible = true;
// If it blocks...
if(blocks)
{
// Both lines...
if(steepDelta == 0)
{
if(shallowDelta == 0)
{
// Remove the arc.
arcs.remove(i);
}
// Only the steep line...
else
{
// Rotate the steep line to that point.
arcs.get(i).addSteepBump(new Point(x + 1, y));
}
}
// Only the shallow line...
else if(shallowDelta == 0)
{
// Rotate the shallow line to that point.
arcs.get(i).addShallowBump(new Point(x, y + 1));
}
// None of the lines...
else
{
// Split the arc in two with the point in between.
arcs.add(i + 1, arcs.get(i).clone());
arcs.get(i).getShallowLine().setPoint2(new Point(x, y + 1));
arcs.get(i + 1).getSteepLine().setPoint2(new Point(x + 1, y));
}
}
break;
}
}
return visible;
}
public boolean isEmpty()
{
return this.arcs.size() == 0;
}
}
private class Arc
{
private Line steepLine, shallowLine;
private ArrayList<Point> steepBumps, shallowBumps;
public Arc(Line steep, Line shallow)
{
this.steepLine = steep;
this.shallowLine = shallow;
this.steepBumps = new ArrayList<Point>();
this.shallowBumps = new ArrayList<Point>();
}
public Line getSteepLine()
{
return this.steepLine;
}
public Line getShallowLine()
{
return this.shallowLine;
}
public void addSteepBump(Point point)
{
this.steepBumps.add(point);
this.getSteepLine().setPoint2(point);
for(Point p : shallowBumps)
{
if(this.getSteepLine().distance(p.x, p.y) < 0)
{
this.getSteepLine().setPoint1(p);
}
}
}
public void addShallowBump(Point point)
{
this.shallowBumps.add(point);
this.getShallowLine().setPoint2(point);
for(Point p : steepBumps)
{
if(this.getShallowLine().distance(p.x, p.y) > 0)
{
this.getShallowLine().setPoint1(p);
}
}
}
public Arc clone()
{
Line steep = new Line(new Point(steepLine.p1.x, steepLine.p1.y), new Point(steepLine.p2.x, steepLine.p2.y));
Line shallow = new Line(new Point(shallowLine.p1.x, shallowLine.p1.y), new Point(shallowLine.p2.x, shallowLine.p2.y));
return new Arc(steep, shallow);
}
}
private class Line
{
private Point p1, p2;
public Line(Point p1, Point p2)
{
this.p1 = p1;
this.p2 = p2;
}
public int hits(Point p)
{
if(distance(p.x + 1, p.y) < 0)
{
return -1;
}
else if(distance(p.x, p.y + 1) > 0)
{
return 1;
}
return 0;
}
public double distance(int x, int y)
{
return ((p2.y - p1.y) * x - (p2.x - p1.x) * y + p2.x * p1.y - p1.x * p2.y) / Math.sqrt(Math.pow(p2.y - p1.y, 2) + Math.pow(p2.x - p1.x, 2));
}
public void setPoint1(Point p)
{
this.p1 = p;
}
public void setPoint2(Point p)
{
this.p2 = p;
}
}
}
