Je travaille sur une simulation Flocking Boites juste pour le plaisir, et je veux l'optimiser un peu. La zone qui a besoin de travail est de trouver des boites près d'un boitier donné. Je pense que pour le faire, une structure de données spatiale adaptée à la tâche serait ma meilleure mise (voir Ici et faites défiler un peu.).
Tout ce que je vais avec, je vais me mettre en œuvre, à partir de zava, en Java. De cette façon, j'apprendrai plus sur la structure de données que je choisis que si je viens d'appeler un tas de fonctions de bibliothèque.
Je suis au courant de r-arbres , KD arbres et Quadtrees . Ce sont toutes des options réalisables, à mon avis. Mais je n'ai aucune expérience avec ces structures de données et je ne suis pas totalement sûr de ce qui convient le mieux à mon objectif. Je n'ai besoin de rien sur cette échelle - je parle peut-être quelques centaines de boids, peut-être au plus d'un millier, plutôt qu'un million, bien que ce soit à l'esprit, je pourrais finir par le faire sur un téléphone Android éventuellement.
S'il vous plaît me recommander une structure de données (non limitée à ce qui précède, bien sûr) pour cela, et donnez-moi une bonne raison de le choisir sur les alternatives.
3 Réponses :
Honnêtement, je commencerais par une version non optimisée et voyez jusqu'où vous pouvez le prendre (combien de boites). Après cela, essayez différentes méthodes et mesurez la différence qu'ils font. Je pense que ce serait la meilleure façon d'apprendre.
Je conviens que ce serait bien pour une approche pratique de l'apprentissage sur le comportement de chaque structure de données, mais je préfère ne pas mettre en œuvre trois (ou plus) structures de données lorsque je suis sûr qu'il y a de bonnes raisons théoriques de choisir un sur les autres pour cela.
Quadtrees est une jolie structure de données standard utilisée pour la détection de frappe dans les jeux vidéo. Je pense que ce serait bien adapté à votre objectif.
neuf ans trop tard pour aider Iskar Jarak mais je vais trimer depuis que d'autres peuvent trouver cette vieille question dans une recherche.
Le point clé est que presque tout est meilleur que l'approche naïf o ( n ²) de regarder chaque paire d'inox. Ainsi, comme l'indique ISKAR, tout type de structure de données spatiales à base d'arbres est une vaste amélioration, étant fondamentalement O ( n journal n ). C'est-à-dire que chacun des boites n doit rechercher ses voisins chacun d'eux (log n ).
Il convient de noter que "Hit Détection" mentionnée par Desmond Vehar est un problème légèrement différent, demandant " Cette position de requête est-elle "à l'intérieur" l'un des "objets" dans ma structure de données? " Dans les simulations multi-agents, nous voulons trouver plusieurs voisins. Parfois "voisin les plus proches de voisins" ou peut-être "tous voisins dans un rayon donné de la position de la requête". Il suffit généralement de décrire un Boide comme point central et filtrer par distance entre les points, produisant une "sphère de requête".
Dans ses cours d'algorithmes Tim Fursgarden continue de demander "Pouvons-nous faire mieux?" Et effectivement - tandis que O (journal n ) est meilleur que O ( n ) pour rechercher un voisin - le meilleur est une recherche constante de temps, O (1). Voici les tables de hachage (alias des cartes non formées) sont nos amis.
Ces deux idées, multiples voisins et hachages, conduisent à une bonne approche pour accélérer les simulations multi-agents: hachage spatial dans des voxels (/ boîtes / treillis). Chaque Voxel contient une collection d'inox / agents. La position de l'espace continu (généralement 2 ou 3 flottants) de l'agent est convertie en coordonnées voxel (2 ou 3 INTS, par une opération "de plancher" échelle), qui sont hachées ensemble pour produire un "ID Voxel" qui est utilisé comme une clé dans une table de hachage de voxels. Donc, dans O (1) Temps constant, comme une référence de tableau, vous pouvez rechercher le Voxel qui contient une collection de tous les agents actuellement dans le même voxel. La "sphère de la requête" chevauchera normalement plusieurs voxels. Ceux-ci peuvent être trouvés en compensant le point de requête par multiples de la distance d'espacement voxel. Le contenu de ces nombreux voxels est fusionné pour former une collection de voisins potentiels, puis filtré par la distance. En tant qu'agents / Boites, ils comparent leur ancienne et nouvelle "ID Voxel" et, s'il n'est pas égal, ils se retirent de la structure de données, puis réinsérent à la nouvelle position.
Sphère de requête dans l'espace Voxel:
Il y a à peu près un zillion type de "structure de données spatiales" / "base de données spatiale". Voir cet article Wikipedia pour une enquête: Base de données spatiale . Voir aussi les premiers papiers de Hanan Samet: structures de données spatiales hiérarchiques et 1995's Structures de données spatiales .
Dans mon propre travail au début des années 2000, j'ai utilisé une collection de Voxels de la taille fixe, adressée avec I, J, K coordonnées:
Interaction avec des groupes de caractères autonomes en 2000 et Big Fouls rapides sur PS3 en 2006. Plus tard, je suis passé à l'aide du "hachage spatial Dans l'approche Voxels ", qui ne nécessite pas de spécification priori des dimensions de la grille Voxel 3D et a une surcharge de zéro pour la distribution d'agent clairsemé avec de nombreux voxels vexages vexages. 