Jump to content
  • Advertisement
Sign in to follow this  
Mizmoon

Collision Response

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

Hello everyone! This is my second time posting on this website, and so far I have very much appreciated the professional help its members have to offer. I am creating a custom physics engine for a game mod and am having some trouble dealing with collision detection and response. This might sound like a common thread topic, but in my case, some special circumstances are making the process more difficult.

 

First of all, the game has trouble dealing with a situation where, when a loop which is run every frame, contains a function which in turn contains its own loop. This usually causes the game to bog down or the entire game loop to be aborted. This happens even if the function only contains an empty loop iterating from 1 to 10. The game is much more tolerant towards nesting loops inside eachother when inside the same funciton.

 

Second, the game is written in a OOP-style scripting language to which there are no pre-existing libraries to include. This means i have to build everything from scratch - i currently have things like vector/quaternion libraries and a module for adding linked lists to classes. So before you suggest raycasting solutions, please explain how to best implement this in a cheap way, keeping in mind the loop issue.

 

Some background to my system:

 

Every frame, two separate loops are run - one for all rigid bodies, applying gravity, friction, velocities and so forward, another for collisions. There, I check first if the objects collide with eachother, and second if they collide with static objects in the game (such as walls, represented by AABBs). I do this by first doing a basic boundary check with an AABB or sphere, and I also plan to implement a SAT test for object-object collisions. If collision occurs, a class instance is created containing information about which two objects are colliding, and if it is a object to object collision, or object to static. Every frame I also loop through all these instances and cleaning out any doubles (two objects colliding will render two collision instances). 

 

My problem:

 

After this, it is time to push the objects apart, and this is what I find tricky. The way I define wether two objects have collided is to check if all axes intersect, but then how do i know on which axis to push them apart? Pushing them along the vector between the objects sound silly to me, because wether I push an object sidewards into a wall, the force should only push it outwards in the direction of the planes normal, and not stop the sidewards motion. How do I find which plane the object is colliding with?

 

NOTE: Something I just came up with while typing this, can I do it by calculating the normals of each surface of the box, and then do a dot product between them and the velocity vector of the object, picking the normal which has the lowest dot value?

 

Second thing is when an object is resting upon another object, like a soldier standing on a tank. I understand you are to apply some kind of constraint to bind the soldier to the tank, how does this work?

 

Thirdly, what is the best way to do collision check on fast moving objects, such as bullets? Is it possible to somehow check a line against a box without using loops, and to low expense?

 

As a side note I can mention that the requirements of precision in this engine are very low. I am doing all i can to simplify things while still having them look acceptably good. Any suggestions overall about how to structure a physics engine or collision detection are very welcome.

Share this post


Link to post
Share on other sites
Advertisement

a few thoughts (based on trying to figure out what is being done here):
if possible, you don't really want to write the physics code in a scripting language;
it may make sense to invest in a tree structure.

the issue of the x^2 costs of checking for object collisions can be reduced basically via things like tree structures (and similar).

basically, we take the collection of objects, divide it roughly in half (as in a binary tree), or sometimes into quads or eighths (a quad-tree or oct-tree), the advantage then is that the number of objects each object needs to check against is greatly reduced (in my case, I had generally used binary trees).

also possible is to use a regular grid, but this makes more sense for large-scale organization (such as different parts of the world), vs small-scale (for things like piles of objects, a tree structure is much better).

 

but, for example, we could use a 16 meter grid for dividing up the world (typically, most interactions also tend to be fairly localized).

 

likewise static objects do not need to check for collisions, only other objects check against them. this makes physics a lot cheaper by avoiding unnecessary checks.

generally, for pushing things apart, we want to find the axis with the least penetration, which if dealing with OBB/OBB collisions, is generally one of the collision axes.

if dealing with rotational movement, it also makes sense to figure out where the collision has occurred (needed for things like torque calculations), which is a little more tricky. one strategy here is using CSG clipping, and another is generating points and then finding their closest point within the adjacent object.

one strategy for things like bullets is basically to represent them initially as a sort of capsule:
we have starting and end points, and a radius (the furthest point from the center);
when doing checks here, we can calculate the closest point of approach between the pairs of objects, and check for collisions at this point;
this might not always work, say if the collision would occur before or after the CPA, bit it works "most of the time".

