Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (527)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (594)
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  
  Java Quadtree Implementation  (Read 14214 times)
0 Members and 1 Guest are viewing this topic.
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Posted 2012-07-13 12:32:25 »

Hey guys. I have something for you. It's my implementation of the quadtree, built on top of the Wikipedia Article.

Quadtree.java:
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  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
package org.matheusdev.arcengine.collision;

import java.util.List;

/**
 *
 * @author matheusdev
 *
 */

public class Quadtree<E extends QuadtreeElement> {
   
   private final QuadRect bounds;
   private E[] elements;
   
   private Quadtree<E> topLeft;
   private Quadtree<E> topRight;
   private Quadtree<E> botLeft;
   private Quadtree<E> botRight;
   
   public Quadtree(float size, int elemPerQuad) {
      this(0, 0, size, elemPerQuad);
   }
   
   @SuppressWarnings("unchecked")
   public Quadtree(float x, float y, float size, int elemPerQuad) {
      bounds = new QuadRect(x, y, size);
      elements = (E[])(new QuadtreeElement[elemPerQuad]);
   }
   
   protected boolean set(E e) {
      for (int i = 0; i < maxElem(); i++) {
         if (elements[i] == null) {
            elements[i] = e;
            return true;
         }
      }
      return false;
   }
   
   public int maxElem() {
      return elements.length;
   }
   
   public boolean insert(E e) {
      if (!bounds.contains(e.getX(), e.getY())) {
         return false;
      }
      if (set(e)) {
         return true;
      } else {
         subdivide();
         if (topRight.insert(e)) return true;
         if (topLeft.insert(e)) return true;
         if (botRight.insert(e)) return true;
         if (botLeft.insert(e)) return true;
         
         throw new ImpossibleException();
      }
   }
   
   public void query(StaticRect range, List<E> results) {
      if (!bounds.intersects(range)) {
         return;
      }
      for (int i = 0; i < maxElem(); i++) {
         if (elements[i] != null) {
            if (range.contains(elements[i].getX(), elements[i].getY())) {
               results.add(elements[i]);
            }
         }
      }
      if (!hasChildren()) {
         return;
      }
      topLeft.query(range, results);
      topRight.query(range, results);
      botLeft.query(range, results);
      botRight.query(range, results);
   }
   
   public boolean hasChildren() {
      return topLeft != null;
   }
   
   /**
    * <p>
    * Subdivides this Quadtree into 4 other quadtrees.
    * </p>
    * <p>
    * This is usually used, when this Quadtree already has an
    * Element.
    * </p>
    * @return whether this Quadtree was subdivided, or didn't subdivide,
    * because it was already subdivided.
    */

   protected boolean subdivide() {
      if (hasChildren()) {
         return false;
      }
      float hs = bounds.s/2;
      topLeft  = new Quadtree<E>(bounds.x, bounds.y, hs, maxElem());
      topRight = new Quadtree<E>(bounds.x+hs, bounds.y, hs, maxElem());
      botLeft  = new Quadtree<E>(bounds.x, bounds.y+hs, hs, maxElem());
      botRight = new Quadtree<E>(bounds.x+hs, bounds.y+hs, hs, maxElem());
      return true;
   }
}


QuadtreeElement.java:
1  
2  
3  
4  
5  
6  
7  
8  
package org.matheusdev.arcengine.collision;

public interface QuadtreeElement {
   
   public float getX();
   public float getY();

}


I won't post the SolidRect.java and the QuadRect.java code here, because these classes would then require Collidable.java and that would be too much for this topic Smiley
The classes QuadRect.java and SolidRect.java are easy to implement anyways Wink

As you can see on the package name, this is code from my current work-in-progress engine ArcEngine. I hope, I'll finish it sometime. It will be built ontop of libGDX with TWL and other stuff Smiley

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline atombrot
« Reply #1 - Posted 2012-07-13 14:25:07 »

What is the Random import used for? Wink

Looks nice from first sight but I think there are some minor issues with your approach.

[Edit]
Because i always switch the words in my text and I think it was written quite unclear I declared a short terminology and use it in my explanation:
Tree: The tree itself which stores the root node and config.
Node: A node defines an area and can have 4 sub nodes.
Item: The effective item, that is stored in the tree.
[/Edit]

Your items are only stored in one node but as I see it rectangles sometimes can be children of multple nodes. This could result in problems. For example imagine the root node has a size of 256x256 units. This is subdivided into 4 128x128 pixel unit sized nodes. When you have an item, that has a size 128x128 (could also be any other size) and it has the location 127, 127, it will fall into the north west / topLeft node, despite the most part of the item lays in the bottom right (and some in the bottom left and top right nodes). If you want to fix this, you would need to insert items in every child node (let the node decide, if the item intersects the node), when you insert into children.

