Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes 		Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Java-Gaming.org > Game Development > Performance Tuning > Quadtree for moving objects
Pages: [1] 2
  Print  
  Quadtree for moving objects  (Read 10076 times)
0 Members and 3 Guests are viewing this topic.
Offline Phear

JGO n00b
*

Posts: 17
« on: 2009-07-16 05:11:57 »
This is my first Quadtree implementation and I'm not too impressed with it Sad

I started out because I wanted to speed up my Boids application (http://www.red3d.com/cwr/boids/).
1) Boids move around
2) Boids adapt their movement based on their closest neigbours

Without any form of spatial organisation I had a O(n^2) complexity for each update

Enter the StaticQuadtree...

My StaticQuadtree generates all lower levels of the tree on instantiation.
A StaticQuadtree with 1 level is basically the same as my original Vector.
After some performance tests I noticed that generating more than 5 levels starts to decrease performance. Especially when removing Boids from the Quadtree when they move and when searching in an area that contains several sub levels.

Is that a normal number of levels for a Quadtree, or can this code be improved by multitudes after a few simple optimizations? Smiley

Also, am I correct in asuming that I have to remove and re-add all boids during update?
Wouldn't it be easier (quicker even) to regenerate the Quadtree before each update?

My first 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  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
import java.util.Collection;
import java.util.Vector;

public class StaticQuadtree implements Quadtree {
   private final static int DEFAULT_LEVELS = 5;
   private final Collection<Entity> entities = new Vector<Entity>();
   private final Node head;

   public StaticQuadtree() {
      this(DEFAULT_LEVELS);
   }
   public StaticQuadtree(int levels) {
      if (levels < 0) throw new IllegalArgumentException();
      head = new Node(levels, new BoundingBox(-256, -256, 256, 256));
   }

   @Override
   public synchronized int size() {
      return entities.size();
   }
   @Override
   public synchronized Collection<Entity> get() {
      return new Vector<Entity>(entities);
   }
   @Override
   public synchronized void get(BoundingBox bb, Collection<Entity> result) {
      head.get(bb, result);
   }
   @Override
   public synchronized void add(Entity entity) {
      if (entities.contains(entity)) throw new RuntimeException();

      entities.add(entity);
      head.add(entity);
   }
   @Override
   public synchronized void remove(Entity entity) {
      if (!entities.contains(entity)) throw new RuntimeException();

      entities.remove(entity);
      head.remove(entity);
   }

   @Override
   public String toString() {
      return "[QT "+ head +"]";
   }

   private final class Node {
      private final int level;
      private final BoundingBox bb;
      private final Collection<Entity> entities;
      private final Node minmin, minmax, maxmin, maxmax;

      public Node(final int level, BoundingBox bb) {
         if (level < 0) throw new IllegalArgumentException();
         this.level = level;
         this.bb = bb;

         if (level > 0) {
            entities = null;
            final double dx = (bb.maxX - bb.minX)/2;
            final double dy = (bb.maxY - bb.minY)/2;
            minmin = new Node(level-1, new BoundingBox(bb.minX,    bb.minY,    bb.maxX-dx, bb.maxY-dy));
            minmax = new Node(level-1, new BoundingBox(bb.minX,    bb.minY+dy, bb.maxX-dx, bb.maxY));
            maxmin = new Node(level-1, new BoundingBox(bb.minX+dx, bb.minY,    bb.maxX,    bb.maxY-dy));
            maxmax = new Node(level-1, new BoundingBox(bb.minX+dx, bb.minY+dy, bb.maxX,    bb.maxY));
         } else {
            entities = new Vector<Entity>();
            minmin = null;
            minmax = null;
            maxmin = null;
            maxmax = null;
         }
      }