so, the physics loop might look something like (per time-step):
calculate bounding-boxes and calculate start/end positions for every object in the scene;
build a tree for the current frame (*1);

for each moving object:
* query objects based on the bounding box for the move (coarse checks);
* find the CPA for the object pairs, calculate positions and check for this point in time (initially sphere-checks);
* if needed, do more precise collision detection;
* if there is a collision, do collision handling stuff.

*1: tree-building cost is important; one trick for speeding this up is managing separate trees for static, moving and non-moving objects, where only moving objects really need to have their tree rebuilt each frame, and the non-moving tree is rebuilt less often (usually when objects start or stop moving).

the idea: static objects use static trees (only rebuilt if static objects change state), non-moving trees were conditionally rebuilt on "coarse ticks" (if an object changes between moving/non-moving, ...), and moving-object trees were always rebuilt.

an object would move into the non-moving set generally if it moves below a certain minimum velocity for multiple coarse-ticks.

time-step is also important for stability, where I have generally had best results using a constant time-step of usually at least 60-100Hz.

IME, time-steps much less than about 30-40Hz tended to result in excess instability (say, with piles of objects, ...).

my engine had used a subdivision strategy, where the 16Hz main tick was subdivided, giving a 128Hz virtual tick (IOW: "coarse" and "fine" ticks).

another trick was that of only engaging fancy physics (and fine-ticks) when objects using fancy physics were actively moving, and mostly using plain AABBs for most things (players, enemies, items, ...), where sliding AABB physics can be done fairly well at a 16Hz timestep (without subdivision), thus making them a lot cheaper.

like, say, the fancier physics only engages when the player runs into a stack of boxes or similar, and we actually need the finer timestep.
 

 

don't know if this helps.

Share this post


Link to post
Share on other sites

First of all, the game has trouble dealing with a situation where, when a loop which is run every frame, contains a function which in turn contains its own loop. This usually causes the game to bog down or the entire game loop to be aborted. This happens even if the function only contains an empty loop iterating from 1 to 10. The game is much more tolerant towards nesting loops inside eachother when inside the same funciton.

 

why ?

 

 

 

 

 

 


So before you suggest raycasting solutions, please explain how to best implement this in a cheap way, keeping in mind the loop issue.

 

 

if a "loop issue" prevents raycasting, there's something fundamentally wrong.

 

 

 

 


After this, it is time to push the objects apart, and this is what I find tricky.

 

most do.

 

there are two basic approaches to collision detection.

 

1. move everything, then check for collisions, and try to figure out the resulting mess. i have no idea who came up with this. apparently it was in some book or something. must have been cause its very popular. i personally consider this a bad way to do things and believe that those who do so get what they deserve. 

 

2. move things one at a time, using stepped movement if necessary, checking and handling collisions as you go.

 

while you don't explicitly state it, it appears you're using the first method. 

 

 

 

 


the game is written in a OOP-style scripting language

 

sounds like that may be the source of your loop problem.    never send a script to do a code's job!

 

 

 

 


Every frame, two separate loops are run - one for all rigid bodies, applying gravity, friction, velocities and so forward, another for collisions.

 

a single loop that does movement followed by collision for each entity/object should be easier to deal with.

 

 

 


and I also plan to implement a SAT test for object-object collisions.

 

possible overkill?

 

 

 

 


If collision occurs, a class instance is created containing information about which two objects are colliding,

 

you new an object on the heap for every collision?    Aggh! just shoot me!     nothing personal.....

 

 

 

 


The way I define wether two objects have collided is to check if all axes intersect,

 

 

again, overkill?

 

 

 

 


but then how do i know on which axis to push them apart?

 

 

by using method #2 as opposed to method #1 mentioned above.

 

 

 

 


can I do it by calculating the normals of each surface of the box, and then do a dot product between them and the velocity vector of the object, picking the normal which has the lowest dot value?

 

 

throwing complexity at a problem usually doesn't help. its akin to throwing code at a problem. 

 

 

 


Second thing is when an object is resting upon another object, like a soldier standing on a tank. I understand you are to apply some kind of constraint to bind the soldier to the tank, how does this work?

 

