c++ implementing collision detection and handling for tiled 2D world with smooth wall sliding

Question

Im using SFML 2.1 for graphics and my game structure follows SFML book quite closely (SceneGraph implementation etc) My world consists mostly of characters (around 1-400, moving around) and tiles (3600, stationary) and I'll check for collisions everytime something moves

In worst case scenario with ~400 characters moving around and ~3600 tiles, I have 4000 possible entities with collision and 800 collision check calls (separate X and Y movement) each frame -> 3.2M collision checks in total.

Almost all my entities have size of 16x16 pixels and I've been looking into implementing either quadtree or simpler grid for collision detection, which should bring number of collision checks down quite a bit. By grid I mean http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

But I have no idea how I should implement simple grid for example. All help is welcome. There's propably even a lot better ways to bruteforce this.

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

I've had the following problem before when I tried to handle both X and Y movement at the same time:

I had no idea if I should reset X or Y position after collision.

Collision handling. I'll handle collisions only when entities are moving (currently only character entities, later projectiles and some special tiles)

1. if entity is tile -> do nothing

2. if entity is character -> check collisions with characters and tiles and reset movement if collision happened

.

void Entity::handleCollision()
{
    if (getCategory() & Category::Tile)
        return;
    if (getCategory() & Category::Character)
    {
        std::set<SceneNode::Pair> collisionPairs;
        checkCollision(*mSceneGraph, collisionPairs);

        for (SceneNode::Pair pair : collisionPairs)
        {
            if (matchesCategories(pair, Category::Character, Category::NonPassableCharacterOrTile))
            {
                resetPreviousPosition();
                break;
            }
        }
    }
}

I'll check collision simply by using SFML's intersects-function. This is propably good enough for this?

bool collision(const SceneNode& l, const SceneNode& r)
{
    return l.getBoundingRect().intersects(r.getBoundingRect());
}

If I were to implement grid or quadtree for collision detection, when should I populate it, when update? Should I update it every time I move one entity, or should I try to come up with a way to move all entities at once, then build grid/quadtree and only after that try to handle all collisions.

So my questions are: (1) In this scenario how and when should I do collision handling? My current implementation works, but I think I do it too often and all examples I looked into grids/quadtrees assumed that I do first all movement and do collision detection and handling after.

and (2) When do I clear/populate/update my grid/quadtree. For example if I have 3600 tiles and 3 moving characters. Should I seek for entity each time one moves in the grid and try to move it to different grid cell / tree branch?

Edit:

What I'll propably try next unless anyone gives better advice

Updated update step. Is this smart or in anyway reasonable way to do this?

1. Remove entity from grid/quadtree

2. Move entity horizontally

3. Add entity to grid/quadtree

4. Check and handle collisions

5. Remove entity from grid/quadtree

6. Move entity vertically

7. Add entity to grid/quadtree

8. Check and handle collisions

9. Repeat 1-8 for all entities

.

Entity::move()
{
    grid.getCell(getPosition()).remove(this);
    ... move x
    grid.getCell(getPosition()).add(this);
    ... if collision, reset x

    grid.getCell(getPosition()).remove(this);
    ... move y
    grid.getCell(getPosition()).add(this);
    ... if collision, reset y
}

Entity::checkCollision()
{
    list<Entity*> possibleColliders;

    possibleColliders = grid.getEntitiesInRectangle(x - s, y - s, x + s, y + s);

   ... now only check collision against possibleColliders
}

Answer 1

I think a quadtree would work quite well and since it will be standalone there's really no issue in adding it into your current system.

The important question you've ask is probably, when to populate and update the quadtree. I think this largely depends on your use case. Since you have around 400 characters that can change position for each frame, it probably wouldn't make a lot of difference if you try to move the nodes in the quadtree or if you fully rebuild the quadtree. Which is really more performant depends on your algorithm and datastructure, which would need some performance testing.

In this tutorial, they also suggest to rebuild the quadtree every frame iteration.

For the "how to fix collision handling" you'll need to provide more information/a separate SO question, since it's not that clear what the issue is.