DOOM (игра 1993 года для DOS) полон по Тьюрингу. Это значит, что можно запустить DOOM в DOOM. В статье приводятся подробности реализации.

Предисловие

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

Что такое полнота по Тьюрингу?

Итак, какую-то видеоигру можно назвать универсальной, полной по Тьюрингу или программируемой. Что это означает? По сути, это значит, что в этой игре можно реализовать компьютер. Но тут есть свои тонкости: если для этого игроку придётся делать слишком много, то это будет уже не так интересно.

Нам нужно что-то, происходящее «неизбежно». Существует множество формулировок машин Тьюринга, но в целом их можно представить как небольшие машины, способные работать автономно, получать ввод при запуске и передавать вывод при завершении работы. Разумеется, если они закончат работу. Под «работой» подразумевается выполнение некой последовательности команд. Есть и другие более тонкие технические аспекты, но в целом это описание даёт достаточное понимание концепции. Верьте или нет, но любая машина, способная на это, в принципе способна вычислить всё, что может представить человек. Конечно, я слишком упрощаю и здесь есть множество нюансов, но давайте не будем пока придираться к определению тезиса Чёрча-Тьюринга.

Вычисления обманчиво просты. Я опущу мистические и философские аспекты этого понятия, и сведу всё к конкретной задаче: может ли конкретная система симулировать вентиль NAND? Если ответ положительный, то это компьютер. Для наших целей он принципиально не отличается от любого другого компьютера. Для справки: вентиль NAND получает два сигнала на вход и возвращает «ложь» тогда и только тогда, когда оба сигнала истинны.

Но в вашем компьютере, вероятно, есть видеокарта, какой-то накопитель, память, не говоря уже об одной-двух сетевых картах, интерфейсах USB и т. п. Всё это правда, но это не относится к нашей теме. Если упростить, то всё вышеперечисленное можно собрать из вентилей NAND, а если нет, то компоненты, не состоящие из вентилей NAND, «просто» передают сигнал чему-то, что колеблет мембрану, возбуждает ячейку или выполняет нечто независимое от задачи, которой занята машина Тьюринга. На практике реальные устройства представляют собой нечто большее, чем просто вентили NAND, и устройства ввода-вывода безумно сложны. Но реальная жизнь всегда сложна, так что давайте просто приступим к созданию симулятора!

Примитивы карт DOOM

Теперь, когда у нас есть цель, нам нужно понять, с чем мы работаем. Я не буду полностью перечислять функции движка DOOM и вместо этого сосредоточусь только на аспектах, важных для готового результата. Сообщество любителей DOOM придумало невероятно богатый и обширный набор методов (например, DeHackEd, compatibility levels и т. д.) для улучшения игрового процесса, но мы не будем обращать на всё это внимание. Если вам интересно, то свяжитесь со мной, и мы всё это обсудим. Как бы то ни было, по сути, движок DOOM загружает карту, а затем симулирует происходящее с учётом последовательности ввода пользователя. Карта содержит информацию о текстурах и геометрию в виде вершин, линий и секторов (состоящих из линий полигонов) с соответствующими метаданными (например, высотой потолка).

Вероятно, вы видели в игре подвижные полы, открывающиеся двери и мерцающие лампы, но как же их сделали? Именно для этого нужны «соответствующие метаданные». Допустим, у нас есть две комнаты, соединённые узким коридором. Когда игрок перебегает из одной комнаты в другую, он обязательно пересечёт линию в коридоре. К этой линии, которую движок называет linedef, можно привязать действие. Эти действия управляют динамическими эффектами освещения, лифтами, дверьми и т. п. Для реализации некоторых эффектов требуется передача действия всем объектам, имеющим некоторую метку. По сути, у одной linedef может быть одно действие, но оно распространяет своё влияние на несколько объектов (до восьми на такт игры). Истинные фанаты Doom знают о пропусках linedef и о том, что есть переключатели и двери, отличающиеся от linedef, но это уже находится за пределами темы нашей статьи.

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

