Hmm. Yes. But is it good for static objects? I mean… Things which don’t change it’s vertices through the whole level?
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.
Yep. That worked out pretty well… but not with a List[], but with a HashMap<Vec2i, E>…
Look at this:
Tested, works perfectly well, performance-wise pretty good
Takes 35-43 milliseconds to update 100k objects
Which is okey, since I think I won’t have 100k objects in game at any time
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
)
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 …
@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?
@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
Soo… this thread seems to be very helpful to googlers
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:
As you probably read, I don’t need to do AABB collision / intersection testing.
So, going on now:
Disadvantages:
[li] 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.
[li] 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 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
Hope this makes it much better to understand.
Thanks to Riven here Also thanks to lhkbob too, since he indirectly gave me the idea of clearing… somehow…
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.
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…
It’s a grid… actually…
but how exactly would I go about making the grid aware of fast objects to avid tunneling?
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.
But since almost every Vec2i gives me different Hashcodes, I won’t have hash collisions, which means I don’t need to fill those linkedlists more than one or two objects.
After some little time the HashMap has built up it’s size, and then it’s not even necessary to delete or put in entries, so I guess it’s not too bad.
And I diagree that LinkedLists are bad for everything It’s true that they’re bad for storing entities (they’re really bad there), but they’re not bad for everything.
Small and fast objects like bullets that travel far every tick can be assumed to travel along a line that is used for the collision testing. So basically you just create the line from the previous tick to the current and check against your grid/accelerator. For large and fast objects you probably need to do something more fancy like sweep areas… brrrr
I…err…nevermind.
Roquen wanders off humming about traffic jams
[quote=“matheus23,post:31,topic:40208”]
That is not how hash maps work. Different hashcodes will cause hash collisions, unless your backing array has 4.2 billion entries.
[quote=“matheus23,post:31,topic:40208”]
They are bad for everything. But let’s not go there, as other threads have done so before.
Why don’t you just use a List[w][h] ? It’s so much better in every possible way. But it seems you have made up your mind, too bad, as the disadvantages have been explained already in this thread, and you just said ‘no’. Oh well, in the end, it’s about what works, not how it’s done. So good luck with your game - if there’s one in the making.
And as for tunneling / swept shapes: it’s normally good enough to make your entities queries so fast, that you can simply iterate the movement of the shape within a single game tick. In games you don’t need perfect solutions, so just moving a bullet with 100 positional updates (and querying for collisions) per tick will simply be enough. Another approach is to query series of overlapping bounding rectangles / circles along the movement vector and do a broad scan of potential colliders.
Nobody in their right minds will simulate more than 1 high speed colliding object, so don’t even bother solving that problem. Complexity increases so rapidly that you can just as well write a scientific simulator, and ditch any plans for your game.
The grid vers Quad tree performance depends on some details. If “things” are similar sizes and you have fairly well bounded space so that you don’t need too many grid cells, grids are pretty fast. Since these 2 things are typically true in games then the generalization that grids are faster easier than quad trees is not a bad approximation.
However with very large spaces, with very uneven distribution of “things” and/or things have quite a wide range of sizes. Then quad trees are faster and have smaller memory footprints.
Quadtrees are also faster for frustum culling.
Just don’t insert/update/remove items through the quadtree.
Just query them, and for large, odd shapes only.