FOV using recursive shadowcasting - improved

Code and improvement for recursive shadowcasting - Henri Hakl

Introduction

This text expands the article by Björn Bergström called "FOV using recursive shadowcasting". The article in question is excellent and describes one of the best visibility determination algorithms for roguelike environments.

The reader is encouraged to read Björn's article on LOS, as this text assumes that the reader knows the method described. This text offers a subtle improvement to the algorithm as well as pseudocode. The improvement is primarily one that allows a more elegant representation, it does not influence the efficiency of the algorithm.

To outline, Björn describes an improvement to Gordon Lipford's shadowcasting article Computing LOS for Large Areas by making use of recursive computation. Shadowcasting divides the Field of View (FOV) into eight sections and traces the rows or columns in the sections according to simple laws that ensure that a minimum of cells need to be investigated: Cells determined to be in shadow are skipped and cells are generally only visited once (with possible exception of cells on the boundaries of sections).

Björn proceeds to explain finer mechanics in considerable detail and with well drawn ASCII art. He omits to offer code in the article, but on-site resources offer an implementation that should suffice for many.

Improvement

Each recursion in the algorithm described by Björn loops through rows/columns until a break condition is met (row/column ends with obstruction). This works because any regions closer to the starting point are already finished, and areas further away are (if appropriate) handled by recursive calls to the shadowcasting code.

For the sake of elegance this breaking condition can be handled differently: Instead of looping if the break-condition isn't met, it facilitates code readability to simply create a recursive call to the shadowcaster. The change does not influence things on an efficiency level, however it does clean up the code somewhat.

Partial pseudocode, describes one octant:

 Scan(depth, startslope, endslope)
 
   init y
   init x

   while current_slope has not reached endslope do
     if (x,y) within visual range then
       if (x,y) blocked and prior not blocked then
         Scan(depth + 1, startslope, new_endslope)
       if (x,y) not blocked and prior blocked then
         new_startslope
       set (x,y) visible
     progress (x,y)

   regress (x,y)

   if depth < visual range and (x,y) not blocked
     Scan(depth + 1, startslope, endslope)
 end

Pascal Implementation

The following code excerpt comes from my own implementation in Turbo Pascal:

• mv -> global describing view distance
• mw -> mv * mv

Octants are divided as follows:

    \ 1 | 2 /
   8         3
   --       --
   7         4
    / 6 | 5 \

function GetSlopeStd(x1, y1, x2, y2 : single) : single;
begin
  GetSlopeStd := (x1 - x2) / (y1 - y2);
end;

function GetSlopeInv(x1, y1, x2, y2 : single) : single;
begin
  GetSlopeInv := (y1 - y2) / (x1 - x2);
end;

function GetVisDistance(x1, y1, x2, y2 : integer) : integer;
begin
  GetVisDistance := (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
end;

procedure RecursiveVisibility(e : PCreature; oct, depth : integer; slopeA, slopeB : single);
var
  x, y : integer;
begin
  case oct of
    1 : begin
      y := e^.y - depth;                                                { initialize y }
      x := round(e^.x - slopeA * depth);                                { initialize z }
      while GetSlopeStd(x, y, e^.x, e^.y) >= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x - 1, y].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 1, depth + 1, slopeA, GetSlopeStd(x - 0.5, y + 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x - 1, y].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeStd(x - 0.5, y - 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        inc(x);
      end;
      dec(x)
    end;
    2 : begin
      y := e^.y - depth;                                                { initialize y }
      x := round(e^.x - slopeA * depth);                                { initialize z }
      while GetSlopeStd(x, y, e^.x, e^.y) <= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x + 1, y].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 2, depth + 1, slopeA, GetSlopeStd(x + 0.5, y + 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x + 1, y].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeStd(x + 0.5, y - 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        dec(x);
      end;
      inc(x)
    end;
    3 : begin
      x := e^.x + depth;                                                { initialize y }
      y := round(e^.y + slopeA * depth);                                { initialize z }
      while GetSlopeInv(x, y, e^.x, e^.y) <= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x, y - 1].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 3, depth + 1, slopeA, GetSlopeInv(x - 0.5, y - 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x, y - 1].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeInv(x + 0.5, y - 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        inc(y);
      end;
      dec(y)
    end;
    4 : begin
      x := e^.x + depth;                                                { initialize y }
      y := round(e^.y + slopeA * depth);                                { initialize z }
      while GetSlopeInv(x, y, e^.x, e^.y) >= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x, y + 1].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 4, depth + 1, slopeA, GetSlopeInv(x - 0.5, y + 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x, y + 1].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeInv(x + 0.5, y + 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        dec(y);
      end;
      inc(y)
    end;
    5 : begin
      y := e^.y + depth;                                                { initialize y }
      x := round(e^.x + slopeA * depth);                                { initialize z }
      while GetSlopeStd(x, y, e^.x, e^.y) >= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x + 1, y].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 5, depth + 1, slopeA, GetSlopeStd(x + 0.5, y - 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x + 1, y].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeStd(x + 0.5, y + 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        dec(x);
      end;
      inc(x)
    end;
    6 : begin
      y := e^.y + depth;                                                { initialize y }
      x := round(e^.x + slopeA * depth);                                { initialize z }
      while GetSlopeStd(x, y, e^.x, e^.y) <= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x - 1, y].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 6, depth + 1, slopeA, GetSlopeStd(x - 0.5, y - 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x - 1, y].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeStd(x - 0.5, y + 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        inc(x);
      end;
      dec(x)
    end;
    7 : begin
      x := e^.x - depth;                                                { initialize y }
      y := round(e^.y - slopeA * depth);                                { initialize z }
      while GetSlopeInv(x, y, e^.x, e^.y) <= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x, y + 1].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 7, depth + 1, slopeA, GetSlopeInv(x + 0.5, y + 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x, y + 1].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeInv(x - 0.5, y + 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        dec(y);
      end;
      inc(y)
    end;
    8 : begin
      x := e^.x - depth;                                                { initialize y }
      y := round(e^.y - slopeA * depth);                                { initialize z }
      while GetSlopeInv(x, y, e^.x, e^.y) >= slopeB do begin            { while in octant }
        if GetVisDistance(x, y, e^.x, e^.y) <= mw then begin            { if within max visual range }
          if WorldSurface[x, y].entity^.obstruct then begin             { if obstruction }
            if not WorldSurface[x, y - 1].entity^.obstruct then begin   { if no prior obstruction }
              RecursiveVisibility(e, 8, depth + 1, slopeA, GetSlopeInv(x + 0.5, y - 0.5, e^.x, e^.y));
            end;                                                        { ^create recursive scan }
          end else begin                                                { no obstruction }
            if WorldSurface[x, y - 1].entity^.obstruct then begin       { if prior obstruction }
              slopeA := GetSlopeInv(x - 0.5, y - 0.5, e^.x, e^.y);      { adjust slope for later recursion }
            end;
          end;
          WorldSurface[x, y].visibility := 3;                           { set block visible }
        end;
        inc(y);
      end;
      dec(y)
    end;
  end;

  if (depth < mv) and not WorldSurface[x, y].entity^.obstruct then begin   { break/continue }
    RecursiveVisibility(e, oct, depth + 1, slopeA, slopeB);
  end;
end;

C# Implementation

A C# 3.0 implementation, including source code, of the above algorithm can be found here[1].