Подведём итог: когда монстр пересекает линию на карте, могут запускаться определённые действия. Для нас важны активирование лифта и телепортация.

Синтез: DOOMHDL

Перечислив доступные нам примитивы, мы можем собрать из них что-то осмысленное. Для начала будет неплохо изучить полные по Тьюрингу системы и прикинуть, какую из них будет легче симулировать с помощью наших строительных блоков. Можно воспринимать триггеры DOOM как приблизительное подобие активации булевого значения. Но серьёзная проблема заключается в том, как «считать» эти активации. Нам нужно подавать выводы в качестве входов на следующем этапе работы. Если считать монстров блуждающей по миру энергией «инь», а триггеры — меняющей пространство мира энергией «ян», то мы приблизимся к решению. Мы можем заставить монстра пройти по триггеру, опускающему лифт. Затем задействованный лифт позволит второму монстру пройти по новым триггерам.

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

Теперь давайте реализуем несколько вентилей.

OR

Вентиль OR («ИЛИ») имеет два входа и возвращает true, если хотя бы один вход равен true. Мы можем сопоставить это с лифтом, который можно опустить двумя способами. Внутри DOOM каждый из этих способов будет соответствовать отдельной linedef, что точно соответствует входным сигналам вентилей OR.

Вы можете задаться вопросом, что DOOM сделает с лифтом, который мы активируем дважды. Очень проницательное замечание! Если вкратце, то DOOM НЕ хранит очередь триггеров и любой активный триггер является блокирующим. Это значит, что во время работы триггера все другие действия игнорируются. Это отлично нам подходит.

На рисунке выше показана реализация вентиля OR. В двух верхних нишах есть триггеры, которые вместе опускают тонкий зелёный сектор, блокирующий дорогу монстру. Эта связь показана двумя большими жёлтыми стрелками. Дальше по пути монстра есть телепорт, перемещающий монстра на исходную точку спауна, отмеченную пунктирной зелёной стрелкой. Не волнуйтесь, если телепорт находится так близко к вентилю, что пробежит через него несколько раз, то из-за того, как DOOM активирует лифты, он не будет ничего активировать дважды. Последнее, на что нужно указать на рисунке — это серая линия между зелёным сектором и телепортом. Эта небольшая linedef обозначает вывод вентиля.

AND

Вентиль AND («И») имеет два входа, он получает значение true, только если ОБА входа равны true. Мы можем реализовать его при помощи двух отдельных лифтов: монстр может пройти, только если опущены оба.

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

NOT

Вентиль NOT («НЕ») имеет только один вход и инвертирует его: true становится false, а false становится true. Звучит достаточно просто, пока дело не доходит до реализации. Так как в нашей схеме сигналами считаются демоны, то как мы можем материализовать их из пустоты в случае false? Наша предыдущая схема, при которой стены опускались, обеспечивая проход, здесь не сработает. Вместо этого у нас будут полы, которые превращаются в «траншеи», мешающие проходу.

Он имеет все компоненты вентиля OR: монстра, сам вентиль, выходной linedef и телепорт. Но здесь можно заметить нечто новое: небольшую выемку в левой части вентиля. Она управляет глубиной траншеи (стоит вспомнить, что лифты в DOOM спускаются до высоты самого низкого соседнего сектора). В этом случае мы можем установить вентиль по умолчанию (т. е. в случае false) на обычной высоте пола, но опускать его при установке бита (т. е. в случае true), препятствуя движению.

Повторитель

Это несложный вентиль, он «необходим» только потому, что я перемудрил с задачей. Можно воспринимать его как вентиль равнозначности, то есть повторяющий своё входное значение: true -> true, false -> false. Меня беспокоило согласование по времени, и вместо того, чтобы поразмыслить побольше, я просто сделал так, чтобы всё занимало постоянное количество времени. Теперь мне не придётся решать проблемы с возможными задержками распространения.

Инженерные заметки

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

