MCBE 红石系统运行不完全分析(3)

时隔半年又一次更新

概述

这次主要说说红石系统是怎么构建出来的，这对红石玩家应该没啥帮助，唯一的作用也就是解释一下为什么有些无方块实体的红石电路为何产生卡顿。

在上一篇中给了游戏1gt更新的顺序表，这个表中的第18项也就是更新红石系统依赖是我没怎么提的，因为当时不懂相关的细节，这次把这个部分补充一下，讲述一下玩家放下红石和打掉红石游戏会进行哪些计算。

红石系统

首先必须清楚的是，在代码层面电路原件(CircuitComponent)和红石相关的方块不是一个东西，这两个是分别维护的，红石相关的状态都存在电路原件里面，和方块无关。每个维度有且仅有一个红石系统，这个系统存储了所有的电路原件以及它们之间的相互关系(相关关系上一篇中的无向图)，具体主要有下面这几项:

1. 所有的原件以及它们的位置
2. 所有的非充能方块
3. 每个信号源以及它们的下级原件(使用该信号源的原件)对应表
4. 等待移除列表
5. 等待添加列表
6. 等待更新列表

缓存

当玩家放下红石相关方块的时候，游戏不会立即将其变成红石原件，而是把目标位置放入等待添加列表中。同上，当玩家移除红石相关方块的时候，游戏也不会立即将红石原件移除，而是把目标位置放入等待移除列表中

处理

游戏在运行到第18项也就是更新红石系统依赖这一项的时候，会集中处理这三个列表(还有个暂时没说的等待更新列表)：

1. 遍历等待添加列表并生成实际的红石原件注意到红石系统中有各种各样的表,为了保证这些表的数据的同步,在增加的时候,这些表全部都要更新一遍,如果更新的原件附近有生产者和电容器,会把这些原件的坐标放入到第三个列表,也就是等待更新列表中.
2. 遍历等待移除列表并移除红石原件同上,为了保证这些表的数据同步,在移除的时候这些表也全部都要更新一遍,同样地会把附近的某些原件坐标加入等待更新列表中.
3. 遍历等待更新列表并进行实际操作等待更新列表是在添加和移除的过程中产生的,而且这个表里全部都是生产者和电容器.注意到生产者和电容器都是能提供能量的,因此我们也不难猜出这一步是要做什么,没错,就是进行电路连接的构建(也就是有向图的构建).对于表中的每个原件S,游戏都会以这个原件坐标为起点,以15为最深的搜索深度进行广度优先搜索,每搜到一个原件C,都会把S加入到C的信号源列表中,当前的深度也就成为了S和c之间的电阻，作为更新红石信号时候的重要数据。不同红石原件的连接特性也就决定了自己能不能被当前信号源搜到。除此之外，充能方块也是在这个过程中被发现和加入红石原件的。

问题

初看这些东西都没啥问题，很合理的算法。但是怪就怪在上面的原件信号源列表以及其它一些会频繁随机增删查改的列表的内部数据结构是vector.在vector上进行随机增删会产生不小的开销。这也直接导致了某些表面上平平无奇的红石电路实际上奇卡无比。