Ruby precise permissive FOV implementation
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