-
My game structure follows SFML book quiet closely (scenegraph, commands, etc) and I'm currently trying to implement better collision detection.
Where should I store my grid / quadtree and how my entities should access and use it?
My gameworld (everything is visible) consists currently of 3600 tile entities (stationary, might have collision box) and 1-400 character entities (roam around map, colliding into things)
**Current entity update step.**
I do X/Y-axis movement separately. Because I want to slide against entities when colliding diagonally.
1. Move entity horizontally
2. Check and handle collisions
3. Move entity vertically
4. Check and handle collisions
5. Repeat 1-4 for all entities
void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
setPreviousPosition(getPosition());
move(sf::Vector2f(mVelocity.x, 0) * dt.asSeconds());
handleCollision();
setPreviousPosition(getPosition());
move(sf::Vector2f(0, mVelocity.y) * dt.asSeconds());
handleCollision();
}
void Entity::handleCollision()
{
if (getCategory() & Category::Character)
{
std::set<SceneNode::Pair> collisionPairs;
checkCollision(*mSceneGraph, collisionPairs);
for (SceneNode::Pair pair : collisionPairs)
{
if (matchesCategories(pair, Category::Enemy, Category::Player))
{
auto& player = static_cast<Entity&>(*pair.second);
resetPreviousPosition();
player.damage(1);
break;
}
else if (matchesCategories(pair, Category::Character, Category::NonPassable))
{
resetPreviousPosition();
break;
}
}
}
}
**How I plan to do entity update step.**
1. Remove entity from grid (old location)
2. Move entity horizontally
3. Add entity to grid (new location)
4. Check and handle collisions
5. Remove entity from grid (old location)
6. Move entity vertically
7. Add entity to grid (new location)
8. Check and handle collisions
9. Repeat 1-8 for all entities
So my questions are as follow:
(1) Is the above implementation reasonable or smart way to do this?
(2) Where should I store and how to access my grid implemtation?
-
The quadtree should be stored in the class that contains and manages your entities, that is, World. The access doesn't fundamentally change from what you already have, you might just use more specific functions because you're operating a different data structure.
I'm not sure if Entity is a good place to handle collisions. In my opinion, an external class should be responsible of that -- either World like in the current book implementation, or even a class dedicated to collision. The Entity may still hold collision-related data, but it doesn't process it. This collision-dedicated class would then also handle the entering/leaving of grids (or cells or nodes) in your quadtree.
-
The quadtree should be stored in the class that contains and manages your entities, that is, World. The access doesn't fundamentally change from what you already have, you might just use more specific functions because you're operating a different data structure.
So should I pass pointer to the quadtree from world to scenegraph so all entities have an access to it?
I'm not sure if Entity is a good place to handle collisions. In my opinion, an external class should be responsible of that -- either World like in the current book implementation, or even a class dedicated to collision. The Entity may still hold collision-related data, but it doesn't process it. This collision-dedicated class would then also handle the entering/leaving of grids (or cells or nodes) in your quadtree.
I had problems with handling collisions in world previously using example from book:
**World update step in book**
1. Move everything (X and Y)
2. Check and handle collisions
Problems
1: chain reaction after collision reset:
(http://i.imgur.com/GDKwIKf.png)
- Green entity moves to the right and Blue entities to the left
- After movement green and leftmost blue collide with each others -> reset their position
- After reset, now both blue ones are colliding -> I need another collision handling step
2: difficult to determine if collision happened in X or Y axis:
(http://i.imgur.com/oUoDcWk.png)
- Green entity is moving to top left direction and collides with 2 entities
- Collision with leftmost entity occurs from x and y directiosn while rightmost happens only from y
- If I were to check x and y movement separately, there would be no x collision at all, but I can't do this when handling collision from world-class. Or can I?
-
So should I pass pointer to the quadtree from world to scenegraph so all entities have an access to it?
There are different options how to relate entities, collision and the scene graph. I would probably move the whole collision logic out of the scene nodes and entities, because you are then more flexible (a quadtree is organized differently than a scene graph, anyway). Collision response (the reactions when a collision occurs) can be handled from outside using the Entity public API such as setPosition().
1: chain reaction after collision reset
You can try to address that problem by "asking" an entity whether it can move to the right. You then recursively perform collision detection and report the results back to the querying entity. If the result is "no", then the querying entity must move itself.
Depending on your logic, you might alternatively want to move always the other entities, so multiple collision steps per frame would indeed be an option.
2: difficult to determine if collision happened in X or Y axis:
Again, it depends on how you want the physics to react when such a collision occurs. If it's enough to move other entities simply away from your own entity, you can move them along the difference vector until they are located outside.
This link about the SAT might also be interesting, it's also mentioned in the book:
http://www.metanetsoftware.com/technique/tutorialA.html
-
So should I pass pointer to the quadtree from world to scenegraph so all entities have an access to it?
There are different options how to relate entities, collision and the scene graph. I would probably move the whole collision logic out of the scene nodes and entities, because you are then more flexible (a quadtree is organized differently than a scene graph, anyway). Collision response (the reactions when a collision occurs) can be handled from outside using the Entity public API such as setPosition().
How would you do this? How would entity and world update step look like?
Again, it depends on how you want the physics to react when such a collision occurs. If it's enough to move other entities simply away from your own entity, you can move them along the difference vector until they are located outside.
This link about the SAT might also be interesting, it's also mentioned in the book:
http://www.metanetsoftware.com/technique/tutorialA.html
I don't need any complex physics. Entity can either move through other entities or it can't.
I have different types of entities, all the collision boxes are 16x16 or multiples of that
1: Walking and flying characters
2: Floor and wall tiles
3: Items etc...
Flying characters can fly over all other characters and tiles.
Walking characters can walk over floor tiles, but not through other walking characters nor wall tiles.
Tiles won't move around and can't be pushed around, but can be destroyed.
Other type of collisions are handling item pickups, projectiles and explosions.
-
How would you do this? How would entity and world update step look like?
In the World update, you perform a search in the quadtree for possible collisions. You should read more about this data structure if you plan to use it.
But Quadtrees are already quite advanced because of their hierarchical organization, for your purposes it might be enough to have a flat grid of equally-sized cells. For each cell, you would then perform collision detection for entities inside the cell and its neighbors.
-
But Quadtrees are already quite advanced because of their hierarchical organization, for your purposes it might be enough to have a flat grid of equally-sized cells. For each cell, you would then perform collision detection for entities inside the cell and its neighbors.
I'm currently working on simple grid, since that's most likely enough for me.
In the World update, you perform a search in the quadtree for possible collisions.
You mean:
1) Move everything
2) Check collisions
?
That seems like a lot more work than checking collisions after each entity move. Since having lots of separate X and Y collisions and chainreaction collisions happening at the same time seem rather confusing.
-
You mean:
1) Move everything
2) Check collisions
?
That seems like a lot more work than checking collisions after each entity move.
More work than what?
You have to check each collidable entity for collision after it has moved -- the trick is to reduce the collision checks to a minimum, for example by keeping them local using a grid.
-
You mean:
1) Move everything
2) Check collisions
?
That seems like a lot more work than checking collisions after each entity move.
More work than what?
More work than checking collisions after each movement in entity-class.
This is what I have currently. I check and handle possible collisions after something have moved.
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();
// Regular update step
mSceneGraph.update(dt, mCommandQueue);
}
void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
setPreviousPosition(getPosition()); // for resetting after possible collision
move(sf::Vector2f(mVelocity.x, 0) * dt.asSeconds());
handleCollision();
setPreviousPosition(getPosition()); // for resetting after possible collision
move(sf::Vector2f(0, mVelocity.y) * dt.asSeconds());
handleCollision();
}
How I uderstood your suggestion. Check and handle collisions after everything has moved.
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();
// Regular update step
mSceneGraph.update(dt, mCommandQueue);
handleCollisions();
}
void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
setPreviousPosition(getPosition());
move(sf::Vector2f(mVelocity.x, mVelocity.y) * dt.asSeconds());
}
You have to check each collidable entity for collision after it has moved -- the trick is to reduce the collision checks to a minimum, for example by keeping them local using a grid.
How I could check collisions from world-class after each entity movement, if that collision check isn't part of entity update step?
-
It is just a design choice whether you handle collisions centralized in World or in each Entity -- the algorithmic effort remains the same. I suggested World because this class has a view "from outside" and because I wanted to move the responsibility for collision detection and response out of each Entity. If the functionality becomes more complex, it may also be worthwhile to create a new class dedicated to collision. Especially since World is already big and has many responsibilities. Where would you store your grid data structure, if not in World (or the new Collision class)? Entity is certainly not the right place for it.
Let's talk about the grid cells. Each cell contains a list of entities that are currently inside, and an API to insert/remove/clear/access them. std::set makes it very simple to maintain them, but you can also use a sequential container like std::vector.
class Cell
{
private:
typedef std::set<Entity*> Container;
public:
void addEntity(Entity& entity);
void removeEntity(Entity& entities);
void clear();
Container::iterator begin();
Container::iterator end();
private:
Container mEntities;
};
Since cells are aligned regularly, it's standing to reason to use a random access container for fast access to a certain cell. You can also provide a function getCellAt() that returns the cell for a specific (x,y) index pair. Internally it maps 2D indices to 1D indices.
std::vector<Cell> mCells;
Cell& getCellAt(sf::Vector2u index2D);
Given a fixed cellSize, you could then find the corresponding cell for each entity in constant time. You just divide its position by the cell size and floor the result (by casting to unsigned int). If negative coordinates are possible, offset them before. The entities being assigned to cells can be fetched using the command architecture.
const sf::Vector2f cellSize = ...;
sf::Vector2f pos = entity.getPosition();
sf::Vector2u cellIndex(
static_cast<unsigned int>(pos.x / cellSize.x),
static_cast<unsigned int>(pos.y / cellSize.y));
Now that you know which cell to take, you can store a pointer to the entity in this cell.
Cell& cell = getCellAt(cellIndex);
cell.addEntity(entity);
In the update step, you then perform a collision between all possible pairs inside a cell, and between pairs of one entity being inside and the other being in a neighbor cell. This is very similar to what we've already done in the book, but there are far less entities to check (because of grid locality) and the iteration can be done iteratively instead of recursively.
This is now a quite detailed description of how you could possibly implement collision detection based on grid cells. Please try it out and experiment a bit on your own before asking for every tiny detail ;)
-
It is just a design choice whether you handle collisions centralized in World or in each Entity -- the algorithmic effort remains the same. I suggested World because this class has a view "from outside" and because I wanted to move the responsibility for collision detection and response out of each Entity.
This is what I would also like to do, but I have no idea how to handle collisions that happened due the chain reaction and if collisions happened from X or Y direction or in what order they happened.
I find algorithimc effort lot simpler in
1) move X
2) check collision, if collision resetX
3) move Y
4) check collision, if collision resetY
5) repeat 1-4 for all entities
compared to
1) move all
2) check all collision
3) if collision check X or Y -> reset X or Y -> check collision again (is this world collision or entity collision?)
4) after possible reset check collisions again -> reset other entities
5) repeat 3-4
Is there some other way to move collision handling away from the entities update step while still checking collisions after every X and Y movement?
If the functionality becomes more complex, it may also be worthwhile to create a new class dedicated to collision. Especially since World is already big and has many responsibilities. Where would you store your grid data structure, if not in World (or the new Collision class)? Entity is certainly not the right place for it.
Currently I store collisiongrid in world and pass its reference to the entities.
Implementin grid or quadtree itself is rather trivial, I'm just having problems figuring out how (and when) to use it.
-
This is what I would also like to do, but I have no idea how to handle collisions that happened due the chain reaction and if collisions happened from X or Y direction or in what order they happened.
I made a few suggestions in my 2nd post, but you're not limited to them.
I find algorithimc effort lot simpler in
1) move X
2) check collision, if collision resetX
3) move Y
4) check collision, if collision resetY
5) repeat 1-4 for all entities
Only because you hide important steps in your list. Instead of "check collision" it is "check collision against all possible entities". If Entity doesn't exploit the grid optimization, there will be many more collision checks than necessary.
Is there some other way to move collision handling away from the entities update step while still checking collisions after every X and Y movement?
The current implementation doesn't use the entity update step to handle collision, either, so yes. If you store pointers to the entities in a Cell class (whose objects are itself stored in World, maybe indirectly in Collision), then you can directly iterate over the entities as I explained in my last post.
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.
-
In my project I used a grid with cells, and, I just get the cell who's on the x,y position and I check the collision with the cell.
But if you want to do something more accurate, you can check the collision on all entities who are in the cell, and you can even do a bounding box hierarchy over the objects.
-
I am doing a similar thing. I was thinking that quadtrees might be a little overkill. I have a couple of questions:
- How do you handle how much space do you give to a cell in a collision grid?
- By the size of the map? By the amount of solid tiles in that particular cell?
- Or you give them some particular size and that's it (example, 5 tiles tall, 5 tiles wide)?
-
Quadtrees usually handle this problem for you. There's no fixed size for a start to lower complexity and avoid unneeded recursive stuff (i.e. iterating through child nodes).
- The biggest node will cover your whole potential map/world.
- Once the number of entities inside becomes bigger than a specific threshold, four child nodes are created and the entities are moved there (essentially creating the first layer in the quad tree; that's what "quad" refers to here).
- Once the number of entities in children significantly fell under the threshold (possibly for a few frames), child nodes can be destroyed or deactivated once again and the parent node manages them again.
This will solve several problems at once:
- Nodes with just a few entities won't dive into several layers without any performance gain (i.e. performance loss due to overhead).
- Nodes with too many entities won't slow down and essentially throw away the intended performance gain (e.g. too many unnecessary collision detection iterations again).
-
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!
-
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.
-
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?
-
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.
-
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...
-
Do you recommend any profiler? I am currently using gprof because it came with ubuntu.
There's a tool called perf.
-
"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.
-
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?
}
-
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.
-
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
(http://i.imgur.com/J0bAklb.png)
** Move everything **
Blue entities move towards green entity and green entity moves to the down right
(http://i.imgur.com/jCm2HUu.png)
** 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
(http://i.imgur.com/1KyqDwQ.png)
-> E2 collides now with E1 (X collision)
2: reset E4 and E7 Y movement to prevent collision
(http://i.imgur.com/PX3882m.png)
-> E4 collides now with E1 (Y collision)
3: reset E5 and E6 X movement to prevent collision
(http://i.imgur.com/HeeYhst.png)
-> 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
(http://i.imgur.com/WSpbt9X.png)
-> 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)
(http://i.imgur.com/kkc2EYZ.png)
-> 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
(http://i.imgur.com/6LPyu1X.png)
** 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
(http://i.imgur.com/uWHaPEE.png)Entities:
B1
B2, G
Blue entities move towards green entity, while green entity moves top left
(http://i.imgur.com/ih4aSkT.png)
**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
(http://i.imgur.com/7fezsWP.png)Entities:
B1, B2
G
Blue entities move towards green entity, while green entity moves top left
(http://i.imgur.com/RrBj9cP.png)
**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?
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)
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.
-
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();
}
}
-
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.
-
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:
(http://i.imgur.com/8ZPcg5j.png)
Collision response:
(http://i.imgur.com/ucDtsQ1.png)
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):
(http://i.imgur.com/JHpFLwU.png)
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:
(http://i.imgur.com/FuzL9S2.png)
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();
}
}
-
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 (https://en.wikipedia.org/wiki/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?
-
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:
(http://i.imgur.com/bPzRr7U.png)
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