Collision detection

1

Hello !
Me again with my game engine !
I have an other little problem with my physic engine …
I take some pieces of code of Humper (https://github.com/aloisdeniel/Humper) to make a collision detection and response velocity based, but there is something I can’t solve :

Every update, I have an entity who is velocity is set by that :

Step 1 :
velocity += (acceleration - friction * velocity) * gameTime.ElapsedGameTime.TotalSeconds

Then i calculate collision and if a collision is found, base on the velocity value (wich is the next move of my entity), I get a value wich corresponds to how I must decrease the velocity to avoid the colliion. It looks like this:

Step 2 :
float collisionResponse = FindCollision(myEntity) (value between 0 and 1)
velocity *= collisionResponse

And finally, I increase my entity position as much as the velocity is, multiplied by the GameTime to smooth the movement and avoid frame drop :

Step 3 :
position += velocity * gameTime.ElapsedGameTime.TotalSeconds

And everything works fine, I have a good value of gravity, I have good and smooth movements, my entity does’nt go through platform, etc …

Except one thing : The FindCollision() return the exact value wich make my entity beside the platform (Step 2), but then in the Step 3, when I add the velocity I must multiply that exact velocity by the elapsed time wich make my velocity slower too soon so my entity slow down before he is next to the platform when he should stop when he has reaches it.

Can you help me ? I know the problem come from the gameTime.ElapsedGameTime.TotalSeconds but I dont know what to do because if I remove this, my entity go very very too fast.
Thanks !

(Sorry if you did’nt understand something, just tell me and I’ll try to say it in another way (I’m french and I dont like Google Translate :P)(Oh ! A bracket in another bracket !))

Just a sketch of how its made:

2

Just glancing this over i see one thing that might be messing you up.

(acceleration - friction * velocity)

evaluates to

var a = friction * velocity;
var b = acceleration;
var c = b - a;

so when
acceleration = 2
friction = 1
velocity = 2

you get
0 = (2 - (1 * 2))
when acceleration is zero you get
-2 = (0 - (1 * 2)
when friction is -2 velocity is 2 acceleration is 2 you get
6 = (2 - (-2 * 2)

Point is the formula looks wrong.
Should be something like.

(acceleration + (velocity / friction)
or
( (acceleration / friction) + (velocity - friction))

3

Friction is likely a number between 0 and 1 in which case the formula makes perfect sense.

1 Like
4

Time is continuous. Instead of thinking about a frame with some duration, think about the flow of time. When your character walks into a wall, the time it happens at can be anywhere within a frame. You should ideally not let the start or end of a frame affect the way you do physics.
Think of the duration of a frame as the budget you have to spend each frame. You spend time by updating the position of your character (if you have multiple physics entities they all have their own budget). Then here’s what you do:

  • Determine the time of the first collision based on current velocity (not the position). This should be done relative to your total time budget (e.g. time .5 is a collision halfway through the frame, time 1 is a collision just at the end of the frame). Let’s call this toi for time of impact. If toi > 1 we don’t have a collision this frame and we’re done! Else continue with the next step
  • Update the position of the character by adding toi * frameDuration. This will put him right at the point of impact.
  • modify character velocity as a result of the collision (e.g. when bouncing into a vertical wall set x velocity to 0).
  • the time up until toi is now spent. But we still have 1 - toi left! Repeat from the start until toi > 1.

Note: you don’t have to normalize the time to a 0-1 range, you can use 0 - frame duration just as well, but I like it better this way :stuck_out_tongue:

This is the fancy way of doing it. In the example image you posted the block could slide down after hitting the wall in the same frame. If you do just 1 iteration you’ll get what’s in the image. In this case an easier alternative is instead of changing the velocity to stop right before the collision, set the position of the character to just before the collision and then change velocity like previously mentioned.

Edit: I think I have some code lying around for the toi stuff. Let me know if you’re interested!

1 Like
5

I already have a toi value, its my collisionResponse (In fact I think collisionResponse
is toi). It’s the time where the velocity has collide the wall and I also have a Slide version to preserve the velocity. (img at the end)
When collisionResponse is 1, the entity position + velocity reaches the destination but if : collisionResponse < 1, there is a collision at the time value of collisionResponse (E.g 0.5f if the collisions is halfway through the frame :wink:). So I aleady have a toi value. But this value is changed at Step 3 when I multiplied it by the gameTime :confused:.

But maybe I misunderstand something :stuck_out_tongue:

Ans also, what do you mean y frameDuration ? Its gameTime.ElapsedGameTime.TotalSeconds ? If not, how can i get it ?

So im interested by your code for toi :grin:
For my collision I take code of Humper but also of this article : https://www.gamedev.net/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084

And I can do a slide response to preserve the velocity like that (but still the same problem):
https://www.gamedev.net/uploads/monthly_04_2013/ccs-146537-0-83526600-1366678432_thumb.png

Here a better idea of the problem:

6

Yes, that’s what I mean.

You want to keep your step 1 the same, but step 3 is wrong. After multiplying with the collisionResponse, to move your character to the point of collision you’d need to do position += velocity. But the velocity at the end of the function call will depend on where in the frame the collision occured (because of collisionResponse, which is relative to the frame), which can cause some issues the next frames. That’s why I prefer the method I explained above.

The core of the method is this:
Rather than changing the velocity in step 2, first update the position of your character with position += velocity * (toi * gameTime.ElapsedGameTime.TotalSeconds) i.e. move the character to the point right before the collision (the red box in the images), then change the velocity to respond to the collision (set velocity.x to 0 in the example).

I’ll see if I can find my old code for this :slight_smile:

1 Like
7

Have you verified that FindCollision is returning the correct fraction? If it was returning a value less than expected, I would expect to see what your animation shows.

1 Like
8

Its true that I did’nt check if it works correctly, but after multiple tests, I can say it return the exact value expected :grin:

OK, so I implemented that in my code :

First without the gameTime:

Then, smooth movement by adding the gameTime:

And finally, hack my code and fix some other bugs with the spatial hash, and we got this (click to see) :

A very happy dummy target !!!Who can jump and jump and … jump again !

Thank you very muck for your time and your help ! :stuck_out_tongue_closed_eyes:

(And if you retrieve your old code for this it may be very helpful for me to optimize or change some part of my code. (My code for the collision is a little bit messy :P) (Damn, another BracketIntoAnotherBracket ! ))