Разработка под Neo Geo: Числа с фиксированной запятой

Современные компьютеры работают с десятичными числами, такими как 0,5, используя числа с плавающей запятой. Если вы помните научную нотацию из школьных уроков, то работа с десятичными числами основана на той же идее. Такие числа в современных компьютерах обрабатываются процессором на аппаратном уровне, поэтому программы могут выполнять вычисления с ними очень быстро. Однако Neo Geo не может работать с десятичными числами вообще. Она умеет производить вычисления только с целыми числами, такими как 1+3, 88*4 или -45/5. Если вы захотите умножить 8 на 0,5 на Neo Geo, то это будет просто невозможно. Но для игр почти всегда нужны десятичные числа, так что же делать?

К счастью, существует способ использовать десятичные числа на такой старой системе, как Neo Geo, используя числа с фиксированной запятой.

Числа с плавающей запятой

Числа с плавающей запятой — это десятичные числа, где сама запятая может находиться в любом положении. Это позволяет компьютерам работать как с очень малыми числами, например 3.00000000001, так и с большими, например 12345678.2. Благодаря возможности перемещать десятичную запятую система с плавающей запятой гораздо более гибкая. В этой статье не будут рассматриваться подробности работы чисел с плавающей запятой, но стоит отметить, что при написании программ в наши дни вы обычно просто используете десятичные числа и редко задумываетесь о том как они работают, поскольку они просто работают.

Плавающая запятая — это сложная система, и поэтому она довольно медленная. Современные компьютеры решают эту проблему, выполняя вычисления с плавающей запятой на аппаратном уровне. Старые системы, такие как Neo Geo, "решали" эту проблему, просто не поддерживая её вовсе :)

Числа с фиксированной запятой

В системе с фиксированной запятой десятичная запятая зафиксирована на одном месте. Например, может использоваться шесть десятичных знаков и десять целых знаков, что выглядит как 1234567890.450012.

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

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

Однако это не совсем так, как мы увидим ниже. Умножение и деление работают немного сложнее.

Слабое место чисел с фиксированной точкой — это точность и гибкость. Если вам нужны действительно точные десятичные числа, вы можете выбрать систему фиксированной запятой с 4 битами для целой части и 12 битами для десятичной части. Но это означает, что максимальное целое число в такой системе будет 7. Если пойти в противоположном направлении и выбрать 12 бит для целой части и 4 бита для десятичной, максимальное целое число будет 2047. Это дает больше свободы, но тогда вы не сможете получать точные десятичные числа.

Расположение десятичной запятой — это компромисс.

Где именно расположить десятичную запятую, зависит от ваших потребностей. Для своей игры я выбрал систему, которая создает довольно точные десятичные числа, но за счет меньших целых чисел. Чаще всего числа с фиксированной запятой используются для вычисления положения чего-либо на экране, и так как разрешение экрана Neo Geo всего 320x224, использование небольшой целой части чисел вполне приемлемо.

Но зачем вообще нужны числа с фиксированной запятой?

Это справедливый вопрос. В конечном итоге всё сводится к размещению спрайтов на экране. Нельзя разместить спрайт в позиции (32.84, 44.9442); так в чем же смысл?

Представьте, что у вас есть персонаж, который может двигаться по экрану, например, Blue.

Персонаж Blue из игры Blue's Journey.

Простой способ сделать это — задать скорость перемещения Blue в 1 пиксель за 1 кадр. Тогда код может выглядеть примерно так:

if (pressingRight) {
    blue.x += 1;
}

graphics_moveSprite(blue.spriteIndex, blue.x, blue.y);

Это не реальный код для Blue's Journey :) Я просто использую его для простого примера.

