my_algorithm.py

def blocks_light(x, y):
    '''my_map is a nested list() of Tile objects that have block_sight, blocked, etc as in the classic tutorial.
    '''
    global my_map
    return my_map[x][y].block_sight


def set_visible(x, y):
    '''visible_tiles is a set() of (x, y) tuples, tracking which tiles are visible.
    it is reset every time fov is recalculated.
    '''
    global visible_tiles
    visible_tiles.add((x, y))


def get_distance(x, y):
    '''euclidean distance'''
    return sqrt((x ** 2) + (y ** 2))


class Slope:
    def __init__(self, y, x):
        self.y = y
        self.x = x

    def greater(self, y, x):
        return (self.y * x) > (self.x * y)

    def greater_or_equal(self, y, x):
        return (self.y * x) >= (self.x * y)

    def less(self, y, x):
        return (self.y * x) < (self.x * y)


class AdamMilazzosAlgorithm:
    def __init__(self, blocks_light, set_visible, get_distance):
        self._blocks_light = blocks_light
        self._set_visible = set_visible
        self.get_distance = get_distance

        self.octant_switch = {
            0: (lambda nx, ny, x, y: (nx + x, ny - y)),
            1: (lambda nx, ny, x, y: (nx + y, ny - x)),
            2: (lambda nx, ny, x, y: (nx - y, ny - x)),
            3: (lambda nx, ny, x, y: (nx - x, ny - y)),
            4: (lambda nx, ny, x, y: (nx - x, ny + y)),
            5: (lambda nx, ny, x, y: (nx - y, ny + x)),
            6: (lambda nx, ny, x, y: (nx + y, ny + x)),
            7: (lambda nx, ny, x, y: (nx + x, ny + y)),
        }

    def compute(self, origin, range_limit):
        self._set_visible(origin.x, origin.y)
        for octant in range(8):
            self._compute(octant, origin, range_limit, 1, Slope(1, 1), Slope(0, 1))

    def _compute(self, octant, origin, range_limit, _x, top, bottom):
        for x in range(_x, range_limit + 1):
            if top.x == 1:
                top_y = x
            else:
                top_y = ((x * 2 - 1) * top.y + top.x) // (top.x * 2)
                if self.blocks_light(x, top_y, octant, origin):
                    if top.greater_or_equal(top_y * 2 + 1, x * 2) \
                       and not self.blocks_light(x, top_y + 1, octant, origin):
                        top_y += 1
                else:
                    ax = x * 2
                    if self.blocks_light(x + 1, top_y + 1, octant, origin):
                        ax += 1
                    if top.greater(top_y * 2 + 1, ax):
                        top_y += 1

            if bottom.y == 0:
                bottom_y = 0
            else:
                bottom_y = ((x * 2 - 1) * bottom.y + bottom.x) // (bottom.x * 2)
                if bottom.greater_or_equal(bottom_y * 2 + 1, x * 2) \
                   and self.blocks_light(x, bottom_y, octant, origin) \
                   and not self.blocks_light(x, bottom_y + 1, octant, origin):
                    bottom_y += 1

            was_opaque = None
            for y in range(top_y, bottom_y - 1, -1):
                if (range_limit < 0) or (get_distance(x, y) <= range_limit):
                    is_opaque = self.blocks_light(x, y, octant, origin)
                    is_visible = is_opaque or (
                        ((y != top_y) or top.greater(y * 4 - 1, x * 4 + 1)) \
                        and ((y != bottom_y) or bottom.less(y * 4 + 1, x * 4 - 1)))
                    if is_visible:
                        self.set_visible(x, y, octant, origin)
                    if x != range_limit:
                        if is_opaque:
                            if was_opaque is False:
                                nx = x * 2
                                ny = (y * 2) + 1
                                if self.blocks_light(x, y + 1, octant, origin):
                                    nx -= 1
                                if top.greater(ny, nx):
                                    if y == bottom_y:
                                        bottom = Slope(ny, nx)
                                        break
                                    else:
                                        self._compute(octant, origin, range_limit, x + 1, top, Slope(ny, nx))
                                else:
                                    if y == bottom_y:
                                        return
                            was_opaque = True
                        else:
                            if was_opaque:
                                nx = x * 2
                                ny = (y * 2) + 1
                                if self.blocks_light(x + 1, y + 1, octant, origin):
                                    nx += 1
                                if bottom.greater_or_equal(ny, nx):
                                    return
                                top = Slope(ny, nx)
                            was_opaque = False
            if was_opaque is not False:
                break

    def blocks_light(self, x, y, octant, origin):
        nx, ny = self.octant_switch[octant](origin.x, origin.y, x, y)
        return self._blocks_light(nx, ny)

    def set_visible(self, x, y, octant, origin):
        nx, ny = self.octant_switch[octant](origin.x, origin.y, x, y)
        self._set_visible(nx, ny)