2009
04.05

The FOV Graal !!!!

Some of you might have read the fov study I did a few months ago.
http://roguecentral.org/libtcod/fov/fov.pdf

My goal was to find the best fov algorithm for libtcod, on both gameplay and speed sides. Unfortunately, every algorithm I checked had some drawbacks.
It seems that Mingos, developer of Umbrarum Regnum has just found something that really looks like the fov graal, getting almost a perfect result on every test. We still have to check that there is no hidden glitch, and the code has still to be polished and optimized, but it’s already beating the other algorithms to a pulp…

  • It has a perfect behaviour in every gameplay test of the study (see some of the screenshots below).
  • It has an acceptable symmetry, as good as the best non-symmetrical algorithms.
  • Its speed blows away other algorithms.

Once again, this has still to be double-checked, but restrictive fov will definitely make its way to libtcod 1.4.2 and 1.5. I’ll publish an updated version of the fov study including restrictive shadowcasting when I find some time… 😉

Detailed results :

Symmetry :
Outdoor : 5.25 %
Indoor : 0.91%

Speed :
Empty 600×600 : 2.36 times faster than shadowcasting
Empty 100×100 : 4.28 times faster than shadowcasting
Empty 20×20 : 3.2 times fasters than shadowcasting
Full 600×600 : 1.38 times faster than shadowcasting
Full 100×100 : 1.9 times faster than shadowcasting
Full 20×20 : 1.39 times faster than shadowcasting
Outdoor 600×600 : second fastest (1.24 times slower than basic raycasting)
Outdoor 100×100 : 1.18 times faster than basic raycasting
Outdoor 20×20 : 1.28 times faster than basic raycasting
Cave 80×80 : 1.36 times faster than shadowcasting

Cave 40×40 : first ex-aequo (as fast as shadow casting)
Cave 20×20 : 1.13 times faster than shadowcasting

5 comments so far

Add Your Comment
  1. mmmm cool.
    i wonder how it works… Hopefully mingos will write an article explaining how it works and why it is so fast.

  2. What do the red and blue squared indicate in the diagrams?

  3. They’re explained in the pdf study.
    On symmetry diagram, these are cells where the fov is not symmetric.
    On the corner peeking map, blue cells are where the player can see the T junction cell

  4. theotherhiveking:
    The article is in preparation. I didn’t have time to write it yesterday, but definitely it’ll be ready this week. I’ll post a comment here as well to notify you.

  5. The article explaining how MRPAS works can be found under the following addresses:

    http://umbrarumregnum.110mb.com/art9_fov.php

    and

    http://roguebasin.roguelikedevelopment.org/index.php?title=Restrictive_Precise_Angle_Shadowcasting