Spatial Partitioning

There two spatial partitioning implementations included with xygine. These are each useful in different situations, and most commonly used in 'broad-phase' culling during collision detection routines. They can also be useful, however, during rendering situations when a large set of entities need to be reduced to only those visible, and the default render culling is not precise enough (although it usually is).

Quad Tree

The QuadTreeSystem, in conjunction with the QuadTreeItem component is great for fixed-size worlds with a lot of static geometry. For example a platform game with many static platforms works well when a quad tree is used to find the geometry near enough to the player that it might collide.

sf::FloatRect playerBounds = entity.getComponent<Player>().bounds;

std::vector<xy::Entity> nearbyEntities = scene.getSystem<xy::QuadTreeSystem>().queryArea(playerBounds);

//nearbyEntities contains all entities with a QuadTreeItem component in or around playerBounds
for(auto entity : nearbyEntities)
{
    doCollision(entity);
}

The QuadTreeSystem has a similar function queryPoint() which takes a point such as the player position, rather than a FloatRect, which returns results that can be processed in the same way.

Balanced AABB Tree

The DynamicTreeSystem and corresponding BroadPhaseComponent work well with any size world area, particularly if many of its entities are dynamic and have their position frequently updated. It is based on Erin Catto and Nathanael Presson's bounding volume hierarchy found in box2D. It's deployed very similarly to the QuadTreeSystem, except it can only be queried with an area, not a point.

sf::FloatRect playerBounds = entity.getComponent<Player>().bounds;

std::vector<xy::Entity> nearbyEntities = scene.getSystem<xy::DynamicTreeSystem>().query(playerBounds);

//nearbyEntities contains all entities with a BroadPhaseComponent in or around playerBounds
for(auto entity : nearbyEntities)
{
    doCollision(entity);
}

As such it has only a single query() function.

Filters

Both the QuadTreeItem and BroadPhaseComponent have 64bit integer values which are used as flags to optionally identify them. This is useful for creating groups that can be filtered when performing a query:

enum CollisionGroup
{
    Solid = 0x1
    Brick = 0x2
    Glass = 0x4
    Dirt  = 0x8
};

entity.addComponent<xy::BroadPhasComponent>().setFlags(CollisionGroup::Solid | CollisionGroup::Brick);

otherEntity.addComponent<xy::BroadPhaseComponent>().setFlags(Solid | Glass);

auto queryResult = scene.getSystem<xy::DynamicTreeSystem>().query(someArea, CollisionGroup::Solid);

//queryResult contains only entities with the CollisionGroup::Solid flag set
for(auto entity : queryResult)
{
    const auto& component = entity.getComponent<xy::BroadPhaseComponent>();
    if(component.getFlags() & Brick)
    {
        //play a brick sound
    }
    else if(component.getFlags() & Glass)
    {
        //play glass sound
    }
}

In the above example flags are OR'd together so that a query can filter all results for CollisionGroup::Solid and then be sub-filtered for solid types.