Its been a while! This time I’ve made a lot of tweaks to the Line of Sight code so that items can correctly and efficiently occlude unit vision and implemented pathfinding using flowfields for smoother unit motion. Both items took quite a bit longer than I had anticipated and are probably still quite slow, but I’m happy with how they are looking. This post will talk about the vision blockers; I’ll leave pathfinding for the next.
Some code existed in the previous build for entities to write their blocking height to a grid covering the game world. This grid tracks the highest unit on each cell and blocks sight for all shorter units. The RevealLOS method has been rewritten to now more accurately read this data and project “shadows” outward to hide areas of terrain. The algorithm has two distinct phases.
Pass 1 – Occlusion angles
The first pass iterates through all tiles within the reveal radius, ordered by their occurrence when sweeping clockwise. Think of this as a radar, which pings for each cell as the detector passes them. This ordering is important to keep the input clean and reduce the amount of work needed later.
Each cells height is compared against the current units height, if the cell is too high, it is added to an ordered list of blocking cells (ordered the same as the iteration, clockwise around the unit). The distance and angles for where the blocked vision starts and stops are also cached. A small optimisation pass is done on this data to remove cells that are eclipsed by other cells nearer to the unit center; these are redundant, since any terrain they occlude will already be occluded by the nearer cells.
Pass 2 – Terrain reveal
The next pass iterates over all tiles within the reveal radius, determines their distance and start/end angles, and looks through the previous list of occlusion cells to determine how much of the tile is occluded. As the occlusion items are ordered, iterating this list forward and shrinking the visible arc is sufficient to correctly calculate occlusion for the left-most angle. This is then repeated in reverse for the right side.
The result of this calculation is four angles; the tiles initial start and end angles relative to the unit, and the unoccluded start and end angles. The visibility of each tile is simply the unoccluded arc size divided by the total tile arc size.
Trigonometry functions are expensive to execute, so “angles” here are approximations. A full circle in this system is 8 degrees, and calculating the angle of a vector is simply determining what quadrant it is in, and then dividing the coordinates.
It is impossible for the arc of a nearer cell to be smaller than a farther cell it is projecting onto. If this were not the case, it could be possible for small arcs to lie entirely within a tiles arc, and be ignored by the system.