AS3中检测物体是否拦截视线的高效方法

Question

我已经有一段时间在尝试找到一种高效的方法来确定某物是否在另一个物体的视线范围内。一个很好的例子是，如果一个球体能看到你，它就会向你发射火箭 - 但如果你在墙后面，它显然不会。

以下是我通常处理这个问题的方法：

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};
}

使用这个的基本方式是：

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

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

这样做可以工作，但随着每个新火箭的添加或不可通过物体数量的增加，速度会变得极慢。

我认为有一种非常简单高效的方法，但我可能遗漏了什么 - 我是说，所有游戏都可以做到（如暗黑破坏神等），即使有成百上千的敌人，除非你可见，否则它们不会做任何事情。

有什么想法吗？

- Marty

Answer 1

我是说，所有游戏都会这样做（Diablo等），使用数百个敌人，除非你可见，否则它们不会做任何事情。

像Diablo这样的游戏使用基于瓦片的引擎来减少计算碰撞、视线和AI行为所需的计算量；瓦片式引擎是出于你对游戏引擎的确切担忧而诞生的。

给定绝对坐标后，很容易确定任何敌人所在的具体瓦片，并将其转换为地图上的x，y坐标。一旦你有了这个瓦片，找出是否有其他对象在视线内应该不太困难。

进一步推进基于瓦片的引擎，寻路在基于瓦片的游戏引擎中也非常有用，可以轻松完成任务；路径距离和/或复杂性可以让你轻松地确定两个对象是否“看得见”对方。（如果需要走四十步或者迷宫般的路径，那么它们之间就看不到彼此）

基于瓦片的引擎< strong>大大< / strong>降低了你开始考虑的开销问题。

- Brian Rosamilia

---

关于基于瓷砖的东西，你提出了一个好点子——检查5个瓷砖肯定比检查800个像素要快。但是你会如何看待这个公式呢？不过似乎我仍然需要每隔一定数量的像素进行转换，以确保我没有越过和忽略单元格的角落等部分。 - Marty

一旦你找到了两个物体之间的最短路径，你就不需要再做更多的事情，只需转弯一次并向前移动一个方块即可找到另一个物体。你可能需要考虑物体所“看”的方向，但这是我的一般模式。 - Brian Rosamilia

不确定你的意思是什么。你让我想到了这样一种公式：根据一个角度选择最合适的相邻单元格，直到到达目标单元格。有点像这个：http://projectavian.com/cells.gif - Marty

啊，是的，那张图片是一个很好的例子，说明我所描述的算法实际上并不适用于所有情况。无论如何，从瓦片地图中的一个点到另一个点的投影仍然更有效率，因为它几乎没有任何碰撞检测开销（在基于瓦片的世界中，碰撞非常简单）。将问题看作是从一个敌人向另一个敌人发射弹道，如果撞到墙壁，敌人就看不见彼此了。 - Brian Rosamilia

无论如何，我认为你已经给了我一个相当不错的起点。我会研究一些路径规划公式之类的东西，看看是否能够帮助我快速选择方向上的单元格。 - Marty

Answer 2

节省编码时间，尝试使用Box2d物理引擎进行光线投射，这样可以减轻很多工作量，而且不需要过多担心速度问题，因为box2d已经优化过了。但是如果您坚持自己编码，基于瓦片的方法肯定是最好的选择，也许加上a*路径搜索用于移动和brian提到的射击方式就足够了。但是如果您需要考虑cells.gif情况，则只需更改瓦片搜索的条件即可。

- Shannon

---

唯一的问题是box2d引擎为项目带来了很多我实际上不需要的东西，将来最好考虑将box2d引擎与我的框架合并。 - Marty

Answer 3

对于碰撞检测，通常最好维护一些网格（或空间树，但网格应该足够好），每个单元格都知道其中的对象，以便您可以直接找到某个空间中的对象。

然后编写一个程序，检索所有与碰撞有关的单元格，在这种情况下，沿着射线的所有单元格。在检索它们时，对其中的对象执行碰撞检查。

以下代码应该基本上可以实现：

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 应该包含坐标和一个物体。 ICollidable 是任何可碰撞的东西的接口，应该单独实现，因为例如线和墙之间的碰撞应该很容易计算。
而且，你应该将这个方法放在 CollisionGrid 中，这样你只需使用 myGrid.rayCast(start, end, theCaster)，就可以方便地在任何两点之间投射光线。

祝你好运 :)

- back2dos

---

谢谢你的帮助，不过我有点难以理解你的回答大部分都是一块代码。我会在午餐时间尽力去理解它。 - Marty