Да

Десятки лет мы задавались вопросом: «Запустится ли на этом устройстве Doom?». Теперь мы наконец можем задать вопрос иначе: «Запустится ли этот код в Doom?»

В статье я продемонстрирую, что в Doom можно запускать любые конечные вычисления, если не учитывать ограничения размеров уровня. Я не доказал, что Doom полон по Тьюрингу (см. ниже).

Система отлично работает с «ванильным» релизом Doom 2 (v1.9) для MS-DOS. Никаких модов и тому подобного не требуется!

Я люблю подобные проекты. Меня вдохновляют эзотерические машины в других играх, например, в Minecraft и RollerCoaster Tycoon.

Демонстрация

Исходный код

На случай, если кому-то интересно, как это работает, я опубликовал исходный код для создания карты:

https://github.com/nukep/doom-calculator

Связанные проекты

В комментариях мне сообщили, что были предприняты столь же впечатляющие попытки демонстрации вычислений в «ванильных» и «неванильных» движках!

• Игра «Жизнь» в BOOM: https://www.doomworld.com/forum/topic/131881-conways-game-of-life-in-boom/
• Doom в Doom: https://www.youtube.com/watch?v=c6hnQ1RKhbo (строго говоря, это эксплойт для исполнения произвольного кода, но всё равно круто)
• https://calabi-yau.space/blog/doom.html [перевод на Хабре] (логические вентили на основе лифтов из «ванильного» Doom.)
• Скрипт Voodoo: https://doomwiki.org/wiki/Voodoo_script (в основном BOOM и полы из конвейерных лент, однако с некоторыми возможностями «ванильного» Doom)
• Каскадный сумматор в BOOM: https://www.youtube.com/watch?v=pvji3DJNnqE, https://www.doomworld.com/idgames/levels/doom2/Ports/a-c/counter

NAND: универсальный логический вентиль

Моей первой попыткой исследования этой темы стала реализация вентиля NAND. Если я смог бы реализовать NAND, то смог бы реализовать что угодно.

NAND — это универсальный логический вентиль. Если вкратце, универсальные логические вентили можно соединять для создания всех возможных логических вентилей.

Таблица истинности NAND:


Например, если a True и b True, то результат будет False.

NAND состоит из двух входов «включено/отключено» и одного выхода «включено/отключено». Если оба входа включены, то выход отключен. Если один из входов отключен, то выход включен.

Оказывается, можно комбинировать NAND (подавать выходы NAND на другие NAND) и создавать любые таблицы истинности. По сути, возможны любые конечные вычисления.

Чтобы разобраться, возможно ли это в Doom, я поэкспериментировал с редактором уровней Doom под названием SLADE. Мне достаточно было реализовать один вентиль NAND. После кучи экспериментов с лифтами, действиями, телепортами, переключателями, дверьми, монстрами и даже клонами игроков я нашёл простую и надёжную систему.

Бинарные диаграммы решений

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

Описанный выше NAND мы можем представить при помощи бинарной диаграммы решений.


Есть два узла для переменных a и b. Пунктирными линиями обозначено «отключено», или 0. Сплошными линиями обозначено «включено», или 1.

Если мы начинаем с «a» и «a» равно 0, то мы перейдём налево и придём к результату «1»; наша работа на этом завершена. Но если мы начнём с «a» и «a» равно 1, то перейдём направо и придём к «b». Если «b» равно 0, то результат равен «1». Если «b» равно 1, то результат равен «0».

Мы можем объединять NAND в цепочки и создавать ещё более сложные диаграммы. Но в данном случае я решил отказаться от простого объединения NAND, потому что это создаёт не очень эффективные диаграммы. На практике лучше создавать цепочки из других логических вентилей, например, AND, OR, XOR и так далее, или напрямую преобразовывать таблицу истинности в диаграмму.

В виде уровня Doom

Как выглядит вентиль NAND (a=1, b=0):


Бинарные диаграммы решений можно представить в Doom очень простым образом.

Узел превращается в небольшую комнату с двумя дверьми для 0 и 1. В корневых узлах находятся монстры.

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

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

Я принял решение обозначить 0 и 1 двумя переключателями. Поначалу кажется логичным иметь по одному переключателю для каждой переменной. Но мне показалось проще явно задавать переменную как 0 или 1, а для вычислений ждать, пока они будут заданы.

В готовом файле WAD калькулятора у меня есть отдельные переключатели для каждой цифры, но это всего лишь визуальная иллюзия. На самом деле это переменные, где каждые пары 0/1 разделены на две цифры: (0,1) -> a; (2,3) -> b; (4,5) -> c; (6,7) -> d; (8,9) -> e. Например, «6» означает «d=0», «7» означает «d=1».

