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.
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:
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!
I can’t seem to get this working. Could you set up a live demo?
Sure, although it might take a little while for me to get to it. What exactly seems to be the problem?
[…] little while back, somebody asked me if I could turn the shadowcasting algorithm I posted here into a working demo. After a bit of fiddling around I set up a demo using the <canvas> tag […]