# Best 2D Space-Partition structure for point proximity

This topic is 4304 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
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.

##### Share on other sites
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:
// 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

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by NohupA 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
I'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.
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).

##### Share on other sites
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.

##### Share on other sites
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,

##### Share on other sites
Quote:
 Original post by NohupWhat 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.
Yeah, 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..

##### Share on other sites
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.