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
y offsets as a
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) visible.add(mapcoord.reverse(uv)) else: visible.add(mapcoord.reverse(uv)) 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.
Thanks for your attention. 😊