Итак, 1 пиксель за кадр — это нормально, он перемещается на 60 пикселей в секунду. Он пересечет экран примерно за 5 секунд. Хорошо, а если мы хотим, чтобы он двигался быстрее? 2 пикселя за кадр? Тогда он пересечет экран примерно за 2,5 секунды. А если это слишком быстро? С этим сложно что-то сделать. Либо слишком медленно при 1 пикселе, либо слишком быстро при 2х пикселях. Можно попробовать сложные решения, такие как перемещение его только в 2х из каждых 3х кадров, но это быстро станет слишком сложным и, кроме того, ваша игра уже не будет действительно работать в 60 кадров в секунду.

Используя числа с фиксированной запятой, мы можем сказать, что Blue перемещается на 1,2 пикселя за кадр или взять любое другое дробное значение (в пределах разумного). Мы можем точно определить, как быстро движется Blue, перемещать его каждый кадр, и всё будет работать просто и удобно. Blue может быть на 32,2 пикселе в одном кадре, а затем на 32,8 пикселе в следующем. Поскольку спрайты должны размещаться на экране с использованием целых чисел, это может привести к тому, что визуально Blue будет находиться на 32 пикселе два кадра подряд, а затем на 33 пикселе в третьем кадре. Это не идеально, но с этим ничего не поделаешь. Это реальность старых систем с низким разрешением.

Если вы когда-либо слышали, как игроки Super Mario Bros. говорят о "субпикселях", то речь именно об этом. .2 и .8 — это субпиксели Blue в примере выше.

К счастью, это только визуальное ограничение. Логика вашей игры остается точной, поэтому управление и "ощущение" игры остаются отзывчивыми.

Создание системы с фиксированной запятой

Система чисел с фиксированной запятой довольно проста в реализации. Сначала определите, какой размер целого числа использовать для фиксированной запятой. Neo Geo хорошо работает с числами до 32 бит. Если вы используете ngdevkit, будет использоваться тип данных s32. Именно его я использую в своей игре.

Затем решите, сколько бит будет отведено для дробной части, например, вот так

typedef s32 fixed;
#define DECIMAL_BITS 5

32 бита на процессоре 68k Neo Geo представляют собой компромисс. У процессора Neo Geo 32-битные регистры, поэтому после загрузки чисел в регистры они обрабатываются без проблем. Так как обращение к памяти ограничено 16 битами за раз, процессору приходится загружать 32-битные числа за два обращения к памяти. Тем не менее, я пришел к выводу, что для использования фиксированной запятой 16 бит недостаточно, и на практике 32-битные числа работают достаточно быстро.

Затем нам понадобятся простые макросы для преобразования в числа с фиксированной запятой и обратно.

#define SCALE (1 << DECIMAL_BITS)
#define TO_FIXED(a) ((a) * SCALE)
#define FROM_FIXED(a) ((a) / SCALE)

И да, по сути, всё, что мы делаем, — это сдвигаем числа вверх в 32-битном пространстве. Этого достаточно, чтобы симулировать десятичные числа.

Теперь, когда у нас есть основа, сложение и вычитание становятся простыми операциями.

// create two integers
s16 a = 5;
s16 b = 6;
// convert them into our fixed system
fixed fa = TO_FIXED(a);
fixed fb = TO_FIXED(b);
// add them together
fixed fc = fa + fb;
// or subtract
fixed fc = fa - fb;
// convert them back into integers
s16 c = FROM_FIXED(fc);

В моей игре я почти всегда храню значения координат x и y позиции объекта на экране в формате фиксированной запятой. Затем, непосредственно перед обновлением спрайта, я преобразую их обратно в целые числа.

struct Bullet {
    fixed xF;
    fixed yF;
    u16 spriteIndex;
};

struct Bullet b;

b.xF = <<SOME FIXED CALCULATION>>
b.yF = <<SOME FIXED CALCULATION>>

graphics_moveSprite(b.spriteIndex, FROM_FIXED(b.xF), FROM_FIXED(b.yF));

Этот код сильно упрощен, но суть должна быть понятна.

Умножение

