2009
01.12

Optimized diamond raycasting

Surprisingly, diamond raycasting is slower than standard raycasting. I removed any memory allocation and expensive container operation from the loop, and it’s still slower. Here are the last results on the same computer as the previous post :

CIRCULAR FOV time : 0.801974s => 125.939 call/s 7ms/call
DIAMOND FOV time : 1.79608s => 56.2336 call/s 17ms/call

The optimized code can be found here. Maybe someone will find a good optimization…
http://code.google.com/p/libtcod/source/browse/trunk/src/fov_diamond_raycasting.c

I have a few explanations about the result. Diamond raycasting main feature is that it visits each cell only once. So it’s supposed to be much faster than standard raycasting when the cell visiting process is long enough. When using a TCODMap, visiting the cell is only testing a boolean value, so the gain is not significant here.
Besides, diamond raycasting involves a lot of function calls. When you removed memory allocation and container access issues, function calls may still kill your performances. While standard raycasting has one function call for each cell on the perimeter (one function call for each ray casted), diamond raycasting has more than 3 function calls for each cell in the fov ! When working on big field of views (like the one used in the benchmark), this certainly has a big impact on the performances. I think the only way to get significant performance improvement (at least 50%) now is to alter the algorithm itself…

Anyway 56 calls/second on a 600×600 map is probably enough for most usages 🙂

7 comments so far

Add Your Comment
  1. Was the viewing range limited? Because if you expanded the FOV 300 cells in each direction, no wonder it turned out slow. Diamond FOV was supposed to be faster with more obstacles. Have you tried it in a corridor?

  2. No, unlimited range, no wall lighting. With more obstacles, both would be faster, and I think standard raycasting will be faster in most cases.

    For example, I just ran a test with a range of 10 cell (something that can typically happen in real games) and I get those results :
    CIRCULAR FOV time : 0.180633s => 559.145 call/s 1ms/call
    DIAMOND FOV time : 0.286258s => 352.829 call/s 2ms/call

  3. But speed is not everything. Diamond fov seems to produce more elegant fields of view. For example, pilar always project a nice shadow, while the shadow might disappear with standard raycasting.

  4. Care to present example images? I’m intrigued…

  5. A single picture might not be very descriptive here. Just download the latest libtcod beta and run the fov sample. You can switch from one algorithm to another with the same dungeon. Very convenient for comparisons 🙂

  6. Diamond FOV had some problems, as discussed here:
    http://www.gamehourz.com/Modelling-Rays-Line-Sight-Object-Rich-World-ftopict229245.html

    Have they been resolved ?

  7. I didn’t fix anything but I don’t reproduce the issue with my implementation..!