General description
Suppose you have many objects moving in a 3D environment, and you need to find the neighbors of a given object. For example for the AI in a prey/predator game. How can you do that?
Performing efficient neighborhood requests (a.k.a. locality queries) is a general problem that is found in many domains, from game programming to database mining to graphics modelling to service geolocalization, etc. Sometimes you want to find all the nearby objects (like for broadcasting a message), and sometimes you're interested only in the nearest ones (like when an prey AI handles the most immediate threads)
What you'll find here is an original solution for answering the problem when the objects are moving, especially adapted to three dimension, and that may optionall handle cyclic worlds too.
This library has been designed for performance and ease of use. It can be seen as an improvement over the bin-lattice algorithm that is generally used for dynamic environments.
More information can be found in the article Query Sphere Indexing for Neighborhood Requests as well as together with the source code.
Article Abstract
This is an algorithm for finding neighbors for point objects that can freely move and have no predefined position. The query sphere consists of a center location and a given radius within which nearby objects must be found. Space is discretized in cubic cells. This algorithm introduces an indexing scheme that gives the list of all the cells making up the query sphere, for any radius and any center location. It can additionally take in account both cyclic and non-cyclic regions of interest. Finding only the K-nearest neighbors naturally benefits from the query sphere indexing by running through the list of cells from the center in increasing distance, and prematurely stopping when the K neighbors have been found.
Query Sphere Indexing for Neighborhood Requests, June 2007, Nicolas Brodu.
Source code
The latest source code implementing this algorithm can be downloaded here . The documentation and API are provided together with the source code.
Usage
- Copy the src/ directory anywhere in your include path.
- Include the "neighand.h" file where you need it.
- That's all. The library is header-only, no link is required.
Example
struct Agent {
// put your fields and methods here
int number;
// handy reference, this Agent ID
ObjectProxy<Agent>* proxy;
};
...
// Define a non-cyclic world with a 16x16x16 discretization
typedef NeighborhoodHandler<Agent,4,4,4,false,false,false> NH;
// The cell size is 6.25 units so the region of interest covers 0 to 100 in each dimension
NH nh(0,0,0,6.25);
...
// Insert a few objects
agent1.proxy = nh.insert(x1, y1, z1, &agent1, ProxiedObjectRemapper<Agent>());
agent2.proxy = nh.insert(x2, y2, z2, &agent2, ProxiedObjectRemapper<Agent>());
...
// Find all objects within distance d from the point at (x,y,z)
vector<Agent*> neighbors;
nh.findNeighbors(x, y, z, d, neighbors);
// Find the closest object from agent1 (but not itself), within d maximum distance
NearestNeighbor<Agent> neighbor;
nh.findNearestNeighbor(agent1.proxy, d, &neighbor);
cout << "The nearest neighbor of agent1 is the agent number " << neighbor.object->number << endl;
cout << "It is at d^2=" << neighbor.squaredDistance << " away from agent1" << endl;
History
| v0.2: | - Added support for directly calling the different query methods (sphere indexing, bin-lattice cube, non-empty cell list, brute-force). - Improved the algorithm for automatically selecting the best method. - API improvements and modifications. - Made the library compatible with user-defined memory allocators. - Made the library compatible with the aliasing rule. - Removed support for separate CPP specialization. That feature was a maintenance nightmare and it was (and still is) simpler to just specialize the templates in the user project CPP files anyway. |
| v0.1: | Initial public release |