Теперь всё становится немного сложнее. При умножении двух чисел с фиксированной запятой "расположение десятичной запятой" смещается. В каждом числе с фиксированной запятой применяется масштабный коэффициент SCALE, поэтому после умножения результат будет иметь коэффициент SCALE*SCALE. Для того чтобы вернуть результат к исходному масштабу, требуется разделить его на SCALE.

fixed fixed_multiply(fixed a, fixed b) {
    fixed temp = a * b;

    // temp has been SCALE'd up twice, so bring it back down
    fixed result = temp / SCALE;

    return result;
}

Не используйте код из этой статьи. Я его упростил, так как этот пост посвящен лишь основам фиксированной запятой. Умножение и деление должны округлять свои результаты. См. раздел «Заключение» ниже.

Для перемножения двух чисел с фиксированной запятой просто используйте fixed_multiply() вместо оператора *.

fixed fa = TO_FIXED(5);
fixed fb = TO_FIXED(8);
fixed fc = fixed_multiply(fa, fb);

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

fixed fa = TO_FIXED(5);
fixed doubledFa = fa * 2;

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

fixed fa = TO_FIXED(5);
fixed doubledFa = fixed_multiply(fa, TO_FIXED(2));

Переполнение при умножении

Умножение двух 32-битных чисел и сохранение результата в 32-битном числе может привести к переполнению. Если взять два очень больших числа, при умножении результат может стать настолько большим, что он не поместится в 32-битное число. Это приводит к потере части данных, что делает результат некорректным. Обычный способ избежать этой проблемы — использовать временное 64-битное число для хранения промежуточного результата.

Однако на Neo Geo с этим есть проблемы, так как она не поддерживает 64-битные числа!

64-битные числа могут быть симулированы компилятором, но поскольку процессор 68k имеет только 32-битные регистры, для работы с такими числами процессору приходится выполнять множество дополнительных операций. Это значительно замедляет вычисления.

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

fixed fixed_multiply(fixed a, fixed b) {
    fixed temp = a * b;

    ngassert(
        a == 0 ||
        b == 0 ||
        abs(temp) >= abs(a),
        "fixed_multiply overflow, a: %d, b: %d, temp: %d", a, b, temp
    );

    // temp has been SCALE'd up twice, so bring it back down
    fixed result = temp / SCALE;

    return result;
}

Тут используется функцию ngassert(), которую я сделал сам. В своем посте MAME Lua for Better Retro Dev я подробно объясняю, как её реализовать.

После завершения умножения, если temp оказывается меньше одного из множителей (например, a), это признак того, что результат был слишком большой, и произошло переполнение. Этот подход не идеален, потому что, если возникает переполнение при умножении, единственный выход — изменить игру, чтобы избежать такой ситуации. Однако он помогает отлавливать критические ошибки на этапе разработки, предотвращая потенциальные сбои игры.

Деление

Аналогично умножению, деление также должно быть реализовано в виде функции.

fixed fixed_divide(fixed a, fixed b) {
    fixed temp = a * SCALE;

    ngassert(
        a == 0 ||
        abs(temp) >= abs(a),
        "fixed_divide overflow"
    );

    return temp / b;
}

Деление работает со SCALE противоположным образом по сравнению с умножением. Здесь результат будет уменьшен на SCALE, поэтому в начале мы увеличиваем входное значение a на SCALE. После деления результат возвращается к правильному масштабу.

Как и в случае с fixed_multiply, может не хватить места для увеличения a на SCALE, поэтому мы проверяем это с помощью ngassert().

Также деление на большое число (например, 1 / 1000000000) может привести к результату 0, если не хватает десятичной точности. Возможно, мне стоит также проверять это с помощью assert…

Литералы чисел с фиксированной запятой

Вы, возможно, заметили, что я никогда не использовал fixed fa = TO_FIXED(5.5), так как это невозможно. К сожалению, для этого нужно сделать следующее:

// fa will be "5.5"
fixed fa = TO_FIXED(5) + fixed_divide(TO_FIXED(1), TO_FIXED(2));

