Increase efficiency of a loop with jQuery

Question

I have a game coded in jQuery where bots are moved around the screen. The below code is a loop that runs every 20ms, currently if you have over 15 bots you start to notice the browser lagging (simply because of all the advanced collision detection going on).

Is there any way to reduce the lag, can I make it any more efficient?

P.s. sorrry for just posting a block of code, I can't see a way to make my point clear enough without!

$.playground().registerCallback(function(){ //Movement Loop
        if(!pause) {
            for (var i in bots) {
                //bots - color, dir, x, y, z, spawned?, spawnerid, prevd
                var self = $('#b' + i);
                var current = bots[i];
                if(bots[i][5]==1) {
                    var xspeed = 0, yspeed = 0;
                    if(current[1]==0) { yspeed = -D_SPEED; }
                    else if(current[1]==1) { xspeed = D_SPEED; }
                    else if(current[1]==2) { yspeed = D_SPEED; }
                    else if(current[1]==3) { xspeed = -D_SPEED; }

                    var x = current[2] + xspeed;
                    var y = current[3] + yspeed;
                    var z = current[3] + 120;
                    if(current[2]>0&&x>PLAYGROUND_WIDTH||current[2]<0&&x<-GRID_SIZE||
                        current[3]>0&&y>PLAYGROUND_HEIGHT||current[3]<0&&y<-GRID_SIZE) {
                            remove_bot(i, self);
                    } else {
                        if(current[7]!=current[1]) {
                            self.setAnimation(colors[current[0]][current[1]]);
                            bots[i][7] = current[1];
                        }
                        if(self.css({"left": ""+(x)+"px", "top": ""+(y)+"px", "z-index": z})) {
                            bots[i][2] = x;
                            bots[i][3] = y;
                            bots[i][4] = z;
                            bots[i][8]++;
                        }
                    }
                }
            }
            $("#debug").html(dump(arrows));
            $(".bot").each(function(){
                var b_id = $(this).attr("id").substr(1);
                var collision = false;
                var c_bot = bots[b_id];
                var b_x = c_bot[2];
                var b_y = c_bot[3];
                var b_d = c_bot[1];
                $(this).collision(".arrow,#arrows").each(function(){ //Many thanks to Selim Arsever for this fix!
                    var a_id = $(this).attr("id").substr(1);
                    var piece = arrows[a_id];
                    var a_v = piece[0];
                    if(a_v==1) {
                    var a_x = piece[2];
                    var a_y = piece[3];     
                        var d_x = b_x-a_x;
                        var d_y = b_y-a_y;
                        if(d_x>=4&&d_x<=5&&d_y>=1&&d_y<=2)  {
                            //bots - color, dir, x, y, z, spawned?, spawnerid, prevd
                            bots[b_id][7] = c_bot[1];
                            bots[b_id][1] = piece[1];   
                            collision = true;
                        }
                    }
                });
                if(!collision) {
                    $(this).collision(".wall,#level").each(function(){
                        var w_id = $(this).attr("id").substr(1);
                        var piece = pieces[w_id];
                        var w_x = piece[1];
                        var w_y = piece[2];
                        d_x = b_x-w_x;
                        d_y = b_y-w_y;
                        if(b_d==0&&d_x>=4&&d_x<=5&&d_y>=27&&d_y<=28) { kill_bot(b_id); collision = true; } //4 // 33
                        if(b_d==1&&d_x>=-12&&d_x<=-11&&d_y>=21&&d_y<=22) { kill_bot(b_id); collision = true; } //-14 // 21
                        if(b_d==2&&d_x>=4&&d_x<=5&&d_y>=-9&&d_y<=-8) { kill_bot(b_id); collision = true; } //4 // -9
                        if(b_d==3&&d_x>=22&&d_x<=23&&d_y>=20&&d_y<=21) { kill_bot(b_id); collision = true; } //22 // 21
                    });
                }
                if(!collision&&c_bot[8]>GRID_MOVE) {
                    $(this).collision(".spawn,#level").each(function(){
                        var s_id = $(this).attr("id").substr(1);
                        var piece = pieces[s_id];
                        var s_x = piece[1];
                        var s_y = piece[2];
                        d_x = b_x-s_x;
                        d_y = b_y-s_y;  
                        if(b_d==0&&d_x>=4&&d_x<=5&&d_y>=19&&d_y<=20) { kill_bot(b_id); collision = true; } //4 // 33
                        if(b_d==1&&d_x>=-14&&d_x<=-13&&d_y>=11&&d_y<=12) { kill_bot(b_id); collision = true; } //-14 // 21
                        if(b_d==2&&d_x>=4&&d_x<=5&&d_y>=-11&&d_y<=-10) { kill_bot(b_id); collision = true; } //4 // -9
                        if(b_d==3&&d_x>=22&&d_x<=23&&d_y>=11&&d_y<=12) { kill_bot(b_id); collision = true; } //22 // 21*/
                    });
                }
                if(!collision) {
                    $(this).collision(".exit,#level").each(function(){
                        var e_id = $(this).attr("id").substr(1);
                        var piece = pieces[e_id];
                        var e_x = piece[1];
                        var e_y = piece[2];
                        d_x = b_x-e_x;
                        d_y = b_y-e_y;
                        if(d_x>=4&&d_x<=5&&d_y>=1&&d_y<=2)  {
                            current_bots++;
                            bots[b_id] = false;
                            $("#current_bots").html(current_bots);
                            $("#b" + b_id).setAnimation(exit[2], function(node){$(node).fadeOut(200)});
                        }
                    });
                }
                if(!collision) {
                    $(this).collision(".bot,#level").each(function(){
                        var bd_id = $(this).attr("id").substr(1);
                        if(bd_id!=b_id) {                           
                            var piece = bots[bd_id];                                
                            var bd_x = piece[2];
                            var bd_y = piece[3];
                            d_x = b_x-bd_x;
                            d_y = b_y-bd_y;
                            if(d_x>=0&&d_x<=2&&d_y>=0&&d_y<=2) { kill_bot(b_id); kill_bot(bd_id); collision = true; }
                        }
                    });
                }
            });

        }
    }, REFRESH_RATE);