One important thing that is missing is rebalancing. You do not want to recreate the tree every update cycle. There needs to be some logic to update the tree, otherwise it can only be used for static objects, that don't move at all.

If you want, I can post my implementation of the quad tree, but it isn't really elegant, commented or anything like that. But take a look at this: http://www.jotschi.de/?p=530

This guy has created a simple (abstract) quad tree and a point and a rect based implementation of it and shared the code on git hub. Look into the rect based implementation to see how he handles it. Unfortunately he also doesn't do rebalancing.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 834
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2012-07-13 14:28:53 »

  • Let's say you specify that you can have N elements per quad.
  • Now put N+1 QuadtreeElement elements at the exact same position.
  • Kaboom! (infinite recursion)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #3 - Posted 2012-07-13 16:32:25 »

What is the Random import used for? Wink
There was also an ArrayList unused import... That was, because I had some testing code below, and I just clipped it away.

Looks nice from first sight but I think there are some minor issues with your approach.

[Edit]
Because i always switch the words in my text and I think it was written quite unclear I declared a short terminology and use it in my explanation:
Tree: The tree itself which stores the root node and config.
Node: A node defines an area and can have 4 sub nodes.
Item: The effective item, that is stored in the tree.
[/Edit]

Your items are only stored in one node but as I see it rectangles sometimes can be children of multple nodes. This could result in problems. For example imagine the root node has a size of 256x256 units. This is subdivided into 4 128x128 pixel unit sized nodes. When you have an item, that has a size 128x128 (could also be any other size) and it has the location 127, 127, it will fall into the north west / topLeft node, despite the most part of the item lays in the bottom right (and some in the bottom left and top right nodes). If you want to fix this, you would need to insert items in every child node (let the node decide, if the item intersects the node), when you insert into children.
Yes. As you can see, the Quadtree only supports Points. I have an Idea in mind, how to add rectangles anyways.

One important thing that is missing is rebalancing. You do not want to recreate the tree every update cycle. There needs to be some logic to update the tree, otherwise it can only be used for static objects, that don't move at all.
Yep. That's right. I wanted to use it for static objects only Smiley
That is, because I'm following some specific Game-Idea I randomly had and in that game I won't need any dynamic objects, or at least I don't need them to be in a quad-tree.

  • Let's say you specify that you can have N elements per quad.
  • Now put N+1 QuadtreeElement elements at the exact same position.
  • Kaboom! (infinite recursion)
This worked:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
   private static class Element implements QuadtreeElement {
      float x, y;
      Element(float x, float y) {
         this.x = x;
         this.y = y;
      }
      public float getX() {
         return x;
      }
      public float getY() {
         return y;
      }
   }
   
   public static void main(String[] args) {
      Quadtree<Element> tree = new Quadtree<Element>(512, 1);
      tree.insert(new Element(20, 20));
      tree.insert(new Element(20, 20));
      System.out.println("Finished...");
   }

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline ra4king

JGO Kernel


Medals: 355
Projects: 3
Exp: 5 years


I'm the King!


« Reply #4 - Posted 2012-07-13 18:15:24 »

I completely disagree with the usage of arrays here. Since you are using generics, you should be using a simple ArrayList that holds all the elements. The max size should be an integer field.

Using an ArrayList makes dynamically removing and adding elements faster, since there should be no null check nor loop through to find the first null element.

EDIT: Riven just noticed that you're not splitting the elements into the sub-quad. In a quadtree, elements are usually in the leafs. When a quad divides, it splits all its elements into their suitable sub-quad.

Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 834
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2012-07-13 18:21:01 »

EDIT: Riven just noticed that you're not splitting the elements into the sub-quad. In a quadtree, elements are usually in the leafs. When a quad divides, it splits all its elements into their suitable sub-quad.
Which will cause the infinite recursion I mentioned earlier, so you have to ensure to have a max-depth of your tree.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #6 - Posted 2012-07-13 18:42:32 »

EDIT: Riven just noticed that you're not splitting the elements into the sub-quad. In a quadtree, elements are usually in the leafs. When a quad divides, it splits all its elements into their suitable sub-quad.
Which will cause the infinite recursion I mentioned earlier, so you have to ensure to have a max-depth of your tree.
Oh. I'm not having such a leaf-concept here...
Is this bad approach or should I leave it like that?

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 834
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2012-07-13 18:47:10 »

It's a bad approach. It ruins the point of a quad tree actually, as you can't query a tiny region in a vast area, without checking a lot of elements in nodes you don't care about.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #8 - Posted 2012-07-13 20:23:40 »