Такой код сложно читать. А также, из-за того, что fixed_divide — функция, а не макрос, инициализация будет происходить во время выполнения, а не на этапе компиляции. Чтобы немного упростить процесс и сгладить эти недостатки, в моей игре используется файл fixedConstants.h.

#include "fixedConstants.h"

fixed fa = TO_FIXED(5) + FIXED_ONE_HALF;

Читать такой код проще, и всё решается на этапе компиляции, а не во время выполнения. Для генерации fixedConstants.h я написал небольшой скрипт на Node.js.

import path from 'node:path';
import fsp from 'node:fs/promises';

const decimalBits = 6;
const scale = 1 << decimalBits;

function toFixed(a: number) {
    return Math.floor(a * scale);
}

async function main(outputDir: string): Promise<void> {
    const rawDefines: string[] = [];

    rawDefines.push(`ONE_HALF ${toFixed(1 / 2)}`);
    rawDefines.push(`ONE_THIRD ${toFixed(1 / 3)}`);
    rawDefines.push(`ONE_FOURTH ${toFixed(1 / 4)}`);
    rawDefines.push(`ONE_FIFTH ${toFixed(1 / 5)}`);
    rawDefines.push(`ONE_SIXTH ${toFixed(1 / 6)}`);
    rawDefines.push(`ONE_TENTH ${toFixed(1 / 10)}`);
    rawDefines.push(`ONE_TWENTIETH ${toFixed(1 / 20)}`);
    rawDefines.push(`THREE_FOURTHS ${toFixed(3 / 4)}`);
    rawDefines.push(`TWO_THIRDS ${toFixed(2 / 3)}`);

    const defines = rawDefines.map((rd) => {
        return `#define FIXED_${rd}`;
    });

    const src = `#pragma once
${defines.join('\n')}
`;

    const definesOutputPath = path.resolve(outputDir, 'fixedConstants.h');
    await fsp.writeFile(definesOutputPath, src);
    console.log('wrote', definesOutputPath);
}

const [_node, _buildFixedConstants, outputDir] = process.argv;
if (!outputDir) {
    console.error('usage: ts-node buildFixedConstants ');
    process.exit(1);
}

main(path.resolve(outputDir))
    .then(() => console.log('done'))
    .catch((e) => console.error(e));

Изменение точности

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

В качестве решения я определил количество дробных бит как переменную окружения. Мой код на C, makefile и скрипты используют эту переменную окружения. Таким образом, если мне нужно изменить точность, я просто обновляю переменную, заново генерирую такие файлы, как fixedConstants.h, и затем выполняю полную перекомпиляцию. Это намного удобнее, чем искать каждое место, где используются дробные биты.

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

Ниже пример того, как это работает в моем скрипте.

if (
    process.env.NEO_DECIMAL_BITS === undefined ||
    Number.isNaN(parseInt(process.env.NEO_DECIMAL_BITS))
) {
    throw new Error('NEO_DECIMAL_BITS env variable was not set');
}

const decimalBits = parseInt(process.env.NEO_DECIMAL_BITS);
const scale = 1 << decimalBits;

function toFixed(a: number) {
    return Math.floor(a * scale);
}

Симуляция чисел с плавающей запятой с помощью GCC

Кстати, если вы используете ngdevkit, то можете работать с числами с плавающей запятой, такими как float и даже double. Однако стоит учитывать, что GCC создаст программную реализацию чисел с плавающей запятой. Она работает ужасно медленно, особенно если вы используете double. В реальной игре это почти наверняка будет неприемлемо. Но это может быть полезно, если вам нужно что-то быстро протестировать.

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

Заключение

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

Обычно необходимость в создании своей собственной системы чисел с фиксированной запятой появляется на таких системах, как Neo Geo, поскольку большинство готовых библиотек делают предположения, которые не верны для старых игровых систем. В основном, они будут допускать использование 64-битных чисел при умножении и делении, что в реальности не осуществимо.