Оглавление

• Введение

  • Несправедливость, которая существовала на AVR

  • Почему Build Engine, а не DOOM Engine

• Кратко о секторных движках

  • Сектор, стена и магия порталов

  • Как 2D‑карта превращается в 3D‑мир

• Пишем MicroBuild на спичечном коробке

  • Прототип на SDL2 и война с типами данных

  • Fixed‑Point арифметика

  • Бинарное измерение углов (BAM)

  • Собственная математика и таблица синусов (LUT)

  • Ужасная рекурсия и решение в духе ECS

  • THE CAKE IS A LIE!

• Скриншоты и примеры карт

• Бенчмарки

• Ссылки

Привет, Хабр!

Это моя первая статья, и сегодня я хочу поделиться опытом разработки собственного псевдо-3D движка для микроконтроллеров AVR. Проект получился технически сложным, но интересным, поэтому я решил подробно описать процесс его создания и те оптимизации, к которым пришлось прибегнуть.

Ниже под спойлером можно посмотреть на финальный результат работы движка.

Спойлер!

Несправедливость, которая существовала на AVR

Мой поисковый забег по запросам вроде «3D Graphics on Arduino» и «DOOM on Arduino» принес лишь разочарование. В основном всё сводилось к каркасным вращающимся кубам. Максимум, что удалось найти — проект Doom‑Nano. Но при ближайшем рассмотрении он оказался классическим рейкастером в духе Wolfenstein 3D (бросаем лучи из камеры по двухмерной сетке, а при пересечении рисуем вертикальную линию). Проект классный, но... это не DOOM.

И тут во мне взыграла инженерная гордость. Идея родилась сама собой: взять DOOM, разобраться в его архитектуре и портировать на AVR. Делов‑то!

Почему Build Engine, а не DOOM Engine

Но реальность быстро спустила меня с небес на землю. Я честно пытался с наскока раскусить BSP‑деревья (Binary Space Partitioning), которые использовал Джон Кармак. Читал документацию, смотрел схемы, но в какой‑то момент понял: Кармак слишком гениален, а BSP‑деревья для меня — это пока слишком темная магия.

Так родился проект MicroBuild — попытка засунуть секторный 3D‑движок в спичечную коробку микроконтроллера AVR. О том, как я боролся за каждый байт памяти и с какими граблями столкнулся, я и хочу рассказать.

Кратко о секторных движках

Сектор, стена и магия порталов

Архитектура любого секторного движка держится на трех китах: секторах, стенах и порталах. В отличие от современных движков, здесь мир не является единой 3D‑сеткой. Карта жестко разделена на два глобальных массива данных: стены и сектора.

В коде MicroBuild это выглядит максимально лаконично:

static FWall GWalls[] = { ... };
static FSector GSectors[] = { ... };

Давайте разберем анатомию этих сущностей.

Стены (FWall)

В самом простом виде стена — это отрезок на плоскости, заданный двумя точками, и её цвет (или индекс текстуры). Однако в портальных движках стена может быть «окном» в соседнюю комнату. Для этого в структуру вводятся переменные портала:

struct FWall
{
    FIntVector2D Point1, Point2; // Координаты начала и конца стены (2D)
    uint8 WallPaletteIndex;      // Индекс цвета стены в палитре
    int8 PortalNextSector;       // Номер сектора за этой стеной (-1, если стена глухая)
    int8 PortalNextWall;         // Индекс связанной стены в соседнем секторе
    FAngle PortalAngleDelta;     // Изменение угла при переходе (для неевклидовой геометрии)
};

Сектора (FSector)

Сектор — это выпуклый многоугольник, который описывает замкнутую комнату. Он не хранит координаты сам по себе. Вместо этого он знает высоту своего пола, потолка и указывает на «срез» в общем массиве стен, которые его окружают:

struct FSector
{
    int8 FloorZ;             // Высота пола
    int8 CeilZ;              // Высота потолка
    uint8 WallStartIndex;    // Индекс первой стены сектора в массиве GWalls
    uint8 WallCount;         // Количество стен у этого сектора
    uint8 CeilPaletteIndex;  // Цвет потолка по палитре
    uint8 FloorPaletteIndex; // Цвет пола по палитре
};

