Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have been reading plenty of tutorials about sliding collision responses yet I am not able to implement it properly in my project. What I want to do is make a puck slide along the rounded corner boards of a hockey rink. In my latest attempt the puck does slide along the boards but there are some strange velocity behaviors. First of all the puck slows down a lot pretty much right away and then it slides for awhile and stops before exiting the corner. Even if I double the speed I get a similar behavior and the puck does not make it out of the corner. I used some ideas from this document http://www.peroxide.dk/papers/collision/collision.pdf.

This is what I have:

Update method called from the game loop when it is time to update the puck (I removed some irrelevant parts). I use two states (current, previous) which are used to interpolate the position during rendering.

public override void Update(double fixedTimeStep)
{
    /* Acceleration is set to 0 for now. */
    Acceleration.Zero();

    PreviousState = CurrentState;

    _collisionRecursionDepth = 0;

    CurrentState.Position = SlidingCollision(CurrentState.Position, CurrentState.Velocity * fixedTimeStep + 0.5 * Acceleration * fixedTimeStep * fixedTimeStep);

    /* Should not this be affected by a sliding collision? and not only the position. */
    CurrentState.Velocity = CurrentState.Velocity + Acceleration * fixedTimeStep;

    Heading = Vector2.NormalizeRet(CurrentState.Velocity);
}

private Vector2 SlidingCollision(Vector2 position, Vector2 velocity)
{
    if(_collisionRecursionDepth > 5)
        return position;

    bool collisionFound = false;

    Vector2 futurePosition = position + velocity;

    Vector2 intersectionPoint = new Vector2();

    Vector2 intersectionPointNormal = new Vector2();

    /* I did not include the collision detection code, if a collision is detected the intersection point and normal in that point is returned. */

    if(!collisionFound)
        return futurePosition; /* If no collision was detected it is safe to move to the future position. */

    /* It is not exactly the intersection point, but slightly before. */
    Vector2 newPosition = intersectionPoint; 

    /* oldVelocity is set to the distance from the newPosition(intersection point) to the position it had moved to had it not collided. */
    Vector2 oldVelocity = futurePosition - newPosition;

    /* Project the distance left to move along the intersection normal. */
    Vector2 newVelocity = oldVelocity - intersectionPointNormal * oldVelocity.DotProduct(intersectionPointNormal);

    if(newVelocity.LengthSq() < 0.001)
        return newPosition; /* If almost no speed, no need to continue. */

    _collisionRecursionDepth++;

    return SlidingCollision(newPosition, newVelocity);
}

What am I doing wrong with the velocity? I have been staring at this for very long so I have gone blind. I have tried different values of recursion depth but it does not seem to make it better. Let me know if you need more information. I appreciate any help.

EDIT: A combination of Patrick Hughes' and teodron's answers solved the velocity problem (I think), thanks a lot! This is the new code:

I decided to use a separate recursion method now too since I don't want to recalculate the acceleration in each recursion.

public override void Update(double fixedTimeStep)
{
    Acceleration.Zero();// = CalculateAcceleration(fixedTimeStep);

    PreviousState = new MovingEntityState(CurrentState.Position, CurrentState.Velocity);

    CurrentState = SlidingCollision(CurrentState, fixedTimeStep);

    Heading = Vector2.NormalizeRet(CurrentState.Velocity);
}

private MovingEntityState SlidingCollision(MovingEntityState state, double timeStep)
{
    bool collisionFound = false;

    /* Calculate the next position given no detected collision. */
    Vector2 futurePosition = state.Position + state.Velocity * timeStep;

    Vector2 intersectionPoint = new Vector2();

    Vector2 intersectionPointNormal = new Vector2();

    /* I did not include the collision detection code, if a collision is detected the intersection point and normal in that point is returned. */

    /* If no collision was detected it is safe to move to the future position. */
    if (!collisionFound)
        return new MovingEntityState(futurePosition, state.Velocity);

    /* Set new position to the intersection point (slightly before). */
    Vector2 newPosition = intersectionPoint;

    /* Project the new velocity along the intersection normal. */
    Vector2 newVelocity = state.Velocity - 1.90 * intersectionPointNormal * state.Velocity.DotProduct(intersectionPointNormal);

    /* Calculate the time of collision. */
    double timeOfCollision = Math.Sqrt((newPosition - state.Position).LengthSq() / (futurePosition - state.Position).LengthSq());

    /* Calculate new time step, remaining time of full step after the collision * current time step. */
    double newTimeStep = timeStep * (1 - timeOfCollision);

    return SlidingCollision(new MovingEntityState(newPosition, newVelocity), newTimeStep);
}

