Game Cities: Skylines was Turing-complete: create a 4-bit adder
Cities: Skylines is a city simulation game that is hard enough to create universal logic elements in it. With the help of universal logic elements it is possible to construct any scheme, 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 based on these elements, so I will demonstrate a 4-bit adder instead. Everything is performed in the vanilla version of the game; neither mods nor additions are required.
This game, like any other city building simulator, requires the player to engage in the supply of electricity and water to the city. Power plants generate electricity, for this they need clean water and sewage. Water towers supply clean water, sewage pipes allow disposal of wastewater, and electricity is required for both types of buildings. This duality between the sewers and water towers allows the creation of AND and OR elements.
The main participants, from left to right: a liquid fuel power station, a water tower, a sewer pipe. There is a wind turbine at the back.
Below is a method for constructing an AND element. The two entrances are the power supply lines leading to the water tower (above) and the sewer pipe (below). The output is the power line connected to the power station. Although the inputs are zero in the screenshot, the power plant still generates electricity - even after the water supply is completed and the sewers work, it takes some time to stop. The buildings are far apart, because otherwise electricity could flow freely between them.
')
The AND element on a conventional map shows layers of electricity and water.
For functional completeness, we need one more component: the inverter, or the NOT element. To create it, we will use the simulation of the dynamics of game fluids. Improper use of dams, canals, or excessive stress on the sewage system can lead to flooding of buildings. A flooded power station does not generate electricity. This is sufficient to create the NOT element shown below.
Above: the electricity layer of the element NOT, 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 such adders can be chained together and create a 4-bit adder. I arranged the logical elements in the grid to show how they will be placed on the map.
1-bit adder circuit with carry.
To simplify my life, I decided to include infinite money and play on the map created in the map editor. PNG images can be imported into the editor, which are used to load the height map. I created a map with blocks of earth on which you can arrange logic elements like on a printed circuit board ! This is what the map looks like. The images show four 1-bit adders, repeated in a 2x2 grid.
The image shows broken lines, because the game does not handle sharp edges very well.
The construction of the scheme is a very monotonous process, and I had to start over again many times because of my mistakes. One of the problems I encountered is intersecting wires. Fortunately, the power lines with a significant difference in height can cross each other without contact.
1-bit adder. I connected together four such elements.
Finally, I need to build a nearby city, creating a volume of waste that is sufficient for simultaneously flooding up to eight wind turbines (yes, our computer works on poop). But I would not call this solution environmentally friendly: every logical element uses a liquid-fueled power station, so the pollution level is rather high. Debugging was difficult: sometimes it turned out that a thunderstorm lightning had led to the rupture of power lines. It is like cosmic rays, but it acts for a longer time.
A network of power lines leading to one of the 4-bit inputs.
I recorded a video to show that addition really works. In the first one, I set a signal at the input, connecting it to a permanently switched on power plant (like powering the 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 on the value from one unit. After a long time, the final value was set to 10111 (= 23). And in fact it 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 is the sum, 1 is the transfer).
The project has some flaws. It will make a very slow computer - one 4-bit addition takes approximately 15 months of in-game time and about 20 minutes of real time. There are problems with size. Because of how power is implemented in the game, the components of the logic element must be spaced far enough apart; otherwise the current will flow between them. The 4-bit adder occupied most of the 9 tiles available in a regular game, but I didn’t optimize it very much. Up to 25 tiles can be used with mods. If you have ideas on how to implement more efficient calculations, write about it in the comments to the original article!
This game, like any other city building simulator, requires the player to engage in the supply of electricity and water to the city. Power plants generate electricity, for this they need clean water and sewage. Water towers supply clean water, sewage pipes allow disposal of wastewater, and electricity is required for both types of buildings. This duality between the sewers and water towers allows the creation of AND and OR elements.
The main participants, from left to right: a liquid fuel power station, a water tower, a sewer pipe. There is a wind turbine at the back.
Below is a method for constructing an AND element. The two entrances are the power supply lines leading to the water tower (above) and the sewer pipe (below). The output is the power line connected to the power station. Although the inputs are zero in the screenshot, the power plant still generates electricity - even after the water supply is completed and the sewers work, it takes some time to stop. The buildings are far apart, because otherwise electricity could flow freely between them.
')
The AND element on a conventional map shows layers of electricity and water.
For functional completeness, we need one more component: the inverter, or the NOT element. To create it, we will use the simulation of the dynamics of game fluids. Improper use of dams, canals, or excessive stress on the sewage system can lead to flooding of buildings. A flooded power station does not generate electricity. This is sufficient to create the NOT element shown below.
Above: the electricity layer of the element NOT, 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 such adders can be chained together and create a 4-bit adder. I arranged the logical elements in the grid to show how they will be placed on the map.
1-bit adder circuit with carry.
To simplify my life, I decided to include infinite money and play on the map created in the map editor. PNG images can be imported into the editor, which are used to load the height map. I created a map with blocks of earth on which you can arrange logic elements like on a printed circuit board ! This is what the map looks like. The images show four 1-bit adders, repeated in a 2x2 grid.
The image shows broken lines, because the game does not handle sharp edges very well.
The construction of the scheme is a very monotonous process, and I had to start over again many times because of my mistakes. One of the problems I encountered is intersecting wires. Fortunately, the power lines with a significant difference in height can cross each other without contact.
1-bit adder. I connected together four such elements.
Finally, I need to build a nearby city, creating a volume of waste that is sufficient for simultaneously flooding up to eight wind turbines (yes, our computer works on poop). But I would not call this solution environmentally friendly: every logical element uses a liquid-fueled power station, so the pollution level is rather high. Debugging was difficult: sometimes it turned out that a thunderstorm lightning had led to the rupture of power lines. It is like cosmic rays, but it acts for a longer time.
A network of power lines leading to one of the 4-bit inputs.
I recorded a video to show that addition really works. In the first one, I set a signal at the input, connecting it to a permanently switched on power plant (like powering the 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 on the value from one unit. After a long time, the final value was set to 10111 (= 23). And in fact it 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 is the sum, 1 is the transfer).
The project has some flaws. It will make a very slow computer - one 4-bit addition takes approximately 15 months of in-game time and about 20 minutes of real time. There are problems with size. Because of how power is implemented in the game, the components of the logic element must be spaced far enough apart; otherwise the current will flow between them. The 4-bit adder occupied most of the 9 tiles available in a regular game, but I didn’t optimize it very much. Up to 25 tiles can be used with mods. If you have ideas on how to implement more efficient calculations, write about it in the comments to the original article!
Source: https://habr.com/ru/post/460233/
All Articles