javascript - 在 JavaScript 中的对象数组中查找数字的快速方法

Question

我需要检查一个物体是否在远处以将其显示在屏幕上(它是一个横向卷轴视频游戏)

到目前为止我有这个:

for ( var i=0; i < Coins.length; i++ )
{
    var obj = Coins[i];


    if ( worldObj.distance > obj.distance && worldObj.distance < obj.distance + canvas.height )
    {

        DrawCoins(obj);
    }
}

其中 worldObj.distance 是玩家走过的距离，obj.distance 是物体的距离。

问题:

由于关卡中的硬币数量(超过 10,000)，这个 for 循环导致移动设备的性能大幅下降，并且每秒执行 60 次(60 fps)

我该如何解决这个问题？

谢谢! :)

编辑:尝试在循环之前将 canvas.height 缓存到变量中(例如:var height = canvas.height;)。没有性能差异(44 毫秒与 I5 2500K 上的 44 毫秒，想象一下在移动设备上!!)。

编辑:尝试在循环之前缓存 Coins.length，(例如:var len = Coins.length;)。没有性能差异(44 毫秒与 44 毫秒)。

编辑:这就是我创造硬币的方式:

for(var i=0; i<10000; i++)
{

    /* Coins */
    for ( var z=0; z < 6; z++ )
    {
        if ( RNG(0,100) < Upgrades.coinChance ) // random number generator, Upgrades.coinChance = 5; -> 5% chance
        {
            Coins.push({ active: 1, type: "Gold", cash: 5, x: 60*(z+1), distance: i*RNG(20,100) });
        }
    }
}

Answer 1

好的。我做了一些数字运算并提出了两种算法，并在它们之间进行了权衡。

作为测试平台，我正在运行以下初始化代码:

var n,m;

var Coin=function(x)
{
    return {x:x,r:1};
}
var coins=[];
var map={};

var viewSize=50;
var worldSize=1000;

n=100000;
while(n--)
{
    coins[n]=Coin(worldSize*Math.random());
}

如您所见，这里有 100000 个硬币。我知道，比你在回答中规定的要多，但我想对事情进行压力测试。

第一个算法是您在问题中发布的算法的优化版本。它只是循环并测试每个硬币的最近边缘是否小于 viewSize/2 到某个点 x 的距离。如果是这样，它会将其添加到一个数组中，并最终返回该数组。

var checkCoins1=function(list,x,w)
{
    var selected,k,n,no;
    selected=[];
    n=list.length;
    while(n--)
    {
        no=list[n];
        if(Math.abs(no.x-x)<w/2+no.r)
        {
            selected.push(no);
        }
    }
    return selected;
};

这种方法不需要额外的时间来设置，每次执行我们的 100000 个硬币需要 7 毫秒。绝对是动画循环中的成本，但可以控制。

第二种算法使用 map 。它首先对硬币列表进行排序，然后在 worldSize 中选择一组点，每个点都与最后一个点相距 viewSize。它创建一个以这些点为键的对象。然后循环遍历所有硬币并保存最接近对象中每个点的硬币的索引。这需要一些时间，但只需要完成一次。当实际循环运行时，它只是在 map 中找到紧靠查看窗口左边缘(或下边缘，视情况而定)之前的点。然后它向前循环遍历列表中的所有硬币，将它们保存到一个数组中，直到它到达比查看窗口的右(或上)边缘更远的硬币。然后它停止并返回数组。这样，它就不必检查列表中的每个硬币，而只需检查其中的几个。

设置代码如下所示:

coins.sort(
    function(a,b)
    {
        return -(a.x<b.x)+(a.x>b.x);
    }
);
n=Math.floor(worldSize/viewSize);
while(n--)
{
    map[n*viewSize]=undefined;
}
n=coins.length;
while(n--)
{
    for(m in map)
    {
        if(map[m]===undefined || Math.abs(coins[n].x-m)<Math.abs(coins[map[m]].x-m))
        {
            map[m]=n;
        }
    }
}

主循环是这样的:

var checkCoins2=function(list,map,x,w)
{
    var selected,y,k,n,no;
    selected=[];
    y=x-w/2;
    n=map[Math.floor(y/w)*w];
    while(1)
    {
        no=list[n++];
        if(Math.abs(no.x-x)<w/2+no.r)
        {
            selected.push(no);
        }
        else if(no.x>x)
        {
            break;
        }
    }
    return selected;
};

初始化耗时高达 900 毫秒，但循环每次运行仅需 1 毫秒。随着 worldSize 和 viewSize 之间的比率增加，循环将变得越来越快。

总的来说，我会说第一种算法更简单，但是如果您发现自己在动画循环中时间紧迫并且可以在游戏(或关卡)加载时花一秒钟时间进行初始化，那么您应该使用第二种算法.

也许，如果您一开始就知道硬币的放置位置，您甚至可以在编写代码时预先对列表进行排序并预先构建 map 。那么您根本不需要客户端进行初始化。

如有任何问题，请提出!