Jump to content
  • Advertisement
Sign in to follow this  
yahn

Collision Detection 2d

This topic is 3325 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, this is the situation of my game: I have a lot of instances. There are two types of objects: static and dynamic. Dynamic instances, in my game, do not need to check for collision with other dynamic instances. Obviously, static instances do not need to check for collision with static instances. Therefore, the only type of collision I have to detect is dynamic-static. However, there are two types of dynamic objects (I'll call them typeA and typeB). TypeA needs to know all (typeA and typeB) dynamic instances within a given region (rectangle). TypeB has no such requirement. In order to get the instances within a region, I am using a quadtree that contains all dynamic instances. Since dynamic instances don't need to check for collision, I only store the coordinates of the instances to build a point-quadtree. I feel like I can really take advantage of this situation computationally. Naturally, static instances do not move. I feel like I could store these instances in a separate structure and have the dynamic instances query this structure only when the dynamic instances move. This seems relatively cheap computationally. Additionally, (I think) the situation is even better. All dynamic instances are roughly circular and all static instances are roughly rectangular. So, I think I can get away with using only approximations of the instances actual shape to detect a collision. However, I don't really know how to go about setting this up. Should I just build a separate quadtree with the static instances in it? I don't know how to store rectangles (I wrote a point-quadtree). I've heard about R-trees, but, from the Wikipedia article I read, R-trees seem to be good for storing rectangles bounded inside other rectangles (never happens in my situation). So, can you please give me some suggestions? I really want to capitalize on this situation; in fact, I need to. Thank you

Share this post


Link to post
Share on other sites
Advertisement
Rectangle-circle collision detection can be done fairly straightforwardly; just find the point on the rectangle that's closest to the circle and see if that's smaller than the circle's radius.

Making a separate quadtree for the static objects is a good idea. Then when you want to find which static objects a dynamic object has hit, you query the static object tree for all objects whose rectangles intersect the dynamic object's bounding box (because this rect-rect intersection test is very fast). Then you iterate over all of those to see which ones actually touched the circle of the dynamic object.

For quadtrees storing objects bigger than points, you simply put the object as far into the quadtree as it can go without crossing a border. For example, if you have a quadtree centered on [50, 50] and an object with a bounding rectangle ([45, 45], [55, 55]), then obviously a standard quadtree won't be able to push that object deeper into the tree, because it's in the center of the area.

Share this post


Link to post
Share on other sites
Quote:
For quadtrees storing objects bigger than points, you simply put the object as far into the quadtree as it can go without crossing a border. For example, if you have a quadtree centered on [50, 50] and an object with a bounding rectangle ([45, 45], [55, 55]), then obviously a standard quadtree won't be able to push that object deeper into the tree, because it's in the center of the area.


I'm still confused. In the point-quadtree I wrote, I store objects only in leaf nodes. I guess a rectangle-quadtree works differently? Maybe I'm so focused on how a point-quadtree works that I'm over-complicating this concept.

Share this post


Link to post
Share on other sites
You can't fit objects only into leaf nodes if they straddle the boundaries between two nodes. And you only push things down into leaf nodes if the current node is too populated. Let's take an example.

You start out with a single node, with no objects in it. This node covers the area between [0, 0] and [100, 100]. Let's give it an ID of 1.

You add an object to it. This object fits in ([10, 10], [20, 20]) (that is, its bounding rectangle is a square with length-10 sides). You could at this point construct a leaf node beneath node 1 to contain this object, but why bother? For now we just stick it into node 1's object list.

You add another object to the tree. This object's bounding box is ([20, 40], [40, 60]). No problem there; you just append it to node 1's object list.

Now let's say you've added 10 objects to node 1. Its object list is starting to get pretty crowded, so it's time to extend the tree. You create four new nodes underneath node 1, IDs 2 through 5. Node 2 has the bounding rectangles ([0, 0], [50, 50]), 3 has ([50, 0], [100, 50]), 4 has ([50, 50], [100, 100]), and 5 has ([0, 50], [50, 100]).

You take the first object you created, and you ask each of the child nodes if they can contain it within their bounding rectangles. Node 2 says that it can, so it gets the object. Now you take the second object you added. None of the four nodes can hold this object, since it straddles the boundary between two of them. Since it doesn't fit at a lower level, it stays in node 1. Finally, you repeat for the other objects you'd added to node 1. Once you're done, node 1's object list hopefully should be much shorter, since most of the objects should fit into one of the child nodes.

Now when you add objects to the tree, you add them to node 1. It then checks to see if any of its children can hold the object. If one of them can, it passes it off to the child node instead; otherwise, it goes in node 1's object list.

You actually don't have to make the child nodes have square boundaries; neither do you have to have exactly four children at any given level of the tree. But evenly-partitioned trees are easier to think about and give good results unless you have special circumstances to deal with.

Share this post


Link to post
Share on other sites
Wow, I feel so dumb now. I kept thinking that r-trees would be almost exactly like point-quadtrees. You cleared up a lot with that post. I really appreciate it.

However, I still don't understand what happens when a bunch of instances decided to populate in such a way that they would need to be bound in the root node (i.e. many instances intersect with the 4 nodes created).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!