title: Fast algorithm for line of sight calculation in an RTS game
body: <p>I'm making a simple RTS game. I want it to run very fast because it should work with thousands of units and 8 players.</p>
  
  <p>Everything seems to work flawlessly but it seems the line of sight calculation is a bottleneck. It's simple: if an enemy unit is closer than any of my unit's LOS range it will be visible.</p>
  
  <p>Currently I use a quite naive algorithm: for every enemy units I check whether any of my units is see him. It's O(n^2)</p>
  
  <p>So If there are 8 players and they have 3000 units each that would mean 3000*21000=63000000 tests per player at the worst case. Which is quite slow.</p>
  
  <p>More details: it's a stupid simple 2D space RTS: no grid, units are moving along a straight lines everywhere and there is no collision so they can move through each other. So even hundreds of units can be at the same spot. </p>
  
  <p>I want to speed up this LOS algorithm somehow. Any ideas?</p>
  
  <p>EDIT:</p>
  
  <p>So additional details:</p>
  
  <ul>
  <li>I meant one player can have even 3000 units.</li>
  <li>my units have radars so they towards all directions equally.</li>
  </ul>