      public synchronized int size() {
         if (level == 0) {
            return entities.size();
         }
         int sum = 0;
         sum += minmin.size();
         sum += minmax.size();
         sum += maxmin.size();
         sum += maxmax.size();
         return sum;
      }
      public synchronized void get(Collection<Entity> result) {
         if (level == 0) {
            result.addAll(entities);
         } else {
            minmin.get(result);
            minmax.get(result);
            maxmin.get(result);
            maxmax.get(result);
         }
      }
      public synchronized void get(BoundingBox bb, Collection<Entity> result) {
         if (!this.bb.intersects(bb)) throw new RuntimeException();

         if (level == 0) {
            for (Entity entity : entities) {
               if (bb.contains(entity.pos)) {
                  result.add(entity);
               }
            }
         } else {
            if (minmin.bb.intersects(bb)) minmin.get(bb, result);
            if (minmax.bb.intersects(bb)) minmax.get(bb, result);
            if (maxmin.bb.intersects(bb)) maxmin.get(bb, result);
            if (maxmax.bb.intersects(bb)) maxmax.get(bb, result);
         }
      }
      public synchronized void add(Entity entity) {
         if (!this.bb.contains(entity.pos)) throw new RuntimeException();

         if (level == 0) {
            entities.add(entity);
         } else {
            if (minmin.bb.contains(entity.pos)) minmin.add(entity);
            if (minmax.bb.contains(entity.pos)) minmax.add(entity);
            if (maxmin.bb.contains(entity.pos)) maxmin.add(entity);
            if (maxmax.bb.contains(entity.pos)) maxmax.add(entity);
         }
      }
      public synchronized void remove(Entity entity) {
         if (!this.bb.contains(entity.pos)) throw new RuntimeException();

         if (level == 0) {
            entities.remove(entity);
         } else {
            if (minmin.bb.contains(entity.pos)) minmin.remove(entity);
            if (minmax.bb.contains(entity.pos)) minmax.remove(entity);
            if (maxmin.bb.contains(entity.pos)) maxmin.remove(entity);
            if (maxmax.bb.contains(entity.pos)) maxmax.remove(entity);
         }
      }

      @Override
      public String toString() {
         StringBuffer sb = new StringBuffer();
         if (entities != null) sb.append(entities);
         if (minmin != null) sb.append(minmin);
         if (minmax != null) sb.append(minmax);
         if (maxmin != null) sb.append(maxmin);
         if (maxmax != null) sb.append(maxmax);
         return "[Node "+ sb.toString() +"]";
      }
   }
}

final class Entity {
   public Point pos;
   public Point vel;

   public Entity(double x, double y) {
      this.pos = new Point(x, y);
      this.vel = new Point(0, 0);
   }

   @Override
   public String toString() {
      return "[Entity "+ pos.x +":"+ pos.y +"]";
   }
}

final class Point {
   public final double x, y;

   public Point(double x, double y) {
      this.x = x;
      this.y = y;
   }
}

final class BoundingBox {
   public final double minX, minY;
   public final double maxX, maxY;

   public BoundingBox(double minX, double minY, double maxX, double maxY) {
      if (minX >= maxX) throw new IllegalArgumentException();
      if (minY >= maxY) throw new IllegalArgumentException();

      this.minX = minX;
      this.minY = minY;
      this.maxX = maxX;
      this.maxY = maxY;
   }

   public boolean contains(double x, double y) {
      return (minX < x && x <= maxX &&
            minY < y && y <= maxY);
   }
   public boolean contains(Point that) {
      return contains(that.x, that.y);
   }
   public boolean intersects(BoundingBox that) {
      return (minX < that.maxX && that.minX <= maxX &&
            minY < that.maxY && that.minY <= maxY);
   }
}


Stay tuned for my DynamicQuadtree update... Smiley
Offline Orangy Tang

JGO Kernel
*****

Posts: 2960
Medals: 37


Monkey for a head
« Reply #1 on: 2009-07-16 06:11:44 »
Quote from: Phear on 2009-07-16 05:11:57
Also, am I correct in asuming that I have to remove and re-add all boids during update?
Wouldn't it be easier (quicker even) to regenerate the Quadtree before each update?

