QuadTree

QuadTree

A QuadTree is a tree data structure for storing geometric data, it works by recursively dividing a 2D region into quarters.

We can use Quadtrees for optimised spatial queries, the most common game dev example being collision detection. Quadtrees provide significant performance increases over using a regular linear search.

Usage

The QuadTree is multipurpose and can be used as a PR (Point Region) or MX-CIF (Matrix) QuadTree.

Setup

A quadtree requires the maximum boundaries of your map (x, y, width, height).

QuadTree quadTree = new QuadTree(0f, 0f, 100f, 200f);

Insert

Inserts an entity into the tree at position x, y, optionally with width and height but by default these are 0

quadTree.insert(e, position.getX(), position.getY(), size.getWidth(), size.getHeight());

Remove

Removes an entity from the tree

If the tree contains multiple ids only the first will be removed

quadTree.insert(e);

Update

Updates the entities position and size

An update is cheaper than removing and re-inserting

quadTree.update(e, position.getX(), position.getY(), size.getWidth(), size.getHeight());

Get

Point

Returns all entities on a single point

quadTree.get(point.getX(), point.getY());

Area

Returns all entities in a rough area

quadTree.get(area.getX(), area.getY(), area.getWidth(), area.getHeight());

Exact

Returns all entities exactly inside the requested area

quadTree.getExact(area.getX(), area.getY(), area.getWidth(), area.getHeight());

Example

public class QuadTreeSystem extends BaseEntitySystem {

    public QuadTreeSystem() {
        super(Aspect.all(Position.class, Size.class));
    }

    private final QuadTree quadTree = new QuadTree(0f, 0f, 100f, 200f);
    private ComponentMapper<Position> positionMapper;
    private ComponentMapper<Size> sizeMapper;

    @Override
    protected void inserted(int e) {
        Position position = positionMapper.get(e);
        Size size = sizeMapper.get(e);
        quadTree.insert(e, position.getX(), position.getY(), size.getWidth(), size.getHeight());
    }
    
    @Override
    protected void processSystem() {
        IntBag nearby = new IntBag();
        //Fills bag with ids of all entities in the area (0, 0) - (10, 10)
        quadTree.getExact(nearby, 0f, 0f, 10f, 10f);
        doAction(nearby);
    }

    @Override
    protected void removed(int e) {
        quadTree.remove(e);
    }


    @Override
    protected void dispose() {
        quadTree.dispose();
    }

}