LOS using strict definition

FOV using strict definition - BBQsauce [arthurhavlicek@gmail.com]

Introduction

This article aim for developers looking for elegant fov solution to implement themselves.

When looking for fov algorithms i was sure hoping there was the "simple and obvious way" to do things. There is not. In fact, there close to a dozen of fov implementations to choose from. The choice you make must depend of your programming skills and the desired behavior of your algorithm - because there is several desired behaviors. If you haven't yet, check out Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds which is a great article to start with. In this article, we'll focus on corner-peeking behavior ; this is really the core problem of fov.

What we want

########
.@......
####O###
---#.#--

Thre majors definition of fov are facing :

- @ and O see each other : see Permissive_Field_of_View

- @ see 0 and the reverse is false : see Shadow casting

- Neither @ and O see each other, you're at the right place.

This imply the following :

#......
#...@..
-######

I can't see the room corner here, because I'm too close to the wall. This is realistic, but that also mean your room won't lit completly as soon as you enter it.

How we do

My solution is iterative and rely on vectors. Reduced to a single wall, it works as follow :

A tile is in not visible if it's center vector is between the two vectors defining a wall tangeant (walls are round as you can see). Every time a wall hide a tile this way, it's lit. Note that a vector can be hid by several walls ; in this case, only the closest wall will be lit.

In a more detailed form :

- Iterate all fov a first time to list every wall position.
- Sort walls by ascending distance to source
- Iterate all fov a second time
  * Build source-tile vector; calculate it's norm and atan2
  * For every wall found :
    * If the distance to wall is superior to distance to tile, we break
    * Tangeants atan2 to a wall is wall atan2 +- asin (0.5/wall distance)
    * The source-tile vector is in shadow if it's norm is superior to wall distance and it's atan2 is (inferior to 1st tangeant and superior to 2nd) or (inferior to 1st tangeant -2pi and superior to 2nd -2pi).
    * If it's in shadow, we lit the wall, shadow the tile, break; else we check next wall.
  * If we haven't breaked from for loop, we have to lit the tile.

Efficiency

The efficiency is comparable to most fov computing algorithm, which are in general O(radius ^ 3). This is fairly high and should be avoided to be fully calculated for non-PC characters. Instead, you should only calculate visibility of a single tile when needed.

Fortunately, you don't have to build walls list for a single tile check ; instead, build a line from source to destination with Bresenham's Algorithm. If the line go through a wall, it's obstructed; simple isn't it ?