if i have ~200 objects and they can all collide with each other(not like fps where u just have one object vs the other objects). so the brute way would be to compare object1 to object2, object3, object4.... object200 then go back to object2 and compare it w/ 3,4,5... so the order of this operation would be n^2. in the case of normal shooters, it would just be N, cuz ur just comparing object1 to the rest and if the rest collide u don't really care(especially if they're walls/non-moving objects so they don't collide at all) what would be the best algorithm for each object to have the detect the collison? rite now, i'm thinking of having say a matrix of num*num with each element representing say 100x100 in the 2d space. then i just go thru all the 200 objects and place them in the matrix. then i rescan the matrix and c if there's more than one object in that individual grid, if there is, then i do more precise collison detection. that sound like a good method? any better? life is unfair, take advantage of it. UNMB2 - if the link doesn't work, try clicking it Edited by - thuned on February 22, 2001 11:06:36 PM

Your method sounds like a good one to me, but one that I have come across that might quite be a bit faster is called Binary Space Partitioning. I probably won''t do a very good job of explaining it, but I will try anyway. It does what you want to about as fast as I know how. If my explanation seems unclear (most likely) then a web search should help you out pretty quickly.

This method creates a tree structure with each node representing part of the game 2d space. Every node of the tree has two sub-nodes with each sub-node having two more etc... all the way down to the bottom most nodes (leaves) of the tree. The root node would represent all the 2d space, the first level of sub-nodes would represent half of 2d space each, the second level quarter each and so on. The idea is that if you can test each time if there are more than two objects in a node and its children, then if there is not you can knock off a large chunk of space quickly instead of checking through every single individual subset of space. I wish I could draw a picture.. maybe this will work:

0 2d space
|
/ \
0 0 half of 2d space / half of 2d space
/ \ / \
0 0 0 0 1/4 of 2d space / 1/4 of 2d space...

If you check the left most node on the second level and there is only one object in it, then there is no need to check any of the nodes below it, for example. I don''t know if this will help, as this is my first time answering a posting, but in the likely event you have more questions a web search on Binary Space Partioning might help. I also think there was a recent article on Gamasutra about Quadtrees, a slightly more complicated variant of this idea.

Hope this helps in some way.

Bob

but with this tree method, don''t u have to build the tree each frame then?
it''s like saying, doing a binary sort(quicksort) so u can do a binary search when you can just do a straight linear search each time.
well, i dunno. i guess i should mention that this is in java and i''m not even sure how do do trees w/o pointers(there''s no pointers in java), heh


thuned

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

references are just as good as pointers in most situations. If I was to make a tree I''d probably have an abstract class TreeNode with two subclasses: BranchNode and LeafNode. Each branch would have two TreeNodes as members, each leaf would have an object as a member. I needed to make a tree yet but you definently can make them and pretty much any other data structure. Honestly it seems like one of java''s strengths.

As for your problem when you are dividing your world up make sure to take into account that something can be in two or more sectors at once. So if things are in adjacent sectors they might be colliding.

You could calculate for each object the next object it will collide with and the time of that collision. If you keep the time of next collision then each frame you check if a collision occurs during the frame. Any time a object changes direction you check it against every other object to see who it collides with next. Also any object that would have collided with it next has to be rechecked against every other object to see who it now collides with next. The same is true when any object is destroyed. Since the collision is two ways the check for what the object changing collides with updates all the other objects that would collide with it. Also if you accumulate the time since last collision you can avoid updating the times every frame. You can instead update the time of collision as you spin through the list due to a change. You just subtract the time since last collision each time through the list and set it to zero when done. Any additional checks just subtract zero then.

Whaa??? No Pointers in Java????

Try this example, I''ll just make up a silly class for an example:

class TestClass
{
int a;

TestClass(int init_a) { a = init_a };

}


TestClass p1 = new TestClass(1)
TestClass p2 = new TestClass(2)

// At this point p1.a = 1, p2.a = 2

p2 = p1

// At this point p1.a = 1, p2.a =1

- Nuff said, p2 is now pointing to the object pointed to by p1. Try it out for yourself, you''ll see it works.

You can extend this quite easily to making trees work in java - and they''re quite simple to implement.

By the way, another method you might try is one that I''ve seen used for detecting if sprites have collided in a game.

