Fast way to find a number in an array of objects in JavaScript

Question

I need to check whether or not an object is in distance to show it to the screen ( its a side scroller video game )

So far i have this:

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

Where worldObj.distance is the distance the player has traveled and the obj.distance is the distance of the object.

The problem:

This for loop causes a great performance drop on mobile devices due to the amount of coins in the level ( more than 10,000) and this gets executed 60 times per second ( 60 fps )

How can i fix this?

Thank you! :)

EDIT: Tried caching canvas.height into a variable, ( eg: var height = canvas.height; ) before the loop. No performance differences (44 ms vs 44 ms on a I5 2500K, imagine on mobile!!).

EDIT: Tried caching Coins.length before the loop, ( eg: var len = Coins.length; ). No performance differences (44 ms vs 44 ms).

EDIT: This is how i create coins:

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

Alright. I've done some number crunching and come up with two algorithms, with tradeoffs between them.

As a testbed, I'm running the following initialization code:

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

As you can see, there are 100000 coins here. More than you stipulated in your answer, I know, but I wanted to stress-test things.

The first algorithm is a somewhat optimized version of the one you posted in your question. It just loops through and tests if the nearest edge of each coin is less than viewSize/2 distance from some point x. If so, it adds it to an array, which it ultimately returns.

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

This method takes no extra time to setup and 7ms for each execution with our 100000 coins. Definitely a cost in an animation loop, but a manageable one.

The second algorithm makes use of a map. It starts out by sorting the list of coins, then selects a set of points across worldSize, each one viewSize apart form the last one. It creates an object with these points as keys. It then loops through all of the coins and saves the index of the one nearest to each point in the object. This takes some time, but it only needs to be done once. When the actual loop runs, it just finds the point in the map immediately before the left (or lower, as the case may be) edge of the viewing window. It then loops forward through all of the coins in the list, saving them to an array as it goes, until it gets to a coin that is farther along than the right (or upper) edge of the viewing window. Then it stops and returns the array. This way, it doesn't have to check every coin in the list, but instead just a few of them.

The setup code looks like this:

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

And the main loop looks like this:

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

The initialization takes a whopping 900ms, but the loop takes only 1ms each time it runs. As the ratio between worldSize and viewSize increases, the loop will get faster and faster.

Overall, I would say that the first algorithm is simpler, but if you find yourself pressed for time in your animation loop and can take a second to initialize when the game (or level) loads, then you should use the second algorithm.

Perhaps, if you know the placement of the coins to begin with, you could even pre-sort the list and pre-build the map when you write the code. Then you wouldn't need the client to do the initialization at all.

If you have any questions, please ask!