In one of my many projects I am implementing a world that is to be populated by many actors. Each actor can interact with the environment and each other. Now, I have been looking into sectorising the world in order to reduce the number of distance checks that each actor has to perform on all of the above. But should I really worry about this? Is there a quantity threshold that you would consider sectorising your world or do you bother at all? As an example consider something like Darwinia which appears to be a brute-force landscape system with many AI elements running around on it.

Do you expect that objects/agents within the world will move around over large distances, or stay relatively localised for periods of time?

As to the issue of brute force versus localised searching, in the area of algorithms for finding nearest neighbours in a data set, I've seen results that suggest brute force is good up to about 10^5 to 10^6 objects. Even if this were only 10^3, you're unlikely to gain much benefit from building a localised search method such as a tree decomposition of the space of objects. This will be especially true if objects are moving around a lot and changing their spatial ordering, since your tree would need to be rebuilt often. I'd suggest starting out with brute force and once everything is working, look for the bottlenecks in your implementation. If your code for comparing objects by brute force is the cause, then and only then look at ways of improving it.

Cheers,

Timkin

Timkin pretty much sums it up (as usual), but I may have a small suggestion. We had good results with a simple KD-tree. Assuming that your objects moves slowly, you dont need to re-build your tree at each time-frame. You only need to re-insert a few in the tree. Just make sure that every actor will be re-inserted in the tree at a reasonnable frequency.
(maximum speed * re-insertion frequency << distance check threshold)

Depending on the amount of agents you plan on having, sectoring can also be used for LOD (not just animation, but their logic, steering, etc...) to speed up characters that are far away that should be minimally updated.

The area I am talking about is not going to be that large and I don't know yet how many actors I want to populate it - I suppose its going to be as many as I can get before the system starts to crumble.

In my infinite world project the world is essentially 2D and that is segmented so that actors only search in their current segment and possibly the 2 adjacent segments.

My paranoia stems from not wanting to waste cycles on an actor that is to far from an object to worry about it - by sectoring it wont even know it is there so doesn't distance check it but without sectoring it will always check it.

Quote: Original post by Steadtler
We had good results with a simple KD-tree. Assuming that your objects moves slowly, you dont need to re-build your tree at each time-frame. You only need to re-insert a few in the tree. Just make sure that every actor will be re-inserted in the tree at a reasonnable frequency.
(maximum speed * re-insertion frequency << distance check threshold)

That's a really nice idea Steadtler and it's so relevant to my current research that I need more information! How extensive was your investigation of your reinsertion technique? As a function of time, do you know what the likelihood of an object being in the wrong leaf bin is (and hence missing it when doing a range or nearest neighbour search for a query near that object)?

How did you determine which objects to reinsert (random, time since last reinsertion, velocity)?

Did you end up publishing anything related to this, or did you draw the idea from previous publications? If so, do you have references please?

Cheers and thanks,

Timkin