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

Assuming I'm correctly understanding that you have (or intend to have) a grid, a large number of the collisions become far more trivial. This would entail having one collision check versus the map, and another collisions check between entities. The reason to do this is that the static nature of a grid makes for some easy collision checks.

Pretending that you have a grid called map, a few functions can be implemented like:

bool map.isPassableAt(x, y)

The underlying implementation of such a function depends on the game a bit, but will be something along these lines:

if (!boundsCheck(x, y))
   return false

return map.getTileAt(x, y).passable 
// or some function that uses the tile data to say if it can be 
// passed through or not

How does the collision against these tiled map elements work? Well I think your approach of checking the x and y components of movement separately is a good approach for allowing the slide effect that you desire. More specifically, an entity can be moved by its x and y component at the same time, and if no collision occurs, great. Otherwise... rewind that entity and move it just by x, if that collides rewind that and move it just by y, if that collides rewind that, and the end result is either partial (slide) or no movement.

The actual collision can be discerned from rectangles (or bounding boxes, as libraries like to call them), or you can see if any of the four corners of the entity are in an impassable area of map.

As far as collisions amongst entities goes, I think this is the realm where the quadtree becomes an option. I've been working on an HTML5 (javascript) and canvas games, so my performance concerns may differ from yours. In my experienced I was surprised at how far plain old brute force took me... truly into the millions of collisions per frame before the calculation was consuming anywhere near 16 ms (my threshold for "too laggy").

When I did make it to using a quadtree, I favored an approach that seems far from perfect, but I'll share it anyways.

1. player inputs are processed, and player is moved (inputs come from the previous frame)
2. all npcs are moved
3. a quadtree is created with the position of all of the above entities (yes, a new quadtree every frame)
4. collisions are checked (is a hostile npc colliding with a player? do damage! is a player colliding with an aggro circle of a hostile npc? set npc to aggro! etc)

That's how I've been doing it, with fairly good results. These entities do not experience "hard" collisions with one another however.