shadowcasting

dungeon.rb

module Dungeon
    # Multipliers for transforming coordinates into other octants
    MULT = [
      [1,  0,  0, -1, -1,  0,  0,  1],
      [0,  1, -1,  0,  0, -1,  1,  0],
      [0,  1,  1,  0,  0, -1, -1,  0],
      [1,  0,  0,  1, -1,  0,  0, -1],
    ]

    # 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 handle_fov(start_x, start_y, radius)
      light(start_x, start_y)
      8.times do |i|
        cast_light(start_x, start_y, 1, 1.0, 0.0, radius,
                  MULT[0][i], MULT[1][i],
                  MULT[2][i], MULT[3][i], 0)
      end
    end

    # Recursive light-casting function
    def cast_light(cx, cy, row, light_start, light_end, radius, xx, xy, yx, yy, id)
      return if light_start < light_end

      radius_sq = radius * radius

      (row..radius).each do |j|
        dx = -j - 1
        dy = -j
        blocked = false

        while dx <= 0
          dx += 1

          # Translate the dx, dy co-ordinates into map co-ordinates
          mx = cx + dx * xx + dy * xy
          my = cy + dx * yx + dy * yy

          # l_slope and r_slope store the slopes of the left and right
          # extremities of the square we're considering:
          slope = 0.5
          left_slope = (dx-slope) / (dy+slope)
          right_slope = (dx+slope) / (dy-slope)

          if light_start < right_slope
            next
          elsif light_end > left_slope
            break
          else
            # Our light beam is touching this square; light it
            light(mx, my) if (dx*dx + dy*dy) < radius_sq

            if blocked
              # We've scanning a row of blocked squares
              if blocked?(mx, my)
                new_start = right_slope
                next
              else
                blocked = false
                light_start = new_start
              end
            else
              if blocked?(mx, my) and j < radius
                # This is a blocking square, start a child scan
                blocked = true
                cast_light(cx, cy, j+1, light_start, left_slope, radius,
                          xx, xy, yx, yy, id+1)
                new_start = right_slope
              end
            end
          end
        end # while dx <= 0

        break if blocked
      end # (row..radius).each
    end

    def handle_visible_tile(tile)
      @visible_tiles << tile
      @explored_tiles[tile] = tile if !@explored_tiles.has_key?(tile)

      @entities.each do |entity|
        # is_visible = entity.x ..(entity.x + entity.w)).include?(tile.x + tile.w) && (entity.y..(entity.y + entity.h)).include?(tile.y + tile.h)
        is_visible = entity.x == tile.x && entity.y == tile.y

        if is_visible
          entity.viewed = true
          @visible_entities << entity
        end
      end
    end

    def find_tile_or_wall(x, y)
      tile = @tiles[x]
      tile = tile[y] if tile

      if !tile
        tile = @walls[x]
        tile = tile[y] if tile
      end

      tile
    end

    # Required method for shadowcasting: returns true if tile blocks view
    def blocked?(x, y)
      tile = find_tile_or_wall(x, y)
      return true if !tile  # out of bounds blocks view
      tile.blocks_sight?
    end

    # Required method for shadowcasting: marks tile as visible
    def light(x, y)
      tile = find_tile_or_wall(x, y)
      return if !tile  # skip if out of bounds
      handle_visible_tile(tile)
    end

    def update_field_of_view
      @visible_entities = []
      @visible_tiles = []

      return if !player

      # Use shadowcasting instead of breadth-first search
      # view distance of 4 (same as your max_distance)
      handle_fov(player.x, player.y, 4)
    end
end