Implementing collision grid or quadtree into sfml book game structure

[warbaque]

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?

[Nexus]

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.

[warbaque]

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:

- 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:

- 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?

[Nexus]

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

[warbaque]

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.

[Nexus]

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.

[warbaque]

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.

[Nexus]

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.

[warbaque]

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?

[Nexus]

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

[warbaque]

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.

[Nexus]

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.

[Lolilolight]

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.

[santiaboy]

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

[Mario]

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