Ещё один аспект тонких секторов заключается в управлении лифтами. DOOM опускает лифт до самого низкого соседнего сектора. Это свойство используется в вентиле NOT.

Вы можете задаться вопросом о синхронизации. И это отличный вопрос. Да, вентили работают достаточно хорошо, но как соединять их в цепи? Если просто связать их вместе, то они всегда будут активны, что может вызвать проблемы по двум причинам: 1) монстры увеличивают вероятность того, что они будут стоять на вентиле, когда он должен деактивироваться, и 2) схему невозможно будет отключить!

Эти проблемы можно решить добавлением сигнала синхронизации. Сигнал будет отвечать за выбор активного вентиля. Это можно реализовать, поместив монстра с вентилем на остров, который опускается только по сигналу синхронизации. Остальные вентили останутся неизменными. На показанных выше рисунках этому соответствует круглая текстура (можно считать её циферблатом часов) на острове монстра. Если входы вентиля будут присутствовать до того, как сигнал синхронизации активирует вентиль, то вентили точно будут передавать свой истинный выход правильно.

И в этом заключается недостаток сигнала синхронизации CLK. Сигналы на входах должны прибыть до того, как CLK активирует вентиль. Для вентилей AND и OR это не представляет особой проблемы, но критично для вентиля NOT. Я кучу времени разбирался, почему схема работала в первый раз а потом только через раз. Проблема заключалась в том, что монстр опускался и пересекал вентиль до того, как он превратится в траншею. Из соображений синхронизации путь CLK расположен таким образом, чтобы каждая фаза запускалась только после завершения предыдущей. Вероятно, здесь можно реализовать ещё много оптимизаций, но такое решение меня устроило.

ДЕМОНстрация: полусумматор

Теперь, когда у нас есть удобные строительные блоки, самое время построить что-то реальное. Очевидным выбором будет вентиль NAND. Но хотя это логично, такой проект будет слишком простым. Более эффектной демонстрацией был бы простой ЦП, но для него потребовалось бы слишком много времени. Поэтому я выбрал нечто чуть более интересное, чем вентиль NAND: полусумматор. Эта схема, по сути, складывает два бита, выводя сумму (mod 2) и перенос. Конкретнее, она имеет 4 возможных ввода и 3 возможных вывода.

Традиционно схема выглядит так:

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

А вот видео работы устройства:

Готовый файл

На случай, если вы захотите поэкспериментировать с картой, её можно скачать отсюда. Стоит открывать её в редакторе карт Doom. Я для этого использовал Doom Builder.

Ограничения

Так как движок DOOM не задумывался как интерпретатор, на наши программы накладываются определённые ограничения. Самое важное — это ограничение на размер программ. Так как в каждом вентиле используется как минимум одна метка, мы можем использовать её как метрику для вычисления верхней границы размера программы. В движке DOOM используются 16-битные метки, то есть можно создать максимум 65535 вентилей. Это не особо большое число. Мы смогли бы реализовать очень маленький ЦП, но мне кажется, достаточно быстро столкнулись бы с этим ограничением.

Ещё одно очевидное ограничение — вывод системы. Так как вывод должен запускаться монстрами, из которых состоит система, он может срабатывать только от телепорта, лифта или от открывающего дверь монстра. Вероятно, в более современных портах есть дополнительные возможности. Как минимум, можно использовать кукол вуду и конвейеры из BOOM, чтобы получить более интересный вывод. Впрочем, я не изучал этот вопрос, поэтому это только мои рассуждения.

Подводим итоги

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

Некоторые читатели могут задаться вопросом, зачем я решил пойти на этот эксперимент, поэтому скажу, что мне просто понравилась идея. Не помню точно, как она появилась в моей голове, но примерно месяц назад я понял, что DOOM может быть полон по Тьюрингу. Сначала я не особо думал над этой идеей, но постепенно начал убеждать себя в этом. Мне достаточно было списка действий linedef; я даже не читал никакого кода. Единственное, о чём жалею, так это об отсутствии в статье отсылок к мему «А DOOM в нём запустить можно?».

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