Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (542)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (606)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2]
  ignore  |  Print  
  Quadtree for moving objects  (Read 18362 times)
0 Members and 1 Guest are viewing this topic.
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 849
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #30 - Posted 2009-09-02 22:21:30 »

If it works and the performance is not a problem, don't change it. Premature optimisation is bad.

It just won't scale well, for culling zillions of items, like when you're rendering forests with millions of trees. Let's say you'd have 1% in your 'catch all' node, that would be 10K items. That will really grind your physics engine to a hold.

With 1000 items in the world that 1% is not going to affect performance noticably.

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

« JGO Spiffy Duke »


Medals: 439
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #31 - Posted 2009-09-02 23:16:08 »

Dead right Smiley

Cas Smiley

Offline captain

Junior Newbie





« Reply #32 - Posted 2009-09-03 09:51:42 »

Because of this thread I am planning on implementing some tests. I am also planning on releasing the source for everyone to see and review.

So far I am planning to test two collision strategies for each data structure:
-bruteforce (O(n^2) for reference)
-sweep and prune with circles or axis aligned boxes (with insertion sort for O(n), perhaps quicksort for O(n log n)

and the following cases of datastructures:
-No data structure at all
-2d grid
-Regular quadtree (create static quadtree to nth level and add objects accordingly)
-Dynamic quadtree (create static quadtree to nth level to avoid runtime allocation, add objects to nodes until the node is full. Once the node is full, redistribute the objects into child nodes)

I'll impose no similar limitations as pointed out by Orangy Tang in my solution. This means that I probably can't squeeze in my "hackish approximation of Quadtree".

There is one major problem though: how do the advocates of the elegant and simple Quadtree approach handle moving objects especially now that one object may be in multiple nodes?

Do you:
 - simply remove the object when it has moved and reinsert it?
 - clear the whole tree and insert all of the objects again?
 - update the tree from within so that you only ascend only the needed amount and then add the node? How are objects that reside in multiple nodes handled?
 - calculate edge and vertex neighbors initialization time, store references to them and update the node that way? Again, how are objects that reside in multiple nodes handled?


Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

« JGO Spiffy Duke »


Medals: 439
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #33 - Posted 2009-09-03 10:13:53 »

My objects only ever live in one node, and as such, they have a reference to the node that they are currently in, to enable me to very efficiently remove them from the node when they are being moved. I then simply add them back into the quadtree. Seems to work fine, especially as my objects are well distributed spatially, so I don't run into the case where lots of them end up in bigger parent nodes than necessary, and it's very fast.

Cas Smiley

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #34 - Posted 2009-09-03 10:28:32 »

Sounds very interesting. Go on - write it with a generic QuadTree interface so we can poke our own algorithms into it so they can shoot it out. Smiley I wouldn't mind writing a loose quad tree variant and seeing how it compares.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline captain

Junior Newbie





« Reply #35 - Posted 2009-09-03 18:58:15 »

Sounds very interesting. Go on - write it with a generic QuadTree interface so we can poke our own algorithms into it so they can shoot it out. Smiley I wouldn't mind writing a loose quad tree variant and seeing how it compares.

I'll have to work on this during the weekend. I implemented bruteforce and prune and sweep collision strategies (the difference is 300 fps for 10000 objects in 20kx20k area as you may imagine). I didn't notice too big of a difference in between insertion sort and quicksort.

What do you want from a generic data structure interface?

Currently I have:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public interface ISpatialDataStructure {

   
   public void add(Entity entity);

   public void remove(Entity entity);
   
   public void collide();
   
   public void update(float dt);
   
   public void draw(Graphics graphics);
   
}


This gives tons of options to anyone developing a data structure. Is there anything else that might be needed?

I'll probably add an intersection query function for a Rectangle (think of FPS style selection) that returns list of objects it intersects. I am going to use Slick for the testbed so I hope that's okay for everyone.
Offline olli-pekka

Senior Newbie


Medals: 1



« Reply #36 - Posted 2009-09-07 18:21:13 »

Hello (I was previously captain, but decided to change my user name to what is use normally)

I had a few extra hours during the weekend so I put together a little testbed.

So far I have implementations for
 - Prune and Sweep Strategy
 - Regular Quadtree

Regular quadtree introduces a ton of overhead at the moment because objects are re-added to it every single time. For some reason I have a gut feeling that updating objects from the leaf node they are in is not going to be efficient since you don't know for certain where else the object also resides.

Any opinions on the implementation? I'd like to see more data structures submitted by others. The code should be free to use in open source compatible way (none of the algorithms are particularly hard), but I'd like to see any improvements made to existing implementations also if someone decides to submit their own implementation.

www.students.tut.fi/~valton22/CollisionTest.zip

Keys:
- Mouse wheel zooms.
- F1 toggles debug information.
- Keys move the view.
Offline Jono
« Reply #37 - Posted 2009-09-08 06:16:14 »

Are there some missing libraries? Does this require Slick?

1  
2  
$ java org.game.CollisionTest 
Exception in thread "main" java.lang.NoClassDefFoundError: org/newdawn/slick/BasicGame
Offline olli-pekka

Senior Newbie


Medals: 1



« Reply #38 - Posted 2009-09-08 08:00:09 »

Yes, it requires Slick. I used Slick for convenience, since I had some existing code related to it.

I wouldn't entirely ignore this because of Slick as it is quick to install and more than adequate for this kind of situation.
Offline olli-pekka

Senior Newbie


Medals: 1



« Reply #39 - Posted 2009-09-08 18:46:30 »

I implemented LooseGrid as featured in N (http://www.metanetsoftware.com/technique/tutorialB.html#section3)

You can take the grid into use by changing the initialization of the data structure in CollisionTest.java to:
1  
ISpatialDataStructure dataStructure = new LooseGrid(200, 200, 100, 100);


and adding the file "LooseGrid.java" with following contents:

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  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
package org.game.collision.datastructures;

import java.util.ArrayList;


public class LooseGrid implements ISpatialDataStructure {

   float cellWidth = 0;
   float cellHeight = 0;
   
   private class Cell {
     
     
      Rectangle bounds = new Rectangle(0, 0, 0, 0);
     
      ArrayList<Entity> objects = new ArrayList<Entity>();
     
     
      public Cell(int i, int j) {
         
         float xOffset = sizeX / 2 * cellWidth;
         float yOffset = sizeY / 2 * cellHeight;
         
         bounds.setBounds( -xOffset + i * cellWidth, -yOffset + j * cellWidth, cellWidth, cellHeight);
      }
     
      public void add(Entity entity) {
         objects.add(entity);
      }
     
      public void remove(Entity entity) {
         objects.remove(entity);
      }
     
      public void draw(Graphics graphics) {
         
         if(debug) {
            graphics.setColor(Color.yellow);
            graphics.draw(bounds);
         }
         
         for (Entity entity : objects) {
            entity.draw(graphics);
         }
         
      }
     
      public int getNumObjects() {
         return objects.size();
      }
     
     
     
      public void collide(ArrayList<Collision> collisions) {
         
         for (Entity entity : objects) {
            float xWorldOffset = sizeX / 2 * cellWidth;
            float yWorldOffset = sizeY / 2 * cellHeight;

            int x = (int)((xWorldOffset + entity.getPositionX()) / cellWidth);
            int y = (int)((yWorldOffset + entity.getPositionY()) / cellHeight);  
                 

            for(int i = -1; i <= 1; i++ ) {
               
               int xOffset = x + i;
               
               if(xOffset < 0 || xOffset >= sizeX) break;

               for(int j = -1; j <= 1; j++ ) {
                  int yOffset = y + j;

                 
                  if(yOffset < 0 || yOffset >= sizeY) break;
                 
                     ArrayList<Entity> cellObjects = cells[xOffset][yOffset].objects;
                     
                     for (Entity foreign : cellObjects) {
                       
                        if(entity == foreign) continue;
                        if(entity.intersects(foreign)) {
                           
                           collisions.add(new Collision(entity, foreign));
                        }
                     }

               }        
            }
         }
         
      }
     
      public boolean intersects(Entity entity) {
         return bounds.intersects(entity.getShape());
      }
     
   }

   
   boolean debug = false;
   
   Cell[][] cells = null;

   private int sizeX = 0;
   private int sizeY = 0;
   
   ArrayList<Entity> objects = new ArrayList<Entity>();
   
   public LooseGrid(int sizeX, int sizeY, float cellWidth, float cellHeight, ICollisionStrategy collisionStrategy) {

      this.sizeX = sizeX;
      this.sizeY = sizeY;
     
      cells = new Cell[sizeX][sizeY];
     
      this.cellWidth = cellWidth;
      this.cellHeight = cellHeight;
     
      for(int i = 0; i < cells.length; i++) {
         for(int j = 0; j < cells[i].length; j++) {
            cells[i][j] = new Cell(i, j);
         }
      }  
   }
   
   
   @Override
   public void add(org.game.Entity entity) {
     
      this.objects.add(entity);
      addToCells(entity);
     
   }

   @Override
   public void collide(ArrayList<Collision> collisions) {

      for(int i = 0; i < cells.length; i++) {
         for(int j = 0; j < cells[i].length; j++) {
            if(cells[i][j].getNumObjects() > 0) {
               cells[i][j].collide(collisions);              
            }
         }
      }
     
   }

   @Override
   public void draw(Graphics graphics) {
     
      graphics.setColor(Color.blue);
      graphics.drawRect(-(sizeX/2) * cellWidth, -(sizeY/2) * cellHeight, sizeX*cellWidth, sizeY*cellWidth);
     
      for(int i = 0; i < cells.length; i++) {
         for(int j = 0; j < cells[i].length; j++) {
            if(cells[i][j].getNumObjects() > 0) {
               cells[i][j].draw(graphics);              
            }
         }
      }
     
     
   }

   @Override
   public String getInfo() {
      return "Loose grid data structure by Olli-Pekka";
   }

   @Override
   public boolean isDebugRenderMode() {
      return debug;
   }

   @Override
   public void remove(org.game.Entity entity) {
      objects.remove(entity);
      removeFromCells(entity);
   }

   @Override
   public void setDebugRenderMode(boolean debug) {
      this.debug = debug;
     
   }

   @Override
   public void update(float dt) {
      for (Entity entity : objects) {
         removeFromCell(entity);
         entity.update(dt);  
         addToCell(entity);
      }
     
   }

   @Override
   public float getHeight() {
      return sizeY * cellHeight;
   }

   @Override
   public float getWidth() {
      return sizeX * cellWidth;
   }
   

   
   private void addToCell(Entity entity) {

      float xOffset = sizeX / 2 * cellWidth;
      float yOffset = sizeY / 2 * cellHeight;

      int x = (int)((xOffset + entity.getPositionX()) / cellWidth);
      int y = (int)((yOffset + entity.getPositionY()) / cellHeight);
     
      cells[x][y].add(entity);
         
   
     
   }
   
   
   private void removeFromCell(Entity entity) {
     
      float xOffset = sizeX / 2 * cellWidth;
      float yOffset = sizeY / 2 * cellHeight;

      int x = (int)((xOffset + entity.getPositionX()) / cellWidth);
      int y = (int)((yOffset + entity.getPositionY()) / cellHeight);
     
      cells[x][y].remove(entity);
         
   }
   
   
   
}


It would be possible to make this better by incoporating prune and sweep. This would be done by changing the addToCell and removeFromCell functions to only remove and add the object if it doesn't intersect with the square. This way the order of the objects is preserved for insertion sort. Furthermore one has to change the sorting algorithms so that they sort the other objects and not the tested object.

Anyone up for Loose Quadtree or improving my Regular Quadtree?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jono
« Reply #40 - Posted 2009-09-08 22:53:54 »

Unfortunately my internet connection is incredibly slow right now (stupid data caps). I'll get the slick libraries in a few days when I'm back up and running properly again. Hopefully I'll find time next week to have a play with some implementations.  Smiley

A couple of thoughts though: can the drawing of Entities be moved out of the datastructure? Perhaps there could be an method to get an Iterator instead which can be used externally to draw them. If debug information needs to be included then this could be provided by the datastructure as a String, or some predefined Debug class.

As a side note, your life might have been easier with sweep and prune if you'd just made a Comparitor and used standard Collections/Arrays sort methods. I believe those methods use quicksort on large arrays, and move to insertion sort once partitions are small enough to not warrant the overhead.
Offline Jono
« Reply #41 - Posted 2009-09-11 02:58:31 »

I've downloaded slick and run the test. I'm not sure of the value of the visualisation though, since once I raise the number of entities to 10k it drops to under 1 fps (it's rendering about once every 15 updates - each timed update and render takes less than 100ms).

With 1k or fewer entities any naive implementation will be fine (say, <1ms for updates and collision detection), so the visualisation doesn't seem all that useful. Here's a test class "CollisionTest2" that drops any graphical output - still using your existing interfaces apart from one extra method in ISpatialDataStructure:
1  
public void clear();


I prints the mean and standard deviation of 50 update+collide calls. Your baseline implementations give:

Reference datastructure using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
1000 entities takes 192ms +/- 109.10838878372223

Reference datastructure using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
10000 entities takes 4909ms +/- 244.99901555071327

Reference datastructure using sweep and prune strategy(insertion sort) by Olli-Pekka Valtonen
1000 entities takes 152ms +/- 56.00231144306528

Regular Quadtree using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
1000 entities takes 28860ms +/- 677.3654851916602


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  
package org.game;
import org.game.collision.Collision;

import org.game.collision.datastructures.*;

import org.game.collision.strategies.*;

import org.game.collision.strategies.SweepAndPruneStrategy.SortingAlgorithm;

import java.util.Random;
import java.util.ArrayList;

public class CollisionTest2{
   public static void test(ISpatialDataStructure dataStructure, int entityCount){      
      Entity[] entities = new Entity[entityCount];
      ArrayList<Collision> collisions = new ArrayList<Collision>();
      Random random = new Random();

      float maxWidth = dataStructure.getWidth();
      float maxHeight = dataStructure.getHeight();


      //run 20x50 test updates
      int runs = 20;
      int updatesPerRun = 50;

      long[] times = new long[runs];
      long mean = 0;
      for(int i = 0; i < runs; i++){
         dataStructure.clear();
         //create the entities
         for(int j = 0; j < entityCount; j++) {

            float radius = 10 + random.nextFloat() * 90f;

            float x = (-dataStructure.getWidth() + radius) / 2 + random.nextFloat() * (dataStructure.getWidth() - 2*radius);

            float y = (-dataStructure.getHeight() + radius) / 2 + random.nextFloat() * (dataStructure.getHeight() - 2*radius);

            x = Math.max(x,-maxWidth/2);

            x = Math.min(x,maxWidth/2);

            y = Math.max(x,-maxHeight/2);

            y = Math.min(x,maxHeight/2);

         

            float velX = random.nextFloat() * 10;

            float velY = random.nextFloat() * 10;

         

            Entity entity = new Entity(dataStructure, x, y, velX, velY, radius);

            entities[j] = entity;

            dataStructure.add(entity);
         }
         //do a run
         long startTime = System.nanoTime();        
         for(int j = 0; j < updatesPerRun; j++){
            dataStructure.update(10);
            dataStructure.collide(collisions);
            collisions.clear();
         }
         times[i] = System.nanoTime()-startTime;
         mean += times[i];
         if((i & 1) == 0){
            System.out.print(".");
            System.out.flush();
         }
      }
      System.out.println("\n"+dataStructure.getInfo());
      mean /= runs;
      long variance = 0;
      for(int i = 0; i < runs; i++)
         variance += (mean-times[i])*(mean-times[i]);
      variance /= runs;
      double standardDeviation = Math.sqrt(variance);
      System.out.println(entityCount+" entities takes "+(mean/1000000)+"ms +/- "+(standardDeviation/1000000));
   }

   public static void main(String[] args){
      int width = 20000;
      int height = 20000;
      //ISpatialDataStructure dataStructure = new ReferenceDataStructure(width, height,new BruteforceStrategy());

      ISpatialDataStructure dataStructure = new ReferenceDataStructure(width, height, new SweepAndPruneStrategy(SortingAlgorithm.InsertionSort));

      //ISpatialDataStructure dataStructure = new RegularQuadtree(width, height, 7, new SweepAndPruneStrategy(SortingAlgorithm.Quicksort));

      test(dataStructure,1000);
   }
}


Offline princec

« JGO Spiffy Duke »


Medals: 439
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #42 - Posted 2009-09-11 10:17:19 »

The perils of microbenchmarks! You're saying a regular quadtree approach to collision detection takes 28 seconds for 50 updates and just 1,000 entities? The whole reason I switched to quadtrees for my game "engine" is that I needed to do about 2,000 entities in a millisecond!

Cas Smiley

Offline olli-pekka

Senior Newbie


Medals: 1



« Reply #43 - Posted 2009-09-11 16:14:24 »

The perils of microbenchmarks! You're saying a regular quadtree approach to collision detection takes 28 seconds for 50 updates and just 1,000 entities? The whole reason I switched to quadtrees for my game "engine" is that I needed to do about 2,000 entities in a millisecond!

Cas Smiley

The beauty of microbenchmarks is the fact that if you don't show it, it didn't happen Smiley
Offline Jono
« Reply #44 - Posted 2009-09-11 20:54:31 »

Quote
The perils of microbenchmarks!
I wouldn't call these micro-benchmarks, since they create 20 complete situations and run them for 50 iterations. This is a benchmark for roughly uniformly distributed, slowly moving objects in an area 200 times their maximum radius.

I think I didn't make the quad tree's extra "clear()" method properly (realised after going to bed last night). I'll check that and repost its time.

Edit: Ok, the correct timing is:
Regular Quadtree using sweep and prune strategy(quicksort) by Olli-Pekka Valtonen
1000 entities takes 2700ms +/- 271.007926407224

Cas, we're only saying that that implementation takes that long. If you looked at the code you'd see it was completely unoptimised (lots of unnecessary method calls), not to mention the fact that the tree gets rebuilt from scratch each update. As far as I can tell it was just supposed to be a baseline.

I added a print out of the average number of collisions. That quad tree implementation gives double the number of collisions as sweep and prune - so I'm guessing there's also a bug in there somewhere.

Finally, when using a sort method for sweep and prune that makes use of the fact that entities are mostly ordered it carves about 20% (at 10k entities) of that time off. Most of the remaining time is spent comparing entities so it looks like moving to some form of 2D sorting (like quad trees) would make sense at that point.
Offline princec

« JGO Spiffy Duke »


Medals: 439
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #45 - Posted 2009-09-12 08:32:00 »

50 iterations isn't up to much.. that's not even 1 second of game play! I'd run them for a lot longer, and also plonk things of varying sizes in there, and also have them move in a bit less of a random way perhaps, such as flocking.

Cas Smiley

Offline olli-pekka

Senior Newbie


Medals: 1



« Reply #46 - Posted 2009-09-15 05:42:54 »

I added a print out of the average number of collisions. That quad tree implementation gives double the number of collisions as sweep and prune - so I'm guessing there's also a bug in there somewhere.

There's definitely a bug in there. I'll attempt to fix this once I have more time. I am planning on extending the test bench to some queries: query against a circle (point & radius) and a rectangle, since those are pretty important in my game.
Offline Mene

Junior Newbie





« Reply #47 - Posted 2009-10-26 14:59:17 »

Hi, I was playing around a bit with this matter the other day and I found "kinetic data structures" to be very interesting for something like this. I'm short on time right now, but as a brief explanation: For each entry calculate the distance to the border of the quadtree node it's in. Then from the distance and the (maximal) movement speed calculate when the next update might be possible. Simulate on and just check the time if there's any need to update. If no update is required you're done, otherwise you just need to update a few entities (usually).
I have tried to implement it and it seems to work so far, but I neither have any benchmarks nor any real tests I made about stability etc. ...I just liked the idea Grin
What do you think about this approach?

Greetings,
Mene
Offline delt0r

JGO Knight


Medals: 30
Exp: 18 years


Computers can do that?


« Reply #48 - Posted 2009-11-06 15:52:39 »

I am perhaps coming into this a little late. But anyway, since i just finished my quad tree implementation for a RTS game I though I would give my experiences and suggestions. Feel free to ignore or otherwise pipe to /dev/null.

My current Quad tree is dynamic and gets 100 game frames per second with 20K units in a type of "boid" simulation. 60% of the CPU usage is updating the boids. Not the quad tree. Given that my target game frame per second is 5-10. This is basically done until it pops up on a profiler.

I use a few tricks that have already been suggested. The only "tricky" thing I do is keep track of adjacent nodes at the same level (or higher). Then when i call revalidate and I find a unit that has moved out of the current leaf, I can send it directly to the adjacent node (which may or may not be a leaf). This provides O(1) performance average case per unit thats moved,  and O(ln n) worst case.  rather than re add from the root that gives O(ln n) average case. It made quite a big difference and it means that increasing the time between game ticks does not *increase* the work needed per tick (too much).

Now i can do 2 fast queries on this structure. k nearest neighbor and "area queries". Both work in about O(ln n) time but the kNN has a larger over head that area queries.  Note that about O(ln n) time  here means we are ignoring the size of the returned result. This does affect performance.  I don't use these for collision detection, but rather "unit" sensors... ie what airplane is closest to me. 

For collision I do an "internal" area query. This still has expected performance O(ln n) for very large units. But average O(1) for smaller units. Since we expect large units to be rare and move slower than small units, so this works pretty good.

In practice I am getting less than a 5% cpu overhead for all these features and can burn CPU time on AI and rendering.

However I have not got to the "what is visible" bit yet. And I use massive vision distance for units, I hope that area queries are more than good enough (should be since I don't need to have a regular area).

Also just one other comment. Insertion sort has performance O(n^2) not O(n) as some post claimed. The best *any* sort can do is O(n) on a sorted list. Since it must take O(n) comparison just to show that a list is sorted. (merge sort and insertion sort gets O(n) for sorted lists. Basic Quick sort degenerates to O(n^2) ) .  You can only do better with radix sorts (not a comparison sort). In fact I did collision detection with a sweep whatever using radix sort. It was fast.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Jono
« Reply #49 - Posted 2009-11-06 20:12:24 »

Thanks for posting this - lots of good information and ideas  Smiley

Also just one other comment. Insertion sort has performance O(n^2) not O(n) as some post claimed. The best *any* sort can do is O(n) on a sorted list. Since it must take O(n) comparison just to show that a list is sorted. (merge sort and insertion sort gets O(n) for sorted lists. Basic Quick sort degenerates to O(n^2) ) .  You can only do better with radix sorts (not a comparison sort). In fact I did collision detection with a sweep whatever using radix sort. It was fast.
I think the post that referred to insertion sort as being O(n) was working with uniformly distributed slow moving entities. So the list is known to be mostly in order at each step. While in reality I'm sure that the number of crossing entities is relative to n (probably sqrt(n) ?) , in the simulation he posted - with so few crossings per time step - it's seems reasonable to refer to it as O(n).
Pages: 1 [2]
  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.

Elsealabs (20 views)
2014-12-28 10:39:27

CopyableCougar4 (21 views)
2014-12-28 02:10:29

BurntPizza (25 views)
2014-12-27 22:38:51

Mr.CodeIt (15 views)
2014-12-27 04:03:04

TheDudeFromCI (20 views)
2014-12-27 02:14:49

Mr.CodeIt (26 views)
2014-12-23 03:34:11

rwatson462 (60 views)
2014-12-15 09:26:44

Mr.CodeIt (48 views)
2014-12-14 19:50:38

BurntPizza (98 views)
2014-12-09 22:41:13

BurntPizza (117 views)
2014-12-08 04:46:31
How do I start Java Game Development?
by gouessej
2014-12-27 19:41:21

Resources for WIP games
by kpars
2014-12-18 10:26:14

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