July 16, 2019 at 14:51The game Cities: Skylines turned out to be Turing-complete: we create a 4-bit adder
- Transfer
Cities: Skylines is a city simulation game with enough complexity to create universal logic elements in it. Using universal logic elements, you can build any circuit, including Turing-complete machines. That is, as in Minecraft, we can create a computer inside Cities: Skylines. However, it would be very difficult to create a full-featured computer on the basis of these elements, so I will demonstrate a 4-bit adder instead. Everything is done in the vanilla version of the game; no mods or add-ons are required.
This game, like any other city building simulator, requires the player to supply electricity and water to the city. Power plants generate electricity, for this they need clean water and sewage. Water towers supply clean water, sewer pipes allow you to get rid of drains, and both types of buildings require electricity. This duality between sewers and water towers allows you to create AND and OR elements.
Key participants, from left to right: a liquid fuel power plant, a water tower, a sewer pipe. Behind is a wind turbine.
The following shows how to construct the AND element. The two entrances are power lines leading to the water tower (above) and the sewer pipe (below). The output is a power line connected to a power plant. Although the inputs are zero in the screenshot, the power plant still generates electricity - even after the water supply is complete and the sewage works, it takes some time to stop. The buildings are far apart, because otherwise electricity could flow freely between them.
The AND element on a regular map showing layers of electricity and water.
For functional completeness, we need one more component: an inverter, or a NOT element. To create it, we will use the simulation of the dynamics of the fluids of the game. Improper use of dams, canals, or too heavy a load on sewers can lead to flooding of buildings. A flooded power station does not generate electricity. This is enough to create the NOT element shown below.
Above: the electricity layer of the NOT element; below: the sewage system turned off and on.
A 1-bit adder can be constructed according to the scheme of 9 different elements, shown below. Four of these adders can be chained together to create a 4-bit adder. I placed the gates in the grid to show how they would fit on the map.
The scheme of a 1-bit adder with a carry.
To simplify my life, I decided to turn on endless money and play on the map created in the map editor. You can import PNG images into the editor, which are used to load the height map. I created a map with blocks of earth on which you can place logic elements like on a printed circuit board ! This is what the map looks like. The images show four 1-bit adders repeating in a 2x2 grid.
Broken lines are visible in the image because the game doesn’t work very well on sharp edges.
Building a circuit is a very monotonous process, and I had to start over and over again because of my miscalculations. One of the problems I encountered is intersecting wires. Fortunately, power lines with a significant difference in elevation can cross each other without contact.
1-bit adder. I connected four such elements together.
Finally, I need to build a city nearby, creating a volume of drains sufficient to simultaneously flood up to eight windmills (yes, our computer works like a poop). But I would not call this decision environmentally friendly: each logic element uses a liquid fuel power plant, so the pollution level is quite high. Debugging was difficult: sometimes it turned out that thunder lightning led to the breakdown of power lines. She is like cosmic rays, but acts for a longer time.
A web of power lines leading to one of the 4-bit inputs.
I recorded a video to show that addition really works. In the first, I set a signal at the input by connecting it to a power station that is always on (like powering an integrated circuit). On the left, I set the value to 1001 (= 9), in the middle of 1110 (= 14). After setting the values of the inputs, I accelerated the game and the output on the right five wires took a value of one unit. After a long time, the final value was set to 10111 (= 23). And it really works!
In the second video, I focused on one of the adders. You can see how the state of the components changes over time until the final output value is established (0 - sum, 1 - transfer).
The project has some flaws. It will make a very slow computer - one 4-bit addition takes about 15 months of in-game time and about 20 minutes of real time. There are problems with the size. Due to the way power is implemented in the game, the components of the logic element must be spaced far enough apart; otherwise, current will flow between them. The 4-bit adder took up most of the 9 tiles available in a regular game, but I did not optimize it very much. Up to 25 tiles can be used with mods. If you have ideas on how to implement more efficient calculations, then write about it in the comments to the original article!
This game, like any other city building simulator, requires the player to supply electricity and water to the city. Power plants generate electricity, for this they need clean water and sewage. Water towers supply clean water, sewer pipes allow you to get rid of drains, and both types of buildings require electricity. This duality between sewers and water towers allows you to create AND and OR elements.
Key participants, from left to right: a liquid fuel power plant, a water tower, a sewer pipe. Behind is a wind turbine.
The following shows how to construct the AND element. The two entrances are power lines leading to the water tower (above) and the sewer pipe (below). The output is a power line connected to a power plant. Although the inputs are zero in the screenshot, the power plant still generates electricity - even after the water supply is complete and the sewage works, it takes some time to stop. The buildings are far apart, because otherwise electricity could flow freely between them.
The AND element on a regular map showing layers of electricity and water.
For functional completeness, we need one more component: an inverter, or a NOT element. To create it, we will use the simulation of the dynamics of the fluids of the game. Improper use of dams, canals, or too heavy a load on sewers can lead to flooding of buildings. A flooded power station does not generate electricity. This is enough to create the NOT element shown below.
Above: the electricity layer of the NOT element; below: the sewage system turned off and on.
A 1-bit adder can be constructed according to the scheme of 9 different elements, shown below. Four of these adders can be chained together to create a 4-bit adder. I placed the gates in the grid to show how they would fit on the map.
The scheme of a 1-bit adder with a carry.
To simplify my life, I decided to turn on endless money and play on the map created in the map editor. You can import PNG images into the editor, which are used to load the height map. I created a map with blocks of earth on which you can place logic elements like on a printed circuit board ! This is what the map looks like. The images show four 1-bit adders repeating in a 2x2 grid.
Broken lines are visible in the image because the game doesn’t work very well on sharp edges.
Building a circuit is a very monotonous process, and I had to start over and over again because of my miscalculations. One of the problems I encountered is intersecting wires. Fortunately, power lines with a significant difference in elevation can cross each other without contact.
1-bit adder. I connected four such elements together.
Finally, I need to build a city nearby, creating a volume of drains sufficient to simultaneously flood up to eight windmills (yes, our computer works like a poop). But I would not call this decision environmentally friendly: each logic element uses a liquid fuel power plant, so the pollution level is quite high. Debugging was difficult: sometimes it turned out that thunder lightning led to the breakdown of power lines. She is like cosmic rays, but acts for a longer time.
A web of power lines leading to one of the 4-bit inputs.
I recorded a video to show that addition really works. In the first, I set a signal at the input by connecting it to a power station that is always on (like powering an integrated circuit). On the left, I set the value to 1001 (= 9), in the middle of 1110 (= 14). After setting the values of the inputs, I accelerated the game and the output on the right five wires took a value of one unit. After a long time, the final value was set to 10111 (= 23). And it really works!
In the second video, I focused on one of the adders. You can see how the state of the components changes over time until the final output value is established (0 - sum, 1 - transfer).
The project has some flaws. It will make a very slow computer - one 4-bit addition takes about 15 months of in-game time and about 20 minutes of real time. There are problems with the size. Due to the way power is implemented in the game, the components of the logic element must be spaced far enough apart; otherwise, current will flow between them. The 4-bit adder took up most of the 9 tiles available in a regular game, but I did not optimize it very much. Up to 25 tiles can be used with mods. If you have ideas on how to implement more efficient calculations, then write about it in the comments to the original article!