Big arrays ==> low framerate?

[Mya]

Hi guys,

I've recently added a function to my game, which checks to see if any element from array A is hitting any of the elements from array B - the function breaks down roughly to:



var arrayA:Array = new Array();
var arrayB:Array = new Array();

var indexA: Number;
var indexB: Number;

for (indexA = 0; indexA < arrayA.length; indexA++) {
for (indexB= 0; indexB < dots.length; arrayB++) {
if (arrayA[indexA].hitTest(arrayB[indexB])) {
trace("success!");
}
}
}


The code works fine, however, ever since putting in this code, my game has begun to slow down considerably after about a minute, even if the function is as simple as a trace...

- the only thing I can think of is that it's to do with the size of the arrays - they both get bigger as the game goes on (one at the rate of about 3 elements per second) plus there are another three arrays besides these two that are increasing similarly - so I guess first of all, does this sound like a likely explanation? If so, can anyone suggest any good methods of controlling the size of arrays?

[Noct]

For loops are notorious for slowing down code. The bigger it gets, the longer it will take to loop through it. You have nested For loops, which is even slower...

Using straight hitTests for multiple item collision detection is generally not a great idea. You may want to do some research on other methods of detection. A lot of people break the stage down into quadrants, and only hitTest objects that share the same area.
Another method is to test each axis seperately. As in, check and see if the objects share an x axis first, then if they do, check their y axis...
It can evaluate a bit faster.

You could spend a lifetime googling through all the theories and methods available...

[Greg SS]

Actually, depending on the implementation (I've never seen the hitTest code), bounding box collision test is considered one of the fastest collision check method around...
You could improve performance by a little bit by "caching" the array length value before entering the loop... it might look trivial, but when every microsecond counts, it might help.

var aLen = arrayA.length;
var bLen = arrayB.length;
for(var x=0; x < aLen; x++){....

But I do agree that you might need to look into more advanced partitioning method to slim down the loop

[Noct]

I wasn't arguing the speed of hitTests, I was saying that evaluating anything in nested for-loops on every frame is going to give you a performance hit, especially with a large array of items.

The suggestions I gave about collision detection are not in lieu of hitTesting, they are precursors to it. Like in my first example, (I can't recall what that method is called), you check the quadrant first, then hitTest objects in the same quadrant. In this case it could be used to slim the array of objects being tested...

I do agree with you on storing the length in a variable though; I used to think the less variables the better, but I read a Senoc post about it recently where he flat out said that it would process faster using var storage, so I'm on board now...

[Greg SS]

Here's an idea... Lets use the grid concept.
Assume a playing field of 800x600 pixels, and the average sprites are no bigger than say... 48 pixels... multiply that by 4, we have roughly 200 pixels. So if we divide the screen by 200x200 grid, we'll have a 2D grid of 4x3.
Lets also assume that each sprite have 2 properties xIndex and yIndex of where it is on the grid (we can always initialize with 0,0);
Lets also assume that we have a 2D array, containing objects, each one has 2 properties...

Aw heck... to do this effectively, we have to implement a linked list....
You know what? I'll just make a tutorial out of this... stay tuned please...