Comment optimiser la fonction distance?

23

Lors du développement d'un jeu de type RTS assez simple, j'ai remarqué que mes calculs de distance avaient un impact sur les performances.

En tout temps, il y a des vérifications de distance pour savoir si une unité est à portée de sa cible, si le projectile a atteint sa cible, si le joueur a renversé une camionnette, une collision générale, etc. La liste continue et vérifie la distance entre deux points est très utilisée.

Ma question concerne exactement cela. Je veux savoir quelles alternatives les développeurs de jeux ont pour vérifier les distances, autres que l'approche sqrt (x * x + y * y) habituelle, qui prend assez de temps si nous l'exécutons des milliers de fois par image.

Je voudrais souligner que je suis conscient des distances de Manhattan et des comparaisons de distance au carré (en sautant le goulot d'étranglement sqrt). Rien d'autre?

Grimshaw
la source
Si vous avez des objets que vous ne vous attendez pas à déplacer, comme des bâtiments, par exemple, cela peut valoir la peine de prendre une série sur mesure 2D de la fonction de distance, de la tronquer au terme carré, puis de stocker la fonction résultante en tant que fonction de distance de ce bâtiment particulier. Cela déplacerait une partie du travail de grognement vers l'initialisation et pourrait accélérer un peu les choses.
Alexander Gruber

Réponses:

26

TL; DR; Votre problème n'est pas lié à l'exécution de la fonction de distance. Votre problème exécute la fonction de distance tant de fois. En d'autres termes, vous avez besoin d'une optimisation algorithmique plutôt que mathématique.

[MODIFIER] Je supprime la première section de ma réponse, parce que les gens la détestent. Le titre de la question demandait des fonctions de distance alternatives avant l'édition.

Vous utilisez une fonction de distance où vous calculez la racine carrée à chaque fois. Pourtant, vous pouvez simplement remplacer cela sans utiliser la racine carrée du tout et calculer la distance au carré à la place. Cela vous fera économiser beaucoup de cycles précieux.

Distance ^ 2 = x * x + y * y;

c'est en fait une astuce courante. Mais vous devez ajuster vos calculs en conséquence. Il peut également être utilisé comme contrôle initial avant de calculer la distance réelle. Ainsi, par exemple, au lieu de calculer la distance réelle entre deux points / sphères pour un test d'intersection, nous pouvons calculer la distance au carré à la place et comparer avec le rayon au carré au lieu du rayon.

Edit, bien après que @ Byte56 ait souligné que je n'avais pas lu la question et que vous étiez au courant de l'optimisation de la distance au carré.

Eh bien dans votre cas, malheureusement, nous sommes dans l'infographie traitant presque exclusivement de l' espace euclidien , et la distance est exactement définie comme Sqrt of Vector dot itselfdans l'espace euclidien.

La distance au carré est la meilleure approximation que vous obtiendrez (en termes de performances), je ne vois rien battre 2 multiplications, une addition et une affectation.

Vous dites donc que je ne peux pas optimiser la fonction de distance, que dois-je faire?

Votre problème n'est pas lié à l'exécution de la fonction de distance. Votre problème exécute la fonction de distance tant de fois. En d'autres termes, vous avez besoin d'une optimisation algorithmique plutôt que mathématique.

Le point est, au lieu de vérifier l'intersection du joueur avec chaque objet de la scène, chaque image. Vous pouvez facilement utiliser la cohérence spatiale à votre avantage et ne vérifier que les objets proches du joueur (les plus susceptibles de frapper / se croiser).

Cela peut être facilement fait en stockant réellement ces informations spatiales dans une structure de données de partitionnement spatial . Pour un jeu simple, je suggérerais une grille car elle est fondamentalement facile à mettre en œuvre et s'adapte bien à la scène dynamique.

Chaque cellule / boîte contient une liste d'objets que la boîte englobante de la grille contient. Et il est facile de suivre la position du joueur dans ces cellules. Et pour les calculs de distance, vous ne vérifiez que la distance du joueur avec ces objets à l'intérieur de la même cellule ou des cellules voisines au lieu de tout dans la scène.

Une approche plus compliquée consiste à utiliser BSP ou Octrees.

concept3d
la source
2
Je crois que la dernière phrase de la question dit que OP cherche d' autres alternatives (ils connaissent l'utilisation de la distance au carré).
MichaelHouse
@ Byte56 oui vous avez raison, je n'ai pas lu ça.
concept3d
Merci pour votre réponse quand même. Pourriez-vous ajouter une phrase confirmant que même si cette méthode ne nous donne pas une distance euclidienne, elle est très précise dans les comparaisons? Je pense que cela ajouterait quelque chose à quelqu'un venant ici d'un moteur de recherche.
Grimshaw
@Grimshaw J'ai modifié la réponse pour résoudre le problème d'origine.
concept3d
@ Byte56 merci de l'avoir signalé. J'ai édité la réponse.
concept3d
29

