Hello! I'm designing an action game, containing a number of static objects that all of my bullets would have to collide with. I want to be able to tell which object it collided with though. What data structure do I need for my collision detection? Thanks in advance!

Whole this may seem as an easy and trivial question, it is fairly more complex than it appears to be. The most direct and easiest (although inefficient) method would be to contain a linked list or a vector of all of the static objects. That way, you can simply loop though and test against collisions. That is the easiest brute-force thing to do, but it is not that efficient. If you have a lot of static objects, you will be checking against objects all the time that might not even be close to the player, thus slowing down your game.

I can't give you the best method for what you want to do because it depends on a lot of things. First, is your game 2D or 3D? 2D is a lot easier to work with and implement. If you have a 3D project, you would need to use a 3rd party physics library to get decent results. Second, how do you store your data? Are you using pure screen cordinates or world coordinates, or both? If you know the world coordinates, you could easily create a set of vectors/linked lists that partition the world into groups, so at any one screen, you only are checking against objects in that scene. Finally, how do your objects interact with each other? Messages, direct calling, callbacks? Those are just a few questions that you'd need to think about and answer before being able to get a better idea of handling this. After that, we can probabally help you out more. Good luck!

Wouldn't it be easier to have the bullet object contain a pointer or reference to the object it collided with rather than the other way around? This would eliminate the possibility of several different bullets hitting the same object. Otherwise, you might need to use some sort of hash table, since one Object might contain references to several bullets.

So instead of querying the object as to what bullet hit it, you could ask the bullet itself which object it hit.

I guess it depends on your game logic though.

I really need to reconcider my options!
Thanks anyway!

Quote:

Original post by Dauntless So instead of querying the object as to what bullet hit it, you could ask the bullet itself which object it hit.

From what I read, that's what he wanted to do anyway. He hasn't gotten to the point where he knows which bullet hit which object, and simply has to retrieve that already-determined information; he actually wants to determine that information to begin with.

I don't know the specifics, having never implemented anything like this myself, but I gather that the main method, touched on by Drew_Benton, is to store a container of all your collideable objects in a way that correlates to how they are arranged in space. A common container that does this type of task is a Binary Space Partitioning Tree (BSP Tree). If you are familiar with basic binary trees, here's how a BSP roughly works. Each node describes a geometric division of space into two halves. In 3D space, this division would be a plane. Any point is either on one side of the plane or the other (or exactly on the plane, this this case can be assumed to belong to one specific side). In 2D space, the division is a line. (In n-dimensional space, the division is (n-1)-dimensional.) A node also has a list of references to any object that is contained in the space represented by that node. (You could force lists to only apply to leafs of the tree, rather than all nodes; I don't know the specifics of how BSPs are commonly implemented.)

So for example, the root node could contain a list of all objects, since it represents all space. It also defines a plane that cuts this space in half. The left child of the root node will represent everything on one side, and the right child of the root node will represent everything on the other side. So the left child has a list of all objects that exist in its half, and the right child does the same for objects in its half. Each of those nodes also divides its own space in half, and has two nodes to represent those halves. Eventually, you won't subdivide any further, because you don't want to make your tree too deep, causing a waste of memory and causing searches to take longer.

Now then, given that, let's say you have a bullet, and you want to know if it has collided with any object. You'll probably have a line defined by two points: the bullet's location at the start of the frame, and its location at the end of the frame. What you want to do is only do collision tests on this line segment with objects that are likely to be really close. So we can check the root node to see if this line segment is fully within the left side or fully within the right side. To do this, we just check each endpoint. If both endpoints are on one side, then the whole segment is on that side. From there, we know that we don't have to worry about any objects that are on the other side. Our bullet isn't in their space, so it couldn't have collided with them. We can now continue our search deeper into the BSP. This node also will have two child nodes. We find out which half our line segment is in, and then only search that child node. Eventually we get to the point where there aren't anymore child nodes. So we stop there, and using the list of objects in our final node, we do normal collision tests against those objects and our bullet's line segment. The number of objects in this list should be far fewer than the number of objects in the whole scene.

Now there are certainly a lot of details I haven't discussed, such as building the BSP tree to begin with, figuring out what to do when your line segment crosses the boundary of a division, et cetera. But hopefully this will get you thinking about things that you can research and refine on your own.

Using BSP-trees seems very promising! I did some google-search right after I read the last post and there seems to be some pretty good tutorials on how to implement BSP-trees!

Thank you all!