Those both sound like bad ideas to me. I'd suggest you update the quad tree incrementally - when an object moves first check if it's still within the same node, if it is then you can leave it where it is. If it's changed then you can search back up the tree until you find a node that does fit, then go down again to find the leaf node to insert it into. For the typical case where an object crosses a boundary you'll only have to search a few nodes rather than doing a complete insertion.
[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Phear

JGO n00b
*

Posts: 17
« Reply #2 on: 2009-07-16 07:53:53 »
Because my Boids fly in flocks and doesn't spread out evenly I think an evenly distributed Quadtree would be a waste.

Enter the DynamicQuadtree:

My DynamicQuadtree is in many ways identical to the StaticQuadtree. However it uses lazy-load to generate the lower layers. A new layer is generated when more then a specified number of Entities has been added to a Node.

Many things improved directly:
+ Inital creation of a Quadtree is now very quick
+ Searching in an empty tree is now much quicker
However:
- Add and remove operations are basically unaffected Sad
64k Entities take ~20 sec to add and ~10sek to remove

Can anyone direct me in the way to improve this?
Are there more parameters than bucket size and tree depth?

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  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
import java.util.Collection;
import java.util.Vector;

public class DynamicQuadtree implements Quadtree {
   private final static int DEFAULT_SPLIT_SIZE = 5;
   private final static int DEFAULT_LEVELS = 5;
   private final Collection<Entity> entities = new Vector<Entity>();
   private final Node head;

   public DynamicQuadtree() {
      this(DEFAULT_SPLIT_SIZE, DEFAULT_LEVELS);
   }
   public DynamicQuadtree(int splitSize, int levels) {
      if (splitSize < 1) throw new IllegalArgumentException();
      if (levels < 0) throw new IllegalArgumentException();
      this.head = new Node(splitSize, levels, new BoundingBox(-256, -256, 256, 256));
   }

   @Override
   public synchronized int size() {
      return head.size();
   }
   @Override
   public synchronized Collection<Entity> get() {
      return new Vector<Entity>(entities);
   }
   @Override
   public synchronized void get(BoundingBox bb, Collection<Entity> result) {
      head.get(bb, result);
   }
   @Override
   public synchronized void add(Entity entity) {
      if (entities.contains(entity)) throw new RuntimeException();

      entities.add(entity);
      head.add(entity);
   }
   @Override
   public synchronized void remove(Entity entity) {
      if (!entities.contains(entity)) throw new RuntimeException();

      entities.remove(entity);
      head.remove(entity);
   }

   @Override
   public String toString() {
      return "[QT "+ head +"]";
   }

   private final class Node {
      private final int splitSize;
      private final int joinSize;
      private final int level;
      private final BoundingBox bb;
      private Collection<Entity> entities;
      private Node minmin, minmax, maxmin, maxmax;

      public Node(int splitSize, int level, BoundingBox bb) {
         if (level < 0) throw new IllegalArgumentException();

         this.splitSize = splitSize;
         this.joinSize = splitSize*2;
         this.level = level;
         this.bb = bb;
         this.entities = new Vector<Entity>();
      }

      public int size() {
         if (entities != null) {
            return entities.size();
         } else { // is split
            int sum = 0;
            sum += minmin.size();
            sum += minmax.size();
            sum += maxmin.size();
            sum += maxmax.size();
            return sum;
         }
      }
      public void get(Collection<Entity> result) {
         if (entities != null) {
            result.addAll(entities);
         } else { // is split
            minmin.get(result);
            minmax.get(result);
            maxmin.get(result);
            maxmax.get(result);
         }
      }
      public void get(BoundingBox bb, Collection<Entity> result) {
         if (!this.bb.intersects(bb)) throw new RuntimeException();

         if (entities != null) {
            for (Entity entity : entities) {
               if (bb.contains(entity.pos)) result.add(entity);
            }
         } else { // is split
            if (minmin.bb.intersects(bb)) minmin.get(bb, result);
            if (minmax.bb.intersects(bb)) minmax.get(bb, result);
            if (maxmin.bb.intersects(bb)) maxmin.get(bb, result);
            if (maxmax.bb.intersects(bb)) maxmax.get(bb, result);
         }
      }
      public void add(Entity entity) {
         if (!this.bb.contains(entity.pos)) throw new RuntimeException();

         if (entities != null) {
            entities.add(entity);

            if (entities.size() >= splitSize && level > 0) { // split
               final Collection<Entity> tmpEntities = new Vector<Entity>(entities);

               entities = null;
               final double dx = (bb.maxX - bb.minX)/2;
               final double dy = (bb.maxY - bb.minY)/2;
               minmin = new Node(splitSize, level-1, new BoundingBox(bb.minX, bb.minY, bb.maxX-dx, bb.maxY-dy));
               minmax = new Node(splitSize, level-1, new BoundingBox(bb.minX, bb.minY+dy, bb.maxX-dx, bb.maxY));
               maxmin = new Node(splitSize, level-1, new BoundingBox(bb.minX+dx, bb.minY, bb.maxX, bb.maxY-dy));
               maxmax = new Node(splitSize, level-1, new BoundingBox(bb.minX+dx, bb.minY+dy, bb.maxX, bb.maxY));

               for (Entity tmpEntity : tmpEntities) {
                  add(tmpEntity);
               }
            }
         } else { // is split
            if (minmin.bb.contains(entity.pos)) minmin.add(entity);
            if (minmax.bb.contains(entity.pos)) minmax.add(entity);
            if (maxmin.bb.contains(entity.pos)) maxmin.add(entity);
            if (maxmax.bb.contains(entity.pos)) maxmax.add(entity);
         }
      }
      public void remove(Entity entity) {
         if (!this.bb.contains(entity.pos)) throw new RuntimeException();

         if (entities != null) {
            entities.remove(entity);
         } else { // is split
            if (minmin.bb.contains(entity.pos)) minmin.remove(entity);
            if (minmax.bb.contains(entity.pos)) minmax.remove(entity);
            if (maxmin.bb.contains(entity.pos)) maxmin.remove(entity);
            if (maxmax.bb.contains(entity.pos)) maxmax.remove(entity);

            int sum = 0;
            sum += minmin.size();
            sum += minmax.size();
            sum += maxmin.size();
            sum += maxmax.size();
            if (sum < joinSize) {
               entities = new Vector<Entity>();
               minmin.get(entities); minmin = null;
               minmax.get(entities); minmax = null;
               maxmin.get(entities); maxmin = null;
               maxmax.get(entities); maxmax = null;
            }
         }
      }

      public String toString() {
         StringBuffer sb = new StringBuffer();
         if (entities != null) sb.append(entities);
         if (minmin != null) sb.append(minmin);
         if (minmax != null) sb.append(minmax);
         if (maxmin != null) sb.append(maxmin);
         if (maxmax != null) sb.append(maxmax);
         return "[Node "+ sb.toString() +"]";
      }
   }
}
Games published by our own members! Go get 'em!
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #3 on: 2009-07-16 08:09:43 »
Quote from: Phear on 2009-07-16 07:53:53
Because my Boids fly in flocks and doesn't spread out evenly I think an evenly distributed Quadtree would be a waste.

Not sure what you mean by "evenly distributed", but the whole point of a quadtree is to localize queries.  Skimming your code, it looks way over complex with lots of redundent data.
Offline Phear

JGO n00b
*

Posts: 17
« Reply #4 on: 2009-07-16 08:20:40 »
Quote from: Roquen on 2009-07-16 08:09:43
Not sure what you mean by "evenly distributed", but the whole point of a quadtree is to localize queries.  Skimming your code, it looks way over complex with lots of redundent data.

I tried to say that if most of my Boids fly around in the top right corner. It would be better to have a high resolution in that corner and a low resolution in the other corners. No need to generate the nodes where there are no Boids.
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #5 on: 2009-07-16 08:40:33 »
Ah! But that's the whole point.  Otherwise you just have a 2D array with an overly complex interface (and memory requirements).  Surely there is some existing Java code you could look at.
Offline princec
« League of Dukes »

JGO Kernel
*****

Posts: 8089
Medals: 96


Eh? Who? What? ... Me?
« Reply #6 on: 2009-07-16 09:03:31 »
Quote from: Phear on 2009-07-16 08:20:40
I tried to say that if most of my Boids fly around in the top right corner. It would be better to have a high resolution in that corner and a low resolution in the other corners. No need to generate the nodes where there are no Boids.

That is exactly how a quadtree normally works - if you rebuild the quadtree from scratch every frame based on the data you're attempting to classify, which is all you have to do. So do that. You'll then find that the quadtree nodes end up being quite a lot of garbage, so you might want to implement a quadtree node factory that uses a pool.

Cas Smiley
Play Revenge of the Titans - Play Titan Attacks - Play Droid Assault
Offline Phear

JGO n00b
*

Posts: 17
« Reply #7 on: 2009-07-16 09:18:59 »
Quote from: Roquen on 2009-07-16 08:40:33
Ah! But that's the whole point.  Otherwise you just have a 2D array with an overly complex interface (and memory requirements).  Surely there is some existing Java code you could look at.

How did my "on-demand tree" become a 2D array?
Exactly why is there a point in having n levels of populated Quadtree if the parent can handle the request?

Please try to be more specific about the parts that are "way over complex with lots of redundent data".
I've tried to write this as straightforward as possible so that others can read it and help me improve it.
Offline Phear

JGO n00b
*

Posts: 17
« Reply #8 on: 2009-07-16 09:30:07 »
Quote from: princec on 2009-07-16 09:03:31
That is exactly how a quadtree normally works - if you rebuild the quadtree from scratch every frame based on the data you're attempting to classify, which is all you have to do. So do that. You'll then find that the quadtree nodes end up being quite a lot of garbage, so you might want to implement a quadtree node factory that uses a pool.

Cas Smiley

This sounds like something that will help during move (remove/add).
Now I get odd profiling results. One of my tests (add 64k of Entities, remove them) generally executes in 30 sec. However every once in a while it takes almost a minute.
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #9 on: 2009-07-16 10:39:22 »
WRT: Being a 2D array that was in reference to "even distributed" not the code, I should have been more clear.

WRT: Being overcomplex. Examples: Nodes is taking on two rolls, that of an interior node and a leaf.  Since your only storing data in leaves the code and data size can be reduced by breaking in two.  'splitSize', 'joinSize' and 'bb' could be replaced by a reference to the tree and a chosen coordinate. (The extent is implicit from the overall size and the depth).  This should speed up construction time.
Games published by our own members! Go get 'em!
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #10 on: 2009-07-16 10:39:36 »
The reason your remove is slow, is that you remove from a Vector.

First you have to search the vector (on average you have to check 50% of the items), and them you have to remove the item (on average you have to shift 50% of the remaining items).

If you replace the Vector by a HashSet, you'd get far better results.

...adding will be a tad slower though...
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #11 on: 2009-07-16 11:00:22 »
Also, your code will gloriously fail when you add N items (where N >= splitSize) at the exact same location.

It will split until a StackOverflow occurs.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline princec
« League of Dukes »

JGO Kernel
*****

Posts: 8089
Medals: 96


Eh? Who? What? ... Me?
« Reply #12 on: 2009-07-16 11:03:04 »
In fact remove the check for contains() as well - it's not actually necessary for the correct implementation of the quadtree.

Cas Smiley
Play Revenge of the Titans - Play Titan Attacks - Play Droid Assault
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #13 on: 2009-07-16 11:47:04 »
Nah, it does a contains() on the *entity position*, which is a normal optimisation.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline Phear

JGO n00b
*

Posts: 17
« Reply #14 on: 2009-07-16 12:35:15 »
Quote from: Roquen on 2009-07-16 10:39:22
WRT: Being a 2D array that was in reference to "even distributed" not the code, I should have been more clear.

WRT: Being overcomplex. Examples: Nodes is taking on two rolls, that of an interior node and a leaf.  Since your only storing data in leaves the code and data size can be reduced by breaking in two.  'splitSize', 'joinSize' and 'bb' could be replaced by a reference to the tree and a chosen coordinate. (The extent is implicit from the overall size and the depth).  This should speed up construction time.

splitSize and joinSize are now moved to the Quadtree class. Still available to the inner class. Thanks! Smiley
I will try to change the BB class into a set of static methods that will work with the "level" and one point. Not sure how readable the code will be however...
Offline Phear

JGO n00b
*

Posts: 17
« Reply #15 on: 2009-07-16 12:51:07 »
Quote from: Riven on 2009-07-16 10:39:36
The reason your remove is slow, is that you remove from a Vector.

First you have to search the vector (on average you have to check 50% of the items), and them you have to remove the item (on average you have to shift 50% of the remaining items).

If you replace the Vector by a HashSet, you'd get far better results.

...adding will be a tad slower though...

Whoa!

After changing Vector to HashSet the add time was reduced from ~17sec to ~200ms
Remove time is reduced from ~13sec to ~4sec
Search times are approximately doubled

Odd... Smiley
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #16 on: 2009-07-16 15:34:00 »
Regarding the performance loss on 'search times'...

You can turn your QuadTree in two-state datastructure.


While adding/removing, use a HashSet.
Once everything has settled, copy all items in your HashSet into an ArrayList.
While searching, use the ArrayList.
Once you need to add/remove again, convert it to a HashSet again.

The conversion shouldn't be too much of a performance-drain. At least it is increasing in nearly linear time with more entities, while the savings are exponential.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline Phear

JGO n00b
*

Posts: 17
« Reply #17 on: 2009-07-22 07:57:58 »
Hi again,

I made a reference implementation of my Quadtree : FlatQuadtree. Basically a wrapper for a single HashSet.
The performance gain compared to my other Quadtrees doesn't seem to be as great as I had hoped. Sad

With FlatQuadtree: 150 Boids @ 60hz
With either Static/DynamicQuadtree: 190 Boids @ 60hz

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  
import java.util.Collection;
import java.util.HashSet;

public class FlatQuadtree implements Quadtree {
   private final Collection<Entity> boids = new HashSet<Entity>();

   @Override
   public void add(Entity entity) {
      boids.add(entity);
   }

   @Override
   public Collection<Entity> get() {
      final Collection<Entity> result = new HashSet<Entity>();
      get(result);
      return result;
   }

   @Override
   public void get(Collection<Entity> result) {
      result.addAll(boids);
   }

   @Override
   public Collection<Entity> get(BoundingSquare bs) {
      final Collection<Entity> result = new HashSet<Entity>();
      get(bs, result);
      return result;
   }

   @Override
   public void get(BoundingSquare bs, Collection<Entity> result) {
      for (Entity boid : boids) {
         if (bs.contains(boid.getPos())) {
            result.add(boid);
         }
      }
   }

   @Override
   public Collection<Entity> get(BoundingCircle bc) {
      final Collection<Entity> result = new HashSet<Entity>();
      get(bc, result);
      return result;
   }

   @Override
   public void get(BoundingCircle bc, Collection<Entity> result) {
      for (Entity boid : boids) {
         if (bc.contains(boid.getPos())) {
            result.add(boid);
         }
      }
   }

   @Override
   public void lock(boolean lock) {}

   @Override
   public int maxLevel() {
      return 1;
   }

   @Override
   public void moveDoit(Entity entity, Point pos) {
      throw new RuntimeException();
   }

   @Override
   public boolean moveTest(Entity entity, Point pos) {
      return true;
   }

   @Override
   public void remove(Entity entity) {
      boids.remove(entity);
   }

   @Override
   public int size() {
      return boids.size();
   }
}



I've also got a new question: Should it be possible for an object to be located in more than one BB?
Right now all objects are limited to one BB. The add method return after the 1st successful add operation.
But if I want to use Quadtrees for colission detection I assume that their location in the Quadtree should be based on their position *and* size and not just their position. Right?
Offline princec
« League of Dukes »

JGO Kernel
*****

Posts: 8089
Medals: 96


Eh? Who? What? ... Me?
« Reply #18 on: 2009-07-22 08:48:03 »
Right. The rule is:

For any object you attempt to add to the tree:
  If the quadtree node has child nodes:
    Offer the object to the child node. If it is accepted, you're done

  Otherwise, if there are no child nodes or none of the child nodes accept the object:
    If the object's bounds fits entirely within this node, add it to this node's list of contents (ie. accept the object)
    Otherwise, don't accept the object.

This means that objects with fall partially outside the absolute outer bounds of the quadtree will not be accepted into the quadtree at all and will need to be kept in a boundless master node, which should have an API like the quadtree, and should be the point of entry from the rest of your code.

Cas Smiley
 
Play Revenge of the Titans - Play Titan Attacks - Play Droid Assault
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #19 on: 2009-07-22 09:21:45 »

I'm gonna jump around.  First some high level choices:

(Should be noted that we're talking about region (equal subdivision) quad-trees...well at least I am)

A) Data only in leaf nodes
B) Data in any node

