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

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

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


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

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




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

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




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

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


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

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



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

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


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

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


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

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


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


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

Комментарии 17

    +30
    Мисье знает толк…
      0
      Сразу вспомнилась цитата из «Честного трейлера» про компьютер в майнкрафте — «почему эти люди до сих пор не создали лекарство от рака?»
        +21
        Думаю все потому, что они изобретают велосипед, используя квадратные колеса. Что-то новое и полезное таким способом вряд ли создашь :)
        +1
        Спасибо за перевод! Не приходило в голову, что там можно такое сделать. Хотя я и вообще подобными извращениями не занимаюсь)
            +3
            8-Bit PC in Factorio Churning Away Fibonacci Numbers
              +2
              Факторио нечестная в этом плане –– там слишком много готовых логических гейтов и инструментов для создании схем :)
              0
              Страшно подумать, что такой автор может намоделировать в каком-нибудь LTSpice. Но почему-то майнкрафты им интереснее…
                0
                Потому что игра — интересный способ изучить тему.
                0
                Тут говорят про майнкрафт и про музыку… Хм, я тут подумал, раз уж там можно компьютер реализовать и легко создать мелодию из музыкальных коробок, то рано или поздно там точно появится аналог синтезатора.
                  0
                  Рано или поздно? В нём уже рейтрейсеры, компьютерные игры, тетрис, покемонов, двумерный Майнкрафт и что только ещё не создавали. Синтезатор это очень давно (уже как лет пять) пройденый этап. Просто всё это жутко медлено работает из-за малой частоты обновления редстоуновых компонентов и командных блоков.
                    +1
                    И здесь до сих пор не вспомнили Dwarf fortress?
                    The Dwarven Computer is finally complete!
                    image
                    I've tested it and it functions as expected, though its performance is really lousy.

                    This monumental build contains 672 pumps, 2000 logs, 8500 mechanisms and thousands of other assort bits and knobs like doors and rock blocks.
                    За подробностями ходить по этой ссылке: для просмотра карты сооружения, к сожалению, нужен Adobe Flash; есть ссылка на гуглодоку с описанием дизайна вычислительной части.
                      0
                      Тьюринговая полнота лезет изо всех дыр github.com/Microsoft/TypeScript/issues/14833
                        0
                        На паровозиках в openttd даже с семисегментным индикатором есть :)
                          +2
                          Скрытый текст
                          +1
                          В редактор можно импортировать PNG-изображения, которые используются для загрузки карты высот.

                          Туда можно импортировать изображения с 16 битами в градациях серого, вроде результат получается более сглаженным.
                          С модами можно использовать до 25 тайлов

                          Когда я в неё играл, были моды на все 91.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое