Можно, но зачем: 7 фигур и 19 положений того самого Тетриса

Троллейбус из буханки хлеба везёт тетромино в стакан

Есть старый мем: а что, если сделать троллейбус из буханки хлеба? Можно, но зачем. В исходнике того самого Тетриса, который Алексей Пажитнов написал для Электроники-60 в ВЦ Академии наук, есть процедура ровно такого устройства. Игра тратит 958 байт кода на то, чтобы при каждом запуске заново вычислить 342 байта данных: семь фигур, их девятнадцать положений и правила поворота. Готовую таблицу можно было положить в программу и не вычислять ничего.

Код игры восстановлен: он компилируется байт в байт в тот же файл, что снят с ленты. Все 590 строк можно открыть и читать.

Фигура в Тетрисе это тетромино: четыре клетки, склеенные сторонами. Разных тетромино семь, и называть их принято латинскими буквами, похожими по очертанию: I, O, T, S, Z, J, L. Давайте посмотрим, как игра строит эти семь фигур и их производные положения.

Фигура: четыре смещения

Сегодня тетромино описали бы битовой картой четыре на четыре. В этой игре фигура устроена иначе:

TYPE
  VEC4 = ARRAY[1..4] OF INTEGER;
  SHP  = RECORD
           DX, DY : VEC4
         END;

Запись SHP хранит четыре пары смещений от точки отсчёта. У буквы T это DX = (-1, 0, 1, 0) и DY = (0, 0, 0, 1): три клетки в ряд и одна под центральной. Пустых клеток в такой записи нет вообще, хранятся только четыре занятые.

Фигура и её таблица смещений: клетке k соответствует пара DX[k], DY[k]

Длина массива не просто так константа. Любое тетромино состоит ровно из четырёх клеток, поэтому VEC4 объявлен как ARRAY[1…4], и каждая фигура занимает восемь слов, шестнадцать байт. Лежат они в общем массиве SHAPE : ARRAY[1…19] OF SHP. Почему записей девятнадцать, а не семь, выяснится через два раздела.

Точка в стакане

Смысл смещений раскрывается вместе со стаканом. Поле хранится в двумерном массиве:

WELL : ARRAY[0..11] OF ARRAY[0..21] OF CHAR;

Игровых колонок десять, строк двадцать, а массив на две больше в каждом измерении: крайние колонки и строки заполнены часовыми CHR(1) и изображают стенки и дно.

Падающая фигура в стакане это одна точка. Текущая позиция XPOS, YPOS плюс указатель CUR на одну из записей SHAPE. Клетки достраиваются к точке: движок четыре раза прибавляет к ней очередную пару смещений и получает координату клетки. Так фигура рисуется на экране, и так же она вписывается в стакан при посадке:

WITH CUR^ DO
  FOR I := 1 TO 4 DO
    WELL[XPOS+DX[I], YPOS+DY[I]] := CHR(1);

Сдвинуть фигуру влево значит уменьшить XPOS на единицу. Четыре клетки при этом не трогаются, они пересчитаются из новой точки при следующей отрисовке.

Перед каждым сдвигом та же арифметика отвечает, поместится ли фигура на новом месте:

FUNCTION CANFIT(X, Y : INTEGER) : BOOLEAN;
VAR K : INTEGER;
BEGIN
  CANFIT := TRUE;
  WITH CUR^ DO
    FOR K := 1 TO 4 DO
      IF WELL[X+DX[K], Y+DY[K]] # CHR(0) THEN BEGIN
        CANFIT := FALSE;
        EXIT
      END
END;

Знак # в этом диалекте означает «не равно». Четыре проверки, и здесь окупаются часовые: выход за край упирается в CHR(1) рамки точно так же, как в осевшую клетку, отдельной проверки границ в игре не существует. EXIT обрывает цикл на первой занятой клетке, оставшиеся даже не читаются.

CANFIT: три шага проходят, на четвёртом третья клетка попадает в стенку

Одна заготовка на четыре фигуры

Теперь к рождению фигур. Таблицы в исходнике нет, вместо неё процедура SETUP, которая отрабатывает при каждом запуске, ещё до заставки. Квадрат она выводит из арифметики: DY[I] := I DIV 3 и DX[I] := -(I MOD 2) дают обход блока два на два. Дальше интереснее, четыре фигуры собираются из одной заготовки:

FOR J := 1 TO 4 DO
  WITH SHAPE[J+3] DO BEGIN
    FOR I := 1 TO 3 DO BEGIN
      DY[I] := 0;
      DX[I] := I-2          { тройка в ряд }
    END;
    DY[4] := 1;
    DX[4] := J-3            { четвёртая клетка едет вдоль ряда }
  END;
SHAPE[4].DY[4] := 0;

Три клетки в ряд неподвижны, четвёртая проходит под ними четыре позиции. Последние три дают L, T и J. А первая даёт фигуру, которой в игре нет: при J=1 четвёртая клетка встаёт по диагонали от тройки и касается её только углом. Это не тетромино. Следующая строка, SHAPE[4].DY[4] := 0, поднимает клетку в общий ряд, и не-фигура превращается в палку.

Заготовка: клетка проходит четыре позиции, снимки ложатся в SHAPE[4..7], заплата чинит палку