Благодаря такой структуре, обход карты становится очень быстрым: мы знаем, в каком секторе находится игрок, берем его стены, отрисовываем их, а если натыкаемся на стену, где PortalNextSector != -1, то переходим к отрисовке следующего сектора.

Как 2D‑карта превращается в 3D‑мир

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

Шаг 1. Перенос в локальные координаты и поворот

Сначала мы берем глобальные координаты стены и переносим их так, чтобы игрок оказался в центре вселенной (в точке 0, 0).

// Перенос относительно камеры
const FVector2D D1 = Wall.Point1 - InCameraLocation;
const FVector2D D2 = Wall.Point2 - InCameraLocation;

// Обратный поворот, чтобы стена оказалась лицом к игроку
FVector2D T1 = FVector2D(D1.X * CosA + D1.Y * SinA, D1.Y * CosA - D1.X * SinA);
FVector2D T2 = FVector2D(D2.X * CosA + D2.Y * SinA, D2.Y * CosA - D2.X * SinA);

Теперь в координатах T1 и T2 ось X отвечает за смещение влево‑вправо относительно взгляда игрока, а Y — за глубину (вперед‑назад). Здесь же рождается первая оптимизация: если Y обеих точек меньше нуля, то стена находится за спиной. Мы просто пропускаем её через continue.

Шаг 2. Ближний клиппинг (Near Clipping)

Если игрок подходит к стене вплотную или встает вдоль нее, координата Y одной из точек стремится к нулю. Последующее деление на ноль сломает fixed‑point математику и уведет расчеты в бесконечность.

Чтобы этого не происходило, мы отсекаем стену по ближней плоскости (NearZ). Если точка пересекает эту невидимую линию, мы программно пересчитываем её X и Y на границе отсечения:

constexpr FFixedFloat NearZ = FFixedFloat::ZeroPointFive;
if(T1.Y <= NearZ) 
{ 
    if(T2.Y == T1.Y) continue; 
    T1.X = T1.X + (T2.X - T1.X) * (NearZ - T1.Y) / (T2.Y - T1.Y); 
    T1.Y = NearZ; 
}
if(T2.Y <= NearZ) 
{ 
    if(T2.Y == T1.Y) continue; 
    T2.X = T2.X + (T1.X - T2.X) * (NearZ - T2.Y) / (T1.Y - T2.Y); 
    T2.Y = NearZ; 
}

Шаг 3. Перспективная проекция

Дальше работает обычный закон перспективы: чем дальше объект (больше Y), тем меньше он должен быть на экране. Мы делим локальные координаты на глубину Y и проецируем их на экран:

// Проекция по горизонтали (X-координаты экрана)
const int16 X1 = WINDOW_HALF_WIDTH + (T1.X * FovDistance / T1.Y).ToInt();
const int16 X2 = WINDOW_HALF_WIDTH + (T2.X * FovDistance / T2.Y).ToInt();
if (X1 >= X2) continue; // Отсекаем развернутые спиной стены

// Проекция по вертикали (высота пола и потолка)
const int16 Ceil1  = WINDOW_HALF_HEIGHT - (FFixedFloat(Sector.CeilZ  - FPlayer::LocationZ) * FovDistance / T1.Y).ToInt();
const int16 Floor1 = WINDOW_HALF_HEIGHT - (FFixedFloat(Sector.FloorZ - FPlayer::LocationZ) * FovDistance / T1.Y).ToInt();
const int16 Ceil2  = WINDOW_HALF_HEIGHT - (FFixedFloat(Sector.CeilZ  - FPlayer::LocationZ) * FovDistance / T2.Y).ToInt();
const int16 Floor2 = WINDOW_HALF_HEIGHT - (FFixedFloat(Sector.FloorZ - FPlayer::LocationZ) * FovDistance / T2.Y).ToInt();