Many thanks,

Answer 1

There are many ways to improve your code.

Algorithmic improvements

You're using almost exclusively O(n²) algorithms for your collision detection. You're testing each bot against each object. For example if you've got 20 bots and 30 obstacles your computer has to test for (19+18+...+1) + (20*30) = 190+600 = 790 collisions.

A simple way of reducing the amount of necessary collision tests is to split the field into smaller parts. One simple way of doing this is to use sorted lists. I assume your objects have rectangular boundaries. Just create a sorted list of the left edge.

sorted_left_border = [40, 51, 234, 240];

Here's the used pseudo code:

for bot in all_bots:
    left = bot.x, right = bot.x + bot.width
    top = bot.y, bottom = bot.y + bot.height
    // binary search is O(log n)
    colliding_objects = binary_search for range in sorted_left_border
    for obj in colliding_objects:
        // check the other 3 borders

There are ways to use all 4 borders, but they are considerably more complicated.

There are some sorting algorithms that can sort in near to O(n) time if the input is almost sorted, but I'd just use the Javascript built-in sort function. (If that's too slow you can write your own later.)

The DOM is slow

Try to update the DOM offline before you insert it back into the browser HTML. The way you're doing it now, the browser has to update the DOM every time you change something. The browser should have to update the DOM not more than 1 time per frame.

To pull the elements from the DOM, there's the detach method in jQuery. Be sure to use jQuery selectors that match only the detached elements:

// remove from DOM, avoid updating it.
var theGame = $("#theGame").detach();

// select all bots and do the updating
var bots = $(".bot", theGame);

// reinsert
theGame.appendTo("body");

Using appropriate technologies

Using jQuery with DOM elements is the wrong technique. The DOM wasn't built for this. If you're only programming for modern browsers, consider using the <canvas> element.

Answer 2

I think what Georg is describing is something like this. Its a java applet so its going to be faster than javascript, but it illustrates the principle. You'll note that distances are only calculated between an object and the objects in the adjacent 8 squares in the grid. If there are no other objects in those 8 squares then that bubble doesn't get checked for collisions at all.

This technique is built on a hash table, which shouldn't be too hard to implement in javascript because every js object is a hash table!