Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Implementing collision grid or quadtree into sfml book game structure  (Read 28699 times)

0 Members and 1 Guest are viewing this topic.

santiaboy

  • Full Member
  • ***
  • Posts: 118
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #15 on: December 09, 2013, 07:25:21 pm »
Well yes, but they are harder to implement as well  ;D

I am stress testing my game, and the framerate is stable. However, I don't know how an older computer will run it. That's why I tried to optimize a bit, but I didn't want to complicate myself too much.

Thanks for the info though!

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #16 on: December 09, 2013, 07:32:52 pm »
I am stress testing my game, and the framerate is stable. However, I don't know how an older computer will run it. That's why I tried to optimize a bit
If you really want to optimize, use a profiler to get a detailed overview about the bottlenecks in your application. Once you have these measurements, you can optimize the corresponding program code specifically.
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

warbaque

  • Newbie
  • *
  • Posts: 18
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #17 on: December 10, 2013, 12:17:20 am »
Edit: Ah, you mean you want to check immediately after X movement and immediately after Y movement. What you could do: Don't apply the velocity directly. Check from outside if position + velocity would lead to a collision (for both velocity components separately), and react correspondingly. If no collision occurs, apply the velocity. I'm not sure if it's more reasonable to abuse the current Entity::mVelocity attribute or to create a new one, such as Entity::mPlannedVelocity. You could experiment a bit here.
"Check from outside if position + velocity would lead to a collision"
What do you mean from outside? And how would you check that collision? Add new object to the collisiongrid and check if it collides with anyhing and if it doesn't move entity?

santiaboy

  • Full Member
  • ***
  • Posts: 118
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #18 on: December 10, 2013, 01:24:23 am »
I am stress testing my game, and the framerate is stable. However, I don't know how an older computer will run it. That's why I tried to optimize a bit
If you really want to optimize, use a profiler to get a detailed overview about the bottlenecks in your application. Once you have these measurements, you can optimize the corresponding program code specifically.

Do you recommend any profiler? I am currently using gprof because it came with ubuntu.

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #19 on: December 10, 2013, 07:20:22 am »
What do you mean from outside?
From outside the entity, i.e. in World or a specific collision class.

And how would you check that collision?
The same way that you check collision now (for example, bounding rect).

Do you recommend any profiler? I am currently using gprof because it came with ubuntu.
I'm on Windows, currently I use the one integrated with Visual Studio. Earlier I used AMD CodeAnalyst. No idea for Linux...
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

FRex

  • Hero Member
  • *****
  • Posts: 1845
  • Back to C++ gamedev with SFML in May 2023
    • View Profile
    • Email
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #20 on: December 10, 2013, 10:43:52 am »
Do you recommend any profiler? I am currently using gprof because it came with ubuntu.
There's a tool called perf.
Back to C++ gamedev with SFML in May 2023

Mario

  • SFML Team
  • Hero Member
  • *****
  • Posts: 879
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #21 on: December 10, 2013, 11:07:13 am »
"Check from outside if position + velocity would lead to a collision"
What do you mean from outside? And how would you check that collision? Add new object to the collisiongrid and check if it collides with anyhing and if it doesn't move entity?

The basic idea is to check *pos1 + vel1* against *pos2 + vel2*  for collisions rather than applying the velocity and then checking. This also has the advantage that you're able to split fast/big movements into several smaller movements to avoid things such as ghosting.

warbaque

  • Newbie
  • *
  • Posts: 18
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #22 on: December 11, 2013, 06:23:43 pm »
What do you mean from outside?
From outside the entity, i.e. in World or a specific collision class.
So we would handle collision and movement separately?

World update
void World::update(sf::Time dt)
{
        // Reset player velocity
        for (Character* c : mPlayers)
                c->setVelocity(0.f, 0.f);

        guideEnemies();

        // Forward commands to scene graph
        while (!mCommandQueue.isEmpty())
                mSceneGraph.onCommand(mCommandQueue.pop(), dt);

        adaptPlayerVelocity();

        spawnEnemies();

        // Regular update step
        mSceneGraph.update(dt, mCommandQueue);

        handleCollisions();
}

