Fully symmetric partial supercover cached field of view calculation

fov_cached.py

# field of view quadrant cache
# uses brute force O(N^3) calculation of fov and caches results
import cython
from bitarray import bitarray
from pygame import Rect

from .geometry import generate_partial_supercover_line, generate_points_in_rect_xy, Coordinate


def _gen_quadrant_adjusted(x0, y0, q1x, q1y):
    yield x0 + q1x, y0 + q1y
    yield x0 - q1x, y0 + q1y
    yield x0 - q1x, y0 - q1y
    yield x0 + q1x, y0 - q1y


def _adjusted_index(stride, x0, y0, q1x, q1y, quadrant):
    x, y = None, None
    if quadrant == 1:
        x = x0 + q1x
        y = y0 + q1y
    elif quadrant == 2:
        x = x0 - q1x
        y = y0 + q1y
    elif quadrant == 3:
        x = x0 - q1x
        y = y0 - q1y
    elif quadrant == 4:
        x = x0 + q1x
        y = y0 - q1y
    else:
        raise ValueError("Illegal quadrant value")
    return y * stride + x


def calculate_quadrant_cache(max_radius):
    stride = max_radius * 2 + 1
    order = stride * stride
    cache = [None] * order
    x0 = max_radius
    y0 = max_radius
    scan_origin = Coordinate(0, 0)
    template = bitarray(order)
    template.setall(True)  # all visible
    cache[y0 * stride + x0] = template  # stash in origin
    qr = Rect(0, 0, max_radius, max_radius)
    for block_x, block_y in generate_points_in_rect_xy(qr):
        if block_x == 0 and block_y == 0:
            continue
        for qx, qy in _gen_quadrant_adjusted(x0, y0, block_x, block_y):
            cache[qy * stride + qx] = template.copy()
        r = Rect(block_x, block_y, max_radius, max_radius).clip(qr)
        for targ_x, targ_y in generate_points_in_rect_xy(r):
            if targ_x == block_x and targ_y == block_y:
                continue
            for x, y, _ in generate_partial_supercover_line(scan_origin, Coordinate(targ_x, targ_y)):
                if x == block_x and y == block_y:
                    for q in xrange(1, 5):
                        cache[_adjusted_index(stride, x0, y0, block_x, block_y, q)][
                            _adjusted_index(stride, x0, y0, targ_x, targ_y, q)] = False
                    break;
    return cache


def calculate_fov(cache, max_radius, map_origin, does_map_block_predicate):
    stride = cython.declare(cython.int, max_radius * 2 + 1)
    rx0 = cython.declare(cython.int, max_radius)
    ry0 = cython.declare(cython.int, max_radius)
    mx0 = cython.declare(cython.int, map_origin.x)
    my0 = cython.declare(cython.int, map_origin.y)
    dim = cython.declare(cython.int, max_radius + 1)
    qx = cython.declare(cython.int)
    qy = cython.declare(cython.int)
    i = cython.declare(cython.int)
    mx = cython.declare(cython.int)
    my = cython.declare(cython.int)
    rx = cython.declare(cython.int)
    ry = cython.declare(cython.int)
    all_blocked = cython.declare(cython.bint)
    qy_strided = cython.declare(cython.int)
    ry_strided = cython.declare(cython.int)

    result = cache[max_radius * stride + max_radius].copy()

    # quadrant 1
    i = 1
    while i < dim:
        all_blocked = True
        qx = i
        qy = 0
        mx = mx0 + qx
        rx = rx0 + qx
        while qy < i:
            if result[qy * stride + qx]:
                all_blocked = False
                my = my0 + qy
                if does_map_block_predicate(mx, my):
                    ry = ry0 + qy
                    result &= cache[ry * stride + rx]
            qy += 1
        qy = i
        qy_strided = qy * stride
        my = my0 + qy
        ry = ry0 + qy
        ry_strided = ry * stride
        qx = 0
        while qx <= i:
            if result[qy_strided + qx]:
                all_blocked = False
                mx = mx0 + qx
                if does_map_block_predicate(mx, my):
                    rx = rx0 + qx
                    result &= cache[ry_strided + rx]
            qx += 1
        if all_blocked:
            break
        i += 1

    # quadrant 2
    i = 1
    while i < dim:
        all_blocked = True
        qx = i
        qy = 0
        mx = mx0 - qx
        rx = rx0 - qx
        while qy < i:
            if result[qy * stride + qx]:
                all_blocked = False
                my = my0 + qy
                if does_map_block_predicate(mx, my):
                    ry = ry0 + qy
                    result &= cache[ry * stride + rx]
            qy += 1
        qy = i
        qy_strided = qy * stride
        my = my0 + qy
        ry = ry0 + qy
        ry_strided = ry * stride
        qx = 0
        while qx <= i:
            if result[qy_strided + qx]:
                all_blocked = False
                mx = mx0 - qx
                if does_map_block_predicate(mx, my):
                    rx = rx0 - qx
                    result &= cache[ry_strided + rx]
            qx += 1
        if all_blocked:
            break
        i += 1

    # quadrant 3
    i = 1
    while i < dim:
        all_blocked = True
        qx = i
        qy = 0
        mx = mx0 - qx
        rx = rx0 - qx
        while qy < i:
            if result[qy * stride + qx]:
                all_blocked = False
                my = my0 - qy
                if does_map_block_predicate(mx, my):
                    ry = ry0 - qy
                    result &= cache[ry * stride + rx]
            qy += 1
        qy = i
        qy_strided = qy * stride
        my = my0 - qy
        ry = ry0 - qy
        ry_strided = ry * stride
        qx = 0
        while qx <= i:
            if result[qy_strided + qx]:
                all_blocked = False
                mx = mx0 - qx
                if does_map_block_predicate(mx, my):
                    rx = rx0 - qx
                    result &= cache[ry_strided + rx]
            qx += 1
        if all_blocked:
            break
        i += 1

    # quadrant 4
    i = 1
    while i < dim:
        all_blocked = True
        qx = i
        qy = 0
        mx = mx0 + qx
        rx = rx0 + qx
        while qy < i:
            if result[qy * stride + qx]:
                all_blocked = False
                my = my0 - qy
                if does_map_block_predicate(mx, my):
                    ry = ry0 - qy
                    result &= cache[ry * stride + rx]
            qy += 1
        qy = i
        qy_strided = qy * stride
        my = my0 - qy
        ry = ry0 - qy
        ry_strided = ry * stride
        qx = 0
        while qx <= i:
            if result[qy_strided + qx]:
                all_blocked = False
                mx = mx0 + qx
                if does_map_block_predicate(mx, my):
                    rx = rx0 + qx
                    result &= cache[ry_strided + rx]
            qx += 1
        if all_blocked:
            break
        i += 1

    return result