Alternatives de partitionnement spatial 2D aux hachages spatiaux et aux quadtrees

11

J'ai essayé d'implémenter un algorithme de partitionnement spatial dans mon jeu, mais les hachages spatiaux et les quadtrees ne sont pas ce que je recherche.

Ma taille de niveau n'est pas censée avoir de limite (uniquement des limites Int32). J'ai besoin d'un algorithme de partitionnement spatial qui n'a pas besoin d'une "largeur de niveau" et d'une "hauteur de niveau".

J'ai beaucoup d'objets physiques en mouvement. J'ai besoin que l'algorithme soit suffisamment rapide pour prendre en charge plus de 500 objets.

Une alternative?

c# collision-detection physics tree Vittorio Romeo
la source

Réponses:

13

Arbre dynamique

Box2D est un moteur bien optimisé conçu par un programmeur expérimenté en physique / jeu . À l'origine, Box2D utilisait une grille de hachage qui nécessitait une hauteur et une largeur fixes.

Quand Erin est passé à un meilleur algorithme à large bande, il est allé avec btDbvt de Nathanael Presson. Il s'agit de la phase large utilisée par Bullet Physics. Erin a modifié et optimisé l'algorithme pour 2d.

Vous pouvez lire un aperçu de très haut niveau dans le manuel de Box2D (§4.11, ou rechercher Dynamic Tree).

Voici une exception de la documentation dans le code (qui est très bonne étant donné qu'elle ne fait pas partie de l'API publique).

Un arbre AABB dynamique à large phase, inspiré du btDbvt de Nathanael Presson. Un arbre dynamique organise les données dans un arbre binaire pour accélérer les requêtes telles que les requêtes de volume et les lancer de rayons. Les feuilles sont des procurations avec un AABB. Dans l'arborescence, nous développons le proxy AABB par b2_fatAABBFactor afin que le proxy AABB soit plus grand que l'objet client. Cela permet à l'objet client de se déplacer par petites quantités sans déclencher une mise à jour de l'arborescence.

Les nœuds sont regroupés et déplaçables, nous utilisons donc des indices de nœuds plutôt que des pointeurs.

Voici ma compréhension de l'algorithme de Dynamic Tree. L'arbre dynamique est le croisement entre un arbre binaire avl classique et un arbre quadruple . L'effet final est un quadtree qui ne divise que chaque nœud en deux, et la ligne de séparation n'est pas fixe (les deux moitiés ne sont pas de taille égale comme un arbre quad). AVL entre en jeu car les quadruples avec des divisions dynamiques peuvent dégénérer essentiellement en une liste (vitesse de recherche O (n)). L'AVL est utilisé pour rééquilibrer les sous-arbres afin d'assurer la vitesse de recherche O lg (N).

Le meilleur de tout le code est le MIT, alors n'hésitez pas à copier / dériver / voler sans vergogne / etc.

deft_code
la source
Ça a l'air ... complexe! Je vais y jeter un œil, cependant. Quelqu'un m'a suggéré d'utiliser la technique "sweep and prune" ou "sort and sweep" mais je n'ai rien trouvé sur une implémentation C # ou .NET. J'ai trouvé un exemple c ++ mais c'est déroutant et cela n'a pas fonctionné (j'ai quand même essayé de l'implémenter). Pensez-vous que SAP serait plus facile à mettre en œuvre? Existe-t-il une implémentation .NET?
Vittorio Romeo
8

C'est très proche d'une question similaire posée ici sur Gamedev, mais étant donné que vous vous souciez des performances et non du stockage de fichiers, ma réponse vous sera peut-être plus utile. Je vais en inclure la majeure partie ici pour être complet, mais la réponse originale fournit un peu plus de profondeur si vous voulez y jeter un œil.

J'ai rencontré un problème similaire et j'ai décidé de créer ma propre structure pour gérer les données. Il est vaguement basé sur un quadtree, mais a une extensibilité infinie (au moins aussi grande qu'un Int) dans toutes les directions. Il a été conçu pour gérer des données basées sur une grille qui se sont développées à partir d'un point central, tout comme Minecraft le fait maintenant. Il est peu encombrant en mémoire et très rapide.

Mon code se trouve ici . Le code est complet, testé (tests unitaires et de charge) et assez optimisé. Le fonctionnement interne n'est pas encore trop bien documenté, cependant, mais toutes les méthodes publiques le sont donc il devrait être utilisable. Si quelqu'un décide de l'essayer, n'hésitez pas à me contacter pour des questions ou des commentaires.

dlras2
la source
1

Lorsque je travaille avec un nombre relativement petit (<plusieurs milliers) d'objets de petite taille (la plupart des objets ne sont pas assez grands pour potentiellement entrer en collision avec beaucoup d'autres objets), je trouve qu'une simple liste ordonnée x de boîtes englobantes alignées axialement (AABB) fonctionne plutôt bien. Je viens de mettre les objets dans une liste, puis chaque image après avoir déplacé les objets, je trie rapidement la liste par valeur x, puis je fais un passage dans la liste en vérifiant la proximité AABB. Pour chaque objet, je le compare aux objets qui le précèdent dans la liste jusqu'à ce que j'atteigne la fin de la liste ou un objet qui est hors de la plage x; c'est-à-dire que la valeur x du bord gauche est> valeur x du bord droit de l'objet testé. Il divise fondamentalement dynamiquement l'espace en tranches parfois chevauchantes, de taille AABB x largeur. Il'

Shavais
la source
0

Peut-être que l' algorithme r-tree est ce que vous recherchez.

Je travaille très bien pour la géométrie statique, mais vous pouvez également l'utiliser pour déplacer des objets en supprimant et en ajoutant des objets à leurs nouvelles positions.

Paresser
la source
J'ai essayé une implémentation C #, et les performances étaient bien trop mauvaises lors de "la suppression et l'ajout d'objets à leur nouvelle position".
Vittorio Romeo