Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (522)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (589)
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-like structure for dynamic / moving Game Objects  (Read 6141 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-11-20 21:18:24 »

Hey guys Smiley

I'm looking for a way to store moving, dynamic objects in quadtrees. Or better: I'm looking for a quadtree-like techneque to store objects, which move and are dynamic. The quadtree-like storage is supposed to only contain dynamic objects, since static objects are stored in a normal quadtree, which is the idea...

So the dynamic quadtree is cleared and filled every frame. Usually quadtrees aren't supposed to be used like that. What'd you suggest?

One more thing: I've also search up on how to use them and I stumbled across this stackoverflow question, which gave 2 ways to do it or 2 ideas:
1. A quadtree with Nodes being able to be node and leave at the same time, so AABB's are stored at the smallest node they can be put into.
2. A quadtree which stores all Rectangles in the leaves as a normal Point-storing-quadtree, but a reference to the Rectangle is hold to every possible leave in the quadtree. (So all leaves the rectangle covers store a reference to it)

So my question is:
Would you suggest a quadtree for storing dynamic objects, if not, what variation of quadtree would you suggest, or what other tree / thing would you suggest?
And:
How would you implement your dynamic quadtree, if you'd go about implementing one: Way 1, or way 2?

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: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2012-11-20 21:25:34 »

Quadtrees are not efficient in today's CPUs. Use a grid instead.

It's both incredibly easy to develop, and much, much faster.

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 #2 - Posted 2012-11-20 21:39:30 »

Quadtrees are not efficient in today's CPUs. Use a grid instead.

It's both incredibly easy to develop, and much, much faster.

What exactly is a grid?
Basically, yeah, I know what a grid is, but ... what exactly.

[size=4pt]JVM! Give me a grid! ... mhmmm... doesn't work :/[/size]

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

Just divide the space into equal-sized rectangles and keep track of what rectangles contain what objects. When the objects move you just update that information.
My experience with grids is that it is very fast unless the density of objects is really uneven. The extreme situation is when all objects are within a single rectangle. I guess that you can deal with this by dynamically constructing sub-grids within the rectangles, but I wouldn't bother unless you get real performance problems.

In three dimensions this might be a completely different story though...

Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2012-11-20 22:16:10 »

Normally it isn't required, but if you're stressed for performance, adjust the cell dimensions at runtime, and keep adjusting, always converging to a varying optimum.

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

JGO Knight


Medals: 32



« Reply #5 - Posted 2012-11-20 22:17:39 »

Checkout my quadtree implementation: https://bitbucket.org/mludwig/ferox/src/b0fc96dafa358ace4ccdf3e92aee468a72afd6f7/ferox-math/src/main/java/com/ferox/math/bounds/QuadTree.java?at=default

It's a quadtree built on top of a grid.

Offline theagentd

« JGO Bitwise Duke »


Medals: 361
Projects: 2
Exp: 8 years



« Reply #6 - Posted 2012-11-20 22:35:45 »

It's a quadtree built on top of a grid.
Uh, it's a a quadtree without the quadtreey parts?

Myomyomyo.
Offline lhkbob

JGO Knight


Medals: 32



« Reply #7 - Posted 2012-11-20 22:47:40 »

It's a quadtree built on top of a grid.
Uh, it's a a quadtree without the quadtreey parts?

No, it uses a grid structure for inserts/removals from the spatial index, intersecting pair queries, and AABB queries. Then a quadtree is built on top of the grid and stored in a single int array; this is possible because it's a complete tree, where the leaves map to the grid cells.

*edit*
The reason I brought this up was because I implemented it to be a structure that worked well with dynamic objects.  Both the grid and quadtree array can be cleared quite quickly, and building the quadtree up from the grid is more efficient than building the tree top-down.  In my game system, I then clear the tree each frame, possible updating what its extents are, and then re-insert every object.

Offline gouessej
« Reply #8 - Posted 2012-11-21 00:11:19 »

I will look at that carefully tomorrow, thank you for sharing this source code. I will look at Frustum.java too, can I use it to compute sub-frusta from 2 quads (typically for portal culling)?

Offline lhkbob

JGO Knight


Medals: 32



« Reply #9 - Posted 2012-11-21 01:26:23 »

I'm sure you could, but I haven't implemented that yet. Since it can support generic perspective frustums with arbitrary right/left, top/bottom values, I should assume it's possible.

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

Senior Newbie


Projects: 1



« Reply #10 - Posted 2012-11-21 07:43:48 »

Quadtrees are not efficient in today's CPUs. Use a grid instead.

It's both incredibly easy to develop, and much, much faster.

Hi all,

In my quest to learn new things, could you explain this a little more? 

I would have said it depends entirely on your scene and the implementation of the quad-tree whether grids are faster.   I say this because I imagine that the way you store the grid would be exactly the same way you'd store a qt (in that both are essentially just AABB - but, unless I am missing something, you can then cull huge areas of your game world with a qt which you cannot do with a grid).  So it would seem to me like the only difference between a grid and a at is you are removing the tree structure? 

Thanks,

Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #11 - Posted 2012-11-21 13:39:24 »

Okey guys, this gave me some very good ideas... And also thanks for the source code, this game me one idea too Smiley

So I'm back in about half an hour...

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 #12 - Posted 2012-11-21 13:42:38 »

I'd say I'd strongly disagree with what Riven is saying, BUT strong agree with the implication.  The problem with QuadTree's is first that it needs to be a good match to the average distribution of things contained.  Second that straight forward text-book implementations, which were fine until the mid-90s or so, will blow chunks on modern machines.  Thirdly that java is a poor language to implement a modern-ish version due to lack of structures.  Forthly (is that a proper word?) the amount of time (in comparison to a uniform grid) is probably exponentially longer and complex to come out with something that's like 10% (to pull a number out of my bottom) faster for spatial queries and that time could be much better spent on something else...and if speed is an issue then that .1*timeOfSpatialQueries cycles can probably be juiced out of somewhere else and still have some engineering time left over to spend on something else.

IHMO, the bottom line is that for large active worlds...breaking into local spaces is the way to go...and potentially hybrid models depending on the exact kinds of scenes involved.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2012-11-21 14:02:05 »

While you are (always) free to disagree, maybe even strongly, I wonder what the differences are in our points. I decided (due to lazyness) that I would not go into great detail, but my reasoning was exactly the same as yours. So... where do we actually disagree (strongly...) ?

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 #14 - Posted 2012-11-21 14:02:43 »

And what actually are your ideas?!? Huh

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: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #15 - Posted 2012-11-21 14:03:45 »

Like I said: use a uniform grid:
   List[w][h] or List[w*h]
it's unlikely you're going to run into performance problems. Unless ofcourse you're going to push the algorithm to its extremes, fine-tuning / benchmarking it, moving it to the GPU, and at the end of the day, don't have a game but a tech demo.

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 #16 - Posted 2012-11-21 14:08:54 »

So... a List<GameObject>[(yeah, I have a class doing this)w*h]?

Hmm... I just had the idea to use a HashMap. I'm pretty, pretty sure this will turn out very well Smiley

(also, I need to store AABB's, so I need to insert them at multiple leaves...)

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 #17 - Posted 2012-11-21 14:11:06 »

@Riven: Only in the statement: "Quadtrees are not efficient in today's CPUs".  They can be worth the effort...it's just very unlikely to be the case.
Offline theagentd

« JGO Bitwise Duke »


Medals: 361
Projects: 2
Exp: 8 years



« Reply #18 - Posted 2012-11-21 14:16:55 »

@Riven: Only in the statement: "Quadtrees are not efficient in today's CPUs".  They can be worth the effort...it's just very unlikely to be the case.
Didn't he just mean that traversing the tree has the same performance problems as a linked list?

Myomyomyo.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #19 - Posted 2012-11-21 14:27:13 »

That, and you have to do bounds checking (on AABBs) for every level, up to 4 times. All in all, there are lots of conditional jumps and lots of scattered memory access. In modern CPUs you get a rather large penalty for such code.

Needless to say, using a grid is just simpler to code, which, in this case, is probably most important.

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 #20 - Posted 2012-11-21 14:30:11 »

That, and you have to do bounds checking (on AABBs) for every level, up to 4 times. All in all, there are lots of conditional jumps and lots of scattered memory access. In modern CPUs you get a rather large penalty for such code.

Hmm. Yes. But is it good for static objects? I mean... Things which don't change it's vertices through the whole level?

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 2012-11-21 14:32:27 »

Exactly.  That's what you don't do in a modern version.  You never visit interior nodes, except in "rare" cases of global queries...which are exceptional.  You only walk leaf nodes, which ideally are attempting to be in cache-oblivious proximity of one-another...which is a nightmare enough with structures and temporal hints.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #22 - Posted 2012-11-21 14:33:21 »

@matheus23: You can just assume that a grid solves all your problems.

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 #23 - Posted 2012-11-21 15:33:46 »

@matheus23: You can just assume that a grid solves all your problems.

Yep. That worked out pretty well... but not with a List<GameObject>[], but with a HashMap<Vec2i, E>...
Look at this:
https://github.com/matheus23/Utils/blob/master/Utils/src/org/matheusdev/util/collections/GridCollection.java
Tested, works perfectly well, performance-wise pretty good Smiley
Takes 35-43 milliseconds to update 100k objects Cheesy
Which is okey, since I think I won't have 100k objects in game at any time Wink
And I won't even have 10k, which takes 3-4 milliseconds and is actually okey too. (for 10k objects? I guess that's pretty good... I'm pretty sure it's better than a Quadtree Tongue )

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

Senior Newbie


Projects: 1



« Reply #24 - Posted 2012-11-21 18:07:36 »

Hi All,

I ask before, but it seems like my post got lost near the top.

It seems a few people are really against using QTs, but for larger worlds I don't see how they can be worse than using a grid.  So again I ask this question to learn ..

Quadtrees are not efficient in today's CPUs. Use a grid instead.

It's both incredibly easy to develop, and much, much faster.

@Riven, as per my previous quesion .. I would have said it depends entirely on your scene and the implementation of the quad-tree whether grids are faster.   I say this because I imagine that the way you store the grid would be exactly the same way you'd store a qt (in that both are essentially just AABB - but, unless I am missing something, you can then cull huge areas of your game world with a qt which you cannot do with a grid).  So it would seem to me like the only difference between a grid and a at is you are removing the tree structure? 

That, and you have to do bounds checking (on AABBs) for every level, up to 4 times. All in all, there are lots of conditional jumps and lots of scattered memory access. In modern CPUs you get a rather large penalty for such code.

Needless to say, using a grid is just simpler to code, which, in this case, is probably most important.

@Riven Here you mention AABBs as if they are only applicable to QTs, but you would need to do this on a grid too surely?  Also, can you tell me which CPU penalties you are referring to ?

Thanks,
-John

Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #25 - Posted 2012-11-21 18:57:19 »

Soo... this thread seems to be very helpful to googlers Smiley

Just quick the new version: GridCollection.java on GitHub

What changed? I added another "query" method, which returns an ArrayList instead of relying on callbacks.

Quickly, what are the advantages and disadvantages of the GridCollection (because I forgot it in the last post):

Advantages:
  • It uses a HashMap to access and create grid elements, which means it is infinitly big and only has the elements created it needs.
  • It doesn't even do Rect vs. Rect collision detection. It only divides the rect's edges by the width and height, and then does for-iterate over all those possible grid positions and adds the elements to each grid element.
Yeah... at this point lintfordpickle interrupted me:

@Riven Here you mention AABBs as if they are only applicable to QTs, but you would need to do this on a grid too surely?  Also, can you tell me which CPU penalties you are referring to ?

As you probably read, I don't need to do AABB collision / intersection testing.

So, going on now:

Disadvantages:
  • I clear all the ArrayLists in all the HashMap entrys. (I don't have to delete them, but clear the content.) This is somehow an advantage, but also a disadvantage.
  • The empty ArrayLists need to be somehow "garbage-collected". Imagine an object wich just flew around in the world at very high speeds, and left a "trail" of created ArrayLists on it's way in the HashMap. This causes memory to be filled...
    But I think I solved this problem very well by deleting the ArrayLists, which haven't got any additional objects between the last and current update().
Point 1 of the disadvantages is probably the worst point, and a point why not to use this Data managing techneque, but I pretty much think the method is very good...

Also, I drew something so you understand this techneque better:

This is the first tick in our game code. The blue box is an active box, or in other words: An ArrayList<GameObject> entry in the HashMap.

This is the second iteration. The GameObject has moved into the next cell. The other cell is not yet "killed", because the code didn't actually recognize that it is unused yet. It will be killed in the next update() - or better - the next iteration:

Here the old cell got killed, because it didn't have any entrys. Basically, speaking programatically: list.isEmpty() returned true, so we map.put(pos, null)...

The last image also shows something else: The game object "intersects" with 4 Cells, instead of being contained in only one cell. This means we have to put it into all the cells it intersects. Again, "intersects" does not mean we do an AABB vs AABB intersection test. That's replaced by math here Wink

Hope this makes it much better to understand.


Thanks to Riven here Smiley Also thanks to lhkbob too, since he indirectly gave me the idea of clearing... somehow...

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: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #26 - Posted 2012-11-21 19:05:07 »

You're creating new problems that you need to solve. You're forcing the HashMap to constantly create new Map.Entry objects and trashing your cache, over and over again.

Just use a grid. Don't try to be cunning, smart or cook up ingenious solutions. Fill your entire grid with Lists. Don't cleanup empty Lists, just let them sit there, consume a bit of memory, it's all fine and dandy, and is actually the best thing to do in the typical usecase. Period.

Nobody in their right mind will use infinite scenes. Therefore you don't need to optimize for memory usage. Keep it simple. Don't try to find the ultimate solution - if you're trying to make a game.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline DrHalfway
« Reply #27 - Posted 2012-11-23 13:46:31 »

I must agree with Riven here

Speaking from a bit of experience, I've created numerous Broadphase detectors, some being more complex than others, such as Quadtrees, Variant of quadtree with ID tracking for nodes (for cache awareness), k-d trees, BSP trees you name it. By far, the best, most robust and fastest solution is Grid, especially for small-medium sized 2D games.

If you're creating an MMO, or want to procedurally create an infinite world of some sorts then yes, the more fancy detectors may be more memory efficient and may be faster, but these cases are very rare, and if you're creating such games you'd probably come up with a specific Hybrid solution for speed anyway rather than a single solution-fits all scheme.

Its late here so I haven't read all the posts, have you considered making your Quadtree/Grid aware of very fast moving objects in order to avoid tunneling? just a thought...

Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #28 - Posted 2012-11-23 14:25:33 »

Its late here so I haven't read all the posts, have you considered making your Quadtree/Grid aware of very fast moving objects in order to avoid tunneling? just a thought...

It's a grid... actually...
but how exactly would I go about making the grid aware of fast objects to avid tunneling?

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: 831
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #29 - Posted 2012-11-23 14:29:03 »

Yes, you have a grid, but not a grid-like datastructure. Remember that a HashMap is 'just' an array of linkedlists. And everybody knows linkedlists are a bad fit for, well, everything.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
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.

xFryIx (62 views)
2014-11-13 12:34:49

digdugdiggy (41 views)
2014-11-12 21:11:50

digdugdiggy (34 views)
2014-11-12 21:10:15

digdugdiggy (30 views)
2014-11-12 21:09:33

kovacsa (52 views)
2014-11-07 19:57:14

TehJavaDev (56 views)
2014-11-03 22:04:50

BurntPizza (55 views)
2014-11-03 18:54:52

moogie (70 views)
2014-11-03 06:22:04

CopyableCougar4 (70 views)
2014-11-01 23:36:41

DarkCart (156 views)
2014-11-01 14:51:03
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!