Jump to content
  • Advertisement
Sign in to follow this  
japro

How to efficently check, store and handle collisions?

This topic is 3197 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

So, I'm just fooling around with some basic 2D graphics programming in OpenGL (well, I started out with the intention of writing a minimalistic RTS game, but there's still a long way to go). I did implement some basic collision algorithms (bounding circles, poly-poly-collision, poly-line-collision etc.). Now I'm at the point where I try to write algorithms and structures to handle collisions for a whole scene. At the moment, the objects are stored in lists which are sorted by the x-coordinate. I then iterate through the list and check only for collisions when the objects x-coordinates differ by less than some threshold value (usually the maximum object size), which results in very few actual collision checks for reasonable "object densities". If a collision occurs I add a CollisionEvent object to a list to process and rectify the collisions later. While this works very well if you want to check for overlaps of small objects in a sparsely populated world, it isn't well suited for finding intersections of lines and objects. The Algorithm obviously works since lines (finite length, no "rays") can be seen as degenerated polygons, but they tend to have rather large dimensions in comparison to the objects populating the world (vehicles etc.) and therefore lead to very high threshold values. So now I'm wondering how to implement the collision checks for the trajectories when my units are firing at each other. An easy solution could be to simulate actual bullets and then only do collision checks for the bullet objects an not the actual trajectories, but this limits bullets to relatively low speeds (otherwise they will "tunnel" through objects if the time steps are too large). So how would you go about doing that? Just using brute force and intersecting long trajectories with significant parts of the whole scene? Or put restritions on the "unit design" by only giving them small firing range or by only implementing slow bullets like rokets? Also, how do you actually handle collisions? At the moment im planning to first move my objects, then checking for collisions and then calling some sort of "handle collision" method for each affected object. Is that the usual approach, are there any pitfalls? I'd appreciate some input, expiriences or ideas.

Share this post


Link to post
Share on other sites
Advertisement
Your 'x sorting' method is actually somewhat reminiscent of the 'sort and sweep' algorithm, a commonly used broad-phase culling algorithm. There are several different ways sort and sweep can be implemented, one of which is to keep two lists (in 2-d), one sorted by x coordinate and one sorted by y coordinate, and update them dynamically whenever an object moves. In other words, it's somewhat similar to what you're doing, only using both axes instead of just one.

Intersection tests for small, fast objects such as projectiles are often expressed as raycasts. Although it's not entirely trivial to implement, there's a nice sort-and-sweep-based raycasting algorithm that should perform well in most cases. There are similar optimized algorithms for other types of spatial partitioning as well (for example, 2D-DDA or 3D-DDA can be used for fast raycasting through a 2-d or 3-d grid).

How much optimization is really necessary will of course depend on the context (number of units, frequency of fire, etc.). If you haven't already, you might try a more or less 'brute force' method and see how it performs (it might not be as bad as you think).

Share this post


Link to post
Share on other sites
Quote:
how do you actually handle collisions?

One method, provided you can store the pertinent collision information, is: for each collided object, sum the vector forces resulting from all the collisions.

Since F = m*a, if you know the total force vector and the mass of the object, calculate the acceleration and modify the object's velocity vector (and then the position) appropriately.

Share this post


Link to post
Share on other sites
Why would you want to "store" collisions? Collision detection and response are part of the same logical process (the physics update) so enforcing a separation is unlikely to be useful.

Share this post


Link to post
Share on other sites
Quote:
Why would you want to "store" collisions?

The storage of collisions is done over a single timestep. The collisions for that timestep are "thrown" away after the physics calcs are completed. As mentioned above, detecting all collisions for a single object in a single timestep allows calculation of a total force vector and response.
Quote:
Collision detection and response are part of the same logical process..

Correct. The interaction of an object with one or more objects simultaneously more closely simulates what occurs in "nature." For some simulations handling each collision and restitution separately may be satisfactory. In others, the total instantaneous force acting on an object may be important.

Share this post


Link to post
Share on other sites
If all og your "bullets" are guaranteed to hit then you could just use a time based self-destruction rather than a collision.

if bullet goes 1 mile a second and target is 1 mile away then destroy self in 1 second.

I'm just throwing out ideas.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Why would you want to "store" collisions? Collision detection and response are part of the same logical process (the physics update) so enforcing a separation is unlikely to be useful.

Well, maybe I'm doing this too complicated. First i checked for collisions at the same time as the "physics update". But this resulted in several problems, like that the objects needs to know its position in the sorted list. But mainly i was concerned about the "symmetry" of collisions. If two objects collide they both have to know what happens, but if i do that while iterating trough the object list there is a "first" object to know about the collision that tries to resolve it. So the other object has somehow to be "told" a collision took place, since when that object is processed the collision is already resolved.

Also, if i calculate physics at the same time as collisions, the whole idea with the sorted lists doesn't work anymore, since the physics very likely mess up the order.

Share this post


Link to post
Share on other sites
First..
Quote:
if i calculate physics at the same time as collisions..

If the possibility exists that an object will intersect more than one other object at an instant, you don't want to resolve a single collision at a time. You need the total forces on an object in that case. So you're on the right track.

In your collision detection routine, you need to store the relevant information for that collision in a structure or something similar so you can examine it later. At collision time, you should have the relative masses, the normal at the intersection point, etc., which you will later need to do the physics. If you're doing simple f=ma physics calcs, little more is needed.

So, store the information you need at collision time.
Quote:
a "first" object to know about the collision that tries to resolve it.. the other object has somehow to be "told" a collision took place

The "first" object should not resolve anything for other objects. You should get all the forces on that "first" object from the collision data and sum them to get its response. Then do the same for other objects. "Symmetry" is taken care of "automatically" if you do the f=ma calcs properly. Forces from a single collision will be equal and opposite.

Share this post


Link to post
Share on other sites
there is a simple method that finds the nearest point on line to another point of your choice, it also returns the distance between those points (which is the minimal distance between your point and the line). so you can just use this to see if your object is close enough to the line before really calculating intersections.
if you want i can look the algorithm up for you..

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!