Несколько инструкций между циклом и заплатой в памяти Тетриса живёт фигура, которую никто никогда не видел на экране.

S и Z: две правки T

Оставшиеся две фигуры не строятся вовсе. Они копируются из готовой T, по одной правке на каждую:

SHAPE[2] := SHAPE[6];
SHAPE[2].DY[1] := 1;      { опустить левое плечо: S }
SHAPE[3] := SHAPE[6];
SHAPE[3].DY[3] := 1;      { опустить правое плечо: Z }

T раздваивается: у левой копии падает левое плечо, у правой правое

В сумме получается личная грамматика семи фигур: квадрат из формулы, четвёрка из заготовки с путешествующей клеткой, S и Z как мутации T. К классификациям тетромино из учебников она отношения не имеет. Это способ автора держать все семь фигур в голове, не записывая ни одной из них координатами.

Поворот, который ничего не вычисляет

Осталось объяснить девятнадцать. SETUP не останавливается на семи фигурах: каждую он прокручивает через процедуру ROTATE и складывает результаты в тот же массив как самостоятельные записи.

PROCEDURE ROTATE(S : SHP);
VAR M : INTEGER;
BEGIN
  WITH S DO BEGIN
    T.DX := DY;
    FOR M := 1 TO 4 DO
      T.DY[M] := -DX[M]
  END
END;

Поворот на девяносто градусов, (x, y) → (y, -x), вокруг той самой точки отсчёта. L, T и J поворачиваются трижды, S, Z и палка по одному разу, квадрат ни разу. Итого 1 + 3×2 + 3×4 = 19 записей: семь публичных фигур и двенадцать скрытых положений. Генератор случайных фигур выбирает только номера 1…7, это буквально RANDOM(7)+1 в коде; положения 8…19 наружу не выдаются никогда и существуют только как ступени колец поворота.

L поворачивается трижды вокруг точки отсчёта, результаты уезжают в SHAPE[11..13]

Кольца строит параллельный массив NXT: для каждого положения в нём лежит номер следующего.

O:  1 -> 1
S:  2 <-> 8      Z:  3 <-> 9      I:  4 <-> 10
L:  5 -> 11 -> 12 -> 13 -> 5
T:  6 -> 14 -> 15 -> 16 -> 6
J:  7 -> 17 -> 18 -> 19 -> 7

В рантайме от поворота остаётся переход по кольцу:

OLD := CUR;
CUR := @SHAPE[NXT[CURPC]];
IF CANFIT(XPOS, YPOS) THEN CURPC := NXT[CURPC]
ELSE CUR := OLD;

Кнопка 8 не вращает ничего. Она берёт соседнюю запись массива и проверяет её всё тем же CANFIT; если новое положение не влезло, указатель возвращается на старую запись, и фигура остаётся как была. Двенадцать поворотов при запуске, ноль поворотов во время игры.

Две детали для любителей археологии. Кольца из двух элементов у S, Z и палки не прихоть: второй поворот даёт ту же фигуру, но сдвинутую на клетку, и кольцо из четырёх записей заставляло бы фигуру уезжать вбок при каждом полном обороте. А замыкаются длинные кольца перезаписью: внутренний цикл сначала честно пишет NXT[19] := 20, ссылку на положение, которого не существует, и только следующий оператор загибает её обратно, NXT[19] := 7. Проверки диапазонов выключены директивой ($T-), и до конца SETUP висящая ссылка никому не мешает.

Почему параметр ROTATE объявлен по значению

В цикле поворотов ROTATE вызывается как ROTATE(T): переменная T здесь одновременно источник и приёмник. Внутри процедуры сначала выполняется T.DX := DY, что затирает половину T, и только потом цикл читает DX. Работает это лишь потому, что S копия аргумента. Объяви автор параметр как VAR, чтение пошло бы по уже затёртой памяти, и все повороты после первого дали бы мусор.

Цена вопроса

Оба варианта я собрал тем же компилятором, которым собран оригинал. Генератор занимает 958 байт кода. Готовая таблица, те же данные плюс цикл копирования, укладывается в 384 байта: 342 байта на 171 слово (19 фигур по 8 слов и 19 переходов NXT) и 42 байта кода. Разница 574 байта, соотношение два с половиной к одному. Для масштаба: весь код игры это 7338 байт, на рождение фигур уходит 13% программы.

Дороже всего обходится кодогенерация. Компилятор разворачивает каждое SHAPE[I*3+7+J].DY[M] в цепочку сложений и сдвигов, WITH заново пересчитывает базу записи, а ROTATE вызывается двенадцать раз и всякий раз копирует восьмисловный аргумент. Чтобы получить 171 слово данных, SETUP выполняет 297 записей в память, не считая копий параметра.

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

Троллейбус, который поехал

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

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

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

Сорок лет спустя код всё чаще пишет машина, а человеку остаётся описание. Этот исходник устроен так с самого начала. Троллейбус из буханки, который поехал.

Гифка из прошлого поста, для вайба

---

Восстановленный исходник, модули рантайма и цепочка сборки настоящим ПАСКАЛЬ/РАФОС: n0isy/original-tetris-recomp.