Je travaille sur un jeu 2D qui a une énorme quantité d'entités dynamiques. Pour le plaisir, appelons-les des soldats et disons qu'il y en a 50000 (ce que je viens de penser au hasard, cela pourrait être beaucoup plus ou beaucoup moins :)).
Tous ces soldats déploient chaque trame selon les règles - pensent aux boites / comportement de flocage / direction. Pour chaque soldat, de mettre à jour son mouvement, j'ai besoin des soldats X les plus proches de celui que je traite.
Quelle serait la meilleure hiérarchie spatiale à les stocker pour faciliter les calculs comme celui-ci sans trop de frais généraux? (Toutes les entités sont mises à jour / déplacées chaque image, il doit donc gérer très bien les entités dynamiques)
3 Réponses :
L'approche la plus simple consiste à utiliser une grille. Il présente plusieurs avantages:
Aussi, assurez-vous de ne pas faire de Squareroot pour chaque chèque de distance. Puisque vous ne comparez que les distances, vous pouvez également comparer la distance au carré.
+1 Pour la place, beaucoup de gens ne réalisent pas à quel point la fonction est expressive et à quel point il est simple de l'éviter;)
Pour la détection de collision à large phase, un Index spatial comme un quad-arbre (depuis C'est 2D) ou une grille fera. J'ai lié à Tutoriel du logiciel Metanet avant; Il décrit un schéma basé sur la grille. Bien sûr, votre jeu n'a même pas besoin d'utiliser des grilles aussi largement. Il suffit de stocker chaque acteur dans une grille cachée et de la collier avec des objets dans les mêmes cellules et voisines.
Quadtree n'est pas le meilleur possible depuis pour chaque objet en mouvement, vous devez le retirer de l'arbre et le réinsérer. Une opération potentiellement coûteuse. Ou vous devez reconstruire l'arbre chaque image à nouveau.
@Reinier: Je pense que vous feriez des tests pour déterminer la fréquence à mettre à jour le Quadtree. Vous pouvez toujours ralentir ce taux et augmenter le rayon d'objets pour tester les collisions. Certes, des objets en mouvement rapide risquent de sortir du rayon élargi de toute façon, mais ceux-ci étaient les problématiques en premier lieu.
même argument va pour la grille; ^)
@Reinier: Alors, quelle est la plainte contre Quadtrees, alors? Peut-être que vous dites que vous devez supprimer et insérer le point à chaque fois, mais la grille enlevez et insérez et avez moins de complexité. Cela aurait un sens.
L'ensemble du point de sélectionner une bonne hiérarchie spatiale consiste à ne sélectionner rapidement que les objets nécessitant des tests. (Une fois que vous avez découvert que le petit sous-ensemble, la racine carrée ne va probablement pas blesser cela beaucoup)
Je suis également intéressé par la méthode la mieux / la plus optimale pour l'indexation spatiale 2D d'objets hautement dynamiques.
Quadtree / KD-Tree semble bien, mais ils ne sont pas trop bons avec des insertions dynamiques. Les kd-arbres peuvent devenir déséquilibrés.
Juste une pensée aléatoire, si vos entités sont des points une structure de tri double d'insertion (par x et y) en combinaison avec une recherche binaire peut être quelque chose à essayer ..
Si ce n'est pas nécessaire, pourquoi l'utiliser?
Voici Un bon algorithme , similaire à la suggestion de REINERIER.
Ce blog a Une bonne écriture d'une solution (ainsi qu'un certain nombre d'autres bonnes articulations)
N'oubliez pas de fermer la question en sélectionnant la réponse la plus utile.