/ 
Game-RaycastFOV-2.03
River stage zero No dependents
/ Game::RaycastFOV

NAME

Game::RaycastFOV - raycast field-of-view and related routines

SYNOPSIS

use Game::RaycastFOV qw(
  bypair circle line
  cached_circle swing_circle
  raycast shadowcast
);

# mostly internal utility routine
bypair( { my ($x,$y) = @_; ... } $x1, $y1, $x2, $y2, ... );

# Bresenham in XS
circle( { my ($cx,$cy) = @_; ... } $x, $y, $radius );
line(   { my ($lx,$ly) = @_; ... } $x, $y, $x1, $y1 );

# fast, slower circle constructions
cached_circle( { my ($cx,$cy) ... } $x, $y, $radius );
swing_circle(  { my ($cx,$cy) ... } $x, $y, $radius, $swing );

# complicated, see docs and examples
raycast( \&circle, sub { ... }, $x, $y, ... );
shadowcast( ... );

DESCRIPTION

This module contains various subroutines that perform fast calculation of lines and circles; these in turn help with Field Of View (FOV) calculations. Raycasting and shadowcasting FOV calls are provided.

Speed is favored over error checking; the XS code may not work for large integer values; etc.

Raycasting Explained in One Thousand Words or Less

     .#.##
   .##.#####                 #
  #.##..##...                #.
 .##.#.##.#...               #.
 #####..#.####             # #.
.#.#.#.###.##..            #.#.##
####....#.##...            #....#
##...#.@#T...##              #.@#
#..#.###....#.#              ###..
.##.#####..#...                 #..
 .##...####.##                   ##.#
 ....#.###.#..                      .
  ###.###.#..
   .######.#
     ....#

Will our plucky hero stumble into that Troll unseen? Tune in next week!

FUNCTIONS

bypair callback ...

Utility function for slicing up an arbitrary list pairwise. Sort of like pairwise of List::Util only in a void context, and that returning the value -1 from the callback subroutine will abort the processing of subsequent items.

bypairall callback ...

Like bypair but does not include code to abort processing the list.

Since v1.01.

cached_circle callback x y radius

This routine looks up the radius in the %circle_points variable (which is available for export and can be modified as need be) to obtain a pre-computed list of circle points (calculated by swing_circle) that are fed to the callback as is done for the circle call.

Will silently do nothing if the radius is not found in the cache. This is by design so that cached_circle is fast.

The cached points might (but are unlikely to) change without notice; calling code if paranoid should set specific sets of points to use or require a specific version of this module.

circle callback x y radius

Bresenham circle. Note that this may not produce a completely filled-in FOV at various radius.

Since version 2.02 only unique points are passed to the callback.

line callback x0 y0 x1 y1

Bresenham line. Returning the value -1 from the callback subroutine will abort the processing of the line at the given point.

raycast circle-fn point-fn x y ...

Given a circle-fn such as circle or swing_circle and the center of a circle given by x and y, the raycast calls line between x,y and the points returned by the circle function; line in turn will call the user-supplied point-fn to handle what should happen at each raycasted point. Additional arguments ... will be passed to the circle-fn following x and y.

"EXAMPLES" may be of more help than the above text.

shadowcast x y radius blockcb litcb radiuscb

Performs a shadowcast FOV calculation of the given radius around the point x, y. Callbacks:

  • blockcb is called with newx, newy (the point shadowcasting has reached), deltax, and deltay (the delta from the origin for the point). It return a boolean indicating whether that coordinate is blocked on the level map (e.g. by a wall, a large monster, or maybe the angle from the starting point is no good, etc).

    The deltax and deltay values are only passed in module version 2.02 or higher.

  • litcb is called with newx, newy, deltax, and deltay and should do whatever needs to be done to present that point as visible.

  • radiuscb is passed deltax, deltay, and radius and must return true if the deltas are within the radius. This allows for different FOV shapes. The delta values could be negative so will need to be run through abs or ** 2 to determine the distance.

The callbacks may be called with points outside of a level map.

sub_circle callback x0 y0 radius swing start-angle max-angle

Finds points around the given radius by rotating a ray by swing radians starting from start-angle and ending at max-angle. Smaller swing values will result in a more complete circle at the cost of additional CPU and memory use. Each unique point is passed to the callback function:

sub_circle( sub { my ($newx, $newy) = @_; ... }, ... );

Has limited to no error checking; the caller should ensure that the swing value is positive, etc.

Since version 2.02.

swing_circle callback x0 y0 radius swing

Calls sub_circle with a starting angle of 0 and a max angle of pi * 2.

Prior to version 2.02 used distinct code.

EXAMPLES

See also the eg/ directory of this module's distribution.

https://thrig.me/src/ministry-of-silly-vaults.git has a FOV subdirectory with example scripts.

use Game::RaycastFOV qw(circle raycast swing_circle);
use Math::Trig 'deg2rad';

# to only draw within the map area
our $MAX_X = 79;
our $MAX_Y = 23;

# assuming a rows/columns array-of-arrays with characters
our @map = ( ... );
# something that updates the @map
sub plot { ... }
# where the FOV happens and how big it is
my ($x, $y, $radius) = ...;

raycast(
  \&circle, sub {
    my ($lx, $ly) = @_;
    # whoops line has wandered outside of map
    return -1 if $lx < 0 or $lx > $MAX_X
              or $ly < 0 or $ly > $MAX_Y;
    # may instead build up a string to print to terminal
    my $ch = $map[$ly][$lx];
    plot($lx, $ly, $ch);
    # abort the line if FOV is blocked
    return -1 if $ch eq '#';
  }, $x, $y, $radius
);

# or instead using swing_circle
raycast(
  \&swing_circle, sub {
    my ($lx, $ly) = @_;
    return -1 if $lx < 0 or $lx > $MAX_X
              or $ly < 0 or $ly > $MAX_Y;
    my $ch = $map[$ly][$lx];
    plot($lx, $ly, $ch);
    return -1 if $ch eq '#';
  }, $x, $y, $radius, deg2rad(5)      # different arguments!
);

The plot routine may need to cache whether something has been printed to the given cell as raycast likes to revisit cells a lot, especially those close to the origin that are clear of FOV-blocking obstacles.

BUGS

None known. Raycast is problematic, but that's probably baked into to algorithm, which is why other methods of FOV were invented.

SEE ALSO

Game::Xomb uses modified code from this module.

NetHack::FOV

https://thrig.me/src/ministry-of-silly-vaults.git

There are other FOV algorithms and implementations to be found on the Internet.

COPYRIGHT AND LICENSE

This software is Copyright (c) 2020 by Jeremy Mates.

This is free software, licensed under:

The (three-clause) BSD License