FOV

I’ve been coding a little roguelike this past week and I just got around to looking at FoV algorithms. Now, many of these algorithms I found hard to understand, but after some trial and error I figured out an easy way (in my mind!) for it to work. Now I’m curious, has anyone else used this technique too? I didn’t see it listed on roguebasin.

Conceptually, it is an optimization over a method that traces hundreds of rays from the player outward. Instead of tracing the rays while the game is running, the work is done beforehand and stored in a static lookup table. The in-game algorithm does a few bitwise operations on the table to determine which rays have been blocked.

The set of rays used to generate the lookup table determine how your FoV looks. Originally, my rays were straight lines from the center to perimeter coordinates. While this may seem sufficient, the results were actually rather ugly and contained artifacts. There were too many squares being marked unseen in unreasonable places. What I needed was permissive FoV. To do this, I used a modified version of Bresenham’s line algorithm that iterated every possible line and sub-line that I cared about. This turned out to work perfectly.

Here’s a few comments I wrote in the source file. Sorry if my explanations are bad; if you want to see the source code, perhaps I’ll make it publicly available on Bitbucket.

// This file generates a lookup table for a fast permissive field of view
// algorithm.
//
// The table is in the octant shaded by '#':
// +-x------>
// y\########
// | \#######
// |  \######
// |   \#####
// v    \####
//
// A higher-level description of the algorithm is as follows:
// We begin by finding every unique "ray" in the octant.
// The rays start at the origin and emanate outwards.
// We give each ray a unique index number to identify it.
// Then, for every coordinate that the ray passes through, we add the ray's
// index to a set belonging to that coordinate.
//
// Finding the LOS is easy with this array of sets: Iterate every coordinate
// in the the octant starting from the center and moving outwards.
// If the coordinate contains a wall, look at what rays belong in its set.
// Since you are iterating outwards, you now know that every ray in that
// set will be blocked in future iterations too. Thus, every ray in that
// set can be considered "dead". Now, for future iterations, the "live"
// rays of a coordinate will be the set belonging to the coordinate _minus_
// the set of previously iterated "dead" rays. If a coordinate has zero "live"
// rays, then it will not be visible.
//
// In practice, this algorithm can be done efficiently using bitwise
// operations. Each ray is given a unique bit flag, and each coordinate set
// is represented by the bitwise OR of every passing ray's flag.
// Calculating the LOS uses bitwise 'AND's to compare "dead" rays to "live"
// rays.

Note: I looked at DCSS’s FoV code quite a bit before doing this, but I couldn’t grok it. I do know it involves lots of precomputation though. Perhaps it’s the same as my version?

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s