Как складывать числа при помощи этой системы?

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

Мы прошли путь от NAND до бинарных диаграмм решений. Теперь давайте попробуем сложить две двоичные цифры.

Существует две двоичные цифры: 0 и 1.

Правила сложения двоичных цифр таковы:


Мы также можем решить интерпретировать эти правила как таблицу истинности. Это называется полусумматор.

Полусумматор — эквивалент логических вентилей:

• перенос = a and b
• сумма = a xor b

Это отлично подходит для сложения двух двоичных цифр… но нам нужно складывать числа побольше!

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

Например, с такими тремя членами: «1 + 0 + 1 = 0, перенос 1».

Полный сумматор эквивалентен таким логическим вентилям:

• перенос = (a and b) or (b and c) or (c and a)
• сумма = a xor b xor c

Теперь мы можем объединить в цепочку полусумматор со множеством полных сумматоров, чтобы создать n-битный сумматор (где n — нужное нам количество битов). Это работает точно так же, как обычное сложение: складываем два числа, затем переносим 1 в левую пару цифр, потом складываем их, и так далее.

Нас интересует сложение чисел от 0 до 9. Как нам это описать? Оказывается, для описания чисел от 0 до 9 нам нужно не менее 4 двоичных цифр (где 0 = 0000, а 9 = 1001). Следовательно, мы используем 4-битный сумматор.

Однако у нас есть серьёзная проблема: нам нужно отображать результаты по основанию 10, а не в двоичном или шестнадцатеричном виде.

Решением будет преобразование результатов 4-битного двоичного сумматора. Получившаяся логика называется BCD adder (двоично-десятичным сумматором).

Если результат больше 9, то мы прибавляем 6. Применяем деление на 8 с остатком. В конце устанавливаем флаг переноса.

Таким образом, операция вида «9 + 5 = 14» даст нам «1001 + 0101 = 0100, перенос 1».

Псевдокод BCD adder:

# 4-битное двоичное сложение
# результат - это бит переноса, а затем биты суммы
zc,z3,z2,z1,z0 = cin + (a3,a2,a1,a0) + (b3,b2,b1,b0)

# если результат 4-битного двоичного сумматора > 9, задаём бит переноса "cout"
cout = zc or (z3 and z2) or (z3 and z1)

# Если результат 4-битного двоичного сложения > 9, прибавляем 6 (0110) и делим на 8 с остатком
     s0 =       z0
cc1, s1 =       z1 + cout  # полусумматор (2 члена)
cc2, s2 = cc1 + z2 + cout  # полный сумматор (3 члена)
_,   s3 = cc2 + z3         # полусумматор (2 члена)

Получившаяся бинарная диаграмма решений (неоптимизированная) выглядит следующим образом (входные переменные выделены синим, временные переменные — жёлтым):


Полная версия находится здесь

Подведём итог: представленная выше диаграмма описывает сложение двух цифр от 0 до 9 и получение цифры от 0 до 9 с переносом.

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

Чтобы визуализировать приведённую выше диаграмму с монстрами и телепортами, в вершине каждого дерева (корневом узле) будет находиться монстр. Все некорневые узлы будут точками перемещения для монстров. Всего есть 14 монстров, по одному для 14 деревьев.

Связывание выходов с переменными

Чтобы собрать диаграммы из множества мелких диаграмм, полезно будет сказать: «этот выход должен быть переменной». Возможно, вы заметили, что BCD adder зависит от этого.

Для уровня Doom это обозначает следующее: «проходящий через телепорт монстр должен открывать другие двери».

В «ванильном» Doom монстры не могут активировать переключатели или дистанционно открываемые двери. Поэтому я решил использовать особенность движка Doom. Все двери ассоциированы с сектором. Если дверь имеет общий сектор с другой дверью, то эти две двери всегда будут открываться и закрываться вместе. Монстры не могут открывать далёкие двери, однако могут открывать локальные двери. Если эта локальная дверь имеет общий сектор с другими дверьми, то монстры могут дистанционно открывать двери!

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

У этой особенности есть различные ограничения. Например, общие секторы должны иметь точно такие же текстуры пола и потолка, а также высоты. К счастью, это не влияет на функциональность, поэтому устраивает нас. Многие редакторы уровней Doom (например, SLADE) при редактировании отдельных полигонов пытаются сделать секторы «необщими», поэтому если вы захотите позже отредактировать карту, это нужно делать внимательно.

Отображение цифр

Я решил, что просто показывать двоичные значения было бы скучно. Мне нужно проделать весь путь и показывать настоящие числа.

Для отображения цифр я создал таблицы истинности для каждого пикселя дисплея.

