Круговое движение на маломощном оборудовании

Я думал о платформах и врагах, движущихся по кругу в старых 2D играх, и мне было интересно, как это было сделано. Я понимаю параметрические уравнения, и для этого достаточно просто использовать sin и cos, но могут ли NES или SNES совершать триггерные вызовы в реальном времени? Я допускаю тяжелое невежество, но я думал, что это были дорогостоящие операции. Есть ли какой-нибудь умный способ рассчитать это движение дешевле?

Я работал над выводом алгоритма из идентификаторов суммы триггера, который использовал бы только предварительно рассчитанный триг, но это кажется запутанным.

На таких аппаратных средствах, которые вы описываете, общее решение общего случая - просто создать справочную таблицу для интересующих ее функций тригонометрии, иногда в сочетании с представлениями значений с фиксированной точкой.

Потенциальная проблема этого метода заключается в том, что он потребляет пространство памяти, хотя вы можете преуменьшить его, выбрав более низкое разрешение данных в вашей таблице или воспользовавшись периодическим характером некоторых функций, чтобы хранить меньше данных и отражать их во время выполнения.

Тем не менее, для специфического обхода кругов - либо для их растеризации, либо для перемещения чего-либо по одному, может быть использован вариант линейного алгоритма Брезенхэма . Конечно, фактический алгоритм Брезенхэма также полезен для обхода линий, которые не стоят в восьми «основных» направлениях достаточно дешево.

Есть вариант алгоритма Брезенхэма от Джеймса Фрита , который должен быть еще быстрее, поскольку он полностью исключает умножение. Для этого не требуется никакой справочной таблицы, хотя можно сохранить результаты в таблице, если радиус остается постоянным. Поскольку оба алгоритма Брезенхэма и Фрита используют 8-кратную симметрию, эта таблица поиска будет относительно короткой.

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

Вы также можете использовать приблизительную версию функций триггера, используя расширения Тейлора http://en.wikipedia.org/wiki/Taylor_series

Например, вы можете получить разумное приближение синуса, используя первые четыре члена ряда Тейлора

Один удивительный алгоритм для равномерного перемещения по кругу - это алгоритм Гертцеля . Требуется только 2 умножения и 2 сложения за шаг, нет таблицы поиска и очень минимальное состояние (4 числа).

Сначала определите некоторые константы, возможно, жестко закодированные, исходя из требуемого размера шага (в данном случае 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;

Алгоритм использует 4 числа в качестве своего состояния, инициализированного так:

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

И, наконец, основной цикл:

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

Это может продолжаться вечно. Вот первые 50 баллов:

Алгоритм, конечно, может работать на оборудовании с фиксированной точкой. Чистая победа над Брезенхэмом - это постоянная скорость по кругу.