Implementing collision response, current implementation does too many checks

Question

I don't know how I should handle my collision response when collision between two entities leads to second collision with third entity.

Blue arrow is velocity of the rightmost entity and numbers below are single collision response.

Single Collision

At the beginning leftmost and middle entities are not colliding with each others, but after rightmost entity collides with middle one, the velocity middle entity gains now causes it to collide with leftmost one

How end result should be

Or if the leftmost entity was a wall -> 0, 0, -v

Current implementation: check collisions until all are handled

Velocities before collision handling

• 0, 0, <-10
• Collisions: 2&3

If entity velocity is changed due the collision do new check

After 1. collision check:

• 0, <-5, <-5
• Collisions: 1&2

After 2. collision check:

• <-2.5, <-2.5, <-5
• Collisions: 2&3

After 3. collision check:

• <-2.5, <-3.75, <-3.75
• Collisions: 1&2

After 4. collision check:

• <-3.125, <-3.125, <-3.75
• Collisions: 2&3

After nth collision check:

• <-3.33, <-3.33, <-3.33
• No collisions
• Continue

Question: As we clearly see, it takes way too many collision checks to fix even simple collisions this way. How should I improve or redo this?

Sample code written with sfml:

I have 3 types of entities in my test case:

• wall
• pushable
• passable

Entity, velocity and boundingRect:

Collision response:

• wall <-> pushable: can't move inside wall, push pushable entity away
• pushable <-> pushable: both are repelled from each others so they won't collide
• wall<->wall: skip collision checks between walls and all checks with passable terrain

Controls in sample code

• Arrow keys: move green entity
• Left mouse button: spawn pushable entities
• Right mouse button: spawn wall entities
• Middle mouse button: spawn moving pushable entities

.

#include <SFML/Graphics.hpp>
#include <iostream>

const sf::Vector2f entitySize(16.f, 16.f);

bool isMovingUp = false;
bool isMovingDown = false;
bool isMovingRight = false;
bool isMovingLeft = false;

enum Category
{
    wall,
    pushable,
    passable,
};

class Entity
{
    public:
        Entity(sf::Vector2f position, sf::Color color, Category type) : position(position), type(type)
        {
            shape.setSize(entitySize);
            shape.setFillColor(sf::Color::Transparent);
            shape.setOutlineColor(color);
            shape.setOutlineThickness(1.f);
        }

        sf::Vector2f position;
        sf::Vector2f velocity;
        sf::Vector2f adjustedVelocity;
        sf::Vector2f defaultVelocity;
        sf::RectangleShape shape;
        Category type;
};

void DrawEntity(sf::RenderWindow& window, Entity& entity)
{
    entity.shape.setPosition(entity.position - entity.shape.getSize() / 2.f);
    window.draw(entity.shape);
}

sf::FloatRect GetBoundingRect(const Entity& entity)
{
    return sf::FloatRect(entity.position+entity.velocity - entitySize / 2.f, entitySize);
}

void HandleCollision(std::vector<Entity>& entities)
{
    bool allCollisionsChecked = false;

    while(!allCollisionsChecked)
    {
        allCollisionsChecked = true;

        // Pair all possible combinations, but only once per pair
        for (auto first = entities.begin(); first != entities.end(); ++first)
        {
            for (auto second = std::next(first); second != entities.end(); ++second)
            {
                if (first->type == Category::passable || second->type == Category::passable || first->type == Category::wall && second->type == Category::wall)
                    continue;

                sf::FloatRect intersection;
                if (GetBoundingRect(*first).intersects(GetBoundingRect(*second), intersection))
                {
                    if (second->position == first->position)
                        second->position.x += entitySize.x;

                    sf::Vector2f direction = second->position - first->position;
                    sf::Vector2f offset;

                    // X collision
                    if (abs(direction.x) > abs(direction.y))
                        offset.x = ((direction.x<0)?-1:1)*intersection.width;

                    // Y collision
                    if (abs(direction.x) < abs(direction.y))
                        offset.y = ((direction.y<0)?-1:1)*intersection.height;

                    if(first->type == Category::pushable && second->type == Category::pushable)
                    {
                        first->velocity -= offset / 2.f;
                        second->velocity += offset / 2.f;
                        allCollisionsChecked = false;
                    }
                    else if(first->type == Category::pushable)
                    {
                        first->velocity -= offset;
                        allCollisionsChecked = false;
                    }
                    else if(second->type == Category::pushable)
                    {
                        second->velocity += offset;
                        allCollisionsChecked = false;
                    }
                }
            }
        }
    }
}