Even though the code above seems to slide the puck correctly please have a look at it.

I have a few questions, if I don't multiply by 1.90 in the newVelocity calculation it doesn't work (I get a stack overflow when the puck enters the corner because the timeStep decreases very slowly -> a collision is found early in every recursion), why is that? what does 1.90 really do and why 1.90?

Also I have a new problem, the puck does not move parallell to the short side after exiting the curve; to be more exact it moves outside the rink (I am not checking for any collisions with the short side at the moment). When I perform the collision detection I first check that the puck is in the correct quadrant. For example bottom-right corner is quadrant four i.e. circleCenter.X < puck.X && circleCenter.Y > puck.Y is this a problem? or should the short side of the rink be the one to make the puck go parallell to it and not the last collision in the corner?

EDIT2:

This is the code I use for collision detection, maybe it has something to do with the fact that I can't make the puck slide (-1.0) but only reflect (-2.0):

/* Point is the current position (not the predicted one) and quadrant is 4 for the bottom-right corner for example. */
if (GeometryHelper.PointInCircleQuadrant(circleCenter, circleRadius, state.Position, quadrant))
{
    /* The line is: from = state.Position, to = futurePosition. So a collision is detected when from is inside the circle and to is outside. */
    if (GeometryHelper.LineCircleIntersection2d(state.Position, futurePosition, circleCenter, circleRadius, intersectionPoint, quadrant))
    {
        collisionFound = true;

        /* Set the intersection point to slightly before the real intersection point (I read somewhere this was good to do because of floting point precision, not sure exactly how much though). */
        intersectionPoint = intersectionPoint - Vector2.NormalizeRet(state.Velocity) * 0.001;

        /* Normal at the intersection point. */
        intersectionPointNormal = Vector2.NormalizeRet(circleCenter - intersectionPoint)
    }
}

When I set the intersection point, if I for example use 0.1 instead of 0.001 the puck travels further before it gets stuck, but for all values I have tried (including 0 -> the real intersection point) it gets stuck somewhere (but I necessarily not get a stack overflow). Can something in this part be the cause of my problem?

I can see why I get the stack overflow when using -1.0 when calculating the new velocity vector; but not how to solve it. I traced the time steps used in the recursion (initial time step is always 1/60 ~ 0.01666):

Recursion depth   Time step next recursive call
[Start recursion, time step ~ 0.016666]
0                 0,000985806527246773
[No collision, stop recursion]
[Start recursion, time step ~ 0.016666]
0                 0,0149596704364629
1                 0,0144883449376379
2                 0,0143155612984837
3                 0,014224925727213
4                 0,0141673917461608
5                 0,0141265435314026
6                 0,0140953966184117
7                 0,0140704653746625
...and so on.

As you can see the collision is detected early in every recursive call which means the next time step decreases very slowly thus the recursion depth gets very big -> stack overflow.

share|improve this question
    
Just a remark on the expected outcome deduced from this snippet: when colliding with a wall, the puck won't really bounce back, but be shifted tangentially to that wall because of the newVelocity component. For better and accurate results, please check with the already given answer and try and use a time step in the collision detection code and in the update equations. Do chime in with what's happening when a collision occurs. Set break points and see whether the collision code gets called even when there's no such event being triggered. The puck shouldn't slow down before a collision. –  teodron May 20 '12 at 20:59
add comment

2 Answers

up vote 4 down vote accepted

Refer to the following picture: collision with a plane