Si vous avez besoin de quelque chose qui reste linéaire sur n'importe quelle distance (contrairement à distance^2) et qui semble pourtant vaguement circulaire (contrairement aux distances carrées de Chebyshev et de type diamant à Manhattan), vous pouvez faire la moyenne des deux dernières techniques pour obtenir une approximation de distance de forme octogonale:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

dist = 0.5 * (dx + dy + max(dx, dy))

Voici une visualisation (tracé de contour) de la fonction, grâce à Wolfram Alpha :

Tracé de contour

Et voici un tracé de sa fonction d'erreur par rapport à la distance euclidienne (radians, premier quadrant uniquement):

Tracé d'erreur

Comme vous pouvez le voir, l'erreur varie de 0% sur les axes à environ + 12% dans les lobes. En modifiant un peu les coefficients on peut le ramener à +/- 4%:

dist = 0.4 * (dx + dy) + 0.56 * max(dx, dy)

entrez la description de l'image ici

Mise à jour

En utilisant les coefficients ci-dessus, l'erreur maximale sera de +/- 4%, mais l'erreur moyenne sera toujours de + 1,3%. Optimisé pour une erreur moyenne nulle, vous pouvez utiliser:

dist = 0.394 * (dx + dy) + 0.554 * max(dx, dy)

ce qui donne des erreurs entre -5% et + 3% et une erreur moyenne de + 0,043%


En cherchant sur le Web un nom pour cet algorithme, j'ai trouvé cette approximation octogonale similaire :

dist = 1007/1024 * max(dx, dy) + 441/1024 * min(dx, dy)

Notez que cela est essentiellement équivalent (bien que les exposants soient différents - ceux-ci donnent une erreur de -1,5% à 7,5%, mais ils peuvent être massés à +/- 4%) car max(dx, dy) + min(dx, dy) == dx + dy. En utilisant ce formulaire, les appels minet maxpeuvent être pris en compte en faveur de:

if (dy > dx)
    swap(dx, dy)

dist = 1007/1024 * dx + 441/1024 * dy

Est-ce que ça va être plus rapide que ma version? Qui sait ... dépend du compilateur et de la façon dont il optimise chacun pour la plate-forme cible. Je suppose qu'il serait assez difficile de voir une différence.