void handlePlayerInput(sf::Keyboard::Key key, bool isPressed)
{
    switch(key)
    {
    case sf::Keyboard::Up:
        isMovingUp = isPressed;
        break;
    case sf::Keyboard::Down:
        isMovingDown = isPressed;
        break;
    case sf::Keyboard::Left:
        isMovingLeft = isPressed;
        break;
    case sf::Keyboard::Right:
        isMovingRight = isPressed;
        break;
    }
}

int main()
{
    sf::RenderWindow window(sf::VideoMode(1280, 720), "SFML Application");
    window.setVerticalSyncEnabled(true);

    std::vector<Entity> entities;

    Entity player(sf::Vector2f(1280/2, 720/2), sf::Color::Green, Category::pushable);
    entities.push_back(player);

    size_t cols = 1280/int(entitySize.x);
    size_t rows = 720/int(entitySize.y);

    for (size_t i=0; i < cols*rows; ++i)
        if (i%cols == rows/5 && i/cols > rows/6 && i/cols < rows*5/6 || i%cols >= rows/5 && i%cols <= rows*4/5 && (i/cols == rows/6 || i/cols == rows*5/6))
            entities.push_back(Entity(sf::Vector2f(entitySize.x*(i%cols)+entitySize.x/2, entitySize.y*(i/cols)+entitySize.y/2), sf::Color::Yellow, Category::wall));
        //else
            //entities.push_back(Entity(sf::Vector2f(entitySize.x*(i%cols)+entitySize.x/2, entitySize.y*(i/cols)+entitySize.y/2), sf::Color::Transparent, Category::passable));

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::MouseButtonPressed)
            {
                sf::Vector2i pixel(event.mouseButton.x, event.mouseButton.y);
                sf::Vector2f coord = window.mapPixelToCoords(pixel);

                if (event.mouseButton.button == sf::Mouse::Left)
                {
                    Entity pushable(coord, sf::Color::Blue, Category::pushable);
                    entities.push_back(pushable);
                }
                else if (event.mouseButton.button == sf::Mouse::Right)
                {
                    Entity wall(coord, sf::Color::Yellow, Category::wall);
                    entities.push_back(wall);
                }
                else if (event.mouseButton.button == sf::Mouse::Middle)
                {
                    Entity mover(coord, sf::Color::Magenta, Category::pushable);
                    mover.defaultVelocity.x = -1.f;
                    entities.push_back(mover);
                }
            }

            switch (event.type)
            {
                case sf::Event::KeyPressed:
                    handlePlayerInput(event.key.code, true);
                    break;

                case sf::Event::KeyReleased:
                    handlePlayerInput(event.key.code, false);
                    break;

                case sf::Event::Closed:
                    window.close();
                    break;
            }
        }

        if (isMovingUp)
            entities[0].velocity.y -= 5.f;
        if (isMovingDown)
            entities[0].velocity.y += 5.f;
        if (isMovingLeft)
            entities[0].velocity.x -= 5.f;
        if (isMovingRight)
            entities[0].velocity.x += 5.f;

        if (entities[0].velocity.x != 0.f && entities[0].velocity.y != 0.f)
        {
            entities[0].velocity.x /= std::sqrt(2.f);
            entities[0].velocity.y /= std::sqrt(2.f);
        }

        HandleCollision(entities);

        // Apply and reset velocities
        for (Entity& e : entities)
        {
            e.position += e.velocity;
            e.velocity = e.defaultVelocity;
        }

        // Draw
        window.clear();
        for (Entity& e : entities)
            DrawEntity(window, e);
        window.display();
    }
}

Sample results

Magenta entities are moving to the left with constant speed and yellow entities are wall.

without checking collisions due the other collisions

Desired outcome:

Same scenario when checking collisions until all are resolved

How could I achieve this?

Answer 1

Usually collision that happen due to the result of resolution will be resolved on the next simulation loop. Most games (basically all of them afaik) do this.

The only time I would think about solving collisions that are caused by resolution, within the same frame, is if interpenetration is something that is fundamentally banned by the physics simulation. This is the case when using continuous collision detection (which nobody should be doing, except in special cases like raycasting).

In short, don't worry about it. If you have physics problems it is not because you aren't solving collisions caused by resolution.