Потолок и пол считаются одинаково, разница только в Z: для потолка берем CeilZ, для пола — FloorZ.

Шаг 4. Рендеринг вертикальными полосами

Всё, что нам осталось — пройти циклом от левой границы стены X1 до правой X2. Мы линейно интерполируем (Lerp) значения высоты пола и потолка между первой и второй точкой и рисуем стену вертикальными линиями пикселей, как в классическом Wolfenstein 3D движке.

if (Wall.PortalNextSector == -1) // Если стена глухая
{
    for (int16 X = StartX; X <= EndX; ++X)
    {
        const FFixedFloat Delta = FFixedFloat(X - X1) / FFixedFloat(X2 - X1);

        const int16 Ceil  = FMath::Lerp(Ceil1 , Ceil2 , Delta);
        const int16 Floor = FMath::Lerp(Floor1, Floor2, Delta);

        // Рисуем контур для красоты, остальное заполняем цветом из палитры
        const FColor WallColor = (X == X1 || X == X2) ? FColor(0, 0, 0) : GPalette[Wall.WallPaletteIndex];
        DrawWall(X, Ceil, Floor, WallColor);

        // Обновляем массивы клиппинга для порталов
        ClipTop[X]    = FMath::Clamp<int16>(Ceil , ClipTop[X], ClipBottom[X]);
        ClipBottom[X] = FMath::Clamp<int16>(Floor, ClipTop[X], ClipBottom[X]);
    }
}

Пишем MicroBuild на спичечном коробке

Перенос математики на реальное железо — самая интересная и сложная часть проекта. Ограничения микроконтроллеров AVR заставили переосмыслить буквально каждую строчку кода. Но обо всем по порядку.

Прототип на SDL2 и война с типами данных

Разрабатывать и отлаживать 3D‑движок сразу на микроконтроллере — затея изначально проигрышная. Поэтому первый рабочий прототип я собрал на ПК с использованием библиотеки SDL2. Базовая версия рендера заняла от силы 100 строк кода.

Затем я искусственно загнал ПК‑версию в рамки будущего железа: выставил разрешение экрана 160×128 пикселей (стандарт для популярных цветных дисплеев под Arduino по типу ST7735) и добавил параметр WINDOW_SCALE, чтобы не ломать глаза на современном мониторе.

Следующим шагом стала замена «тяжелых» для 8-битного процессора типов данных (int32_t, int64_t) на легковесные int8_t и int16_t. И здесь меня ждал первый серьезный баг, на поиск которого ушло полтора дня.

Выяснилось, что при расчете перспективной проекции промежуточные значения формул получаются просто огромными. Даже если финальная координата пикселя на экране гарантированно укладывается в диапазон от 0 до 128, в процессе деления и умножения чисел происходит жесткое переполнение регистра. В итоге после долгих поисков причин «сломанных» и улетающих в бесконечность стен решение было найдено: все промежуточные экранные координаты (пол и потолок) обязаны считаться строго в int32, и только перед самым выводом на экран их можно безопасно урезать через Clamp до размеров дисплея.

Fixed‑Point арифметика

На архитектуре AVR нет аппаратного математического сопроцессора (FPU). Любая операция с типом float эмулируется программно. На 8-битном микроконтроллере банальное сложение или деление двух чисел с плавающей точкой превращается в тяжеловесный танец на сотни процессорных тактов. В условиях рендеринга 3D‑сцены в реальном времени это непозволительная роскошь.

Решение этой проблемы я подглядел у Джона Кармака в коде DOOM — это Fixed‑Point арифметика (числа с фиксированной запятой). Я написал собственный класс FFixedFloat на C++, перегрузив базовые операторы для удобства.

Переход на новую математику делался плавно: я шаг за шагом заменял float на FFixedFloat, временно оставляя на концах формул метод .ToFloat(), чтобы проверять корректность рендера.

