Bear, thanks for the extra explanations of the FastLOS, I'll check it out when I have a bit more time, at the moment I'm trying to finish testing of the bit-fiddled brute force method that we were mentioning about.

Let me think... My 'mapchunks' (one level per mapchunk, in most cases) are 100 x 100, so 10000 tiles per level. So the storage requirement per mapchunk, using one bit per tile pair, is (10000x10001)/2 bits = 5005000 bits, or about 5 megabytes. That's too chunky for a phone, but not outrageous on a desktop machine. The way I'm doing it, with a 64 bit mask per tile, is 640000 bits or a bit over a half-megabyte.

So you'd get much simpler code, easier to debug, and about the same speed modulo cache issues, and I'd get a savings of about 85% in memory devoted to speeding up line of sight checks.

Suppose we were to store at each tile a bitmap of which other tiles within sight radius from it are visible. With sight radius of 15, that would be about 500 bits per tile because any pair of tiles can use mutual visibility mapping for the leftmost of them, or the uppermost if they're in the same column; that way you only need bits for half of the 31x31 tiles under consideration.

Now this is a factor of about 8 bigger than what I'm using for FastLOS, but it's a lot more straightforward to calculate and has an additional advantage of requiring storage that scales linearly with increasing area rather than with the square of increasing area.

Wait, wait, there might have been some confusion, the costs with the tile pair storage would not be as you suggest. For a 100x100 map with 15 max sight radius, the costs would be 2^N bits, where:

N = mapIndexBits + 2*sightRadBits +1 (1)

mapIndexBits = the number of bits needed to represent the linear map index. For 100x100 = 10000, and 10000 < 16384, so:

mapIndexBits = 14

sightRadBits = the number of bits needed to represent the sight radius. For 15, 15 < 16, so:

sightRadBits = 4

So, if you plug the numbers above in eq. (1), you'll need 23 bits, which means 2^23 = 1 MB of storage. With this 1MB you can store up to a 128x128 map with 15 max sight radius. By now, you might be ask where does eq. (1) come from.

Now as I said in one of the previous post, when you want to store a pair of points, you can do:

* sort the points by the X axis

* store the first point's linear index in the mapIndexBits ( linear index is "point.x + map.width*point.y")

* store the second point's offset to the first point in the rest bits. The offset in X is ALWAYS positive or 0, so sightRadBits will suffice. The offset in Y needs one more bit for the sign. And that's why its "2*sightRadBits + 1" in eq. 1.

The costs for updates are also very nice: if you update a few tiles, you would just need to run the FoV algorithm in these tiles:

`for each tile in updated_tiles:`

view_points = points_in_radius(tile, max_sight_radius) // get all points in the given radius, centered on tile

for each vpoint in view_points:

is_visible = LineOfSight(tile, vpoint) // Calculate line of sight with your fav fov

set_precalc_los_bit( tile, vpoint, is_visible) // update our dense precalculated-LoS map