Hello there fellow Java Gamers – Another day and another code share day. Today i’d like to share some code on a Quadtree for 2D and Octree for 3D which in my opinion has a great medium between speed, reliablility and practicality. This is NOT a tutorial so I won’t go into details of how to build them, its strictly sharing code!
Our engine at the moment is configured to use both the Quadtree i’m about to share, the Octree which it will shortly use for 3D and a Grid implementation (which I wont share! *insert super evil scientist laugh here).
So enough of my rumbling, lets get to it. I’m known for not being able to explain code nicely, and I’m even more known not to comment code. If something is unclear, please drop it down and i’ll do my best to explain it.
This Quadtree is fairly simple, i’ve cut out some (more or less) important bits of implementation such as how to build the pair of collisions or how to retrieve an object from inside the Quadtree. For the purposes of sharing this implementation, i’ve used Java’s ArrayList ( our actual implementation uses a custom made container for speed ). So for those little things, i’ll leave them for you the reader, or else the world will turn grey and things will become… rather boring. Since these type of things are specific to the solution you’re working on, i’ll try to make it as easy as possible to incorporate it into your own Engine/Game.
This code was originally written in C by Christer Ericson and a full discussion about general BroadPhase detectors (including this quadtree/octree) can be found in his excellent book RealTime Collision Detection.
First let us define us some very basic primitive types to make this implementation work, we have GameObject, Circle and Vector, again your game/engine may have these setup slightly different.
public class GameObject {
// the collider
public final Circle circleCollider;
// other GameObject specific data
public GameObject(final float radius) {
circleCollider = new Circle(radius);
}
}
public class Circle {
public float radius;
public final Vector center;
public Circle(final float radius) {
this.radius = radius;
this.center = new Vector();
}
public void update(final Vector position) {
center.set(position);
}
}
public class Vector {
public final float vec[];
public Vector() {
vec = new float[3];
}
public Vector(final float x, final float y, final float z) {
vec = new float[3];
vec[0] = x;
vec[1] = y;
vec[2] = z;
}
public void set(final Vector position) {
for (int i = 0; i < 3; i++) {
vec[i] = position.vec[i];
}
}
}
Now that is out of the way, I’ll assume that GameObjects have a Circle collider attached to them, since its the fastest and easiest type to check collisions with. Next we define a simple interface called BroadPhase, you may wish to extend this with functionality if you wish.
public interface BroadPhase {
public void insertObject(final GameObject obj);
public void clean();
}
And now, for the main event! Let us create our QuadTree class
public class QTree implements BroadPhase {
private final QTreeNode node;
// define a quadtree extends as width and height, define quadtree depth.
public QTree(final float worldExtends, int worldDepth) {
node = new QTreeNode(0,0,worldExtends, worldDepth);
}
// insert a GameObject at the quadtree
public void insertObject(final GameObject obj) {
node.insertObject(obj, obj.circleCollider);
}
// clean the quadtree
public void clean() {
node.clean();
}
}
And let us not forget the main workhorse of the Quadtree, the nodes itself. There are man variations of Quadtrees available at the moment. This quadtree ensures that a single object only occupies a single cell, meaning that objects may end up higher in the quadtree nodes. The advantage of this is that it is potentially faster, the disadvantage is that the quadtree is less accurate, meaning that potentially more false-negative collisions are generated. This Quadtree is more useful for dynamic data, for static data you may wish to alter it, or go with another solution that works parrallel with this Quadtree.
Lets define the QtreeNode
public class QTreeNode {
private final int currDepth; // the current depth of this node
private final Vector center; // the center of this node
private final QTreeNode[] nodes; // the child nodes
private final ArrayList<GameObject> objects; // the objects stored at this node
public QTreeNode(float centerX, float centerY, float halfWidth, int stopDepth) {
this.currDepth = stopDepth;
// set Vector to current x-y-z values
this.center = new Vector(centerX, centerY, 0.0f);
this.objects = new ArrayList<GameObject>();
float offsetX = 0.0f;
float offsetY = 0.0f;
if (stopDepth > 0) {
// create 4 child nodes as long as depth is still greater than 0
this.nodes = new QTreeNode[4];
// halve child nodes size
float step = halfWidth * 0.5f;
// loop through and create new child nodes
for (int i = 0; i < 4; i++) {
// compute the offsets of the child nodes
offsetX = (((i & 1) == 0) ? step : -step);
offsetY = (((i & 2) == 0) ? step : -step);
nodes[i] = new QTreeNode(centerX + offsetX, centerY + offsetY, step, stopDepth - 1);
}
}
else {
this.nodes = null;
}
}
public void insertObject(final GameObject obj, final Circle collider) {
int index = 0; // get child node index as 0 initially
boolean straddle = false; // set straddling to false
float delta;
// get the raw arrays, makes it easier to run these in a loop
final float[] objPos = collider.center.vec;
final float[] nodePos = center.vec;
for (int i = 0; i < 2; i++) {
// compute the delta, nodePos Vector index - objPos Vector
delta = nodePos[i] - objPos[i];
// if the absolute of delta is less than or equal to radius object straddling, break
if (Math.abs(delta) <= collider.radius) {
straddle = true;
break;
}
// compute the index to isnert to child node
if (delta > 0.0f) {
index |= (1 << i);
}
}
if (!straddle && currDepth > 0) {
// not straddling, insert to child at index
nodes[index].insertObject(obj, collider);
}
else {
// straddling, insert to this node
objects.insert(obj);
}
}
public void clean() {
objects.clear();
// clean children if available
if (currDepth > 0) {
for (int i = 0; i < 4; i++) {
nodes[i].clean();
}
}
}
}
Well, that doesnt look pretty. I believe I promised an octree implementation. Believe it or not, it is almost EXACLY the same as above, except an Octree has 8 child nodes instead. Below is the OctreeNode implementation.
public class OctreeNode {
private final int currDepth; // the current depth of this node
private final Vector center; // the center of this node
private final OcTreeNode[] nodes; // the child nodes
private final ArrayList<GameObject> objects; // the objects stored at this node
public OctreeNode(float centerX, float centerY float centerZ, float halfWidth, int stopDepth) {
this.currDepth = stopDepth;
// set Vector to current x-y-z values
this.center = new Vector(centerX, centerY, centerZ);
this.objects = new ArrayList<GameObject>();
float offsetX = 0.0f;
float offsetY = 0.0f;
float offsetZ = 0.0f;
if (stopDepth > 0) {
// create 4 child nodes as long as depth is still greater than 0
this.nodes = new QTreeNode[8];
// halve child nodes size
float step = halfWidth * 0.5f;
// loop through and create new child nodes
for (int i = 0; i < 8; i++) {
// compute the offsets of the child nodes
offsetX = (((i & 1) == 0) ? step : -step);
offsetY = (((i & 2) == 0) ? step : -step);
offsetZ = (((i & 4) == 0) ? step : -step);
nodes[i] = new OctreeNode(centerX + offsetX, centerY + offsetY, centerZ + offsetZ, step, stopDepth - 1);
}
}
else {
this.nodes = null;
}
}
public void insertObject(final GameObject obj, final Sphere collider) {
int index = 0; // get child node index as 0 initially
boolean straddle = false; // set straddling to false
float delta;
// get the raw arrays, makes it easier to run these in a loop
final float[] objPos = collider.center.vec;
final float[] nodePos = center.vec;
for (int i = 0; i < 3; i++) {
// compute the delta, nodePos Vector index - objPos Vector
delta = nodePos[i] - objPos[i];
// if the absolute of delta is less than or equal to radius object straddling, break
if (Math.abs(delta) <= collider.radius) {
straddle = true;
break;
}
// compute the index to isnert to child node
if (delta > 0.0f) {
index |= (1 << i);
}
}
if (!straddle && currDepth > 0) {
// not straddling, insert to child at index
nodes[index].insertObject(obj, collider);
}
else {
// straddling, insert to this node
objects.insert(obj);
}
}
public void clean() {
objects.clear();
// clean children if available
if (currDepth > 0) {
for (int i = 0; i < 8; i++) {
nodes[i].clean();
}
}
}
}
Thank you for reading this and I hope this comes in handy for you the reader as some point. I was debating weather or not this should be a code snippet article or a tutorial and came to conclusion that its not exacly an article on “how” to build a quadtree or octree as there are so many different implementations available. This implementation is very basic, for example, performing collision detection or build pair-pair lists has been omitted. If there is some confusion with the implementation though i’ll post a code example on how to do that aswell.
I’m trying to get some screenshots of this running in our engine. Again thank you for reading and good luck! =]
Here is a Screenshot of Quadtree in Debug mode with Depth 3 (the big object is one you control). I sort of plowed through those objects there. The colored Cells are occupied. The darker the color, the more the depth descends.
And Screenshot of Quadtree with Depth 4.
(and I like tutorials a lot 
kindish voice