Сама суть Fixed‑Point арифметики проста. Представьте, что вам нужно посчитать бюджет. Вместо того чтобы оперировать дробными рублями (1.12 ₽), вы переводите всё в целые копейки (112 коп.). Вы работаете со стандартными быстрыми целыми числами, но мысленно помните, что последние два знака — это дробная часть.

В MicroBuild используется формат Q16.16 на базе обычного int32_t:

• 16 бит отведено под целую часть.

• 16 бит — под дробную часть.

В такой конфигурации единица (наш «рубль») — это 2^16 = 65536. Соответственно, число 0.5 хранится как 32768. Главная прелесть целых чисел здесь в том, что базовое сложение и вычитание работают «из коробки» на уровне процессора: при переполнении дробной части единица сама автоматически переходит в старшие биты целой части.

Для умножения и деления, конечно, приходится делать битовые сдвиги (<< 16 и >> 16), но для 8-битного процессора это всё равно в разы легче и быстрее, чем программная эмуляция честного float.

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

Бинарное измерение углов (BAM)

Бинарное измерение углов — штука экзотическая. Ее почти что никто не вспоминает, но когда надо — она сама приходит.

Суть проста: всю окружность мы сохраняем в виде uint8_t числа, то есть переводим 360° в диапазон от 0 до 255 (вместимость 8-битного числа).

Что мы теряем? Ну, во‑первых, точность. Теперь сказать 1.5° явно не получится. Во‑вторых, и 1° тоже не скажешь, ибо точность упадет до 360/256 = 1.4°. То есть одна единица в uint8_t будет равняться 1.4 градусам на окружности.

Многовато ли? Может быть. Но для нашего движка это подходит.

Тем более, даже внутри Unreal Engine при сетевой игре для других персонажей передается не полный угол игрока (со всеми числовыми дробностями), а упаковывается лишь в 8-битное число и отправляется по сети.

using FAngle = uint8;

Но остается последний вопрос — синусы и косинусы. Как их считать? А их не надо считать!

Собственная математика и таблица синусов (LUT)

LUT — Look‑Up Table (подстановочная таблица, или таблица поиска) — по сути обмен «тактов» на «память».

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

И для косинусов‑синусов это работает идеально!

Не будем ходить вокруг да около: BAM дает нам вместо миллиона градаций дробностей фиксированные 256 значений. Почему бы не использовать их как индекс в таблице, а саму таблицу посчитать заранее?

Да, можно. Так и делаем. Таблицы для синусов и косинусов, и готово.

Но! Мы можем уменьшить таблицу в 8 раз. Как? Вспоминаем школьную тригонометрию и график синуса/косинуса — они смещены на π/2, то есть на 90 градусов:

Это значит, что чтобы получить косинус, мне нужно от угла прибавить 90 градусов и посчитать его как синус. Бинго! Уже уменьшили таблицу в 2 раза (теперь у нас только полная таблица на синус).

Вот как это выглядит в коде:

static FFixedFloat Sin(const FAngle InAngle)
{
    const uint8 Quadrant = InAngle >> 6;
    const uint8 Index = InAngle & 0x3F;
    
    const FFixedFloat RawValue = SinLUT[(Quadrant == 0 || Quadrant == 2) ? Index : (63 - Index)];
    return Quadrant >= 2 ? -RawValue : RawValue;
}

static FFixedFloat Cos(const FAngle InAngle) { return Sin(InAngle + 64); }

Итого: таблица на 64 значения вместо 256, косинус через синус со сдвигом, и всё это в Fixed‑Point. Дёшево и сердито.

Ужасная рекурсия и решение в духе ECS

А вот тут начинается самое интересное.

Изначально RenderSector вызывал сам себя. Когда рендер натыкался на портал, он рекурсивно вызывал RenderSector для соседнего сектора. На ПК это работало нормально — стек большой, рекурсия уходила в глубину, всё было хорошо.

На AVR это закончилось предсказуемо: второй вложенный портал — и всё, стек кончился, микроконтроллер умер.

Надо было что‑то делать. И решение пришло в голову: а что, если вместо рекурсии использовать очередь задач?

