Incomplete analysis of MCBE redstone system operation (3)

A translated article

Overview

This time I will mainly talk about how the Redstone system is constructed. This should not be helpful to the Redstone players. The only function is to explain why some Redstone circuits with no cube entities cause lag.

In the previous article, I gave the sequence table for the game 1gt update. The 18th item in this table is the update of the Redstone system dependency. I didn’t mention it much, because I didn’t understand the relevant details at the time, so I will add this part this time. , Tell us what calculations will be made when the player puts down the Redstone and destroys the Redstone game.

Redstone system

First of all, it must be clear that at the code level, the circuit component (CircuitComponent) and the Redstone-related block are not the same things. These two are maintained separately. The Redstone-related state is stored in the circuit original and has nothing to do with the block. Each dimension has one and only one Redstone system. This system stores all the original circuit components and their interrelationships (the undirected graph in the previous article on the correlation relationship). The specific main items are as follows:

• All originals and their locations

• All non-powered blocks

• Correspondence table of each signal source and their subordinate originals (the originals that use the signal source)

• Waiting to remove the list

• Waiting to add a list

• Waiting to update the list

Cache

When the player puts down the Redstone-related block, the game will not immediately turn it into the original Redstone, but will put the target location on the waiting list. Ibid., When the players remove Redstone relevant box, the game does not immediately remove the original Redstone, but the target position into the waiting list removed in

Deal with

When the game runs to the 18th item, that is, when the Redstone system depends on this item, it will focus on these three lists (there is a waiting list that is not mentioned for the time being):

Traverse the waiting list and generate the actual Redstone original

Note that there are various tables in the Redstone system. In order to ensure the synchronization of the data of these tables, all these tables must be updated when they are added.

If there are producers and capacitors near the updated originals, the coordinates of these originals will be placed in the third list, which is to wait for the update list.

Traverse the waiting list and remove the original Redstone

Same as above, in order to ensure the synchronization of the data of these tables, all these tables must be updated when they are removed. Similarly, some nearby original coordinates will be added to the waiting list for updating.

Traverse the list of waiting to be updated and perform actual operations

The list of waiting to be updated is generated during the process of adding and removing, and all in this table are producers and capacitors. Note that both producers and capacitors can provide energy, so it is not difficult for us to guess this step is What to do, yes, is to construct the circuit connection (that is, the construction of the directed graph). For each original in the table, the game will start with this original coordinate, and 15 is the deepest search depth for breadth-first search, each search to the original, will put added to the list of the source signals, the current depth will become and the resistance between, as the update Redstone signal when important data. The connection characteristics of different Redstone originals also determine whether they can be searched by the current signal source. In addition, the charging block was also discovered and added to the original Redstone during this process.SCSCSc

Problem

At first glance, there is nothing wrong with these things, and the algorithm is very reasonable. But the strange thing is that the internal data structure of the original signal source list above and other lists that are frequently added and deleted randomly is the vector. Random additions and deletions on the vector will generate a lot of overhead. This also directly leads to the fact that some seemingly plain Redstone circuits are incomparable.

Source: hhhxiao