How to prevent newer Collisions bypassing old collisions? (2D)

Question

I'd like to make my own collision system with polygons in C++. There are static colliders (never move, can't be pushed) and dynamic ones (can move, can never be inside static colliders.). My current approach is:

for (auto &dyn : dynamicColliders) {
    for (auto &stat : staticColliders) {
        // "how deep" is any vertex of dyn inside of stat? Store that in t.
        //    Is dyn inside stat (0 <= t <= 1)? -> push dyn outside by t
        // not inside? -> next 2 lines
        // "how deep" is any vertex of stat inside of dyn? Store that in r.
        //    Is stat inside dyn (0 <= r <= 1)? -> push dyn outside by r.
    }
}

Here's an Example of what happened:

https://youtu.be/XeGga98ZtUY

Basically, the squares are static objects. The hexagon is dynamic. Now, when the hexagon collides into the bottom square, it is pushed into the top square. The top square however pushes the hexagon back into the bottom square. (Now, the physics step is over. The false bottom collision isn't minded anymore. This order happens cause the top square is the "newest" collision object)

What I tried:

1. Summing all "Push" vectors and adding them at the end
2. Cancel the movement in the current physics step completely if there's a collision after being pushed outside of a square.
3. (Above approach)

Results:

1. Didn't work: Hexagon got pushed into below square, that it didn't collide with before.
2. Actually works, but extremely glitchy. I can't glide along a square because it's cancelled.
3. (See above video)

How would one avoid the bypassing of this type of collision? Thanks a lot!

Answer 1

This single point approach to colision detection is (sadly) not going to work. Since it models every object at a single point where the collision occures, it does not take into account the fact that the object may have also colided somewhere else so cannot move or rebound in the direction it tries to push it.

You need to check all of the points it collides with using whatever detection system you are using, then have your collsion handling logic react based on the valid directions it can go in.

If you are also building the detection system (which it sounds like from your question) then you will need an efficent algorithm for mapping possible colision points in 2d space, you probably want an implementation of Nearest Neightbor Search with a kd-tree. You can find many C++ libraries to do this for you.

(Note that a kd-tree loses balance with every insertion and removal, therefore you should have a dynamic tree for your moving points which gets rebalanced periodically and a static tree for your static points which can be left alone)