Идея простая. Вместо того чтобы RenderSector вызывал сам себя, он добавляет задачу в очередь: «отрисуй сектор N в диапазоне от MinX до MaxX с такой‑то виртуальной камерой». Главный цикл рендера крутится, пока очередь не опустеет, и никакой вложенности вызовов нет.

struct FRenderTask
{
    int8 SectorIndex;
    int16 MinX;
    int16 MaxX;
    FFloatVector2D CameraLocation;
    FAngle CameraAngle;
};

struct FRenderTaskQueue
{
    static inline FRenderTask Queue[RENDERING_TASK_QUEUE_ELEMENTS] = {};
    
    static void Empty() { Head = 0; Tail = 0; }
    
    static bool AddTask(const FRenderTask&& InRenderTask)
    {
        if(Head >= RENDERING_TASK_QUEUE_ELEMENTS) return false;
        Queue[Head++] = InRenderTask;
        return true;
    }
    
    static int8 PopTaskIndex()
    {
        return Tail >= Head || Tail >= RENDERING_TASK_QUEUE_ELEMENTS ? -1 : Tail++;
    }

private:
    static inline int8 Head = 0;
    static inline int8 Tail = 0;
};

А главный цикл выглядит так:

FRenderTaskQueue::Empty();
FRenderTaskQueue::AddTask(FRenderTask { FPlayer::CurrentSector, 0, WINDOW_WIDTH - 1, FPlayer::LocationXY, FPlayer::Angle });

int8 TaskIndex;
while((TaskIndex = FRenderTaskQueue::PopTaskIndex()) != -1)
{
    RenderSector(
        FRenderTaskQueue::Queue[TaskIndex].SectorIndex,
        FRenderTaskQueue::Queue[TaskIndex].MinX,
        FRenderTaskQueue::Queue[TaskIndex].MaxX,
        FRenderTaskQueue::Queue[TaskIndex].CameraLocation,
        FRenderTaskQueue::Queue[TaskIndex].CameraAngle
    );
}

Почему «в духе ECS»? Потому что здесь та же идея: Есть данные (массив FRenderTaskQueue) и есть система (RenderSector), которая проезжает по этим данным как газонокосилка и обрабатывает их. Данные отдельно, обработка отдельно. Это не ECS в каноническом смысле (нет Entity, нет Component), но концепция та же — data‑oriented подход.

Бонусом получилось то, что обход стал breadth‑first: сначала рисуются все сектора первого уровня, потом второго и так далее. Ближние сектора рисуются раньше, и клиппинг работает эффективнее.

THE CAKE IS A LIE!

А теперь самое интересное....

Когда я впервые заметил, что движок рендерит портал из своей камеры. Ключевое — из своей — я подумал: «а что если...». А что если рендерить не из своей камеры, а где‑нибудь... с другого места?

И я выбрал меньшее из двух зол: выделил один байт и просто захардкодил туда угол между двумя порталами.

Да, может, тупо. Но зато сработало!

Технически это выглядит так. У стены‑портала есть параметр PortalAngleDelta — угол, на который поворачивается портал при переходе.

В коде это выглядит так:

if(Wall.PortalNextWall != -1) // Non-Euclidean Portal
{
    const FWall TargetWall = LoadFromFlash(GWalls[Wall.PortalNextWall]);
    const FAngle VirtualAngle = InCameraAngle + Wall.PortalAngleDelta;
    
    const FFloatVector2D PortalCenter = FFloatVector2D(FFloatVector2D(      Wall.Point1) + FFloatVector2D(      Wall.Point2)).DivByTwo();
    const FFloatVector2D TargetCenter = FFloatVector2D(FFloatVector2D(TargetWall.Point1) + FFloatVector2D(TargetWall.Point2)).DivByTwo();
    
    const FFloatVector2D LocalLocation = InCameraLocation - PortalCenter;
    
    const FFixedFloat CosAngle = FMath::Cos(Wall.PortalAngleDelta);
    const FFixedFloat SinAngle = FMath::Sin(Wall.PortalAngleDelta);
    
    const FFloatVector2D RotatedLocation = FFloatVector2D(LocalLocation.X * CosAngle - LocalLocation.Y * SinAngle, LocalLocation.Y * CosAngle + LocalLocation.X * SinAngle); 
    const FFloatVector2D VirtualLocation = TargetCenter + RotatedLocation;
    
    FRenderTaskQueue::AddTask({ Wall.PortalNextSector, StartX, EndX, VirtualLocation, VirtualAngle });
    continue;
}

