FOV Calculations

Posted by Naelstrof on January 21, 2016

Working on a space station 13 clone with a friend, I had the challenge of developing FOV. The term FOV in top-down RPG games usually refers to determining which tiles are visible.

My first idea was to just raytrace from the player, marking every tile hit visible. So I ripped out the Bresenham algorithm and traced to every tile on the perimeter of the screen. This method seemingly works great!


There's two problems though, column shadows have gaps, and walls get random splotches of shadows as well.

column gaps

You can see that the Bresenham lines increment at the perfect time to dodge the column, making some unrealistic shadows.

wall gaps

There's just not enough rays to hit every part of the wall, and it's unfeasible to just add more rays...

There's other FOV calculation methods other than ray tracing, but most of them are convoluted and confusing, and so I devised my own solutions to fix these artifacts.

Wall Gaps Solution

This problem was a little more complex, I understood that if any part of a perfectly flat wall is visible: the whole wall would be visible. I first had to develop a tool that could interpret if a group of wall tiles is a wall, and which direction that wall is facing. To do this I realized I just need the hit-normals of the casted rays. In most other games, when you do a ray-trace you recieve a hit-normal so you can tell what kind of surface it hit. In a 2D game about spess men, it's a little more complex since "walls" are a pretty arbitrary concept with 2D tiles. For example a single solid tile wouldn't be a wall, it would be a column. Do two tiles in a row make up a wall? Do three tiles in a corner configuration make up two walls? To solve this what I did was when a ray hits a solid tile, it checks adjacent tiles and put them in a flag like this:

o = center
# = adjacent

So if the flag is 3 then it would indicate we have 3 tiles in a straight line. While 5 would indicate a SE corner tile. From there it's pretty easy to set up a switch statement to handle hit normal calculations separately.

With this new powerful tool, it's fairly simple to detect when a wall is hit. The normal just has to be pointing in a cardinal direction to know we hit a "wall". You can see it in action from the blue lines in all of the images.

From there we can trace the wall, marking every tile visible until we hit a corner, an already visible tile, or if the wall ceases to be visible due to obstructions (a quick raytrace back, offset by the hitnormal can do this for us) fixing our wall gaps!

wall gaps

Seems like it would be really inefficient, but because a wall trace often terminates immediately, it hardly makes a difference in speed.

Column Gaps Solution

Lua as two values that evaluate as false: false and nil. I abuse this feature to mark certain tiles as "forbidden", disallowing them to be marked visible for the current frame. With my hit normal tool, it's pretty simple to set tiles behind columns as forbidden. Which fixes our column gaps!

no more column gaps

With that my FOV calculations work pretty well, and it was fun to work on.

Views: 117