N Nearest Neighbor Structure
Author
I'm working on a game with a lot of NPCs that are persistent and need to carry out complex routines at all time. One thing the NPCs need to be aware of their neighbors in a region (rectangular or circular is sufficient).
The problem is that I have thousands of NPCs in a relatively small space (I'm trying to create a simulated city) and some of these NPCs move around a lot -- enough of them that I think it will really make the KD-tree useless since it will have to be rebalanced so much. However, the vast majority of the objects "hang out" around the same area indefinitely.
I originally tried using a quad-tree but the objects moved to much and it honestly wasn't very efficient.
What do you think?
by neighbours, you mean touching distance? Is this a 2D problem? Are your agents an identical size?
Then I'd consider a grid structure, or sweep and prune.
A grid is not the most memory efficient structure (if your objects are sparse, that's a lot of empty cells), but it's simple and fast, and it scales well with the number of actors.
Another example. It's pretty rough though, but even then here is the breakdown.
- 1,000 objects, arbitrary size.
- 64 x 64 cells, dense coverage.
doing one broadphase query.
doing one area query.
doing one line-of-sight query.
2 ms on a Core2 6600 @ 2.4ghz.
I'm sure with a more ad-hoc approach, and with a more sparse environment, you could have much better performance. The grid approach in N-tutorials will be ideal for an environment where all your actors have the same size (and as long as the size of the actor is less or equal than the size of a cell).
Just a heads up. Not sure about the performance of sweep and prune when consider a very large environment, but it should give you some nice performance too.
Then I'd consider a grid structure, or sweep and prune.
A grid is not the most memory efficient structure (if your objects are sparse, that's a lot of empty cells), but it's simple and fast, and it scales well with the number of actors.
Another example. It's pretty rough though, but even then here is the breakdown.
- 1,000 objects, arbitrary size.
- 64 x 64 cells, dense coverage.
doing one broadphase query.
doing one area query.
doing one line-of-sight query.
2 ms on a Core2 6600 @ 2.4ghz.
I'm sure with a more ad-hoc approach, and with a more sparse environment, you could have much better performance. The grid approach in N-tutorials will be ideal for an environment where all your actors have the same size (and as long as the size of the actor is less or equal than the size of a cell).
Just a heads up. Not sure about the performance of sweep and prune when consider a very large environment, but it should give you some nice performance too.
also you really need to consider if actual collision detection on agents outside your view is necessary. If you have 1,000 of agents doing their own thing, you may need a form of level of detail for the agent behaviour.
Author
I was thinking about using sweep and prune, but I think that will also be fairly inefficient. I think a simple grid may actually be the best thing I can use for this problem.
Thank you
Thank you
A spatial hash table should be a lot more memory efficient than a grid, and a hash table using chaining with some type of freelist allocator would be pretty fast.
Quote:Original post by thefries
A spatial hash table should be a lot more memory efficient than a grid, and a hash table using chaining with some type of freelist allocator would be pretty fast.
true.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