Say we are at instance t and we want to get the velocity and position of the entity at time t+Dt. The simplest and crudest pseudocode comprising collision detection, handling and naive Euler integration would then be:

     predictedPos = oldPos + oldVelocity * Dt;
     if ( insideSurface(predictedPos) )
     {
        intersectionPoint = intersect(Plane, oldPos, predictedPos);
        normalVel = dot(planeNormal, oldVelocity) * planeNormal; // yellow arrow
        intersectionTime = length(oldPos, intersectionPoint) / length(oldPos, predictedPos) * Dt;
        timeLeft = Dt - intersectionTime; // the time left for the ball to travel from the intersection point to the corrected position
        newVelocity = oldVelocity - 1.9 * normalVelocity; // geometrically reflect the velocity using the plane's normal
        correctedPos = intersectionPoint + timeLeft * newVelocity;
     }
     else
     {
        correctedPos =  oldPos + oldVelocity * Dt;
        newVelocity = oldVelocity;
     }
     oldVelocity = newVelocity + acceleration * Dt;
     oldPos= correctedPos;

Acceleration can be anything: gravity, -b* oldVelocity - a drag force or even a constant if you plan on having a rocket boosted hockey puck. Note that -1.90 * normalVelocity is used to geometrically reflect the velocity, but also to "dampen" it as an effect of an imperfect elastic collision. If you don't want to lose energy, just use 2.0 * normalVelocity instead for perfect reflections.

For a sliding behaviour use this trick:

     predictedPos = oldPos + oldVelocity * Dt;
     if ( insideSurface(predictedPos) )
     {
        intersectionPoint = intersect(Plane, oldPos, predictedPos);
        normalVel = dot(planeNormal, oldVelocity) * planeNormal; // yellow arrow
        intersectionTime = length(oldPos, intersectionPoint) / length(oldPos, predictedPos) * Dt;
        timeLeft = Dt - intersectionTime; // the time left for the ball to travel from the intersection point to the corrected position
          // cancel out the normal component
          newVelocity = oldVelocity - 1.0 * normalVelocity;
          // correct the magnitude
          newVelocity = length(oldVelocity) / length(newVelocity) * newVelocity;
        correctedPos = intersectionPoint + timeLeft * newVelocity;
     }
     else
     {
        correctedPos =  oldPos + oldVelocity * Dt;
        newVelocity = oldVelocity;
     }
     oldVelocity = newVelocity + acceleration * Dt;
     oldPos= correctedPos;

This way, you make sure the newVelocity has the same magnitude as the oldVelocity, hence no energy loss, hence no "slowing down".

Collision with a circular rink/wall Refer to the picture below: enter image description here Say your collision handling method looks like:

  HandleCollision( currPos, currVel, timeSlice, outPos, outVel)

Then you should compute a possible collision between your object and the rink, then from the intersecion point, with a new (reflected) velocity, call again this method until the time left to travel is zero or either the puck is completely inside the circle. In naive pseudocode:

  HandleCollision( currPos, currVel, timeSlice, outPos, outVel)
  {
       bool intersects = IntersectWall(currPos, currVel, timeSlice, intPos);
       if (intersects)
       {
           // time left to travel after collision
           timeLeft = timeSlice - length(currPos - intPos) / length(currVel);           
           newPos = intPos;
           normal = normalize(intPos - circleCenter);
           // reflection with losses (energy)
           newVel = currVel - 1.90 * dot(currVel, normal) * normal;
           // check for collisions 
           HandleCollision(newPos, newVel, timeLeft, outPos, outVel);
       }
       else
       {
           outPos = timeSlice * currVel + currPos;
           outVel = currVel;
       } 
  }

Checking with the picture: the initial time step is t0, but when the puck still has t1 units to go, it hits the wall at P1. Now, the procedure is called again, this time t2=t1 is the time left to travel. When it hits the wall again, at P2, is still got some t3 units left to go. Again, we set the current position to P2 and reflect the velocity. Using t3 and the reflected velocity, we end up with the final position, P3. This is just one example depicting how the method should work, conceptually.

Working sample

