- 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.
- Measurement
- Square based grid
- 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.