# Difference between revisions of "FOV using recursive shadowcasting - improved"

Line 1: | Line 1: | ||

Code and improvement for recursive shadowcasting | Code and improvement for recursive shadowcasting - Henri Hakl | ||

1. Introduction | 1. Introduction | ||

This text expands the article by Bj? | 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 | shadowcasting". The article in question is excellent and describes one of the | ||

best visibility determination algorithms for roguelike environments. | best visibility determination algorithms for roguelike environments. | ||

The reader is encouraged to read Bj? | The reader is encouraged to read Bj????rn's article, as this text assumes that the | ||

reader knows the method described. This text offers a subtle improvement to 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 | algorithm as well as pseudocode. The improvement is primarily one that allows | ||

Line 15: | Line 14: | ||

algorithm. | algorithm. | ||

To outline, Bj? | To outline, Bj????rn describes an improvement to Gordon Lipford's shadowcasting | ||

article "Computing LOS for Large Areas" by making use of recursive computation. | article "Computing LOS for Large Areas" by making use of recursive computation. | ||

Shadowcasting divides the Field of View (FOV) into eight sections and traces | Shadowcasting divides the Field of View (FOV) into eight sections and traces | ||

Line 23: | Line 22: | ||

of cells on the boundaries of sections). | of cells on the boundaries of sections). | ||

Bj? | 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 | drawn ASCII art. He omits to offer code in the article, but on-site resources | ||

offer an implementation that should suffice for many. | offer an implementation that should suffice for many. | ||

Line 30: | Line 29: | ||

2. Improvement | 2. Improvement | ||

Each recursion in the algorithm described by Bj? | 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 | 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 | because any regions closer to the starting point are already finished, and |

## Revision as of 22:08, 17 January 2007

Code and improvement for recursive shadowcasting - Henri Hakl

1. 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, 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.

2. 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

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;