Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (562)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Quadtree and Octree implementation  (Read 7558 times)
0 Members and 1 Guest are viewing this topic.
Offline DrHalfway
« Posted 2012-09-08 09:11:57 »

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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
public class GameObject {
   // the collider
  public final Circle circleCollider;
   
   // other GameObject specific data
 
   public GameObject(final float radius) {
      circleCollider = new Circle(radius);
   }
}


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
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);
   }
}


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
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.

1  
2  
3  
4  
public interface BroadPhase {
   public void insertObject(final GameObject obj);
   public void clean();
}


And now, for the main event! Let us create our QuadTree class

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
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

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
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.


Offline gouessej
« Reply #1 - Posted 2012-09-08 13:56:48 »

I prefer my implementations based on JUNG.

Offline matheus23

JGO Kernel


Medals: 107
Projects: 3


You think about my Avatar right now!


« Reply #2 - Posted 2012-09-09 09:32:16 »

I prefer my implementations based on JUNG.
We always like alternatives Smiley (and I like tutorials a lot Smiley ) pleeaaasee Cheesy *kindish voice*
(Currently I'm thinking about using quadtrees for a collision lib...)

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline gouessej
« Reply #3 - Posted 2012-09-09 15:05:53 »

I prefer my implementations based on JUNG.
We always like alternatives Smiley (and I like tutorials a lot Smiley ) pleeaaasee Cheesy *kindish voice*
(Currently I'm thinking about using quadtrees for a collision lib...)
JUNG has a lot more features. DrHalfway's example is nice in his particular case but I wouldn't use it in a library as is, I would rather use a part of his source code with a more general API for trees. My source code goes farther than JUNG for the tree support, there are a lot more tests similar to Java scenegraphs (Ardor3D, JMonkeyEngine).

Offline SHC
« Reply #4 - Posted 2012-10-15 15:27:23 »

There's a good tutorial at http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Offline CaptainJester

JGO Knight


Medals: 12
Projects: 2
Exp: 14 years


Make it work; make it better.


« Reply #5 - Posted 2012-10-17 17:10:56 »

I prefer my implementations based on JUNG.
We always like alternatives Smiley (and I like tutorials a lot Smiley ) pleeaaasee Cheesy *kindish voice*
(Currently I'm thinking about using quadtrees for a collision lib...)
JUNG has a lot more features. DrHalfway's example is nice in his particular case but I wouldn't use it in a library as is, I would rather use a part of his source code with a more general API for trees. My source code goes farther than JUNG for the tree support, there are a lot more tests similar to Java scenegraphs (Ardor3D, JMonkeyEngine).
Then share.

Don't shoot someone else down for sharing code. This would be a place to start learning since he was nice enough to share it.

Offline gouessej
« Reply #6 - Posted 2012-10-18 18:24:54 »

I prefer my implementations based on JUNG.
We always like alternatives Smiley (and I like tutorials a lot Smiley ) pleeaaasee Cheesy *kindish voice*
(Currently I'm thinking about using quadtrees for a collision lib...)
JUNG has a lot more features. DrHalfway's example is nice in his particular case but I wouldn't use it in a library as is, I would rather use a part of his source code with a more general API for trees. My source code goes farther than JUNG for the tree support, there are a lot more tests similar to Java scenegraphs (Ardor3D, JMonkeyEngine).
Then share.

Don't shoot someone else down for sharing code. This would be a place to start learning since he was nice enough to share it.
It's here, I thought you knew it was a part of my main project.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (21 views)
2014-09-21 02:42:18

BurntPizza (15 views)
2014-09-21 01:30:30

moogie (17 views)
2014-09-21 00:26:15

UprightPath (25 views)
2014-09-20 20:14:06

BurntPizza (27 views)
2014-09-19 03:14:18

Dwinin (42 views)
2014-09-12 09:08:26

Norakomi (73 views)
2014-09-10 13:57:51

TehJavaDev (97 views)
2014-09-10 06:39:09

Tekkerue (49 views)
2014-09-09 02:24:56

mitcheeb (70 views)
2014-09-08 06:06:29
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!