Мы берём центр портала, центр целевой стены, поворачиваем локальную позицию камеры на PortalAngleDelta и получаем виртуальную камеру. И добавляем задачу с этой виртуальной камерой. Камера не «телепортируется» — она виртуально пересчитывается для каждой задачи рендера.

И в конечном итоге: у нас работают неевклидовы порталы прямо на AVR! Для примера есть карта ТАРДИС — снаружи маленькая будка, а внутри большое пространство. И это не фейк, это честная неевклидова геометрия.

Есть, конечно, ограничение. Неевклидова рекурсия ограничена константой RENDERING_NON_EUCLIDEAN_PORTAL_MAX_RECURSION (у меня это 8). Если игрок видит портал в портале в портале — глубина обрезается. На AVR иначе никак: каждая вложенная задача — это ещё один проход рендера, а микроконтроллер не резиновый.

Скриншоты и примеры карт

Карта «DuoRooms»

Карта «Stairs»

Карта «Simple Portals!»

Карта «TwoCorridors»

Карта «TARDIS»

Бенчмарки

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

На AVR я настроил Timer1 в режиме нормального счёта с предделителем 64. Это значит, что таймер тикает с частотой 16 МГц / 64 = 250 кГц. То есть один тик — это 4 микросекунды.

Перед началом кадра я сбрасываю счётчик в ноль (TCNT1 = 0), после кадра — читаю его значение. Дальше остаётся только перевести тики в FPS:

FPS = 250'000 / Ticks

Почему 250'000? Потому что 250 кГц — это 250'000 тиков в секунду. Если кадр занял Ticks тиков, то в секунду таких кадров поместится ровно 250'000 / Ticks.

Результат отправляется в serial‑порт пятью цифрами — чтобы можно было читать прямо в мониторе порта, не подключая ничего лишнего.

struct FTimerFPS
{

public:
    static void Initialize()
    {
        TCCR1A = 0; TCCR1B = (1 << CS11) | (1 << CS10);
    }
    
    static void Start()
    {
        TCNT1 = 0;
    }
    
    static void End()
    {
        uint16 Timer = TCNT1;
        
        FSerial::Send(( Timer / 10000)      + '0'); 
        FSerial::Send(((Timer / 1000) % 10) + '0');
        FSerial::Send(((Timer / 100) % 10)  + '0');  
        FSerial::Send(((Timer / 10) % 10)   + '0');
        FSerial::Send(( Timer % 10)         + '0');
        FSerial::Send('\n');
        FSerial::Send('\r');
    }
};

Цифры

А теперь самое интересное. С дисплеем ST7735 картина такая:

4.82 FPS. Мягко говоря, не густо. Но не спешите закрывать статью.

Дело в том, что основной тормоз — это не математика и не рендер, а сам дисплей. ST7735 общается по протоколу SPI, и каждая операция SetWindow + BeginDraw + Draw + EndDraw — это реальные транзакции на шине. На разрешении 160×128 мы за кадр прогоняем десятки тысяч пикселей, и большую часть времени процессор просто ждёт, пока дисплей их примет.

Поэтому я сделал замер с отключённым дисплеем (DEBUG_NO_ST7355). И вот тут моя математика показала себя во всей красе: От 10 до 15 FPS! (средняя 12)

То есть вся логика движка — обход секторов, порталов, проекция, клиппинг, fixed‑point — укладывается в 66–100 миллисекунд на кадр. Остальное съедает сам дисплей.

Ссылки

Весь код проекта лежит на GitHub: RootTool0/MicroBuild