1) Data stored in single node (leaf or otherwise)
2) Data (potentially) stored in multiple.

A+1: Is only really reasonable if your maximum depth is restricted so you never need to visit more than 'n' siblings. So if you limit the depth such that the largest object will just fit within that leaf, you have to check up to 3 siblings. Of course any B generally requires some walking. I personally use A+2.

Logically I treat the universe as normalized on range [0,1] for both dimensions and only consider split values.  This way any node which is outside the universe will map to the leaf with the closest Manhattan distance. (Shrug)  There's no one right or wrong way to do this stuff and the best choice (when clear) will depend on a lot of details of exact system.
Offline ryanm
« League of Dukes »

JGO Strike Force
*****

Posts: 788
Medals: 4


Used to be bleb
« Reply #20 on: 2009-07-22 09:30:18 »
I'm going to go off on a tangent and ask: Is a quadtree even necessary?

Note: I'm assuming boids are points, or can be approximated as such.

Boids are apparently only interested in their immediate neighbours and so the query area is going to be fixed and pretty small. Drilling through layers of tree nodes to find out which leaves we should be looking at seems silly when we can directly address into a simple grid of linked lists.
This also gives you back fine-grained (non-power-of-two) control over the number of leaf boxes, so you can experiment with the size of the grid boxes and find the sweet-spot where the false-positive cost of large boxes balances the cost of examining lots of little (probably empty) boxes.

