An efficient way to check for objects intercepting a line of sight in AS3

Question

I've for a while now been trying to work out an efficient way to see if something is in something else's line of sight. A good example is having a sphere that fires a rocket at you if it can see you - but obviously not if you're behind a wall.

Here's how I generally went about doing this:

function cast(end:GameObject, walls:Array, accuracy:uint=10):Object
{
    var xp:Number = skin.x;
    var yp:Number = skin.y;

    var ang:Number = Math.atan2(end.skin.y - yp, end.skin.x - xp);
    var xvel:Number = Math.cos(ang)*accuracy;
    var yvel:Number = Math.sin(ang)*accuracy;

    var i:uint = 0;
    for(i; i<800/accuracy; i+=accuracy)
    {
        xp += xvel;
        yp += yvel;

        var j:GameObject;
        for each(j in walls)
        {
            if(j.skin.hitTestPoint(xp, yp))
                return {visible:false, x:xp, y:yp};
        }
    }

    return {visible:true};
}

The use of this would be basically:

var sight:Object = cast(player, impassable);

if(sight.visible) trace('can see');
else trace('cant see - collision at ' + sight.x + ", " + sight.y);

Works, but as we know this will get extremely slow with each new rocket added or as the amount of impassable objects increases.

I'm assuming there's a really simple efficient way that I'm missing - I mean, all games do it (Diablo, etc) with hundreds of enemies that don't do anything unless you're visible.

Ideas?

Answer 1

I mean, all games do it (Diablo, etc) with hundreds of enemies that don't do anything unless you're visible.

Games like diablo use tile based engines in order to reduce the number of computations needed to calculate collision, line of sight and AI behavior; tile based engines were born of the exact concerns you have for your game engine.

Given absolute coordinates, it is trivial to figure out which specific tile any enemy is in and translate that to an x,y coordinate on your map. Once you have that tile, it shouldn't be too difficult to narrow down the number of "checks" you need to run in order to figure out if another object is in sight.

Taking a tile based engine further, pathfinding is also very useful in tile based game engines and can accomplish your task quite easily; path distance and/or complexity can allow you to EASILY figure out if 2 objects can "see" each other. (Chances are if you need to go forty steps, or in a maze-like path the objects aren't visible to each other)

Tile based engines drastically reduce the overhead problems you're beginning to consider.