Число от 0 до 9 можно представить 4 двоичными цифрами (0/1). Например, я возьму пиксель в строке 1, столбце 2 и покажу его таблицу истинности. Учтите, что для удобства чтения я свёл 4 входа в один столбец таблицы.


Её можно выразить как следующую бинарную диаграмму решений:


Двоичные значения с 10 по 15 не определены (undefined), потому что мы не ожидаем их встретить. Написанный мной алгоритм генерации диаграммы назначает произвольные выходы значениям с 10 по 15, в зависимости от которых происходит дальнейшая оптимизация диаграммы. (На практике для цифр «bit 3=1» просто означает 8 и 9. Если 8 и 9 имеют одинаковый результат, то мы знаем результат для «bit 3=1».)

Генерация уровня при помощи кода

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

Код генерации файла WAD написан на языке программирования Clojure.

Lisp подчиняется философии «код — это данные», поэтому древовидные структуры в виде кода писать получается достаточно интуитивно.

Мы можем описать вентиль NAND при помощи синтаксиса Lisp.

;; a NAND b:
(a 1
   (b 1
      0))

Это древовидная структура данных. Она состоит из вложенных списков в виде (variable on-0 on-1).

Также это можно визуализировать как идущее вбок дерево, считываемое слева направо:


Но самое замечательное в том, что всё это одновременно работает и как код. Если a и b — это функции, возвращающие левую или правую форму, то можно действительно это выполнить и получить результат!

;; функция, возвращающая right
(defn a [left right] right)
;; функция, возвращающая left
(defn b [left right] left)

(a 1
   (b 1
      0))
;; returns 1

В очень кратком синтаксисе мы можем реализовать более сложную логику:

;; Полный сумматор

;; Дерево 1: бит суммы
(cin (a (b 0 1)
        (b 1 0))
     (a (b 1 0)
        (b 0 1)))

;; Дерево 2: бит переноса
(cin (a 0
        (b 0 1))
     (a (b 0 1)
        1))

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

Однако многие бинарные диаграммы решений представляют собой не деревья, а графы. Узлы в бинарной диаграмме решений могут иметь несколько родителей. Как же выразить графы?

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

Оптимизация деревьев

Для оптимизации деревьев я использую различные методики:

1. Если дерево «a» указывает на деревья «b» и «c», и при этом b = c, то a = b = c
2. Если переменная «v» используется в другом месте только один раз, находится в корневом дереве «a», и дерево указывает на деревья «b» и «c», то v.0 = b и v.1 = c
3. Удаляем все деревья, которые в конечном итоге не влияют на выходы (где могут появиться монстры).

Оптимизацию 3 я решил реализовать при помощи матриц смежности. Пусть K — матрица смежности деревьев к деревьям; я вычисляю K^0 + K^1 + K^2 + ..., что даёт нам окончательный результат всех достижимых деревьев. Код для этого находится здесь: https://github.com/nukep/doom-calculator/blob/e3dd9c0c6de19830febd0d1f845befca70ad632d/src/doomcalc/tree.clj#L217

Отрисовка уровня

Уровни Doom хранятся в формате WAD. Согласно «Библии Doom» Тома Холла, WAD официально расшифровывается как «Where's All the Data?».

Несмотря на то, что игра трёхмерная, карты Doom существуют на плоской декартовой плоскости. Высота создаётся присвоением полигональным фигурам на карте переменных высот полов и потолков (в Doom эти фигуры называются «секторами»).

К счастью, WAD — очень простой формат файлов, поэтому мне удалось с нуля написать программу создания WAD.

Так как уровни задаются в 2D, процедуры отрисовки уровня схожи с функциями отрисовки векторной графики, например, «нарисовать линию из a в b».

Обходим особенности «ванильного» Doom

Я заметил, что открывающие двери монстры работали в GZDoom, но иногда не работали в Chocolate Doom или в «ванильном» Doom для MS-DOS.

Чтобы разобраться, почему так происходит, я поступил как любой разумный человек: заглянул в исходный код Doom. (Конечно, всё, что я делал до этого, было абсолютно разумным.)

Официальный релиз исходного кода Doom компании id Software можно найти здесь: https://github.com/id-Software/DOOM.

При помощи Ctrl+F я поискал ключевые слова наподобие «open» и «door», в конечном итоге обнаружив код, где монстры пытаются самостоятельно открывать двери.

Я начал со следующей функции P_Move(): https://github.com/id-Software/DOOM/blob/77735c3ff0772609e9c8d29e3ce2ab42ff54d20b/linuxdoom-1.10/p_enemy.c#L272.

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