But how can my entity know if it can move to some location if it has no access to collision grid and locations of other entities?
void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
        checkIfEntityCanMoveUsingmVelocityAndAdjustAccordingly();
        move(mVelocity * dt.asSeconds());
        // shouldn't I also update collision grid after entity moves?
}

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #23 on: December 11, 2013, 07:15:29 pm »
So we would handle collision and movement separately?
Yes... That's what I'm saying all the time.

The movement depends on the velocity, and the velocity can be affected by collision response. Thus, the collision response indirectly influences the movement.

But how can my entity know if it can move to some location if it has no access to collision grid and locations of other entities?
It can't. And that's exactly the reason why I suggest to handle collision outside the entity.

Another reason why it's a bad idea to handle collision during Entity::current() is the asymmetry created by the order of iteration: Entities that are moved before others (but in the same frame) get priority for collision. When an entity checks other entities for collision, a part of them has already moved, while another one hasn't.

The third reason is modularity and separation of responsibilities. It's favorable if Entity needn't be aware of the whole world. As suggested, I would even create a separate class for collision detection and response, because World is already quite big.
« Last Edit: December 11, 2013, 07:17:16 pm by Nexus »
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

warbaque

  • Newbie
  • *
  • Posts: 18
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #24 on: December 11, 2013, 10:42:25 pm »
So we would handle collision and movement separately?
Yes... That's what I'm saying all the time.

The movement depends on the velocity, and the velocity can be affected by collision response. Thus, the collision response indirectly influences the movement.
Something like this?

** Start **
Entities (all entities are non passable):
1, 2, 3,
4, 5, 6,
7, 8, 9


** Move everything **
Blue entities move towards green entity and green entity moves to the down right



** Check collisions **
List of collisions (let's handle collisions in this order:
1: E2 collision with E3 (X collision)
2: E4 collision with E7 (Y collision)
3: E5 collision with E6 (X collision)
4: E5 collision with E8 (Y collision)
5: E6 collision with E8 (X and Y collision)

** Handle collisions **
1: reset E2 and E3 X movement to prevent collision

   -> E2 collides now with E1 (X collision)

2: reset E4 and E7 Y movement to prevent collision

   -> E4 collides now with E1 (Y collision)

3: reset E5 and E6 X movement to prevent collision

   -> E5 collides now with E4 (X collision)
   -> E5 collides now with E7 (Y collision)
   -> E5 collides now with E8 (X and Y collision)

4: reset E5 and E8 Y movement to prevent collision

   -> E5 collides now with E1 (X and Y collision)
   -> E5 collides now with E2 (Y collision)
   -> E5 collides now with E4 (X collision)

5: reset E6 and E8 X or Y collision to prevent collision (I've yet to figure out which one) (let's select X collision this time)

   -> E8 collides with E7 (X collision)


** Check collisions **
1: E1 collision with E2 (X)
2: E1 collision with E4 (Y)
3: E1 collision with E5 (X and Y)
4: E2 collision with E4 (X and Y)
5: E2 collision with E5 (Y)
6: E4 collision with E5 (X)
7: E7 collision with E8 (X)

** Handle collisions **
1: reset E1 X movement (E2 movement already resetted)
2: reset E1 Y movement (E4 movement already resetted)
3: Do nothing (E1 and E5 movement already resetted)
4: reset E2 Y movement
5: Do nothing
6: reset E4 X movement
7: reset E7 X movement



** Check collisions **
No more collision
   -> Continue



Problems I have with above aproach:
1. hard to detect should I reset X or Y movement

Scenario 1
Entities:
B1
B2, G
Blue entities move towards green entity, while green entity moves top left

**Collisions**
1: B1 collides with B2 (Y)
2: B1 collides with G (X and Y)
3: B2 collides with G (X)

-> Reset blue movement
-> Reset green X movement (nothing blocks Y)

Scenario 2
Entities:
B1, B2
    G
Blue entities move towards green entity, while green entity moves top left

**Collisions**
1: B1 collides with B2 (X)
2: B1 collides with G (X and Y)
3: B2 collides with G (Y)

-> Reset blue movement
-> Reset green Y movement (nothing blocks X)

Collisions don't know about each others and in these scenarios 2. collision is fixed by handling 3. collision.
How should I handle XY-collision?

Quote
Another reason why it's a bad idea to handle collision during Entity::current() is the asymmetry created by the order of iteration: Entities that are moved before others (but in the same frame) get priority for collision. When an entity checks other entities for collision, a part of them has already moved, while another one hasn't.
But there's still assymmetry depending on which order collisions are handled. (It doesn't really matter in this case though)

