[Перевод] Запустится ли это в Doom? Калькулятор, работающий на демонах

;; функция, возвращающая 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/

 

Источник