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.

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!

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).

, 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.

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.

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?