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.

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.

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.

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.

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.