Kreisbewegung auf Hardware mit geringem Stromverbrauch

Ich dachte an Plattformen und Feinde, die sich in alten 2D-Spielen im Kreis bewegten, und fragte mich, wie das gemacht wurde. Ich verstehe parametrische Gleichungen und es ist trivial, sin und cos zu verwenden, aber könnte ein NES oder SNES Echtzeit-Trigger-Aufrufe ausführen? Ich gebe schwere Unwissenheit zu, aber ich dachte, das wären teure Operationen. Gibt es eine clevere Möglichkeit, diese Bewegung billiger zu berechnen?

Ich habe daran gearbeitet, einen Algorithmus aus Triggersummenidentitäten abzuleiten, der nur vorberechnete Trigger verwendet, der jedoch kompliziert zu sein scheint.

Auf Hardware, wie Sie sie beschreiben, besteht eine übliche Lösung für den allgemeinen Fall darin, einfach eine Nachschlagetabelle für die Trigonometriefunktionen zu erstellen, an denen Sie interessiert waren, manchmal in Verbindung mit Festpunktdarstellungen für Werte.

Das potenzielle Problem bei dieser Technik besteht darin, dass sie Speicherplatz beansprucht. Sie können dies jedoch herunterspielen, indem Sie sich für eine niedrigere Auflösung der Daten in Ihrer Tabelle entscheiden oder die periodische Natur einiger Funktionen nutzen, um weniger Daten zu speichern und zur Laufzeit zu spiegeln.

Für das spezifische Durchlaufen von Kreisen - entweder um sie zu rastern oder um etwas entlang eines zu bewegen - kann jedoch eine Variation des Bresenham-Linienalgorithmus verwendet werden . Der eigentliche Algorithmus von Bresenham ist natürlich auch nützlich, um Linien, die nicht in den acht "primären" Richtungen liegen, recht billig zu durchqueren.

Es gibt eine Variation von Bresenhams Algorithmus von James Frith , die noch schneller sein sollte, da sie die Multiplikation vollständig eliminiert. Es braucht keine Nachschlagetabelle, um dies zu erreichen, obwohl man die Ergebnisse in einer Tabelle speichern könnte, wenn der Radius konstant bleibt. Da sowohl der Bresenham- als auch der Frith-Algorithmus eine 8-fache Symmetrie verwenden, wäre diese Nachschlagetabelle relativ kurz.

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

Sie können auch eine ungefähre Version der Triggerfunktionen mithilfe von Taylor Expansions http://en.wikipedia.org/wiki/Taylor_series verwenden

Zum Beispiel können Sie eine vernünftige Annäherung an den Sinus verwenden, indem Sie die ersten vier Begriffe der Taylorreihe verwenden

Ein großartiger Algorithmus, um gleichmäßig über einen Kreis zu fahren, ist der Goertzel-Algorithmus . Es sind nur 2 Multiplikationen und 2 Additionen pro Schritt, keine Nachschlagetabelle und ein sehr minimaler Zustand (4 Zahlen) erforderlich.

Definieren Sie zunächst einige Konstanten, möglicherweise fest codiert, basierend auf der erforderlichen Schrittgröße (in diesem Fall 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;

Der Algorithmus verwendet 4 Zahlen als Status, die wie folgt initialisiert wurden:

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

Und zum Schluss die Hauptschleife:

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

Es kann dann für immer gehen. Hier sind die ersten 50 Punkte:

Der Algorithmus kann natürlich auf Festkomma-Hardware arbeiten. Der klare Sieg gegen Bresenham ist die konstante Geschwindigkeit über den Kreis.