2
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I kinda figured that my current implementation, which while it resolves the problems I have, isn't really a good solution or solution at all. I only worry because I haven't yet figured out how to prevent entities from pushing each others through walls, other than that horrific loop. \$\endgroup\$ – warbaque Dec 16 '13 at 0:12
  • \$\begingroup\$ Are your objects tunnelling, or slowly pushing through the wall? You might ask a new question after you mess around a bit and gather some info. If you do I can try to answer it as well. \$\endgroup\$ – RandyGaul Dec 16 '13 at 0:31
  • \$\begingroup\$ The more there is entities in a line pushing the deeper into wall they sink (and eventually through) [i.imgur.com/hCwUfZX.png] Yellow entities are wall and purple entities move to the left with constant velocity. Desired effect [i.imgur.com/hHxhv9f.png] \$\endgroup\$ – warbaque Dec 16 '13 at 0:46
  • \$\begingroup\$ Yep, this is a much more complex problem to solve. You are trying to implement "stacking". In order to do this there are two main methods: contact graph and shock propagation, or a more advanced collision resolution scheme, such as Erin Catto's sequential impulses. The contact graph should be easier. Both are non-trivial. \$\endgroup\$ – RandyGaul Dec 16 '13 at 0:47
  • \$\begingroup\$ Is there any simple solution for this that I could use? I don't need accurate physics simulation for this scenario. I just need to prevent entities from moving through walls and other entities, while still allowing them to push each others. \$\endgroup\$ – warbaque Dec 16 '13 at 0:55

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.