Quote
The third reason is modularity and separation of responsibilities. It's favorable if Entity needn't be aware of the whole world. As suggested, I would even create a separate class for collision detection and response, because World is already quite big.
This is main reason why I would like to move collision handling away from entity update step. It just makes movement a bit trickier.
« Last Edit: December 11, 2013, 10:44:21 pm by warbaque »

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #25 on: December 12, 2013, 12:23:29 am »
Thanks for the detailed description.

I still think the separate X/Y movement for collision response is quite complicated to implement. It might be worthwhile to try a different approach, I mentioned the vector that leads away from the colliding entity. The idea is that all colliding entities contribute to the total "evade" vector. This approach is very simple, it took me only about ten minutes to write a short program that illustrates the principle.

You can click on the screen to insert a new entity. Collisions will be resolved over multiple frames, and symmetrically. The collision response is not perfect; you'll see some shivers when many entities overlap in a large area, and entities with identical positions are left unchanged. But overall, collision is resolved in a not so unintuitive way. I'm sure you can tweak this more and smooth it according to your needs ;)
#include <SFML/Graphics.hpp>

const sf::Vector2f entitySize(40.f, 40.f);
const float speed = 0.1f;

struct Entity
{
        sf::Vector2f position;
        sf::Vector2f velocity;
};

void DrawEntity(sf::RenderWindow& window, const Entity& entity)
{
        sf::RectangleShape shape;
        shape.setSize(entitySize);
        shape.setPosition(entity.position - shape.getSize() / 2.f);
        shape.setOutlineColor(sf::Color::Blue);
        shape.setOutlineThickness(1.f);
        shape.setFillColor(sf::Color::Transparent);
       
        window.draw(shape);
}

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

void HandleCollision(std::vector<Entity>& entities)
{
        // 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 (GetBoundingRect(*first).intersects(GetBoundingRect(*second)))
                        {
                                // Compute vector that leads away from other entity
                                // and accumulate with current velocity
                                sf::Vector2f offset = speed * (first->position - second->position);
                                first->velocity += offset;
                                second->velocity -= offset;
                        }
                }
        }
}

int main()
{
        std::vector<Entity> entities;

        sf::RenderWindow window(sf::VideoMode(640, 480), "SFML Application");
        window.setFramerateLimit(20);

        while (window.isOpen())
        {
                sf::Event event;
                while (window.pollEvent(event))
                {
                        if (event.type == sf::Event::KeyPressed || event.type == sf::Event::Closed)
                                return 0;
                        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)
                                        entities.push_back( {coord, sf::Vector2f()} );
                        }
                }

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

                HandleCollision(entities);

                // Draw
                window.clear();
                for (const Entity& e : entities)
                        DrawEntity(window, e);
                window.display();
        }
}
« Last Edit: December 12, 2013, 12:37:49 am by Nexus »
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

warbaque

  • Newbie
  • *
  • Posts: 18
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #26 on: December 12, 2013, 01:18:58 am »
I still think the separate X/Y movement for collision response is quite complicated to implement. It might be worthwhile to try a different approach, I mentioned the vector that leads away from the colliding entity. The idea is that all colliding entities contribute to the total "evade" vector. This approach is very simple, it took me only about ten minutes to write a short program that illustrates the principle.
Thank you for your 10 minutes :)
I'll look into it.

