Further shadowcasting optimizations #23373
Labels
Code: Performance
Performance boosting code (CPU, memory, etc.)
Info / User Interface
Game - player communication, menus, etc.
(P5 - Long-term)
Long-term WIP, may stay on the list for a while.
Z-levels
Levels below and above ground.
Projects
Discussed a major overhaul to shadowcasting with OrenAudeles on the discord server.
There are a number of adjustments we discussed, some of which may or may not yield a speedup.
The most central change is replacing the current iteration-with-recursion-on-nested-spans with a purely iterative approach.
As each row of an octant is processed, it writes the visibility data as usual, but when a new span is detected, it stashes it in a queue instead of recursing into it immediately. As a result, it proceeds in a breadth-first fashion, resulting in much higher cache coherency, it's possible it can achieve only one cache miss per cache line.
This should also extend to 3D shadowcasting, by arranging the array in the order in which the algorithm iterates over it.
A number of further optimizations to this are possible:
Store the octant data (both inputs and outputs) in a group of arrays instead of a single array. This may make writing the octants less efficient, but will make the shadowcasting algorithm itself much faster if it can proceed in row-major order instead of column-major order in half of the octants.
These octant arrays can further be triangular arrays where lookup into the array uses a custom calculation. This will reduce memory overhead, and further improve cache locality.
Represent angles (and hence spans) as fractions instead of FP numbers, or possibly as tile numbers.
Along with #22721, we could store the queue state when an area has been scanned, and if the player scrolls to reveal a new area quickly continue calculating the FoV using the stored spans.
The text was updated successfully, but these errors were encountered: