# Basic Shadow Casting, Part 2

In the last article, we looked at a field-of-view algorithm called shadow casting and implemented it for a special case: one octant of a square grid. In this article, we'll expand this partial solution to cover all directions.

The strategy for extending the solution will be to define a mapping between coordinates in the other octants and the one that we already solved and then, for each octant, apply the mapping, run our original algorithm, and map the solution back.

First, let's take a look at the new shadow-casting algorithm. The logic is the same in the previous post, but:

• We've changed the coordinate names from `x`, `y` to `u`, `v` to reflect the fact that the coordinates in this algorithm are being transformed, and don't correspond to actual points in the grid.
• The algorithm runs coordinates through a coordinate mapping before checking for blocking cells or coordinates as visible or invisible; we'll look at the `OctantTransform` class in more detail below.
• The original one octant solution is looped over eight octants.
``````def get_fov(obstacles: Map) -> Map:
visible: Map = set()

mapcoord: OctantTransform

def scan(u: int, maxslope: float, minslope: float) -> None:
"""Apply shaodwcasting a 'column' `u`.

Map an octant from the map into the coordinates for the first
octant and apply shadowcasting. The mapping is applied so that
the shadowcasting algorithm can be kept simple.
"""

if u >= MAPSIZE:
return

startv = int(u * maxslope)
endv = max(0, round(u * minslope))

blocked = mapcoord.reverse((u, startv)) in obstacles
newmax = maxslope

for v in range(startv, endv - 1, -1):
uv = (u, v)
if mapcoord.reverse(uv) in obstacles:
if not blocked:
blocked = True
scan(u + 1, maxslope=newmax, minslope=endslope(u, v))
else:
continue
else:
if blocked:
blocked = False
newmax = startslope(u, v)
else:
else:
if not blocked:
scan(u + 1, maxslope=newmax, minslope=minslope)

for octant in range(1, 9):
mapcoord = OctantTransform(octant)
scan(1, 1.0, 0.0)

return visible
``````

Next, let's take a look at the `OctantTransform` class. The octants are numbered from one to eight, starting at the x-axis and going counter-clockwise (an arbitrary arrangement, but one that's was conventional in my math education). We define three transformations that move points around in this space: reflecting points across the X or Y axes, or reflecting points across the line where X = Y. Next, we assign each octant a list of transformations to map it to the first octant, where we can run our algorithm. These mappings have the lovely property that you can run the backwards to map solutions back to their original location.

``````def reflect_x(p: Point) -> Point:
u, v = p
return -u, v

def reflect_y(p: Point) -> Point:
u, v = p
return u, -v

def flip_xy(p: Point) -> Point:
u, v = p
return v, u

TRANSFORMS: ty.Dict[int, ty.List[PointFn]] = {
1: [],
2: [flip_xy],
3: [flip_xy, reflect_y],
4: [reflect_x],
5: [reflect_y, reflect_x],
6: [flip_xy, reflect_x, reflect_y],
7: [flip_xy, reflect_x],
8: [reflect_y],
}

class OctantTransform:
def __init__(self, octant: int):
assert octant in range(1, 9), "Invalid octant: {}".format(octant)
self.octant = octant
self.transforms: ty.List[PointFn] = TRANSFORMS[octant]

@classmethod
def apply_transforms(cls, p: Point, fns: ty.Iterable[PointFn]) -> Point:
from functools import reduce

for f in fns:
p = f(p)
return p

def reverse(self, p: Point) -> Point:
return self.apply_transforms(p, reversed(self.transforms))

def __call__(self, p: Point) -> Point:
return self.apply_transforms(p, self.transforms)
``````

The full code (including tests and an improved map-printing function) can be found here.

In the final article, we'll look at adding another transform to let us calculate field-of-view from points other than the origin.