Ruch kołowy na sprzęcie o niskiej mocy

Myślałem o platformach i wrogach poruszających się w kółko w starych grach 2D i zastanawiałem się, jak to zrobić. Rozumiem równania parametryczne i do tego jest trywialne użycie sin i cos, ale czy NES lub SNES mogą wykonywać wywołania trig w czasie rzeczywistym? Przyznaję, że to duża ignorancja, ale myślałem, że to kosztowne operacje. Czy jest jakiś sprytny sposób na tańsze obliczenie tego ruchu?

Pracowałem nad uzyskaniem algorytmu z tożsamości sumy wyzwalającej, która używałaby tylko wstępnie obliczonego wyzwalacza, ale wydaje się to skomplikowane.

Na sprzęcie, który opisujesz, powszechnym rozwiązaniem w ogólnym przypadku jest po prostu stworzenie tabeli przeglądowej dla funkcji trygonometrii, która była zainteresowana, czasami w połączeniu z stałymi punktami reprezentacji wartości.

Potencjalnym problemem związanym z tą techniką jest to, że zajmuje ona miejsce w pamięci, choć można to bagatelizować, wybierając niższą rozdzielczość danych w tabeli lub korzystając z okresowego charakteru niektórych funkcji, aby przechowywać mniej danych i dublować je w czasie wykonywania.

Jednak w przypadku szczególnie przemierzających kręgów - w celu ich rasteryzacji lub przesunięcia czegoś wzdłuż jednego, można zastosować odmianę algorytmu liniowego Bresenhama . Rzeczywisty algorytm Bresenhama jest oczywiście przydatny również w przypadku tanich linii, które nie są w ośmiu „pierwotnych” kierunkach.

Istnieje odmiana algorytmu Bresenhama autorstwa Jamesa Fritha , która powinna być jeszcze szybsza, ponieważ całkowicie eliminuje mnożenie. Aby to osiągnąć, nie potrzebuje żadnej tabeli przeglądowej, chociaż można przechowywać wyniki w tabeli, jeśli promień pozostaje stały. Ponieważ algorytm Bresenhama i Fritha używa 8-krotnej symetrii, ta tabela przeglądowa byłaby stosunkowo krótka.

// FCircle.c - Draws a circle using Frith's algorithm.
// Copyright (c) 1996  James E. Frith - All Rights Reserved.
// Email:  jfrith@compumedia.com

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 //

Możesz także użyć przybliżonej wersji funkcji wyzwalacza za pomocą Taylor Expansions http://en.wikipedia.org/wiki/Taylor_series

Na przykład, możesz uzyskać rozsądne przybliżenie sinusu, używając jego pierwszych czterech terminów z serii Taylor

Jednym z niesamowitych algorytmów do równomiernego podróżowania po okręgu jest algorytm Goertzela . Wymaga tylko 2 zwielokrotnień i 2 dodatków na krok, bez tablicy odnośników i bardzo minimalnego stanu (4 liczby).

Najpierw zdefiniuj niektóre stałe, być może zakodowane na stałe, w oparciu o wymagany rozmiar kroku (w tym przypadku 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;

Algorytm wykorzystuje 4 liczby jako swój stan, zainicjowany w następujący sposób:

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

I wreszcie główna pętla:

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);
}

Może wtedy trwać wiecznie. Oto pierwsze 50 punktów:

Algorytm może oczywiście działać na sprzęcie o stałym punkcie. Wyraźną wygraną z Bresenhamem jest stała prędkość nad kołem.