The player's collider is an axis-aligned bounding box in my 2D platformer, but the environment can be different shapes. I already have collision-detection that prevents the player from going through colliders, but I don't have anything for getting the player out of concave polygons if he ends up inside one by for example flipping the collider when changing direction from/to left/right.

SAT doesn't work on concave polygons, so I need an algorithm that can tell me if an AABB and any polygon intersects and give me the minimum translation vector to push the shapes apart. (The velocity of the objects will not need to be considered).

BTW the game is written in C# with the MonoGame framework if that's of any relevance.

  • 2
    \$\begingroup\$ Every concave polygon can be cut into multiple smaller convex polygons \$\endgroup\$ – Bálint Aug 7 '17 at 7:01
  • \$\begingroup\$ I know, but that wasn't my question. I don't want to make sure every single polygon in the game is cut into convex polygons, it's prone to human error and is bound to leave a small bug that is hard for me to spot that will break the game. It's more unnecessary work. \$\endgroup\$ – Martin Aug 7 '17 at 7:56
  • 2
    \$\begingroup\$ there are already algorithms for this, then you can use a simple SAT collision detection \$\endgroup\$ – Bálint Aug 7 '17 at 12:48
  • \$\begingroup\$ Could you recommend any algorithms? Should I use it in-game, or in my level editor? \$\endgroup\$ – Martin Aug 7 '17 at 13:15
  • \$\begingroup\$ mathoverflow.net/questions/60212/… and when yoh save it \$\endgroup\$ – Bálint Aug 7 '17 at 21:23

If your game starts with the player AABB completely outside of the concave polygon, then I would solve an easier problem:

Test the edges (line segments) of the polygon against the AABB. If you have an intersection, just push out the AABB so it is on the correct side of the linesegment.

Your polygon is probably counter-clockwise, so you know which part of the edge is "inside" and which part of the edge is "outside."

enter image description here

Beware this can cause "tunnelling" if your AABB moves too fast and goes from completely outside the polygon to completely inside the polygon within a single simulation step.

To do edge-versus-AABB in 2D, you can use the Cohen-Sutherland algorithm.

| improve this answer | |

Intersecting a polygon P with a box/rectangle R is the essence of clipping, so you could use a clipping algorithm. There are several, e.g., the Cohen-Sutherland algorithm. A box R and a polygon P intersect if (and only if), when you clip P to the box R, the result is not empty, i.e., some parts of P are inside R.

| improve this answer | |
  • \$\begingroup\$ What is clipping? I do have the AABB of P (the bounds), but I don't see how my goal is achieved by comparing the box with the AABB surrounding P. Also I want to check if R overlaps P, which is a lot harder than checking if all vertices of P are inside R. \$\endgroup\$ – Martin Aug 7 '17 at 15:17
  • \$\begingroup\$ @Martin: Perhaps I did not understand your goal. I will add a reference for clipping, and remove the other discussion, which I now see is irrelevant. \$\endgroup\$ – Joseph O'Rourke Aug 7 '17 at 15:26
  • \$\begingroup\$ Oh, wait now I remember. Clipping is connected to rendering and I already have that in my game. Unfortunately, it has nothing to do with my collision-detection problem. I'm talking about the physics. \$\endgroup\$ – Martin Aug 7 '17 at 15:37
  • \$\begingroup\$ @Martin: Clearly we are talking past one another. I'll leave it to someone else to perhaps clarify. \$\endgroup\$ – Joseph O'Rourke Aug 7 '17 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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