# p_enemy.c: P_Move()
def P_Move(actor):
    # Направление - это единичный вектор. 1 из 8 возможных направлений (с инкрементом в 45 градусов).
    try_position = actor.position + actor.speed*actor.direction

    actor_moved = False

    # p_map.c: P_TryMove(), P_CheckPosition()
    spechit = []
    for each line within the actor radius from try_position:
        # p_map.c: PITCheckLine()
        # Примечание: линии разделены на blockmap (секции уровня 128x128).
        # Blockmap проверяются снизу вверх, а затем слева направо. (буквой N)
        if line has no back face: break
        if line blocks players or monsters: break
        if line has a special action: spechit.push(line)

    if loop did not break:
    if new floor is within 24 units (not too high or low):
    if actor can fit in the room:
        move the actor to try_position
        actor_moved = True
        for each line in spechit, in reverse order:
            if actor walks over line: trigger line
        spechit = []

    if not actor_moved:
        for each line in spechit, in reverse order:
            use line
        spechit = []

Вот самые важные открытия:

• Игра ищет все особые линии в радиусе действия монстра, от которых монстр пытается двигаться (а не оттуда, где находится).
• Существует глобальный массив, добавляемый с особыми линиями «spechit». Может храниться до восьми таких линий, но игра не останавливается на восьми (возможно, переполнение буфера).
• Поиск по blockmap выполняется начиная со столбцов (снизу вверх, затем слева направо)
• Процедура итерации прекращается, если у любой из линий в радиусе действия монстра имеется включённый флаг «block players» или «block players and monsters».
• Также она прекращается, если находит стену без обратной грани (например, внешнюю грань карты).

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

• В пределах радиуса+скорости монстра нет линий с флагами «block players/monsters» (для розового демона: 30.0 + 10.0 = 40.0 единиц)
• В пределах радиуса+скорости монстра (40.0 единиц) нет односторонних линий (например, периметра карты)
• Все двери, которые не нужно открывать монстрам, должны находиться вне пределов радиуса+скорости монстра (40.0 единиц)

В оригинале статьи есть интерактивное демо, симулирующее дисплей цифр.


Оно полностью соответствует тому, что происходит на карте Doom.

Значит ли это, что Doom полон по Тьюрингу?

Мои наблюдения этого не подтверждают. Однако это может быть потрясающим утверждением, ведь оно означало бы, что мы можем запустить что угодно, включая и сам Doom (конечно же, если устранить ограничения карт и памяти).

Проект «Doom-in-Doom» использует эксплойт с исполнением произвольного кода для запуска Doom в Doom: https://www.youtube.com/watch?v=c6hnQ1RKhbo. Он невероятно впечатляет! Также стоит заметить, что для выполнения логики он использует не механизмы Doom, а сразу спускается на уровень оборудования и выполняет машинный код (и его точно нельзя портировать за пределы «ванильного» или Chocolate Doom!).

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

Чтобы Doom был полон по Тьюрингу, он должен позволять выполнять какую-нибудь конструкцию неограниченного цикла.

Моя система неполна по Тьюрингу, потому что в ней нет неограниченных циклов и состояния. Когда монстры добираются до своей конечной точки, они остаются там навечно. Нет никакого способа «сбросить» монстров. Возможно, это можно сделать селективным повторным вызовом (телепортацией) определённых монстров, чтобы они могли использоваться в качестве входов для следующей итерации вычислений. Вероятно, это был бы следующий этап доказательства того, является ли Doom полным по Тьюрингу.

Оптимистично ли я настроен относительно его полноты по Тьюрингу? Ещё как! Но чтобы судить об этом с уверенностью, нужно проделать дополнительную работу.

Если в конечном итоге окажется, что он полон по Тьюрингу, то мы сможем доказать полноту по Тьюрингу, реализовав что-то, обладающее таким свойством. Если мы сможем реализовать конвеевскую игру «Жизнь» или правило 110, то это будет достаточным доказательством. (Мне нравится идея игры «Жизнь» из-за ироничности реализации «Жизни» в видеоигре, посвящённой убийству демонов).

Дополнение: игра «Жизнь» работает в Doom! Для её запуска нужен более новый движок, совместимый с BOOM: https://www.doomworld.com/forum/topic/131881-conways-game-of-life-in-boom/.

Другие люди тоже реализовали логические вентили в Doom!

Я с перерывами работал над этим проектом в течение двух с лишним лет. За это время меня обогнал Джаред Канделариа! Он даже придумал похожее название для статьи.

https://calabi-yau.space/blog/doom.html [перевод на Хабре]

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

Скачать WAD

Запускать карту я рекомендую в современном порте исходников наподобие GZDoom.

Также я выложил версию WAD, работающую в релизе Doom 2 (v1.9) для MS-DOS, однако она имеет множество графических глитчей. Впрочем, она функциональна и обладает всеми ограничениями «ванильного» Doom!

Вот она! https://github.com/nukep/doom-calculator/releases/