basically you have a doubly-linked list keeping track of the position of each object, and keep this sorted by position (either x or y value - usually x) and for every frame go through the list from left to right.

Start with the leftmost object, and then keep checking until the next object in the list is too far away to be colliding with it, then move to the next object in the list.

I''m not sure how this stacks up efficency wise against the binary tree deal, but it might be easier to implement.. who knows?



- Flanders -

ok, with the binary tree and the linked list implementation, it looks like it to me that i have to rebuilt them each frame(rite?). but wouldn''t that be a HUGE performance dip cuz u have to search half the list each time u add a node?
then again, i have to mention i''m using java. i can''t have like these huge calculations in each frame. i''ve checked and i and do about a for loop from 1 to ~250k and that''s just about the lowest i want to go. (i guess that''s ~500k steps since it''s doing both the comparison and the increment in each loop).

for this thing, i''d gladly sacrafice memory for speed(unless if it goes over say 10megs ). if so, isn''t matrix the best way?
or maybe i don''t entire get what ur saying in the binary tree example. so if each level down divides the "world" in half and u eleminate the half that''s doesn''t contain 2+ objects, how would u check for collison?
what would each node of the tree actually contain? the position it covers and how many children it contains? now, if i''m thinking correctly, there''s 2 ways to stop(pop off the top of the stack). one is just simply no more child nodes. the other one would be if the amount of space the node covers is smaller than the object itself(and it still has child nodes), then that means it''s hitting its child nodes.
so if it''s the 2nd case, i can just pass the refernce of that node to another function since it would collide with everything under it? then i guess i would still need to trace down all the nodes still to check for the collisons of its child nodes.

is that what i''m supposed to do(am i understanding/explaining it correctly)? if so, does anyone know how this binary method compares to the matrix method?


thuned

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

Thuned, I did it exactly like you described in your first post, to my game. I have sometimes 2000+ bullets flying in the air, and hundreds of small bombs that can be detonated with a hitting bullet. No matter how much stuff there is, the performace is great.

I suggest making that matrix as a linked list so that you''ll only have to check through the objects that are actually in the same grid cell.

-Hans [home]

that''s right, java doesn''t have pointers. It has references which are much better in most situations, but they don''t have quite the power that pointers do, for example you cannot make a reference to a reference. In order for that to be possible references would have to be objects but they aren''t.

Don''t you have to rebuild your matrix each frame? I don''t think a BSP tree would help you. It would be more useful for testing collisions with walls. A node would represent a wall with everything infront of the wall on one branch and everything behind the wall on the other branch. So if you had two square rooms divided by a wall the root node would be the wall between the two rooms. One of the far walls is in front of that wall and the other is behind it. Then the two rooms the side walls are either both in front or behind the far wall. One of the side walls becomes the next node down and the other wall is either in front or behind it. The other wall has nothing in front or behind it so it is a leaf. Then when you check collision you check the line defined by the node. You are either in front of it, behind it or intersecting it. Since walls might have openings you have list of line segments at the node where each segment is a section of that line. If you intersected with the line then you check if you intersected with an individual segment. If not then you split your object by what is in front and behind that line and check the subnodes. I don''t think it is practical to build a bsp on the fly. If you have dozens of rooms with tables, chairs and various other objects blocking movement it becomes a fast way to narrow down what you might collide with. It isn''t for a bunch of dynamic objects moving around though.

You could use something similar to do quick collision detection, but the code gets rather nasty. It basically works the same as your matrix, but the size is dynamic. Conceptually you can divide you game world into four regions in relationship to an object, i.e. left, right, above or below. So you put an object in the root node. Then you add an object. If it''s right is less than the left of the root then goes into the subtree for all object left of the root. If not then you proceed around the root checking the other bounds. If it doesn''t go entirely into a subtree then you add it to a list for that node and also to any subtrees it fit partially within. When you are done building the tree you traverse it checking collisions on any node with more than one object. It is basically the same thing you are doing with the matrix except that it is dynamic instead of static. If you choose your resolution well on your matrix then you will most likely do as well or better. With your 100 by 100 matrix you have 10,000 cells holding 200 objects. When you are done building it you have to check all 10,000 of those. The tree is going to have at most 200 nodes and if perfectly balanced then it would have four levels, i.e 4^4. So building the tree and traversing it isn''t necessarily a killer. It is complex enough that testing is really the only way to say for sure which is faster.