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

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 v开发者_JS百科isible.

Ideas?

---

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.

---

Save yourself having to code so much and try raycasting using the Box2d physics engine, takes alot of the hard work out for you and you don't need to worry about speed so much as box2d is already optimised but if you insist on the coding yourself tile based would definitely be the way to go, perhaps with a* pathfinding for moving and what brian said for shooting would suffice. But if you need to account for the cells.gif scenario then just change the conditions of the tile search.

---

For collision, it generally makes sense to maintain some sort of grid (or spatial tree, but grid should be fine enough), each cell knowing the objects in it, so that you can directly find objects in a certain space.

You then write a routine, that retrieves all cells in question for collision, in this case, all cells along the ray. As you retrieve them, perform a collision check for the objects in them.

This code should basically do it:

function rayCollision(start:Point, dest:Point, grid:CollisionGrid, ignore:* = null):CollisionData {
    var direction:Point = new Point(dest.x - start.x, dest.y - start.y);
    if (direction.length == 0) return null;//just in case
    const limit:Number = direction.length;
    direction.normalize(grid.cellSize);
    var pos:Point = start;
    var cur:Array, last:Array = null, tested:Dictionary = new Dictionary();
    if (!(ignore is Function)) {
        if (ignore is ICollidable) tested[ignore] = true;
        else for each (var entry:* in ignore) tested[entry] = true;//assume it is a collection
    }
    var collision:CollisionData = null;
    while (grid.containsPoint(pos) && (pos.subtract(start).length < limit) {//stop when you're off the grid or out of range
        cur = grid.getCellByPoint(pos);
        if (cur == last) continue;//cell already checked, skip
        last = cur;
        for each (var object:ICollidable in cur) {
            if (tested[object] || (ignore && ignore(object))) continue;//object already checked or should be ignored, skip
            tested[object] = true;
            collision = object.collideWithLine(start, dest);
            if (collision) return collision;
        }
        pos = pos.add(direction);
    }
    return null;
}

CollisionData should probably contain coordinates and an object. ICollidable is an interface for anything collidable, that should be implemented individually, because for example a collision between a line and a wall should be fairly easy to calculate.
And actually, you should make this a method of CollisionGrid, so you just go myGrid.rayCast(start, end, theCaster) and you'll be able to conveniently cast rays between anything you want.

Good luck with the details ;)