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

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

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


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

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




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

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




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

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


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

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



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

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


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

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


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

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


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


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

Оставить комментарий