Happily, the degenerate case where all boids are clustered in one box is something that they are specifically trying to avoid.
Unhappily, you'll fall foul of the no-arrays-of-generic-collections annoyance.
Offline captain

JGO n00b
*

Posts: 5
« Reply #21 on: 2009-09-02 05:21:15 »
I have recently solved this in a situation where everything is 2d:

The best solution I've found is to combine 2d array of cells and a quadtree that perfectly matches the 2d grid so that each leaf node is also a cell of the 2d array. I will post code once I get back home after work.

The datastructure consists of:
- 2d array that contains cells containing the objects.
- A quadtree where each cell forms a leaf node.
(- A multimap which stores all the objects in iterable form by cell.)

Ideal requirements:
- Fast neighbor finding.
- Fast proximity finding.
- No wasted ascending or descending the tree (ideally only when inserting, removing objects or intersection tests).
- No going through empty cells.

Limitations:
- The game area width in cells must be a power of two.
- Only leaf nodes can contain objects.
- Each object is contained by only one cell even if it intersects multiple cells.
- All objects must be smaller than one cell.

The data structure has:
-addition O(Log n) if added from root node (vs O(n^2) of 2d grid), addition to a cell is O(1);
-remove O(Log n) if removed from a cell, O(n^2) otherwise;
-No ascending the tree when moving objects. In worst case if neighbors aren't found initialization time you have to ascend to root node and then descend back;
-No need to clear the tree and reinsert objects after each update;
-Fast proximity finding O(1) vs ascending and descending of quadtree or complicated initialization algorithms.

Further optimization:
-Holding all your game objects in a MultiMap where each cell index(j * size + i) works as a key to the objects eliminates the need to go through a 2d array to update empty cells.
-Using HashSets inside the cells instead of ArrayLists removes the need to copy or move memory when removing objects from leaf nodes (not sure if this happens).


1  
2  
3  
4  
       Node
    /    \    \ \
   /     |     |  \
Cell Cell Cell cell


--------

Quadtrees alone aren't very good for moving objects. A 2d grid isn't very good for inserting and removing objects at random places. Quadtree is good for deciding whether objects intersect, 2d grid isn't. I am using this for boid movement as well and so far it has been working great.

Comments? Improvements?
Offline Orangy Tang

JGO Kernel
*****

Posts: 2960
Medals: 37


Monkey for a head
« Reply #22 on: 2009-09-02 06:24:06 »
Quote from: captain on 2009-09-02 05:21:15
- Each object is contained by only one cell even if it intersects multiple cells.
- All objects must be smaller than one cell.
Ouch, those are pretty harsh limitations. You're going to be limiting your gameplay considerably with those. And if those limitations are acceptable then why bother with the quadtree bit at all? A simple 2d array which you index into by position would do the job just as well but with less overhead. IMHO you've violated one of the fundamental principles (nodes should *entirely* contain their children, otherwise hierarchical culling breaks down), at which point you've not got a proper quad tree. It's not surprising that you'd conclude that "quad trees" (or rather, your hacked approximation) are unsuitable for moving objects.

