Monday, 9 July 2012

Field of vision on heightmaps, part 1

Spent the day researching field of vision algorithms. I've had a look round that part of roguebasin a few times before, but so far I've not made any games that needed anything more complex than simple Bresenham lines. All my previous games had a hard limit on the player's sight radius and only drew the FOV once per turn, though. Here, not only will sight range be bounded only by the map (because if you're standing on a hill you should be able to see an army on the other side of the map). I'll also need to (occasionally) calculate FOV for non-player actors, to allow scouts to report what they see and to allow groups to detect enemies they could engage or avoid.

Someone pointed me to an algorithm that only checks each tile once, and which doesn't check obstructed tiles. It's quite attractive to check as few tiles as possible, when there are so many on such a large, open map. At the moment it's 512x512, and if I decide to make formations looser by default (in order to make tight formations more meaningful and facilitate friendly formations moving through each other) then that might go up to 1024x1024. Most of the FOV algorithms around check some tiles more than once, which obviously isn't desirable on such a map.

For instance, one algorithm draws a Bresenham line to each point on the border of the viewable area. Near the borders you'll have just one ray passing through each tile, which is nice, but near the centre you'll have several rays passing through, checking the central tiles more than once!

A few pages of a notepad, and it turns out that for a square map, the number of times a tile is checked depends on where in the map you stand. In the very corner, the number of tiles checks will be 3 times the number of tiles on the map, in the middle of the border it'll be 2.25 the number of tiles, and in the centre it'll be 1.5 times. Because there aren't any obstacles that guarantee there's nothing in FOV behind them, every tile has to be checked. So, which algorithm to prefer depends on how expensive it is to process a tile under the different schemes (and whether it's any cheaper to skip over an already-checked tile).

LibTCOD has both of these algorithms (unfortunately not in a form I can use directly, since it deals with definite obstructions rather than heightmaps), and apparently it's faster to cast rays to every point on the border (and it would still be faster if the rays were cast from the corner of the map). Since the diamond raycasting algorithm is more difficult to understand, more difficult to implement, and slower in the implementations that already exist, I think I know which one I'm going to try first.

Or ever.

Part 2 when I've implemented at least one FOV algorithm.

Also:
I think I could totally get away with grouping tiles into 2x2, 4x4, 8x8 or 16x16 squares as distance from the observer increases. It would definitely work well with the minimap, and it would save a huge number of tile checks allowing more actors per second to have their FOV calculated. If the player scrolls to some faraway area then the calculations can be done at the single-tile scale there.

The only problem I anticipate is if a scout looks around, gets some coarse FOV data with big 16x16 chunks, reports it to the player, the player looks around, and sees a big artificial-looking 16x16 chunk of weirdness. I guess the solution would be to do fine raycasting for things that will be exposed to the player (player FOV, scouts who intend to report back), and coarse raycasting for other things (everyone else).

Furthermore:
Given that there are bounds on how high a tile can be, there are actually definite obstructions - if the product of the distance with the highest slope encountered on this ray is greater than the difference between the observer's eye level and the maximum height, then the ray can be terminated.