Gumgo 968 Report post Posted July 17, 2011 I'm currently trying to code up some 2D platformer physics. My goal is to get something along the lines of Super Metroid style movement. Level creation is done by drawing line segments to represent surfaces, so it should support slopes and not just horizontal/vertical surfaces. As a first attempt, I tried implementing swept capsule - line segment collision detection and response (code posted below). It is essentially this implementation: [url="http://www.peroxide.dk/papers/collision/collision.pdf"]http://www.peroxide....n/collision.pdf[/url], except using line segments and capsules instead of triangles and ellipsoids, and in 2D instead of 3D. Unfortunately I keep running into bugs which seem to be caused by floating point precision. I have a few questions relating to this, as well as the overall technique I'm using. (I've attached an image explaining what I mean for a lot of this.) 1. My implementation predicts when a capsule is about to hit a line segment, moves it close, and alters its velocity. However, it doesn't deal with the case where the capsule somehow is intersecting already with the line segment (it shouldn't happen with infinite precision, but of course, that doesn't exist). What's the best approach for handling this, since it seems to be causing problems. 2. Sometimes a capsule is able to get a distance of 0 from a line segment, rather than the enforced minimum epsilon distance. When this happens, a collision is always immediately detected after 0 time, so the capsule gets "stuck". How should I be dealing with these cases? (I guess this is the same as question 1.) 3. Right now to detect whether I'm on a surface, I check whether there are any line segments within an epsilon distance from the capsule that aren't too steep. If so, I don't apply gravity but instead move the capsule back and forth along the tangent vector. However, due to floating point, I believe the capsule sometimes gets a little bit "too far" and gravity kicks back in for 1 frame (3). What's the best approach for "consistently" keeping the player on a slope once they've hit? 4. There are a few issues I've noticed with the overall technique that don't seem to be quite what I expected. For example, when you collide upward with a sloped ceiling, you shoot off at the angle of the slope (1). Another example is walking over a "kink" in the floor - rather than following the floor, the player overshoots and then lands (2). What alternative platformer physics techniques exist that don't have these problems? 5. I really like the technique of swept collisions to solve for the exact intersection point since it doesn't have the problem other techniques do with fast moving objects (it is also very easy to test), but it seems very finicky - if you get floating point imprecision which brings the player just a little too close or too far from the line segment, the whole thing breaks. Is there an approach which uses the accuracy of sweep tests to find the closest intersection point but is more forgiving about precision? 6. Related to question 4 - perhaps I'm actually going about this all wrong... am I using the sweep tests incorrectly? Thinking more about it, sweep testing is only in the detection phase, and it's really my collision responses that are wrong. If someone could explain to me or point me to a description of an algorithm that uses sweep tests correctly/doesn't suffer from the finickyness, that would be really great. Here's the algorithm I've come up with (the actual code is more optimized) - I've tried to put it in readable pseudocode and explain it will with images, but let me know if it's unclear (note: "colliders" are line segments): [source] actor: a // this is the capsule we're colliding // check whether the actor is on the ground bool on_ground = false // whether ground is detected vec2 ground_normal // the normal vector we find for the ground Collider ground // the line we found to be the ground // this is the range the ground must be in float ground_range = epsilon * 3 // loop through each potential collider and see which one is closest float min_distance = FLOAT_MAX for each potential collider ls: // find the distance and normal vector of this collider to the capsule (img 4) ( float dist, vec2 normal ) = distance2( a.capsule, ls ) // make sure the distance is within range if dist >= 0 and dist < ground_range and dist < min_distance: if ls is not too steep: min_distance = dist ground_normal = normal ground = ls on_ground = true // now we apply either walking or gravity if on_ground: // if on the ground, apply walking // find a vector orthogonal to the ground normal vec2 right_vec = ground_normal.orthogonal() if right_vec.x < 0: right_vec.negate() // split the velocity into 2 components so we can edit the right/left velocity (img 5) float up_velocity = ground_normal.dot( a.velocity ) float right_velocity = right_vec.dot( a.velocity ) // adjust left/right velocity if walking right: if right_velocity < a.walk_speed: right_velocity = min( a.walk_speed, right_velocity + a.walk_acceleration ) else if right_velocity > a.walk_speed: right_velocity = max( a.walk_speed, right_velocity - a.walk_acceleration ) else if walking left: if right_velocity > -a.walk_speed: right_velocity = max( -a.walk_speed, right_velocity - a.walk_acceleration ) else if right_velocity < -a.walk_speed: right_velocity = min( -a.walk_speed, right_velocity + a.walk_acceleration ) else if standing still: if right_velocity > 0: right_velocity = max( 0, right_velocity - a.walk_acceleration ) else if right_velocity < 0: right_velocity = min( 0, right_velocity + a.walk_acceleration ) // recombine the velocity a.velocity = up_velocity*ground_normal + right_velocity*right_vec // if jumping, add some vertical speed if a.jump: a.velocity.y -= a.jump_speed else: // we aren't on the ground, so apply gravity if a.gravity > 0: a.velocity.y += a.gravity else if a.gravity < 0: a.velocity.y += a.gravity // now do the actual collision detection/response // we start out with 100% of the original velocity // each iteration, we subtract the percentage of the velocity we move until we reach 0 float velocity_remaining = 1 // the direction and magnitude of the current velocity vec2 next_velocity = a.velocity for r = 0 to MAX_ITERATIONS: // do some early outs first if velocity_remaining < epsilon or next_velocity.magnitude() == 0: break // we can only move the remaining portion of next_velocity vec2 velocity = next_velocity * velocity_remaining // get the magnitude of the velocity and find the normalized velocity float velocity_magnitude = velocity.magnitude() vec2 velocity_normalized = velocity / velocity_magnitude // when we do the sweep test, we actually use a slightly larger velocity // this is so we detect collisions that are at the very end of the velocity vector, // so we don't accidentally move right up next to any objects (img 6) vec2 larger_velocity = velocity + velocity_normalized*epsilon float larger_velocity_magnitude = velocity_magnitude + epsilon // loop through each potential collider and see which one we hit first // store the minimum sweep time in min_sweep_time and the collider in min_collision // store the normal vector of the intersection in min_isect_normal and the point of intersection in min_isect_point // (img 7) float min_sweep_time = 1 vec2 min_isect_normal vec2 min_isect_point Collider min_collision bool collision = false for each potential collider ls: // perform the sweep test using velocity plus epsilon (that is, velocity_larger) ( float sweep_time, vec2 isect_normal, vec2 isect_point ) = sweep( a.capsule, larger_velocity, ls ) // if this is the smallest time, store this potential collider if (sweep_time < min_sweep_time) { min_sweep_time = sweep_time min_isect_normal = isect_normal min_isect_point = isect_point min_collider = ls collision = true } } if !collision: // if there was no collision, we just move forward by the original velocity (remaining) velocity_remaining = 0 a.capsule.position += velocity else: // there was a collision! now things get tricky // the sweep time is currently in terms of larger_velocity // however, this was just to make sure there wasn't an object "just out of reach"; // that is, within epsilon units from the end of the velocity vector // larger_velocity is velocity + epsilon, so we need to get // sweep time back in terms of velocity float actual_min_sweep_time = min_sweep_time * (larger_velocity_magnitude / velocity_magnitude) // we move to the point of collision float move_magnitude = velocity_magnitude * actual_min_sweep_time // now there's a problem; we never want to get within epsilon units of the collider // we could just subtract epsilon from move_magnitude, however that doesn't account for grazing angles // see (img 7) for visual explanation // instead, we solve for the magnitude of the velocity vector that will bring us epsilon units from the collider // see (img 8) for visual explanation // first, we find the point on the capsule that the collision would occur at if moved along velocity vec2 isect_on_capsule = min_isect_point - actual_min_sweep_time*velocity // now we parameterize this point as p + vt; that is, moving along the velocity vector // we solve for t such that the distance between p + vt and the collider is equal to epsilon // n = min_isect_normal, i = min_isect_point, p = isect_on_capsule, v = velocity, t = time, d = distance // d = n . ((p + vt) - i) // d = n.(p + vt) - n.i // d = n.p + n.vt - n.i // d = n.vt + n.p - n.i // d = n.vt + n.(p-i) // d - n.(p-i) = n.vt // t = (d + n.(i-p)) / n.v // we want to solve for when d = epsilon float denom = min_isect_normal.dot( velocity ) if denom != 0: // find t float t = (epsilon + min_isect_normal.dot( min_isect_point - isect_on_capsule )) / denom // this is the maximum we can move before we get epsilon distance float max_allowed_move_magnitude = velocity_magnitude * t // if our current velocity magnitude exceeds this, set it to max_allowed_move_magnitude instead if max_allowed_move_magnitude < move_magnitude: move_magnitude = max_allowed_move_magnitude // make sure we're not moving further than the original velocity or backward move_magnitude = clamp( move_magnitude, 0, velocity_magnitude ) // adjust the remaining velocity based on the percent move_magnitude is of the original magnitude velocity_remaining *= (1 - move_magnitude / velocity_magnitude) // perform the move by moveMagnitude vec2 move = velocity_normalized * move_magnitude a.capsule.position += move // we need this still, so move it also isect_on_capsule += move // now that we have moved epsilon way from the collider, we find our new velocity vector // we need to figure out the next velocity based on the angle of the collider // we want to move to a point down the collider which is also epsilon away from it // therefore, we find the point on the collider we would want to move to and push it out by epsilon // first find the vector to slide along - this is orthogonal to the collider's normal vec2 slide_vector = min_isect_normal.orthogonal() // the new velocity is the component of the velocity in the direction of slide_vector, // since the collider absorbed the perpendicular force // we find the destination point on the slope vec2 destination = min_isect_point + slide_vector * slide_vector.dot( next_velocity ) // again, we don't want to move to the collider, we want to move a little bit away destination += min_isect_normal * epsilon next_velocity = destination - isect_on_capsule // loop another iteration // finally, set the actor up for the next frame with the new velocity a.velocity = next_velocity [/source] Thanks in advance. EDIT: Anyone? How about if I rephrase it like this: I am able to successfully detect exact intersection points between objects (capsule to line) using sweep tests. Now that I have this functionality, what approach should I take to implement "stable" collision which doesn't break if something goes a bit wrong with small values? 0 Share this post Link to post Share on other sites