Mouvement circulaire sur du matériel de faible puissance

Je pensais aux plates-formes et aux ennemis qui tournaient en rond dans les vieux jeux 2D, et je me demandais comment cela se faisait. Je comprends les équations paramétriques, et il est trivial d'utiliser sin et cos pour le faire, mais un NES ou un SNES pourrait-il faire des appels trig en temps réel? J'admets une grande ignorance, mais je pensais que ces opérations étaient coûteuses. Existe-t-il un moyen intelligent de calculer ce mouvement à moindre coût?

J'ai travaillé sur la dérivation d'un algorithme à partir d'identités de somme de trigonomètres qui n'utiliseraient que des triggers précalculés, mais cela semble compliqué.

Sur le matériel tel que vous le décrivez, une solution courante au cas général consiste simplement à produire une table de recherche pour les fonctions de trigonométrie qui vous intéressaient, parfois en conjonction avec des représentations à virgule fixe pour les valeurs.

Le problème potentiel de cette technique est qu'elle consomme de l'espace mémoire, bien que vous puissiez minimiser cela en optant pour une résolution inférieure des données dans votre table ou en profitant de la nature périodique de certaines fonctions pour stocker moins de données et les refléter lors de l'exécution.

Cependant, pour traverser spécifiquement les cercles - soit pour les pixelliser, soit pour déplacer quelque chose le long d'un, une variante de l'algorithme de ligne de Bresenham peut être utilisée . L'algorithme réel de Bresenham , bien sûr, est également utile pour traverser des lignes qui ne sont pas dans les huit directions "primaires" à peu de frais.

Il y a une variation de l' algorithme de Bresenham par James Frith , qui devrait être encore plus rapide car il élimine complètement la multiplication. Il n'a pas besoin de table de recherche pour y parvenir, bien que l'on puisse stocker les résultats dans une table si le rayon reste constant. Étant donné que l'algorithme de Bresenham et de Frith utilisent une symétrie 8 fois, cette table de recherche serait relativement courte.

// FCircle.c - Draws a circle using Frith's algorithm.
// Copyright (c) 1996  James E. Frith - All Rights Reserved.
// Email:  [email protected]

typedef unsigned char   uchar;
typedef unsigned int    uint;

extern void SetPixel(uint x, uint y, uchar color);

// FCircle --------------------------------------------
// Draws a circle using Frith's Algorithm.

void FCircle(int x, int y, int radius, uchar color)
{
  int balance, xoff, yoff;

  xoff = 0;
  yoff = radius;
  balance = -radius;

  do {
    SetPixel(x+xoff, y+yoff, color);
    SetPixel(x-xoff, y+yoff, color);
    SetPixel(x-xoff, y-yoff, color);
    SetPixel(x+xoff, y-yoff, color);
    SetPixel(x+yoff, y+xoff, color);
    SetPixel(x-yoff, y+xoff, color);
    SetPixel(x-yoff, y-xoff, color);
    SetPixel(x+yoff, y-xoff, color);

    balance += xoff++;
    if ((balance += xoff) >= 0)
        balance -= --yoff * 2;

  } while (xoff <= yoff);
} // FCircle //

Vous pouvez également utiliser une version approximative des fonctions trigonométriques à l'aide de Taylor Expansions http://en.wikipedia.org/wiki/Taylor_series

Par exemple, vous pouvez avoir une approximation raisonnable du sinus en utilisant ses quatre premiers termes de la série Taylor

Un algorithme génial pour voyager uniformément sur un cercle est l' algorithme de Goertzel . Il ne nécessite que 2 multiplications et 2 ajouts par étape, aucune table de recherche et un état très minimal (4 chiffres).

Définissez d'abord certaines constantes, éventuellement codées en dur, en fonction de la taille de pas requise (dans ce cas, 2π / 64):

float const step = 2.f * M_PI / 64;
float const s = sin(step);
float const c = cos(step);
float const m = 2.f * c;

L'algorithme utilise 4 nombres comme état, initialisé comme ceci:

float t[4] = { s, c, 2.f * s * c, 1.f - 2.f * s * s };

Et enfin la boucle principale:

for (int i = 0; ; i++)
{
    float x = m * t[2] - t[0];
    float y = m * t[3] - t[1];
    t[0] = t[2]; t[1] = t[3]; t[2] = x; t[3] = y;
    printf("%f %f\n", x, y);
}

Cela peut alors durer éternellement. Voici les 50 premiers points:

L'algorithme peut bien sûr fonctionner sur du matériel à virgule fixe. La victoire nette contre Bresenham est la vitesse constante sur le cercle.