the matrix will be created w/ the once in init and then updated each frame. doesn''t need to be deleted then recreated, so no time spent allocating memory.

as for the tree method, it looks like ur talking about quadtree. i dunno tho, cuz i didn''t really read about quadtree yet. but more than likely, since my game is kinda like Han''s game where tens of bullets spew out of a machine gun at once(from several different ships), they''ll all be kinda cuttered so the tree won''t be balanced. futhermore, i want the game to be smoother in framerate. so i don''t want like 150fps in one frame and then 30fps in the next.

anyways, thanks to all who helped, i think i''ll just use the matrix method

thuned

life is unfair, take advantage of it.
UNMB2 - if the link doesn''t work, try clicking it

Just a thought, but I''m all for the concept of keeping collision times. Lets say we have N independent elements, each with a velocity and acceleration vector guiding their movement.

At time (t) = 0, we compare all elements to find pending collisions. Basic stuff; given acc, vel do the paths intersect, at a common time t2.

For each element, keep a record of all pending collisions,
and keep an external record of collisions, sorted from most to least immediate.

Now you do your updates, and check the time. If a collision
occures, we jump to it from our collision list, and remove the two elements in the collisions. But before removing, take the list of collisions that that element was destined for, and travel down each link to the element it will now no longer collide with. Remove the collision from that list, and since that collision is linked to our external list of collisions, remove it from there as well.

Now we have removed all the collisions associated with those elements. Next frame, continue...

This -only- works if you start with a set number of items, and can predetermine all possible collisions. It also depends on the fact that the number of collisions any item will be involved with is minimal.

To start with, you have a heavy load; calculating all possible collisions; N + N - 1 + N - 2... + 0, ie. 1/2 (X^2 + X) operations. Only 5050 for 100 objects.

Then we have to worry about each frame; the number of collisions we can get, and the number of possible collisions that object will have. Well...since I''m bored... =)

Cases:

0) No objects collide.

Result: No processing required. Next frame.

1) All objects collide, each object is specified it will collide with all other objects.

Result: All objects vanish. Total operations = N*2, removing from external list, and removing indervidually.

2) N objects collide, each object collides with no other objects.

Result: Remove those N objects from the external collisions list, and remove those N objects from the group. Operations = 2*N.

3) N objects collide, each object collides with K other objects.

Result: Riight. For each of the N objects, we take those collisions out of the external list, then decend down to the other objects linked internally by the collision. Each of the objects have K objects to handle, and each of those must have the relevant operation removed from the external list. Operations = N * (2*K).

4) N objects collide, each object collides with K1, K2, K3.. etc.
other objects, where KN is the number of collisions the Nth object in the collision is going to collide with.

Result: As with (3), only we get operations = 2*(K1 + K2 + K3 + ...)

(5) Finally lets take some average case: Say, each frame an average 1/10th of the items collide, each time the item is linked to 1/4 of the other items. Thats on randomish motion.

You get: N * (2*K) == N(total)/10 * (2 * N(total)/4). Ie. N(total)^2 / 20 operations.

So, for 100 items we get for the cases:
(0): 0
(1): 200
(2): N * 2 (Worst case: 99 * 2 = 198 (or 200, if we do a (1))
(3): N * (2*K) (Worst case: 99 * (2 * 100) = 19800)
(3): (K1 + K2 + K3...)*2 (Worth case: As with (3))
(4): 500

whew! Now, if you go for an NxN matrix, you start by pushing all those items into the matrix (N operations), then skim through all the matrix cells (you get all items), and do more detection only if there is a collision. We''ll call the magic number of operations a detection like that will generate Z.

Best case: Inserted into the first 200 elements of the matrix. No collisions. Operations = 200 * 2 = 400.

Worst case: Inserted into last 200 elements of the matrix. No collisions. Operations = 10000 + 200 = 12000.

Avg Case, say last element in the middle item of the matrix. No collisions. Operations = 5000 + 200 = 5200.

Then we go for cases where there is a collision... Oooo... something like (200) + (200 - P/10000 - P/5000) + Z * P, where P is the number of elements in the same cell. Arg. I give up.

That detection LilBudyWizer was talking about might offer better performance, so might the BSD tree. I dunno. I havent bothered to look at them. =) Just thought this might be interesting.

I''m sure you could figure out the cost of add new elements to the system too.. something like N operations to compare to all other elements, + log 2 Extern'' list length blah for binary search to insert the collisions times * the number of collisions the new item will get.

Wow, that woke me up. Time for breakfast; apologies for any obvious errors.

ciao!

I''m of the general opinion that if you have the performance you need then you have done enough to performance tune it. Your matrix seems to be doing fine so I wasn''t trying to say do it this way instead. Rather I was just explaining some alternatives. Since the original question was is there a faster way that seemed appropriate. If you have the performance you need then the only recommendation I would make is try it with a smaller matrix. 10,000 cells for 200 objects seems a bit excessive. Most likely a 20 by 20 with 400 cells wouldn''t have any significant increase in the number of collisions checked unless the objects are densely packed together.

thanks for all your help.

my dsl was down for another day so i came up w/ another thing to add to my matrix algorithm to make it more efficient.

btw, did i mention that this is my friend''s game and i''m just helping him?

anyways, he has declared stuff[1000] meaning there''s can be a maximum of 1000 moving objects in the game.

so say if i have a matrix like matrix[500][500], that''ll be 250k elements, which just searching thru all would take more steps than i can afford.

what i was thinking was to create another array, int array[1000].
at the begginning of the process, i don''t need to reset the array, i just need to keep track of how much i used.
i start adding stuff to the matrix, at the same time, i add the id of the element of the matrix that i just added and put that into the array.
now, each time i add a new object to the matrix and something''s alreay there, i just call a function that does the precise coldet.
so near the end of the loop, if there''s no collisions, the operation would just be N*3(add to matrix and add to array and increment count, probably more, but at least it''s not N^2).
then, using the id''s contained in the array, i''ll go back to the matrix and reset those elements; now i don''t have to search thru the WHOLE 250k elements.

so say there''s 200 objects.
with no collisions, the operation would be like 200*5 = 1000?
and the cool thing about this is since i have a HUGE amount of elements in the matrix, there''s not likely gonna be multiple collisions in one element of the matrix.
so if every object collides with something and i have 7 steps to do w/ each collision:
200*5*7/2 = 3500
the /2 is cuz A collides w/ B is the same as B colliding w/ A.

that seems pretty good w/ the addition of the 2nd array, i''ll go ahead and tell my friend(projectxf) to implement it then.
the site is currently hosted on my server at:
http://thuned.dhs.org/projectxf/shooter2d/shooter.html

Shadow Mint, thanks for your method, but like alot of the objects will be ships w/ their own ai so there''s no way to predict when and where they''re gonna collide


thuned





life is unfair, take advantage of it.
UNMB2 - if the link doesn''t work, try clicking it