I'm looking for solutions to a Line of Effect system I'm creating.  

Specifically,  I'm looking for a real-time algorithm that helps an AI unit find the closest tile in range that has a line of effect to its target

At the moment, I'm using raycasting (in Unity)  to determine what tiles have lines of effect (no obstructions) to each other.  

This information is then used by the AI to locate an unobstructed targeting position within range.  

The end result is that every tile has a list of other tile locations it has a clear line of effect to.  

The problem is that it takes forever to scan and makes the map far too static for my needs. 

Anyone implement something similar?  

Thanks

The opening post allows for much freedom, because it specifies no constraints or optimizations that may already be working. So I throw in some thoughts an hope they help ...

• Static geometry defines a-priorily known combinations of tiles between which LOS will never work. Hence baking a list of possible target tiles into each tile gives a subset of where further calculations are meaningful at all. This may not work well in case that the "sight" is very far.
• A variation of the above may be to bake a list of angle ranges describing direction that are blocked (or unblocked). This may work better in case that the "sight" is very far, or different characters have different demands on "sight".
• Pairs of tiles need to be investigated only if the one tile is occupied by the AI agent itself and the other is occupied by a (living) member of a hostile party.
• The effect range may restrict the distance of tiles that can be reached. Looking further than that would be meaningless.
• An order like scanning an inner ring (around the AI agent of interest) of tiles before scanning the next outer ring allows the algorithm to stop at the first hit; you're looking for the "nearest" tile, right?
• The computations are bi-directional. If an uninterrupted LOS is found from agent A to agent B, then it is also valid from agent B to agent A (but may perhaps be qualified with another view distance and/or effect range). Other way around the same: If agent A cannot see agent B, then agent B cannot see agent A.

Thanks for your help.  I will definitely give these constraints a try. 

One complication I didn't mention is that in my case the tile grid is 3d.  Which means if I have a small level that is (50x25x50) for example,  I'm looking at 3,906,250,000 combinations (50x25x50x50x25x50) for a static scan.   Yikes! that's a 3 GB file per level, assuming I store byte (bool) values and not bits to the file.  The bi-directional property will reduce this, but at the moment I'm not sure about the proper algorithm to implement it.   Iterating over a 6 dimensional array is easy, but it will certainly take forever and it's not optimal.   I know there is a way to iterate over all the possible combinations taking bi-directional factor into consideration, but I haven't worked out the structure for such a loop yet.  Ray casting will definitely need to be avoided if the the line was previously scanned from the opposite direction.  Regardless, it is still a monster to manage in either case.   

I might have to re-evaluate the need for such a system and consider less optimal solutions for the AI.    

The initial system I wrote picked up all the tiles at a radius out from the target and performed pathfinding on each tile.   The problem is that the longer the range the slower the system (more tiles need to be scanned) .And if you limit the tiles to those between the attacker and the target, some wall shapes (like U shaped walls) cause this technique to fail.    

Thanks

One other complication is that the correct way to test for line of effect and cover is to use the corners of each square and not the center point.  This makes this problem even more cpu intensive when raycasting.  

1 hour ago, 00Kevin said:

... I'm looking at 3,906,250,000 combinations ...

Then obviously the full scan need to be replaced by a sparse scan. How many "combinations" of opponents may occur? E.g. an algorithm like this:

for the current AI agent
   calculate the (squared) distance to all opponents on the map
   sort the list by distance
   foreach opponent in the list do
      if opponent is known to see the current agent
         break
      if opponent is known to not see the current agent
         continue
      determine and store visibility(agent, opponent) by casting a ray
      if visible
         break

I'm not sure that helps all that much considering the positions of units often change.  Known positions are rarely useful.     In addition the environment can often change as well.   

With that said, an initial raycast towards each opponent is useful.   

I'm considering compressing the bit array because quite frankly it's the ultimate solution most of the time.   I'll need a compression method that still allows for the data to be read without un-compressing the entire file.  

If you have a regular grid, and a finite distance, you can build a static map of feasible rays. A ray going 5 tiles north goes through the same set of tiles if you look relative to the starting point. Thus if you store those 5 tiles, you can just check their content rather than computing all the rays.

That is, it's a re-usable template  of tiles that you visit relative to your starting point rather than a unique set of rays from each position. Obviously walls become occupied tiles now, as the pattern doesn't have walls.

Secondly, if you hit a blockade at some tile, that blockade will be there as well for a ray the goes in almost the same direction. That is, one blockade hits a lot of rays that you can skip even trying. Each blockade disables a set of rays.

Assuming you have a sparse number of enemy tiles being used, you can also do this in reverse. From a given relative tile, you know which rays will go to that tile, so to test if you can hit that enemy, you only need to check those rays.

That's interesting I'll have to give this some thought.  To be honest, I'm still trying to visualize this solution.   

As an alternative to ray casting I wrote a Bresenham 3D line drawing algorithm that returns a list of tiles.     In fact, my tilemap already has obstructions and occupied squares identified. 

So the solution I've settled on for now is to let my path-finding system do all the work. 

You simply find a path to the target.   

Then you scan that path for points within range and loop until you find the one with a line of effect via a ray cast.  

The problem is that this solution ignores things like windows which might be closer.    One solution to this is to  create a second grid with a much smaller granularity (0.25 size squares) and use it for the initial path-finding.  This would allow the path-finding system to pass through windows and small openings.  

Users may not like an AI that is so cunning