Using Ogre as a render engine, I've written this terribly simplified update function:

 void BaseApplication::PerformCollision(Ogre::Vector2 currPos, Ogre::Vector2 currVel, double timeSlice, Ogre::Vector2 &outPos, Ogre::Vector2 & outVel)
 {
Ogre::Vector2 newPos, newVel = currPos;
newPos = currPos + currVel * timeSlice;

if (newPos.length() > mRadius)
{
    //collision
    Ogre::Vector2 intPos = currPos;
    double timeLeft = timeSlice;
    Ogre::Vector2 normalVec = newPos;
    normalVec = normalVec / normalVec.length();
    Ogre::Vector2 reflVel = currVel - 1.9f * normalVec * normalVec.dotProduct(currVel);
    PerformCollision(intPos, reflVel, timeLeft, outPos, outVel);
}
else
{
    outPos = newPos;
    outVel = currVel;
}
 }

this is how it should work..

share|improve this answer
    
Thanks a lot I think I know how it works now, but I still can't get it to work properly (-1.0 = stack overflow). Is your sliding code suppose to be a recursion? I thought a sliding collision response always was. When I use -2.0 at low speeds I can see that the puck oscillates along the arc of the circle; I think if I can make -1.0 work this will go away. I have added my collision detection code to the first post, maybe something is wrong with that? Depending on how I set the intersection point the puck gets stuck at different places in the corner. Maybe this is the cause of my problem? –  dbostream May 22 '12 at 18:51
    
I can add that I tested the sliding collision response code when colliding with one of the long sides of the rink and it works perfectly. I also tested the sliding code in a corner with twice the radius and it had the same problem as the smaller one. Finally if I use the exact intersection point when I assign newPostion the collision check sometimes fail. –  dbostream May 22 '12 at 20:04
    
Theoretically, you can do without recursion, because the amounts and functions here are linear and you do not aim for a physically based simulation. That's what I tried to infer: just detect where the puck intersects the rink, detect how much time has elapsed from oldPos to intersectPos and subtract this time from the timestep Dt. The remaining time can be used to propagate your puck further with the reflected velocity. That way you avoid any unnecessary recursion. Of course, for more intricate scenarios, stick with recursion. Good luck –  teodron May 23 '12 at 7:35
1  
Vimeo sucks badly, here's the youtube link –  teodron May 30 '12 at 14:45
1  
Took a break from this but I guess using -1.8 will have to do. Thanks for all the help. –  dbostream Jun 9 '12 at 15:24
show 11 more comments

Your recursion isn't handling time, and without knowing how much time was used out of the fixed step in the calling function you can't move your position in any real way.

Because new position = old position + velocity * time.

If you recurse on the Update() function instead of SlidingCollision() and figur out how much time had been used before the collision and used that value to pass back into Update() then this might work like you expect.

Example:

Update( 1.0 )
  hit something at 0.75 of my full possible move
  Update( 0.25 )
    hit something at 0.5 of my full possible move
    Update( 0.125 )
      nothing hit
    pop
  pop
returns

At least I think that's it.

share|improve this answer
    
Thanks I will consider that. But if you look at appendix F of the link I posted there is no time in that recursion either. The velocity passed to SlidingCollision is based on fixedTimeStep shouldn't that be enough? First call to SlidingCollision gets the full distance to move (as velocity), then for each recursive call velocity is decreased by (futurePositon-intersectionPoint). After a number of recursions we have moved the entire step initially passed to the first SlidingCollision call (as velocity). So as long as the puck moves the same distance on each Update() I dont see why it slows down. –  dbostream May 20 '12 at 21:14
    
Something's not working and this is a solution I used a while ago and thought it might help. The real physics of it is that once the puck doesn't bounce off and begins the slide around it becomes part of the wall's reference frame and it's no longer a collision problem but one of friction slowing the puck (not collision) and the wall pushing back equally against the puck's push into it at an angle based on the radius of the curve. –  Patrick Hughes May 20 '12 at 21:45
    
@dbostream Just for the fun of it, try using a damped collision reflection: Vector2 newVelocity = oldVelocity - 1.90 * intersectionPointNormal*oldVelocity.DotProduct(intersectionPointNormal); –  teodron May 21 '12 at 14:21
    
@teodron The big loss in speed at the beginning of the slide is gone, however the puck is still slowing down and eventually comes to a halt in the corner. Care to explain where 1.90 comes from? –  dbostream May 21 '12 at 15:44
    
@PatrickHughes I will try your suggestion now. –  dbostream May 21 '12 at 15:55
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.