source: lost-perception/astar/QuadTree.java

package astar;

import java.awt.Graphics;
import java.awt.Rectangle;

import main.MapObject;

public class QuadTree {
    private QuadTree[] arr;
    private AStarNode node;
    private int depth;
    private int x;
    private int y;
    private int width;
    private int height;
    
    public QuadTree(final QuadTree tree1, final QuadTree tree2, final QuadTree tree3, final QuadTree tree4) {
        (this.arr = new QuadTree[4])[0] = tree1;
        this.arr[1] = tree2;
        this.arr[2] = tree3;
        this.arr[3] = tree4;
        this.depth = 1;
        tree1.depth = this.depth + 1;
        tree2.depth = this.depth + 1;
        tree3.depth = this.depth + 1;
        tree4.depth = this.depth + 1;
        this.node = null;
    }
    
    public QuadTree(final int x, final int y, final int width, final int height) {
        this.arr = null;
        this.node = new AStarNode(this);
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.depth = 1;
    }
    
    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
    
    public int getHeight() {
        return this.height;
    }
    
    public int getWidth() {
        return this.width;
    }
    
    public int getDepth() {
        return this.depth;
    }
    
    public boolean isLeaf() {
        return this.arr == null;
    }
    
    public QuadTree[] getChildren() {
        return this.arr;
    }
    
    public AStarNode getNode() {
        return this.node;
    }
    
    public void expandTree(final QuadTree tree1, final QuadTree tree2, final QuadTree tree3, final QuadTree tree4) {
        if (!this.isLeaf()) {
            return;
        }
        (this.arr = new QuadTree[4])[0] = tree1;
        this.arr[1] = tree2;
        this.arr[2] = tree3;
        this.arr[3] = tree4;
        tree1.depth = this.depth + 1;
        tree2.depth = this.depth + 1;
        tree3.depth = this.depth + 1;
        tree4.depth = this.depth + 1;
        this.node = null;
    }
    
    public void addObstacle(final MapObject o) {
        if (o.getBound() == null) {
            return;
        }
        if (!this.isLeaf()) {
            this.arr[0].addObstacle(o);
            this.arr[1].addObstacle(o);
            this.arr[2].addObstacle(o);
            this.arr[3].addObstacle(o);
            return;
        }
        final Rectangle square = new Rectangle(this.getX(), this.getY(), this.getWidth(), this.getHeight());
        if (!this.getNode().passable || !o.getBound().intersects(square, o)) {
            return;
        }
        if (this.depth == 4 || o.getBound().contains(square, o)) {
            this.getNode().passable = false;
            return;
        }
        final int newWidth = this.getWidth() / 2;
        final int newHeight = this.getHeight() / 2;
        final QuadTree qt1 = new QuadTree(this.getX(), this.getY(), newWidth, newHeight);
        final QuadTree qt2 = new QuadTree(this.getX() + newWidth, this.getY(), newWidth, newHeight);
        final QuadTree qt3 = new QuadTree(this.getX(), this.getY() + newHeight, newWidth, newHeight);
        final QuadTree qt4 = new QuadTree(this.getX() + newWidth, this.getY() + newHeight, newWidth, newHeight);
        this.expandTree(qt1, qt2, qt3, qt4);
        this.arr[0].addObstacle(o);
        this.arr[1].addObstacle(o);
        this.arr[2].addObstacle(o);
        this.arr[3].addObstacle(o);
    }
    
    public void coalesce() {
        if (this.isLeaf()) {
            return;
        }
        this.arr[0].coalesce();
        this.arr[1].coalesce();
        this.arr[2].coalesce();
        this.arr[3].coalesce();
        if (!this.arr[0].isLeaf() || this.arr[0].node.passable) {
            return;
        }
        if (!this.arr[1].isLeaf() || this.arr[1].node.passable) {
            return;
        }
        if (!this.arr[2].isLeaf() || this.arr[2].node.passable) {
            return;
        }
        if (!this.arr[3].isLeaf() || this.arr[3].node.passable) {
            return;
        }
        this.x = this.arr[0].x;
        this.y = this.arr[0].y;
        this.width = this.arr[0].width * 2;
        this.height = this.arr[0].height * 2;
        this.arr = null;
        this.node = new AStarNode(this);
        this.node.passable = false;
    }
    
    public void draw(final Graphics g, final int x, final int y, final boolean fill) {
        if (this.isLeaf()) {
            if (fill) {
                g.fillRect(this.getX() + x, this.getY() + y, this.getWidth(), this.getHeight());
            }
            else {
                g.drawRect(this.getX() + x, this.getY() + y, this.getWidth(), this.getHeight());
            }
        }
        else {
            this.arr[0].draw(g, x, y, fill);
            this.arr[1].draw(g, x, y, fill);
            this.arr[2].draw(g, x, y, fill);
            this.arr[3].draw(g, x, y, fill);
        }
    }
    
    public void drawBlocked(final Graphics g, final int x, final int y) {
        if (this.isLeaf()) {
            if (!this.getNode().passable) {
                g.fillRect(this.getX() + x, this.getY() + y, this.getWidth(), this.getHeight());
            }
        }
        else {
            this.arr[0].drawBlocked(g, x, y);
            this.arr[1].drawBlocked(g, x, y);
            this.arr[2].drawBlocked(g, x, y);
            this.arr[3].drawBlocked(g, x, y);
        }
    }
}