I'm creating a top-down 2d strategy game, with a square grid map. So far, I've used Bresenham's line drawing algorithm in a circle to determine what's in LOS of each unit, and then targedt one of the targets in the circle. Now I find that this limits my units to shoot only at targets that they see. I want to extend my targeting algorithm to target any other unit in range of my weapon, even if they're out of sight range of this given unit, if they're "spotted" by another friendly unit. In other words, I want to enable usage of weapons with ranges longer than sight range. Is there a better way than iterating over all sighted units and computing range and LOSto each of them?


1 Answer 1


If you store the units for each side in an quadtree, you can cheaply avoid iterating over enemy units that are beyond range (assuming your units can't shoot over more than half the board!).

If you store your unit list in each quadtree sorted by whether its been seen or not (e.g. just have two lists), you only have to compute the line-of-sight (LoS) between a unit and an enemy if its potentially unspotted.

And if you track who saw each who first, you only have to recompute the LoS when one of the pair moves.

Tangentially related, here's how to efficiently compute the visible board for a unit (my blog). If you only want to compute LoS between units, and don't need tile visibility (e.g. fog-of-war), then checking LoS using Bresenhams is likely a better bet.

Small complication: Bresenhams doesn't actually visit all tiles on a line! It will miss some. If you need a precise computation, look at my own question (3D, but the problem is the same in 2D).

  • \$\begingroup\$ Can you please further explain the quadtree solution? \$\endgroup\$
    – nihohit
    Jul 8, 2013 at 16:17
  • \$\begingroup\$ I think a quadtree is an overhead, since this units are already on a grid map. \$\endgroup\$ Jul 9, 2013 at 6:19
  • \$\begingroup\$ @GustavoMaciel quadtrees avoid visiting empty grids to find out if they are empty. It also stops you needing to put moving objects into two grid tiles, and large units into multiple ones. \$\endgroup\$
    – Will
    Jul 9, 2013 at 6:42
  • \$\begingroup\$ Apart from avoiding visiting empty grids, the other two issues can be dealt with easily. If it's units ranges are not too great(like an tower defense game), visiting empty grids can be better than paying for rebuilding the quadtree. But that's very dependent on his game. \$\endgroup\$ Jul 9, 2013 at 6:45
  • \$\begingroup\$ @Will, can you please point me at an explanation of how to implement this? \$\endgroup\$
    – nihohit
    Jul 9, 2013 at 15:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .