Sunday, April 05, 2009

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 600x600 : 2.36 times faster than shadowcasting
Empty 100x100 : 4.28 times faster than shadowcasting
Empty 20x20 : 3.2 times fasters than shadowcasting
Full 600x600 : 1.38 times faster than shadowcasting
Full 100x100 : 1.9 times faster than shadowcasting
Full 20x20 : 1.39 times faster than shadowcasting
Outdoor 600x600 : second fastest (1.24 times slower than basic raycasting)
Outdoor 100x100 : 1.18 times faster than basic raycasting
Outdoor 20x20 : 1.28 times faster than basic raycasting
Cave 80x80 : 1.36 times faster than shadowcasting

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