Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
   Home   Help   Search   Login   Register   
  Show Posts
Pages: [1]
1  Game Development / Performance Tuning / Re: Quadtree for moving objects on: 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.
2  Game Development / Performance Tuning / Re: Quadtree for moving objects on: 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?


3  Game Development / Performance Tuning / Re: Quadtree for moving objects on: 2009-09-02 12: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.

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.
4  Game Development / Performance Tuning / Re: Quadtree for moving objects on: 2009-09-02 09: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?
5  Game Development / Game Mechanics / Phys2d Composite Objects and FixedJoint on: 2007-12-18 09:39:43
I checked out the demo "rejoint" where fixed joint was used to generate composite bodies out of multiple bodies. The problem, however, is that I can't simply do the same in my project.

I have three boxes main body and two smaller boxes that could be called wings for example. When I connect them with FixedJoint, rotation works decently, however when I thrust (apply force along one of the cardinal axises of the object) the bodies that I attached with FixedJoint stall behind. I am not even talking about minor stuttering, but they get completely detached.

I saw a similiar post and yes, I am trying to achieve the same thing. I want to have the bodies "superglued" together with joints.

The code that I am using is very simple, almost straight from Rejoint demo from Phys2d sources.

Also, what is the relaxation property supposed to do? What kind of values is it supposed to take?



Pages: [1]
 

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

The first screenshot will be displayed as a thumbnail.

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

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

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

BurntPizza (84 views)
2014-12-08 04:46:31

JscottyBieshaar (45 views)
2014-12-05 12:39:02

SHC (59 views)
2014-12-03 16:27:13

CopyableCougar4 (58 views)
2014-11-29 21:32:03

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

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

toopeicgaming1999 (32 views)
2014-11-26 15:20:08
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

List of Learning Resources
by SilverTiger
2014-07-31 16:29: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!