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.
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
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.
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