# Simulation basics, step order and colission detection

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

## Recommended Posts

I've been thinking about how to add collision to my hobby project, and I haven't been able to find a few answers to some basic issues I have with the simulation itself.

First is, the order in which the different parts of the simulation should be applied. Say I have a series of forces acting on a particle, applying an acceleration that depends on it's position (such as gravity). Should I calculate the forces, apply them to the object (modifying it's speed), then move it, or move it using the speed from the last frame, then recalculate forces and apply accelerations to get the speed for the next frame? It seems to me at first glance that in the general case this order would not matter, and the results would be the same (except for frame number, one would run one frame behind the other).

But then you add player input, say an acceleration in a given direction. So the order I was thinking is, I detect the player accelerating, I add that acceleration to the sum of accelerations that the object is under, modify the speed of the object and then update. That way I minimize the lag between the player action and the result. Little diagram below:

immediate -
Frame 0 - Player action
Frame 1 - add player + env acceleration, modify speed, apply modified speed -> new position

delayed -
Frame 0 - Player action
Frame 1 - Apply frame 0 speed -> new position; add player + env acceleration modify speed -> frame 1 speed
Frame 2 - Apply frame 1 speed -> new position;

But then I want to add some basic collision detection (sphere-sphere, meaning distance from center of object).

The idea I'm having is I need to first determine the new positions for all the objects (either delayed or immediate doesn't matter). I'm thinking my 'physical state' needs to be 'double buffered', meaning I don't overwrite positions as I go but rather keep the old state and write the new speeds and positions to a... buffer, I guess. On the buffer I then run the collision detection, first making a pass to determine all the collisions (I figured this was necessary in case one object collides with two others, if I go solving collisions as I find them I might move the first two objects away and leave the third undisturbed).

For an object 'n' with position p(n), and radius r(n), there's a collision if

length(p(a)-p(b)) < r(a)+r(b).

Once I have a list of the collisions, I can start resolving them. My first idea is, since this is sphere-sphere, to determine at what time between frame(prev) and frame(current) the collision happened, and what the correct position should be. I assume for this that the speeds, s(a) and s(b) are constant between frames. I know the previous positions before the collision, and the current positions, and thus the speed of the collision. The distance they covered while colliding is

dist = r(a)+r(b)-length(p(a)-p(b)) -- (we already checked that length(p(a)-p(b)) is lower than r(a)+r(b) to determine they collided).

So they collided t time ago, where t = dist / length(s(a)-s(b)). We can determine their impact positions, then, as

pc(n)=p(n)-s(n)*t,

which backs them up in the simulation to the time of impact. Then we calculate the velocity using elastic collision physics (I don't recall the exact formulation, but basically I remove the center of mass speed, reflect the speed along the collision plane, then add the CoM speed again), and advance them along the new speed vectors to their correct positions,

pnew(n)=pc(n)+snew(n)*t

The thing is, though, that I now need to make sure they're not colliding in their new positions with anyone else. Thankfully, I only need to check a and b (in the case of simple collision) against any other objects, not everyone against everyone. I suppose I would need a bit of recursion where, if I find a collision in the new positions, I run the collision resolution again between these bodies. Thankfully, t would grow smaller and smaller with each collision so I'll eventually reach a point when I'm not colliding any more.

This would mean then that the order should be

Frame 0 - Player action
Frame 1 - Add player + env acceleration, modify speed, apply modified speed -> new position, loop until all collisions resolved(run collision detection, run collision resolution -> new positions)

So I guess my question is, have I made any glaring errors? Missed obvious optimizations or thought too much? I know I'll need to partition space to cull impossible collisions and the like, I'm curious about the actual collision resolution, and for the sphere-sphere case only.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11
×

## Important Information

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!