I'm also surprised that no-one has suggested sweep-and-prune yet. It handles the edge case that Phear was worred about (all objects bunching up in a single quad tree node), and is nicely parallisable too.
[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline captain

JGO n00b
*

Posts: 5
« Reply #23 on: 2009-09-02 08:50:54 »
First things first: with a any game you are going to end up with multiple data structures for multiple purposes once you start having performance problems. There isn't a one single solution that optimally satisfies all requirements set out by multiple different problems such as: collision detection, path finding, proximity finding and hierarchial culling.

Quote from: Orangy Tang on 2009-09-02 06:24:06
Ouch, those are pretty harsh limitations. You're going to be limiting your gameplay considerably with those. And if those limitations are acceptable then why bother with the quadtree bit at all?

Because quadtree essentially complements a 2d grid nicely. Why combine sweep and prune and a Quadtree? Because they work well together. I don't see how those limitations are going to effect the gameplay.

Quote
A simple 2d array which you index into by position would do the job just as well but with less overhead.

Still, in worst case you'd be going through the array in n^2. This would come to reality when doing intersection tests over large areas.

Quote
IMHO you've violated one of the fundamental principles (nodes should *entirely* contain their children, otherwise hierarchical culling breaks down), at which point you've not got a proper quad tree.

There's absolutely nothing wrong in restricting object ownership to a single node. Note that an object intersecting multiple leaf nodes *can* still be tested against more objects than the ones in the same leaf.

Quote
It's not surprising that you'd conclude that "quad trees" (or rather, your hacked approximation) are unsuitable for moving objects.

While I did not state that quadtrees are unsuitable for moving objects I firmly hold the opinion that quadtrees are not an optimal solution to collision detection of moving objects. Quadtrees have much better uses in storing, representing and manipulating static 2d geometry.

Quote
I'm also surprised that no-one has suggested sweep-and-prune yet. It handles the edge case that Phear was worred about (all objects bunching up in a single quad tree node), and is nicely parallisable too.

Yes, it is a good improvement over brute force testing in almost all situations. On gamedev.net Someone had taken the time to create performance comparisons in between 2d grid, quadtree and prune and sweep. Unfortunately I can't find this at the moment.
Offline Orangy Tang

JGO Kernel
*****

Posts: 2960
Medals: 37


Monkey for a head
« Reply #24 on: 2009-09-02 09:19:29 »
Quote from: captain on 2009-09-02 08:50:54
Because quadtree essentially complements a 2d grid nicely. Why combine sweep and prune and a Quadtree? Because they work well together. I don't see how those limitations are going to effect the gameplay.
Sooner or later you're going to want to have entities of substantially different sizes. The obvious example would be boss characters in most shooters or platformers. If you're going to impose such crude limitations then you don't need a quad tree. If you are going to want entities of grossly different sizes then your "quad tree" is useless.

Quote
Still, in worst case you'd be going through the array in n^2. This would come to reality when doing intersection tests over large areas.
No-one said anything about looping over the whole array.

Quote
There's absolutely nothing wrong in restricting object ownership to a single node. Note that an object intersecting multiple leaf nodes *can* still be tested against more objects than the ones in the same leaf.
Nothing wrong with it, but you're no longer doing a quad tree, you're doing a custom hacked solution which may or may not be more appropriate for a certain, constrained set of usage in your game. And yes, you can test against more object than in the current leaf, but you have to know in advance how many surrounding leafs around you to check - again you're imposing an arbitrary upper bound on the size of your entities.
[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline princec
« League of Dukes »

JGO Kernel
*****

Posts: 8089
Medals: 96


Eh? Who? What? ... Me?
« Reply #25 on: 2009-09-02 11:55:03 »
The simple quadtree solution is loads more elegant and very simple and theoretically as fast as possible with no constraints on position other than efficient collisions can only occur within the coordinate space defined by the root node. Why not stick with that?

Cas Smiley
Play Revenge of the Titans - Play Titan Attacks - Play Droid Assault
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #26 on: 2009-09-02 12:27:03 »
Quote from: princec on 2009-09-02 11:55:03
The simple quadtree solution is loads more elegant and very simple and theoretically as fast as possible with no constraints on position other than efficient collisions can only occur within the coordinate space defined by the root node. Why not stick with that?

Cas Smiley

Because it's not fastest.

Besides that, in your algorithm, a LOT of items will end up in the 'catch all' list -- for example: every item in the middle of the map would end up being rejected all the time. Also, the 'parents' will have way too many items, which could otherwise be put in half-cell-shifted-grids -- see below:

The obvious solution is to create another abstraction, with a translation of the 'grid' by half a cell size on each axis at each level (recursion depth). That way, if it fits the parent, but not entirely fits in any of its children, you can try the shifted cells, which have a high probability of accepting the item.

You'd have to leave the regular OO way of designing your tree. It should merely be a View on your grids for each level. Let's say your root-node has a (cell)size of 256.0f, the 4 children would have cellsizes of 128.0f, and would be positioned to exactly fit inside the parent. Every item that has its boundingbox intersecting the cell-boundaries would put in the parent (recursively). If you'd add another grid (at level 1 -- root is level 0) of 3x3 cells, shifted (-cell/2, -cell/2) you could catch all those edge-cases in the right level of your tree.

In the next level (#2) you'd have 4x4 cells with a dimension of 64.0f units. The 'shifted grid' would have 5x5 cells of 64.0f units, shifted (-32, -32) to (again) catch all edge-cases.

etc. etc. etc.

In the end, you have all items in their proper level / depth, instead of pushing them up the tree in edge-cases. This obviously yields in better performance, as you have less items in each node.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline princec
« League of Dukes »

JGO Kernel
*****

Posts: 8089
Medals: 96


Eh? Who? What? ... Me?
« Reply #27 on: 2009-09-02 12:55:04 »
Hm I suppose it may not be always the fastest. I do know about the boundary cases where things fall directly in the middle of a node boundary and end up right in the root node - but you have to generally assume that for 99.9% of the time not everything occupies this area. And indeed doesn't, because they collide and generally blow up Smiley

Cas Smiley
Play Revenge of the Titans - Play Titan Attacks - Play Droid Assault
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #28 on: 2009-09-02 13:06:32 »
The problem is not only that quite a few end up at the root node (not only the middle, but also the center axes) but for every level, this problem exists, causing the item to be pushed to the parent. So it's definitly not 0.1%, because when the cells get smaller, the 'boundingbox hitting center axes'-problem grows exponentially.

With my shifted grids, you approach 0.0% as there are no edge-cases, at all.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline princec
« League of Dukes »

JGO Kernel
*****

Posts: 8089
Medals: 96


Eh? Who? What? ... Me?
« Reply #29 on: 2009-09-02 18:16:16 »
Hm, seems to work just fine here though. For the simplicity I'd go for my solution every time Smiley

Cas Smiley
Play Revenge of the Titans - Play Titan Attacks - Play Droid Assault
Pages: [1] 2
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.15 seconds with 19 queries.