bcrist
la source
3
Intéressant, je n'ai jamais vu ça avant! At-il un nom, ou tout simplement "moyen de Tchebychev et Manhattan"?
congusbongus
@congusbongus Il a probablement un nom, mais je ne sais pas ce que c'est. Sinon, peut-être qu'un jour on l'appellera la distance Crist (hah ... probablement pas)
bcrist
1
Notez que les multiplications en virgule flottante ne sont pas très efficaces. C'est pourquoi l'autre approximation utilise 1007/1024 (qui sera implémentée comme une multiplication entière suivie d'un décalage de bit).
MSalters le
@MSalters Oui, les opérations en virgule flottante sont souvent plus lentes que les opérations entières, mais ce n'est pas pertinent - 0.4 et 0.56 pourraient tout aussi facilement être convertis pour utiliser des opérations entières. De plus, sur le matériel x86 moderne, la plupart des opérations en virgule flottante (autres que FDIV, FSQRTet autres fonctions transcendantales) coûtent essentiellement le même prix que leurs versions entières: 1 ou 2 cycles par instruction.
bcrist le
1
Cela ressemble beaucoup à Alpha max + Beta Min: en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm
drake7707
21

Parfois, cette question peut se poser non pas à cause du coût des calculs de distance, mais à cause du nombre de fois où le calcul est effectué.

Dans un grand monde de jeu avec de nombreux acteurs, il est impossible de continuer à vérifier la distance entre un acteur et tous les autres. De plus en plus les joueurs, PNJ et projectiles entrent dans le monde, le nombre de comparaisons qui ont besoin d'être se développera quadratiquement avec O(N^2).

Une façon de réduire cette croissance consiste à utiliser une bonne structure de données pour éliminer rapidement les acteurs indésirables des calculs.

Nous recherchons un moyen d'itérer efficacement tous les acteurs qui pourraient être à portée, tout en excluant la majorité des acteurs qui sont définitivement hors de portée .

Si vos acteurs sont assez uniformément répartis sur l'espace mondial, alors une grille de seaux devrait être une structure appropriée (comme le suggère la réponse acceptée). En conservant les références aux acteurs dans une grille grossière, vous n'avez qu'à vérifier quelques-uns des seaux à proximité pour couvrir tous les acteurs qui pourraient être à portée, en ignorant le reste. Lorsqu'un acteur se déplace, vous devrez peut-être le déplacer de son ancien seau vers un nouveau.

Pour les acteurs qui sont moins uniformément répartis, un quadtree peut faire mieux pour un monde à deux dimensions, ou un octree conviendrait à un monde à trois dimensions. Ce sont des structures à usage plus général qui peuvent partitionner efficacement de grandes zones d'espace vide et de petites zones contenant de nombreux acteurs. Pour les acteurs statiques , il existe un partitionnement d'espace binaire (BSP), qui est très rapide à rechercher mais beaucoup trop coûteux à mettre à jour en temps réel. Les BSP séparent l'espace à l'aide d'avions pour le couper de façon répétée en deux et peuvent être appliqués à n'importe quel nombre de dimensions.

Bien sûr, il y a des frais généraux pour garder vos acteurs une telle structure, surtout lorsqu'ils se déplacent entre les partitions. Mais dans un grand monde avec de nombreux acteurs mais de petites plages d'intérêt, les coûts devraient être bien inférieurs à ceux encourus par une comparaison naïve contre tous les objets.

La prise en compte de l'augmentation des dépenses d'un algorithme à mesure qu'il reçoit plus de données est cruciale pour la conception de logiciels évolutifs. Parfois, il suffit de choisir la bonne structure de données . Les coûts sont généralement décrits en utilisant la notation Big O .

(Je me rends compte que ce n'est pas une réponse directe à la question, mais cela peut être utile pour certains lecteurs. Mes excuses si j'ai perdu votre temps!)

joeytwiddle
la source
7
C'est la meilleure réponse. Il n'y a rien à optimiser dans la fonction distance; il suffit de l'utiliser moins souvent.
sam hocevar
3
La réponse acceptée couvre également le partitionnement spatial, sinon votre réponse est vraiment optimale. Merci.
Grimshaw
Mon temps a été très bien consacré à la lecture de votre réponse. Merci, Joey.
Patrick M
1
C'est la meilleure réponse et la seule qui se concentre sur le vrai problème plutôt que sur le redingue des performances de la fonction de distance. La réponse acceptée peut également couvrir le partitionnement spatial, mais c'est en aparté; il se concentre sur le calcul de la distance. Le calcul de la distance n'est pas le problème principal ici; l'optimisation du calcul de la distance est une non-solution de force brute qui ne se redimensionne pas.
Maximus Minimus
Pourriez-vous expliquer pourquoi le nombre de comparaisons serait exponentiel? Je pensais que ce serait quadratique, en comparant chaque acteur les uns avec les autres au cours de chaque période.
Petr Pudlák
4

Et la distance de Chebyshev? Pour les points p, q, il est défini comme suit:

distance

Ainsi, pour les points (2, 4) et (8, 5), la distance de Tchebychev est de 6, comme | 2-8 | > | 4-5 |.

De plus, soit E la distance euclidienne et C la distance de Tchebychev. Ensuite:

distance2

La limite supérieure n'est probablement pas très utile car vous devez calculer la racine carrée, mais la limite inférieure peut être utile - chaque fois que la distance de Tchebychev est suffisamment grande pour être hors de portée, la distance euclidienne doit également l'être, ce qui vous évite d'avoir à le calculer.

Le compromis, bien sûr, est que si la distance de Tchebychev est à portée, vous devrez de toute façon calculer la distance euclidienne, ce qui vous fera perdre du temps. Une seule façon de savoir si ce sera une victoire nette!

Tetrinity
la source
1
Vous pouvez également utiliser la distance de Manhattan comme limite supérieure.
congusbongus
1
Assez vrai. Je suppose qu'à partir de là, ce n'est qu'un saut, un saut et un saut vers la "moyenne de Chebyshev et Manhattan" comme suggéré par bcrist.
Tetrinity
2

Une optimisation locale très simple consiste simplement à vérifier d'abord une seule dimension.

C'est :

distance ( x1, y1 , x1, y2) > fabs (x2 - x1)

Donc, la simple vérification en fabs (x2 - x1)tant que premier filtre peut donner un gain appréciable. Combien dépendra de la taille du monde par rapport aux plages pertinentes.

De plus, vous pouvez l'utiliser comme alternative à la structure des données de partitionnement spatial.

Si tous les objets pertinents sont triés dans une liste dans l'ordre des coordonnées x, les objets à proximité doivent être à proximité dans la liste. Même si la liste devient désordonnée parce qu'elle n'est pas entièrement maintenue lorsque les objets se déplacent, étant donné les limites de vitesse connues, vous pouvez toujours réduire la section de la liste à rechercher pour les objets à proximité.

Keith
la source
2

Des efforts ont été faits dans le passé pour optimiser sqrt. Bien qu'il ne s'applique plus aux machines d'aujourd'hui, voici un exemple du code source de Quake, qui utilise le nombre magique 0x5f3759df :

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

Une explication détaillée de ce qui se passe ici se trouve sur Wikipedia.

En bref, ce sont quelques itérations de la méthode de Newton (un algorithme numérique qui améliore itérativement une estimation), avec le nombre magique utilisé pour fournir une estimation initiale raisonnable.

Comme le souligne Travis, ce type d'optimisation n'est plus utile sur les architectures modernes. Et même si c'était le cas, cela ne pourrait fournir qu'une accélération de taux constant à votre goulot d'étranglement, tandis que la refonte algorithmique pourrait obtenir de meilleurs résultats.

joeytwiddle
la source
2
Ce n'est plus une optimisation valable. Presque toutes les architectures de PC grand public que vous pouvez acheter de nos jours ont des instructions sqrt optimisées pour le matériel qui exécutent la racine carrée dans un cycle d'horloge ou moins. Si vous avez vraiment besoin du sqrt le plus rapide possible, vous utilisez l'instruction sqrt en virgule flottante simd x86: en.wikipedia.org/wiki/… Pour des choses comme les shaders sur GPU, l'appel de sqrt se traduira automatiquement par une telle instruction. Sur le CPU, je suppose que de nombreux compilateurs implémentent sqrt via SIMD sqrt si disponible.
TravisG
@TravisG Oui, cela mérite d'être mentionné, j'ai donc mis à jour la réponse. Cette réponse a été fournie pour le plaisir et l'intérêt historique uniquement!
joeytwiddle