Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
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. – John McDonald Mar 30 '12 at 18:47
Yes all entities moving around – Denis Ermolin Mar 30 '12 at 18:48
What are you doing when an entity moves? The simplest (and slowest) approach is to remove the entity, then re-add it. – John McDonald Mar 30 '12 at 18:50
1  
I used libkdtree++ STL-like implementation. On every move i erased, rebalanced and insert entity again. That was super slow. – Denis Ermolin Mar 30 '12 at 18:51
See my other answer here: gamedev.stackexchange.com/a/20609/9366 it may help – John McDonald Mar 30 '12 at 18:52
show 2 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
up vote 0 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.