Best 2D Space-Partition structure for point proximity
Author
Greets,
The game is a 2D landscape, with hundreds(thousands?) of component based game object creatures living their lives... Grazing, hunting, mating, Whatever their AI component wants them to do.
The Creatures interact with each other by sending messages to nearby creatures whenever they do something interesting.
IE... If Creature#1234 kills and eats Creature#45, a message is sent to every other Creature within 500 units, so they can decide what to do.
Also, If Creature#4321 sends out a mating-call, then a message will go out to every other Creature within 1000 units, so that they can react.
Of course, there's other message types, which travel over different ranges, but the idea is the same.
I've been doing a for loop on EVERY:( Creature to determine the distance-squared, but this is a costly operation. (I profiled it, and the time spent in the "FindNeighbors(int)" function was around 10%. Not Odius, but more than I'd like, and only going to get worse when I ramp up the Creature Count).
I need this Space Partition structure to speed up my message passing, by lowering the potentialy interested set of Creatures.
The Creature's distribution is slightly clumpy, but can also be spread out over large areas, so no help there. :(
---------------------
I can see using a few different space partitioning structures to minimize the potential Creature set...
Loose Quad/Octree
Quad/Octree
Hashed Grid
Loose Quad/Octree:
My Creatures in this instance are just 2D points on a map. The fact that they are points makes a Loose Quadtree seem like a less-than-perfect solution, because all of my Creatures will end up in the bottom leaves. That's not a terrible problem, but it makes me think something else may work better.
A Quad/Octree would work, but since the creatures are somewhat dynamic/mobile they'll be breaking out of their sectors regularly, making me rebuild the quadtree somewhat often.
A Hashed grid seems like it would work great. Just hash a Creature's x, and y, to get it's sector, and check against creatures linked in that sector, then check against every creature in every sector within the message-radius. This seems good, because there's less pointer-tracing down a quadtree, but I'll end up doing quite a bit of distance checks on empty sectors.
If anyone hass tried any/all of these with a Large number of point-only game objects, and found one system to be very efficient, I'd love to hear your results. My only other option, is to code up all of these, and try them all out separatly.
I'd forget about Octrees for a start, seeing as you've got a 2D world.
I think the adjacency info that you'd have to store somehow would be much easier to do in a quadtree than a hash table.
I think the adjacency info that you'd have to store somehow would be much easier to do in a quadtree than a hash table.
I think your grid idea is probably your simplest solution at this point, though there's no reason to hash it. If your grid is uniform, you just need to check all grid squares within units/square_width distance..
pseudo-code:
Of course, this won't give you a circle of influence, but a quick tweak would fix that.
Another option is to do your messaging in a queued manner. When your creature performs a messagable action, the message and radius is pushed onto a queue. The next frame when you update your creature positions, have each check it's distance from the message source and react accordingly (for each message in the queue) You're still checking every object, but in a slightly smart way. :P
pseudo-code:
// scanning left -> right, top -> bottom.int nGridSquares = message_radius / gridwidth;int nStartX,nStartY,nEndX,nEndY;nStartX = message_source.x;nStartY = message_source.y;nEndX = nGridSquares*2 + nStartX;nEndY = nGridSquares*2 + nEndY;for(int nY=nStartY; nY < nEndY; ++nY){ for(int nX=nStartX; nX < nEndX; ++nX) { // send the message to each creature for(int nCreature=0; nCreature < grid[nX][nY].creatures.count; ++nCreature) { // message stuff. } }}Of course, this won't give you a circle of influence, but a quick tweak would fix that.
Another option is to do your messaging in a queued manner. When your creature performs a messagable action, the message and radius is pushed onto a queue. The next frame when you update your creature positions, have each check it's distance from the message source and react accordingly (for each message in the queue) You're still checking every object, but in a slightly smart way. :P
Just an idea:
Since its 2d it makes things very simple and can be compressed to a verry neat search structure. Just partition your space as a binary tree by deviding the space in halves to any desired resolution. Yor animals or just any generic entity in space will be the leaves of your partition structure. Every time a entity updates its position you can do a simple check if it still in a valid region and if not you have to update its position in the structure. You can also use frame coherence to your help and store potential creature groups that are in close proximity to eachother. Since its most likely that creatures in a group will most likely not move far from eachother from one frame to the next.
Hope that helps, if you don't understand what im talking about i can explain it better.
Since its 2d it makes things very simple and can be compressed to a verry neat search structure. Just partition your space as a binary tree by deviding the space in halves to any desired resolution. Yor animals or just any generic entity in space will be the leaves of your partition structure. Every time a entity updates its position you can do a simple check if it still in a valid region and if not you have to update its position in the structure. You can also use frame coherence to your help and store potential creature groups that are in close proximity to eachother. Since its most likely that creatures in a group will most likely not move far from eachother from one frame to the next.
Hope that helps, if you don't understand what im talking about i can explain it better.
Quote:Original post by NohupI've used something like this and it worked great. Although my game area wasn't that large so I could use a simple 2d-array to do the work faster than a hash table would. The structure is super-fast to update and to loop through sector's contents.
A Hashed grid seems like it would work great. Just hash a Creature's x, and y, to get it's sector, and check against creatures linked in that sector, then check against every creature in every sector within the message-radius. This seems good, because there's less pointer-tracing down a quadtree
Quote:but I'll end up doing quite a bit of distance checks on empty sectors.What do you mean? Of course you shouldn't do any distance checks for empty sectors.
For sectors whose area is entirely within 500 units distance, you'd know that all objects in there should receive the message. For sectors that are on the border of the 500-radius circle, you'd need to check the distance for each object wihin that sector (which may be 0 of course).
Author
Quite right anonymous.
I mis-spoke above when saying I would check empty sectors. A flag in every sectory saying "Empty, don't bother checking" would, of course make visiting this sector unnecessary.
What I should have said was that this system will create a much larger list of potential sectors which must be distance-checked against the event-emminating point. As this method would not have the Quadtree's ability to quickly rule-out large chunks of real-estate.
I mis-spoke above when saying I would check empty sectors. A flag in every sectory saying "Empty, don't bother checking" would, of course make visiting this sector unnecessary.
What I should have said was that this system will create a much larger list of potential sectors which must be distance-checked against the event-emminating point. As this method would not have the Quadtree's ability to quickly rule-out large chunks of real-estate.
Hi,
referring to my experience in computational geometry one solution to this problem are Higher Order Voronoi Diagrams. Given a set of N input points S in 2D and an arbitrary query point X, a Voronoi diagram allows you to find the point in set S, which is the nearest neighbor of the query point X. See the figure as illustration.
Higher Order Voronoi Diagrams generalize this concept to allow for searching for M nearest neighbors, not just one. What you can do is just keep querying the structure for farther nearest neighbors until you exceed the distance limit. Once this happens, you don't need to search anymore, because all other points are farther than the last point.
The disadvantage of this approach is that the implementation is not easy at all. It might take several days to code this, but I believe it's worth the time.
Here's an applet which demonstrates the idea behind first order Voronoi Diagrams Voronoi Diagram Applet.
Hope this helps,
bboyBladeJ
referring to my experience in computational geometry one solution to this problem are Higher Order Voronoi Diagrams. Given a set of N input points S in 2D and an arbitrary query point X, a Voronoi diagram allows you to find the point in set S, which is the nearest neighbor of the query point X. See the figure as illustration.
Higher Order Voronoi Diagrams generalize this concept to allow for searching for M nearest neighbors, not just one. What you can do is just keep querying the structure for farther nearest neighbors until you exceed the distance limit. Once this happens, you don't need to search anymore, because all other points are farther than the last point.
The disadvantage of this approach is that the implementation is not easy at all. It might take several days to code this, but I believe it's worth the time.
Here's an applet which demonstrates the idea behind first order Voronoi Diagrams Voronoi Diagram Applet.
Hope this helps,
bboyBladeJ
Quote:Original post by NohupYeah, but that isn't probably so bad if you adjust the section size to such that it gives the best performance. From your description I'd think that the creatures are sending message much rarer than they'll be updating their positions. With a simple grid structure the position updates will be faster to do than with quadtree, and I'd say that it counts much more than what quadtree's better pruning would help when finding nearby creatures..
What I should have said was that this system will create a much larger list of potential sectors which must be distance-checked against the event-emminating point. As this method would not have the Quadtree's ability to quickly rule-out large chunks of real-estate.
What I have done before (which worked very well, including in the physics engine for Rumble Box) was to create a grid of sectors, and then keep a list of all of the objects in that sector.
Whenever an enemy moves, if it changes sectors, it tells the old sector that it's not there anymore (removing it from the list) and tells the new sector that it is now there (adding it to that sector's list).
Then, when you want to check who is nearby, you just check the nearby sectors and you'll only have to loop through the enemies in their lists.
Whenever an enemy moves, if it changes sectors, it tells the old sector that it's not there anymore (removing it from the list) and tells the new sector that it is now there (adding it to that sector's list).
Then, when you want to check who is nearby, you just check the nearby sectors and you'll only have to loop through the enemies in their lists.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
