Ruby precise permissive FOV implementation
Jump to navigation
Jump to search
This is an implementation of Precise Permissive Field of View algorithm. It is based on the Python implementation by Aaron MacDonald.
To use the algorithm, create a Map class or somesuch and provide two methods:
blocked?(x, y) returns true if the tile at (x, y) blocks view of tiles beyond it (e.g. walls)
light(x, y) marks (x, y) as visible to the player (e.g. lit up on screen)
Then include PermissiveFieldOfView within your Map class (or call extend(PermissiveFieldOfView) on your Map instance if you want to be dynamic) and call do_fov.
Compared with shadowcasting, permissive FOV runs ever so slightly slower but is reputedly artifact-free and symmetric (if you can see something, it can see you). Unfortunately this algorithm produces a square FOV shape around the player. Uncommenting the lines in visit_coord will change it to a diamond, but I don't understand enough to get a circle out of it :(
My Ruby is fairly novice so if anyone sees anything amiss with the code, you are more than welcome to change it.
module PermissiveFieldOfView
# Determines which co-ordinates on a 2D grid are visible
# from a particular co-ordinate.
# start_x, start_y: center of view
# radius: how far field of view extends
def do_fov(start_x, start_y, radius)
@start_x, @start_y = start_x, start_y
@radius_sq = radius * radius
# We always see the center
light @start_x, @start_y
# Restrict scan dimensions to map borders and within the radius
min_extent_x = [@start_x, radius].min
max_extent_x = [@width - @start_x - 1, radius].min
min_extent_y = [@start_y, radius].min
max_extent_y = [@height - @start_y - 1, radius].min
# Check quadrants: NE, SE, SW, NW
check_quadrant 1, 1, max_extent_x, max_extent_y
check_quadrant 1, -1, max_extent_x, min_extent_y
check_quadrant -1, -1, min_extent_x, min_extent_y
check_quadrant -1, 1, min_extent_x, max_extent_y
end
private
# Represents a line (duh)
class Line < Struct.new(:xi, :yi, :xf, :yf)
# Macros to make slope comparisons clearer
{:below => '>', :below_or_collinear => '>=', :above => '<',
:above_or_collinear => '<=', :collinear => '=='}.each do |name, fn|
eval "def #{name.to_s}?(x, y) relative_slope(x, y) #{fn} 0 end"
end
def dx; xf - xi end
def dy; yf - yi end
def line_collinear?(line)
collinear?(line.xi, line.yi) and collinear?(line.xf, line.yf)
end
def relative_slope(x, y)
(dy * (xf - x)) - (dx * (yf - y))
end
end
class ViewBump < Struct.new(:x, :y, :parent)
def deep_copy
ViewBump.new(x, y, parent.nil? ? nil : parent.deep_copy)
end
end
class View < Struct.new(:shallow_line, :steep_line)
attr_accessor :shallow_bump, :steep_bump
def deep_copy
copy = View.new(shallow_line.dup, steep_line.dup)
copy.shallow_bump = shallow_bump.nil? ? nil : shallow_bump.deep_copy
copy.steep_bump = steep_bump.nil? ? nil : steep_bump.deep_copy
return copy
end
end
# Check a quadrant of the FOV field for visible tiles
def check_quadrant(dx, dy, extent_x, extent_y)
active_views = []
shallow_line = Line.new(0, 1, extent_x, 0)
steep_line = Line.new(1, 0, 0, extent_y)
active_views << View.new(shallow_line, steep_line)
view_index = 0
# Visit the tiles diagonally and going outwards
i, max_i = 1, extent_x + extent_y
while i != max_i + 1 and active_views.size > 0
start_j = [0, i - extent_x].max
max_j = [i, extent_y].min
j = start_j
while j != max_j + 1 and view_index < active_views.size
x, y = i - j, j
visit_coord x, y, dx, dy, view_index, active_views
j += 1
end
i += 1
end
end
def visit_coord(x, y, dx, dy, view_index, active_views)
# The top left and bottom right corners of the current coordinate
top_left, bottom_right = [x, y + 1], [x + 1, y]
while view_index < active_views.size and
active_views[view_index].steep_line.below_or_collinear?(*bottom_right)
# Co-ord is above the current view and can be ignored (steeper fields may need it though)
view_index += 1
end
if view_index == active_views.size or
active_views[view_index].shallow_line.above_or_collinear?(*top_left)
# Either current co-ord is above all the fields, or it is below all the fields
return
end
# Current co-ord must be between the steep and shallow lines of the current view
# The real quadrant co-ordinates:
real_x, real_y = x * dx, y * dy
coord = [@start_x + real_x, @start_y + real_y]
light *coord
# Don't go beyond circular radius specified
#if (real_x * real_x + real_y * real_y) > @radius_sq
# active_views.delete_at(view_index)
# return
#end
# If this co-ord does not block sight, it has no effect on the view
return unless blocked?(*coord)
view = active_views[view_index]
if view.shallow_line.above?(*bottom_right) and view.steep_line.below?(*top_left)
# Co-ord is intersected by both lines in current view, and is completely blocked
active_views.delete(view)
elsif view.shallow_line.above?(*bottom_right)
# Co-ord is intersected by shallow line; raise the line
add_shallow_bump top_left[0], top_left[1], view
check_view active_views, view_index
elsif view.steep_line.below?(*top_left)
# Co-ord is intersected by steep line; lower the line
add_steep_bump bottom_right[0], bottom_right[1], view
check_view active_views, view_index
else
# Co-ord is completely between the two lines of the current view. Split the
# current view into two views above and below the current co-ord.
shallow_view_index, steep_view_index = view_index, view_index += 1
active_views.insert(shallow_view_index, active_views[shallow_view_index].deep_copy)
add_steep_bump bottom_right[0], bottom_right[1], active_views[shallow_view_index]
unless check_view(active_views, shallow_view_index)
view_index -= 1
steep_view_index -= 1
end
add_shallow_bump top_left[0], top_left[1], active_views[steep_view_index]
check_view active_views, steep_view_index
end
end
def add_shallow_bump(x, y, view)
view.shallow_line.xf = x
view.shallow_line.yf = y
view.shallow_bump = ViewBump.new(x, y, view.shallow_bump)
cur_bump = view.steep_bump
while not cur_bump.nil?
if view.shallow_line.above?(cur_bump.x, cur_bump.y)
view.shallow_line.xi = cur_bump.x
view.shallow_line.yi = cur_bump.y
end
cur_bump = cur_bump.parent
end
end
def add_steep_bump(x, y, view)
view.steep_line.xf = x
view.steep_line.yf = y
view.steep_bump = ViewBump.new(x, y, view.steep_bump)
cur_bump = view.shallow_bump
while not cur_bump.nil?
if view.steep_line.below?(cur_bump.x, cur_bump.y)
view.steep_line.xi = cur_bump.x
view.steep_line.yi = cur_bump.y
end
cur_bump = cur_bump.parent
end
end
# Removes the view in active_views at index view_index if:
# * The two lines are collinear
# * The lines pass through either extremity
def check_view(active_views, view_index)
shallow_line = active_views[view_index].shallow_line
steep_line = active_views[view_index].steep_line
if shallow_line.line_collinear?(steep_line) and (shallow_line.collinear?(0, 1) or
shallow_line.collinear?(1, 0))
active_views.delete_at view_index
return false
end
return true
end
end