Description générale
Supposez que vous disposez d'objets mobiles dans un environnement 3D, et vous devez trouvez les voisins d'un point donné. Par exemple, afin de réaliser une IA dans un jeu proie/prédateur. Comment faites-vous?
Effectuer de façon efficace des requêtes de voisinage est un problème général et pluridisciplinaire, pouvant s'appliquer à la programmation de jeux, aux moteurs de recherche dans des bases de données, à la modélisation graphique, aux services de géolocalisation, etc. Dans certains cas vous devez trouvez tous les voisins dans un rayon donné (par exemple pour diffuser un message), et parfois vous n'êtes intéressés que par les plus proches (par exemple pour une IA traitant en priorité les dangers immédiats).
Ce que vous trouverez ici est une solution originale pour répondre au problème où les objets sont mobiles, en trois dimensions, et pouvant optionellement gérer les mondes cycliques.
Cette bibliothèque est conçue dans un soucis de performance tout en restant facile à utiliser. Elle peut être vue comme une amélioration de la méthode dite "bin-lattice" généralement utilisée dans les environments dynamiques.
Vous trouverez plus d'information dans cet article "Query Sphere Indexing for Neighborhood Requests" ainsi que dans la documentation accompagnant le code source.
Résumé de l'article
Ceci est un algorithme pour trouver les voisins d'objets ponctuels pouvant évoluer librement sans position prédéfinie. La sphère de voisinage consiste en un centre de requête ainsi qu'un rayon dans lequel les objets voisins sont recherchés. L'espace est découpé en cellules cubiques. Cet algorithme introduit une méthode d'indexation donnant la liste de toutes les cellules composant la sphère de voisinage, pour n'importe quelle distance et centre de requête. Il peut de surcroît considérer des mondes cycliques si besoin est. Lorsqu'il s'agit de trouver uniquement les K voisins les plus proches cet algorithme bénéficie du fait que la liste des cellules est parcourue depuis le centre de la sphère de requête, et peut donc être arrêté prématurément lorsque les K points ont étés trouvés.
Query Sphere Indexing for Neighborhood Requests, Juin 2007, Nicolas Brodu.
Code source
Le code source le plus récent implémentant cet algorithme peut être téléchargé ici. La documentation et l'API de la bibliothèque sont fournies avec le code source.
Usage
- Copiez le répertoire src/ n'importe où dans le chemin d'inclusion des fichiers du compilateur.
- Incluez le fichier "neighand.h" où vous en avez besoin.
- C'est tout. La bibliothèque est composée uniquement de fichiers en-tête.
Exemple
struct Agent {
// Vos propres méthodes et variables
int number;
// l'ID de cet Agent pour la bibliothèque
ObjectProxy<Agent>* proxy;
};
...
// Définit un monde non-cyclique découpé en 16x16x16 cellules
typedef NeighborhoodHandler<Agent,4,4,4,false,false,false> NH;
// Chaque cellule fait 6.25 unités, la région couverte s'étend de 0 à 100 dans chaque dimension
NH nh(0,0,0,6.25);
...
// Insère quelques objets
agent1.proxy = nh.insert(x1, y1, z1, &agent1, ProxiedObjectRemapper<Agent>());
agent2.proxy = nh.insert(x2, y2, z2, &agent2, ProxiedObjectRemapper<Agent>());
...
// Trouve tous les voisins dans un rayon de distance d, autour du point (x,y,z)
vector<Agent*> neighbors;
nh.findNeighbors(x, y, z, d, neighbors);
// Trouve le voisin le plus proche de l'agent 1 (mais pas lui-même), et pas plus loin que la distance d
NearestNeighbor<Agent> neighbor;
nh.findNearestNeighbor(agent1.proxy, d, &neighbor);
cout << "Le plus proche voisin de l'agent 1 est l'agent numéro " << neighbor.object->number << endl;
cout << "Il se situe à d^2=" << neighbor.squaredDistance << " unités de l'agent 1" << endl;
Historique
| v0.2: | - Ajout de la possibilité d'appeler directement les différentes méthodes de recherche de voisins (indexation de la sphere, cube de la norme 1, liste des cellules non vides, recherche exhaustive). - Amélioration de l'algorithme pour sélectionner automatiquement la meilleure méthode de recherche. - Améliorations et modifications de l'API. - La bibliothèque accepte maintenant des allocateurs de mémoires définis par l'utilisateur. - La bibliothèque est maintenant compatible avec la règle de l'aliasing des pointeurs C/C++. - Suppression du support pour une spécialisation CPP. Cette fonctionalité était non-maintenable et de toutes façons trop complexe et redondante: il est plus simple pour l'utilisateur de spécialiser les templates directement dans un de ses fichiers projet. |
| v0.1: | Version publique initiale. |
