Meandering about line of sight

[GoogleCodeExporter]

OK, no actual code yet. I just wanted to air some ideas about efficient
line-of-sight (LOS) and field of view (FOV) calculation. 

With hundreds of units on a large map LOS could be a bottleneck. This is
especially true if the AI needs to compute LOS and FOV for many potential
locations where it might consider moving its units in the near future.
Precomputation can be used in several ways to speed up these functions. 

1. One simple approach is to use a big bloom filter to weed out many LOS
requests that are certainly going to be blocked. The bloom filter will take
two map coordinates and respond with 'bloocked' if it is certain there is
no LOS between them or 'maybe' if it cannot say for sure. A very fast, very
simple hash function must be used for this to make any sense. 
If n is the number of locations on the map, precompute time is O(n^2) and
space requirements is the size of the filter (not very big). 

2. Another approach is based on grouping locations that are all visible to
each other, and assign an integer-id to them. Store this id in each
location. Two locations with the same id have LOS. I have no idea how to
precompute this. It does not sound trivial to break down a map into optimal
(largest possible) regions of reciprocal LOS. Maybe a NNN (Natural Neural
Network, aka brains ^ ^) could do this... that is, a human just looks at
the map and tries to find large convex polygons of unobstructed plains, sea
etc. This might work well in conjunction with a bloom filter, as the
methods seem to complement each other. Space reqirements is just O(n).

3. LOS can be calculated quicker with a precomputed map of 'warning signs'.
Example: For each map location, store 8 values of the highest local LOS
obstruction, one for each nearby octant (answering to the octants normally
used when implementing Bresenham's algorithm and the like). 'Local' might
mean something like 'within 1 km'. This allows the LOS algorithm the
compute how far ahead it can jump without having to test the intermediate
map locations for fear of any LOS obstruction. The precomputed data can
also be utilised by the FOV algorithm. 
Space requirements are significant, O(CN) for some big C, but reasonable.
Precomutation time complexity is the same.

4. A FOV is nice to have to give a player a sense of what can NOT be seen.
However, it's somewhat expensive to compute compared to simple LOS between
units. Maybe one could only compute it in special situations? Say a unit
has stoped moving and has spent some time scanning the surrounding terrain.
Then a FOV is calculated and displayed to the player. A calculated FOV does
not need to be recalculated unless something has changed in it. E.g. if a
smoke grenade has been detonated in the area. This could be handled
similarly to how windows are redrawn on a GUI (I think it's called a
"listener pattern" or something like that). The unit with the FOV can
'register as a listener' to the map locations in it's FOV. If any one of
them for instance is filled with smoke, they send a message to the
FOV-owning unit that 'we need to be recalculated'.

5. Some possible problem areas: (A) Precalculation only works for permanent
LOS obstructions. Smoke, moving fog and the like must be handled
dynamically. (B) One should probably make sure the LOS and FOV algorithms
give exactly the same result. This may require some pondering on rounding
errors etc. 

I might be able to implement some or all of this, but then again, I might
not, LOL... 

Original issue reported on code.google.com by torgau...@gmail.com on 22 Jan 2010 at 10:21

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Original comment by torgau...@gmail.com on 23 Jan 2010 at 5:10

• Changed state: Invalid