I've always found that edge based works better...sadly I can't think of a good way to do it in java.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 834
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2012-07-18 05:18:14 »

I've always found that edge based works better...sadly I can't think of a good way to do it in java.
Could you elaborate? My Google-fu seems insufficient.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #10 - Posted 2012-07-18 12:17:02 »

Sure.  Here's a quick sketch.

Classic version. Store an entity in the smallest node that will contain it.  It's easy to write but not very efficient as it requires a fair amount of tree walking for pretty much all queries (at least one leaf-> root or vise-versa is required).  So the next version we only store entities in leaf nodes.  Opens up a can of worms about handling all entities that have volumes that cross boundaries but significant drops the required tree walks.

Step back.  How often do we need to perform global operations? Virtually never.  Probably no: "Hey, I've randomly chosen the origin of a circle with this radius: What entities are inside it?"  Pretty much everything is going to be related to an existing entity.  What can I see? What might I collide with?  Spawn a missile here with respect to me. etc. etc.  So the non-leaf nodes should not need to be visited often.  (Actually they can not exist at all, but that's a little trickier)

So in edge based, each leaf stores its edges, where each edge can connect to two leaves on the opposite side.  The two comes from adding the additional requirement that all touching leaves be within one level of each other.  (This shouldn't be a big deal as is a normal distribution).  Now since almost always start with a known leaf, then operations can simply directly walk other leaves within the needed volume.

And yeah Riven, using your MappedObject library would work pretty well for this.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #11 - Posted 2012-07-18 13:39:48 »

I still jave to fully understand the quadtree. Would it be possible to query any shapy of the area covered? If the entities are moving, do they all have to be updated every frame, and is the tree thus defined? Also, can the nodes cover smaller areas themselves, such as tiny rectangles? Usually, baddied in games take up more than just a single point Smiley

Offline Roquen
« Reply #12 - Posted 2012-07-18 15:19:22 »

The first question should be: do I even want to use a quadtree.  They were very interesting say from the mid-90s and earlier, but are less-so now. They're good at reducing memory footprint if you have clustering of entities...but memory footprint isn't quite the issue that it used to be.  Also the gap is speed between reading/writing to main memory and CPU speeds have made them a little trickier to get really fast.  I think that most people would be better simply using one or more uniform grids which is much easier to write.  For example any space query is pretty much the same thing as a scanline method of rendering that shape with more expensive checks along the edge and 'is-inside' is auto-magic for interior cells.

WRT quadtrees.  Yeah, any shape can be queried...you have to code it up.  When entities move, they need to be moved to the appropriate node if they go across a boundary (or multiple nodes if you're tracking stuff that way).  Entities can be any shape...typically will be modeled by a sphere, AABBox or extruded versions of the previous.  Typically you'll query for potential sets and then refine from there.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #13 - Posted 2012-07-18 15:26:45 »

The first question should be: do I even want to use a quadtree.  They were very interesting say from the mid-90s and earlier, but are less-so now. They're good at reducing memory footprint if you have clustering of entities...but memory footprint isn't quite the issue that it used to be.  Also the gap is speed between reading/writing to main memory and CPU speeds have made them a little trickier to get really fast.  I think that most people would be better simply using one or more uniform grids which is much easier to write.  For example any space query is pretty much the same thing as a scanline method of rendering that shape with more expensive checks along the edge and 'is-inside' is auto-magic for interior cells.

WRT quadtrees.  Yeah, any shape can be queried...you have to code it up.  When entities move, they need to be moved to the appropriate node if they go across a boundary (or multiple nodes if you're tracking stuff that way).  Entities can be any shape...typically will be modeled by a sphere, AABBox or extruded versions of the previous.  Typically you'll query for potential sets  and then refine from there.

I agree on the grid, but I'm trying to understand this now. What happens when a box/shape is overlapping a line, split between two nodes? Are there any solid and extendable implementations of this in java, that I can play with?

Offline Roquen
« Reply #14 - Posted 2012-07-19 08:31:47 »

Uniform grid or quadtree you'll have to deal with the issue of an entity crossing one or more boundaries.  Assuming that collision detection is instantaneous and that the maximum extent (radius if circle or edge length if AABBox) of the largest entity is relatively small, then the easy solution is to simply store each entity in the cell or node of its center and to expand all queries by half that maximal extent.  Minor extension is to logically break large entities into smaller proxies if they are relatively few.  Another option is to simply store references in every node/cell that entity is within...that's pretty much a PITA.
Offline Lucasmontec

Junior Devvie


Medals: 1
Exp: 4 years



« Reply #15 - Posted 2013-05-06 20:21:50 »

People people, I'm here to solve all the problems with my google-fu:
http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

S2 all of you =)
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #16 - Posted 2013-05-06 20:46:17 »

People people, I'm here to solve all the problems with my google-fu:
http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

S2 all of you =)

Ah. No need of google here. This topic is old. Also there are already like thousands of Quadtree implementations out there now.
And my last point: I've never used the quadtree.
Functional people like quadtrees.
The other use grids.
The pure functional people just have no other choice Grin

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Lucasmontec

Junior Devvie


Medals: 1
Exp: 4 years



« Reply #17 - Posted 2013-05-06 21:33:05 »

Grids are very good for handeling objects the same size. But when size varies quadtrees can do a bit better.
Offline Roquen
« Reply #18 - Posted 2013-05-07 03:59:01 »

Distribution is the key litmus test.  Then it depends on the implementation.
Offline gouessej
« Reply #19 - Posted 2013-05-08 12:40:06 »

Functional people like quadtrees.
What do you mean? I plan to use a quadtree (or a BSP tree) to build a network of cells and portals.

Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #20 - Posted 2013-05-08 12:45:44 »

Functional people like quadtrees.
What do you mean? I plan to use a quadtree (or a BSP tree) to build a network of cells and portals.

With 'functional' people, I mean people who write in purely functional languages.
What does purely functional mean? You can't change anything. Imagine to only be able to create
final [datatype] variable
variables.

What's the problem?
Imagine you have a Grid. A very simple one, only an array, where each Tile for a tile-based game is stored. Whenever you want to change the tile, you need to create a new Grid and copy all the tiles into them, since you can't change anything (a.k.a. so called side-effects (changes of state) aren't allowed).
Now copying a grid which is big is not cheap. What they do is: Use a data structure which is basically a tree. And then whenever a tree leaf changes, they only have to change all the leaf's ancestors. Which is only 3-10 Quadtree nodes, depending on the size of the Quadtree and implementation.

Done.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Roquen
« Reply #21 - Posted 2013-05-14 12:22:32 »

Immutability hurts you here.  In no way does it help.  People with distributions which aren't close to uniform prefer <method-X> over uniform grids.
Offline l3dx

Junior Devvie


Medals: 1


Say what?


« Reply #22 - Posted 2013-05-14 12:47:00 »

Just a side note:

You don't copy immutable objects. As they never change (mutate) there is no point in holding more than one copy. You reference it (which is cheaper).
Offline StreetDoggy

Innocent Bystander





« Reply #23 - Posted 2013-05-14 13:55:58 »

Try this implementation PointQuadTree.java.
It will handle Riven's issue with infinite recursion, and it shatters/merges branches in the tree as needed.
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #24 - Posted 2013-05-15 13:11:54 »

Immutability hurts you here.  In no way does it help.  People with distributions which aren't close to uniform prefer <method-X> over uniform grids.

Yes... I was talking about functional languages...  Cranky

Just a side note:

You don't copy immutable objects. As they never change (mutate) there is no point in holding more than one copy. You reference it (which is cheaper).

With 'copy' I mean 'create a new one with changed parameters'. Take the copy method from scala's case classes as example...
(just so you know:)
1  
2  
case class Person(name: String, age: Int)
val john = Person("john", 21).copy(age = 22); // Results in "john", 22

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Roquen
« Reply #25 - Posted 2013-05-15 15:11:35 »

Immutability hurts you here.  In no way does it help.  People with distributions which aren't close to uniform prefer <method-X> over uniform grids.

Yes... I was talking about functional languages...  Cranky
You mean you're talking about purely functional languages. Wink
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #26 - Posted 2013-05-15 16:29:09 »

Immutability hurts you here.  In no way does it help.  People with distributions which aren't close to uniform prefer <method-X> over uniform grids.

Yes... I was talking about functional languages...  Cranky
You mean you're talking about purely functional languages. Wink


Grin just because that wasn't enough, here is a quote from my post before:

With 'functional' people, I mean people who write in purely functional languages.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
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.

PocketCrafter7 (14 views)
2014-11-28 16:25:35

PocketCrafter7 (9 views)
2014-11-28 16:25:09

PocketCrafter7 (10 views)
2014-11-28 16:24:29

toopeicgaming1999 (76 views)
2014-11-26 15:22:04

toopeicgaming1999 (67 views)
2014-11-26 15:20:36

toopeicgaming1999 (16 views)
2014-11-26 15:20:08

SHC (30 views)
2014-11-25 12:00:59

SHC (28 views)
2014-11-25 11:53:45

Norakomi (32 views)
2014-11-25 11:26:43

Gibbo3771 (28 views)
2014-11-24 19:59:16
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!