QuadTree: stocker uniquement des points ou des régions?

Je développe un quadtree pour garder la trace des objets en mouvement pour la détection de collision. Chaque objet a une forme englobante, disons que ce sont tous des cercles. (C'est un jeu top-down 2D)

Je ne sais pas s'il faut stocker uniquement la position de chaque objet ou la forme entière de délimitation.

Si vous travaillez avec des points, l'insertion et la subdivision sont faciles, car les objets ne s'étendent jamais sur plusieurs nœuds. En revanche, une requête de proximité pour un objet peut manquer des collisions, car elle ne tiendra pas compte des dimensions des objets. Comment calculer la région de requête lorsque vous n'avez que des points?

Si vous travaillez avec des régions, comment gérer un objet qui s'étend sur plusieurs nœuds? Doit-il être inséré dans le nœud parent le plus proche qui le contient complètement, même si cela dépasse la capacité du nœud?

Merci.

Si vous stockez des objets étendus (régions) dans un quadtree, l'objet doit être référencé à partir de tous les nœuds feuilles qu'il touche. Je n'essaierais pas de trouver l'ancêtre le moins commun et de le stocker là-bas, car par exemple, un petit objet qui traverserait une frontière de haut niveau se retrouverait dans un nœud très élevé et devrait être testé par rapport à tout le reste de ce grand , nœud de haut niveau lorsque vous effectuez des requêtes de collision, etc.

Cependant, vous devez également être prudent car les gros objets peuvent finir par être référencés à partir de nombreux nœuds, ce qui les rend coûteux à mettre à jour lorsqu'ils se déplacent et les oblige à être revérifiés plusieurs fois pour détecter les collisions, etc. Selon votre cas d'utilisation, il Cela pourrait valoir la peine d'utiliser une sorte d'heuristique pour stocker de gros objets à un niveau supérieur dans l'arborescence, mais cela compliquerait les algorithmes, donc je ne vous dérangerais probablement pas, sauf si vous établissez que c'est vraiment un problème de performances dans votre cas particulier.

De même, pour interroger une région, la requête doit regarder tous les nœuds terminaux que la région interrogée touche.

Ceux-ci utilisent essentiellement le même algorithme, qui consiste à commencer par une région et à la pousser vers le bas dans l'arborescence pour trouver les nœuds foliaires qu'elle touche. C'est une traversée en profondeur, mais à chaque nœud, vous pouvez tailler tous les enfants qui ne touchent pas la région. Vous devrez conserver une pile pour savoir où vous en êtes dans la traversée.

Vous devez le stocker dans le plus petit nœud qui le contient complètement, même si cela dépasse la capacité (utilisez un conteneur redimensionnable).

J'ajouterais ceci en tant que commentaire en réponse à la réponse de @Nathan Reed, sauf qu'il est trop gros pour être un commentaire, et est peut-être en tout cas digne d'être une réponse distincte.

Nous faisions précisément ce qui était proposé dans sa réponse, et en fait nous avons des commentaires dans la source reliant à cette page. Pour la plupart, cela a extrêmement bien fonctionné, sauf qu'une fois tous les deux ou trois mois, nous avons perdu un serveur au hasard qui est devenu non réactif en raison de la durée massive des requêtes de recherche.

La cause première du problème est venue à mon attention lors d'une vérification des performances pour essayer de comprendre la cause de ce problème. Ce n'est probablement une préoccupation que si vous autorisez les objets qui se chevauchent. Dans notre jeu, nous le faisons, et dans le pire des cas, cela conduit parfois à un pic de profondeur qui tue les performances.

Nous avons eu un cas de bord où environ 100 objets, tous avec des disques de délimitation, ont été regroupés à une très grande proximité. Cela a conduit au problème d'un pic très profond dans l'arbre, car nous sommes arrivés au point où les objets étaient plus grands que la zone couverte par les nœuds de l'arbre, donc chaque nouvel objet apparaissait en plusieurs nœuds, conduisant à une subdivision massive du arbre, faisant ainsi boule de neige le problème hors de contrôle.

La conclusion à en tirer est que si vous autorisez les régions d'objets à se chevaucher, gardez un œil attentif sur les choses si vous obtenez des grappes d'objets serrés, pour vous assurer que votre arbre ne soit pas trop profond.

La solution que j'étudie actuellement consiste à stocker des objets sous forme de points, puis lors d'une recherche, augmenter les limites du rectangle de recherche par le rayon maximum stocké dans l'arborescence. Cela devrait fonctionner pour nous, car l'arborescence est une recherche de première passe, nous effectuons ensuite une vérification de la plage basée sur un véritable cercle, ainsi que quelques autres vérifications de critères, de sorte que les fausses alertes supplémentaires seront filtrées.

Votre kilométrage réel peut varier.