XNA 2D line-of-sight check

Question

I'm working on a top-down shooter in XNA, and I need to implement line-of-sight checking. I've come up with a solution that seems to work, but I get the nagging feeling that it won't be efficient enough to do every frame for multiple calls (the game already hiccups slightly at about 10 calls per frame).

The code is below, but my general plan was to create a series of rectangles with a width and height of zero to act as points along the sight line, and then check to see if any of these rectangles intersects a ClutterObject (an interface I defined for things like walls or other obstacles) after first screening for any that can't possibly be in the line of sight (i.e. behind the viewer) or are too far away (a concession I made for efficiency).

public static bool LOSCheck(Vector2 pos1, Vector2 pos2)
    {
        Vector2 currentPos = pos1;
        Vector2 perMove = (pos2 - pos1);
        perMove.Normalize();

        HashSet<ClutterObject> clutter = new HashSet<ClutterObject>();
        foreach (Room r in map.GetRooms())
        {
            if (r != null)
            {
                foreach (ClutterObject c in r.GetClutter())
                {
                    if (c != null
                        &&!(c.GetRectangle().X * perMove.X < 0)
                        && !(c.GetRectangle().Y * perMove.Y < 0))
                    {
                        Vector2 cVector = new Vector2(c.GetRectangle().X, c.GetRectangle().Y);
                        if ((cVector - pos1).Length() < 1500)
                            clutter.Add(c);
                    }
                }
            }
        }

        while (currentPos != pos2 && ((currentPos - pos1).Length() < 1500))
        {
            Rectangle position = new Rectangle((int)currentPos.X, (int)currentPos.Y, 0, 0);
            foreach (ClutterObject c in clutter)
            {
                if (position.Intersects(c.GetRectangle()))
                    return false;
            }
            currentPos += perMove;
        }
        return true;
    }

I'm sure that there's a better way to do this (or at least a way to make this method more efficient), but I'm not too used to XNA yet, so I figured it couldn't hurt to bring it here. At the very least, is there an efficient to determine which objects may be in front of the viewer with greater precision than the rather broad 90 degree window I've given myself?

Answer 1

First, ahead of time, build a list of BoundingBox objects from your clutter. (If you're calling this 10 times a frame, there's no sense creating a list of them in the method itself. If removing objects that are definitely off-screen proves to be a useful optimization, then do that only once per frame and store the list of bounding boxes for repeated use.)

Second, build a Ray from your two positions. pos1 will be origin of the ray; pos2 - pos1 (normalized) will be the direction. You will also want to store the distance between the two points for later use.

Then, just loop over each object in your pre-built list of bounding boxes and call the Intersects method of your ray. You'll get back either true (if the line of sight is blocked by the box) or false (if it isn't). And because a ray is semi-infinite, it can actually return true if the box is past the end of the ray, so you need to check that the distance returned from the Intersects method is less than the distance between the two input points.

Note that both the BoundingBox and Ray types are 3D: just set the Z component to 0.

This method (ray tests against a list of blocking objects) is extremely standard and significantly quicker than marching along the line checking for intersections at each individual spot. As a bonus, if it's still too slow (which is unlikely), there are standard techniques for further optimization, all of which involve testing the ray against fewer boxes. But this should be plenty fast enough.

Answer 2

Calculating the line of sight between two objects, isn't so complicated to go through arrays and much more as you've illustrated. It just simply takes a few mathematical-provided functions to calculate radial-angle differences, so-long as you know the object positions and angles.

Works just by calculating the difference between radial-angles (converted to radians using no functions but a bit of mathematics) and vector distances.

public static bool InLOS(float AngleDistance, float PositionDistance, Vector2 PositionA, Vector2 PositionB, float AngleB)
{
    float AngleBetween = (float)Math.Atan2((PositionA.Y - PositionB.Y), (PositionA.X - PositionB.X));
    if ((AngleBetween <= (AngleB + (AngleDistance / 2f / 100f))) && (AngleBetween >= (AngleB - (AngleDistance / 2f / 100f))) && (Vector2.Distance(PositionA, PositionB) <= PositionDistance)) return true;
    else return false;
}

An example of its use:

if (InLOS(90, 500, Player.Position, Enemy.Position, Enemy.Angle)) //Do something

That example can translate into readable language like so: "If the player is within a 90 degree angle of the enemy and less than 500 pixels of difference between the player and the enemy, do something.."