warbaque

  • Newbie
  • *
  • Posts: 18
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #27 on: December 15, 2013, 06:08:28 am »
You can click on the screen to insert a new entity. Collisions will be resolved over multiple frames, and symmetrically. The collision response is not perfect; you'll see some shivers when many entities overlap in a large area, and entities with identical positions are left unchanged. But overall, collision is resolved in a not so unintuitive way. I'm sure you can tweak this more and smooth it according to your needs ;)
I had little time today in my hands so I tried your approach. Overall it works quite nicely with few entities.

Entity, velocity and boundingRect:


Collision response:

If colliding with wall, push pushable entity away.
Or if colliding with other pushable entity, push both.
Skip wall<->wall collision checks and checks with passable terrain.

While single collisions and collisions with just few entities work quite nicely, problems arise when adding multiple pushable and especially moving entities to the world.

Multiple moving entities can push other entities through walls and pushable entities can be squeezed together.

What causes the problem (numbers below are velocity modifications due the collision handling):

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 it should be:

Or if the leftmost entity was a wall -> 0, 0, -v
But I don't really know (or atleast good ideas) how to achieve this.

Sample code below:
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(color);
                }

                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)
{
        sf::Vector2f topLeftCorner;
        sf::Vector2f size(entitySize.x + abs(entity.velocity.x), entitySize.y + abs(entity.velocity.y));

        if (entity.velocity.x < 0)
                topLeftCorner.x = entity.velocity.x;

        if (entity.velocity.y < 0)
                topLeftCorner.y = entity.velocity.y;

        return sf::FloatRect(entity.position+topLeftCorner - entitySize / 2.f, size);
}

void HandleCollision(std::vector<Entity>& entities)
{
        // 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))
                        {
                                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;
                                }
                                else if(first->type == Category::pushable)
                                {
                                        first->velocity -= offset;
                                }
                                else if(second->type == Category::pushable)
                                {
                                        second->velocity += offset;
                                }
                        }
                }
        }
}

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);

        size_t i = 0;
        for (; 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();
        }
}
« Last Edit: December 15, 2013, 06:48:22 am by warbaque »

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #28 on: December 15, 2013, 11:45:43 am »
But I don't really know (or atleast good ideas) how to achieve this.
Some spontaneous ideas to account for multiple objects being involved:
  • Invoke the collision response multiple times per frame until results are correct. This avoids intermediate "wrong" states, but it also leads to jumps or hard collision reactions, which may not be what you want.
  • Determine the group of colliding entities, instead of just the pair, and exploit the knowledge about multiple neighbors for more sophisticated collision response.
  • Steering behaviors: even if they are usually used to avoid collisions rather than to react to them, some concepts like applying the sum of multiple vectors or force/potential fields can prove useful.
  • Use the physical concept of momentum. For complex simulations, a physics library such as Box2D could also be an option.
I've quickly tested your code, it seems to work well... Does it do what you expect?
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

warbaque

  • Newbie
  • *
  • Posts: 18
    • View Profile
Re: Implementing collision grid or quadtree into sfml book game structure
« Reply #29 on: December 15, 2013, 02:36:05 pm »
I've quickly tested your code, it seems to work well... Does it do what you expect?
Yes, it does and that's the sort of collision I want between pushable entities and walls (and it works with pairs quite well):
wall <-> pushable: pushable can't move inside wall
pushable <-> pushable: both are repelled from each others so they won't collide


So I used your first idea since I've been thinking that too and it seems to do just what I want (very heavy and unoptimized though)

So next steps are to make collision handling run faster and implement some sort of collision grid to bring number of collision checks down.

#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);

        size_t i = 0;
        for (; 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();
        }
}

It takes quite a many collision checks to fix even simple collision this way

Start, 3 entities:

Velocities in the beginning:
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
« Last Edit: December 15, 2013, 04:08:21 pm by warbaque »