Хабрахабр

[Перевод] Игра Cities: Skylines оказалась Тьюринг-полной: создаём 4-битный сумматор

Cities: Skylines — это игра-симулятор города, обладающий достаточной сложностью, чтобы создавать в нём универсальные логические элементы. При помощи универсальных логических элементов можно построить любую схему, в том числе и Тьюринг-полные машины. То есть как и в Minecraft, мы можем создать внутри Cities: Skylines компьютер. Однако было бы очень трудно создавать на основе этих элементов полнофункциональный компьютер, поэтому я продемонстрирую вместо него 4-битный сумматор. Всё выполняется в ванильной версии игры, не требуется ни модов, ни дополнений.

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

Основные участники, слева направо: электростанция на жидком топливе, водонапорная башня, канализационная труба. Сзади стоит ветровая турбина.
Ниже показан способ построения элемента AND. Двумя входами являются линии электропитания, идущие к водонапорной башне (сверху) и канализационной трубе (внизу). Выходом является линия электропитания, подключенная к электростанции. Хотя на скриншоте входы равны нулю, электростанция всё равно вырабатывает электричество — даже после завершения подачи воды и работы стоков ей требуется какое-то время для остановки. Здания разнесены далеко друг от друга, потому что в противном случае электричество могло бы свободно течь между ними.

Элемент AND на обычной карте, показаны слои электричества и воды.

Чтобы создать его, мы воспользуемся симуляцией динамики жидкостей игры. Для функциональной полноты нам требуется ещё один компонент: инвертор, или элемент NOT. Затопленная электростанция не вырабатывает электричество. Неправильное использование дамб, каналов или слишком большая нагрузка на канализацию могут привести к затоплению зданий. Этого достаточно для создания показанного ниже элемента NOT.

Сверху: слой электричества элемента NOT, снизу: отключенная и включенная канализация.

Четыре таких сумматора можно соединить в цепочку и создать 4-битный сумматор. 1-битный сумматор можно построить по схеме из 9 разных элементов, показанной ниже. Я расположил логические элементы в сетке, чтобы показать, как они будут размещаться на карте.

Схема 1-битного сумматора с переносом.

В редактор можно импортировать PNG-изображения, которые используются для загрузки карты высот. Чтобы упростить себе жизнь, я решил включить бесконечные деньги и играть на карте, созданной в редакторе карт. Вот как выглядит карта. Я создал карту с блоками земли, на которых можно расположить логические элементы как на печатной плате! На изображениях показаны четыре 1-битных сумматора, повторяющихся в сетке 2x2.

На изображении видны ломаные линии, потому что игра не очень хорошо обрабатывает чёткие края.

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

1-битный сумматор. Я соединил вместе четыре таких элемента.

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

Паутина линий электропередач, ведущая к одному из 4-битных входов.

В первом я задал сигнал на входе, присоединив его к постоянно включенной электростанции (как питание интегральной схемы). Я записал видео, чтобы показать, что сложение действительно работает. После задания значений входов я ускорил игру и выход на правых пяти проводах принял значение из одних единиц. Слева я задал значение 1001 (=9), посередине 1110 (=14). И в самом деле работает! Спустя долгое время окончательное значение установилось на 10111 (=23).

Во втором видео я сфокусировался на одном из сумматоров. Можно увидеть, как изменяется со временем состояние компонентов, пока не установится окончательное значение на выходе (0 — сумма, 1 — перенос).

Проект имеет некоторые изъяны. Из него получится очень медленный компьютер — одно 4-битное сложение занимает примерно 15 месяцев внутриигрового времени и около 20 минут реального. Есть проблемы и с размером. Из-за того, как реализовано в игре электропитание, компоненты логического элемента должны быть разнесены достаточно далеко друг от друга; в противном случае ток будет течь между ними. 4-битный сумматор занял бОльшую часть из 9 тайлов, доступных в обычной игре, однако я не очень сильно его оптимизировал. С модами можно использовать до 25 тайлов. Если у вас есть идеи о том, как реализовать более эффективные вычисления, то напишите об этом в комментариях к оригиналу статьи!

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть