# Basic Shadow Casting, Part 3

This is the final article in a series about shadow casting. The first article covered a solution that worked for a portion of the field of view. The second article extended the solution to cover the whole field of view.

The solutions in previous articles always checked line-of-sight to the grid's origin (with x,y coordinate 0,0).This article will finish the solution by adding the ability to check line-of-sight for any point in the grid. Our strategy will be to add a transformation to the algorithm that changes its starting point, much like we did to solve the problem of covering different directions.

Some changes to the code are highlighted here; the full code is available here.

To begin, we define a base transformation class so that we can handle transformations generically.

``````import abc

class BaseTransform(abc.ABC):
@abc.abstractmethod
def __call__(self, p: Point) -> Point:
raise NotImplementedError

@abc.abstractmethod
def reverse(self, p: Point) -> Point:
raise NotImplementedError
``````

Because it already implements this interface, the `OctantTransform` from the previous article can inherit this base class without other changes.

Next, we define an `OffsetTransform` class that will let us move points around by specifying `x` and `y` offsets as a `Point`.

``````class OffsetTransform(BaseTransform):
def __init__(self, offset: Point) -> None:
self._offset = offset

def __call__(self, p: Point) -> Point:
dx, dy = self._offset
x, y = p
return (x + dx, y + dy)

def reverse(self, p: Point) -> Point:
dx, dy = self._offset
x, y = p
return (x - dx, y - dy)
``````

One final transform: because we want to combine an offset transform and the original octant transform, we'll define a `CompoundTransform` that takes a list of transformations and applies them together.

``````import functools

class CompoundTransform(BaseTransform):
def __init__(self, transforms: ty.Iterable[BaseTransform]) -> None:
self._transforms = list(transforms)
self._reversed_transforms = list(reversed(self._transforms))

def __call__(self, p: Point) -> Point:
return functools.reduce(lambda p, t: t(p), self._transforms, p)

def reverse(self, p: Point) -> Point:
return functools.reduce(
lambda p, t: t.reverse(p), self._reversed_transforms, p
)
``````

Putting these together (with some of the code from previous articles) our shadow casting function can now take a `Point` to calculate field of view from. Each for each octant we combine the offset transformation with the octant transformation.

``````def get_fov(obstacles: Map, frompoint: Point) -> Map:
visible: Map = set()

orig_x, orig_y = frompoint
origintransform = OffsetTransform((-orig_x, -orig_y))

mapcoord: BaseTransform

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 = CompoundTransform(
[origintransform, OctantTransform(octant)]
)
scan(1, 1.0, 0.0)

return visible
``````

With that final addition, our shadow casting code can now calculate field-of-view relatively efficiently for any point in our map. Hopefully working through this series has helped you get a sense of how the algorithm works.

Depending on your application, you might want to investigate things like tuning the view distance, how it interacts with different geometries, and how it changes if you tune different parameters. Those decisions will depend on your application, so I'll leave them to you.

An index of code listings for this series, as well as a fleshed out example with tests and a demonstration using bearlibterminal is available on Bitbucket.