I'm developing a flash game with Macromedia Flash 8 (it's really obsolete, isn't it?). The player moves a plane that continuously fires a stable stream of bullets and uses it to destroy enemies. Much like Bloons Super Monkey
I use MovieClip.hitTest() method to determine whether a bullet has collided with an enemy. Yet due to the vast quantity of bullets(m) and enemies(n), it can take up to O(mn) hitTest() calls, which is very slow. Is there any approach that can improve game performance by reducing hitTest() call count?
For non-flash developers, assume hitTest() methods takes two shapes as input, and returns whether they overlap each other. Regardless of the shape and size of both graphs, hitTest() always returns in Θ(1) time. However the constant is very large, so one hitTest() call takes the same time as more than thousands of arithmetic calculations. No need to concern about memory cost as there's always plenty.
Note: All of these stuffs are moving rapidly, I can only keep an static array of them (that is, insert and delete only, can't move an element from one index to another). The actual position of everything at a specific time is not sorted. Only object creation time is sorted but that seems useless. So it's not possible to scan from left to right or from top to down.
Macromedia Flash 8 (it's really obsolete, isn't it?)
In my view its was so the day they tacked an eight on it, when was that, 2006?
(and on a completely personal note, there was never a barge pole long enough for me to ever go near flash, I feel sorry for all that ever had to struggle with the abomination that is flash)
Bounding circle test
For speed you can do a cut down distance test (bounding circle test). Basicly tests if two circles overlap.
B is approx 4 pixels in radius and the bad dudes D 100 pixels in radius then if (D.x - B.x) * (D.x - B.x) + (D.y - B.y) * (D.y - B.y) < 4 * 4 + 100 * 100 then Hit .Assuming that B.x B.y and D.x D.y are the center coordinates of the objectsBounding oval test
If the bad dudes are not square such that their width is significantly different from their height you can modify the above test to do bounding oval test. You will need to get the ratio of width to height and scale the height calculations.
So if bad dudes have width and height D.w = 100 D.h = 50
if (D.x - B.x) * (D.x - B.x) + (D.y - B.y) * (D.y - B.y) * (D.w / D.h) < 4 * 4 + D.w * D.w then Hit .Assuming that B.x B.y and D.x D.y are the center coordinates of the objects. AND assuming that the bullets are relatively small in comparison to the bad dudes.Bounding box test. A.K.A. AABB (Axis Aligned Bounding Box)
You could also do a bounding box test where you test if the boxes that contain the bullet and the bad dude overlap. This is about the quickest if you dont have to calculate the left right top and bottom edges.
if not (B.leftEdge > D.rightEdge or B.rightEdge < D.leftEdge or B.topEdge > D.bottomEdge or B.bottomEdge < D.topEdge) then HitAnd can be a little quicker if you add the bullet size to the bounding box of the enemy's bounding box at setup.
if not (B.x > D.rightEdge or B.x < D.leftEdge or B.y > D.bottomEdge or B.y < D.topEdge) then Hit (NOTE edges have half bullet width and height subtracted, added from left right, top bottom.More speed
You can further improve the test if you know that there is a zone where bullets and bad dudes do not interact. EG side scroller from left to right bad dudes never get closer than 1/3 of screen width then test bullets only if past 1/3 of screen width. Or track the leftmost bad dude and test only bullets greater than that distance from left. You can also do this if bullets are not expected to hit anything unless they have been in flight for over n frames.
Test whether to hitTest
All the tests are approximate hits. If you still want a precise hit test use one of the above methods to determine whether or not to do the more detailed and slow test you were using.
If boundingBox == true then do hitTestThat way you only use the slow test if there is a good chance of a hit.