gdx-quadtree

Recommended reading

You're making a top-down real-time strategy game, where the player handles lots of units on a large map, and naturally all of these units need to execute some logic, such as checking if they're close enough to an enemy unit so they can attack them. As you can see in Game Programming Patterns' Spatial Partition section, this gets ugly really fast. 

void updateUnits(Unit[] units) {
    for (int attackerIndex = 0; attackerIndex < units.length; attackerIndex++) {
        Unit attacker = units[attackerIndex];
        for (int defenderIndex = 0; defenderIndex < units.length; defenderIndex++) {
            Unit defender = units[defenderIndex];
            if (defenderIndex == attackerIndex) continue;
            if (defender.getPosition().dst(attacker.getPosition()) < attacker.getMaxAttackDistance()) {
                attacker.attack(defender);
            }
        }
        // Other unit logic
    }
}

Just by looking at the code, you can tell it's going to be pure pain for the machine that's going to run it, and the problem is only going to get worse the more units are spawned into the world. This won't cut it!

The Solution

Use a spatial partitioning pattern! Game Programming Patterns describes it as: 

For a set of objects, each has a position in space. 
Store them in a spatial data structure that organizes the objects by their positions. 
This data structure lets you efficiently query for objects at or near a location. 
When an object's position changes, update the spatial data structure so that it can continue to find the object.

Now keep in mind - this is really good if you have lots of objects in your game world. If you're making a game such as a platformer or anything that doesn't have too many objects that need to check their position relative to other objects, then it's not worth it - in fact, you'll make the game perform worse!

The Quadtree implementation I'm using is gdx-quadtree, which I made by looking at these already existing ones 1, 2, 3.
Click here for a live demo of gdx-quadtree, and here for the demo's source code.

You may be wondering why I made another Quadtree library when there's already three of them - here's why:

My implementation uses libGDX's Poolable interface to a great extent (more information here), and allows you to change various properties of the Quadtree (such as the maximum amount of levels the Quadtree can split into and the maximum amount of items per node) in an easier, object-oriented way. Not only that, but it works by actually using a Rectangle rather than a point (regarding this, I tested the first two Quadtree implementations but not the third one, so I'm not sure if that's also true for the last one).

Usage

Rectangle cameraBounds;
Array<Entity> entities;
QuadTreeRoot<Entity> quadtreeRoot;

@Override
public void create() {
    Rectangle rootBounds = new Rectangle(-1000, -1000, +1000, +1000);
    quadtreeRoot = new QuadTreeRoot<Entity>(rootBounds);  // another constructor is available
    // initialization of entities, camera rectangle, etc.
}

@Override
public void render() {
    // Game logic
    root.Clear();
    for (Entity entity : entities) {
        QuadTreeItem<Entity> item = root.ObtainItem();
        item.init(entity, entity.getAABBRectangle());
        // Performance would probably much better if all static entities & geometry 
        // that make up a level is inserted into the Quadtree only once!
        root.insert(item);
    }
    Array<QuadTreeItem<Entity>> list = root.retrieve(cameraBounds);
    for (QuadTreeItem<Entity> item : list) {
        item.getObject().draw(batch);
    }
}
In this case, we're using the Quadtree to find all entities inside an area, represented by our cameraBounds Rectangle to then draw them. It's exactly the same as the example in the demo. And while it can be used as a culling algorhythm, I don't think it's worth it - disabling the Quadtree and testing all entities against the cameraBounds Rectangle then discarding the ones that don't overlap said rectangle is much faster than retrieving those same entities with the Quadtree, even with very large numbers. You should only use this pattern if you are doing enough queries to find object by location that your performance is suffering.

Going back to the example mentioned at the beginning - it could look like this: 

Array<Rectangle> areas;

@Override
public void create() {
    areas = new Array<Rectangle>();
    areas.add(new Rectangle(10, 10, 100, 100));
    areas.add(new Rectangle(...));
    // and so on
}

void updateUnits(Unit[] units) {
    for (Rectangle area : areas) {
        Array<Unit> units = root.retrieve(area);
        for (int attackerIndex = 0; attackerIndex < units.length; attackerIndex++) {
            Unit attacker = units[attackerIndex];
            for (int defenderIndex = 0; defenderIndex < units.length; defenderIndex++) {
                Unit defender = units[defenderIndex];
                if (defenderIndex == attackerIndex) continue;
                if (defender.getPosition().dst(attacker.getPosition()) < attacker.getMaxAttackDistance()) {
                    attacker.attack(defender);
                }
            }
            // Other unit logic  
        }
    }
}
This is extremely basic, and doesn't cover all corner cases (such as units being close enough to interact with each other, but in different areas), but it's good for showcasing the Quadtree's strength - now units will check if they can attack other units close it, but will not consider units too far away!

The Quadtree is a really powerful structure when used properly - keyword is properly. If your game world doesn't have many objects, or doesn't need to find objects by their position too often, then it's best not to use any spatial partitioning - or at the very least, not this particular one. Keep it simple!

Back to libGDX First published: 2023-03-04 Last revision: 2024-09-29