Determining which line to collide with

I am making a platformer, where my player is represented as a circle and the ground is represented as lines. The actual collision detection and resolving works, it's just an edge case I can't find a solution for.

I check on which line the hero is by using the normal, and if the hero's center is between these normals I know he is on that line. That works except for the case in the image above. When he get's in the 'Problematic Area' the algorithm will not detect any collision.

So how do I know which line to pick for the collision when the hero get's in this area?

Here is some code that shows how I test collisions (which again works, but does not consider the problem I actually have).

playerPointer:Vector2D = New Vector2D(position.x - line.x1, position.y - line.y1)
lineNormal:Vector2D = line.vector.Copy()
lineNormal.LeftHandNormal()
playerOnNormal:Float = playerPointer.ProjectionOn(lineNormal)
playerOnLine:Float = playerPointer.ProjectionOn(line.vector)

#Do we have a collision between the circle and the infinite line

#Get the direction vector of the line
Local directionVector:= New Vector2D(line.x2 - line.x1, line.y2 - line.y1)

#Is the player inside the normals boundaries
If (playerOnLine <= directionVector.Length) And (playerOnLine >= 0)

• How are you computing collisions? – Mokosha Mar 26 '13 at 0:52
• I compute a vector from the lines origin to the player (player's center), project the normal onto it and see if it's smaller than the radius of the player. – shinkiro1 Mar 26 '13 at 1:01

A circle may be a bad choice. A rectangle (AABB) allows you to more easily use SAT here, which will in this case detect the bottom edge of the AABB as the normal.

Another option is to recognize that you don't just want line collision but also vertex collision. Using Voronoi Regions, the circle is in the region belonging to the vertex joining the lines. Using the normal between a vertex and a circle will give you the vector pointing from the vertex to the circle (or vice versa) which is exactly what you want. One way to handle this is to calulcate distance to any candidate vertex, then calculate distance to lines. When doing the line distance algorithm, you generally must clamp a t value to [0,1]; just ignore the line if the value is outside that range. Take the shortest found distance.

Yet another option I've never seen used but might work is to see that the circle collides with both lines, take both normals, and average them together. I don't think that's the best solution, but maybe it's the easiest option for you.

• Why wouldn't a circle work with SAT? The projection will just be the same along any axis right? – Mikael Högström Mar 26 '13 at 14:07
• You're right. You can do SAT with the circle, too. The math a little nicer with the AABB, though, IMO. – Sean Middleditch Mar 26 '13 at 19:56

Circle/line segment collision is the same as point/pill collision. A pill can be simplified as a box and two circles on the end points. Using your existing code you are only half way there. If you add point/circle collision to the line segment endpoints (and simply resolve your collision with whatever hits first) your problem goes away (as both line segments will have identical circles at that point), and you gain proper end point normals from the circle collision.

Here's a rough diagram showing what I mean. The gray lines are your original lines and the gray circle is your player's bounding circle. The collision resolution of that is equal to the black point of the circle and the black lines and circles that are extruded from the line segments that make up the box.

There's more detail in this question: A ball hits the corner, where will it deflect?

• Could you elaborate on this? And by 'whatever hits first' you mean simply looping through all segments and then stop? – shinkiro1 Mar 26 '13 at 14:28
• Per frame you'll do a trace against whatever things you might be colliding with and if you potentially would hit two different things you resolve using whatever is closest. – Tetrad Mar 26 '13 at 17:12