from typing import List

BASIC = 0
RECURSIVE_SHADOWCASTING = 1

_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]]


class Fov:
    def __init__(self, block_map: List[List[bool]]):
        self.block = block_map
        self.reset_visible()

    def reset_visible(self):
        self.visible = [[False for _ in range(len(self.block[row]))]
                        for row in range(len(self.block))]

    def compute_visible(self, y, x, radius, algorithm, reset_visible=True):
        """Compute visible areas."""
        if reset_visible:
            self.reset_visible()

        if algorithm == BASIC:
            self._map_compute_fov_basic(y, x, radius)
        elif algorithm == RECURSIVE_SHADOWCASTING:
            self._map_compute_fov_recursive_shadowcasting(y, x, radius)

    def _map_compute_fov_basic(self, y, x, radius):
        for row in range(y - radius, y + radius):
            for col in range(x - radius, x + radius):
                self._set_visible(row, col)

    def _map_compute_fov_recursive_shadowcasting(self, y, x, radius):
        self.visible[y][x] = True
        for octant in range(8):
            self._cast_light(x, y, 1, 1.0, 0.0, radius,
                             _MULT[0][octant], _MULT[1][octant],
                             _MULT[2][octant], _MULT[3][octant])

    def _set_visible(self, y, x):
        if (0 <= y < len(self.visible) and
                0 <= x < len(self.visible[y])):
            self.visible[y][x] = True

    def _blocked(self, y, x):
        return not (0 <= y < len(self.block) and
                    0 <= x < len(self.block[y]) and
                    not self.block[y][x])

    def _cast_light(self, cx, cy, row, startslope, endslope, radius,
                    xx, xy, yx, yy):
        """ Cast light using recursive shadowcasting to determine FOV.

        http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting
        Iterates from startslope = 1.0 to endslope = 0.0 in the top left octant.
        xx, xy, yx, yy are used to determine the actual X, Y in their respective octants.
        dx, dy iterate in the top left octant as follows:

         dx  dy
        =======
         -1  -1
         -1   0
         -2  -2
         -2  -1
         -2   0

        The gradient is determined by dx over dy to invert the gradient from 0 to 1,
        instead of 1 to infinity.
        """
        if startslope < endslope:
            return
        radius_squared = radius * radius
        for j in range(row, radius + 1):
            blocked = False
            dx, dy = -j - 1, -j
            while dx <= 0:
                dx += 1
                X, Y = cx + (dx * xx) + (dy * xy), \
                       cy + (dx * yx) + (dy * yy)
                lslope, rslope = (dx - 0.5) / (dy + 0.5), (dx + 0.5) / (dy - 0.5)
                if startslope < rslope:
                    continue
                elif endslope > lslope:
                    break
                else:
                    if (dx * dx) + (dy * dy) < radius_squared:
                        self._set_visible(Y, X)
                    if blocked:
                        if self._blocked(Y, X):
                            newstart = rslope
                            continue
                        else:
                            blocked = False
                            startslope = newstart
                    else:
                        if self._blocked(Y, X) and j < radius:
                            blocked = True
                            self._cast_light(cx, cy, j + 1, startslope,
                                             lslope, radius, xx, xy, yx, yy)
                            newstart = rslope
            if blocked:
                break
