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.

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

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.


  1. The issue I've ran across with drawing lines to the edge of the sight radius, is that Bresenham Lines drawn to the edge of a Bresenham Circle leave gaps. Using a Manhattan Circle gets rid of the gaps, but causes some artifacts around corners. Ultimately, I settled on raytracing to every tile in the field of view (circle of radius say 3-10 around the player). Not sure how well it works when drawing to the edge of a rectangular map/FOV.

    Also, keep in mind that monsters do not necessarily need a fancy FOV; you might be able to get away with just raytracing a line to the player or to other monsters, items, etc., as needed, and seeing if that line is obstructed or not.

    Is there any reason why you need to see the entire map? FOV algorithms work best (both in terms of speed and aesthetics) with a limited field of view, such as the aforementioned radius around the player.

    Finally, with regards to heightmaps, you can treat them exactly the same as binary obstructions if the height of the target tile is higher than the originating tile (when you raytrace you start from the center and step through the line tile by tile). This will accomplish being able to see larger swaths of the map on top of hills than in valleys.

    Best of luck!

    Ebyan "Nolithius" Alvarez-Buylla

    1. Hi Nolithius, thanks for the comment!

      I think I addressed most of those issues in the post, but I guess I can reiterate them...

      Fortunately I wasn't considering using circular FOV - it's good to have confirmation that drawing to the edges of a square doesn't leave any gaps. What kind of artefacts do you get with that technique? I presume they're mostly to do with corridors, walls, doorways, and things that won't show up in this game (until the last battle, at least)?

      I did consider using LOS to check if actors can see each other, but unless I do something clever that would be quadratic in the number of actors, which is several thousand. I could try checking LOS between members of each group, but that would require a grouping framework that I don't yet have. I'll need FOV for the player anyway, so I'll do these calculations with FOV to begin with.

      Physically, the map really isn't that big - something like half a kilometre on each side. If I were standing on a hill even in the southwest corner of that area, I'd expect to notice an army 0.7 kilometres to the northeast, and certainly anything closer. That's just about the only situation where I'd expect to see the *whole* map, but there's always the *potential* to see any given tile from any distance.

      I *could* treat anything higher than the observer's eyelevel as blocking LOS, but this would have strange effects like making an army on a hillside invisible to someone on the plains facing the hill. I want more ways to hide armies than simply to stick them in a forest TW-style, and having realistic heightmap FOV is a great (not to mention intuitive) way to give the player (and the enemy) options when they want to hide their troops.