What is best approach to implement tracking in real time for, say, 1000 npcs? Every frame update simple a square grid (remove or insert into linked list) and every time check in square radius? I tried kd-tree but its really bad in real time updates even with 100 entities I can't reach 10 FPS.
\$\begingroup\$
\$\endgroup\$
7
-
\$\begingroup\$ Are all of these objects moving? It also doesn't sound right to get only 10fps with 100 entities, I can handle a lot more than that in my Quadtree implementation. \$\endgroup\$– John McDonaldMar 30, 2012 at 18:47
-
\$\begingroup\$ Yes all entities moving around \$\endgroup\$– Denis ErmolinMar 30, 2012 at 18:48
-
\$\begingroup\$ What are you doing when an entity moves? The simplest (and slowest) approach is to remove the entity, then re-add it. \$\endgroup\$– John McDonaldMar 30, 2012 at 18:50
-
1\$\begingroup\$ I used libkdtree++ STL-like implementation. On every move i erased, rebalanced and insert entity again. That was super slow. \$\endgroup\$– Denis ErmolinMar 30, 2012 at 18:51
-
\$\begingroup\$ See my other answer here: gamedev.stackexchange.com/a/20609/9366 it may help \$\endgroup\$– John McDonaldMar 30, 2012 at 18:52
|
Show 2 more comments
2 Answers
\$\begingroup\$
\$\endgroup\$
Not your typical answer, but I think it's useful to add this for future googlers. Here's some snippets from our chat:
Denis: minimum size of map 1000 x 1000 pixels
Denis: maximum can be 2500 x 2500 not more i think
Denis: units are 50 x 50
For sparser and larger worlds, I'd advocate the Quadtree, but I think for small and busy worlds, it is probably going to be slower than a Spatial hashing.
Denis: i see every time it clear all buckets and fill it again, is it good for real time game?
Personally, I'd expect it to be cheaper to test if the entity has moved into/out of a spatial grid, and only do some recalculation at that time. I know for my QuadTree, it's way quicker to test a moving object before removing and re-adding it. Also... don't re-calc the position of every object in the spatial hash. When the object moves, it should set a flag (or something) then and only then should it re-calculate its position in the spatial hash.
answered Mar 30, 2012 at 19:39
\$\begingroup\$
\$\endgroup\$
Maybe you could use a secondary structure that can be partitioning into the quadtree. If you can break your world down into components like rooms, or even subsection (and just track what is in which subsection then construct collision structure for those it should greatly improve performance. for example
if I have a world composed of 50 rooms, and each of those rooms has several entities then each room gets its own collision structure, and it can even be possible to take objects out of one structure, and transition it to another structure.
Another one I have seen is implementing a quadtree, and then having a BSP tree inside the lower levels of the quadtree (this is assuming that these low levels can still be large enough to accommodate a BSP tree.
in short many partitioning systems do not have to exist independently.
a good resource on the logic behind many collision detection algorithms is "Real Time Collision Detection" by Ericson
