Monday, January 12, 2009

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...

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 600x600 map is probably enough for most usages :)