Why algorithms matter. Quad tree example

Introduction

    Plot above shows differences between brute force collision detection algorithm and quad tree based collision detection algorithm. x axis shows number of circles in scene and y axis shows time in seconds which spent detecting collision between one circle and others.

Explanation

    Even big-O notation is a base of software engineering many programmers don't care about algorithms they use. In earlier stages of development you may not see difference between O(N) and O(logN) algorithms but later it may become a really huge problem. As you can see on the plotting above performance becomes poor if you have 2 millions points if you use brute force and quad tree shows good performance even if you have 5 million points.

Quad tree

    So basically quad tree is data structure which node has exactly four children and each child has four children and so on recursively. It's often used in 2D game development for collision detection, image processing and so on.

How it works

    Let me explain you how it works using collision detection in 2D game as an example. 

Imagine you have a game surface which holds a lot of moving objects which collide with each other. As example it may be some shooter game with upside down view with moving player and targets which hit boxes are represented as circles he must hit. In addition surface has some entities such as bushes, trees and so on. And player shoots. You have to detect the collision of a bullet and enemies, besides bullet may hit a tree and destroyed or change it's direction and so on. You may check bullet's collision with every object in game using something like this:

    public static HashSet&ltPair&ltShape, Shape&gt&gt getCollisions(List&ltshape&gt list, Shape s) {
        HashSet&ltPair&ltShape, Shape&gt> pairs = new HashSet&lt&gt();
        for (Shape c : list) {
            if (s.equals(c)) {
                continue;
            }
            Vec2d v1 = new Vec2d(c.getBounds2D().getCenterX(), c.getBounds2D().getCenterY());
            Vec2d v2 = new Vec2d(s.getBounds2D().getCenterX(), s.getBounds2D().getCenterY());
            double distance = v1.distance(v2);
            if (distance <= c.getBounds2D().getHeight() / 2 + s.getBounds2D().getHeight() / 2) {
                pairs.add(new Pair<>(s, c));
            }
        }

        return pairs;
    }

This code uses simple idea that if distance between two circles is lower than sum of their radiuses they collide. As you can see this code is't too fast by itself. It uses a lot of division, square root to get distance and so on but it's going to be ok to use it by passing all objects to the list argument if you have about 100 objects on the screen or something about this. But what if you have 10000 objects? You will have to do 100000000 operations every frame. Looks like it's not going to work. What do you have to do in this case? Well, forget about it and drink a lot of vodka thinking about your miserableness. Oh, no sorry thats an article about quad tree. Use quad tree!
    The main idea is that you don't have to check everything that cant collide at all. It's like when for example you have two boxes with eggs. Eggs in different boxes can't collide with each other. So we have to divide our game scene into quads and check only those objects that lies in the same quad as our bullet! That's it.

As you can see on the picture above pink circle in the middle which is out bullet is collided with cyan circle. Red rectangles represent quad tree.

Demo

Implementation

Insertion

    private static void insertShape(Shape shape, QuadTreeNode root) {
        if (!root.mBoundingRect.contains(shape.getBounds2D()) && !shape.intersects(root.mBoundingRect)) {
            // Cant add because shape lies completely outside of the rectangle
            return;
        }

        if (root.mChildren == null) {
            if (root.mObjects == null || root.mObjects.size() < root.getMaximumObjectsPerQuad() ||
                    root.mBoundingRect.getWidth() / 2 <= root.mMinimumSide ||
                    root.mBoundingRect.getHeight() / 2 <= root.mMinimumSide) {
                if (root.mObjects == null) {
                    root.mObjects = new ArrayList<>();
                }
                root.mObjects.add(shape);
                return;
            } else {
                divideRectangle(root);
            }
        }

        for (QuadTreeNode child : root.mChildren) {
            if (root.mObjects != null) {
                for (Shape s : root.mObjects) {
                    insertShape(s, child);
                }
            }
            insertShape(shape, child);
        }

        root.mObjects = null;
    }

    Basically insertion routine is very simple. First we have to check if shape is contained within our bounding rect(by contained i mean full continence and partial continence when only part of it is inside of rectangle) if it's not just return. Second we check conditions for insertion. Those conditions may be different, here i have getMaximumObjectsPerQuad condition which controls maximum number of shapes within quad and minimum side condition which controls minimum quad side. If conditions pass we just add shape to current node that means that current node becomes a leaf(node which contains objects). If conditions don't pass and node doesn't have any children we divide quad into four and put objects contained in current node and new shape into these four quads.

Remove

    Remove operation is a little bit more tricky than insertion.

    private static void getUniqueShapesInQuad(QuadTreeNode root, HashSet<Shape> set) {
        assert root != null;

        if (root.getObjects() != null) {
            set.addAll(root.getObjects());
            return;
        }

        if (root.mChildren != null) {
            for (QuadTreeNode n : root.mChildren) {
                getUniqueShapesInQuad(n, set);
            }
        }
    }

    private static void undivideRectangleIfNeeded(QuadTreeNode parent) {
        assert parent != null;

        HashSet<Shape> shapes = new HashSet<>();
        getUniqueShapesInQuad(parent, shapes);

        if (shapes.size() <= parent.getMaximumObjectsPerQuad()) {
            assert parent.mObjects == null;
            parent.mObjects = new ArrayList<>();
            parent.getObjects().addAll(shapes);
            for (QuadTreeNode n : parent.mChildren) {
                n.mParent = null;
            }
            parent.mChildren = null;

            if (parent.mParent != null) {
                undivideRectangleIfNeeded(parent.mParent);
            }
        }
    }

    private static void removeShape(Shape s, QuadTreeNode root) {
        ArrayList<QuadTreeNode> nodesContainingShape = new ArrayList<>();
        containsShape(s, root, nodesContainingShape);

        HashMap<QuadTreeNode, QuadTreeNode> parentChildMap = new HashMap<>();
        for (QuadTreeNode n : nodesContainingShape) {
            n.getObjects().remove(s);
            parentChildMap.put(n.mParent, n);
        }

        for (HashMap.Entry<QuadTreeNode, QuadTreeNode> e : parentChildMap.entrySet()) {
            if (e.getValue().mParent != null) {
                undivideRectangleIfNeeded(e.getKey());
            }
        }
    }

The main idea behind remove is that you need to recursively check if number of objects in parent node of the node you removed shape from is equal or less than maximum number of objects in a node. If so we have to "undivide" or merge children quads into one and repeat it recursively .

Thats it. Building of quad tree is simple - it's just adding all elements you need and updating shape is removing it and adding back.

Summing up

Quad tree is a good data structure which operates in O(logN) in average(worst case performance is O(N)) which can help you to get good performance in performance dependant tasks.

You can get the code for this article here