each soldier has a variable that tells you which tank the soldier is on.     when you move the tank, you move the soldier too.  when you need to draw or collision check the soldier, you know where they are (the location of the tank), and their altitude (they're on top of it).

 

 

 

 


Thirdly, what is the best way to do collision check on fast moving objects, such as bullets? Is it possible to somehow check a line against a box without using loops, and to low expense?

 

 

possibly, but stepped movement works fine. if you can come up with a general geometric solution that's faster, and have the demo program to prove it, i think we'd all be interested.

 

 

 

 


As a side note I can mention that the requirements of precision in this engine are very low. I am doing all i can to simplify things while still having them look acceptably good. Any suggestions overall about how to structure a physics engine or collision detection are very welcome.
 

 

use method 2.   use AABB.   throw the rest in the trash.   job done.  miller time!

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

Hmm, i think i will need to give some extra info on this front. 

 

@cr88192:

 

Trree structures is something i have considered for buildings, where one AABB can represent the building as a whole and child boundaries represent walls and such. To be fair though the play area of the game is not very large, and the ammount of objects quite few (12 players + about as many vehicles and turrets, upon that all the projectiles), and the need for optimization is not very large. This is not really a game per say, but a map for warcraft 3. The challenge is to create a "game within a game", where everything is replaced and the original game is only used for rendering and other basic functions. This is one of the reasons why it is accepted for the engine to be rather crude.The game loop runs every 0,03 seconds which is the lowest supported. The game does not handle rotational movement in collision responses.

 

About treating static objects separately, that is a good tip. Could I perhaps treat objects with a velocity length of 0 as static, and not test them against other objects? Small velocities are rounded down to 0 as of current.

 

Sphere tests seem a bit over-the-top for me, iIunderstand the equations for those are quite heavy. 

 
Overall, I appreciate your input, but what I need is really details on how these things would be implemented. 
 
 
@Norman Barrows:
 
Yeah, the loop issue propably inherits from the fact that it is just a scripting language. Infact, it is not even really OOP, i use a preprocessor that translates the classes into series of arrays and functions. But like I said, the object is to push the boundaries.
 
The common way of dealing with collisions is, like you said, to move everything, check for collision, move stuff around a bit, and then repeat the process four or five times until you're guessing everything is solved. I agree this is a very bulky way, although when checking collision object by object, I'm not sure how you would deal with situations where one body displaces another, for instance by pushing into it. You cannot move back to your former position, and all you can do is try to move it out of the way and hope it doesn't end up inside something else.
 
The first makeshift way I had when dealing with collision with static objects, I just checked for collision axis by axis before adding velocity, and if adding velocity to that particular axis made the object collide with something, i removed the velocity again. With large velocities though, objects would end up resting some distance away from the object they're colliding with, so in the end, you need to find a collision point. By the way, when saying I check if all axes intersect, i mean with AABBs. And no, that is not overkill, it is the simpliest, and perhaps only way of finding wether two boxes overlap. 
 
The solution with creating a collision event (just bundles of data iterated through when doing response) was to keep the collisions manageable, and to deal with events where one object collides with several others. My idea was to maybe extend it into finding all the objects you intersect with and making the collision response taking them all into account at the same time. The operation is really just saving/retrieving data from an array and is really not heavy, right me if i'm wrong. Perhaps i am overdoing it though. 
 
I seriously don't think stepped movement can replace raycasting as you proposed. The reason you have problems with fast objects in the first place is that they move faster than the game updates. If you were to move all objects a little bit at the time with shorter intervals, checking for collision as you go, everything would simply go slower and you would waste loads of processing power in the process. 

Share this post


Link to post
Share on other sites

Hmm, i think i will need to give some extra info on this front. 
 
@cr88192:
 
Trree structures is something i have considered for buildings, where one AABB can represent the building as a whole and child boundaries represent walls and such. To be fair though the play area of the game is not very large, and the ammount of objects quite few (12 players + about as many vehicles and turrets, upon that all the projectiles), and the need for optimization is not very large. This is not really a game per say, but a map for warcraft 3. The challenge is to create a "game within a game", where everything is replaced and the original game is only used for rendering and other basic functions. This is one of the reasons why it is accepted for the engine to be rather crude.The game loop runs every 0,03 seconds which is the lowest supported. The game does not handle rotational movement in collision responses.

 
not having rotational movement simplifies things considerably.
 
as for trees, generally these are built without really taking structures into account.
 
like, it isn't so much "where are the walls?" as much as "where is the average center of this collection of objects?" and maybe "how are they distributed relative to this center?". usually subdivision continues either the collection can no longer be divided or until some minimum object-count is reached.
 
so, building it is something like:

  • loop over objects to calculate common origin;
  • if count was too low, create a leaf;
  • loop again to calculate a good division plane;
  • 3rd loop to try splitting along plane (IME, often left/right/middle, where objects in middle cross the plane);
  • if can't split (left or right is empty), create a leaf;
  • otherwise, create a node and repeat process for each half.

when we want to check something, we walk down the tree, and generally the number of required checks is somewhat lower than if using linear searches.

 

 

About treating static objects separately, that is a good tip. Could I perhaps treat objects with a velocity length of 0 as static, and not test them against other objects? Small velocities are rounded down to 0 as of current.
 
Sphere tests seem a bit over-the-top for me, iIunderstand the equations for those are quite heavy. 
 
Overall, I appreciate your input, but what I need is really details on how these things would be implemented.

that is basically the non-moving case.

 

the main difference between the static and non-moving cases typically is that a non-moving object currently has a velocity of 0, whereas a static object can never have a non-0 velocity. either way, most checks can be skipped for both cases.

 

 

sphere checks aren't really all that expensive.

 

the main drawback with sphere-checks is mostly that they don't really generally fit the shape of most objects as good as bounding-boxes.

 

the advantage they have though, is that they can fit other types of objects in an "orientation agnostic" manner.

 

an example would be a brick flying and tumbling through the air, where if seen as a sphere we can mostly ignore its orientation at a given moment, as the brick will (in every possible orientation) still be within the confines of the sphere. more accurate checks can be left for cases where they are needed.

 

 

otherwise, for non-orientable objects, bounding-boxes make more sense.

 

there is a little more involved in cases where you need to check against objects moving in space, rather than simply jumping from one position to the next, where sphere-based calculations can still be a little cheaper and more accurate than a lot of other checks.

 

granted, it is possible to calculate and check AABBs at the closest-point-of-approach though (mostly, this is a relatively minor amount of vector math involving the line-segments for the movements).

Edited by cr88192

Share this post


Link to post
Share on other sites

, I'm not sure how you would deal with situations where one body displaces another, for instance by pushing into it.

 

time for you to experience the "Ah ha!" we all do when learning "move and check each in turn" collision checking.

 

you don't move a unit then run the checks, that's no different than moving them all.

 

you PRE-MOVE a unit:

 

x=unit.x

y=unit.y

 

// move x,y

 

// check new x.y for collision

 

if (collision) handle_collision

else

       {

        tgt.x=x;            // NOW move the unit, its ok, nothing in the way.

        tgt.y=y;  

        }

 

 

 

for handle_collision, you can calculate how far it could move, then just move it that far and stop, or bounce off, or whatever you want.  The point is that you know a collision will occur BEFORE you move. so you never move. and therefore you never have to UN-MOVE.   wink.png

 

 

once you experience the "Ah ha!" of this concept, you'll never have to worry about collision checking again in your entire life.  well, maybe not your entire life, but its worked for me for going on 20 years now at least, with no signs of being an issue in the foreseeable future.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

what types of checks depends on the level of accuracy required.   start with the fastest lowest resolution check (probably AABB). if AABB says no collision,you're done. if AABB says collision, and that's accurate enough for you, you're done.   if its not accurate enough, THEN apply progressively more accurate and slower checks, until you get the level of accuracy required (perhaps all the way down to pixel perfect in 3d).  Checks are only performed on collisions flagged as true by higher level less accurate checks.

 

you want to use the fastest lowest accuracy check you can.

 

if you need a slow accurate check, and the number of entities involved is low, you may be able to simply use the slow accurate check by itself. if its too slow that way, you'll have to use progressive checks.

 

maybe i should post a journal entry on collision checking, its not that big  deal. but it seems to keep coming up. whats the deal?  i thought i heard that someone wrote a book on it.  was it just an overview of a bunch of algos or something?

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!