Hey i will try to make this breif since i am dead tired.

• The goal is to minimize data sent to a specific entity.
• The data is positions of other entities
• The data received by the entity should be about entities near it (say 50 pixels).

So if i have three entities with a distance of 1000 meters between them, no one should receive any data. If they all move closer however, they should get data from the close ones.


I have implemented 3 versions.

1. Measurement
2. Square based grid
3. Hexagonal grid

The fourth are supposed to be a QuadTree (OctTree in 2D). The concept about the QuadTree is to remove uninteresting data, perfect just what i need. But when i look into it it seems that i have a hard time seeing how it shall be done.

I made this image (below). I guess that the top state must be splittet again because the green dot is so close to the edge.
- If it goes to A, it misses the red one.
- If it goes to B, i must go and split much more, depending on how splitted they are (big cube requires some more untill down on "current dots cube"-size)
- But it has to go with B, because even if i have a minimum size on the cubes/quads an entity can still be at the edge (therefore requiring *se above*)

[sub]Also. I will benchmark these algorithms and see how much information they filter. Time is not really an issue, but if a quadtree is supposed to go fast i do not want it almost as slow as O(n^2).[/sub]
If you look at the image above, you see that i redo the inserting in the grids every time i run the algorithm. This works good for (tested) up to 10.000 entitys with fast results. The first one however, since it is O(n^2) is slow as hell with 10.000 (20+ seconds, apart from the grids wich have like 40-60ms).

So how should i do the quadtree in relation to this information. Should i be doing one quadtree for every entity ([sub]meaning close to O(n^2) if i am not thinking wrong[/sub]), or one quadtree -> Then check the entitys in it?.

Maybe i am explaining my thoughs bad. If so, i will try again tomorrow.

Oh, and the entities inside will not have bounding boxes. They are just 1 pixel each.

Look into kd-trees and the n-nearest-neighbor lookup problem.

Will do, thanks.

Oh, and the entities inside will not have bounding boxes. They are just 1 pixel each.[/quote]

Chances are you can use a spatial hashing algorithm which is much simpler and considerably faster than quadtrees. Instead of recursively divided grid nodes, picture a uniform grid instead. The grid itself is conceptual - it isn't an actual structure in code. It's simple to calculate the grid node that a given entity is in, in constant time. Now a given entity may be close enough to the edge of a node to influence entities in neighbouring nodes. You need to make the grid nodes large enough so each object can influence at most 4 nodes (left/right/above/below). To do this you set the node diameter to at least twice the entity influence radius.

Here's where the magic occurs. To determine what a given entity influences, you calculate the nodes it influences (constant time as the number is always 1,2 or 4). You then find the list of entities in each of these nodes, which is another constant time operation, because every entity is added to a hash table, indexed by it's node coordinate.

To reiterate, there is no grid structure stored in memory. Objects are actually added to a hash table (Try boost::unordered_multimap) to allow the list of objects in each node to be retrieved in constant time. Now as is typical in hash tables, two different keys will on occasion map to the same bucket. So performing a query on a given node will return all the entities that lie in that node and possibly entities which do not lie in the node. You can of course verify whether the entity lies in that node, in constant time, if this is desired. Normally you'll just calculate the (up to) 4 nodes that an entity spans and then retrieve the list of entities for each of those nodes. Then you'll perform a distance check on each.

Actual time complexity is dependent on the geometric distribution with the worst cases being when you have a clump of entities in a small area. But the node size needs only be twice as large as the influence radius (i.e. equal to the influence diameter), so the algorithm will process relatively few entities which are outside the influence radius you're querying against.

Oh, and the entities inside will not have bounding boxes. They are just 1 pixel each.

Chances are you can use a spatial hashing algorithm which is much simpler and considerably faster than quadtrees. Instead of recursively divided grid nodes, picture a uniform grid instead. The grid itself is conceptual - it isn't an actual structure in code. It's simple to calculate the grid node that a given entity is in, in constant time. Now a given entity may be close enough to the edge of a node to influence entities in neighbouring nodes. You need to make the grid nodes large enough so each object can influence at most 4 nodes (left/right/above/below). To do this you set the node diameter to at least twice the entity influence radius.

Here's where the magic occurs. To determine what a given entity influences, you calculate the nodes it influences (constant time as the number is always 1,2 or 4). You then find the list of entities in each of these nodes, which is another constant time operation, because every entity is added to a hash table, indexed by it's node coordinate.

To reiterate, there is no grid structure stored in memory. Objects are actually added to a hash table (Try boost::unordered_multimap) to allow the list of objects in each node to be retrieved in constant time. Now as is typical in hash tables, two different keys will on occasion map to the same bucket. So performing a query on a given node will return all the entities that lie in that node and possibly entities which do not lie in the node. You can of course verify whether the entity lies in that node, in constant time, if this is desired. Normally you'll just calculate the (up to) 4 nodes that an entity spans and then retrieve the list of entities for each of those nodes. Then you'll perform a distance check on each.

Actual time complexity is dependent on the geometric distribution with the worst cases being when you have a clump of entities in a small area. But the node size needs only be twice as large as the influence radius (i.e. equal to the influence diameter), so the algorithm will process relatively few entities which are outside the influence radius you're querying against.

[/quote]

This seems like a good idea and i will keep it in mind. However i kind of have to implement a quadtree since this is for my bachelors degree. And i am to compare different algorithms. If i make the quadtree in time i will try the hashtable also.

I will assume this is an implementation of it: http://wiki.gamedev.net/index.php/Spatial_Partitioning (bottom)

I have now implemented a QuadTree. The implementation is a first try for me, and i like to simplify things (hence the pictures).

The implementation as of now is that a Quad have a list of entities and a list of (4) quads.

And It has kind of two functions
- void insert( entity e ) this handles the insertion. (is there to much entities? is the quads level to deep? create new quads)
- void distribute() this one distributes the entities into the next 4 quads based on positions. Then it deletes the list ([sub]entities lives now in smaller lists in smaller quads below "this" quad[/sub])

This makes the basic idea for my quadtree to make the entities "flow" down the tree much like a river.

And here is it in action.

Red dots are player positions. We can clearly see the problem here. The blue area is a given players area of interest. Other player in this area should be known by the player. Now if a player is near the edge, it must in some way get that / those quads entitys/player-lists to.

Any clever ideas or pointer before i will start my brain-thinking-period?

It's not really that hard to solve; instead of finding entities directly find intersecting quad-tree cells, going down until you hit the bottom level for each group of cells, then take that list of cells which will be the bottom level and test entities contained in those cells.
As an added bonus if a cell is completely in your area of intrest then you can trivally accept all entities in the cell as being 'in intrest'.

It's not really that hard to solve; instead of finding entities directly find intersecting quad-tree cells, going down until you hit the bottom level for each group of cells, then take that list of cells which will be the bottom level and test entities contained in those cells.
As an added bonus if a cell is completely in your area of intrest then you can trivally accept all entities in the cell as being 'in intrest'.

Thank you for the fast reply. So i should check the intersection with the quads, then recursively do this untill no more quads, sounds reasonable. I will try this out.

Correct; the whole point of a spacial partioning system is to speed up lookups across the world, not just the cell your entity is in