Field of view in Javascript using recursive shadow casting

Field of view, and stuff

Field of view, which involves determining which tiles are visible to the player, is a particularly fun aspect of writing roguelikes, in my opinion. When writing a field of view algorithm, you often find yourself trading quality for performance, or vice versa. Some algorithms get around this with a bit of trickery, like the Rogue algorithm. Other algorithms have no visible artifacts and in fact are quite pleasing visually, but pay for this with a definite decrease in performance.

There have been, of course, plenty of articles written about field of vision, and there is in fact an excellent compendium of resources over at Roguebasin (you can check that out here). This is a problem that has been thoroughly solved many times, beginning with Rogue’s rudimentary solution (you can see all the tiles in the room you’re in, but nothing else is visible; when in corridors, only the corridor tiles next to you are visible). The thing is, only a few Javascript algorithms (if any) are available to calculate FOV. Since I’m writing a Roguelike and have of course come up with an algorithm of my own, I have decided to remedy this lack of JS algorithms by sharing mine with you. It’s nothing fancy, but does provide a rather nice gradient falloff, which works in tandem with the display.js library that I previously posted.

Finding the happy medium

Many FOV algorithms have been written in an attempt to find the happy medium between performance and quality. After trying a few algorithms out, I eventually settled with recursive shadowcasting, which was both optimized for maximum performance but also very few artifacts. All in all, I’m happy with my choice. Here are some of the results you can get with recursive shadowcasting combined with a gradient falloff:

Demonstration of Saege's FOVMore Saege FoV

The field of view you see here is using a radius that is roughly double that of which is found in my game in order to better display the nice lighting falloff. However, even with aforementioned smoothed lighting, performance isn’t impacted in the slightest.

Has the happy medium been found?

As I’ve mentioned before, performance is usually achieved at the cost of quality. However, I was able to find a way to boost the performance of the algorithm without impacting quality. Now, to update the lighting, most algorithms clear the map of light and reset all the tiles to “unlit” or, depending on whether the player has already seen the tiles, “unseen”, which basically means the player has seen that tile at some point but can’t currently see it. The lighting algorithm then calculates the tiles within the player’s field of view and sets those tiles to “visible”, and the rendering engine displays them as lit up. Pretty straightforward.

The difference in my algorithm is that instead of clearing the entire map, it only sets to “unseen” those tiles which were lit the previous turn. This means that loads of CPU cycles aren’t wasted trying to reset the entire map’s lighting, most of which is outside the player’s field of view anyways. The algorithm simply appends each tile that is set to “visible” to an array, which is stored. When the lighting is next updated, those tiles in the array, and only those tiles, are set to “unseen” and the algorithm proceeds to calculate lighting as normal; wash, rinse, repeat, and you’ve got yourself one quick little field of view algorithm.

If you’ve stuck with me this long…

…you must be interested in seeing the algorithm. So, without further ado, here it is. It’s been sparsely commented, but hopefully should be of some help to some of you. And, as before, the LightSource class which contains the algorithm does make use of some external functions, which I will be introducing to you later on as progress on my game continues. And, before I forget, here’s a demo demonstrating its use.

Hopefully this article has given you something to think about, and, as always, feel free to comment and let me know if I’ve made any mistakes or typos!